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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
目录
人工智能第四次实验报告 1
遗传算法求TSP问题 1
一 、问题背景 1
" X/ c3 V8 z7 D/ e9 `1.1 遗传算法简介 1
1.2 遗传算法基本要素 2
1.3 遗传算法一般步骤 2
+ h, l9 G# d' y' k& c% N1 l二 、程序说明 3
2.3 选择初始群体 4
2.4 适应度函数 4
& F: p: w5 p2 T1 b% o6 h2.5 遗传操作 4
! s6 N2 ~3 n% k- k% t( K2.6 迭代过程 4
三 、程序测试 5
3.1 求解不同规模的TSP问题的算法性能 5
3.2 种群规模对算法结果的影响 5
3.3 交叉概率对算法结果的影响 6
- i" m- b) t+ c/ x3.4 变异概率对算法结果的影响 7
( V3 E) L# T0 b) H0 l3.5 交叉概率和变异概率对算法结果的影响 7
7 e, m7 w- g' I- n四 、算法改进 8
4.1 块逆转变异策略 8
4.2 锦标赛选择法 9
五 、实验总结 10
' R) x2 F+ v- y/ l1 q7 H* F一 、问题背景
8 k0 N' b/ s9 c* l7 |8 w/ U& g6 u1.1遗传算法简介
遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
2 ]! J8 u3 ?% K0 m' C! ?遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
! K, H" X0 g( |$ s' s1.2遗传算法基本要素
1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
3 e# j8 c4 m9 J6 y2.设定初始群体：
" h; j% U5 x) t0 k4 `% b1 u& v1.启发 / 非启发给定一组解作为初始群体
8 k" T) V' p9 R0 p6 K, F2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
) B/ i# ?: e: X6 B9 K9 i4.设定遗传操作：
1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
2.交叉：两个个体的基因进行交叉重组来获得新个体
0 f0 \5 I; Y4 @2 `6 B  O) j* ^3.变异：随机变动个体串基因座上的某些基因
5.设定控制参数：例如变异概率、交叉程度、迭代上限等。

import numpy as np
import random
import matplotlib.pyplot as plt
' Q: E$ e" _& g1 nimport copy
import time

8 e6 x) K' c0 T$ }+ Wfrom matplotlib.ticker import MultipleLocator
) `9 c9 r5 p, ?3 s& Ufrom scipy.interpolate import interpolate
( m* Y& J) Q# M5 h
CITY_NUM = 20
City_Map = 100 * np.random.rand(CITY_NUM, 2)

DNA_SIZE = CITY_NUM     #编码长度
POP_SIZE = 100          #种群大小
CROSS_RATE = 0.6        #交叉率
' m1 h' X1 X9 uMUTA_RATE = 0.2         #变异率
4 p- b: {  U+ B; q) F: QIterations = 1000       #迭代次数

# 根据DNA的路线计算距离
- S0 y9 K! {7 {; adef distance(DNA):
" j( ]* Z2 o: w) U$ ?    dis = 0
    temp = City_Map[DNA[0]]
    for i in DNA[1:]:
        dis = dis + ((City_Map[0]-temp[0])**2+(City_Map[1]-temp[1])**2)**0.5
  f3 y( V4 f2 I% C% [        temp = City_Map
    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5

$ O4 Q% h7 b* H, v! z6 p; j7 D# 计算种群适应度，这里适应度用距离的倒数表示
6 T' p7 c! |. M8 I0 Hdef getfitness(pop):
    temp = []
- Q$ C- V5 t6 d7 x    for i in range(len(pop)):
        temp.append(1/(distance(pop)))
9 j' s) b3 F2 p- E    return temp-np.min(temp) + 0.000001

# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
def select(pop, fitness):
2 ~, X# k6 y) @2 w1 z    s = fitness.sum()
$ v5 o" _( B' w+ \: D    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
- y  Z8 o, h8 `! r! w% e8 n; Q    p = []
    for i in temp:
        p.append(pop)
    return p

# 4.2 选择：锦标赛选择法
1 c- [5 Q* ]& z# |5 Odef selectII(pop, fitness):
    p = []
: t. `! h% ~; x! I* S1 [    for i in range(POP_SIZE):
        temp1 = np.random.randint(POP_SIZE)
( B5 p( ?- {& O# t        temp2 = np.random.randint(POP_SIZE)
6 P$ X, J, B+ C  e! j/ o+ C  F, c, N        DNA1 = pop[temp1]
6 M) }' f' t1 O% |7 l: V7 z/ O        DNA2 = pop[temp2]
; ~% t& M: ^& d; y' B8 w5 y  \        if fitness[temp1] > fitness[temp2]:
            p.append(DNA1)
        else:
  v: C2 u& r" b" H5 p5 {+ x            p.append(DNA2)
    return p

, g4 _0 o# p% i: k6 g$ m( z# 变异：选择两个位置互换其中的城市编号
  T2 ~; A/ @+ c: {def mutation(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
9 E- b! [" O- t) Q& Q. o        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
4 [$ J: z6 x% b7 e6 H! s& z# Z        mutate_point1 = np.random.randint(0, DNA_SIZE)
1 B1 Z. {  V- e8 x4 t# J9 C1 k3 V        mutate_point2 = np.random.randint(0,DNA_SIZE)
        while(mutate_point1 == mutate_point2):
; w7 R7 \2 u6 {  I; k: Q            mutate_point2 = np.random.randint(0,DNA_SIZE)
        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]

# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
2 L( s! l$ B2 [* [def mutationII(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE:
, n) k7 E! H0 I& @' x) R        mutate_point1 = np.random.randint(0, DNA_SIZE)
0 r1 n  X5 b/ n4 c) r        mutate_point2 = np.random.randint(0, DNA_SIZE)
        while (mutate_point1 == mutate_point2):
            mutate_point2 = np.random.randint(0, DNA_SIZE)
, X" Q% ?0 T5 N7 N        if(mutate_point1 > mutate_point2):
# ~" R5 ~. M9 T$ q2 [, c- m            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
7 ?1 J% R& e, v0 R# V4 A        DNA[mutate_point1:mutate_point2].reverse()

# 4.1 变异：调用 I 和 II
def mutationIII(DNA, MUTA_RATE):
    mutationII(DNA, MUTA_RATE)
- b; P% c1 x& Z5 B( T* q- y    mutation(DNA, MUTA_RATE)

# 交叉变异
# muta = 1时变异调用 mutation；
# muta = 2时变异调用 mutationII；
: V: }- y$ _6 b0 S/ _& J- d2 |# muta = 3时变异调用 mutationIII
def crossmuta(pop, CROSS_RATE, muta=1):
    new_pop = []
! ]2 Z7 l' A4 ^6 f* k  z& F( b; G5 u    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
        n = np.random.rand()
        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
( x. ]0 {2 T8 T5 Q( n, E6 d            temp = pop.copy()
. v& f: ]& |0 |  m) v% K& c            new_pop.append(temp)
        # 小于交叉概率时发生变异
        if n < CROSS_RATE:
5 }1 s) C5 u, b5 m            # 选取种群中另一个个体进行交叉
            list1 = pop.copy()
            list2 = pop[np.random.randint(POP_SIZE)].copy()
            status = True
            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
4 J, A6 ~+ ?  [$ v; k% f            while status:
7 B2 v6 O; i8 T) p0 M                k1 = random.randint(0, len(list1) - 1)
! A0 P% W1 [. m* ^4 |                k2 = random.randint(0, len(list2) - 1)
  _5 R  O1 ?# O+ X1 x# R                if k1 < k2:
: @! o6 g; I0 t. ]                    status = False

            k11 = k1
( V- G2 s0 A1 q' v
8 U) j& w- P7 @            # 两个DNA中待交叉的片段
3 ?8 [& K" g9 S- s" e            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]
5 _- N2 p% y' K+ `
            # 交换片段后的DNA
            list1[k1: k2] = fragment2
+ w! m. S3 o9 F8 s& ~            list2[k1: k2] = fragment1
" H* n; r  f6 q! Z0 n" _9 c/ P$ }; e
0 j3 E( j$ l. l+ \; X            # left1就是 list1除去交叉片段后剩下的DNA片段
- T' j0 n' i! X5 i2 `            del list1[k1: k2]
; e$ T7 U8 ^, f4 Y2 B            left1 = list1

            offspring1 = []
1 W! o2 B3 c8 F& B$ w            for pos in left1:
                # 如果 left1 中有与待插入的新片段相同的城市编号
9 H3 v1 p( }" J6 h                if pos in fragment2:
* g2 L0 |2 I; b3 }                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
                    # 循环查找，直至这个城市编号不再待插入的片段中
# [' x" A. e3 `0 }& T* k; Y                    pos = fragment1[fragment2.index(pos)]
                    while pos in fragment2:
                        pos = fragment1[fragment2.index(pos)]
: L- [; \$ k9 z: m1 ^- a# k% T, l                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
! x1 r1 U4 y  J" f9 F                    offspring1.append(pos)
' f8 ]) K* y+ H" ?                    continue
5 A7 V" K% T# ?( X" a                offspring1.append(pos)
            for i in range(0, len(fragment2)):
                offspring1.insert(k11, fragment2)
                k11 += 1
            temp = offspring1.copy()
- n. \  p" D; E5 b9 X0 s            # 根据 type 的值选择一种变异策略
8 q4 z6 v9 i) T) Q' E9 b, {            if muta == 1:
                mutation(temp, MUTA_RATE)
            elif muta == 2:
                mutationII(temp, MUTA_RATE)
5 d7 u7 h6 k' y- ]  {            elif muta == 3:
                mutationIII(temp, MUTA_RATE)
! V. a$ Q: ]9 b0 N2 V            # 把部分匹配交叉后形成的合法个体加入到下一代种群
1 P" {2 K7 e/ m5 V: ?  ~            new_pop.append(temp)
+ X+ |, _! b  A% m
* o0 w* v/ {) r/ I) r. P. R  m' Q    return new_pop
  ?% {; [( M0 C5 e8 g( m8 T- C
def print_info(pop):
0 |$ F8 S0 O+ x% d! K/ d6 O    fitness = getfitness(pop)
' F% S, N- o8 A9 n    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
    print("最优的基因型：", pop[maxfitness])
    print("最短距离：",distance(pop[maxfitness]))
- S) K* q3 ^& t$ F" Q8 j    # 按最优结果顺序把地图上的点加入到best_map列表中
2 o$ n# y! r$ ~5 {% n+ \    best_map = []
& A- g# v' X. j' R    for i in pop[maxfitness]:
% Q8 u0 k& q! ]: q        best_map.append(City_Map)
; M6 x+ g1 s' K% b$ T) P    best_map.append(City_Map[pop[maxfitness][0]])
1 o2 I; R# ?5 h4 E3 E    X = np.array((best_map))[:,0]
    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
+ P# x7 a. s6 G1 J- B9 w    plt.figure()
$ B' e' e! F( H  D    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.scatter(X,Y)
+ \6 z  Q1 p& ]7 \% I: p; W    for dot in range(len(X)-1):
) W( B/ |5 S' \/ y# l8 f3 V        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
" t8 _( O) U, s    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
1 j5 b- }, x$ f- j* ^1 N8 a6 F: T# ~    plt.plot(X,Y)

# 3.2 种群规模对算法结果的影响
/ j  v8 j2 f; ^  g0 e) M/ r  w" f8 m" E; Xdef pop_size_test():
4 \/ ~0 J$ b+ \: h* C    global POP_SIZE
  _& [1 q7 r8 w& U! v    ITE = 3 # 每个值测试多次求平均数以降低随机误差
* C( ]7 |$ A( X6 b7 M6 b    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
: e; ^- M) \3 \! c    b_list = []
1 M8 y& B8 z  }! E    t_list = []
    for i in i_list:
8 {% n8 E5 ^5 k- x% i5 j        print(i)
        POP_SIZE = i
        time_cost = 0
/ ^7 I, F: W6 K& W* l& X        min_path = 0
; t# |% p- C! j# g8 ^& i+ b7 H        for j in range(ITE):
6 t' V' e7 r" d, m4 f9 r            time_start = time.time()
% n- h5 }* F9 a0 F, z/ V            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start
- m' n4 r: d  C! ?
1 q/ U7 Z1 B4 a7 x0 V        b_list.append(min_path / ITE)
% O5 C; I' {2 c, L& L        t_list.append(time_cost / ITE)
    show_test_result(i_list, b_list, t_list, "POP_SIZE")

# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
    global CROSS_RATE
+ W, w  @* g: d" S2 J$ B    ITE = 3 # 每个值测试多次求平均数以降低随机误差
! D; `7 l' e8 s2 Q0 f: h, L4 S0 M, n    i_list = range(0, 21)
' L& ?) `+ z2 y$ \) L# z6 q    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
        CROSS_RATE = 0.05 * i
( k2 Z1 l% q8 {" d* K        ii_list.append(CROSS_RATE)
0 q+ {& T. q) @3 g9 D* T+ S        time_cost = 0
        min_path = 0
" ~& Z: s+ O5 x1 C# {# Q3 S        for j in range(ITE):
" n: q5 S+ s% q/ T4 a            time_start = time.time()
            ans = tsp_solve()
# N( _: S- Z3 a- l3 ^            min_path += min(ans)
: u3 Q& i: t% B8 I            time_end = time.time()
            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
6 \0 t) @; i% n, s1 z7 Q        t_list.append(time_cost / ITE)
    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")

# 3.4 变异概率对算法结果的影响
def muta_rate_test():
    global MUTA_RATE
+ Y6 X. ~0 O; {/ Z/ A    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
    b_list = []
    t_list = []
: @0 |% |- K9 [( j& a    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
& O  o7 B4 v6 h/ S& \2 k    for i in i_list:
        print(i)
        MUTA_RATE = 0.05 * i
3 i1 Q2 u, Z1 ?& V) _7 h5 Q        ii_list.append(MUTA_RATE)
        time_cost = 0
        min_path = 0
. V* P3 t( V4 A5 [4 @. {, r        for j in range(ITE):
            time_start = time.time()
6 I9 A1 Q1 T# X5 h            ans = tsp_solve()
: q; i" _1 P. v/ v2 f8 N            min_path += min(ans)
* g1 k0 m: f, B1 C) v5 z            time_end = time.time()
- }' S9 y1 p7 Z; ^4 e            time_cost += time_end - time_start
! {) ]: r$ |" L: e. Q5 b$ O( G; N6 a2 |
        b_list.append(min_path / ITE)
: f& A; ?( ?  i6 |        t_list.append(time_cost / ITE)
    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")
! J# Q( p2 M  {3 q
# 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])
0 Q7 a; s' M! A% n% G  S6 K# A9 i    X, Y = np.meshgrid(s,s)
    Z = np.zeros(shape=(11, 11))

    global MUTA_RATE
    global CROSS_RATE
8 T5 g! W/ B; ~  @7 M& r3 E    for i in range(11):
        for j in range(11):
            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
            MUTA_RATE = Y[0,j]
            ans = tsp_solve()
5 V- f% t6 S5 B5 @            Z[i, j] = min(ans)
8 A8 b" v$ h3 O6 s
( p0 u; ?* F: R+ M$ D- f    ax = plt.axes(projection='3d')
    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')
    plt.show()

, H, h9 o' f, \" |9 M" R2 f2 y5 @# 3.2-3.4 生成参数测试结果的可视化图表
def show_test_result(i_list, b_list, t_list, msg):
, _( h. o2 k$ P: S# A& _2 U    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b')
    ax1.set_xlabel(msg)
    ax1.set_ylabel("Shortest Path")

. W6 T( j. A$ g" K! f$ K- ~3 W5 e    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'r')
    ax2.set_xlabel(msg)
    ax2.set_ylabel("Cost Time")
* [! A' V2 l' F2 A/ d    plt.show()
2 R8 o% J3 s+ q; _; l0 N
# 求解TSP问题并返回最大值
! {% O6 }! r0 S9 O# muta 指定变异方式，sel 指定选择方式
' }1 l+ m& D3 D) Gdef tsp_solve(muta=1, sel=1):
7 _' ~0 A; }( K; h) X4 V( r* B& Y    pop = []
% E( G! A0 H7 C. g9 `; E% W: {/ n    li = list(range(DNA_SIZE))
, e) z8 K: b  e, C& f    for i in range(POP_SIZE):
        random.shuffle(li)
+ y) v) }) s2 c+ _' X: [        l = li.copy()
        pop.append(l)
    best_dis = []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
: Y5 g. e8 _6 b( \        pop = crossmuta(pop, CROSS_RATE, muta=muta)
& L0 I8 s8 \; W9 \- e        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
        if sel == 1:
/ S. V" W$ z; K  p' u8 r            pop = select(pop, fitness)  # 选择生成新的种群
- x+ T) S3 U/ K8 p9 x) K0 Q        elif sel == 2:
            pop = selectII(pop, fitness)  # 选择生成新的种群

1 q  Y  U4 M, H& k    return best_dis
+ v( h3 S% C6 Q! \: j1 W& i
# 4.1 块逆转变异策略对比测试
4 i3 d/ Q% m4 ^$ R- U2 @def opt1_test():
    ITE = 20    # 测试次数
    i_list = range(ITE)
    b_list = []     # 每次求出的最短路径
    t_list = []     # 每次求解的耗时
    b_listII = []
    t_listII = []
; I( J1 a' _; @/ b( a1 f8 `    b_listIII = []
    t_listIII = []
7 e8 y( H. ~( s( ~
3 F% {3 Z- ]9 N5 ?! r0 U    for i in i_list:
        print(i)
        # I. 原两点互换异策略
! k) F* }, p& z" a! L  O6 U        time_start = time.time()
        b_list.append(min(tsp_solve(muta=1)))
        time_end = time.time()
" Z! {# K; t4 e: Z0 C$ L+ r3 y        t_list.append(time_end - time_start)
        # II. 块逆转变异策略
, n- O2 W, U  i: P        time_startII = time.time()
: A0 p2 e4 M0 M4 b7 B7 ]5 N        b_listII.append(min(tsp_solve(muta=2)))
0 h+ e) O$ h' m% B        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
" W8 m; r& S( g% B2 E        # III. 同时使用上述两种编译策略
5 M4 X* g* T5 W1 @/ g3 h        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(muta=3)))
% V# N7 I3 Q3 U, T" N( z! [7 k0 V; l        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
6 t% a! O4 Y1 f! C6 u' P8 n& h9 O
# J( d+ G" \' H. b$ \% J0 n    # 做排序处理，方便比较
/ @0 e! `' u; l2 T' k- `    b_list.sort()
    t_list.sort()
    b_listII.sort()
    t_listII.sort()
    b_listIII.sort()
, X( B7 o  l2 x) e# X    t_listIII.sort()

    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
; A, s& T( ~! _    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")
8 @+ z/ q# q( ^( K% P9 ~    ax2.plot(i_list, t_listII, 'r', label="Block-reversal")
    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
! R5 h2 L+ P& ~& i    ax2.set_ylabel("Cost Time")
. M9 _( j& ]3 T' e    plt.legend()
/ V$ j1 _3 s9 W) v' S4 a; q    plt.show()
- `& C1 O6 f+ x% X2 x' o
# 4.2 锦标赛选择策略对比测试
def opt2_test():
    ITE = 20  # 测试次数
    i_list = range(ITE)
    b_list = []  # 每次求出的最短路径
    t_list = []  # 每次求解的耗时
    b_listII = []
. \4 E; y9 ?$ u; x8 I+ \    t_listII = []
; W: V! h! X( o# K' u    b_listIII = []
5 E* [+ D2 a' X3 t    t_listIII = []

* U9 c9 T1 i6 O7 d/ k# c    for i in i_list:
$ M( }8 ^3 R/ B8 d' h! o        print(i)
: D" f+ [/ g5 T* e# \: q        # I. 原赌轮盘选择策略
! i% n7 t; S3 n' ]0 e5 M: {3 _4 b        time_start = time.time()
1 P5 r; }# y, I5 p+ M2 I. ~        b_list.append(min(tsp_solve(sel=1)))
        time_end = time.time()
        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
! U+ u7 y5 o7 \/ W        time_startII = time.time()
        b_listII.append(min(tsp_solve(sel=2)))
        time_endII = time.time()
, r+ f2 f1 ?; G* y$ R        t_listII.append(time_endII - time_startII)
$ r, ]# P5 b/ }& P        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
3 @: ^# X  f* _4 N9 d5 d# D. r        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
/ C) q- |1 T1 y- y2 L6 {
5 u. E$ f9 J3 U) y8 E  h( T    # 做排序处理，方便比较
; f" [' R+ F% Z6 M. i# R    b_list.sort()
    t_list.sort()
* }2 ?5 S5 |" n. W  u* c+ }. b    b_listII.sort()
& ~5 `: X8 c) N  y; \( k7 y1 U7 I" ]    t_listII.sort()
& k/ q0 U% f2 M4 Z- p: U% D    b_listIII.sort()
    t_listIII.sort()

) R+ i; [2 z/ E9 H% [4 l: K- t    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
    ax1.plot(i_list, b_listII, 'r', label="Tournament")
' A/ O4 v1 h/ L    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
5 @( K. T5 V9 \$ Q! g) M; J; l    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
* W! V9 ]' j7 i    ax2.plot(i_list, t_list, 'b', label="Origin")
. D  A- t& `; @    ax2.plot(i_list, t_listII, 'r', label="Tournament")
3 g3 a* D0 l# b/ C; ?    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
+ n6 e! p: a3 z0 @5 s    ax2.set_ylabel("Cost Time")
    plt.legend()
2 ]0 V8 K4 }' ?) t" Q9 F  P    plt.show()

# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
def ori_main():
5 K& {! z# |* w+ T    time_start = time.time()
9 D8 @) c. s' ?% P6 l    pop = [] # 生成初代种群pop
5 _0 R8 a" G. V- o    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
& L/ l0 G& i- j- [        l = li.copy()
        pop.append(l)
    best_dis= []
$ X7 U! r; F* U$ b( G' e    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
0 C% s  o2 p  i7 v7 f( L    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE)
( Z0 Y8 r# t# x: f' S# d        fitness = getfitness(pop)
) \/ p# J8 g8 k! U        maxfitness = np.argmax(fitness)
* W. u0 c% Q" n) s2 v/ |        best_dis.append(distance(pop[maxfitness]))
7 J  x! U& `5 S! V        pop = select(pop, fitness)  # 选择生成新的种群
! ^$ X* v! |7 \4 L' z  W, t* l% N8 m
0 t7 @" l2 ^) Q" m: t- y    time_end = time.time()
    print_info(pop)
& w/ }: U! e' ?1 j' O8 f' y    print('逐代的最小距离：',best_dis)
/ ~! ^, R0 e6 Q, N: `* y6 d( x    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
1 R. i3 q0 m2 N) V+ w    plt.plot(range(Iterations),best_dis)
  c- ~5 m1 \; L$ S; _1 o' C
# 4.1 块逆转变异策略运行效果展示
def opt1_main():
    time_start = time.time()
    pop = []    # 生成初代种群pop
2 y3 H! T) k( c    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
' \6 S. b+ n3 H8 g  _+ }2 z/ j3 _0 M+ U    for i in range(Iterations):  # 迭代N代
: [$ E3 E1 |0 V( `        pop = crossmuta(pop, CROSS_RATE, muta=3)
' z2 ?, F1 F* ]- J8 P. a6 w        fitness = getfitness(pop)
/ _0 F- Q- h$ i3 |9 N, N        maxfitness = np.argmax(fitness)
, V! B! e" n0 c/ q7 L, Z8 p5 O% f: W/ I        best_dis.append(distance(pop[maxfitness]))
        pop = select(pop, fitness)  # 选择生成新的种群

) B- v+ ~) q; J7 f8 p* a    time_end = time.time()
    print_info(pop)
    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
    plt.plot(range(Iterations),best_dis)
* Y* x. z( A+ X3 a3 A& g3 L
if __name__ == "__main__":
; A( g" G$ J& R4 X4 T  A6 K. f
    ori_main()    # 原程序的主函数
  j1 Y; j9 ?  B: d    opt1_main()   # 块逆转变异策略运行效果展示
% x6 R3 m2 P  @( c$ L" V    plt.show()
    plt.close()
: [# {( ]7 K8 M( ?( J
# Y: t# h' j' W5 m    # opt1_test()   # 块逆转变异策略对比测试
- r5 J- ~! J: M. H. ?5 c    # opt2_test()   # 锦标赛选择策略对比测试
' z. J) e7 W9 r0 S' C. G8 e
% B  W9 B1 y* \! ^: }' S, e    # pop_size_test()       # POP_SIZE 种群规模参数测试
' @4 w* a& l6 g  _0 _8 [    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
2 E1 ~; i6 _' R, h" l1 n; }    # muta_rate_test()      # MUTA_RATE 变异率参数测试
: I5 A, @* y8 ]. e) F6 \    # cross_muta_test()     # 交叉率和变异率双参数测试
7 u$ c! q* M+ v) p2 d# _
8 K# H1 d0 l+ R) w* _
5 o4 i, u" ?" T6 _1
4 Y3 g. |1 ~5 x" m2
3
, x3 s) W- I( g( ^4
5
6
8 z9 F, \5 p4 O  w- z/ Q7
8
0 W  M- ?" V, }: h1 o9
10
$ Q. W* T3 L# x! b* \11
12
! z4 B. k, L/ C* W: h6 }13
14
; b/ H5 z1 @" ^- Y& E15
  J; o, n9 M9 L- T16
17
% `1 f5 c) p$ Y! H18
19
20
21
2 l% g5 q6 S2 z22
23
7 L7 N; F; g* U/ j6 G0 @24
  [9 c( l8 Q" D6 G25
3 L' K* x) U! U/ X$ [26
6 f6 k! {; q; v6 a0 U27
; z4 C" k* z4 V0 a/ V28
29
30
4 _1 L/ u% S4 k31
1 q2 y* v0 V: Q32
* {5 m; J% C3 Y. Q33
34
35
- ]- V5 W  f+ W% a" F  g* G9 F: ?36
37
38
# u6 V4 B0 O( ^) b. L9 I+ D5 h39
40
41
42
. \8 V! W/ F2 R6 S: f43
44
# c1 Q9 Z5 y6 \5 \2 E. K# L6 S45
46
2 W* F+ A+ ~1 I47
# U8 S4 k5 i9 p" E48
6 t2 i3 E+ p/ M49
50
51
# L- _( L3 W- I# U6 _: j- i52
53
2 M- ]; I- Z0 e/ L* [! y54
55
56
. Y# @, U4 P2 q& K57
58
: u: @' f% y9 C4 W4 |: V59
3 ^) Z, e4 {; ]60
61
2 K% [: P7 t3 X2 D62
63
64
65
66
67
8 M) c% ^, s* o6 G/ {" q- J68
69
70
71
72
5 j' m( {! h, ?8 _; z$ N' ]73
! l' _! `1 }! W# j8 W& C/ J74
75
" w3 D4 ~+ Y, K2 O4 S76
' _. w7 b+ L8 q6 y. N77
78
+ Y: h# U. i; J: Z* X79
80
81
9 h/ s; c) M- d3 `; U6 F  A1 a' j) |82
, |, [: X% e2 a2 m83
84
; _7 ~6 o% A8 F& Z+ z$ A, J2 _7 I85
86
; e& P% d1 E" h/ \8 T87
9 B4 D3 O/ R" Z88
89
90
91
7 F. d; d, m' J) J& P1 R92
93
94
95
( C! m) \7 q; }0 ~* u3 f96
97
98
99
100
101
- t' b3 o  p" S3 _" r8 J) f& _102
103
104
105
, K% c0 M  ~+ T6 H- B0 O4 u7 U106
. n) k" M  ^, h+ {/ E$ e' s0 v# l107
108
) ]: v% v* R: A% J: R2 R109
110
! J, w! J+ D+ D; F* h111
112
7 l2 |$ H% S+ A5 Z113
; q& T) l4 s2 W6 g114
* ^; V1 v" v  s115
116
117
) x' a( v& {1 K/ }$ f6 ]118
119
! k& Z' `  i. a; c120
6 C, X8 Q, c( s121
; {! p! N% B3 H- r% b6 N5 w, P122
3 R3 |) U2 ]# _4 s  z% r8 [8 z+ g2 h" A123
3 }% G% n5 R) ]1 k+ U* u7 r+ j7 _124
* E  I; h; i- z& d125
126
* b4 m1 A+ v3 t2 }3 \127
128
129
130
131
2 w" x6 t% n( b/ Z: s5 ]% b5 g132
' _; T9 z( b6 L: f* G) r9 V133
134
# A% ~( t9 t; \  D+ L135
' I1 u( a4 a; V, @; K5 v% u136
; `- ^; l  [. I2 T/ o137
138
139
140
  i! r8 q2 Y2 u5 R( v2 L  T141
5 H' B  H, j9 k4 m7 k142
143
144
6 f5 |% r/ Z+ P1 l' }% w0 W+ u! s145
146
' z  p) Z" j+ T147
7 V; v8 W/ g  u3 p9 R0 U$ y7 K0 ?148
4 W4 x8 B  A0 n" A1 C8 l- X149
. ?% X" R# C! R& v. \: B150
) N' S. H: n7 ~151
152
4 C7 ]5 V6 @7 L5 B153
- P) [/ ^4 p) q! x154
3 Y+ z9 D/ H8 O: J155
156
( j% b1 p8 }  A! I" p, s$ d8 }' S157
158
* g1 y* n- c- f- r159
160
' b8 |( K5 j3 O, [1 ?/ [161
162
4 r# b4 J( w4 z8 a7 E: i163
; B; T3 n( z  i$ O3 Y# Q. i5 N3 r/ S164
165
1 s+ p2 r# W  I3 J. L166
4 o! ?& ?7 y) `167
168
9 J8 t% h& H; Y5 c5 i$ y. H169
. d' p( y' d: @170
171
172
8 D& h) Y/ R5 S. g  C173
2 {& S- G" [8 D. j& K& {$ h174
175
, ?( X  B, V2 |. `) |176
4 F0 e2 `1 I/ [) w6 N" @; y: T177
178
! a$ }) t# b7 M179
180
181
2 W4 f, O; [0 ^* y182
' W2 L* B3 S) |1 w! }4 p) U183
184
1 J. _; I' V2 W5 E9 V185
186
; Y/ f) d. Z; C& d187
188
. h7 R- w/ l* r; _8 h3 }$ k9 k+ s189
190
( I: t6 x* f* x$ H% O& H  _191
9 s9 j& x/ y" Z- T/ G; P192
, X( {: [, U5 H! N' w193
194
! H/ `* J: V" s' d) s" }9 I$ K4 Q8 R195
/ R' b$ K" R" X2 f196
- C  T5 _- K+ K" @4 h, ~" g" T197
198
199
200
201
202
. x8 o+ h4 D6 P+ a% u: n9 e203
204
205
206
3 x# \! M- ?% ~$ a# D- E9 y207
208
209
" g6 r% k! N1 P: Y; i210
8 ]% E& ]+ d# l$ j$ U; h211
212
; F9 y. h5 M4 ^) V% x+ w3 c213
214
+ \4 Z' ~+ N5 V  j/ B215
8 m9 G- s. E2 {216
217
218
+ [9 a! y( Q( k) a, b* R2 A219
220
221
222
223
' T* K( A9 p/ p) n# D224
225
226
227
228
229
230
% N8 D: t2 t6 \5 C: W231
1 B, @/ y. Q9 \232
4 P0 D7 Z9 |) Z, ~: T233
% \1 Y2 c( F, j234
235
236
, _- Y0 x, w0 H/ J& S237
( i9 C$ C0 j$ R& o: a( b5 s) W238
, W. O0 h, C- y& k7 B& l4 T: ~239
240
" j& a. I8 {0 S/ h241
' E/ {# G' q8 w8 y242
243
244
5 y6 g# l( Q9 [: D' W: T245
2 e2 I4 u! u( ~246
: U6 l6 Q8 D! Y- P0 x" z+ A3 y/ o4 ?- h247
248
249
250
2 L3 z! j" Q' H% J! n+ P% Z+ I251
; L1 G! [2 P- S# K252
253
254
255
4 J4 M+ B8 s" U' l0 c256
257
/ H5 B" p% O( L( i7 B. q# O258
259
# }  I! }) }! l3 F+ \! X1 ]- Y1 s260
261
262
263
$ p6 w; t. F" y264
265
' V" p! n$ g* x) E& x5 m266
267
: L0 P. F! y0 i3 D* R: `268
2 b. a' C8 l. i& L: Z, o1 V269
- e% z* s# p; ^  N- z" i8 T270
271
, u& y" `6 Z6 F/ v$ y272
273
274
275
- }( a% j- t5 _) K/ ?1 ]276
6 _3 X) Q' A# F% H277
7 T4 S' M, [; \# e; H! B% J& E278
; X5 F$ q( d/ w, n/ m, n279
280
281
282
283
3 t  ]" ~" Y+ @. a' f" `284
: o) [: a0 X/ u7 U285
6 Q6 {  L, z0 F- }3 H1 Q286
287
288
/ [# e! e' T9 v. R289
; ?* H) n1 I) M. O290
: @/ _* [# j+ }291
292
293
: C* W3 t- m+ U294
295
296
7 n* w7 z" D% W7 W0 Z% |297
% T. X8 v0 v5 l' J( W+ {" w298
299
300
2 L, b8 e- |# t301
5 [3 R3 v# Y0 b- W302
303
304
' B) }/ t) Y. H9 o; b% Z305
306
; M( Y4 A4 P$ q2 ^9 w+ V5 h307
5 \0 H* C) S  R. N( q# W308
309
# U6 n: Y: _' j4 M2 o310
311
312
313
! V/ P) N2 D# [0 t7 @314
315
5 U6 q* t  x" f316
317
5 ~+ b! m7 x9 K, a& @# ~318
. H3 c" L( l  G) B( v) f3 Z319
* k  Y8 y/ E2 p/ j: D320
2 S) ^9 \  h% o2 L% Z/ Y321
! c4 o; x/ e& {" U4 g; `. T322
323
+ X- c. K0 Y9 [. h) x324
325
4 z0 O5 h* S: L+ T/ _7 d326
2 R" u7 p6 j) y/ l' j1 S327
328
329
330
9 n# |* p$ v# A; G" b( M331
332
, k4 _% I+ {4 V* H/ a. V333
/ l: |' o5 S2 R- y! i334
335
336
337
338
339
340
341
342
343
344
* R. @, m/ h$ q345
346
+ Q  x0 {& z2 @3 o6 T347
  R3 ~( a% y$ H3 j: X  L5 F- ?348
, @' g0 p9 O# a) K349
350
# l; [7 l; ~0 x, L; D/ T351
352
3 i: E4 A1 N& f, }; D9 D3 {353
354
355
& H3 |% F/ d" b356
. k( F! E" ^( p: z  V- q/ i  Q/ y$ F357
358
359
; x9 E( V  `- u: F' u; b  K6 z360
# t1 ~8 R. V' Z5 R0 V5 N, ?  K361
9 |" e/ p% T" Q! ~362
363
3 @+ x; ?) Q: [) d9 D! H, Q& i364
365
$ w0 a/ L( e' ~0 O2 w8 E, G7 R366
& ~" ?+ a( L" p  e9 R+ E/ A) Q367
( W! ]3 q7 p5 l368
369
) E& V4 N' }+ Q/ K370
371
" r+ W4 _, Q3 Q6 N372
373
$ T4 D1 G- ]% m; s374
375
, J* O5 _; h& J376
377
378
379
380
381
382
383
384
385
386
( Y7 F/ l! K) Q7 G% d) s, p, s6 I387
388
389
390
5 C, w3 d! W, e. a391
392
393
394
395
# p$ m  t, F/ ]396
3 `4 l' \( v0 a397
; j- j% p$ g& j9 Z398
399
- B- I! B- F7 M$ W: R400
401
4 i, d6 _9 _( n) z* D+ y402
3 F+ Z: @: G4 F# J! P8 Y403
1 j) _* G9 n2 q  r404
405
: ?9 U& [% K4 b* Z$ g: h% l406
407
408
$ }9 E1 C! E: F7 c" b' v8 ?* O" ~409
7 ~) k2 U. K9 E410
411
412
413
414
415
416
- L/ m- \' D0 A3 v4 \* e417
% |. U/ ]: r$ k. D3 T* A" B+ G1 }418
419
420
, D- F1 T( Z+ u& E" v421
+ w( m( b0 U( s  W# O422
423
7 t9 z/ ~" s& y+ ~! \1 F" j424
425
6 D* c$ D2 a4 N& M! v! ^426
9 ]$ ?  w9 v$ ?7 O. W427
+ x" M" ^. u+ d428
) _, s/ B6 E5 L/ z429
430
431
432
433
434
: x3 K( F4 @+ _% o: ^% h435
5 J; |: L; Q, m436
! r; ~! d0 K' O, N- [* \$ w437
438
439
3 S2 ^8 r3 A. u; s* ?4 P) R4 \/ P6 c440
441
442
443
" T- l& q7 V) F9 g# M$ E444
% i, }, W. _0 s& Z! U8 g445
446
. V  e! r5 ]! I4 v447
448
449
450
451
452
453
454
, j; P/ v1 @, U5 L455
$ `. A0 s, p" {9 `$ w7 [456
  }' J3 r, T8 z% S& G457
458
459
460
+ U: E8 M$ ^$ {7 i1 Y461
" U8 z5 h+ J+ r1 L1 Y462
463
464
. X: V0 Z" @9 Y" U4 n9 _$ ~* ^465
466
467
* \( m" M- u9 ]) W  i468
* t8 p( \+ c. t/ E469
: v0 d3 Y! S+ o: Y

0 r. }: R  W1 z" C, |& e

3 I: e  }# F. ]( }! \& i& O1 b& {/ @) ?
3 Q; R$ ]7 F; \: g& L# m* [5 s6 c  _
# U. ^5 N/ i1 _+ e, z& q


$ z6 O& k9 S. _! M. G
: R# y$ o6 M- M& M& g$ t4 g+ u


( c( ?: e6 }- i7 o" L

" A8 Z9 v! i3 p+ [" k
6 ^% `9 j. R8 m# X9 v) A* f

5 l& @& U" Z" x$ \+ P* F  U



, h3 K7 z! P9 a% U$ ~5 q
" W6 E3 n! u1 p: d
  D3 h1 Q0 J- a9 j/ ?
* }& i9 a9 Q' `2 ]# G& y. J

6 ^6 q% \/ }# t————————————————
版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212
" d6 S7 E4 H% P3 A
' T( n1 ?7 c! u1 q4 V- `