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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
目录
人工智能第四次实验报告 1
: t1 Y' O) D8 G' k5 N遗传算法求TSP问题 1
一 、问题背景 1
1.1 遗传算法简介 1
1.2 遗传算法基本要素 2
1.3 遗传算法一般步骤 2
二 、程序说明 3
$ s5 p% j8 b/ D; A5 I- B2.3 选择初始群体 4
2.4 适应度函数 4
! g! d3 G9 d2 }/ @2.5 遗传操作 4
6 S! L! n  u- q* }- K% X8 h  \" B2.6 迭代过程 4
; J5 q, w% }2 e" A) ~4 B' }$ D5 |三 、程序测试 5
3.1 求解不同规模的TSP问题的算法性能 5
4 y5 |# |. P- y7 r! d3.2 种群规模对算法结果的影响 5
5 {7 [8 U0 ~* X+ `5 E3.3 交叉概率对算法结果的影响 6
0 \! Q$ v1 x/ m! C" P3.4 变异概率对算法结果的影响 7
7 X; u9 l6 G- X4 i- L3.5 交叉概率和变异概率对算法结果的影响 7
8 W) H% Y; i- U6 M/ @四 、算法改进 8
7 X# X: |1 j4 J; l: e$ K( P4.1 块逆转变异策略 8
4.2 锦标赛选择法 9
五 、实验总结 10
1 @9 @; N: @+ q2 d一 、问题背景
1.1遗传算法简介
遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
, X! R2 K' |3 Y6 o( P* Z遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
1.2遗传算法基本要素
- W2 l" [) I( t) T6 e8 H$ P* ~# O; J1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
2.设定初始群体：
1.启发 / 非启发给定一组解作为初始群体
2.确定初始群体的规模
6 m: y; K5 s9 I' K. a9 [1 @3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
& S9 g7 ]% p, b( E( Y" h/ ]$ g4.设定遗传操作：
1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
0 r: e+ U6 u! A- X! R: Q# r  [2.交叉：两个个体的基因进行交叉重组来获得新个体
+ m3 M; ]* ?5 @3.变异：随机变动个体串基因座上的某些基因
- x" d( I( I4 K8 T. D/ F5.设定控制参数：例如变异概率、交叉程度、迭代上限等。
7 |6 f# O" e# W7 N% u$ j
import numpy as np
import random
import matplotlib.pyplot as plt
import copy
9 f7 P/ [2 c7 v9 dimport time

from matplotlib.ticker import MultipleLocator
5 [5 i+ G1 t+ l1 J" ~  |- [( |from scipy.interpolate import interpolate

CITY_NUM = 20
City_Map = 100 * np.random.rand(CITY_NUM, 2)

DNA_SIZE = CITY_NUM     #编码长度
, I% c* `( P2 k0 C5 kPOP_SIZE = 100          #种群大小
CROSS_RATE = 0.6        #交叉率
MUTA_RATE = 0.2         #变异率
Iterations = 1000       #迭代次数

# 根据DNA的路线计算距离
5 F3 `8 @& H- c7 s: a3 Adef distance(DNA):
9 `7 `% Z+ o8 U9 U- E    dis = 0
$ d$ `1 n% W. P3 F    temp = City_Map[DNA[0]]
0 @& V$ R6 j7 O/ K) j    for i in DNA[1:]:
        dis = dis + ((City_Map[0]-temp[0])**2+(City_Map[1]-temp[1])**2)**0.5
        temp = City_Map
    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5
( _2 z( o3 H$ p7 Q0 c
, i2 C$ L% g& G1 m* X# P& Z# 计算种群适应度，这里适应度用距离的倒数表示
def getfitness(pop):
    temp = []
    for i in range(len(pop)):
        temp.append(1/(distance(pop)))
3 W- }9 A6 F- V+ o8 g    return temp-np.min(temp) + 0.000001

# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
def select(pop, fitness):
    s = fitness.sum()
    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
    p = []
    for i in temp:
' H$ z4 B) o2 [! P        p.append(pop)
8 I" x/ ~1 w5 V6 w& w0 C; f    return p

# 4.2 选择：锦标赛选择法
: D& Q# O* o2 k5 @" ?* Tdef selectII(pop, fitness):
    p = []
) x, M! b/ u" e2 V* z7 E    for i in range(POP_SIZE):
( t/ h( L+ p: W2 C# O6 R) x& p        temp1 = np.random.randint(POP_SIZE)
        temp2 = np.random.randint(POP_SIZE)
3 ?* g" Z$ L  I        DNA1 = pop[temp1]
        DNA2 = pop[temp2]
        if fitness[temp1] > fitness[temp2]:
4 ^5 T  h8 K% y            p.append(DNA1)
& o3 `' H, P2 }% i! N( V( P2 o        else:
  Y9 y& F; H; m1 _( k            p.append(DNA2)
    return p
" V! l+ F5 T% n( o, B6 K: Z
/ i4 R% d( e. b& a% v, d1 B# 变异：选择两个位置互换其中的城市编号
6 S( p* [( ]3 g9 I, odef mutation(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
. z0 x: R3 r3 @8 [, O8 \        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
, @$ T: R2 ]; ]+ w        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0,DNA_SIZE)
% F' _3 L) D0 F1 Z- W1 _& p        while(mutate_point1 == mutate_point2):
$ a" x, @# x, Q5 r7 U5 P7 g            mutate_point2 = np.random.randint(0,DNA_SIZE)
% R) Z2 L+ Z8 e! M9 q2 B- \6 y        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]
/ W/ [8 t( D7 L$ X  o% L
# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
def mutationII(DNA, MUTA_RATE):
9 s& v: F/ u2 C, y    if np.random.rand() < MUTA_RATE:
  f9 y2 E5 c& @4 T- U        mutate_point1 = np.random.randint(0, DNA_SIZE)
8 z' C4 @+ R4 m+ ?8 N        mutate_point2 = np.random.randint(0, DNA_SIZE)
        while (mutate_point1 == mutate_point2):
            mutate_point2 = np.random.randint(0, DNA_SIZE)
        if(mutate_point1 > mutate_point2):
            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
4 S; [$ j% M' ?% f4 a        DNA[mutate_point1:mutate_point2].reverse()

) W9 I2 v% \0 h" M# 4.1 变异：调用 I 和 II
& U+ Z' A6 X1 T( \def mutationIII(DNA, MUTA_RATE):
    mutationII(DNA, MUTA_RATE)
    mutation(DNA, MUTA_RATE)
- P7 j& V. _1 e
# 交叉变异
# muta = 1时变异调用 mutation；
& Q, J5 I' p& F. m: k! B# muta = 2时变异调用 mutationII；
) W4 o- V8 l( b+ I& J2 o# muta = 3时变异调用 mutationIII
* [; H6 W& w: ?* i% a, [def crossmuta(pop, CROSS_RATE, muta=1):
3 `4 f* `! k. ?" S+ h    new_pop = []
    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
        n = np.random.rand()
4 P9 A5 d6 k+ i        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
            temp = pop.copy()
' d% I$ @) j4 W            new_pop.append(temp)
        # 小于交叉概率时发生变异
9 m8 U* F; p: V, b. C4 ^* b        if n < CROSS_RATE:
! L  C- v0 c* O+ u8 A$ [            # 选取种群中另一个个体进行交叉
            list1 = pop.copy()
            list2 = pop[np.random.randint(POP_SIZE)].copy()
+ ^& N" k' Q4 W/ F: X9 n, g+ U7 N            status = True
& k7 C. O: h2 ?            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
: w3 Y$ }8 P! ^5 Y7 g            while status:
* U4 F2 T' ^4 W3 u7 t                k1 = random.randint(0, len(list1) - 1)
* x9 Z, k( b9 ]; A: u4 a" E                k2 = random.randint(0, len(list2) - 1)
. I7 z! u" v& m9 Y4 `& |: [                if k1 < k2:
                    status = False
( O/ v0 c0 l5 O0 t* C
% n% i0 U6 }; u+ r. I+ B! X8 ~            k11 = k1

            # 两个DNA中待交叉的片段
0 w/ T) D" B* T6 K: c            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]
0 s. W9 [6 G! J, p" {
# A' p7 N+ Y7 n" H0 G6 e- A% @            # 交换片段后的DNA
' m+ V$ F2 E' w            list1[k1: k2] = fragment2
            list2[k1: k2] = fragment1

            # left1就是 list1除去交叉片段后剩下的DNA片段
            del list1[k1: k2]
            left1 = list1

            offspring1 = []
0 A) B' T/ |! v) L+ J, E            for pos in left1:
                # 如果 left1 中有与待插入的新片段相同的城市编号
                if pos in fragment2:
                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
  ^6 }0 }! _( v- m: ~5 k( V                    # 循环查找，直至这个城市编号不再待插入的片段中
                    pos = fragment1[fragment2.index(pos)]
9 M# F% n! z) K7 X% N( C( \! k! }7 {                    while pos in fragment2:
. T. Y1 o- u" l# ?9 V! j                        pos = fragment1[fragment2.index(pos)]
                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
1 f  Y3 ~, l1 M/ V6 v                    offspring1.append(pos)
                    continue
                offspring1.append(pos)
% p7 Z, X9 t3 P            for i in range(0, len(fragment2)):
                offspring1.insert(k11, fragment2)
. P6 Z, B, s9 @. S& [1 V3 D" q, `                k11 += 1
+ v4 K2 `( o% l8 m            temp = offspring1.copy()
" \% \" O( q3 M- z4 N) e7 B5 u            # 根据 type 的值选择一种变异策略
8 F; d0 j, o( h; l9 G+ S: g& F' k. C' Y            if muta == 1:
/ N+ y9 x2 w  ?4 Q                mutation(temp, MUTA_RATE)
- A" s& F, O; ^) |2 t3 g7 _) l            elif muta == 2:
                mutationII(temp, MUTA_RATE)
8 h0 o( z5 m) _            elif muta == 3:
                mutationIII(temp, MUTA_RATE)
            # 把部分匹配交叉后形成的合法个体加入到下一代种群
            new_pop.append(temp)
8 K$ q9 i& ?& [0 ~, L( W
) ~1 l  q2 @( H    return new_pop

8 \$ o8 E- e) ?- ^- tdef print_info(pop):
    fitness = getfitness(pop)
2 t1 E9 E* Y; E+ g$ [. A    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
    print("最优的基因型：", pop[maxfitness])
. g" j, t6 B. A1 z  W5 X  l& h; j    print("最短距离：",distance(pop[maxfitness]))
# o- k. R0 _% W: z4 @; ^' ^6 y    # 按最优结果顺序把地图上的点加入到best_map列表中
    best_map = []
; I, a1 |4 ^+ n    for i in pop[maxfitness]:
        best_map.append(City_Map)
    best_map.append(City_Map[pop[maxfitness][0]])
% C7 ~' D, J' ^' d2 K5 U$ U# r    X = np.array((best_map))[:,0]
" E0 a& G4 f! e3 F7 V    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
    plt.figure()
8 h- I, q5 W% ~9 d1 V( W( @    plt.rcParams['font.sans-serif'] = ['SimHei']
  s. E3 i0 v  d$ R- z    plt.scatter(X,Y)
2 s  e* m) W( \    for dot in range(len(X)-1):
/ J9 G+ _0 @1 G1 L9 O1 n! F        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
0 k( Z6 G+ s2 w0 m! G9 l$ x    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
    plt.plot(X,Y)
: D- h( v! L; z5 h# N" S8 F
9 Z! I( B" c; [/ \; F, H% Z# 3.2 种群规模对算法结果的影响
2 g' G( q/ m; p4 ~. q' R, W( s2 pdef pop_size_test():
    global POP_SIZE
, e+ w- x1 N, L% ~! K, g$ D    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
    b_list = []
    t_list = []
6 n2 r5 {' b0 M* [    for i in i_list:
        print(i)
1 R" ~8 j! Y6 u        POP_SIZE = i
$ a2 Q7 z8 `( O2 K  {9 q' s& h        time_cost = 0
        min_path = 0
        for j in range(ITE):
4 O8 _$ x) r1 n3 X) C            time_start = time.time()
6 v# i$ l( y/ U! }7 ~            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
2 w+ [2 d3 [) j6 y! V            time_cost += time_end - time_start
: `$ S# H" Q* o- ]* Y+ e+ G% @
        b_list.append(min_path / ITE)
' p$ n: R# R% r+ ~5 k        t_list.append(time_cost / ITE)
* G  _+ ?* X- U7 k# R; B    show_test_result(i_list, b_list, t_list, "POP_SIZE")
5 T2 R; i8 [9 _5 d9 Y
; `9 V, G4 A& p# X# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
    global CROSS_RATE
6 P" P5 h* X5 `% e& x. s; a    ITE = 3 # 每个值测试多次求平均数以降低随机误差
5 m; V2 j% [6 o9 {- ]' l    i_list = range(0, 21)
    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
0 \5 u! w3 X* w# G( z5 E/ H, T    for i in i_list:
! G* T$ v5 }6 N  U8 ?        print(i)
) W- e9 S0 N6 n0 I* a- j        CROSS_RATE = 0.05 * i
        ii_list.append(CROSS_RATE)
        time_cost = 0
        min_path = 0
        for j in range(ITE):
0 v1 h' H2 r6 p! i. I8 z            time_start = time.time()
            ans = tsp_solve()
6 v) H# y# p4 p' o0 z            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start

$ a0 w2 ^! `9 N0 q7 @  D        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
) F* [+ C/ G+ }7 K5 Y    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")
# J  b+ ^$ U# }; I' P
7 m% V5 |) t$ p9 f2 w7 t# 3.4 变异概率对算法结果的影响
1 o! P4 W4 u% R. t5 L' z. s0 g- pdef muta_rate_test():
" d5 M  C( ~% u" t; S    global MUTA_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
! O, U* b& v4 J    i_list = range(0, 21)
  _- K0 d  }9 t) u    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
5 H3 h2 w0 T( Z; t3 K        print(i)
  {- A1 a9 G! V. o8 b0 I2 }( ?' s        MUTA_RATE = 0.05 * i
) I9 R% ]) k6 J2 j! P        ii_list.append(MUTA_RATE)
        time_cost = 0
        min_path = 0
        for j in range(ITE):
            time_start = time.time()
" a. J5 a- D  r+ l& d1 d4 _6 l. d            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start
  y$ o# b. H) }: Q. c6 d  p4 C
5 }, W0 {+ V6 A        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
- K; l9 \5 K" C  ^    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")
" J0 i0 i  I4 H  j1 G: B  I
/ u- w# W2 D0 ]1 N& t; n# 3.5 交叉概率和变异概率对算法结果的影响
8 f1 L) ?% o; ]4 k6 adef cross_muta_test():
5 l0 P& H6 _% Z3 X  n/ H1 R; M    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))
9 B% N8 [+ h( X8 |- w. r/ I
    global MUTA_RATE
    global CROSS_RATE
    for i in range(11):
+ ]& H& T. `& s, Z' m8 w, N        for j in range(11):
% m1 ?1 B' _! M. i# y            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
, `4 K6 b0 E& P            MUTA_RATE = Y[0,j]
5 \+ S' H4 q" l8 {) W            ans = tsp_solve()
            Z[i, j] = min(ans)

% Q6 o# l' v& z  X, w- O( a( V. e, S" |; G    ax = plt.axes(projection='3d')
  G: o/ c. `6 D    ax.plot_surface(X, Y, Z, rstride=1, cstride=1,cmap='rainbow', edgecolor='none')
    ax.set_xlabel("CROSS_RATE")
: A; v' C! P& I( w    ax.set_ylabel("MUTA_RATE")
    ax.set_zlabel("Shortest_Path")
$ G- y( A& M8 q    ax.set_title('TSP')
    plt.show()

4 `& K) b, Z/ T' w+ }% m1 }# 3.2-3.4 生成参数测试结果的可视化图表
+ i5 K) x; g: T  z( X4 k3 D9 rdef show_test_result(i_list, b_list, t_list, msg):
9 ^) G2 B5 J; b+ _* G# C    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b')
$ }; r# [$ a/ Q. ]. n    ax1.set_xlabel(msg)
! G9 z  b: k4 O1 R    ax1.set_ylabel("Shortest Path")
8 V) x' Q7 G; {. o- Y
    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'r')
    ax2.set_xlabel(msg)
    ax2.set_ylabel("Cost Time")
    plt.show()

' w5 |: t: |5 W9 D- j# 求解TSP问题并返回最大值
) \' Q& g5 p  w- g' j: t" L" y- U2 W# muta 指定变异方式，sel 指定选择方式
def tsp_solve(muta=1, sel=1):
    pop = []
    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
" P% Y. P/ T% H! B; c4 z; o8 a    best_dis = []
3 J* S9 t* I; j, H  r; l0 E    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
* S# h8 ^; D& u& g9 M7 d; C6 A3 n    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=muta)
9 r& v6 z. ^: W# g4 _. L        fitness = getfitness(pop)
) F0 t) t- Q+ ^. B        maxfitness = np.argmax(fitness)
- |/ t: z9 X, F$ C5 y$ P0 t        best_dis.append(distance(pop[maxfitness]))
        if sel == 1:
: U# e) b# U& }/ b6 ~# [            pop = select(pop, fitness)  # 选择生成新的种群
% `5 J2 K2 ?/ X        elif sel == 2:
            pop = selectII(pop, fitness)  # 选择生成新的种群

" n2 _- O. i/ u) ?' x, c9 h    return best_dis
" \  `$ N  p) B
# 4.1 块逆转变异策略对比测试
, J( [1 S+ W0 q" u. \7 D5 Idef opt1_test():
    ITE = 20    # 测试次数
  h3 {. s, C% `4 s# a    i_list = range(ITE)
4 |$ @* _; h% n3 i4 }    b_list = []     # 每次求出的最短路径
    t_list = []     # 每次求解的耗时
    b_listII = []
    t_listII = []
' v3 D* f1 \$ K+ r: \    b_listIII = []
    t_listIII = []
6 T8 M- \/ y1 ?1 d5 b6 Y7 w
    for i in i_list:
- Q, A. ^! ]0 p6 N! D6 F) f        print(i)
2 c: D6 h2 y2 Q5 v+ z6 G" }; Z4 c        # I. 原两点互换异策略
        time_start = time.time()
' Z9 }+ J9 i7 O. P, f        b_list.append(min(tsp_solve(muta=1)))
        time_end = time.time()
9 \* o9 e  s& |7 O3 _        t_list.append(time_end - time_start)
- G" {' e- _$ }  ^* b) v4 r        # II. 块逆转变异策略
. W& z9 o0 C. e; g        time_startII = time.time()
        b_listII.append(min(tsp_solve(muta=2)))
1 W2 A! s- a$ k( j        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
4 f0 ]5 x9 K$ U        # III. 同时使用上述两种编译策略
        time_startIII = time.time()
1 k- A# p) x, E0 z. p        b_listIII.append(min(tsp_solve(muta=3)))
+ E1 i7 z$ p% }3 G- ^& V% i        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
4 x# c. b$ [" @* L; Y4 s6 L5 I
    # 做排序处理，方便比较
    b_list.sort()
    t_list.sort()
# h: `9 I" F7 A. J' K  T9 j. L    b_listII.sort()
    t_listII.sort()
    b_listIII.sort()
    t_listIII.sort()

# V# I9 g; J# D# V, e( r- C    ax1 = plt.subplot(121)
. H: F+ n3 z( {% k$ F    ax1.plot(i_list, b_list, 'b', label="Origin")
- }8 t0 F4 W) x( f, b8 m    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
    ax1.plot(i_list, b_listIII, 'g', label="Origin + Block-reversal")
    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'b', label="Origin")
    ax2.plot(i_list, t_listII, 'r', label="Block-reversal")
! W6 s. F# y+ p2 |! r2 |    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
    ax2.set_ylabel("Cost Time")
    plt.legend()
    plt.show()
- [/ E0 p' v! l; c; w% Q
# 4.2 锦标赛选择策略对比测试
def opt2_test():
5 b' U: G% H9 w    ITE = 20  # 测试次数
  b0 f. U- ]) p6 Z    i_list = range(ITE)
5 G4 u3 A! L9 q: u    b_list = []  # 每次求出的最短路径
' x0 g1 K0 ~0 P5 s    t_list = []  # 每次求解的耗时
8 A$ m6 i  B/ P: v, M    b_listII = []
' b+ V' o* @$ n    t_listII = []
% g% g& m+ H$ @- ^0 d8 x$ Z2 K    b_listIII = []
* O9 r! r; w4 W0 }) U    t_listIII = []
1 c" C$ Y2 W# K0 F4 b5 a8 [
. j. Z6 A  p* W' j; A, v& O    for i in i_list:
" q/ O8 @/ X! x1 u3 v8 ]        print(i)
        # I. 原赌轮盘选择策略
9 z) z: O( z3 c& u        time_start = time.time()
        b_list.append(min(tsp_solve(sel=1)))
) P3 j' B5 D7 `! r4 c% F        time_end = time.time()
        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(sel=2)))
        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
7 N: x3 a! V: U+ M: g2 G; I# u- @1 _9 i        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
' D% b1 H. U* T+ K: q        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
2 }' b( c7 S4 D. g8 X
; s7 m2 @9 g, S0 C/ X, ?+ u    # 做排序处理，方便比较
" {+ P& O( N& x0 ^6 D7 s8 N    b_list.sort()
    t_list.sort()
    b_listII.sort()
    t_listII.sort()
+ B& I  L: q; G* i/ X% d    b_listIII.sort()
- z+ ^* U6 Z, y; s# L    t_listIII.sort()
# P6 X6 g" I2 S  E% r' U
    ax1 = plt.subplot(121)
1 n/ y/ F5 ~) U    ax1.plot(i_list, b_list, 'b', label="Origin")
4 q, y- ?7 r0 h. B1 [    ax1.plot(i_list, b_listII, 'r', label="Tournament")
9 `) z$ n$ N2 m. A1 j- I    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
; N6 {$ M, Z& W! Y: d+ G    ax1.set_ylabel("Shortest Path")
, Q9 c% o# y2 l5 c- r    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'b', label="Origin")
    ax2.plot(i_list, t_listII, 'r', label="Tournament")
    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
5 d5 g" s# k' y    ax2.set_ylabel("Cost Time")
    plt.legend()
; I: e/ i- o4 e    plt.show()

5 }. p6 I. H; I7 q$ S( L) E# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
def ori_main():
1 N4 _; P( N4 e# [% W' B3 [    time_start = time.time()
9 _0 U# S5 \% r- v: j    pop = [] # 生成初代种群pop
# h5 `" l: V+ v# Q    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
9 a3 C: z$ w6 E' G' B' m    best_dis= []
' e9 j: [7 ^4 d6 g    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
6 P! \( Y0 S* |5 _    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE)
        fitness = getfitness(pop)
+ Q3 b) z( Q: p0 G. m        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
* O1 }8 F% k% v        pop = select(pop, fitness)  # 选择生成新的种群
5 e4 R- K" c/ e% T. e: M
, ]( e; q% d3 F    time_end = time.time()
. p: A% o! |) g6 n. \7 i8 p    print_info(pop)
+ H2 \/ y( `' {/ z- b6 u+ V    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
3 v+ r  W6 d! g2 e, Y1 f" P; @    plt.figure()
    plt.plot(range(Iterations),best_dis)

3 E( r/ \- K1 e+ _; a# 4.1 块逆转变异策略运行效果展示
3 F+ `2 m6 N4 O, Z3 V+ d, j5 \def opt1_main():
    time_start = time.time()
    pop = []    # 生成初代种群pop
) O7 b. K; `6 E% l9 D6 H2 s& }    li = list(range(DNA_SIZE))
; S0 ^8 E% P' f/ `; t6 |/ U+ `    for i in range(POP_SIZE):
& j  s* i" t. V        random.shuffle(li)
        l = li.copy()
( K2 F; A( o- m        pop.append(l)
" y( X! J$ `) L4 o7 p+ ]9 l    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
9 W2 m+ T  m1 A; k- z        pop = crossmuta(pop, CROSS_RATE, muta=3)
        fitness = getfitness(pop)
/ b  u3 J# t% `0 c        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
  z, e6 m5 H% c2 h$ |; `        pop = select(pop, fitness)  # 选择生成新的种群

    time_end = time.time()
    print_info(pop)
7 s) `. _0 z8 V! P    print('逐代的最小距离：',best_dis)
, Y5 l/ h9 m  a6 m$ i    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
    plt.plot(range(Iterations),best_dis)
" p# t; i7 Q# }  v3 ?9 k
2 t1 \) N" q0 s% Q! S: gif __name__ == "__main__":

    ori_main()    # 原程序的主函数
    opt1_main()   # 块逆转变异策略运行效果展示
2 l9 R8 r5 x& i. }3 A5 Y    plt.show()
9 O4 Y% B; l0 n7 T, l    plt.close()
: J9 h) t! k6 n& c* j, s
    # opt1_test()   # 块逆转变异策略对比测试
0 b3 y, C. g1 f! y1 M" O    # opt2_test()   # 锦标赛选择策略对比测试

    # pop_size_test()       # POP_SIZE 种群规模参数测试
+ m2 I( o' Y1 d: k' ?/ J9 [    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
4 G; l! N' w0 }4 [3 ^' I    # muta_rate_test()      # MUTA_RATE 变异率参数测试
" \- |' C, H  L+ S) w    # cross_muta_test()     # 交叉率和变异率双参数测试
& O! t" S* K4 {  a- l, E8 w5 S

1
' h8 ~5 \+ U7 x) ]; a! u! j2
5 ^# Z- q# g9 Q" f4 Y/ x$ `6 L3
4
5
7 @* c, D. ^! A6 y* F7 z6
7
8
+ T* A2 G: B: d7 D5 h0 V1 A/ J9
" z% e$ H8 g) h10
1 W2 K$ O. ]/ x( z1 P. H11
12
13
1 r9 ]) G% S  L1 W' V( N7 h14
7 V" {' x  Y: s3 Y% D15
" v# O6 @5 a* I9 c6 V16
17
' O5 x9 p0 i. l18
  V; H! `1 H7 Q- w+ d19
5 [7 n5 X1 a8 A' B$ {9 ?20
. Q: g, L/ f. F3 U5 h2 E2 F" P21
22
6 r; V; s5 \! O0 Z. S0 }9 g23
24
25
" B# E& v. ~6 l) f26
6 K/ T6 v  |; Z27
; Y5 e* g' l+ Y4 h( H; d$ z, x4 D28
29
/ q. T/ V4 R; p4 h; l" C8 M30
* r( h8 V2 t9 g6 `6 }3 T  @4 Y: P31
32
33
- _% d  W, s; S$ G1 ?34
35
8 W! q9 a' T) x3 Q& W9 W) b36
37
38
39
40
41
# I6 O( K. a. [- F42
" U& X6 F9 m, q# h5 k43
44
3 G( {! n" ?9 e7 v; R2 X0 N45
, I& V- \  U# [' x. ~46
47
48
49
50
8 z& K+ T; ?2 t# t51
9 @4 c  E; v- l, q6 m" S3 u52
53
5 d) w, @6 G; X" L& C54
55
56
57
58
59
* ^4 ~' l# b4 U/ G! ~5 |$ B60
61
62
63
' M7 ]/ E2 X, \3 e$ A7 ?; f1 L64
65
4 J' R2 _* b( V3 J5 a! _5 N1 l66
67
# H( p" u3 s7 _: b' ^, J68
69
70
& E  q( w* t9 ]: S8 A71
0 m9 `) G2 `* v2 I; t. ~  _! \, Q6 a72
73
74
2 h: P* U0 _, t: D: m9 h75
76
' y  W* [- ^4 @( i77
78
79
80
' ~  y; K  F  h/ B3 L( J* a4 i9 t81
82
83
84
4 B' W4 v  T; }0 \, [( ^85
86
87
88
89
& z2 x3 }' n+ m90
91
92
93
$ F' d+ J4 W/ G! Q94
) I1 }$ V4 A: B% v95
96
  V) j+ F# H4 B* t* I" t97
98
99
100
) c3 Z. H. f3 ]  K' W! h101
102
103
104
105
106
8 @/ `* V! h% a/ w107
/ V) f( N8 e* x2 d8 r108
8 V" f% i  F" j! W; U4 `' Q109
: u# R9 y1 F0 \$ t110
111
112
& y" I2 a: c: G* Q% ^$ A113
114
" m% G( @5 S9 {115
116
" H' c5 R+ x- X2 Q  `# N117
( q2 m& N9 Z) \! a' f118
* I: K$ n0 W9 X0 T( z- g) R$ t5 \; y119
) ?( l4 F, O" M! I; |0 J, ]9 T120
: i( Q& Y, P& b" w5 q! Q% O/ I! @, W121
# Q2 f! p) h% J3 f# Y! N1 I122
123
9 l& p* w* ~. Y8 H124
. a% M0 t; m3 N7 T; l125
. J3 R9 |& f- r% O" x% i6 x7 ~3 |. T126
" `) H* X, p" B* u" m' @127
128
. v! q+ T7 k+ [1 H. R129
( _. B6 f" n8 ~! l: n" Z2 h/ A3 k130
( j* b: W1 E% x/ a0 M) J7 a131
132
+ e! a1 A/ M% [* \9 Q' q133
1 X; M3 S( A( t2 `( ]134
135
136
" ]  J) H% ?9 q7 a137
138
139
140
141
142
) `/ R& ?: R0 D# [143
0 j# S- _1 A4 [( l" R144
. `) l+ @7 M/ N2 M" [145
146
6 Q8 M/ `9 Q# k, g147
148
149
! m5 h8 ~! g8 W4 i* F/ a2 U7 c8 M150
151
2 x5 C* @3 H( B152
0 D( ?: S5 C3 l! w153
6 T, P0 \; `  t1 _  i( c* I% N% W154
155
/ a9 ?1 `5 w% i; a* t; J( ]156
157
5 U3 _3 H0 v. R: W$ a158
0 s8 B; Z# ?: i2 t* S159
: z( }* j* e  d6 s8 G160
161
162
) p! j$ g4 [2 ]1 M  }  d$ s5 P163
( X8 |& ?$ [$ \9 j$ B4 E* v. Z3 E; \: L164
165
7 U0 P/ _/ _5 x166
# n+ d6 R' B+ N; P; Q3 T# a167
168
169
170
171
172
5 s* ?4 v& }2 ^+ a$ \: \173
174
( d  K% C; L& [+ k6 }: u% w175
176
: ?0 u, F# L" {7 N( P177
178
/ o7 @0 }( }3 p' r- K9 A0 D' `+ D179
180
181
8 S8 a" _. r5 {8 {5 d  ]( t/ C182
8 m6 n2 `6 B  E4 Q183
184
2 g5 E6 A/ `' W& |, Q' v6 a4 e( t185
4 u0 D9 v! f) o' S3 W1 X3 Y186
187
. p7 n. i2 v7 ~4 Q1 ~; D188
189
1 t9 s: l# ?1 f* @( c0 I% {/ Q190
191
$ S3 j! |& [/ o' T* T$ @192
193
1 Y4 T3 `/ @0 X" _! q4 {194
195
- m3 \0 \0 @9 P2 L8 o196
197
" F9 K: d: g* x5 F7 E198
199
200
. X: M2 v8 |& A% S$ q201
202
203
204
205
1 d, g0 c' t8 L3 Z0 D  s+ K206
8 _! X2 w' `! R& h5 [& ]5 _9 E2 s207
208
209
210
3 m) z8 @$ ?, s1 J- A6 N8 a211
212
213
, ^6 k0 P; w2 w& h214
215
216
217
218
219
220
) z2 ~2 u$ F; a/ l* M: B4 i221
222
. I& I$ Q: [1 @9 V& ?" ?223
, Q/ e1 i* n0 Z6 t2 g5 u" T2 \224
: a! h; Y4 _* P, y225
226
0 S$ ^1 S( V9 C0 q: o227
3 o* }+ j) T' A1 o2 Y228
) l' g3 p" S7 x+ }229
230
231
232
233
( g1 I" G7 O2 t: z6 r' h$ F234
235
236
% N* `' `2 O. s9 S& H- H237
238
239
, u( @' B# x% P, U( y; y4 V240
241
242
243
* U% w# [* u0 p& Y244
245
246
247
9 Y2 t' _3 N% m- k& W248
+ [' Z1 Q8 h. N6 ~: X: m249
250
3 a9 m9 ]8 [2 o* e+ p4 s/ W2 B251
9 h  {2 F* |, o252
253
' a' m5 @! U/ u, [& Z# N254
' _# ]) Y2 j* k255
1 n3 n# R& G2 J, F1 Y$ d256
. K  x- H5 c7 n1 n0 }$ z) U' f257
8 W3 n0 I" i+ t: x( }# V$ n# a258
! T3 [3 Y# Y0 s  _9 J" G259
/ R$ z7 t0 F+ H% c/ G260
6 S3 U3 ~5 Q- \7 ~; w261
262
263
6 p- K8 v: C) p  H( v& U/ z8 l1 a264
265
; K  |5 P: H7 p266
5 X& F1 H9 v2 ~2 D  o/ C5 w8 E267
268
269
! a7 Q* w) Z) }- r270
% `1 K4 [9 M" y9 s3 C  [1 [1 ^& U271
272
4 {, ^/ S2 z5 k3 h* b- U3 D273
274
275
) M) z( u7 b: N2 H8 e0 Y276
277
278
279
4 Z- o$ h; X/ d$ ~280
5 _7 F6 g, C" S281
282
( E& t; X% q$ d; f283
284
285
286
8 B% h: O0 a! R  r) t( c5 Y/ n287
288
289
290
291
292
293
294
' }( }( H0 \  n, t! g' I295
4 |! X1 s; C- W; y8 y" X296
297
* U, Z* q' x2 e4 f298
299
300
301
4 n9 k8 w$ D$ {' f+ o7 h! t/ p302
- M9 U+ U  n. q% D7 r303
: L0 C% k% m% i6 n304
305
306
307
308
309
310
: i- S  _4 K, W, s/ X311
312
6 F# z- `, ?2 Z* F# `1 Y: F; n313
1 H) @# N2 h& M# L& w314
315
316
* a/ K4 z' O  m, M6 x; E317
9 l- _9 x* Y1 K318
3 P6 x0 M+ D/ r319
4 V2 @" ~; N- c, A320
321
322
! H. y( i0 U+ p+ `323
324
325
  h: ^; Z, x9 \% y+ N6 L326
. P" |% v% P; h327
* C* w9 X$ N8 ]0 A9 ~5 i328
! s1 W. K) Z0 Z; D. [8 Q329
3 l2 t* S: m" S7 X8 [0 ]330
6 u. `3 |" E' l$ \331
332
333
334
335
( T4 m# o+ b" x! v2 F336
, o+ K/ {6 ]- G! Y# a: ?5 z0 R337
' C- |! V1 x: y* }2 y% d338
0 y7 i$ W& c6 M, Y) }+ J' M0 X339
! Y7 I% `. j$ q$ {! y" b340
0 A& Q5 S; E9 E# N2 l5 N341
342
343
* p  F+ l* f9 e% {5 a2 O9 h344
4 ~! p* K' A3 A3 u345
+ f' J( ~" p4 [& v/ y9 Y346
3 e3 h, m) w! T6 m) x  `& t+ T  h347
* G) O9 |+ K: |- L. T2 Q/ i348
; W" s- h. N% L; @. L349
2 Z' g4 B, f  ^+ w7 T, }350
351
1 U8 w2 L3 \2 R  D: P# a352
; f2 r" q' m7 W353
* z0 ^2 a+ _* Y+ c2 u2 o; ?6 _354
355
( T3 k' u, R7 Z$ v356
2 N' W! x- D' \+ l357
9 J- ~& M2 x( i  H3 r358
1 g: ]& \& @" Q& ]- E3 U359
" w5 D( f' a  S; G  F360
8 N  j* O% O* Z$ K/ [$ I  R: x. U361
362
& L$ p1 I4 [0 X) @2 v% j$ i" ^363
3 `& Z- c! g$ e, Z- U$ v364
365
. C, p' q% ?: L- h4 F366
' j6 P" e; A' G3 W. A6 I# F1 J: q: U367
; C, V6 t0 A2 @5 D/ ~4 j368
* H: w3 S4 I7 F: ?$ S2 s$ C369
370
371
4 m( Q( s1 _3 h  s( p# C372
6 c( H' r, F$ N; @7 z& r; ]373
374
375
376
9 N7 K  c9 O/ T9 D3 I/ f+ [& \$ n377
" d. q/ P1 ~% H9 i378
( }3 g4 l( U' \: i7 ^, R0 ?! R9 x1 x7 H379
380
6 a9 Y/ m! G5 Z7 h6 P- w, n381
8 o1 ]6 O9 A, y: y382
383
  v# U% k8 L, `; H  ^* `384
# S9 h- q( a$ E  P' l$ M9 v+ P- t& G385
) Z$ o! ^( S: B( z386
2 f1 @( N4 O5 i9 g4 b- |% v( k9 p387
388
389
* R" B' _# f( [, |: G390
391
392
" D" ], l! N9 _3 T* J393
9 z' z) l1 B0 i7 `- e1 N- G394
1 s* X" C: N( l" \; K9 V5 N395
4 R  T6 K2 s1 @* n396
397
398
399
, i! p# p+ [% c4 _, T' v) t* S400
401
402
403
: }' r/ h6 n& v404
405
' @# u( C6 ^6 P3 L406
407
/ m+ r4 a- t0 {& V: H& z) @408
4 ^+ l# L0 j+ \. H  V/ m, ]+ K" [409
0 \& v9 E3 G5 g  X) f1 t: x410
411
412
" ?$ V# H6 `9 v% B413
" h' e/ v. M0 V1 U" ~/ L414
/ D( r0 _, n; u9 x415
" R& ^0 T  [( H; h2 |416
417
418
/ G9 u4 S' r  g) x# q8 D2 Q419
7 H. I6 T6 P1 P$ \# J' n) `  K420
/ u- F- k  v2 z0 k6 M* E2 j3 ?" L421
422
423
424
425
7 ]' x9 V5 X; X! _* i5 ?426
" E- d& _8 b5 A3 S" S427
- L( W4 v, i2 X4 A: l6 l428
( N* p+ l: q, {9 X# m429
430
431
6 G5 Z! e4 a( w432
4 x# r! i1 ~- r3 ~& B6 C8 T433
434
435
0 ~# |1 Q. N5 @436
5 k1 ~# \  N8 c" ]+ B# g* Y437
" X% `5 ]: }- J438
/ C& z/ a6 c6 }439
, R1 j% ~: ^% r2 |440
441
442
443
444
445
! |9 }0 r2 ^" j( ^6 A6 b) x$ Z446
447
448
449
450
451
% c0 D6 @! Z" Y- P$ p452
453
$ x2 j8 c7 ]7 _; T1 Z: h1 t454
455
- H0 n& M/ r# h5 Q& M! Z456
5 K( M# k; o! H6 l( F4 ?457
458
459
9 ^; v1 b) m- A$ Z8 _9 t& L460
5 G' i" t2 H$ @' j( C7 u461
5 w. p( c) s  r462
463
464
$ o0 n5 d8 _2 t6 q, @  Y8 E465
466
467
6 ^% f* \8 g: j) X/ H468
469
+ o+ x: e: M1 G6 d! I

, J8 `  T$ d8 ~# H% l0 ^/ m4 u
: S, o& i3 g7 `
9 q3 L6 Z0 K* l* U: ]' t/ ^& V

3 D3 t% _8 K8 @
' a3 F7 S8 \7 I$ x


+ C' `* W4 K! ]# R. {5 w



$ \$ ~$ X) H) n1 G; T+ `
2 f8 I. Y; f2 a: d( B& `
, F/ ]6 W# t4 a6 M! x" E+ O% V

# @" o6 W# ~7 D' ?& f+ C

- ?$ X- G: j* B8 N- l% f

# b* c8 |3 W" s* c' `4 C, f/ r
) W! l: E0 ?6 P) ~6 H( t
) S) y* t# p/ @( g+ J4 l' C, z

9 k+ f* v5 Y$ f. Y# `1 G2 u
( g) L9 [/ D: q( \. T. v————————————————
- r3 J6 F  f# S1 w5 y  W! H- \版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 ^& W3 \" h$ h: X原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212
, w) t" E9 f# j5 U

( C5 l% n# S, |  d
; h+ ?& h* H2 [/ y# Q