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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
+ a) ^  C( ^0 P目录
) q- g8 ^1 @& |; P: r0 _; M% p人工智能第四次实验报告 1
遗传算法求TSP问题 1
% m! E2 Y! i( y% s! \, O0 e# \3 {一 、问题背景 1
1.1 遗传算法简介 1
1.2 遗传算法基本要素 2
+ o) J! m# F; l1 a" H/ x( F; V, S1.3 遗传算法一般步骤 2
0 w0 o# e3 |2 o, G二 、程序说明 3
3 P  I0 Q+ q2 K2 ?1 @, y$ k2.3 选择初始群体 4
2.4 适应度函数 4
2.5 遗传操作 4
" a* U" q+ p" B% H# U/ n/ g2.6 迭代过程 4
; U' X  O/ s& O1 y9 T8 q' U+ M8 R! u三 、程序测试 5
; _" u  X* |' @% Y( }" U3 R* H3.1 求解不同规模的TSP问题的算法性能 5
3 v1 Y6 K/ g0 n( p! U: y: \7 `- O9 ~( e3.2 种群规模对算法结果的影响 5
: a+ S) D$ v2 K$ H3.3 交叉概率对算法结果的影响 6
# o  a6 T) _. `% n$ U7 h3.4 变异概率对算法结果的影响 7
+ q) o, Y4 N5 [' E& w. q3.5 交叉概率和变异概率对算法结果的影响 7
- E" w; d7 T( ~) r四 、算法改进 8
' Q( ^7 V' B4 x4.1 块逆转变异策略 8
! q+ C/ I9 i( z: N  @4.2 锦标赛选择法 9
( n; A# F7 ^! W( `. ]! [五 、实验总结 10
+ w8 B' Q% b/ a& c( E& n# R一 、问题背景
1.1遗传算法简介
遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
& ?  R1 B2 y# L. o" x/ S遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
5 O3 M! @) u" B1.2遗传算法基本要素
9 Z$ z+ g  J' d+ }1 U0 X1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
" W$ W0 x$ ^8 u5 e2.设定初始群体：
1.启发 / 非启发给定一组解作为初始群体
2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
: S6 E# ?# L: _2 y9 N8 q9 U4.设定遗传操作：
/ X1 v* p7 U" x1 U' V$ q1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
8 ]1 A  I1 x3 Y0 R2.交叉：两个个体的基因进行交叉重组来获得新个体
3.变异：随机变动个体串基因座上的某些基因
5.设定控制参数：例如变异概率、交叉程度、迭代上限等。
0 y" I' G+ z6 G% o) Q2 F- s1 q
& {) ~8 j% U" V0 V9 oimport numpy as np
import random
import matplotlib.pyplot as plt
# D# _9 v; }6 j& o6 h6 l( o; ]import copy
import time

from matplotlib.ticker import MultipleLocator
" f+ Y2 `! J& s) L9 L9 Dfrom scipy.interpolate import interpolate

7 d# ~2 [* E* P( V: r' }CITY_NUM = 20
City_Map = 100 * np.random.rand(CITY_NUM, 2)

# G8 E; p# w9 k( |" u, EDNA_SIZE = CITY_NUM     #编码长度
POP_SIZE = 100          #种群大小
! B7 w0 k# z5 L. p4 V% mCROSS_RATE = 0.6        #交叉率
7 ^1 R( t" S& e$ K* jMUTA_RATE = 0.2         #变异率
* Z7 c) O5 e5 pIterations = 1000       #迭代次数

# 根据DNA的路线计算距离
def distance(DNA):
$ X9 N6 Y6 B+ _' E    dis = 0
2 s8 o/ ]& r/ Y) o    temp = City_Map[DNA[0]]
# x/ J& q# ^6 z0 p3 Z    for i in DNA[1:]:
        dis = dis + ((City_Map[0]-temp[0])**2+(City_Map[1]-temp[1])**2)**0.5
1 ^& V+ |1 J# \0 x        temp = City_Map
    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5
, ^0 z6 t: `* D: a$ j( ]
2 H8 W6 P/ I! F0 K# 计算种群适应度，这里适应度用距离的倒数表示
( ~$ ^4 @1 f8 k6 O5 \1 Q  Kdef getfitness(pop):
3 v- |7 ~+ K3 S+ n4 V9 x; ?    temp = []
  C; r% `+ R+ S/ v# E0 P  q- Y0 j& K    for i in range(len(pop)):
1 L+ ~+ J5 }- B: S6 F# n) E8 v/ J        temp.append(1/(distance(pop)))
    return temp-np.min(temp) + 0.000001

9 }+ p+ o9 o& d# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
" z8 P/ O# P! F, O* L( ~) xdef select(pop, fitness):
    s = fitness.sum()
6 }3 \( r* V& W$ }) \9 a9 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)
    return p

# 4.2 选择：锦标赛选择法
def selectII(pop, fitness):
    p = []
) a( K) @; Y" H* B. F: _    for i in range(POP_SIZE):
        temp1 = np.random.randint(POP_SIZE)
9 w6 e; ~3 ^+ O  b/ h3 k        temp2 = np.random.randint(POP_SIZE)
        DNA1 = pop[temp1]
        DNA2 = pop[temp2]
3 e6 [! c7 ]# Q. y        if fitness[temp1] > fitness[temp2]:
            p.append(DNA1)
        else:
            p.append(DNA2)
    return p

4 C( Y5 |6 D1 b' s* g; K! {# 变异：选择两个位置互换其中的城市编号
5 w, N- q: q% x7 ]" odef mutation(DNA, MUTA_RATE):
* j( F% y: I( T' b7 Z/ `, H    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
, x+ f& @$ g3 I% K0 K, `        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0,DNA_SIZE)
        while(mutate_point1 == mutate_point2):
            mutate_point2 = np.random.randint(0,DNA_SIZE)
# v/ O: {6 h" ~8 F7 k3 j        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]
2 G" k, c; n" D: o0 f, H  M
# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
7 L7 a" K2 o5 C  N: N0 n8 Kdef mutationII(DNA, MUTA_RATE):
* i# |( _! w$ r    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):
' a0 K2 n1 `7 P1 D! ?  _            mutate_point2 = np.random.randint(0, DNA_SIZE)
- Y: p0 x$ u( c: Z+ K- P1 D1 r        if(mutate_point1 > mutate_point2):
/ y: D, @/ n% W9 ~$ r1 @2 C            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
        DNA[mutate_point1:mutate_point2].reverse()

# 4.1 变异：调用 I 和 II
def mutationIII(DNA, MUTA_RATE):
- R9 V  ~3 \9 ^3 X" s    mutationII(DNA, MUTA_RATE)
    mutation(DNA, MUTA_RATE)

0 v/ W$ w4 \9 Z5 j- `# 交叉变异
# muta = 1时变异调用 mutation；
: ?! X8 i. {# {# muta = 2时变异调用 mutationII；
1 V% ^9 ?: X/ M; J5 u0 h# muta = 3时变异调用 mutationIII
2 I- ^5 a$ }( T# s8 Adef crossmuta(pop, CROSS_RATE, muta=1):
    new_pop = []
$ e0 |) d. T7 P! m. j    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
% q. s4 o4 l- r+ \9 X; X        n = np.random.rand()
        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
3 ~* t& L* {/ Z            temp = pop.copy()
1 l- D1 J0 f+ J& M. i# L+ e; k            new_pop.append(temp)
        # 小于交叉概率时发生变异
        if n < CROSS_RATE:
' i, P% ]7 h% z) b  t6 c% d            # 选取种群中另一个个体进行交叉
            list1 = pop.copy()
% B3 C' ~. C% f$ s) x3 t5 A2 w            list2 = pop[np.random.randint(POP_SIZE)].copy()
            status = True
            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
            while status:
. V0 U9 A- {* |8 u6 \                k1 = random.randint(0, len(list1) - 1)
                k2 = random.randint(0, len(list2) - 1)
& Q( _9 x- f3 ]                if k1 < k2:
! K+ @" z+ g0 _* L* ^0 p                    status = False
0 i0 r5 f1 @' o. D
            k11 = k1

            # 两个DNA中待交叉的片段
            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]
2 D9 ~% X2 L5 _% t) X
( F! X. N- [9 `) x7 m! ?            # 交换片段后的DNA
0 b3 i* f1 h# M; i3 o) {            list1[k1: k2] = fragment2
            list2[k1: k2] = fragment1

            # left1就是 list1除去交叉片段后剩下的DNA片段
5 c9 A' z: c5 K1 @: ?! o            del list1[k1: k2]
: T7 d; F: }( u+ T3 o: l            left1 = list1

+ x2 R9 i3 B' s9 ?0 M, D- h# J+ B            offspring1 = []
% E9 s5 i) e7 L/ k, n# b; V2 S            for pos in left1:
                # 如果 left1 中有与待插入的新片段相同的城市编号
7 w% u4 F$ \) A9 o' f; Z2 b                if pos in fragment2:
% c: F0 E$ x& e' j5 I                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
                    # 循环查找，直至这个城市编号不再待插入的片段中
                    pos = fragment1[fragment2.index(pos)]
& K& r- A) a$ b5 s7 k. @# }                    while pos in fragment2:
* A) B3 F* q% U7 X; A8 e1 Y) a) E+ W                        pos = fragment1[fragment2.index(pos)]
. u( u. a7 s& ?- X                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
- g" @! J$ |# z, A- J                    offspring1.append(pos)
( I* d9 `6 }4 K/ R5 J! p                    continue
                offspring1.append(pos)
( v1 p6 ^$ y6 I            for i in range(0, len(fragment2)):
0 z* O3 @. l; h: b- t) M, Q                offspring1.insert(k11, fragment2)
                k11 += 1
            temp = offspring1.copy()
            # 根据 type 的值选择一种变异策略
            if muta == 1:
4 ~4 o0 |2 _+ R; k7 r                mutation(temp, MUTA_RATE)
9 S3 z( u0 I1 \; o+ t* P8 N            elif muta == 2:
$ t  H1 }# @$ P5 f$ i                mutationII(temp, MUTA_RATE)
+ g, U0 [% n% W7 p; Z            elif muta == 3:
6 w1 h6 z1 o6 ~; W( U$ X                mutationIII(temp, MUTA_RATE)
, Y: `: g) k5 X6 ~5 u5 F            # 把部分匹配交叉后形成的合法个体加入到下一代种群
            new_pop.append(temp)

    return new_pop
! L. n# g  O' a* \  _8 n6 W
% d6 K9 x2 @' d* m/ T7 @9 Ddef print_info(pop):
$ z& n3 E4 ^/ ]( h1 [1 r; c! `    fitness = getfitness(pop)
. S1 h$ W, Y- k8 f    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
    print("最优的基因型：", pop[maxfitness])
  ~6 f( `- l- l& O* X3 Z" [    print("最短距离：",distance(pop[maxfitness]))
- C9 u- L, l8 ~4 Y1 N7 h- {    # 按最优结果顺序把地图上的点加入到best_map列表中
    best_map = []
0 R- m/ o: G& S    for i in pop[maxfitness]:
  ^" N* W( H& H4 c        best_map.append(City_Map)
6 E* \7 F; z& i    best_map.append(City_Map[pop[maxfitness][0]])
$ y# @& e  P2 I1 v( D9 v    X = np.array((best_map))[:,0]
    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
6 E8 C" q3 j6 S2 G1 `  A- f    plt.figure()
    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.scatter(X,Y)
    for dot in range(len(X)-1):
        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
    plt.plot(X,Y)
2 U  @$ U8 ?* W( |$ H+ d
# 3.2 种群规模对算法结果的影响
" p; h7 k5 J+ G1 gdef pop_size_test():
9 `  R) l( U0 o: I. W: ~    global POP_SIZE
% ^1 |# N2 |3 _" v4 D    ITE = 3 # 每个值测试多次求平均数以降低随机误差
! k/ L. A) \' Z9 O( A    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
    b_list = []
6 o) C- J, H; `- E% q    t_list = []
    for i in i_list:
        print(i)
        POP_SIZE = i
: C7 _+ B' ^* _2 `        time_cost = 0
        min_path = 0
7 Q9 {. l* K$ f        for j in range(ITE):
            time_start = time.time()
$ e6 j5 K0 U% j9 [# B% K7 l            ans = tsp_solve()
            min_path += min(ans)
4 u/ z- l3 k# R# U8 a& C            time_end = time.time()
            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
; P3 U. Y; e" [% p: Y5 Q5 m        t_list.append(time_cost / ITE)
# }7 c$ p: r% m; \    show_test_result(i_list, b_list, t_list, "POP_SIZE")

% l9 S" K. u4 v# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
+ G$ k; ~" A% {4 S  v* k7 s    global CROSS_RATE
; E; ?% W0 L0 B; \! }0 @, y  G    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
    b_list = []
7 c" R; W# G, v9 L. [    t_list = []
$ j. G  S* f7 S* P    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
        CROSS_RATE = 0.05 * i
5 K5 ~; X4 Z! m( X2 U2 B        ii_list.append(CROSS_RATE)
        time_cost = 0
' |  f: K$ D2 ~" ?/ ^5 l1 t, h        min_path = 0
" e8 _" D$ O. L4 |        for j in range(ITE):
# G/ }( x* D9 I  j! T" T0 V9 N) m            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)
' q% M+ ~# J- u. K* X    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")
0 x5 U" r$ e( g3 P. B, E6 Q
# 3.4 变异概率对算法结果的影响
def muta_rate_test():
    global MUTA_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
  @5 z0 t, c/ c0 f% G- ~    for i in i_list:
- v) L3 ?5 ^5 P3 L( Q: L7 G- s# T        print(i)
1 Q: M% R' l  a7 ^        MUTA_RATE = 0.05 * i
7 Y6 f3 ^' |2 b9 I$ ~        ii_list.append(MUTA_RATE)
4 ~" _. A- ^0 Z$ S        time_cost = 0
1 d1 z/ x0 y1 G: }/ y4 l        min_path = 0
  K' N# t1 c  A7 D0 q6 }        for j in range(ITE):
  q, S0 i1 J. A9 t1 q            time_start = time.time()
* V# d. A; _. Z/ H; u            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
5 p) B0 D* N2 ?6 ^) d0 _; y$ A( E            time_cost += time_end - time_start

3 B, ]( i, M( S5 S( q        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
- ?6 B& F( g; Z6 h8 j) e. l    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")
+ s) V1 x) E' _& \2 ?/ {
# 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)
- ^5 a/ y2 ^6 M; c- i2 P8 i    Z = np.zeros(shape=(11, 11))

3 s+ v1 c. ^9 K1 L! E    global MUTA_RATE
1 X' k, }+ x- H4 b& Q. q% _    global CROSS_RATE
3 J2 \4 h1 z- }4 N. V    for i in range(11):
7 C& L! f. E2 a: Q6 ^5 t! \        for j in range(11):
            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
/ ]- X0 y  P: k3 C$ p& x7 A2 a            MUTA_RATE = Y[0,j]
) K& s: @9 u- d8 _; K2 z: |7 }1 k! v            ans = tsp_solve()
            Z[i, j] = min(ans)
4 a8 G( m) ]% k  C* \) v
0 w, s$ q( |% M4 K* S5 y    ax = plt.axes(projection='3d')
    ax.plot_surface(X, Y, Z, rstride=1, cstride=1,cmap='rainbow', edgecolor='none')
9 Y5 e3 b: }- `5 W6 A  a, w- ]/ d    ax.set_xlabel("CROSS_RATE")
5 V, e  Q, P% S# {& l3 X" K    ax.set_ylabel("MUTA_RATE")
    ax.set_zlabel("Shortest_Path")
    ax.set_title('TSP')
6 P4 _5 D! N) \9 c    plt.show()
4 }  J1 t  F6 l: _
( d+ e( d, N2 M8 q) a# 3.2-3.4 生成参数测试结果的可视化图表
def show_test_result(i_list, b_list, t_list, msg):
8 z1 f$ }" b8 L) i, X  i    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b')
' }" b! K; `/ n' h+ Q% V9 D# w" V4 d    ax1.set_xlabel(msg)
    ax1.set_ylabel("Shortest Path")

    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'r')
$ ]% g& m3 C1 t9 h    ax2.set_xlabel(msg)
- z$ m  n0 S; a+ C5 n' g: [    ax2.set_ylabel("Cost Time")
    plt.show()
" ~9 X5 Q5 W& d
# 求解TSP问题并返回最大值
3 K: X/ S3 j% ~9 x# @# muta 指定变异方式，sel 指定选择方式
0 e# j& |* U5 A) s- Vdef tsp_solve(muta=1, sel=1):
5 d5 X7 V7 E4 l# u    pop = []
" }% C- M- v# j    li = list(range(DNA_SIZE))
, I- w6 h& O6 @, @3 d' ^    for i in range(POP_SIZE):
        random.shuffle(li)
* Z& R* B2 S7 ?, w/ V5 B        l = li.copy()
        pop.append(l)
) H# I7 X# E3 G6 J    best_dis = []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=muta)
        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
" O5 B: e/ N9 {% A; d6 |1 f        if sel == 1:
  M7 I7 u1 I$ P5 h: b; V            pop = select(pop, fitness)  # 选择生成新的种群
        elif sel == 2:
0 K# v4 P0 i5 d+ r6 G) B' M9 p: N            pop = selectII(pop, fitness)  # 选择生成新的种群
" p8 `, W) _- v( E
- M/ X! m: M3 m. C9 ^/ i6 e8 X3 ?& f9 ~    return best_dis
6 H) c# N0 u( F6 N+ d! ~
: g0 a2 d7 S& d# 4.1 块逆转变异策略对比测试
' `3 W" ?' F2 r+ F9 G1 I# Vdef opt1_test():
    ITE = 20    # 测试次数
) y) G7 e4 _: p9 k- t; m: }    i_list = range(ITE)
    b_list = []     # 每次求出的最短路径
( p( \4 n5 ^8 _7 a* w# E    t_list = []     # 每次求解的耗时
. K+ c$ H4 {" H" i" ^    b_listII = []
    t_listII = []
    b_listIII = []
# q! T9 X% O" W9 P    t_listIII = []
) G- B( J6 ~. {! S* l4 a
    for i in i_list:
        print(i)
        # I. 原两点互换异策略
* E3 u& o$ Q3 \. t( J9 [  I, l3 E        time_start = time.time()
        b_list.append(min(tsp_solve(muta=1)))
) x. O3 a- g9 I        time_end = time.time()
        t_list.append(time_end - time_start)
        # II. 块逆转变异策略
$ D* W4 c) [2 h1 P; ~9 Z9 b, ^        time_startII = time.time()
  t- z) ~2 a# r6 O- E3 M        b_listII.append(min(tsp_solve(muta=2)))
# g. o5 d0 F8 a$ z        time_endII = time.time()
7 m' F3 K4 W2 P2 A, I" ~        t_listII.append(time_endII - time_startII)
: g% {$ q0 @$ i# F. W6 J8 O        # III. 同时使用上述两种编译策略
        time_startIII = time.time()
6 i, j" [3 ?  q% ^5 n. m8 x        b_listIII.append(min(tsp_solve(muta=3)))
. S; u+ a  t3 R7 _6 n0 Z        time_endIII = time.time()
1 L- T" S& l" q+ O/ O% F        t_listIII.append(time_endIII - time_startIII)

+ Q, @7 _+ t: ^1 d    # 做排序处理，方便比较
1 |; P# [  O' K8 b, v& ?    b_list.sort()
    t_list.sort()
$ Z. U1 Y: v' S  p' k* y1 e& A    b_listII.sort()
    t_listII.sort()
! O) U, l2 b4 b& I    b_listIII.sort()
: V: [4 m- a& c0 L    t_listIII.sort()
/ h9 f  w7 T+ Q: J
3 o; B; K4 e$ O/ s    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
! Y5 C2 D: y. G: E3 ]  F( v    ax1.plot(i_list, b_listIII, 'g', label="Origin + Block-reversal")
    ax1.set_ylabel("Shortest Path")
/ t8 q$ W" g/ |' s    ax2 = plt.subplot(122)
    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")
    ax2.set_ylabel("Cost Time")
( B) D% S$ t; P( C    plt.legend()
, |, n% d8 D6 v8 D, e    plt.show()
4 @9 S+ F8 y6 A- H+ D  S  R
( e4 ~7 ~1 @( B- i1 ^% X& K# 4.2 锦标赛选择策略对比测试
+ \: r+ Z& v! i6 m' B4 Kdef opt2_test():
/ O' o& u1 Y5 N8 B& k; R    ITE = 20  # 测试次数
2 @9 x" p8 j% B# X    i_list = range(ITE)
- a. J# ]! i- d7 X4 i    b_list = []  # 每次求出的最短路径
0 `! X% }- D7 W8 T- a4 E2 V    t_list = []  # 每次求解的耗时
4 l/ i, \: n( G" ^9 B    b_listII = []
' l7 D( F/ F9 y: j$ l3 |2 w! F    t_listII = []
    b_listIII = []
    t_listIII = []

    for i in i_list:
$ R& q  F2 [, W        print(i)
        # I. 原赌轮盘选择策略
) r& g$ K0 E1 C6 U& t        time_start = time.time()
; T1 _+ f- T0 Q        b_list.append(min(tsp_solve(sel=1)))
3 `6 B1 u# ^% q9 S. @" G' n        time_end = time.time()
' @& n3 N% i0 B+ c        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(sel=2)))
/ u; j* P& g. R5 a9 V6 v; p9 k        time_endII = time.time()
9 Q0 Z, T2 u# N7 R, d        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)

5 Q/ {4 d& i0 N9 F, C; O    # 做排序处理，方便比较
, Y! {8 _5 w7 p2 c    b_list.sort()
    t_list.sort()
    b_listII.sort()
; X4 t3 l6 d0 l9 N3 K    t_listII.sort()
" ]% @# r  j: ^6 D    b_listIII.sort()
0 v' N: F1 A5 e' D7 k& b    t_listIII.sort()

    ax1 = plt.subplot(121)
6 d1 q6 J& n1 \3 A0 ]    ax1.plot(i_list, b_list, 'b', label="Origin")
$ v, \0 _0 Y' I8 w    ax1.plot(i_list, b_listII, 'r', label="Tournament")
& G9 @* y. a: h8 y$ Y4 @1 L    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
# r" D: t7 x* H0 G    ax2.plot(i_list, t_list, 'b', label="Origin")
& ^) p% `- m- G$ [* k( k    ax2.plot(i_list, t_listII, 'r', label="Tournament")
& ~4 }( w. W; O    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
7 K* `( N5 N4 u# p7 x  j& u    ax2.set_ylabel("Cost Time")
    plt.legend()
( W3 i# t/ v  B6 E# G) W    plt.show()

. n" a/ n7 T0 Y- N# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
def ori_main():
0 y* o4 q+ |0 u0 v! f    time_start = time.time()
    pop = [] # 生成初代种群pop
8 o/ U% a/ L" S* C* f$ j2 c' Q    li = list(range(DNA_SIZE))
0 O5 v) Q, O4 R    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
3 X& W. l' W9 U        pop.append(l)
' x( r0 c5 x/ y. s# w5 o    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
! |& I( ?' S  ]2 n$ M# o7 @        pop = crossmuta(pop, CROSS_RATE)
8 o. ?% e6 s1 B5 W! s        fitness = getfitness(pop)
* O( f( O; j4 P" X        maxfitness = np.argmax(fitness)
" [# j3 f# M2 _  V8 x* b" Y; B: F        best_dis.append(distance(pop[maxfitness]))
! R' m. ^8 E5 s4 J' c/ s        pop = select(pop, fitness)  # 选择生成新的种群

    time_end = time.time()
% E' J& L* J* I$ g' c% o& X    print_info(pop)
" U- ~. j4 n/ s0 i0 o8 f    print('逐代的最小距离：',best_dis)
" H* R  m" d3 P. z( ]# M    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
7 K  W, Z: j/ t% @    plt.plot(range(Iterations),best_dis)

# 4.1 块逆转变异策略运行效果展示
8 T; ?6 m, w; l) pdef opt1_main():
    time_start = time.time()
    pop = []    # 生成初代种群pop
    li = list(range(DNA_SIZE))
: T2 N4 ^  `  a1 i    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
  d- D4 \6 B/ Y; M# u, O+ B' b    for i in range(Iterations):  # 迭代N代
$ u, C$ ?- {0 K7 q4 O2 r) v, S        pop = crossmuta(pop, CROSS_RATE, muta=3)
9 U; u8 w( O7 t8 ?+ P) W        fitness = getfitness(pop)
& z& J# o, f$ E5 c0 N7 F        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
" Z) m$ [0 M9 Q        pop = select(pop, fitness)  # 选择生成新的种群

' \3 h. A) B3 r/ V: J    time_end = time.time()
    print_info(pop)
; K5 t! F9 {( v    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
. K1 r. ?# L$ b+ [    plt.plot(range(Iterations),best_dis)
" e- `6 P. ?: W7 g5 E/ Y+ p; j& |
if __name__ == "__main__":

    ori_main()    # 原程序的主函数
    opt1_main()   # 块逆转变异策略运行效果展示
    plt.show()
* H3 [: X, a3 j( y  m6 D    plt.close()
$ J3 `: t  t& G  m. o
    # opt1_test()   # 块逆转变异策略对比测试
    # opt2_test()   # 锦标赛选择策略对比测试

    # pop_size_test()       # POP_SIZE 种群规模参数测试
* i1 i- J! C/ D  b* P    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
    # muta_rate_test()      # MUTA_RATE 变异率参数测试
    # cross_muta_test()     # 交叉率和变异率双参数测试
5 V" ?/ [, ]8 @1 A
" E4 r  z& |5 M8 ]9 O& `) S
- `0 W* S) H1 Z8 W1
2
3
4
5
# g5 |7 [! N; G6 f8 z9 E$ P2 i6
: T3 d" o8 @/ L' m% m7
! I) H4 |; `2 w8
9
10
- \' b: p- _8 P1 f/ P11
12
13
14
- f+ J+ k" I6 y" y# N& m& s! i& a15
16
17
5 u6 W- {5 n$ [# c9 ^! s18
, N5 l% _. f; i0 b" t6 p19
20
$ H/ o! o8 p- u+ k4 W8 {% j21
22
23
) t, e' D; W0 [- B9 b% t, ^/ s. L0 E24
9 T1 T; r1 T0 o4 S25
7 l/ N" M9 a0 I' _26
4 d) U% H* u" r27
28
29
30
31
32
$ j3 s  s5 z) V1 Z6 q- z4 S33
34
7 e! B9 R! F" c5 E35
36
" z* z: Z% l1 L! U1 e37
; w$ @! r6 U$ ~- D* p38
! y( X4 B* Z8 ~3 X( A6 i39
% Q8 P1 H6 a( L4 `3 A40
) C$ i# F# t6 p' U! h' h41
42
43
44
* L" x; e3 t/ H& {  C+ u* a8 U9 H' x45
46
47
7 o2 V; J) q, ~/ R$ x; [& s4 }48
1 o4 o, ~' y: ~6 L$ K* f# r; q4 J49
( A  ~. F9 c& N( E50
! g% v/ z2 i$ U6 a( q# d51
52
53
% W* W) C$ p+ I' a. l54
55
56
57
58
" E$ N( K3 X& K, q: j% |3 {; }59
60
61
0 [$ [, b# g! G: T  P& q62
63
64
4 P+ P- n4 h' `9 ~1 m1 g/ F+ T65
& Y, @' V' @5 Q1 w66
7 d0 P5 J$ \) @0 g67
68
- \& p- @& i  D8 [69
70
) P- d0 k# ]. ~6 O, R& |# W0 ^, l71
+ B( |0 @+ n( Y! c! t72
73
74
7 S& z0 o" e& ^75
  R; z+ B/ O  ]% l76
77
78
79
80
81
82
83
84
! O" ~' j2 |- k/ y7 f* J% W) U85
86
8 j: Z7 f4 E  G7 N87
88
" ?! t# O7 G3 G8 A& B2 k89
1 Z0 u  E( {% w2 k/ ?90
8 @6 Q2 m1 U$ A& z8 X% s$ Z91
92
' `9 U) q6 W4 w  c% l: ~# w2 X$ Z93
  x  C8 L9 a' X$ ?94
, R% l8 I/ y/ B/ ?2 t- y95
# C/ w5 [" Z1 K/ u  N( [# p96
  j, m, J  b" n  F97
98
) }: m1 t  O8 l) r8 {& M/ X99
- p( {2 |/ L' `4 e# L4 @100
101
2 R% ~2 \8 m: ~102
103
104
105
106
) P% _- Y: g8 @( r1 n: C0 \107
6 S$ ]4 l. P. `+ e  b/ n108
% |0 h7 G3 Z5 K; R109
110
111
112
113
114
5 o8 o9 [% [' f7 H115
' @4 C- ^# z  H( C116
* L; {3 T4 S) L2 X, G3 ^117
; R: \: B5 i& n% z* [1 A118
- N2 c8 K- D* V( C119
' b' D! L! E: c  q120
( b5 h- q0 v3 I( F7 g6 d121
122
. g( U, M0 W# X$ H! R" E123
124
4 f9 h2 w6 ]! e& D125
" B% e5 |% z* p1 ~- Q4 r126
6 C8 {4 B. }- D127
128
+ m7 P8 b  p' o; S129
130
131
132
5 c6 {& K5 g) {- D& W( W$ ?* t133
134
135
; G5 X( ]7 ]1 q$ E- P136
137
9 Y5 d: a( j3 c3 B# Y138
139
( }; u% w% l4 s8 a1 P140
141
142
143
* S0 X7 r5 t3 f& S144
145
' K- h; y4 v3 @; a* o" A: F146
147
/ j- T. c# _" p& e0 S# Z" j9 W148
149
% Y8 }9 d9 H! k/ Z  J& u5 y2 W150
4 q3 P$ [' V& W. Q1 J9 A: s151
152
' z, T5 F0 y7 V9 D' E! ^/ _- p3 e4 z153
154
9 o' x, ?6 S9 r3 P155
, m& i0 I7 ~& _' L: X156
157
  L0 R' h- b" l* n1 D+ G158
& F5 \& \  k' W$ t3 p159
* F% t! ~1 P/ B0 `6 W" \160
1 n  i! j; z9 D; {9 C$ C161
162
163
! K, e) c  \3 s* g$ |# S164
2 t2 b7 X& i* E/ I165
166
+ O. I! p* W- C167
$ i( B" N$ f5 v168
; C$ ^- J) `1 c- M/ S# t169
170
) R$ t3 M/ Q' w9 d171
, N: v2 ^" p" O, W$ W% g. g; W. {172
173
174
& t- E; y* q0 I& b175
: [, Z. T, f! r. x0 g+ U# B  G176
177
: @+ _1 O+ r  @" B/ {178
, M. E3 i8 T3 L" |1 e$ t179
. M0 c! ], b8 e- ]7 a  e180
0 j, a# d6 ]" _# p. ~5 w181
2 {. f9 m9 ^% @182
: K% o- q7 m* M0 Y& a183
184
185
186
" f+ c' k2 x8 l187
3 k4 F7 k( F: C0 @188
/ [1 X2 x/ |9 w+ g# @& v; j189
190
191
- A3 t: |3 A" F( {+ l192
7 E/ _7 J) O# ?- H5 J7 c& r; D: Y193
194
. S* S1 V$ [3 |2 Z/ p195
196
197
  [* ~) ^2 {' c- i" e198
# S9 f) c$ t1 q2 n199
200
201
202
- S& r9 z$ B6 B& _; c/ ?) D+ V5 L203
204
& `$ Q6 L7 c' P* l( ?& w/ L. q205
206
207
208
209
  ]/ w# \* H! }; j- s% w210
# c9 K2 O; E$ g" X. f# b$ D1 Q1 S211
, x9 l# q/ A7 \212
213
; e* s, k+ a, q" C7 `214
215
216
) m& t! X9 Z& V+ V: F# ~217
218
/ Q4 Z" O/ J# z219
220
221
/ S! l) {+ E/ I: `222
3 B" ?; o' S4 C223
+ l/ n0 ?. U& K224
) y; _5 {! r) ]: V2 J225
226
227
) ]$ n/ L' N4 Q3 V; i7 f228
$ Y7 _) k0 g6 Q: w; u2 a229
230
2 D2 V. A! W# _' x231
+ k' b% [  u# w# h- o/ Y" A232
) q: {7 C. D8 f9 S2 V1 U233
234
( Z6 |' d! H/ |3 C235
/ [. M" X# j6 C. H) G+ S236
237
/ p" b- R! Q. L; ?" y& D, V238
$ S4 Y* H& b, B: S# S" V; s' F239
" x( ?$ R  |  I1 M3 O$ A240
241
242
243
6 v3 K! c, t" W4 g4 ^/ G244
% I2 P* ?3 n- K% J5 V  Z245
246
& ]/ e7 m0 j" U$ G9 `, X4 x) R247
248
249
250
+ s4 o- ^9 F3 ]251
9 E) y, E/ |% Z& x  U2 G252
+ m5 K, G+ k6 |1 a, v# U; D253
5 D& `! L0 @# T: x- r7 a$ Y% A4 C254
; C! f; c: T; d255
256
) y6 H7 |6 P, ?6 |257
8 V1 G# ~/ b$ G$ f& }258
259
260
  y9 y9 u8 ?% F" @8 ]261
262
263
264
265
. ^- R& G. T8 A: k, ]  O266
' g4 ?. Z( C: o$ e267
* [/ f- J- j! Y  r8 W* C. [268
269
7 U" f5 W2 L  ?% U270
271
272
" \! y4 n- i1 C! L273
+ Y. i- N  M9 j9 [2 k274
+ w3 j* }% @, u* u& y275
  W  S! H& \% B1 ?; N4 y# r9 p1 |, y276
3 ?) h) ?8 @4 P' ^2 D277
278
279
. ]6 Y5 T3 ]1 \  A5 o280
( e; }3 n# N) D* z  e9 {! n" I281
282
283
284
285
1 R5 T8 T) C' i% H286
287
288
289
290
7 {3 I* _9 Z, {/ T291
6 y, [6 z0 T5 y4 s; J* e292
293
294
/ {9 y/ L& `- s295
! i9 U% e  s5 n$ B0 e4 n) L296
297
* |( n* z/ N% X298
, `5 |4 ~" |/ i( E$ u2 Z4 G5 v299
300
+ R* B2 w7 h' P; m301
9 d: A! s+ K  x: P302
( \7 m3 H3 e$ T7 w0 N! H8 k303
, p5 H) z" x& M) v+ w$ ]304
305
306
307
# _& _! {6 p$ N# ~9 n% j, c308
( m5 q) `4 J2 M: L# W4 x2 H1 ~1 [309
310
" x4 t! G/ v1 J7 }5 g0 v+ i) a311
312
313
% W( A' c. k: v+ {6 d314
2 X4 X+ V$ C, }3 C315
316
6 }" f( `4 f% d3 ]2 P317
318
319
320
! X, l; S% z$ w$ K321
322
1 F8 Z- n) @! C9 N; Q9 X323
324
1 _9 b. j- j) {( X0 V; e1 V" b325
3 }7 a! s8 `5 N( Z/ z* F+ T326
327
328
4 l2 k8 f3 C. w/ t0 O329
330
: I4 B, h2 R0 M, D* N331
332
333
334
& }7 g. T+ m/ w9 y$ q0 X* q6 a335
, L4 r* V* u5 q( D# f5 _336
337
% Y! m; i7 G: q' l# U/ w338
& M8 Z" R4 k0 m. f& \339
, j+ D* B: Y$ S' ^340
1 y0 ^5 ]  U/ G  D341
! G) |4 O; `( _( L$ e! ~: X342
343
344
4 p7 B4 H; X3 T4 \1 ?345
& I3 S$ F$ `7 p2 C& r346
347
348
  Q" t% B: {* ], S. C3 v" Z! w2 B9 t$ Q349
2 C% _/ R2 Z' j8 d350
351
! l5 j7 |4 s# Y& I! }/ e352
353
$ s# e- i, L# v, k- x' h; L2 N354
355
356
$ i9 X: d4 g# b! s5 j, x4 ~8 b357
358
( T; s5 u: u+ u359
6 E- X% t7 E+ S% w( R& w360
361
362
- o' w2 K9 a, g! b8 U9 D, }363
( d# k( S5 u+ _$ N  t5 ?) u- J1 o! n364
5 N7 c' J" P* w4 k* L" W! \0 H365
366
0 r) w+ k& O2 V& D* l6 x1 @' f9 J5 C/ a367
* Z2 d6 v+ y# T. \/ l8 p  s368
( \+ [& J/ S: `& s. K5 w2 A369
370
371
5 ?* C5 ~+ W. P6 c. n6 K/ O372
2 j( s1 P; q2 [8 i+ }- p373
- q7 A; ~. O3 i7 q2 V) ]374
) N  j, F- J' b3 W* X  v375
376
: F3 P4 Y8 z3 j5 o4 \* ]; x377
; p, t8 a9 w) |4 ?; I9 L! L( x378
; {# _( y  _, }6 t7 T* N379
380
- w; H$ P3 N- T; H. K" _. p381
; j9 L3 G+ c7 m382
383
384
  n% M4 H8 p! ^8 D! c385
386
# ]* `9 G5 h3 ^2 l387
388
389
$ ?! Q3 i# x9 k' Q8 e390
391
392
393
  n; Z/ E* [' y. `) Y394
395
396
397
398
399
400
401
402
403
404
405
. ?- s5 V9 K4 ?4 a8 n406
407
$ y# i% z+ s" y7 W( c3 q408
409
2 |. @# }# @/ G& r7 M410
2 t( K* a9 d% S2 e8 y8 s) `411
412
413
414
0 ?; A% ?1 b$ W1 [/ V415
416
417
418
3 @5 r$ k. Z% g6 J4 z# c" L419
' h! g" \* B$ N, g0 I0 A420
421
' q. W# J, Q- M: Z6 D( F422
: ?* E2 a* K4 T8 _423
+ y6 P' o: K( t, p$ D1 ]! I% F424
) L" m; w' G- ?% R. `& x9 h425
426
% f/ E) r% Y* _3 R- A0 |427
  ?' ?, N2 D, D4 h* M428
7 l6 k! _9 ]& g. i2 g429
+ q& S  C/ s8 L; n/ B. E: M430
. W' t0 N0 _6 j5 O' v431
432
433
434
435
; n7 w& s+ e2 i/ p9 h436
437
9 ^8 \* _% q5 C6 T438
439
  k. j' a' G5 c4 i2 b7 c440
441
9 P) ~! U8 L) K: q/ p7 N442
% z( b( j- u% g443
+ I  d! F; x/ y- }$ C: z) D444
445
+ i- ?" E! J: [& y, X* \0 Z446
3 Z8 G0 m5 n: ^) {2 T447
448
. c; g3 Y$ I9 |3 |9 I449
450
" s1 H' D7 o4 x0 o5 s# y451
452
453
454
455
' C" B1 s* z  I! a$ ^+ b% @" S456
0 z) z2 e9 J% T4 h2 B* _457
$ `2 S- b' M: N- \458
459
460
9 H9 O$ L; _. u' L4 {: O461
462
463
* u9 n* ^5 Z) \; b464
465
+ u* ~" U7 d: T5 I/ }5 K# l& G6 {466
467
468
469

: a$ R; t, j- _5 I; f* N, E


5 N) a8 Z4 ^( X: q1 ~' c4 b6 c% R* B









+ L1 }3 U$ ]; F

7 J5 x! M* S. Y
1 O1 f) E3 c- O& B; W: M




9 G0 v, f8 C. `5 [7 n


- r6 q4 r3 u* K1 p+ P8 f
6 |: t2 T1 F3 p! L' i  T' D
# G0 N( a( E4 r0 R9 \& K3 O————————————————
版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 D- n; b, O( H7 O原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212


2 D/ o% m. _, z7 V; U
- p) h8 s, o, x. t9 o. k& E0 U