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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
目录
+ H9 v/ y0 i0 M! b人工智能第四次实验报告 1
) ]7 m. d1 `# ]$ n* ?' c$ `3 z遗传算法求TSP问题 1
/ x6 I1 R# c" w+ \% W一 、问题背景 1
1.1 遗传算法简介 1
# y$ V0 ~5 j6 C0 |# }1.2 遗传算法基本要素 2
1.3 遗传算法一般步骤 2
二 、程序说明 3
" F8 k- `( b3 n" }, W2 P. i' a2.3 选择初始群体 4
- w4 {( r9 h6 a! |' `- G2.4 适应度函数 4
2.5 遗传操作 4
8 t! L2 A4 Z1 `: V0 O6 ]( |2.6 迭代过程 4
三 、程序测试 5
3.1 求解不同规模的TSP问题的算法性能 5
7 ?  n. y/ d) ^" S6 T. P! T3.2 种群规模对算法结果的影响 5
: h( d5 `. `# n8 D3.3 交叉概率对算法结果的影响 6
3 B: m( N% P* o7 V3.4 变异概率对算法结果的影响 7
. ^# x1 b1 K, J) J5 ^3.5 交叉概率和变异概率对算法结果的影响 7
四 、算法改进 8
4.1 块逆转变异策略 8
4.2 锦标赛选择法 9
五 、实验总结 10
一 、问题背景
+ M) i. v' {0 A* y& ~1.1遗传算法简介
8 L( X. K- W4 N7 K& l; I遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
; G& s6 C( T/ e! z( z& r遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
. r$ x# i' L0 r9 n0 V1.2遗传算法基本要素
- t" j' ]4 s3 I9 l# z1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
2.设定初始群体：
/ C* M# |" ~! v$ H" U) q1.启发 / 非启发给定一组解作为初始群体
" W- x0 E0 p4 ?# B2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
. L! J+ \/ ]" }# D0 y4.设定遗传操作：
1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
$ m8 e- d1 B' N: x2 k) R2.交叉：两个个体的基因进行交叉重组来获得新个体
* |; }% v; e" L. F6 J3.变异：随机变动个体串基因座上的某些基因
' h  }2 Y! R/ G! K8 p% U* r' h5.设定控制参数：例如变异概率、交叉程度、迭代上限等。

$ t' k& E1 s! i, b) V' D7 Timport numpy as np
7 S9 e) r/ z  w2 R- C5 W- Cimport random
. Z4 c/ ?5 S+ `4 ~% Uimport matplotlib.pyplot as plt
import copy
import time
1 U2 w  K6 Y! Y4 e' y4 {' P# ^
from matplotlib.ticker import MultipleLocator
from scipy.interpolate import interpolate

1 i5 }1 H2 V7 U: ICITY_NUM = 20
8 O/ e% X% X( y  z2 ]0 gCity_Map = 100 * np.random.rand(CITY_NUM, 2)

DNA_SIZE = CITY_NUM     #编码长度
POP_SIZE = 100          #种群大小
CROSS_RATE = 0.6        #交叉率
. B" A( V3 K" u& z& @MUTA_RATE = 0.2         #变异率
Iterations = 1000       #迭代次数

" n) D2 A! \: x; o8 m$ G( D# 根据DNA的路线计算距离
7 [* h! G- u6 G$ U6 j* L9 x4 \def distance(DNA):
1 |5 N& O. }; U' z$ n    dis = 0
    temp = City_Map[DNA[0]]
, ]7 E$ i( ~7 @2 g! i    for i in DNA[1:]:
        dis = dis + ((City_Map[0]-temp[0])**2+(City_Map[1]-temp[1])**2)**0.5
6 e  v$ E; G* D6 q+ }        temp = City_Map
    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5

  F6 {* G( s6 d1 ?# 计算种群适应度，这里适应度用距离的倒数表示
0 U: l5 U+ c7 \5 A* U4 q) qdef getfitness(pop):
    temp = []
) u$ I; ^  D' c9 ^1 d    for i in range(len(pop)):
: C- ^0 B/ m  ?  z8 I# B' ^        temp.append(1/(distance(pop)))
    return temp-np.min(temp) + 0.000001

! i) @' X2 }( x6 E( G; M# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
def select(pop, fitness):
    s = fitness.sum()
9 C) e  L7 ~$ {( t! z$ O4 |6 _    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
    p = []
2 m1 S( }( D1 x/ J8 c/ T, K    for i in temp:
, o5 f. e6 L# @# }+ g6 C% S        p.append(pop)
    return p
% Q7 Y& k" \$ S' v- k1 [, \- h
( P# u" p; F- p$ H& @7 a& @( g# 4.2 选择：锦标赛选择法
def selectII(pop, fitness):
1 A. J! t3 |4 G( j    p = []
$ z% D% ?/ s# v6 m  H    for i in range(POP_SIZE):
        temp1 = np.random.randint(POP_SIZE)
        temp2 = np.random.randint(POP_SIZE)
        DNA1 = pop[temp1]
        DNA2 = pop[temp2]
        if fitness[temp1] > fitness[temp2]:
            p.append(DNA1)
        else:
            p.append(DNA2)
, J( {& K; f+ ?" V    return p

# 变异：选择两个位置互换其中的城市编号
0 |' @  H! {& y( h6 fdef mutation(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
% _, E; g' D: P: N  v        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0,DNA_SIZE)
+ E, Y5 @$ R5 h        while(mutate_point1 == mutate_point2):
            mutate_point2 = np.random.randint(0,DNA_SIZE)
4 E! q3 K1 }1 G$ \* E! S. J        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]

4 H. v: y4 M) V- C: P0 [8 \# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
def mutationII(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE:
        mutate_point1 = np.random.randint(0, DNA_SIZE)
3 [0 Z* Z2 g; T3 t        mutate_point2 = np.random.randint(0, DNA_SIZE)
! v! D; M- p8 y, s- H& }        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
6 i" o% {3 B" U! ?+ w1 \% c/ A        DNA[mutate_point1:mutate_point2].reverse()

# 4.1 变异：调用 I 和 II
- q0 y1 `! s6 O+ k; l. S7 K% odef mutationIII(DNA, MUTA_RATE):
    mutationII(DNA, MUTA_RATE)
3 a: g9 u2 {- D& A4 u    mutation(DNA, MUTA_RATE)
1 i5 w2 H$ b$ d5 s
# 交叉变异
# muta = 1时变异调用 mutation；
0 O! {, \+ v- S7 e1 \# muta = 2时变异调用 mutationII；
: F) z7 K6 P( t) X/ u5 ^5 n# muta = 3时变异调用 mutationIII
def crossmuta(pop, CROSS_RATE, muta=1):
/ q& q8 H5 X8 I6 l    new_pop = []
! b1 |8 \9 d' H3 n4 o    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
( l8 e! f, m6 |3 q' V        n = np.random.rand()
# G! [( s+ p1 ?" B! y* S7 G        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
7 O6 F6 R% R" s            temp = pop.copy()
  n  C& c% C) W$ j# j: D9 i$ _/ H9 Q            new_pop.append(temp)
7 F( e9 N" I5 [7 ?        # 小于交叉概率时发生变异
. |- a; j! I8 b" }$ v  i( u        if n < CROSS_RATE:
            # 选取种群中另一个个体进行交叉
, {; c3 R, ]9 n# Q/ h( u            list1 = pop.copy()
+ \/ a$ d3 G( F  T& B3 q! b            list2 = pop[np.random.randint(POP_SIZE)].copy()
            status = True
% b& v. ]" w% j; y* a            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
0 D! }. ?5 o# ]( r/ |# Y            while status:
                k1 = random.randint(0, len(list1) - 1)
( c- X& d' d- w; g  e                k2 = random.randint(0, len(list2) - 1)
                if k1 < k2:
5 Z5 Y; V) d' d" ^                    status = False

            k11 = k1
! ?/ ~: K( Z' k3 H) L
4 O: G- g4 C% g, U; j; [5 S% N+ J            # 两个DNA中待交叉的片段
            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]

            # 交换片段后的DNA
            list1[k1: k2] = fragment2
1 W2 h0 Z0 Q; \( j& U: I            list2[k1: k2] = fragment1

# p* f- M' I! ?2 D8 s8 V  D            # left1就是 list1除去交叉片段后剩下的DNA片段
            del list1[k1: k2]
            left1 = list1
, N3 L, _5 F2 |$ M
1 a  }% S% ?" l% }4 W( l! M            offspring1 = []
( l4 S! m2 x% `1 a) t6 E            for pos in left1:
; v7 u3 a2 [+ {  V2 _* M                # 如果 left1 中有与待插入的新片段相同的城市编号
5 ^6 f4 J+ ~; X7 t. y! }/ W                if pos in fragment2:
                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
2 s& Y0 P$ b1 G6 z0 s* k3 ~. [  _                    # 循环查找，直至这个城市编号不再待插入的片段中
                    pos = fragment1[fragment2.index(pos)]
                    while pos in fragment2:
0 @1 ?% @: f5 [+ Z- V, Z6 G9 U( r                        pos = fragment1[fragment2.index(pos)]
                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
                    offspring1.append(pos)
/ O$ S. w$ a3 r, F! o: |" l3 r. g1 f" R                    continue
  R8 e( d3 l1 R3 G                offspring1.append(pos)
            for i in range(0, len(fragment2)):
3 @( G/ i0 M, }' Y1 _                offspring1.insert(k11, fragment2)
  ], [& T2 b7 b$ x% U7 u                k11 += 1
            temp = offspring1.copy()
            # 根据 type 的值选择一种变异策略
            if muta == 1:
                mutation(temp, MUTA_RATE)
            elif muta == 2:
, D; _" K% H& O$ U, }9 F" Q' G                mutationII(temp, MUTA_RATE)
- z4 N  s! b+ x* h  B            elif muta == 3:
* Z+ ]/ \. ?7 S8 n                mutationIII(temp, MUTA_RATE)
# o8 v# L# }6 ]            # 把部分匹配交叉后形成的合法个体加入到下一代种群
            new_pop.append(temp)
) r4 s; l0 e: {8 n& A
/ F" T$ Y5 V3 D# _9 h( X    return new_pop

def print_info(pop):
9 l; _9 A) h$ h% r    fitness = getfitness(pop)
, ?2 j) _0 ~- U7 u6 @    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
    print("最优的基因型：", pop[maxfitness])
    print("最短距离：",distance(pop[maxfitness]))
    # 按最优结果顺序把地图上的点加入到best_map列表中
( u; b6 F2 v; R    best_map = []
% g( |& K2 d; L/ b+ y. X0 n  }1 P: H    for i in pop[maxfitness]:
        best_map.append(City_Map)
    best_map.append(City_Map[pop[maxfitness][0]])
* z1 Y+ r( I1 H* D/ @& k3 M9 f& `    X = np.array((best_map))[:,0]
0 P! |1 I" `$ e" D    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
, D3 R  e9 H2 t' N9 z$ E+ Q" E1 ~    plt.figure()
    plt.rcParams['font.sans-serif'] = ['SimHei']
- G4 I* P' d3 c& N# r6 A6 ^! Z    plt.scatter(X,Y)
    for dot in range(len(X)-1):
  H$ P  z" Q) i3 M        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]))
9 x" ~/ \( M- l( s4 X    plt.plot(X,Y)

5 T, i( W3 e" A& U/ ~5 h: @# 3.2 种群规模对算法结果的影响
def pop_size_test():
- o" n+ |+ H; {' K( Q    global POP_SIZE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
' W& Q4 L2 U  @" Z& Y    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
; y* s; e5 i% m: z2 u8 `1 ^" [    b_list = []
, U! v( V, O3 s# b  U    t_list = []
% u7 T  R! @* G' }    for i in i_list:
/ c: d: F, G6 \+ g0 h/ F- y5 r        print(i)
        POP_SIZE = i
" ], p, K  ?$ d* ]4 Z; J( P' J        time_cost = 0
. w9 U& O7 a- W        min_path = 0
        for j in range(ITE):
            time_start = time.time()
2 Y2 @' I/ H4 ?: a1 P            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start
, d% j5 K+ t+ A3 I* e
6 Q0 H6 N% R9 I4 [9 |+ O" V1 o        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
    show_test_result(i_list, b_list, t_list, "POP_SIZE")
" t! n) b) h1 a- M
7 Y0 ]2 Z1 u( a+ m# 3.3 交叉概率对算法结果的影响
/ s/ n4 F2 {0 Tdef cross_rate_test():
    global CROSS_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
  z& F! G& k3 [    b_list = []
+ I' q6 n+ H& S, A    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
. r8 `; D, R1 y* c, S    for i in i_list:
        print(i)
        CROSS_RATE = 0.05 * i
6 P3 v% M3 b& }" f; f, i        ii_list.append(CROSS_RATE)
. k7 s4 Y$ ~/ X, I        time_cost = 0
' o) e; S8 v% h0 L$ p# P3 `" W        min_path = 0
" ?2 Y9 f0 G9 F. {% k& ]" Z        for j in range(ITE):
  k- l0 u- b6 F4 V) ?6 ^3 w            time_start = time.time()
            ans = tsp_solve()
8 ^/ `* ?- c* s4 z: a            min_path += min(ans)
, L& p0 O% Q% s1 J/ T2 O8 o! J            time_end = time.time()
            time_cost += time_end - time_start
' a9 I) a; c# {/ E# D, }
' v8 k+ q& R- A* L% w        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
3 W, ?% m  K, x' R' B" o    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")

, s3 t/ q! X. J7 ]# 3.4 变异概率对算法结果的影响
/ c: b9 N, C' D( }' Q: |def muta_rate_test():
    global MUTA_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
  e; n9 l9 o+ g- o    i_list = range(0, 21)
    b_list = []
  P4 c2 x5 z# S- S    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
% ~& p& z1 ~9 `4 c! F$ a    for i in i_list:
        print(i)
        MUTA_RATE = 0.05 * i
        ii_list.append(MUTA_RATE)
        time_cost = 0
        min_path = 0
        for j in range(ITE):
7 y+ |1 s4 r: f" m6 N            time_start = time.time()
) R7 f7 @! w# Y1 c" H2 |            ans = tsp_solve()
            min_path += min(ans)
* m, c: [9 d1 l% n9 c            time_end = time.time()
            time_cost += time_end - time_start
; `7 i7 s9 k4 p0 y( _  [
% Q3 w8 n" B" T: Z: ]        b_list.append(min_path / ITE)
: F% @* o# Y- ?! i4 j        t_list.append(time_cost / ITE)
    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")

: L# e/ s6 W* Y( s* l+ K" H9 p# 3.5 交叉概率和变异概率对算法结果的影响
def cross_muta_test():
. E2 r" P# R: p$ Z+ t3 q% S    s = np.array([0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0])
3 Q9 n1 J) T7 w; U. Z$ ]    X, Y = np.meshgrid(s,s)
    Z = np.zeros(shape=(11, 11))
4 U4 G" N3 e: j3 m; `
    global MUTA_RATE
6 u' s, B1 G+ @, Z! }    global CROSS_RATE
    for i in range(11):
        for j in range(11):
            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
: A# j8 W, Z2 f            MUTA_RATE = Y[0,j]
- k) z4 d, B- |, M% |" |            ans = tsp_solve()
, ^1 b2 `$ x+ l* d  A0 L" l            Z[i, j] = min(ans)
+ M# u4 u+ q) j8 q+ Q& b: @
    ax = plt.axes(projection='3d')
    ax.plot_surface(X, Y, Z, rstride=1, cstride=1,cmap='rainbow', edgecolor='none')
1 c4 A3 G/ j/ w1 v- G$ I  G    ax.set_xlabel("CROSS_RATE")
9 w. A1 u, ?6 B" g8 A    ax.set_ylabel("MUTA_RATE")
+ F7 U1 G, Q5 O1 }/ ?; F    ax.set_zlabel("Shortest_Path")
/ s% h; N2 i  {% L    ax.set_title('TSP')
7 ^! ^6 x# b7 m% y    plt.show()
4 I# f$ {8 l5 E. a. D3 D" a
3 f! F6 U7 V* _/ }, q1 V5 X# 3.2-3.4 生成参数测试结果的可视化图表
; ~% p# m1 V6 T. _* ~8 mdef show_test_result(i_list, b_list, t_list, msg):
    ax1 = plt.subplot(121)
. D* j: N0 g% D: y    ax1.plot(i_list, b_list, 'b')
$ O% k# Y+ j2 w5 J    ax1.set_xlabel(msg)
  t4 G7 h# z: v    ax1.set_ylabel("Shortest Path")
& v1 z! n: Y' _0 ~# ~' `
0 \. t! u5 Q4 W9 x% A/ M    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'r')
' H9 W8 z1 Z5 V' D5 x# y2 z    ax2.set_xlabel(msg)
    ax2.set_ylabel("Cost Time")
! k+ D/ U2 \" b/ p0 Q# K    plt.show()

2 Y6 x5 g- v7 a) x- W' n# 求解TSP问题并返回最大值
  j( l8 r: k8 D/ N# muta 指定变异方式，sel 指定选择方式
def tsp_solve(muta=1, sel=1):
    pop = []
% h7 }; b- v. _  i    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
! J7 S9 A7 I# [1 O/ m    best_dis = []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=muta)
6 b3 C; _: b: i% K+ b& m        fitness = getfitness(pop)
; R* D- u8 J  j2 o        maxfitness = np.argmax(fitness)
+ G8 p$ W3 ?/ R9 l' R% ^8 L5 ]        best_dis.append(distance(pop[maxfitness]))
        if sel == 1:
            pop = select(pop, fitness)  # 选择生成新的种群
        elif sel == 2:
3 T! B7 @( H4 \4 ]            pop = selectII(pop, fitness)  # 选择生成新的种群
. ]/ [/ o0 U- d
7 a4 r1 ~- Q9 Y' D2 n    return best_dis
% ?& `1 z% T0 E; {9 {" w8 t& F# o
3 R9 x9 R9 j6 A# i$ G& F! a' h# 4.1 块逆转变异策略对比测试
  p7 }" r, ]0 q1 O+ i! mdef opt1_test():
) H( F, z. Z; o, D  p; g. P: `    ITE = 20    # 测试次数
/ [% M# @) A  O2 U    i_list = range(ITE)
    b_list = []     # 每次求出的最短路径
8 |' I0 S- l% U/ {" ]8 X    t_list = []     # 每次求解的耗时
: {9 y, I- M. ?& I! c) y/ z    b_listII = []
' T7 Z/ S8 A- x: b* X    t_listII = []
* @$ A; H& a% [, f    b_listIII = []
    t_listIII = []

- g" x% R/ H% c, {    for i in i_list:
& h* l% @; I  G3 R  u( R( s        print(i)
  [4 D+ R$ P3 L- \( N& B        # I. 原两点互换异策略
        time_start = time.time()
0 Q, z% D0 P- ?/ M3 b/ h7 f" I        b_list.append(min(tsp_solve(muta=1)))
        time_end = time.time()
, z4 S7 Y3 _- C        t_list.append(time_end - time_start)
4 V* M3 c9 q! h5 z- y) j0 e5 O0 e4 E        # II. 块逆转变异策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(muta=2)))
9 p! g5 |9 z+ i' s8 j/ q        time_endII = time.time()
, o' j+ B( E5 E9 @7 x9 K6 |' L        t_listII.append(time_endII - time_startII)
        # III. 同时使用上述两种编译策略
1 |0 V6 {( _2 [2 c        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(muta=3)))
        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)

2 Y" L0 b1 H/ }% q    # 做排序处理，方便比较
    b_list.sort()
8 i% F1 U& d2 v" n6 X" _    t_list.sort()
    b_listII.sort()
    t_listII.sort()
5 R& L+ |( h/ E8 L- i    b_listIII.sort()
7 }7 |: J) P8 s0 _- r' \    t_listIII.sort()
. k" X0 r+ ]7 |9 }
& z+ e$ o# x5 j6 g9 b$ }    ax1 = plt.subplot(121)
- \/ c, k0 q4 {3 i4 S% q    ax1.plot(i_list, b_list, 'b', label="Origin")
6 D4 I) P; Y/ Q+ t    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
) A7 V3 M% t) D" o2 `0 Z+ O' ?7 \# _    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")
  E7 ^3 h' W# F- _+ z    ax2.plot(i_list, t_listII, 'r', label="Block-reversal")
0 X' z5 a: K6 M- r! F& ]    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
& l: M" U7 W/ T2 H    ax2.set_ylabel("Cost Time")
; K8 i  F6 W/ B8 Z3 z+ |    plt.legend()
    plt.show()

# 4.2 锦标赛选择策略对比测试
def opt2_test():
    ITE = 20  # 测试次数
    i_list = range(ITE)
    b_list = []  # 每次求出的最短路径
! m& F- B* p2 I+ h) f    t_list = []  # 每次求解的耗时
    b_listII = []
    t_listII = []
    b_listIII = []
    t_listIII = []

: V) y- E: p5 U% V' k+ s. W3 d( Y    for i in i_list:
& l; I# F2 i" p, \( ~        print(i)
& w6 J6 }/ j/ @        # I. 原赌轮盘选择策略
- a& {& j' p8 [; d3 @        time_start = time.time()
        b_list.append(min(tsp_solve(sel=1)))
        time_end = time.time()
8 q1 p. j8 @& Q. _2 x) x) L. Q        t_list.append(time_end - time_start)
: s1 h2 U4 q# {8 ^% d        # II. 锦标赛选择策略
. v) t: A- _4 ?        time_startII = time.time()
& Y0 U: B4 r/ R% g/ y        b_listII.append(min(tsp_solve(sel=2)))
! [$ t1 B5 g( f5 L        time_endII = time.time()
7 a2 M5 a1 d/ w0 b' o        t_listII.append(time_endII - time_startII)
+ M2 D4 b. U9 c: a) X" R" c: n% S$ h& `        # 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)
' ?+ c+ ?# E( v( h# A; H) t7 X
    # 做排序处理，方便比较
: \& J6 T3 ~2 _% T1 j    b_list.sort()
    t_list.sort()
- U8 G8 X4 R# C: Y$ C5 p3 F  l    b_listII.sort()
, q: H) j9 x9 o" Y& y2 J% R    t_listII.sort()
' T6 P( ?* A# n+ T    b_listIII.sort()
( T8 x' b' q* v; G; j0 l  k; j    t_listIII.sort()

1 g+ e1 }4 ?5 q    ax1 = plt.subplot(121)
/ q& V; N' c2 @+ F/ `1 u    ax1.plot(i_list, b_list, 'b', label="Origin")
. M2 g. C* \- g% }' E+ v    ax1.plot(i_list, b_listII, 'r', label="Tournament")
7 t" Y# g+ P. t; Y. n1 J9 y  d    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax1.set_ylabel("Shortest Path")
8 q3 Q3 T- e* x4 M/ R( [1 u    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'b', label="Origin")
    ax2.plot(i_list, t_listII, 'r', label="Tournament")
; {% F- Q, I7 }& W% x' Q& G5 s    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax2.set_ylabel("Cost Time")
    plt.legend()
    plt.show()
. n3 h- L  P* m( Y8 d# {
, b. k- A) B0 c! j  n+ r6 D. d# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
def ori_main():
. K! E1 J( z+ X, X  @& i! M) b4 X    time_start = time.time()
    pop = [] # 生成初代种群pop
, y5 T+ u/ F6 J  e6 U5 L" Z& t2 F    li = list(range(DNA_SIZE))
& u+ v1 I+ N& X5 [6 Y; o    for i in range(POP_SIZE):
3 J( I0 R) s5 m5 E- j        random.shuffle(li)
; x1 x2 C& N$ Q8 _( U6 H8 L        l = li.copy()
9 D0 Z% K" z) S& t        pop.append(l)
3 b$ A2 k' r' u) m    best_dis= []
' T0 g- @( _0 I2 {( w    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
. {2 E6 [# @2 B* Y4 C    for i in range(Iterations):  # 迭代N代
$ t6 V6 O2 R( D        pop = crossmuta(pop, CROSS_RATE)
        fitness = getfitness(pop)
! D# K4 t8 B9 a. v        maxfitness = np.argmax(fitness)
& U4 I- g6 E( M& G8 X) N* v, b% o' k/ I        best_dis.append(distance(pop[maxfitness]))
" P1 k6 b) K8 f1 p' J5 ~  I8 K; y        pop = select(pop, fitness)  # 选择生成新的种群

! v# {% M" |* t/ C, d$ _    time_end = time.time()
7 a6 q9 ]+ Y, x, y  ^# V' G    print_info(pop)
5 t/ d6 E4 S! Z7 m    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
    plt.plot(range(Iterations),best_dis)
4 c* L, Z2 }( m3 v+ M2 u1 [: O
# 4.1 块逆转变异策略运行效果展示
+ S* J; {/ _; Gdef opt1_main():
; ]# W' _+ w8 O0 C0 W9 O    time_start = time.time()
  M: b) V0 y, a- q    pop = []    # 生成初代种群pop
$ q/ g, X+ o# d% `+ [( ^    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
& v  h5 O, N' h! @7 G" m& o' [: r, d    best_dis= []
! g+ P4 C$ s1 \9 h% T- ?    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=3)
        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
% g' _( f4 g* B" ~$ j' F        best_dis.append(distance(pop[maxfitness]))
# f, L+ j/ f" g3 y        pop = select(pop, fitness)  # 选择生成新的种群

7 b/ Y8 F$ H2 p    time_end = time.time()
! i' y" F5 W1 t- c' X8 k) ]; u    print_info(pop)
7 t! U& O0 A! [$ y/ S    print('逐代的最小距离：',best_dis)
8 p7 @3 G1 X3 `2 k! b    print('Totally cost is', time_end - time_start, "s")
6 {# F* g4 ~# i6 K+ _/ p- n, W    plt.figure()
' X# j8 e5 B2 k8 N) C8 ^$ {    plt.plot(range(Iterations),best_dis)

4 ]+ [7 h% t3 x  v' `: `if __name__ == "__main__":

    ori_main()    # 原程序的主函数
2 |2 g7 i) v3 }9 T8 R* r3 _    opt1_main()   # 块逆转变异策略运行效果展示
    plt.show()
) q0 g: T* p$ _# W    plt.close()
' ~, F8 N; }# d% z% i6 W+ b! K
    # opt1_test()   # 块逆转变异策略对比测试
5 L" z: q" y4 h- u* d    # opt2_test()   # 锦标赛选择策略对比测试
! A# g: y% {7 C0 K& |3 ?0 o
    # pop_size_test()       # POP_SIZE 种群规模参数测试
, a, @' t* J- L* P% p    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
    # muta_rate_test()      # MUTA_RATE 变异率参数测试
    # cross_muta_test()     # 交叉率和变异率双参数测试


" P7 R) ~; o$ m) T& }$ D1
2
3
4 z7 r$ C  u3 @! N4
5
6
7
8
, W  ~  @5 p; k$ D  Z% `5 Z9
10
; k( _: d1 p1 s0 f& b1 [; L11
! d; C& V* I$ {8 j8 S, N12
7 A; a: {5 K$ o1 _- P7 g13
14
6 N8 ?, l9 w% p+ B4 I1 p15
) O/ B/ C4 `% ?" x: d" T8 k' r16
3 @2 E' s3 C4 a1 G+ r' B3 g& w17
18
19
4 g& t% o0 x) o! j6 A- T4 B9 N% h20
21
22
23
24
6 Q7 ~5 x3 E! c( L; I; A7 v25
. z0 \  E1 Z; k  R* h0 P$ Z0 Z26
27
28
: c) G0 |" n5 L# v2 t& ?+ `29
* n2 x  B2 }" ]$ A  {0 x9 L30
31
. B3 t2 |6 @7 O' t32
/ ^- u$ _/ R  ^33
34
1 n$ k$ _5 j7 c. S3 b35
+ ~0 k4 W0 A' v: |+ S- [36
, F, {& w0 G% g$ @7 y9 \37
1 r: ^# h% b3 r' e38
& r) F" j' m1 c4 |5 x6 b' @39
+ a( }% n" W0 U" h40
% ]" Q* w( ^: n2 k8 B41
6 O6 f6 l# ?9 B6 A+ h6 Y* |" q1 j42
43
44
) k4 @2 f0 e. _- s, a45
. M  t) |+ h* n, v' }/ }. H( E46
6 n$ O4 G9 o9 h' D47
48
49
50
7 \/ D3 ~' R# {- u) m51
0 ]) q# z/ l- S2 [52
- Z3 I( k+ N% o' |$ M53
54
- @; M& Q, g$ N6 M55
56
57
58
59
60
( A" h( ?# b! n% U  f0 i  J61
/ F4 T. T& g  E2 S8 n! l1 e62
. Y' Q1 l9 f( e9 M63
64
5 S  Q/ z  N. T2 c65
66
67
68
69
: |! c  p: L7 X) y+ S9 S70
8 L& F  A3 `8 {9 b- Q71
72
7 V! A" l( x" d3 `73
74
$ D2 N& Q$ x+ `! M+ @75
76
# \; A8 q. F4 D77
8 [: Q3 H! S6 i( @: f" k- e  G. K78
79
3 x: P  j5 F* D7 r80
/ y: Z; C8 q! T7 l81
82
0 y% x' a3 _6 `0 Y83
* R9 E# o6 m' m  g  O5 z84
85
3 M' `5 g3 P8 n& G86
' \3 `& ~" p9 l& I87
8 \, x5 b! v9 e& t7 [8 [+ `88
# {( Z+ B# w% I7 O' O7 ?- G* F89
90
, [/ G6 n7 c6 ]91
92
" s# K, j/ M- h3 b93
+ P: e" E* z' x3 M% V94
95
96
" o1 a0 z4 k2 ~; ~97
8 f4 f8 _- l- t* L: E0 G; k0 _98
. z& Y, {# y$ f, s  D+ d3 s99
100
101
102
4 P2 P4 C% Z) }1 e2 U# Z# h2 c103
0 n: \: T. w2 ]! p104
& z7 G5 B2 i8 e3 c, e! {" C105
* `7 a2 E1 L1 p( i: k6 q106
107
108
0 S1 p7 o; b3 A2 i4 s/ C9 @( q109
110
111
112
& Z7 n2 S' K- d6 ~" J113
' X/ u& c; M; X0 n, A1 n114
115
116
117
  t, C+ U# l+ K( t118
. K2 D$ f" C1 N* u: f; S6 z119
. ?7 c, L0 I7 P9 Z9 X# Y120
121
122
  ]0 B+ ^# O5 r, G; k. G( {+ j  Z123
124
1 r0 G3 T& Y2 m+ o. V/ I8 H9 n- d125
3 r+ J: p/ \9 ^6 T2 W8 f126
127
128
129
& {9 ~5 h5 X7 n; K% {130
7 l, Y3 W! D5 D+ ^131
132
+ S( r# }+ S* }0 Z; ~133
# @. n9 m+ j# E134
4 ]  O3 z0 P3 q& T135
136
. v# V& B5 a- y+ S( F) u137
138
139
& {' c4 n  a/ v) t  d) D140
9 m/ v4 D% i6 [- u- e! y# D141
142
143
144
145
4 Q) M$ u$ m* y( E, N( l146
147
148
9 O# y2 x3 W- C149
150
5 E, I0 x. ^2 _' M3 h, V' n151
, B, f! N0 \' d9 H0 K152
1 n: ^1 N2 C. s5 A) J153
( j9 S- _8 I3 s' u6 \0 j0 ]# U" k154
- r0 T5 N3 A/ j8 o155
, M% D$ H1 t  I2 S156
6 E* J1 W2 k1 i6 M157
158
159
160
' w: w5 g  L& }8 Z161
162
163
164
165
' u/ }1 G/ {2 y& Q$ i166
167
. |4 T# {; x. S( Q) H* s- O168
169
+ ^) X; a8 E7 y1 d- t( B/ {4 c170
. o2 }8 P% s- P' Z2 P2 s171
: ~9 B  u0 L7 P3 _172
* f( o! y: k9 V0 T' g: C5 t% F8 q! S173
5 x' u5 V& M/ b174
175
176
177
178
179
180
" }9 Q( n! E) v. l9 a* B181
. v7 m  ~* Z. e. V$ s0 r; A182
. z& f/ ]1 m6 P9 {2 @/ g0 }183
' i7 i+ o+ L  J9 [/ y* S184
) |! v# a7 |. }2 ]185
" f( C) J3 m% e( x% `; s9 E2 y  u. |186
) J* z0 z! l/ [- N& s187
7 b- ]. W! Z5 j6 n. h' Y  D/ k188
189
7 j2 d/ u* Q4 O0 |; B3 `) b  H190
, @. x; |, h. ~( Z8 _191
192
193
194
4 ]! ^7 _( e8 I/ k& t195
  W9 A" T2 y$ _& g' L196
+ i. e  T( [- z. ~/ H4 x197
7 [2 r. h/ F, q2 O198
199
, ?" l9 i# d$ g! C4 T0 t2 u200
0 x. n# E! @! Q0 x201
1 {. @4 B) r+ l202
" w( U# E# E) }203
204
205
. n2 {" @0 A1 j3 b1 Q5 P206
207
208
  i6 m4 T4 y: R4 d. H1 N209
210
. k* T# j4 a  g211
212
- N/ a3 ?& A9 F/ S  \213
- c' G( t/ z# i  R214
  z. {  c) p5 L' b" B215
6 j/ Y( L9 a' F& L5 b216
217
- w6 M: x& e2 [+ P3 E. X218
219
2 W& m3 E0 n* Z. y4 e0 ]220
* W; F( e2 |. F; w& Z221
. |9 l4 c% W( F6 n; N$ X" i) Z$ I222
- d4 ~* a9 k1 F) I8 B223
  c: S! `, u- q/ [% w% s! E224
225
226
227
228
7 A/ M5 I2 z' F& v229
230
231
# b; J* n) q/ R  x" c7 z9 R" O6 x232
# {# J- V" j0 I2 m  [( M  l233
234
235
236
237
238
239
240
241
  S; n' U6 i' W. O3 f/ |242
" h5 G$ S) h, K6 d! ~0 _243
244
245
246
0 ~  r1 Y2 M" J. U# O) ]" f. g1 `247
248
249
250
251
252
253
254
; U- }$ h' @- L2 L" u* m$ m  Z0 G255
256
257
, d) \% _+ e" S258
+ r% ~' m' M+ }) ?) _259
260
" |  i; G4 [: m) N% s261
% ]+ q( {& K  L3 P3 q262
263
264
265
266
6 i, j6 G/ P9 a, B' x( A267
1 N, ?8 t& P7 f+ r  `: T* W268
6 L3 o' T' u8 @4 B. ~9 e) C269
270
271
272
: ]/ @* i8 {. ^8 [$ D' U273
# [" G2 N4 Q; w5 ^274
( o1 r, i, p) c; ^  W! s# b275
276
4 ^# c' }, }) C277
3 X- O' I, Y% j3 u# `# ]% d! m278
& v! K) ]; Q; K5 o279
! Z; ]6 N# x& ?280
0 P- m3 X" E2 m- ~281
282
! a& c+ j6 \' j283
284
285
286
) d; r4 i& F5 g0 w4 E287
288
289
290
291
: G: @8 w$ p. p: B, G292
293
4 u( g6 \9 L( b5 S1 T294
: {5 H) A& }; ^1 ?295
% E/ U) }8 s8 J# m9 n+ ?9 j8 G296
9 S3 ^) H. B: B+ G& m297
298
. {) k$ Q  b2 O! b" o299
300
: ~4 r2 Z3 `% ^+ y301
/ A) f/ p: Y8 _6 l* T7 X) F302
% @' o% x7 p0 d9 K2 A3 ?303
304
1 l  s" Q, P" _* ~3 D$ U305
/ i9 J1 W- L8 ]306
307
308
309
3 ^8 K, |8 Y$ o: l, T5 u310
3 ]( H9 J( ]( w0 N* |( ~311
' M) l0 W. c( v( h# u312
313
314
: l; H; v6 h* P( [- C315
; q  W/ p! }& k, r316
9 t( V6 j* B0 T7 Z7 D  l" _317
318
319
* B* u# x0 Y: \3 x# i. e320
321
322
323
324
' T4 E1 S# @; X9 _2 B' \. j& k1 Q) f325
( k3 E7 c* }2 ^+ a& g3 L  z326
327
9 r, j: I& v- ~/ r- M) Z328
$ G# ?+ v- r# _. G8 |& ^& r329
330
331
1 \$ s* w# c% X+ }332
; ]9 F  h6 Y9 E0 ^4 }+ G( c333
334
; _, G5 Z; ]7 J' t) T335
; |1 ?$ d# Z- w9 ~$ }- }336
337
338
5 M$ K5 D" o) U: q+ R3 U) U339
, i4 a. Q8 c4 M4 @- Y2 C340
341
  A+ {9 H9 H1 i. m1 ~# a7 i342
6 s3 M4 E! }0 k. Q343
344
345
0 b4 v$ Z3 o, i346
! {9 }2 `) E' ^% b5 P% S# o" i347
3 _2 ?  U" Q6 D) r348
  u9 D' u9 u6 e, ]' N9 \  P349
350
351
; E* ~3 n3 v: G6 S" d- D) s352
9 }2 Z9 s; n  T353
! K8 p0 c# ^6 l/ x354
355
3 o2 n0 v2 G5 j; e: ?1 @6 g356
357
358
9 }- P. w/ y3 u2 A$ q- l8 k359
360
. A& V' Z2 w8 S. ^% f361
362
" d7 q" w* q2 |363
364
365
; v: y1 ]+ ?% k9 `" \: v, y366
; P3 m  O0 [8 I- B1 `367
4 a5 o7 K8 h1 D# ^) T6 o368
7 f' E0 m, P4 U- u; @! l: Q/ d369
3 a+ Y- e; Z2 b( r/ p8 z; K370
' g- w+ K$ q8 z, d0 u371
372
- U0 C; w; D  ?& p( l" W/ n% i6 p$ ^373
; `/ M1 y% E, P+ o374
375
4 m  l3 P: {6 i0 p( ?& R376
) E& C/ w- ]* K% l377
378
379
380
381
( }& ^+ |8 [6 o" v: o" h382
  K/ |2 r6 c9 G8 p3 F. V+ k, v' Q( `383
384
! }: Q" t. e9 F( m* P385
5 f# l/ E" b; S0 n386
387
388
5 Q! h4 m8 j1 P& B! ^3 x+ X389
390
391
392
  e  Q$ s5 {9 x! ~: d* P393
394
395
: R: Y& ^0 x3 L9 i# m396
397
398
, s, f" j- V& _6 v6 z- T, n399
2 C, V5 |1 x! ]; g% H$ {  d400
401
* _3 F5 D$ n: L$ W402
403
404
5 u- {( b# [7 U9 G) v405
9 q( C1 n6 Q  `* K  |. k406
9 L2 @+ R7 |$ m& N; F407
7 z. n: P! M- s/ @408
2 A' _8 v9 {5 A% q6 ~. |409
# A$ [$ A6 `: S2 A; C- h7 z1 E: ?6 ~410
3 n, S. O& g1 I6 o2 e411
412
% V% g- U7 @& ~! f) X2 n1 ^" I  B: j413
5 u) F- E" O6 Z0 d414
415
5 W+ g8 G. i- S416
417
418
* X( H0 p9 N% w% O  f' T419
420
421
$ o9 Q& k) o+ o3 d% X0 J422
) w& H. @) n- x7 [) \423
" v$ R3 Z, q% S) V424
  |3 V* v& M, w4 \; ~; `425
426
427
428
429
430
431
432
9 i/ L3 }" F! E  }3 U" ^433
, L. t* U3 E2 S: O434
435
) T$ T8 h+ D# c6 x# s436
$ b; K& Z! z( e- ^; N  g. o" J437
438
439
440
441
442
443
444
445
+ l5 o7 z  p; z: E446
& c7 j2 Q2 H9 V+ ]& N447
& a' ?) j+ h3 v1 ]! O448
449
450
+ }+ \' K$ u4 o3 ]451
  ]  P& R- A3 A- l452
: h. w, c5 e; S! }; y* q453
; Z% ~2 Z0 B! |2 D4 p( R9 u454
455
% T, p7 s3 y/ e& }0 M6 l! ~/ S456
457
3 e  _3 {1 z# M0 R458
$ @" P0 N0 v+ i' s; p- m459
2 Y1 l8 \% \5 T1 ]' W460
461
+ ?& ~9 R5 u( r7 u3 ]* |) K462
. C  P6 U9 p9 d" ?. W463
464
1 [9 V0 g- @# C) F' h465
466
+ I! z( L4 U6 J6 y' o467
4 ?# n! {( }/ G+ ^. N1 G; U468
469
& @3 G' G1 O) u0 a8 n
3 V/ P# U3 \0 u& T& ^+ h# N


: I' ~1 w# Y% ?! U- G% W& |

( a" ^! T) ?' q. q: x" u

0 v9 P+ [5 s6 ?- |; V; C% I
9 t2 o2 o' s0 J



& N# f' |% @# w" `; C7 o

, T  v8 D  Q$ I  y' t

3 @3 |5 T6 k! M8 Q+ ~

$ ]# Q5 I( ~7 s' w( E% s9 ^
( [" b6 f' v) o, L
# a& S' V% ?" L* Q  ?


4 X1 K( r% C+ Z" O


————————————————
版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212
) S; f  z" S- }" ]7 i; x5 f


9 Y3 E8 }: {& H4 j/ k! j* O4 {5 t