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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
7 I, r/ n9 z) O$ N9 z1 H( s目录
人工智能第四次实验报告 1
8 z1 }  @4 W) Z: i# y$ k2 \+ j遗传算法求TSP问题 1
/ U5 u3 C8 b; c1 i/ H( E+ P一 、问题背景 1
1.1 遗传算法简介 1
1.2 遗传算法基本要素 2
/ ?$ k3 D0 t! ]' k1.3 遗传算法一般步骤 2
- m4 ~$ ]$ r2 Q/ s" }: ?3 \* m: W二 、程序说明 3
2.3 选择初始群体 4
" Y6 r# H; B0 z: h! S. z2.4 适应度函数 4
2.5 遗传操作 4
2.6 迭代过程 4
三 、程序测试 5
# L2 Y: N# M3 @, d/ I2 z3.1 求解不同规模的TSP问题的算法性能 5
: n6 n4 x" R* Y& `) N% K3.2 种群规模对算法结果的影响 5
% b; U, ]3 }+ n, s3.3 交叉概率对算法结果的影响 6
5 l! m; o# y, w& j, s3.4 变异概率对算法结果的影响 7
  N- E5 ]  k9 Y% l3.5 交叉概率和变异概率对算法结果的影响 7
四 、算法改进 8
4.1 块逆转变异策略 8
. G8 ~/ n5 K# P7 b) t4.2 锦标赛选择法 9
5 y. m' X  W: n9 h3 {五 、实验总结 10
一 、问题背景
7 J5 m0 L& ?- T9 D0 f1 Y1.1遗传算法简介
遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
1.2遗传算法基本要素
. x+ R& ?3 X# Y" |* `! \& ]) a1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
; k3 C. X, O% c  {, d2 H2 t2.设定初始群体：
1.启发 / 非启发给定一组解作为初始群体
' ]4 `: V( P+ I: t2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
" t" l+ p' ^, Y1 }% I5 t4.设定遗传操作：
1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
) s2 x' P1 W1 h% H0 b$ j" R1 ?2 T' |2.交叉：两个个体的基因进行交叉重组来获得新个体
& Z' i& d& }  O5 h* w5 `8 z6 N3.变异：随机变动个体串基因座上的某些基因
; u: }8 q; X8 n! m! U7 |! m5.设定控制参数：例如变异概率、交叉程度、迭代上限等。
( b+ @. `) j% w/ I7 u+ r
import numpy as np
import random
+ R( x2 V+ D2 k+ Z, zimport matplotlib.pyplot as plt
9 x: \/ ]/ R$ P4 z6 R7 K" O) m, dimport copy
import time

from matplotlib.ticker import MultipleLocator
. X  p0 E' @/ K& Cfrom scipy.interpolate import interpolate
  y6 F% T/ A3 {% x: x5 O5 u6 |- x6 m
CITY_NUM = 20
City_Map = 100 * np.random.rand(CITY_NUM, 2)
( k. [- E3 d( U: Q) \% h/ {( ~& X
DNA_SIZE = CITY_NUM     #编码长度
POP_SIZE = 100          #种群大小
! A2 I4 L* o1 B9 y& ~CROSS_RATE = 0.6        #交叉率
MUTA_RATE = 0.2         #变异率
Iterations = 1000       #迭代次数

; O1 e7 U  F" u  v) B# 根据DNA的路线计算距离
2 w7 N6 m* z2 c% U2 Wdef distance(DNA):
) P0 ?' V- z, o8 V" f4 {0 e    dis = 0
    temp = City_Map[DNA[0]]
2 C" _7 E: K! N    for i in DNA[1:]:
        dis = dis + ((City_Map[0]-temp[0])**2+(City_Map[1]-temp[1])**2)**0.5
        temp = City_Map
, Y1 [- [: j$ K+ w8 p3 ^& D    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5

# 计算种群适应度，这里适应度用距离的倒数表示
' r) d0 u% o+ S8 j/ wdef getfitness(pop):
    temp = []
    for i in range(len(pop)):
        temp.append(1/(distance(pop)))
% g# `% \6 ?. X+ `5 ^    return temp-np.min(temp) + 0.000001

# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
* V+ A3 t$ @- ?7 D" [, udef select(pop, fitness):
* X8 @# |/ Y$ J    s = fitness.sum()
) n# D8 `( B+ [; S6 l    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
    p = []
    for i in temp:
        p.append(pop)
, r+ [8 |& `5 r. o7 F    return p

# 4.2 选择：锦标赛选择法
1 @% y. l2 c3 n# n0 o7 ?def selectII(pop, fitness):
    p = []
    for i in range(POP_SIZE):
" @+ Q5 _+ ^" u        temp1 = np.random.randint(POP_SIZE)
& Z; [2 M* ]% @7 t        temp2 = np.random.randint(POP_SIZE)
        DNA1 = pop[temp1]
        DNA2 = pop[temp2]
        if fitness[temp1] > fitness[temp2]:
            p.append(DNA1)
        else:
            p.append(DNA2)
    return p
! q5 Z) F  e$ g# ~! X
# 变异：选择两个位置互换其中的城市编号
def mutation(DNA, MUTA_RATE):
% q0 K0 Y( w" ?( L5 y+ {( |    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
3 L" [+ F. X# z  b( C        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
% y* R3 ^+ g1 l( ?9 _& N9 d( q        mutate_point1 = np.random.randint(0, DNA_SIZE)
7 i/ H# [. p* C        mutate_point2 = np.random.randint(0,DNA_SIZE)
        while(mutate_point1 == mutate_point2):
  Q8 _! [1 p- l$ m$ M2 v& B            mutate_point2 = np.random.randint(0,DNA_SIZE)
9 I6 `1 L& A3 q: c, ^        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]
, [3 h2 C* L0 e9 H
/ u  |' u# k7 X7 S9 X4 B8 D# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
def mutationII(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE:
  [+ a4 |# @3 E9 Y( ^        mutate_point1 = np.random.randint(0, DNA_SIZE)
) C0 j! f/ i" M9 [/ u        mutate_point2 = np.random.randint(0, DNA_SIZE)
        while (mutate_point1 == mutate_point2):
$ a( _+ i+ B, I% Z( [' E. K* u            mutate_point2 = np.random.randint(0, DNA_SIZE)
+ h, Y2 G6 B! D3 ^/ [5 Q        if(mutate_point1 > mutate_point2):
            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
        DNA[mutate_point1:mutate_point2].reverse()

# 4.1 变异：调用 I 和 II
def mutationIII(DNA, MUTA_RATE):
) T! W* h" h5 v% g& O) E. p* w    mutationII(DNA, MUTA_RATE)
! I. s/ T9 Q6 B8 m+ g6 F, d    mutation(DNA, MUTA_RATE)
  K* X( H1 o6 t" Q: o: y4 ^: ]
# 交叉变异
7 z1 G) N1 u, R# muta = 1时变异调用 mutation；
# muta = 2时变异调用 mutationII；
/ D, n9 E! r9 `7 N3 S' H# muta = 3时变异调用 mutationIII
def crossmuta(pop, CROSS_RATE, muta=1):
    new_pop = []
    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
" [# H. ]. e! p        n = np.random.rand()
) i' Y- t9 O, b        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
6 K  \: W- a2 W; U4 K) `            temp = pop.copy()
            new_pop.append(temp)
        # 小于交叉概率时发生变异
- X$ j7 X; U& j. Q; D3 m5 ]        if n < CROSS_RATE:
* I6 F1 \* D! e, q6 `7 Z1 Q            # 选取种群中另一个个体进行交叉
0 S$ S# f* z7 f            list1 = pop.copy()
            list2 = pop[np.random.randint(POP_SIZE)].copy()
            status = True
: U2 S# K: q' Y            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
            while status:
' c+ H) R" t4 k  w' m* f                k1 = random.randint(0, len(list1) - 1)
+ Y# p& J# Y4 V. _+ n                k2 = random.randint(0, len(list2) - 1)
                if k1 < k2:
9 s4 j7 f0 u: s- n  U- g                    status = False
  R9 {- c. a4 }+ C0 X) ^2 q
! A7 O  E1 A  i            k11 = k1

            # 两个DNA中待交叉的片段
            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]
& w3 i$ g8 y/ B& S) o: C) p0 m$ L
            # 交换片段后的DNA
; H3 A6 O& |4 E6 `0 a            list1[k1: k2] = fragment2
            list2[k1: k2] = fragment1
$ h+ H( t! H7 M+ C6 C! b" g
+ v) u+ r$ ]- b  t: y            # left1就是 list1除去交叉片段后剩下的DNA片段
/ p5 A5 i( y: }0 s" f            del list1[k1: k2]
& F" Y  {; m8 F  N/ U            left1 = list1
1 F2 K3 V/ C/ O7 n0 z, B
' |3 f+ N7 X' \3 l. j/ _# w& A/ M            offspring1 = []
6 E' A% ]5 h; b            for pos in left1:
                # 如果 left1 中有与待插入的新片段相同的城市编号
                if pos in fragment2:
                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
                    # 循环查找，直至这个城市编号不再待插入的片段中
                    pos = fragment1[fragment2.index(pos)]
                    while pos in fragment2:
# v# d2 j1 j% A                        pos = fragment1[fragment2.index(pos)]
                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
- ?) A% Q: F. I. n7 y1 P                    offspring1.append(pos)
                    continue
) P) [1 I  X) X9 a6 o                offspring1.append(pos)
            for i in range(0, len(fragment2)):
2 e3 V5 c) _0 o1 P$ Z                offspring1.insert(k11, fragment2)
                k11 += 1
            temp = offspring1.copy()
            # 根据 type 的值选择一种变异策略
+ ^% ]) I& }/ s            if muta == 1:
; ~: ]4 k7 l+ p& G' a9 j8 L                mutation(temp, MUTA_RATE)
7 Y; a$ V- t* `. G3 o7 a            elif muta == 2:
6 _# \, t+ q+ l- H! C2 f$ `% O                mutationII(temp, MUTA_RATE)
            elif muta == 3:
                mutationIII(temp, MUTA_RATE)
  p) K, c% F3 u* d& R: L# S: s            # 把部分匹配交叉后形成的合法个体加入到下一代种群
. d# |% W/ T. E1 m; M1 X% m. E            new_pop.append(temp)
9 t; z6 @6 l* T7 k" o
' x" f9 H7 |4 J# `    return new_pop

0 o! G( \. K' S) `$ O! Edef print_info(pop):
* O1 `! |3 V% w    fitness = getfitness(pop)
* T" _' B: ~1 o' z    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
, p& q( z1 Z9 ?! m' V) e) y    print("最优的基因型：", pop[maxfitness])
+ f- C% y% m4 Z$ Z; g# g    print("最短距离：",distance(pop[maxfitness]))
& x, [; D( _* p4 f0 B+ E    # 按最优结果顺序把地图上的点加入到best_map列表中
+ O( s5 v; k0 j; P, W    best_map = []
' m. y! n; T6 L$ L3 V    for i in pop[maxfitness]:
+ M; [0 Q6 u* ~0 B        best_map.append(City_Map)
    best_map.append(City_Map[pop[maxfitness][0]])
    X = np.array((best_map))[:,0]
9 _+ i0 i4 ~% j5 I    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
    plt.figure()
    plt.rcParams['font.sans-serif'] = ['SimHei']
# y1 Z& e5 f7 _3 @& P0 C7 k    plt.scatter(X,Y)
8 u& _' V. W: q& j    for dot in range(len(X)-1):
1 T/ |; o/ }4 O" J( V) s        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
( K6 D3 s. e( U9 G' |    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
    plt.plot(X,Y)

# 3.2 种群规模对算法结果的影响
def pop_size_test():
& u1 @$ c/ D" K" b    global POP_SIZE
8 Y' L" y+ V; J  K    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
    b_list = []
    t_list = []
    for i in i_list:
9 P+ n* P; q+ T) R1 S        print(i)
        POP_SIZE = i
        time_cost = 0
6 R5 ?! X" P( e- l        min_path = 0
* [2 v' p8 c# q% H6 }        for j in range(ITE):
            time_start = time.time()
/ k( X% U" L- M, v            ans = tsp_solve()
% p$ i2 w  G7 l4 Z( P! F            min_path += min(ans)
            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")

( T4 q, v. `! d# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
    global CROSS_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
( W  W  S. {( }' |& t    b_list = []
- |4 O) f4 w! X2 i5 ?    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
        CROSS_RATE = 0.05 * i
; K" m" E: x; d7 Y- [( |        ii_list.append(CROSS_RATE)
        time_cost = 0
        min_path = 0
        for j in range(ITE):
' w/ M) w/ O! y. S1 O" _            time_start = time.time()
            ans = tsp_solve()
            min_path += min(ans)
& A' Z* W8 b: `/ u            time_end = time.time()
% W4 \% g6 Y5 V            time_cost += time_end - time_start
& A% N+ ^- y( k% n( q+ m" A' q
# n( P% Z2 n6 b8 V- D: ?        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
0 I6 w1 H4 p5 b. p# I$ |9 q    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")

1 i& X* Q7 N& w( O! {2 y6 U# 3.4 变异概率对算法结果的影响
; V4 i7 B# Z) y( pdef muta_rate_test():
% b! {1 e$ y8 n+ [5 L5 t3 k" w    global MUTA_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
  ]# _* L! k8 g6 w2 s    i_list = range(0, 21)
    b_list = []
! w1 k, Z5 l; V- K9 ]& n    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
' R( A4 E* }& B* R/ \2 f        MUTA_RATE = 0.05 * i
$ A( @/ Y6 }  q# S& s2 D        ii_list.append(MUTA_RATE)
4 ?$ W3 N, v, Y" w; Z; Z- \' ?        time_cost = 0
        min_path = 0
        for j in range(ITE):
            time_start = time.time()
            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
" k0 }6 r- [! ]- Q* }    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")
- T7 Y* D% V5 T- z" g4 ]/ W
# 3.5 交叉概率和变异概率对算法结果的影响
def cross_muta_test():
7 c1 @0 w8 z- ]/ b( \    s = np.array([0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0])
$ Q3 f" d  l, _1 e/ ?; Y5 E    X, Y = np.meshgrid(s,s)
    Z = np.zeros(shape=(11, 11))
5 J, y# p* I- \2 V( X
    global MUTA_RATE
+ X% |3 ~9 B5 m1 j' q$ z7 @0 d    global CROSS_RATE
    for i in range(11):
        for j in range(11):
+ g1 m. |* y( c! v: H& T0 A7 B3 |            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
            MUTA_RATE = Y[0,j]
            ans = tsp_solve()
/ W. J; R* B8 s( @( a5 \2 V            Z[i, j] = min(ans)

6 ?' U4 Z: I/ R8 m2 ^0 e    ax = plt.axes(projection='3d')
) m5 y. v( n; q# J8 N1 y1 ?9 e9 m    ax.plot_surface(X, Y, Z, rstride=1, cstride=1,cmap='rainbow', edgecolor='none')
    ax.set_xlabel("CROSS_RATE")
    ax.set_ylabel("MUTA_RATE")
    ax.set_zlabel("Shortest_Path")
    ax.set_title('TSP')
* \& I! c6 C7 s+ Y  @7 e' H    plt.show()
0 x  U/ F2 s5 Z  [/ c
# 3.2-3.4 生成参数测试结果的可视化图表
, z7 o3 L! \$ t7 C- i6 |! ldef show_test_result(i_list, b_list, t_list, msg):
    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b')
    ax1.set_xlabel(msg)
8 ^1 V% N. ^6 m& w    ax1.set_ylabel("Shortest Path")

% v! k5 o. N1 _2 u# t    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'r')
    ax2.set_xlabel(msg)
2 E2 |0 K- I. |. T( _2 `. B    ax2.set_ylabel("Cost Time")
3 M# o5 `1 k/ t    plt.show()
" W9 q2 ]4 Y5 j1 \
# 求解TSP问题并返回最大值
0 J8 Z5 a' b! z7 c# muta 指定变异方式，sel 指定选择方式
* E. ^$ u3 ?" Edef tsp_solve(muta=1, sel=1):
    pop = []
    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
) E8 L! j' B) }& d        random.shuffle(li)
        l = li.copy()
        pop.append(l)
    best_dis = []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=muta)
        fitness = getfitness(pop)
3 _& [' t% q$ h5 r        maxfitness = np.argmax(fitness)
0 q, W7 S6 F. P0 }        best_dis.append(distance(pop[maxfitness]))
        if sel == 1:
            pop = select(pop, fitness)  # 选择生成新的种群
! e& u2 y* i0 k0 c        elif sel == 2:
            pop = selectII(pop, fitness)  # 选择生成新的种群
5 \0 o8 P' C: I; A: {. s* Y, B
    return best_dis
# c5 `( m4 P8 y/ c' g0 {( ~# t
" s+ P4 z3 i4 O: `$ S# 4.1 块逆转变异策略对比测试
/ f) w( L6 @! |) M0 b: tdef opt1_test():
    ITE = 20    # 测试次数
    i_list = range(ITE)
/ H( o. C5 v' ~- Z$ u) S    b_list = []     # 每次求出的最短路径
    t_list = []     # 每次求解的耗时
* U+ C' i# r5 f  Q$ }6 {    b_listII = []
    t_listII = []
3 v2 D, K2 x6 O9 H: P8 }0 ?    b_listIII = []
    t_listIII = []

& R5 X+ \+ x& Z% e3 V    for i in i_list:
5 X1 I% m5 B% t        print(i)
        # I. 原两点互换异策略
        time_start = time.time()
- a+ ^- Y+ x+ f; [        b_list.append(min(tsp_solve(muta=1)))
        time_end = time.time()
8 \! j2 `7 ^+ P' M        t_list.append(time_end - time_start)
& R/ S$ H" Q: L" D& _3 m, |/ m" g/ Z        # II. 块逆转变异策略
1 w  [1 N7 y% c0 g5 y* K        time_startII = time.time()
        b_listII.append(min(tsp_solve(muta=2)))
        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
+ j* @( ]7 r1 u: L        # III. 同时使用上述两种编译策略
; b! @6 t" u( d2 `) c        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(muta=3)))
        time_endIII = time.time()
2 X9 k/ y; R5 u( Z/ P5 x$ X8 b$ {        t_listIII.append(time_endIII - time_startIII)

& {  @1 J9 u/ w    # 做排序处理，方便比较
    b_list.sort()
    t_list.sort()
" N+ w1 [/ }" a4 E    b_listII.sort()
    t_listII.sort()
+ j! ?) X8 g. a! S9 L    b_listIII.sort()
* V0 O: a  J0 E3 F' d7 k    t_listIII.sort()

    ax1 = plt.subplot(121)
, h' p3 h  r9 \  @' X    ax1.plot(i_list, b_list, 'b', label="Origin")
    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
$ L3 h+ @" y$ H9 O- g& A$ k  o& a    ax1.plot(i_list, b_listIII, 'g', label="Origin + Block-reversal")
8 _# ]  E2 `/ ~    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
& A. I2 C; l) p, z  Q; e' g    ax2.plot(i_list, t_list, 'b', label="Origin")
* F  l5 @; X5 S. R  N. r    ax2.plot(i_list, t_listII, 'r', label="Block-reversal")
    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
    ax2.set_ylabel("Cost Time")
/ f1 s/ P2 D. {8 f    plt.legend()
! Z# n9 o: J+ Q; }    plt.show()

1 P) C/ J7 v4 R3 W# 4.2 锦标赛选择策略对比测试
* B3 _( m# s! @7 M. H3 @def opt2_test():
' }  f8 o/ O% w9 C, X' `5 \, ~2 j    ITE = 20  # 测试次数
    i_list = range(ITE)
% c5 i- e( W: |1 M( {    b_list = []  # 每次求出的最短路径
    t_list = []  # 每次求解的耗时
1 f3 x' T4 @+ Z% {    b_listII = []
    t_listII = []
3 E5 w/ e9 z( ~0 b! _    b_listIII = []
    t_listIII = []
& q7 \5 K0 d/ q$ w( c; L
3 a0 P. W- w; i) e4 I, x    for i in i_list:
        print(i)
        # I. 原赌轮盘选择策略
4 C) ]- S% x4 z3 Q9 R. b# [        time_start = time.time()
        b_list.append(min(tsp_solve(sel=1)))
        time_end = time.time()
; z! d5 m, U3 X$ q        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(sel=2)))
6 k- c  s) p1 S4 q/ s% y        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)

    # 做排序处理，方便比较
7 Z: X5 l" y/ q! T  j( ~& b  J) O    b_list.sort()
    t_list.sort()
    b_listII.sort()
- j' T+ d  w8 n% K9 Z; j, w; P+ a* P    t_listII.sort()
    b_listIII.sort()
# S7 ?' [# q$ Q- z5 g; e! ~3 i) M/ c    t_listIII.sort()
/ k! J6 w# q/ M! k/ h
    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
7 I" z$ e/ Y& a! H+ U) a2 D6 E    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")
) Z0 x" ^: S3 B8 ^( s7 J# f: z9 _    ax2 = plt.subplot(122)
$ u& k* H" n0 c; q. H6 B/ Q    ax2.plot(i_list, t_list, 'b', label="Origin")
: {5 z' X" j" B/ ]3 m5 r    ax2.plot(i_list, t_listII, 'r', label="Tournament")
9 _8 y+ n/ B5 }+ Y9 k. |    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
- ?6 R2 m, R! Q3 F& T    ax2.set_ylabel("Cost Time")
; s( a2 p8 f- `( F# p1 k; T    plt.legend()
    plt.show()

4 C2 x- r- P2 a# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
, C- V4 F  V2 ~/ p; v4 V1 N+ gdef ori_main():
    time_start = time.time()
    pop = [] # 生成初代种群pop
    li = list(range(DNA_SIZE))
0 @- b' P) T; l    for i in range(POP_SIZE):
/ y; C9 j+ @" Q( F" q        random.shuffle(li)
+ l8 t. l1 u' x& s( B8 Y! F7 B        l = li.copy()
3 |+ @: q" A7 y1 t( v        pop.append(l)
" {* h8 R1 c, h    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE)
        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
* ~6 H5 y" z9 i# ~3 x: O        best_dis.append(distance(pop[maxfitness]))
        pop = select(pop, fitness)  # 选择生成新的种群

    time_end = time.time()
    print_info(pop)
& I3 B) o6 q% H7 V    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
3 Q- d) j2 p1 j    plt.figure()
    plt.plot(range(Iterations),best_dis)

3 {# b+ _2 b2 k  S8 O: E. X# 4.1 块逆转变异策略运行效果展示
1 @: @: b( g0 ^$ a1 |! ?( Ydef opt1_main():
/ `$ D) w: w' x3 U( F! k    time_start = time.time()
" H/ z5 }! m! D" w0 l3 ?" B5 U# u    pop = []    # 生成初代种群pop
    li = list(range(DNA_SIZE))
: n. }. B8 X% B) @; a; v4 i9 I    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
8 I; S& w/ G* r9 b5 U2 a    best_dis= []
" |- B6 l8 n. [! j  {' a, |    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
/ [0 z) K3 k9 P2 P" p  t+ N' H# t    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=3)
$ k4 r1 P( d/ h4 S/ ^  H        fitness = getfitness(pop)
& P+ \1 J) [' l! ~        maxfitness = np.argmax(fitness)
# B* q( g: c0 l& n9 C        best_dis.append(distance(pop[maxfitness]))
        pop = select(pop, fitness)  # 选择生成新的种群
4 {1 N$ R5 ^# h, Z* H" S3 b& p: i
    time_end = time.time()
; v* r" p5 `8 @    print_info(pop)
    print('逐代的最小距离：',best_dis)
  b; I5 E$ ?8 M# j( M0 V; m5 D: D    print('Totally cost is', time_end - time_start, "s")
$ ~: x& n: k4 y' T* j/ Y) L    plt.figure()
    plt.plot(range(Iterations),best_dis)

0 z% x' Z2 D# e2 sif __name__ == "__main__":
& N5 k. r$ f/ }9 W
0 ~; j* F9 l* S/ J    ori_main()    # 原程序的主函数
    opt1_main()   # 块逆转变异策略运行效果展示
    plt.show()
+ I  y* W# W  L    plt.close()

    # opt1_test()   # 块逆转变异策略对比测试
    # opt2_test()   # 锦标赛选择策略对比测试

2 S3 u( v$ G& D  y& u# J; J    # pop_size_test()       # POP_SIZE 种群规模参数测试
/ Q8 o# j( p# j: l    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
    # muta_rate_test()      # MUTA_RATE 变异率参数测试
    # cross_muta_test()     # 交叉率和变异率双参数测试


/ ]5 T# s" t" E& }' m( L( A6 l# T! Q1
2
7 H3 z: S$ l; I* b$ b3
4
5
  d; \- \4 F& y6
7
# t$ R, N" _! O' z3 ~% [8
9
10
11
7 C* Y; p5 |6 N2 O- o( p2 ~  s12
0 ], Y5 A2 t! Z13
# i% ~% r& g; ]14
. V# Z7 i& k5 ?5 M15
16
! D- }, `9 \' B  m2 H17
18
+ ~4 f+ E+ X1 K7 \2 o$ f  O9 `19
& |, Q: W; e5 Q; Z' c20
21
22
3 b- W9 \2 W, F- i- Y2 V3 P4 k23
24
1 C' ]$ i$ Q2 N' x: _. p0 ?25
. l1 }6 ^% C: `% t- \26
  `' _- i- Y. \+ K27
; _3 B% u' N/ n! A28
8 G3 H) x. ?3 r7 p1 I29
/ p4 i, S, B) S- H7 X- |8 y30
3 p7 y  |3 W& m  k, C31
& [  D' ~9 z* ^! D% r; \; H32
33
34
5 n. y: z0 z5 W1 u35
36
37
' d; j0 E! @% w) e* |2 l6 D. X. Y; k38
39
40
41
42
43
44
3 d7 K7 h! t1 f. I45
/ g& p5 `: X6 K5 B! b- D8 T9 \46
47
# i" _' q9 Q) _" g4 K5 r48
" `' k, K9 c+ Q% f49
% ^" c+ Q. R4 \" g: C50
- c$ s8 W4 L& p' O51
9 c) y( K: k1 P1 Q1 l52
) s" }: T% V  D0 q8 k2 q53
+ ?7 C' G0 K* }8 ^1 U0 X2 T54
55
56
- N% q) J( t# Z, T57
58
59
60
5 R: M/ _( c% b. p& q61
62
63
, H( M" D+ F* |# |" a1 i64
1 l7 f: W' I( _3 L: C1 l8 O0 s" ]65
66
67
& U7 _7 o, Z! }68
69
70
71
( @3 _! {, R7 d+ _% Q" }72
73
74
75
76
77
* A. f0 r* Z, K3 @/ x7 [78
79
5 ]! ?  }% s8 D% s80
6 p0 U3 Y7 y& I1 `) F9 W* q+ `81
82
83
84
& h! l( \: N6 ]- m$ q* w2 V85
7 q, W+ x3 Q4 S, j% U$ p86
0 ^2 b: ^. k  \+ \; G87
88
/ _# a  b) H! ?) i5 s" R7 H89
90
$ f- b6 v5 V0 \8 M91
3 B' u" ]' ^+ E1 `. r: ^, x  U92
93
94
95
96
( M% J* M% X% V. d* F4 _2 F97
1 D% D! D9 ^4 H9 v8 X98
99
100
; x0 D6 |. p5 \& X$ D101
3 P- N2 u9 h5 x* |3 H2 }102
103
104
105
106
# T) y4 U- U8 V; Y: S3 A2 d107
108
1 x% P: v$ G. n4 p109
110
111
112
# Q8 ?; [# k' Q" w$ {& l  F113
; A! r5 c7 f& X" V- \114
115
8 g3 e; Q# N7 i& H& T: c+ A+ R116
117
118
119
120
121
% D- Y& O1 e0 ~+ h122
123
% x1 i. a# s& G+ ?% _124
- [2 N, J3 }: ]" R: e$ t5 W125
3 \, p( b; G) ?! b7 ]126
5 {/ L# @: C+ C127
128
129
130
8 i0 J- ^1 {3 }& l, F6 C7 ?" h" L131
132
133
134
135
1 c! k* K" c8 S! x136
( E! d3 B( a) \) e" l# E$ F  I137
/ @: n' V0 V& b5 G& `* S138
; d2 f6 V0 S: T9 R139
140
* l  x5 R( b1 c141
" |9 d) L$ L! q8 {2 @- E3 G142
, P9 `  g) Q7 \) S' S) Z143
5 s. H: _! x9 h3 G144
145
+ ~( a# u1 Q1 l9 d& Y6 a146
147
148
149
$ y( k0 }, e' }" i# D% {150
151
152
153
154
155
; |. M; \5 g* }- c: n- r/ g) L* q156
6 @% O# h) ?; Q4 T$ S157
158
159
160
161
162
163
164
7 u. ?9 H$ z+ G  I" N3 x165
6 A3 L! B9 X* K8 Y6 P7 l166
167
. M% g3 |( o* ^& U# z) t  G168
169
170
0 I5 r) ?2 g3 \7 l' E171
3 e  p1 K3 C5 e2 [172
- v% X( K" j; q$ @0 m! J, ?173
& q- Q! H' \/ \7 T. a, |% |174
+ h  O: A8 ]% X% F175
/ |5 r5 R, {5 e" n4 D" z3 t5 |4 b) Q176
- B( q* [2 U/ m  k' W177
178
179
180
+ D8 M' S4 v  _$ I9 G: J+ U- H181
% e. @! y" d% J+ K/ b. q182
5 F( j" J( ?; ~& T183
& \" X# ~& o2 u184
185
0 @1 [) E- |- m* m" `2 {! ?, v* Y186
187
188
% }4 }* z$ V. T9 E! k+ g. R189
190
191
192
193
) s7 t0 r4 b. B194
195
# X6 s& w6 @' B( p1 ^# A196
, Q" r7 H8 Z" q197
/ r; m( |; k7 U: ]+ R) ~+ h: j3 `198
8 N% B% c, g& K- r6 N, H199
$ b( i* t- o7 T1 V8 s0 S& n200
201
" J5 B$ R' G% X$ y) r$ K0 l- C202
3 E  ^+ h3 o/ Y7 _" t203
204
205
206
207
208
1 [2 {, E& w# K- E5 ^209
210
211
212
213
214
215
" L: h7 C( u+ ?; _' q216
; e3 m4 g% H# G5 r  ]' T217
218
219
" }6 j6 o! @1 |3 K$ [. w220
221
222
223
3 @" h6 M5 y! c# i8 Y224
225
226
# F2 ?" `) q5 \7 l  ]227
3 q  E& O; a2 r# A( }228
229
" P9 ?- Q6 A  F/ F' X5 g230
7 _9 {2 d7 g% h$ S* u  `231
: q& `% \- l/ b1 q9 _; T  v7 J232
233
4 u7 |% H4 H% C, ]) N; g234
! o. Z4 O/ A$ F: m235
236
237
% N& z. f6 ~5 n: r' E+ p9 x6 o. p* |238
4 a5 G# o' A+ r1 d7 t239
2 O; s  Q+ s8 U0 |240
: E, X& O6 @+ G' B/ m2 @241
* J$ G9 t2 d: I( z  I242
$ I/ s7 _4 g  y9 P4 V  D243
+ D' L# |3 ^+ L% M; ], A244
245
4 Y  [! ~9 N- r; y6 s9 d246
247
248
249
8 Q7 D: u: d3 e$ j5 g0 j: |250
/ ~, Z0 x. J, I0 i5 C9 R  }251
$ q/ A/ g: n3 D9 G1 c3 i252
253
' Y, A) S$ D$ F4 x, J) T254
255
& M% _% o0 W2 c9 o( [& E3 h256
257
1 {; X- B- U+ B" e% y/ z0 u: j258
; \0 t% B, l* s+ h259
7 X: K. B6 K% e6 z4 C. {% t260
: p* t! d7 R  @# Z1 d261
262
* Q  w1 I/ s" H) Q" g6 d263
264
' z4 n# }  j4 d0 R% u265
& w! @# p  N& t3 s+ }7 K266
' m5 b1 f" L: y/ W; s) M- o/ t267
# z+ j! u2 z- R268
269
' u  h7 Y" b$ p: z270
: t! G# D0 R# L271
272
) H* c5 V/ u: P% f273
274
5 z8 x3 U# P" q4 V  C* l' J$ ^& d275
& h! |* Y, w* S5 Y/ `276
0 Y2 U! l& t" f' \7 \2 A$ ^& P277
+ w; l4 l, N$ a- h278
279
280
* G) U" {  ]0 C2 b6 ^; s0 A# q281
9 R/ _) A( Q1 B8 b# @282
283
284
285
286
287
288
289
290
& ^: c7 Z( F. W; S291
+ T, Z9 d, t- w, e* S292
293
! g( n; o# u( Z- g# l2 Q% K294
295
) {" k3 F: R+ r  h296
6 C7 a( \! v# _  f/ O9 A) [9 Y297
298
" d! ~& D7 A# c! q5 \( i' ]299
3 S( \" `# W1 t% j' J7 f0 Z300
301
302
; E' {- P2 i& E5 f! g6 v. o* [303
304
305
306
9 w7 {; Q9 X% A; R! p8 a" i3 J6 p307
: L0 p6 S1 C: j2 `; M: q' n308
309
310
! Q$ c# X1 v  k  V& g; j3 B: N5 L311
! U/ D6 o$ `( r7 J4 Z312
1 X, }' e$ I* i, y4 k; X313
+ m* i6 n4 g+ ~; B7 M. m% R314
0 `* N" O4 K8 W3 a- d- M- E8 p7 B315
  K$ c4 Z( k* v7 Y+ M! B2 ?7 ]& V316
317
" G* E6 l) m% O* v% \! ]8 G6 R318
319
320
# |! k' Q, |# M2 C  C321
4 \- {; p& x9 s3 O322
323
% Z# n, Y9 S) H, U324
6 q* s2 ?9 W6 |8 N325
326
327
3 h9 W8 K9 C1 B328
2 s1 Z; I' r$ [& J& g329
330
3 @  Y% A# f+ C+ o" b% I7 p( Q: e331
: Z3 @  p, q) D2 i332
. ]7 d5 J) ?+ h* o! f333
334
, {- u' J/ h8 N) z, C335
3 G# K. D) u6 ]2 g3 M4 C6 o6 |& T, n336
337
338
339
, x' {5 W; k! J- w7 E' ]340
341
1 ?  }( e2 K+ j! n$ g/ w& E342
4 }! P9 r5 I% ?) I. c& ?343
; m6 {* Y2 B+ F5 }( d344
345
# n# j0 L9 P& B0 J346
347
; P) g2 A! }/ c) B' j3 L  S% U348
$ B. M) f9 D+ K/ s' m& d349
4 M; M9 J& r2 H* Z& l4 a350
351
  a) w/ B& a+ ~2 y352
353
$ i' ?  t! D" C, A2 t354
% d0 n% T# K" b3 ^355
356
357
' E% J* Y# w: |1 W4 ~! L358
359
360
$ x+ y: j$ `" _2 o$ t361
362
6 ~: L- Z- i4 `* }# b363
1 l: k/ P" I. L3 y& u. G364
" T; f! `2 ^0 w' |: J* ~365
' I4 i  W- r! R366
367
368
369
370
371
5 }2 }) K7 J( u( W372
373
  @2 p4 H* o; x4 x4 C374
, P5 M6 }7 U" _375
376
377
: C$ x% C- R/ A3 X378
379
380
7 z4 O0 y1 M0 {% H6 x8 g381
0 H/ D7 c5 f; l# d- v8 c: M# w382
383
384
385
" H6 ^! ?3 t' Z. x" U386
# D9 u  B( W3 ?8 V! t, a( N3 G& N0 Q- {387
( z0 C9 S2 s2 v388
389
! N! \% `+ z) X# l8 C390
1 [0 A. p. u- a* U+ h391
392
* h( F; w# j! u* ~3 c393
394
8 H) D( j- M/ v395
396
5 u% v  O; _4 V) s# C- L397
398
' @) q/ M/ E3 v: K5 I399
4 B7 z+ d; ]7 `; h! r400
401
402
+ F2 b; e, T5 T403
) ~) ]3 f' [! M404
# {! X) D- m' ~* m% A# N0 {3 J( q0 r, X2 q405
406
% l2 E8 H( P/ I6 ], w1 Q407
408
409
410
6 r8 j; `) p+ r+ a9 w" O5 ]411
) @# i$ Z0 W# j0 C: g9 x! p# |% s412
1 p# L; z2 ?$ m) t, F413
$ @, {8 K- f" E5 S414
415
! ]& Q& l5 l4 _416
2 i; S7 _: p# p, d5 U) i417
5 N& O) q% e! S, R0 c418
419
420
421
422
) O! g( v, n" C7 F423
0 @6 R: o4 p5 d9 @% ~. F# d424
425
( D* u+ E9 e8 s8 `426
427
428
429
; @% s* e" X, B" U430
431
, f) {' g, _0 w/ m8 {, b) `0 v432
433
434
435
: U  c+ q! w0 i436
" k" H9 R. ~4 F3 s& ]437
438
1 l3 o6 E% A3 F# G8 X1 u439
440
2 C4 A2 f: y  A- f441
442
' f- q7 ]. `# D1 K( p443
) S/ g' I- @6 Z5 Q: W, e7 c/ f444
445
446
447
% w. T% h! d/ w& L, Y448
449
450
451
- F  B& Y5 `# T1 K: _452
8 @: u4 t! n& R0 c  O& ?- N453
1 r) c- L) Q# n% r, V. K& {454
% V7 F' E8 ?5 |2 A( E455
456
% [$ `6 E8 s' d) }6 G/ x( j; ^$ t6 ~457
5 o" l9 j( q" P4 P) l458
459
8 s" y' b5 h4 ^6 F% P9 i5 e% f460
+ e8 W6 C/ T9 b( l3 S7 x9 z2 W( H5 G& j461
462
463
# X) U7 [" @$ m, h$ n464
465
466
467
468
# m+ V/ S9 ~0 u3 \3 C469
( `3 W: @2 c) m% n, N5 j
0 t8 A" i* S# u0 n
, F# w- v0 W6 F0 j5 V0 C. S
! h7 d3 G) ^% H, q8 V


9 ]3 {0 L/ l- f, F( ?0 u; r
$ P1 H, W' Q0 j  K5 Z1 k3 x( t

+ Z7 O# P/ b' J3 F8 {$ S/ O1 w
& y+ n8 U3 C6 `7 Z


/ H6 q4 H$ J  g. R1 p# C2 V3 F





  f. U! |' p8 i3 D9 J' ]1 i
% D3 h7 }# `2 X$ j
6 N; V" O$ i- u) W) W: X
" C( q3 N/ w: x1 A6 P
/ w3 }# Y- P- n2 s  S2 D


6 |/ L" g- Z5 ^
————————————————
& @( O9 B$ H: y, ?) h1 C/ p3 E版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 [8 n2 Z8 H# q: d0 Q) Z+ ~6 p8 j5 H原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212
" C; U' ?. c9 v8 f' m! Z


  N# I! V2 o( X) p! [( A& G