基于Python实现的遗传算法求TSP问题

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
( L3 z/ e6 O+ B" k) s0 j1 v4 U目录
  j6 K+ p- l1 q2 _* j+ @% Z+ P* P4 K人工智能第四次实验报告 1
遗传算法求TSP问题 1
4 y( `- w( C  Y% V/ k( X一 、问题背景 1
1.1 遗传算法简介 1
, j; g: c# Z$ o; G1.2 遗传算法基本要素 2
+ z6 m; z6 ^5 K- ~* u) \1.3 遗传算法一般步骤 2
* k  T4 G* w3 H" m  S二 、程序说明 3
: `3 E3 z% |* e+ q2.3 选择初始群体 4
2.4 适应度函数 4
2.5 遗传操作 4
! s2 U- ~& ?) x% e2.6 迭代过程 4
  E2 b8 l& D: l! x# V+ Z/ \- v9 |$ r# @三 、程序测试 5
3.1 求解不同规模的TSP问题的算法性能 5
% C7 G1 x0 V& t- v! r& E3.2 种群规模对算法结果的影响 5
& h7 f. `, \' M% K! _: j& Y3.3 交叉概率对算法结果的影响 6
, o& N, h/ j+ i7 l# m% p3.4 变异概率对算法结果的影响 7
1 {! h# \+ c. L' r2 D0 ?- u2 f3.5 交叉概率和变异概率对算法结果的影响 7
四 、算法改进 8
4.1 块逆转变异策略 8
4.2 锦标赛选择法 9
五 、实验总结 10
一 、问题背景
1.1遗传算法简介
! T6 H/ O# T0 g2 S( l4 r0 E遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
9 l8 }0 j. a! z, O7 A0 @& {! L; _遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
7 y9 e# K0 T* v$ n- m7 O$ N1.2遗传算法基本要素
1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
* {' g. w5 `, _- [: S* p2.设定初始群体：
/ H' u' W5 A5 f& C9 N- p8 Y( R1.启发 / 非启发给定一组解作为初始群体
2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
4.设定遗传操作：
: J5 z2 J8 a1 V' `1 r2 @1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
2.交叉：两个个体的基因进行交叉重组来获得新个体
3.变异：随机变动个体串基因座上的某些基因
5.设定控制参数：例如变异概率、交叉程度、迭代上限等。
) R& ?  h1 y; ~5 ^2 A' J6 V. p7 F
import numpy as np
' d' Y  L  X- w- d& cimport random
6 \4 ^6 w' M3 v" l# c! Q" H, Fimport matplotlib.pyplot as plt
import copy
import time

from matplotlib.ticker import MultipleLocator
from scipy.interpolate import interpolate

: A2 P" N# J, ~1 {* Y1 k5 T" v+ OCITY_NUM = 20
! L8 p% i8 ]1 F( UCity_Map = 100 * np.random.rand(CITY_NUM, 2)
: ?% c- Z2 G& M0 R; u- K! U
DNA_SIZE = CITY_NUM     #编码长度
' a, E% T. y" i* x4 t- QPOP_SIZE = 100          #种群大小
CROSS_RATE = 0.6        #交叉率
MUTA_RATE = 0.2         #变异率
Iterations = 1000       #迭代次数

% i+ t/ |$ P) k, ]& Q/ _' j# 根据DNA的路线计算距离
& x) ^& I  u5 y0 i3 k% ^! I7 idef distance(DNA):
    dis = 0
4 T6 i: Q2 I. Y1 p/ z4 W2 ~) E# T    temp = City_Map[DNA[0]]
& }  u' m& m# B+ P- g! \' a% K3 B    for i in DNA[1:]:
        dis = dis + ((City_Map[0]-temp[0])**2+(City_Map[1]-temp[1])**2)**0.5
; ?) U+ M! F1 v1 b. g        temp = City_Map
" U8 i0 N% K7 M) [    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5
+ K4 C+ b" K3 c% |- {0 t% R
# 计算种群适应度，这里适应度用距离的倒数表示
! ?  c. U( m+ \- Q5 y; [8 tdef getfitness(pop):
    temp = []
5 n7 B. w9 u' z    for i in range(len(pop)):
: H, ~( p2 }" C& f& A1 u        temp.append(1/(distance(pop)))
    return temp-np.min(temp) + 0.000001

4 U( g1 Z0 j$ O6 h4 ?# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
def select(pop, fitness):
! H5 Q3 J# |) ]0 m8 V    s = fitness.sum()
2 l( j9 b8 p. V) A2 V    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
    p = []
    for i in temp:
        p.append(pop)
/ ]' k0 R# [" T7 {    return p
& l, ^! |5 {- f, P5 S- X1 L
# 4.2 选择：锦标赛选择法
; g6 e3 z. z* G- U# Ydef selectII(pop, fitness):
, r0 M' k5 o) N- _5 ^' g4 y& ^+ [    p = []
& r$ ~+ Q) w6 s2 |3 |& m9 s    for i in range(POP_SIZE):
, D) b8 N* P$ b0 y  F* F        temp1 = np.random.randint(POP_SIZE)
        temp2 = np.random.randint(POP_SIZE)
' p+ m6 ]+ S% _        DNA1 = pop[temp1]
        DNA2 = pop[temp2]
        if fitness[temp1] > fitness[temp2]:
% [; ^# S* g9 n3 g* q) \; j            p.append(DNA1)
        else:
            p.append(DNA2)
    return p
* f7 q% ]. P- I1 Z
# 变异：选择两个位置互换其中的城市编号
def mutation(DNA, MUTA_RATE):
) e# z, {* f/ B) w1 Y! Y  Q$ x    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
        mutate_point1 = np.random.randint(0, DNA_SIZE)
- e# e+ ~- ~* ]/ Y- @: A) ?) ~        mutate_point2 = np.random.randint(0,DNA_SIZE)
: r+ j4 v% k& U7 T2 a7 T        while(mutate_point1 == mutate_point2):
            mutate_point2 = np.random.randint(0,DNA_SIZE)
" l) O4 X  V- ?4 e9 M; l; O        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]
# {3 }7 y& m2 e& F: `; Z. O; t
* W6 X4 o0 b, b0 b# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
& ^+ L: ~8 q/ O2 E. S  N) a+ Bdef mutationII(DNA, MUTA_RATE):
% M4 P; y8 H/ Y2 z/ p    if np.random.rand() < MUTA_RATE:
        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0, DNA_SIZE)
        while (mutate_point1 == mutate_point2):
: W4 H* R# B7 P7 g8 O3 {            mutate_point2 = np.random.randint(0, DNA_SIZE)
        if(mutate_point1 > mutate_point2):
# x: E5 N1 L+ Z$ ?( M/ V$ e5 Q) x            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
        DNA[mutate_point1:mutate_point2].reverse()
( V6 L4 W0 Q$ V' f
/ u/ W3 |. u( X4 O( Q# D# 4.1 变异：调用 I 和 II
def mutationIII(DNA, MUTA_RATE):
    mutationII(DNA, MUTA_RATE)
6 t" `' P7 L! l; B    mutation(DNA, MUTA_RATE)
% q6 F' R4 x1 f$ B) ^7 P4 e) F! F, j
# 交叉变异
2 E, S* ]7 @( a* p: L# muta = 1时变异调用 mutation；
# muta = 2时变异调用 mutationII；
# muta = 3时变异调用 mutationIII
. F+ {$ ^! r( j2 cdef crossmuta(pop, CROSS_RATE, muta=1):
7 p0 h: s# f# i9 e    new_pop = []
    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
6 z4 R, W. _- J& w5 S        n = np.random.rand()
        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
            temp = pop.copy()
            new_pop.append(temp)
        # 小于交叉概率时发生变异
' }6 C3 q0 l9 J3 K8 }& ]        if n < CROSS_RATE:
4 g! l- s: Q" n0 Y4 R; r            # 选取种群中另一个个体进行交叉
            list1 = pop.copy()
            list2 = pop[np.random.randint(POP_SIZE)].copy()
+ H6 y6 E5 i: _: e7 o            status = True
. e( e  }; f! i  c0 {            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
            while status:
                k1 = random.randint(0, len(list1) - 1)
                k2 = random.randint(0, len(list2) - 1)
, [/ I' o+ E; ~7 f) n% B                if k1 < k2:
                    status = False
2 W  M4 [6 m; h* R
! s8 x  Y/ q8 b( N" N0 p! D5 t            k11 = k1

4 z3 r. w+ {7 ^% T) M' G2 x            # 两个DNA中待交叉的片段
+ L& P$ F( a6 S6 K: ?* i            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]

            # 交换片段后的DNA
            list1[k1: k2] = fragment2
! B% c, M2 t; U' b& [5 M5 p9 O            list2[k1: k2] = fragment1
" G# M8 g; p4 a; w
( \! F% A% R6 J  e+ h% d8 {, }% O            # left1就是 list1除去交叉片段后剩下的DNA片段
9 H1 k2 {" w( V            del list1[k1: k2]
: L9 U5 `7 N" N- y$ j" X, o, j            left1 = list1

2 d! K6 w% j9 s( i" M            offspring1 = []
$ ]( \1 O: n; e2 F2 C            for pos in left1:
( \( U: X# M3 A( j0 [. L' m                # 如果 left1 中有与待插入的新片段相同的城市编号
8 Z3 w8 H2 O! m+ f                if pos in fragment2:
$ L% p& Z! ~' e# s( ?& d# K& \                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
                    # 循环查找，直至这个城市编号不再待插入的片段中
- [& }. k* j7 p- [' O4 o$ O                    pos = fragment1[fragment2.index(pos)]
# q7 Q: Z* U. w# R1 ~4 ]                    while pos in fragment2:
* Q# J6 V( I; Z. H1 w5 V                        pos = fragment1[fragment2.index(pos)]
7 N8 h5 v# A: n6 ^( \                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
                    offspring1.append(pos)
' V( J3 U. r! q- V                    continue
                offspring1.append(pos)
$ _9 P6 Z8 }" J& Q            for i in range(0, len(fragment2)):
/ A1 U& S: ?( v6 C1 l! W& d" v                offspring1.insert(k11, fragment2)
' Q7 Q: Z" f, f$ x                k11 += 1
6 L% c3 s/ j" j+ I9 w! _2 {5 R) F            temp = offspring1.copy()
$ ]5 t4 D, L# s5 F: \            # 根据 type 的值选择一种变异策略
+ @, @( ?( I, G9 K: i6 p% A% ^/ y            if muta == 1:
                mutation(temp, MUTA_RATE)
            elif muta == 2:
                mutationII(temp, MUTA_RATE)
& S( a! b' j8 N/ \" S            elif muta == 3:
                mutationIII(temp, MUTA_RATE)
4 S1 D1 g; A( M$ j# ?$ m            # 把部分匹配交叉后形成的合法个体加入到下一代种群
+ a. v# {# a0 K0 Q) k; H            new_pop.append(temp)
& c* r2 b: C" ~" _, l% H% X; J
    return new_pop

2 r2 U3 u! ^9 z, ddef print_info(pop):
6 W: z8 h4 {: I6 L3 ]    fitness = getfitness(pop)
% v- J2 v8 v! j$ f; \9 Q0 B3 ?    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
$ _4 x. [' s- ]9 G    print("最优的基因型：", pop[maxfitness])
1 |) h7 ~3 u* m: x0 M6 w* H    print("最短距离：",distance(pop[maxfitness]))
! [6 Z0 ]* ^9 l7 V) m    # 按最优结果顺序把地图上的点加入到best_map列表中
    best_map = []
* {4 m2 o  f* K# }7 y% ~5 z    for i in pop[maxfitness]:
  J2 S: y- B6 b! J; R- D& ?        best_map.append(City_Map)
7 E: c7 V' ~6 _  I! K3 z    best_map.append(City_Map[pop[maxfitness][0]])
    X = np.array((best_map))[:,0]
( g7 P/ X# s4 K0 H! n    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
& j2 a/ z0 t+ b    plt.figure()
1 Z% @$ I& c9 ]6 h# I, c    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.scatter(X,Y)
    for dot in range(len(X)-1):
) K* f+ R8 [' x: e        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
( M  X4 n; O$ h$ U$ v5 m) l    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
5 a' l* C# {# S1 A7 L    plt.plot(X,Y)

# 3.2 种群规模对算法结果的影响
def pop_size_test():
    global POP_SIZE
- O9 s% a& ?2 N    ITE = 3 # 每个值测试多次求平均数以降低随机误差
8 R# w  E' U) I( |) t3 X    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
7 i, y8 z- g' Y9 G" p5 _' \. S9 f    b_list = []
    t_list = []
* }4 E# u: Q2 s    for i in i_list:
        print(i)
0 @" ^' B% W+ @$ y3 v* H1 E1 J# o        POP_SIZE = i
        time_cost = 0
        min_path = 0
( S) E6 \( k& u. i$ v1 I# L        for j in range(ITE):
            time_start = time.time()
            ans = tsp_solve()
& h7 M/ d' v( O2 r) \5 S" a, g            min_path += min(ans)
) q4 Y: d* j% [* S( ]            time_end = time.time()
            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
    show_test_result(i_list, b_list, t_list, "POP_SIZE")
" T' P3 C3 t; U$ j. F* w, X
# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
    global CROSS_RATE
4 z  @: X3 i, H  k6 K0 X- a    ITE = 3 # 每个值测试多次求平均数以降低随机误差
3 [1 P( _0 e3 u7 s; g% J    i_list = range(0, 21)
    b_list = []
    t_list = []
% I$ F) u+ y3 J) o4 Z+ N; M    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
        CROSS_RATE = 0.05 * i
        ii_list.append(CROSS_RATE)
        time_cost = 0
        min_path = 0
        for j in range(ITE):
            time_start = time.time()
4 B8 ~+ O; c5 ]; c/ G- s3 u8 m            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
  H' d9 m1 K7 s8 q0 W# O- V            time_cost += time_end - time_start

$ R) {/ Z* `: s; B" t# O        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
9 _; t- Q( G( x2 v8 H6 a6 M: f    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")

# 3.4 变异概率对算法结果的影响
( Y8 M% ?& w& x* Z9 T" W% Gdef muta_rate_test():
    global MUTA_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
% n" S. D' m# @$ c4 M# M    i_list = range(0, 21)
    b_list = []
! f9 b+ w7 g  ^& d" \6 Y    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
# D& ~+ ]- c+ N3 C7 [. s9 Z' C    for i in i_list:
        print(i)
        MUTA_RATE = 0.05 * i
        ii_list.append(MUTA_RATE)
1 R8 |) _& k$ `% p. p        time_cost = 0
- Y" u5 o; ?5 J. K# `3 i& O/ `        min_path = 0
        for j in range(ITE):
            time_start = time.time()
            ans = tsp_solve()
1 @' S" ^3 W& e* {3 x            min_path += min(ans)
            time_end = time.time()
' U7 w. g& _" J' r: ^, w            time_cost += time_end - time_start
8 |. ~. b" m( a# ?7 q
        b_list.append(min_path / ITE)
; t0 p: v' a1 T3 C        t_list.append(time_cost / ITE)
    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")

# 3.5 交叉概率和变异概率对算法结果的影响
def cross_muta_test():
    s = np.array([0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0])
    X, Y = np.meshgrid(s,s)
    Z = np.zeros(shape=(11, 11))
4 P6 \( y$ u$ c; @
1 V' T  P1 Q8 b& R    global MUTA_RATE
+ ]$ _- p2 w8 S* i$ n* I    global CROSS_RATE
    for i in range(11):
0 E; J& c$ V7 y- b+ O- ^, Y        for j in range(11):
            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
            MUTA_RATE = Y[0,j]
            ans = tsp_solve()
, i8 f/ A/ D/ `" J            Z[i, j] = min(ans)
' T9 @  w. ?7 C& ~3 J. W! p; V+ z
    ax = plt.axes(projection='3d')
. E2 W3 y4 L6 h, v; S    ax.plot_surface(X, Y, Z, rstride=1, cstride=1,cmap='rainbow', edgecolor='none')
    ax.set_xlabel("CROSS_RATE")
    ax.set_ylabel("MUTA_RATE")
8 l1 @. s: G0 v/ W    ax.set_zlabel("Shortest_Path")
, a. @6 U3 D! w! |* m    ax.set_title('TSP')
    plt.show()

8 ~& \4 m8 Q4 F1 {1 B/ h0 j% D% Q# 3.2-3.4 生成参数测试结果的可视化图表
: W9 E2 [/ A# F7 ?  rdef show_test_result(i_list, b_list, t_list, msg):
    ax1 = plt.subplot(121)
+ l0 j. F$ O6 l! \3 Z* C    ax1.plot(i_list, b_list, 'b')
    ax1.set_xlabel(msg)
    ax1.set_ylabel("Shortest Path")
6 n3 U- w$ K; ^6 `& P
    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'r')
    ax2.set_xlabel(msg)
& N1 E. j4 i, W  j+ l) C5 ]/ J    ax2.set_ylabel("Cost Time")
4 J* T0 x' i% n; ^( B0 y    plt.show()

. S% i0 w9 g3 Y2 K# 求解TSP问题并返回最大值
2 a8 Y7 h, ^1 b( T9 N2 i5 R9 v; [" m# muta 指定变异方式，sel 指定选择方式
! i: B$ C8 G4 \! M$ t! Gdef tsp_solve(muta=1, sel=1):
    pop = []
: u3 }8 r0 l$ @, u2 e8 t, k( a    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
" @7 M+ B: M& W: V2 u: w        random.shuffle(li)
        l = li.copy()
) V4 i# F4 u2 X4 }9 g6 d7 I        pop.append(l)
% C% M5 X, z+ f  @6 s/ Q    best_dis = []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=muta)
        fitness = getfitness(pop)
; ?$ e0 l" n; k- p) a( S- p        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
7 X* R. _4 V8 m7 N* t) ]        if sel == 1:
9 H# c4 A3 t: Q% n3 t' ]            pop = select(pop, fitness)  # 选择生成新的种群
        elif sel == 2:
. r+ c7 z5 n* @5 `# A. H% t' M            pop = selectII(pop, fitness)  # 选择生成新的种群

) f: G( {- I! m6 |1 c& L* o! B    return best_dis

# 4.1 块逆转变异策略对比测试
def opt1_test():
' A3 Q  }0 ?! e; l; Q    ITE = 20    # 测试次数
    i_list = range(ITE)
    b_list = []     # 每次求出的最短路径
0 o. @& s, q; _3 u, r. n. ]) @    t_list = []     # 每次求解的耗时
    b_listII = []
$ T+ O- R  w0 v- d. G0 e; W2 s    t_listII = []
5 S# U& a. i' D) Z) P    b_listIII = []
; Z* R) X0 [7 Y% }7 J/ A4 k    t_listIII = []

  B4 V& Y; {( t/ F& ^    for i in i_list:
( w* |  M. Z0 u$ `  B8 E3 C        print(i)
( ?  q( _9 a$ h        # I. 原两点互换异策略
        time_start = time.time()
1 d$ m5 U0 K' T        b_list.append(min(tsp_solve(muta=1)))
$ _5 @0 T! B( w. {2 u- m        time_end = time.time()
        t_list.append(time_end - time_start)
        # II. 块逆转变异策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(muta=2)))
        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
        # III. 同时使用上述两种编译策略
        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(muta=3)))
        time_endIII = time.time()
3 J' L# m: y3 V+ R/ E: G        t_listIII.append(time_endIII - time_startIII)
+ P. G# _$ A# m1 ^' P
    # 做排序处理，方便比较
    b_list.sort()
    t_list.sort()
, U  b0 X/ y; |) @6 E    b_listII.sort()
    t_listII.sort()
5 ~8 [9 B' k! r6 q. }    b_listIII.sort()
- A: y) `. L$ s( L  t$ C    t_listIII.sort()
9 \7 o% ?" `+ `# |2 z$ d8 e
8 P3 O. Y/ B- F0 j" E* x    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
    ax1.plot(i_list, b_listIII, 'g', label="Origin + Block-reversal")
+ _0 S, `7 ?. W5 g8 j# M    ax1.set_ylabel("Shortest Path")
& ~8 I- h: o# @9 n4 K! g# ]    ax2 = plt.subplot(122)
3 x3 S0 ~/ J) Y# R  S/ W    ax2.plot(i_list, t_list, 'b', label="Origin")
    ax2.plot(i_list, t_listII, 'r', label="Block-reversal")
    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
4 @  Z, {; o! J# Y& N$ H    ax2.set_ylabel("Cost Time")
  {( c- ?2 A6 f0 o* y& }0 @, Z    plt.legend()
: O$ h& C! F# A  Y    plt.show()
- z# N1 G3 W" k3 V6 W' F' w
: E, i. W" _* ]- j; [! @& ?6 ]# 4.2 锦标赛选择策略对比测试
def opt2_test():
- E; A7 ]. k( [6 R# k1 j' O    ITE = 20  # 测试次数
  i1 \% \, i7 i: F/ d/ M    i_list = range(ITE)
" r2 u+ q/ W& ^& s  W: {: e    b_list = []  # 每次求出的最短路径
    t_list = []  # 每次求解的耗时
6 e' |8 }4 G8 Q* g* b    b_listII = []
/ g: D9 W/ p7 d( C6 N9 k4 t    t_listII = []
1 @% [* x, c+ G  W7 d2 |& Q4 ?, e    b_listIII = []
    t_listIII = []
1 n. m1 ~& d3 V9 T  c
# Y5 U. l0 ~( H  B/ l    for i in i_list:
- D/ M: |5 t: S  H  J        print(i)
        # I. 原赌轮盘选择策略
        time_start = time.time()
        b_list.append(min(tsp_solve(sel=1)))
        time_end = time.time()
        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
        time_startII = time.time()
( \% a, \- w- o; J. n9 I; S3 t# ~        b_listII.append(min(tsp_solve(sel=2)))
! b% Z0 `6 h5 ~* }+ Z( V        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
7 @2 B7 p0 D( ?. B, C: D# k        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
        time_startIII = time.time()
. G+ z7 v5 y! b, V2 {7 t        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
; ~( p% s! V& R; Z5 c* s7 P5 k# k1 y        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
* u# p/ q3 V6 {
    # 做排序处理，方便比较
1 Q) Y6 q& @0 q3 r: }/ K    b_list.sort()
    t_list.sort()
7 O6 s! C; \7 \8 s0 W# G+ {# i    b_listII.sort()
    t_listII.sort()
    b_listIII.sort()
: g& ^* R4 L" T0 d. n    t_listIII.sort()
* J& H( D" P" f- [0 k! r
" I1 ?& [6 }& t0 x' W7 I) E8 {# V    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
4 L: L' A/ Q6 x& G    ax1.plot(i_list, b_listII, 'r', label="Tournament")
    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'b', label="Origin")
- G# B/ t6 W* t* E/ _' X+ o    ax2.plot(i_list, t_listII, 'r', label="Tournament")
    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
0 o7 C6 m# n" E/ {+ c    ax2.set_ylabel("Cost Time")
    plt.legend()
    plt.show()
3 G/ g9 b* J! c+ ?
# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
: K5 Q0 I# g4 E6 ydef ori_main():
$ Z$ C& @- D$ V' g/ b7 m& |$ Y# N: f    time_start = time.time()
    pop = [] # 生成初代种群pop
; `! f2 G5 N5 T' W    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
1 G! s" ]7 e9 O! G6 j8 G        l = li.copy()
( l' m" r; k; D+ z- l        pop.append(l)
! j# i6 Z$ d, P7 W    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
! k/ M$ s0 X3 P    for i in range(Iterations):  # 迭代N代
* W& ~/ w# Q' e4 V. ]        pop = crossmuta(pop, CROSS_RATE)
% l2 a) U3 z, U/ b9 n        fitness = getfitness(pop)
7 o( L5 J7 f: `9 e) v        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
" |: R3 N9 F3 m; H! G# T        pop = select(pop, fitness)  # 选择生成新的种群

4 J5 a( ^' o0 g( M' D, U    time_end = time.time()
    print_info(pop)
$ B- {) t" \# s: {0 `    print('逐代的最小距离：',best_dis)
% O- e% E& m" x8 x$ L    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
5 n' S3 X. s8 R* x# X* z    plt.plot(range(Iterations),best_dis)
& ?: O. T, ~7 @! W- y
# 4.1 块逆转变异策略运行效果展示
6 a. i* X! b' ^  y, n0 |. Xdef opt1_main():
    time_start = time.time()
    pop = []    # 生成初代种群pop
- k4 \8 V4 A8 `% u$ D0 j    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
. s$ d& ]8 Y  v- n! }* q        l = li.copy()
        pop.append(l)
    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
2 }  n/ }! a3 C4 ?% J    for i in range(Iterations):  # 迭代N代
$ O2 G( x( H6 p6 A* a        pop = crossmuta(pop, CROSS_RATE, muta=3)
        fitness = getfitness(pop)
# I- T: Z( H. X, x        maxfitness = np.argmax(fitness)
: r" ?9 b8 C: c$ Y# A- i) w        best_dis.append(distance(pop[maxfitness]))
& K. w3 Z9 N, X9 ~  d        pop = select(pop, fitness)  # 选择生成新的种群
2 I, j1 q# X; G
    time_end = time.time()
    print_info(pop)
    print('逐代的最小距离：',best_dis)
% Z7 d2 s4 N& N% H    print('Totally cost is', time_end - time_start, "s")
2 g. f, y8 ]$ S- T( o* Q    plt.figure()
& E( ~" k7 w' W. `2 x    plt.plot(range(Iterations),best_dis)

6 ]$ s8 n- o- B! @" F" [5 Yif __name__ == "__main__":
( Z; G% g! F2 j! q* Q7 B7 y
    ori_main()    # 原程序的主函数
2 H+ ^& g4 ^; Z7 z; k- Q    opt1_main()   # 块逆转变异策略运行效果展示
    plt.show()
    plt.close()
. ]" S, \. p$ L: |9 w) q8 O6 u
2 E$ N% }$ }& _1 n    # opt1_test()   # 块逆转变异策略对比测试
3 x- b2 {6 u  w' E! ~! [  @    # opt2_test()   # 锦标赛选择策略对比测试
9 O% m4 e4 u9 v
( H! J  G/ W! T7 a6 H$ G  F5 I3 r    # pop_size_test()       # POP_SIZE 种群规模参数测试
8 S8 b1 n3 J/ M2 x) u5 Y; h0 a9 O" V- f    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
    # muta_rate_test()      # MUTA_RATE 变异率参数测试
0 z$ ]6 y. J1 U0 `    # cross_muta_test()     # 交叉率和变异率双参数测试

  u+ p( k/ q: S( W
& g. S, c  d/ }, C1
& U- u1 ^: h; B1 B2
6 u4 ]9 i4 `$ J: E1 K- ^$ w+ {3
! |) Y  G7 f9 M, }) x/ F' Q7 r# j4
5
3 B/ f7 G$ m; x# h' X6
. e4 ]9 p% ^% z8 Q2 d) s9 _' I7
  y; b+ D4 N6 r8
9
8 F$ f$ Q: K0 o& Y6 s+ Y" W" _10
11
12
( u( y3 K% ?  H13
14
: L+ z, p' a+ e* e) l, m0 w15
16
/ r1 C- h+ O9 n7 i! p/ N' W17
  ]0 ~6 |4 l- ^! K6 O/ l18
! r& c* z9 l! W- l19
20
21
22
" U! [" R4 G2 U; |23
24
25
* l2 Y0 L) C9 ~. Y, U26
27
28
29
30
31
32
33
34
35
36
37
3 |2 t0 {0 T. z5 o0 [% y/ F38
39
. w& I, A' ?* k; C7 V40
41
42
& @$ H  U/ E1 E1 U2 q/ M: f! z% a43
2 u. f# \8 {7 z1 j6 S44
3 k) k" g2 t0 [  m! A& Z" X8 L45
46
4 X6 ~9 d0 h; M47
+ i. R/ a# y3 P* U) i48
49
% t, ?8 Y! r! ~  A* J50
51
52
53
54
55
  j) I& f) h  T2 T) j56
57
58
' {- v  D# ~# b0 z4 n59
60
61
62
63
64
; ^! Z5 {& Q4 b( o9 @65
66
. t( c( T. C5 G1 N, J7 p1 y67
  w2 ]6 D* z% p5 {7 S68
3 `8 o# i, E7 H% v/ b/ Z* c69
70
6 l% X; U' f9 ~/ K7 R  [* \: p71
72
4 g1 [8 M8 Q0 z# ?( T73
+ ]! J) y/ n+ Z; |5 k7 Z74
75
* U$ A8 k! G$ h% ^) O+ C: c76
77
4 J$ H& C; X  \. e  f( J! D6 {( R/ b78
. }: ~# `: e" g( x! L: ?79
7 Y4 @: H& U3 a' W. L4 U6 B80
1 x5 p6 x$ J. @' W5 E81
82
& Y7 `7 S3 y, Y, ~: t1 b83
6 s( B4 q( C% a4 K; s6 `- L# s84
  G9 T. q. L+ Y) P2 J2 d85
86
87
88
( W  W6 B+ N8 S0 F! v89
90
91
92
' N5 b4 l6 x$ Y5 F93
94
95
96
1 }$ `4 n/ a1 }' p( U3 V97
' s' C$ L6 G$ G" |' b4 t98
99
100
101
102
103
: ~3 r7 U4 w" a; o+ [104
6 g; t9 s2 W! }, e% l105
1 r( U9 M# Y% ]2 }106
* ^: F' M' p" W$ s# j  W107
108
$ j5 `4 X: v' q$ T4 R4 F8 p- U109
110
! F( P$ j5 J7 O; Z: v111
112
, x) \7 I7 d! ]  D113
/ }( |- w" \6 w. [4 J0 C114
3 ^2 z2 I! X: h, h' T( q/ X" S115
116
117
118
119
120
121
122
123
5 }$ w0 I; U9 b' J2 V2 z124
- l* M$ W) e) H2 i125
126
127
2 P6 }- I4 n: w128
129
130
131
132
$ W7 o& P. W$ w: `$ K1 O7 R133
; u6 R  P7 E: G* Q" L& j7 r4 d134
* J1 l: {* ^/ L% o+ q135
136
5 t: ]* P  Y6 ~8 `137
2 J5 V: v$ c/ T1 f5 o138
# u; V5 f: D7 b7 d2 T" Q* B) _139
/ h4 [; x' [* Q, D- A( K! O( S  z140
( {5 |0 a4 w' l% t8 ~7 F& a141
: q5 M1 e  k& m6 c% X142
. w: c3 [$ k5 Z" S* L7 l143
  U3 T$ v$ `  O$ O9 d- F$ L( ^/ E& G144
145
' h0 J, g4 w5 z8 A146
+ Q$ t1 `2 y* R9 A7 [147
148
149
150
151
# M0 f' j: U8 h( Z152
153
154
155
" d9 s* t5 w/ L- J/ S' ]6 X( g- y9 p156
- u1 I3 D. n6 i157
158
5 k/ M# f. S2 U7 }0 _! d) y159
/ M5 d  j1 z2 r0 I160
161
; P+ o, \2 D8 k# Z% e162
163
9 i* Q% g* b5 g& \; }* f164
- V9 b3 n4 ~1 }& N' g165
166
167
168
4 n5 |8 J6 k' A) E! U169
170
171
- h+ B% ~8 E% R5 t0 ], ?/ U+ m# r, O172
4 W1 Z$ Z6 }) y- @" Q. X1 y  w173
# ]) C1 J) N0 l' M6 }# I174
, a  j: R" o- e6 j3 m9 p+ `175
+ j# y0 _  F2 B176
5 J' U" U8 z2 _* G1 o' x( E7 v177
178
179
180
181
182
183
184
185
186
5 L1 o( ~. O+ K187
8 E( D- o9 q5 j  ~! e6 J* F188
$ ?2 `. `0 o9 m( N0 ~189
6 t! _# m1 n0 U% D9 L) a( R190
' C7 ^: g9 w$ n7 E$ V+ y191
192
193
194
$ X; {) ^7 m& C; j195
7 g" M. d, I1 I196
197
198
, {9 @, q) G  \: T- C$ Q199
* B8 M/ g( O4 K# H" v200
201
202
' ~/ K) r+ }* C) Q203
204
, X- S( z: b6 b$ D: s205
7 y' l* j) Q- b206
5 ~) r& i$ w! h% ^% F207
; i9 q% E  z* Y# A6 w! `+ f* n208
! k) H" I0 e, [: I6 _5 R( X% @209
210
211
0 ]9 v& i- T8 {5 m212
* }2 D8 Z+ B2 l# t' }$ i213
214
& h4 E4 R. [$ s: c: H1 L( ~215
" v" ]' x( g( V) f: d216
! E( O; U" j  F" e217
7 T3 x+ J7 }3 f( o$ o5 I. W9 \; g218
219
220
- l+ h/ L. g7 a221
222
223
- h& n1 K; _# B. \/ f224
225
. a/ _; A& s* J+ @' _# V1 ?226
227
) ~3 A0 `! f" h$ _228
229
230
% l8 c% V, i& F: @) x231
, W$ p% s( w" i1 t4 {232
233
" n7 O0 j' Z" g+ @234
235
) @; D$ I8 }" U  Q8 N+ K/ d236
1 ?% Z' L* \9 [; o: A$ p237
7 M, \9 q% ^6 p238
: |8 G6 M; s/ l  Q239
4 N1 d( W* N* G9 n) m4 z240
241
242
243
244
245
246
+ O  I5 |5 d+ }2 E* ]247
248
249
4 P& T2 m2 R5 _+ G& ]7 \250
: `/ F6 G7 j7 v# `2 w# S251
& M! I, W' F" f252
, k/ X( \' N8 B5 `( H) T253
254
255
- A" ~: n- ^- {0 l256
/ M- {$ P& ^' N257
5 w+ q0 E( d& [% d% ?# l3 C( W258
259
260
( X1 L& H, s7 B3 t261
: \' s" o' J% G( ?1 g! M+ }262
6 g, X9 |+ N  E- {+ ]! ]) A6 d263
264
9 ~6 z7 ^$ c) v% F: u) z9 e265
266
) q1 ?. s/ p/ m/ ]6 j3 L3 w267
268
269
+ V& X# H8 s; k1 n3 L3 ^270
271
272
* r& R3 A  [6 X! [; y! d: r273
274
275
' j, P# J! O' t; f276
" o+ C* `2 v5 I7 s( C277
278
279
+ w* r6 t/ Q& x. B8 o* [8 j280
281
282
283
5 }, g: }& S. c284
/ J+ S4 U5 Q9 B+ M7 s5 j285
286
287
288
289
290
; r$ j( I6 @8 f, o; C* J291
5 E- g) f$ g* ]( e& G& b292
" E4 w# f$ `# h$ }+ L293
- c' t5 k% d( T. h2 O! C$ e294
- R' r9 l7 G5 _! ]% E295
0 z5 f/ x: r# s, [. o6 A" r3 A296
, }+ M4 [/ p+ }" @" b% {( P- p297
" G; k% h' G4 l  L298
0 z6 W& L6 {1 h/ j4 ]9 N" L# j299
. Y" ~  T; l! ]& z300
8 @& {9 P: ~3 U301
302
8 d1 G; U& ~8 T, O( e7 d9 J303
304
305
306
307
308
309
7 I  R! Z7 [# s; `/ ^310
+ @9 ?6 ]+ f. t  |* P6 j' e311
312
313
0 N/ [( {8 o4 ~# }. k314
. }3 e5 x0 C& e6 N0 K- [315
1 M) C! U, O) O: a( h; C/ v316
317
8 ?! Z  |2 f% Z* z$ u) v, Y6 Q318
# H+ q5 x  t1 j319
320
321
$ q# _! b. X4 u& N8 ~1 ^1 Q  i* S% y322
. w# z8 q2 a. u! P# q323
324
325
/ Q  m( S' }4 [0 }& x326
; ~4 Y1 J# N4 Z, X6 \0 x+ T: ]1 L327
: _* B4 H% r, m9 ?8 |1 M* z5 v328
$ X- P2 f% ^9 ?6 P. h9 |329
9 ?( v' a/ n( c& g330
9 [% z' @# x% h+ U, U) \* \331
4 U, t7 W! W5 o: E. T7 @$ J( D! k332
6 h( [( I$ P/ R4 `; s. ]333
+ h! ]. R' Z2 b% l# Y) V# m" y$ t  Y334
4 K3 k( e! O/ h: m% \8 [335
336
- T2 D2 W, P7 s9 r' b337
) d3 f) [! k6 l  h* G  v* `338
. T! m2 o& v& k7 }2 K' |/ |: A339
8 @8 _6 W! I: n2 V6 x9 m# N# a/ E340
5 x3 d8 d/ j; l/ s# z$ ~341
( b3 @0 {) L6 Y  u1 m9 m& W342
. L% F: H* N6 @# t" m; }343
344
345
6 S! |9 j, |$ s( q! m$ j3 j# K346
347
! Y. ^: W! f: B2 A5 h& R7 a348
6 N& Y2 ~& \' E) b1 Q+ g349
8 u0 }* h" z, S0 Y$ l7 U( n) g8 S350
351
352
353
354
355
/ `7 {( ~7 ^; F; w8 Y356
& x! Q0 C0 g" D; p. i5 T357
8 o9 g! p4 x8 A! x8 @8 S. a4 H( b7 @! M358
: k# a% A: {3 j359
360
361
362
363
) G2 E) z" k  A# |  Z1 j0 L+ |; p9 K364
6 f' e+ I; n# A" M365
( `5 S# B; W3 e" x0 R9 k* L0 J366
367
368
( S* j+ I  d6 o369
370
. h) V6 U+ r) Y371
372
( a; v+ |/ ?! i$ |373
5 y' v% ?4 q' T7 c- i5 e374
375
376
377
378
" q! C4 }4 j8 P4 R379
380
2 q$ p+ h# [! k- G8 J. X381
" V* `) Q* A  G5 M3 T% ?382
383
384
385
1 F; G! t5 _* Z) P( c) g  R6 `( z# Y386
387
# Q6 O% x  V% ]% [# G0 d& {% s/ [388
" n0 h+ W) o6 R* p  L  n4 g389
390
391
392
393
: j6 z0 l' J+ m; t3 _/ F& ^( V394
: r# f7 u6 p9 ~; X7 |" e# [- E# T0 r395
6 Z4 V  H: r  Y* ]396
397
2 o7 |! D0 i; V398
" |" H' _  q+ _  F399
400
401
402
, i$ h+ g. ?8 n, P$ L- d: g( I403
2 M* e3 M4 L# C1 P7 [* \3 `, Y404
405
406
407
# s  ^! \$ m# g" G. O0 E408
409
/ F) E) ^0 A# ~! X; A5 f410
  Z; ~0 B6 G& O. p411
412
413
- u, T8 Q; \  L. J7 D414
415
416
* b! X) P, ^, L4 s417
0 F( ^, J; E: X, t2 u5 b# C418
$ g# K3 U2 }- M2 a% {4 g1 A8 _$ \- S419
3 l  x/ ^" ~+ @- f" F420
: ]8 k  j# }( |5 Y2 s, z421
$ T3 h7 m2 t% H; I422
  _$ w7 _, m' y5 [423
424
) T6 p  k. ~1 u425
1 j* y8 _. Y- \4 T" {0 {; K6 S) m" U& j5 i426
$ a$ ?/ D& T2 W427
428
! h1 w' f2 @. h429
430
3 R6 S- }  t) d" D2 ?431
432
% v" Y& x, X( P; t, N1 N+ T433
434
435
436
) @( E* G8 M( Z% G  Z0 ~4 X; M" w437
# Q. G! M* V: ^0 R$ ?438
439
8 ~; C0 A  r4 v. B) k* V  u2 t440
441
9 c6 x. `1 M3 R/ L5 n442
443
444
6 G7 k0 B" `  T9 U; L0 @  x445
446
447
448
449
! q& h. L6 Q9 e( C9 @0 i8 Z450
. G: H+ Y. ^2 O8 E451
9 }8 R: O8 }1 n. ?& `452
453
7 u0 {, m$ v) r1 e454
455
456
) `3 C' [, Y! }& ^/ j8 U; h457
2 h1 [/ L6 u- I; Z" X* H$ A! S! T3 S458
4 v9 `0 n; D# b' e6 f459
460
! W- U  K8 n) z2 `6 n1 B! t" O' ~461
462
% Q2 o9 q; ]* A! m& c4 X  i463
. I' ^8 R! `/ b# A464
1 b% W& J3 ^% k- L465
466
4 J: [; N" e* F) s467
% k5 }( J' K: {( G  U: g468
469


& x' h) o1 W, W
2 y! R" B( d0 f$ s

6 |* Q7 N$ f5 q
$ p( v& ~7 a& q! p% {4 ^
6 A8 O2 l- P5 ?  z( }% f7 S% ?. I

# Z: v* E& j. g8 [3 |, w! U8 I

( Z' S' Q, W6 [' q5 t( }  y& L

  \( N$ x9 `" J- r1 J* |. ~9 W" f


! n( E! n  S( p


+ C& p$ k  {  h7 J# d
0 ^  \0 _/ Z/ x9 s- Z

* t* K$ w4 C$ D6 D6 q" H& e6 s


, w1 t/ F. Z* v  }+ c
% F& a# U  |1 N: B
1 x9 B7 X9 K8 r6 [/ N————————————————
* a3 I" j/ B/ j版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212


! z0 q1 i/ L0 c$ F% U  M3 B
; k6 z6 N! `+ ^( q: z; D; ]