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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
! _1 I1 ^, b- A# j  d4 K目录
人工智能第四次实验报告 1
. i. G. v  X' m! P) q遗传算法求TSP问题 1
3 U# `0 Z. Z& H! O  w# M2 W一 、问题背景 1
2 _2 a2 r. Y) U; z4 W4 ]. w3 b) ]1.1 遗传算法简介 1
- Z6 o' Z  s& t& S1.2 遗传算法基本要素 2
1.3 遗传算法一般步骤 2
二 、程序说明 3
2.3 选择初始群体 4
2.4 适应度函数 4
& h. d0 I& f: G' _& b- O2.5 遗传操作 4
- N* a1 P" g+ i: \) \2.6 迭代过程 4
三 、程序测试 5
3.1 求解不同规模的TSP问题的算法性能 5
3.2 种群规模对算法结果的影响 5
& o: \" w4 J8 i& v2 V  c3.3 交叉概率对算法结果的影响 6
! G- i+ s. y0 J$ b; J8 m3.4 变异概率对算法结果的影响 7
3.5 交叉概率和变异概率对算法结果的影响 7
8 `+ x$ j& ^4 k# R1 k4 R% `四 、算法改进 8
/ m+ }. a2 O8 `4.1 块逆转变异策略 8
4.2 锦标赛选择法 9
2 Q, d2 r% w: Z' T( M五 、实验总结 10
+ \( t$ p5 F/ T一 、问题背景
0 @* s5 X3 X. b- a" y1.1遗传算法简介
% w7 B. z) T5 N, H* I+ ]遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
1.2遗传算法基本要素
1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
2.设定初始群体：
8 u" E- {# g$ x9 F1.启发 / 非启发给定一组解作为初始群体
2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
/ O6 h: h% p5 I, b6 O- m; `4.设定遗传操作：
1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
) y  v& v+ a) b0 k7 G% j0 R# M/ d2.交叉：两个个体的基因进行交叉重组来获得新个体
3.变异：随机变动个体串基因座上的某些基因
/ b& x2 u9 W* p0 |. l3 c5.设定控制参数：例如变异概率、交叉程度、迭代上限等。

import numpy as np
5 ^9 ^! h! `: r+ ?! }import random
import matplotlib.pyplot as plt
import copy
import time

9 J3 t6 B- e2 e- h' \3 jfrom matplotlib.ticker import MultipleLocator
from scipy.interpolate import interpolate
: y: t. U- B+ |, N1 ]  n
6 S) J( q( c4 w3 d: wCITY_NUM = 20
City_Map = 100 * np.random.rand(CITY_NUM, 2)

) d$ X  k3 H5 r: GDNA_SIZE = CITY_NUM     #编码长度
# B" D1 V' w) m  P3 r9 c/ ^* l8 ]( nPOP_SIZE = 100          #种群大小
CROSS_RATE = 0.6        #交叉率
- `; S9 p# s" D1 }MUTA_RATE = 0.2         #变异率
Iterations = 1000       #迭代次数

# 根据DNA的路线计算距离
def distance(DNA):
, T7 t3 I2 x2 x  w3 k% C    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
        temp = City_Map
    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5
1 _4 D( k: {$ b" ^1 ?4 t3 c
# 计算种群适应度，这里适应度用距离的倒数表示
  V/ o5 i: J, x0 U1 g; cdef getfitness(pop):
    temp = []
    for i in range(len(pop)):
2 @! A% U- Q) `- U! v5 @        temp.append(1/(distance(pop)))
    return temp-np.min(temp) + 0.000001

3 f4 R6 c; N7 I' s6 C7 t/ X# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
def select(pop, fitness):
    s = fitness.sum()
$ q' c5 d2 T) g, x& w2 V    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
8 w/ }) f% U& g& U    p = []
    for i in temp:
. e/ i! t4 T6 G. ]/ i( l        p.append(pop)
  u6 f; \  z, C- k" [    return p
5 ~' I4 W/ Y) d$ k
" ]9 P. Q( D  z# 4.2 选择：锦标赛选择法
8 Q$ N( v% e; s) idef selectII(pop, fitness):
: C0 z, {+ u) P& G0 Q: Y. R4 p    p = []
    for i in range(POP_SIZE):
        temp1 = np.random.randint(POP_SIZE)
        temp2 = np.random.randint(POP_SIZE)
        DNA1 = pop[temp1]
        DNA2 = pop[temp2]
! O) w2 P5 f& ]% e: n* k1 l9 E: l        if fitness[temp1] > fitness[temp2]:
            p.append(DNA1)
; h) h5 x. D% d! r7 ]1 f        else:
            p.append(DNA2)
    return p
4 x# k1 d9 Q8 {! z2 M4 i3 `
# 变异：选择两个位置互换其中的城市编号
: e1 n  U4 [- U7 e$ \) Fdef mutation(DNA, MUTA_RATE):
) _- b" M  y3 j) Q  g    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将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)
        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]

# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
8 H, n, E  k% W6 Y$ Qdef mutationII(DNA, MUTA_RATE):
$ {# b- w4 w8 t9 f' T3 t4 d    if np.random.rand() < MUTA_RATE:
; f/ w. _; w9 J0 n        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0, DNA_SIZE)
  Q" o- F. w$ z4 B        while (mutate_point1 == mutate_point2):
- K! f- w( ]& G, g" @- }3 @: o: v            mutate_point2 = np.random.randint(0, DNA_SIZE)
& z- o4 y4 @% s        if(mutate_point1 > mutate_point2):
& j9 e% y. O! c9 R3 I# E: X            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
        DNA[mutate_point1:mutate_point2].reverse()
7 A8 I+ v/ Y9 c$ F7 T! A
# 4.1 变异：调用 I 和 II
8 n2 q# Z  p9 q: ~/ ]- Z; hdef mutationIII(DNA, MUTA_RATE):
$ |( g* \- M$ z5 a$ P5 s    mutationII(DNA, MUTA_RATE)
) y0 k+ |4 x7 D) M    mutation(DNA, MUTA_RATE)

# 交叉变异
# muta = 1时变异调用 mutation；
# muta = 2时变异调用 mutationII；
# muta = 3时变异调用 mutationIII
def crossmuta(pop, CROSS_RATE, muta=1):
    new_pop = []
* a: A! p5 m0 ], g5 S    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
        n = np.random.rand()
        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
            temp = pop.copy()
" w; ^$ f0 Q7 \6 a( ?, b            new_pop.append(temp)
1 D) ~+ z7 p" H4 B        # 小于交叉概率时发生变异
        if n < CROSS_RATE:
4 ?7 j9 \' v1 I            # 选取种群中另一个个体进行交叉
$ s" K: |; W( k8 N6 T  Z' N6 w            list1 = pop.copy()
1 m+ {& E0 a( H) H: g# t3 |            list2 = pop[np.random.randint(POP_SIZE)].copy()
& C% P1 E  b* h$ T: f6 q0 A            status = True
            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
            while status:
% N8 `% j% X- q                k1 = random.randint(0, len(list1) - 1)
7 [& [( f/ z+ F                k2 = random.randint(0, len(list2) - 1)
                if k1 < k2:
3 Z# E6 P1 A) J                    status = False
, G: A4 w+ S# `2 [
            k11 = k1
2 k+ m8 o' `6 q& \/ P! ~' ^
            # 两个DNA中待交叉的片段
            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]
) N$ ?% h" w0 o6 P+ v
            # 交换片段后的DNA
            list1[k1: k2] = fragment2
3 ?% n6 g: P: Q% D* @$ N/ p            list2[k1: k2] = fragment1
# O: G! r& A% A  j- ~# k
5 F' A* P6 ~- h" }6 o+ ^: C( d( f4 J+ ?            # left1就是 list1除去交叉片段后剩下的DNA片段
* y2 a' R  i3 Y/ X% I- l& e            del list1[k1: k2]
/ U- h2 l% H9 d4 [5 x            left1 = list1

3 I' v, C/ C8 I2 p2 D+ F            offspring1 = []
5 ~$ s; D) R6 f3 U$ @            for pos in left1:
3 A" m. N; L; A: I- w                # 如果 left1 中有与待插入的新片段相同的城市编号
                if pos in fragment2:
+ J) ^( C3 ^$ p: a                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
! T# H& N( G1 \3 P, N( ~4 r  e                    # 循环查找，直至这个城市编号不再待插入的片段中
                    pos = fragment1[fragment2.index(pos)]
                    while pos in fragment2:
0 t# W. i8 R" |+ m! w" h                        pos = fragment1[fragment2.index(pos)]
6 |6 p) P: s6 k" d0 p6 T                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
; ?: \  G8 U8 K& Y( w" H3 A9 a                    offspring1.append(pos)
                    continue
                offspring1.append(pos)
            for i in range(0, len(fragment2)):
                offspring1.insert(k11, fragment2)
                k11 += 1
            temp = offspring1.copy()
) j+ ~* p; Y$ r% O8 v1 o6 _            # 根据 type 的值选择一种变异策略
            if muta == 1:
                mutation(temp, MUTA_RATE)
            elif muta == 2:
                mutationII(temp, MUTA_RATE)
            elif muta == 3:
                mutationIII(temp, MUTA_RATE)
            # 把部分匹配交叉后形成的合法个体加入到下一代种群
, ~3 X- X/ q( r; R+ a            new_pop.append(temp)

    return new_pop
" h! q* N1 Q6 Y; c4 C
def print_info(pop):
    fitness = getfitness(pop)
4 r! }- i! u" X( P" L3 h    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
    print("最优的基因型：", pop[maxfitness])
, I- n" P/ Y0 S- e# w    print("最短距离：",distance(pop[maxfitness]))
: m" A& w3 b2 V- n# h1 N; l/ x    # 按最优结果顺序把地图上的点加入到best_map列表中
% K. p5 R. D& }9 P) V    best_map = []
% h. I* @( K" i8 o    for i in pop[maxfitness]:
        best_map.append(City_Map)
3 E+ Y( C* k# j    best_map.append(City_Map[pop[maxfitness][0]])
- k9 K+ o0 ]) I. |6 e0 w2 D. m    X = np.array((best_map))[:,0]
/ X. t5 Q* \# C    Y = np.array((best_map))[:,1]
0 `2 D( q+ M* K( f& k, l/ f    # 绘制地图以及路线
2 a3 ^6 P" c, s0 e. ?: X    plt.figure()
    plt.rcParams['font.sans-serif'] = ['SimHei']
" J0 G- T! C' M5 S/ G2 ~+ Q    plt.scatter(X,Y)
* u: t. I6 ~# V* m3 }: [    for dot in range(len(X)-1):
7 O: E3 \$ O' N" A        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)
" v! f5 B4 R: W( }( h/ Q3 M
& P" e5 r. i5 m. z8 ~# 3.2 种群规模对算法结果的影响
, Z& l/ B/ g/ @& A+ h( Bdef pop_size_test():
    global POP_SIZE
6 Z- I8 e& _" w  w" l& `: T    ITE = 3 # 每个值测试多次求平均数以降低随机误差
9 }1 L: r( C! `( e# u- L* }    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
# v2 G& q: U, z& H1 h    b_list = []
    t_list = []
* U3 X3 l5 l1 N6 N5 W    for i in i_list:
        print(i)
        POP_SIZE = i
        time_cost = 0
        min_path = 0
        for j in range(ITE):
0 m; e+ M$ N0 |/ W/ f            time_start = time.time()
            ans = tsp_solve()
. t  S' f6 x( u9 s+ r& p! H            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
! _) B$ z5 D' C1 t        t_list.append(time_cost / ITE)
+ W& q* o5 @, a4 O: p    show_test_result(i_list, b_list, t_list, "POP_SIZE")
& [6 D) w/ R$ j8 s/ _7 s, d
3 B6 Q4 A" a5 f$ \# 3.3 交叉概率对算法结果的影响
, l1 M/ `2 C' p, d+ ?, ~def cross_rate_test():
7 k/ ~+ h/ |/ K7 k8 c+ j    global CROSS_RATE
6 w" \) Z9 K# E' w. B% o9 M    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
8 V0 Y% A2 S  F4 y) n( N2 ]) f    for i in i_list:
        print(i)
        CROSS_RATE = 0.05 * i
  s8 A0 u2 I* d4 D& v# u" e0 {        ii_list.append(CROSS_RATE)
        time_cost = 0
        min_path = 0
+ c# ?; x3 o9 K* ?) |9 _        for j in range(ITE):
            time_start = time.time()
6 i) b9 c8 P# m2 N; i+ `; I% T            ans = tsp_solve()
/ ~# e% \, |& l% Z            min_path += min(ans)
            time_end = time.time()
, s4 K$ m; |- w2 U" d            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
; |* B4 p+ n/ v+ ^) L9 S        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
& q: V$ O  s6 S5 u0 m  G8 \1 j- w    ITE = 3 # 每个值测试多次求平均数以降低随机误差
+ z5 U5 Q: c. k2 \    i_list = range(0, 21)
. F9 i" H5 `4 D: b) S    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
, b0 E' b. P' u) M/ f; L9 x    for i in i_list:
& \3 W9 G( V+ L; Q2 z; k! o& u0 I        print(i)
  [7 s4 j3 J2 T0 N1 E; Z3 T9 P        MUTA_RATE = 0.05 * i
7 l! N) Z  x' ?+ [0 H- i0 o        ii_list.append(MUTA_RATE)
        time_cost = 0
        min_path = 0
        for j in range(ITE):
            time_start = time.time()
            ans = tsp_solve()
            min_path += min(ans)
) ]+ K' s+ P' @% S- G            time_end = time.time()
+ T- D4 Q  N* @5 I            time_cost += time_end - time_start

0 u* i9 j$ {: ~9 T' B2 N        b_list.append(min_path / ITE)
0 M' o6 p" J  X, q6 H; [# `# c& i        t_list.append(time_cost / ITE)
* P2 q/ S, ~; h& v# |    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")
$ [, b# U1 R* E) J1 B. q( n
# 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])
* [- c" f" m5 \" o    X, Y = np.meshgrid(s,s)
# Z6 p5 a. |, s+ O7 P+ [. b7 P    Z = np.zeros(shape=(11, 11))
1 b9 u- ~2 w. v
" \% S* `5 k$ x- _8 d2 ^7 X5 p* t    global MUTA_RATE
! P9 B8 u* w  @4 U. y( R8 S    global CROSS_RATE
9 P9 H% [9 E7 e5 t6 V0 j' v8 [% X    for i in range(11):
4 O; T9 V2 F3 x- ~2 P8 i        for j in range(11):
9 z' F8 ^! h1 h! n! a4 @$ D            print(str(i) + ":" + str(j))
- Y7 [. }; d; s, w+ r6 I            CROSS_RATE = X[0,i]
            MUTA_RATE = Y[0,j]
            ans = tsp_solve()
3 I* p8 q+ Q9 E# U4 _5 o1 z; V            Z[i, j] = min(ans)

    ax = plt.axes(projection='3d')
% H6 Q- U/ p: L- a( V+ w+ z% J    ax.plot_surface(X, Y, Z, rstride=1, cstride=1,cmap='rainbow', edgecolor='none')
, b: }4 ~  L0 h    ax.set_xlabel("CROSS_RATE")
# I* M6 t: O" y! G1 X; e3 R& ~2 U. c    ax.set_ylabel("MUTA_RATE")
    ax.set_zlabel("Shortest_Path")
    ax.set_title('TSP')
  N9 S2 K4 [: D9 J, g: Q; P    plt.show()
% H" q. r8 T' a9 D. M; I, j) x
# 3.2-3.4 生成参数测试结果的可视化图表
8 K9 ]" {" W$ [def show_test_result(i_list, b_list, t_list, msg):
% p3 Y! x) Z" C$ o5 _1 C8 Z8 n    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b')
    ax1.set_xlabel(msg)
: {1 J  m& u. F' `, v% ?7 B    ax1.set_ylabel("Shortest Path")
6 N" n/ }: c# A
    ax2 = plt.subplot(122)
' a0 j' x! ^. Z3 i1 S    ax2.plot(i_list, t_list, 'r')
& M* H' }2 X+ R' h    ax2.set_xlabel(msg)
    ax2.set_ylabel("Cost Time")
1 I+ f# N* [4 V0 {, y: U! H" u: h    plt.show()
8 G5 T- a# \& \" P- N
% \9 y' v+ u- g: G9 [# 求解TSP问题并返回最大值
9 O: f  D9 S3 E, A6 `# muta 指定变异方式，sel 指定选择方式
def tsp_solve(muta=1, sel=1):
& C6 ]# b" K- _. I6 ?" V    pop = []
    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
! b; ^* Y. T( o% F4 ?6 I+ S1 T    best_dis = []
# u; b* ]7 n8 t( [8 d7 W5 @  n    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
5 e/ e9 a) b+ F/ }# h6 z        pop = crossmuta(pop, CROSS_RATE, muta=muta)
/ w- }3 a6 I2 {5 x/ T4 J$ u: |. d4 d        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
        if sel == 1:
, p8 j; I6 O& p$ I( f+ X, X            pop = select(pop, fitness)  # 选择生成新的种群
        elif sel == 2:
/ z; o5 |% a  _! o            pop = selectII(pop, fitness)  # 选择生成新的种群
" B% [3 }8 Y1 w8 h; @
    return best_dis

# 4.1 块逆转变异策略对比测试
def opt1_test():
4 t. ~9 R4 N. C9 K! \% l( k    ITE = 20    # 测试次数
$ K: U1 }8 A4 g    i_list = range(ITE)
& z1 \0 U- ]7 `$ j6 b+ _# ?6 O    b_list = []     # 每次求出的最短路径
    t_list = []     # 每次求解的耗时
    b_listII = []
9 c6 b: K8 k$ `3 S9 b' N" w    t_listII = []
    b_listIII = []
    t_listIII = []
( d1 k4 R& F, Y8 u
    for i in i_list:
% u1 Z/ C; A1 @, }8 y8 B1 _" T        print(i)
        # I. 原两点互换异策略
        time_start = time.time()
+ u+ C. z1 r5 u9 `; r        b_list.append(min(tsp_solve(muta=1)))
        time_end = time.time()
        t_list.append(time_end - time_start)
        # II. 块逆转变异策略
1 K- t1 R, o. d5 q# w  ]4 D        time_startII = time.time()
        b_listII.append(min(tsp_solve(muta=2)))
+ W! ]2 g1 @3 x# Y( H( ^        time_endII = time.time()
  J# F* h0 i. A        t_listII.append(time_endII - time_startII)
. _5 P. r7 g4 E( u: E: n        # III. 同时使用上述两种编译策略
: r& {  m$ H; w) ]6 h        time_startIII = time.time()
6 h' W7 y$ J3 m8 c        b_listIII.append(min(tsp_solve(muta=3)))
0 s( |8 O& I, ]6 i: G, X4 b# W+ k        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
4 }+ P- f# k) D, j
    # 做排序处理，方便比较
    b_list.sort()
' j- n- v! C  ]9 p9 i; y$ p    t_list.sort()
9 ?7 ^" S/ E4 |: A4 O    b_listII.sort()
    t_listII.sort()
    b_listIII.sort()
    t_listIII.sort()
! p! t9 ~" |/ z9 J& f
2 U; w# A8 O% D    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
9 R( |: R9 C( |    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
    ax1.plot(i_list, b_listIII, 'g', label="Origin + Block-reversal")
; ~: O: D' c+ \    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
5 O' _8 a9 e4 C3 X    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")
, O' s8 s! N6 \& w: M    ax2.set_ylabel("Cost Time")
$ x9 d' r% }8 W( U    plt.legend()
    plt.show()

: {( C4 Z2 w' E5 }2 r0 b9 I; G6 m0 \# 4.2 锦标赛选择策略对比测试
def opt2_test():
6 T7 b1 b4 X; |' P, S7 Q3 _    ITE = 20  # 测试次数
- N/ h/ U' E& Z* |) L- d    i_list = range(ITE)
' n( m% i+ u7 t+ b    b_list = []  # 每次求出的最短路径
7 A& k1 v! Z: z- G    t_list = []  # 每次求解的耗时
    b_listII = []
    t_listII = []
    b_listIII = []
2 D9 V; n3 f5 m) K% S9 w5 V    t_listIII = []
- H* z% J  q& [) X# L4 N
* R5 ~3 l  F% |& h# u+ M. e6 \# P( C    for i in i_list:
7 E3 K5 _. j1 C" I& z+ T, ^        print(i)
        # I. 原赌轮盘选择策略
        time_start = time.time()
        b_list.append(min(tsp_solve(sel=1)))
1 r8 k5 [# y3 b! F        time_end = time.time()
- Y* O! M0 l: y* O9 d        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
        time_startII = time.time()
6 t( D+ `# }1 h        b_listII.append(min(tsp_solve(sel=2)))
2 P4 U  Q- O, q        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
% _, {4 U% T5 Q5 ]& y3 q        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
        time_startIII = time.time()
/ f: y# |7 L* \  C5 p        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
8 f. }  @" w0 m" `% P, _# i  C1 t        time_endIII = time.time()
3 Q  E' m' D) P: Y; g$ H# y        t_listIII.append(time_endIII - time_startIII)
  b3 w2 U0 i$ @3 \8 ]- X6 a
+ w/ G+ M# G  v0 @+ Y+ c) E    # 做排序处理，方便比较
+ f" c7 U2 D& H* B+ i( N1 Y    b_list.sort()
    t_list.sort()
; i% _. a8 k% a# U8 n, N/ E5 t+ W    b_listII.sort()
    t_listII.sort()
    b_listIII.sort()
) h* Y! Z/ f6 U; `# y' w5 y3 k0 a    t_listIII.sort()

    ax1 = plt.subplot(121)
/ r6 [- J3 b0 m2 {( M: z3 J$ l8 z* {    ax1.plot(i_list, b_list, 'b', label="Origin")
    ax1.plot(i_list, b_listII, 'r', label="Tournament")
4 n3 q& ^. f2 b4 ?8 i; O0 {    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'b', label="Origin")
% ]% v1 X7 Q) t$ \' b    ax2.plot(i_list, t_listII, 'r', label="Tournament")
7 u& S/ V5 p2 d1 O8 ]- w    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax2.set_ylabel("Cost Time")
    plt.legend()
2 ^' I* Z* f- n& j8 F    plt.show()

# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
def ori_main():
1 C" c, C' i$ i; o; K6 [    time_start = time.time()
    pop = [] # 生成初代种群pop
* |) b9 G. g; k/ @6 e; \) \    li = list(range(DNA_SIZE))
$ X8 Q! \3 o* y$ O. o    for i in range(POP_SIZE):
. @7 n8 U3 o7 P: Z" i+ J        random.shuffle(li)
0 A/ |% e! W" N6 W+ _/ t  r        l = li.copy()
        pop.append(l)
    best_dis= []
# j1 ~- L4 f: a+ ?* y% P4 p    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
# I& y- W2 _3 e+ r$ [5 f    for i in range(Iterations):  # 迭代N代
2 U0 d1 m: j7 _0 y        pop = crossmuta(pop, CROSS_RATE)
8 ^# o. n' T4 M$ v# K        fitness = getfitness(pop)
9 i5 V1 d" H( F4 r; {3 C& @        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
( Z- g$ C$ j+ N8 l& Q$ p3 W        pop = select(pop, fitness)  # 选择生成新的种群

4 y/ d$ T- l  {    time_end = time.time()
3 ~1 }$ V+ k! d1 O# L. r6 q    print_info(pop)
    print('逐代的最小距离：',best_dis)
0 r1 O  o( u1 z" @7 }    print('Totally cost is', time_end - time_start, "s")
- D( y6 F8 K: R/ |0 _6 T! V    plt.figure()
9 c+ P7 b$ I/ E/ Q5 ]* c9 V    plt.plot(range(Iterations),best_dis)

' i; e1 O7 \2 M- f8 `, J# 4.1 块逆转变异策略运行效果展示
$ b$ `7 K2 C2 T- ~def opt1_main():
    time_start = time.time()
2 l6 K  X4 @, r7 a3 ?1 h& d7 M    pop = []    # 生成初代种群pop
    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
+ A; n1 Q6 Y2 ?6 i    best_dis= []
. R" Y; p2 o/ x  C+ [9 K; F. w    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
$ e' `0 |& m' l4 ]8 T: q# Z    for i in range(Iterations):  # 迭代N代
) ?; g5 B  v+ K/ h3 s& A6 e        pop = crossmuta(pop, CROSS_RATE, muta=3)
        fitness = getfitness(pop)
5 T$ A7 {4 ]: R        maxfitness = np.argmax(fitness)
1 d, f; c  M9 d        best_dis.append(distance(pop[maxfitness]))
        pop = select(pop, fitness)  # 选择生成新的种群

    time_end = time.time()
- Q3 k7 S+ T/ @# D    print_info(pop)
1 B5 Q0 M% ~( u    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
* X: K8 |; ]/ [, w0 q- h3 E5 M    plt.figure()
    plt.plot(range(Iterations),best_dis)

% s) J/ b% J- l. t) Eif __name__ == "__main__":

6 D/ V2 Q" `: S( k    ori_main()    # 原程序的主函数
* ?. ?. R% o/ `  ~7 r    opt1_main()   # 块逆转变异策略运行效果展示
( Y- A' u4 \) H/ w+ {    plt.show()
$ u, m2 N; L5 _    plt.close()

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

5 n7 U! e- {# w    # pop_size_test()       # POP_SIZE 种群规模参数测试
8 m- _% i1 B& P" I3 s    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
1 V! B& u- A% G/ K; T1 S    # muta_rate_test()      # MUTA_RATE 变异率参数测试
! G0 G5 F) U0 B  b5 Y    # cross_muta_test()     # 交叉率和变异率双参数测试

! J" p3 Z- l1 O. i7 ^
# d! Q$ w6 _' b7 G$ s1
/ I1 O7 t( @& p1 c0 U2
3
4
8 h1 f; _0 x6 J3 q5
! g( P  F+ k4 f/ ]+ O6
7
8
9
10
11
. \; |8 `1 I+ U6 M+ H' ^12
. ?& r# y" q2 k$ }. ~& w" X  [13
14
15
+ o4 U/ B: V! x( h) d16
17
18
19
( {; i( i) E0 p6 y" x20
* J. a) X- |1 \+ y  K+ N21
* g8 Z8 [: v. q, [4 o6 [4 D22
  k3 B6 R' @3 z- H( m0 G6 |% y/ c& b23
, N. G# L% ?9 `7 \: A1 X24
% r( O9 Z0 A2 ^25
* y# P% J' U) @- _; r! X26
4 ~5 ]4 s2 r# F( V! `: \7 r27
- Z! s$ ?+ X  Q& B5 N( y28
/ l  t. G/ @3 _6 \29
1 i7 ]  K! F! o' j30
9 C8 R0 Q5 ~9 I: C31
32
33
34
! Q5 n, \" ~, O' z0 i# }35
36
. f3 Y" X( v& O# h# z" P0 h37
. D" {, \% D3 V% Y0 d38
39
. Z* f; z' M7 ~% N40
41
42
- L5 t( J$ p( w/ N" U4 d43
44
45
( F; q8 J$ ^( W- @46
, x/ n% r1 u( M9 w47
5 M  f; c& T9 y/ ^48
  F0 m9 Y8 K. H49
50
# x# C0 X0 O. I! E  Z( _- ?2 P51
52
53
54
" I2 |1 U4 H6 E2 `1 S( V2 a55
56
57
# f4 `" Z$ _5 K7 K58
( i, o6 H0 D  |. B9 x, J' y. ]# s59
/ F* B+ G' ?& G60
61
6 Q# }, r; c  N) M& d% }( h) ]2 h+ D62
63
64
( ?5 C5 U2 N3 ~. [1 ?65
- v( n9 c1 p/ K3 b( u- B. a% E66
67
68
69
1 d+ ~1 {, h  H. @' i; ]5 Q. u70
. u$ J5 m# Y5 s; i  {- s+ }71
* Q+ D( Q/ N, U. ~& o- w72
  g$ e* }+ `: D4 v; w' j3 j( x73
8 U7 L8 d1 C7 L$ d74
75
" S0 J. U* E+ R( l1 z6 y. T! h76
77
78
8 {1 ]8 ~  V7 r79
80
! }9 U4 P2 x, W81
6 Y8 W; r3 j3 N, J6 I  F82
) `( P$ L0 e2 ]; }83
84
* U2 ^, K# D* H85
6 c4 o* ^! H3 F% J. F86
  e. f; s$ Z) x/ H+ v2 i- ^7 Z87
/ ~: h8 K. P+ @& g' ^88
89
9 z+ ~2 n# g# F4 p( d90
91
0 A& g4 m* M4 U/ a92
  Z) S( a9 W  z8 X: m93
$ f- e  ~. u( a( u94
95
96
) y. w; q8 |3 i: G0 a6 a6 Y97
98
99
* a# b* \) ~6 s# V# F( r/ L5 B100
! w& P9 e! _% {# j101
102
103
) e  ?4 H4 y9 G" H& _3 n$ A8 t9 [104
0 @3 `/ l; N3 ]105
106
107
0 D9 M* |. w  o# w108
+ w9 F# J7 o& u; W109
110
111
112
9 C, m; Z# I. N& Q6 ?/ p113
1 Z' W$ h5 y/ [/ d) ^" b114
115
7 K9 x) ?- O! F" i* n116
: ]: W; Z( x  C( y9 b+ I$ q) a117
5 {  n$ E* j6 e2 _118
) H' P. U/ _+ y1 i" n& P: l* k119
120
2 u; r( i; ?5 S2 B+ @121
122
% K& v9 @) L7 G123
124
) r9 e; r, ~. P7 R125
9 _3 ?" g, @, Y% L126
$ @) @& Z, H0 R& C. B! |5 f127
" n6 h. t; E& G# |" |7 @128
129
130
2 h. }0 g, I" y+ h131
, g% O4 n6 [2 G# ^8 {% V# C132
+ g7 r% E$ ~% ?6 M. x9 n133
134
135
136
( K0 n; m# |8 G9 y$ J( d137
138
139
( E1 y9 r- A" \; s0 C. W9 ^# z140
' S$ ^, ~: |; T141
/ q3 I! N- [3 W, ?0 b4 m, K( I142
# J8 W0 `* L+ e# W2 P6 ?143
144
! J3 O: t! V" @1 V8 s$ x+ M) U145
146
6 e; t" {/ j, ~147
148
8 i) i4 ~1 i1 W7 _1 H% H0 y149
150
' u& y- y- M% y) u151
152
153
. Z, W' e2 d9 f154
155
156
157
6 e+ |3 E& c) q( T158
/ j4 }* n. e" n( Z3 F159
160
161
162
163
164
165
166
( `" L1 a; c6 f167
) c" U* H* t* ?% S- c168
169
; W. z- k8 ]  |9 [/ C) a7 G" u170
171
$ m2 k3 G1 B! C172
4 r( R  O7 ^% |' ?, [173
174
175
176
% Q- a8 {7 g% [, Q+ i/ p177
# g3 |6 T1 p- |2 q178
5 \' Y) }4 S6 q8 q# V179
180
: ?0 u+ b6 @; W181
3 Q2 y# S8 a' j' p) ?182
183
184
( O( s$ l% ?; N( T$ L' L185
  ~4 `( ]. q8 k8 I7 P186
+ G' o) f0 P/ Q9 l: z9 H187
% N( b6 I3 H) m- x# j' k188
189
' Q% P  w; g* Y$ w% ]% i6 z190
191
" Y- A6 O" f+ e192
193
0 d+ `1 f, I0 b) k* s194
195
196
7 ^9 h5 U( j3 R197
198
+ q& ]& \8 n' Y5 ^5 j199
200
201
- n3 W1 _) [/ N$ F# N7 C% d2 y$ G202
5 ~- g/ P. I, a+ y" F2 L8 u203
204
* ]: v& a, l; {& ~$ I3 K205
2 G* s9 n7 u( |  o. u# O3 ~$ j- \1 \206
* N" |, u* h7 g/ e# j7 b8 A2 _207
: [& ~3 T" I- d) C' N208
209
- F( S( o  s6 ^* \+ Q210
# M, t  L% w7 s  e2 r# Q; G3 F$ M( Z211
212
& s+ v! s8 F" R5 o5 s213
# E& C6 h, {7 T1 m4 J+ v2 e214
215
, k5 m( F. d1 v* T& v) @2 L1 F/ x8 V216
2 r* P' |9 [: a  q- j) L9 o+ T217
7 h# W; P9 d. A  ^4 U218
6 v, B5 Z4 T2 a( J( D  U% v219
9 |2 ]* g' V4 w: d/ q- A& d220
1 b. t: m: n  Z2 F& d, n* W* b, S221
222
" N1 ?+ I( q; }5 j7 C& x223
224
225
226
; `5 B& B* O  i% N227
) J, }' I. k! x7 `7 ?- ^228
7 \+ S6 U* x5 C5 ?% T% F1 x6 g4 j229
. M$ _& G/ o1 d8 g& ~230
231
) _, S& D, b3 h. a: Z7 {( ?232
  n# G2 d# i* }- v0 |233
. a2 u7 K% L6 v234
6 U* z  e7 a' a) H1 a9 G2 w235
- @- a, f/ @5 `0 {0 p5 i$ H1 a5 G) L236
237
* p% U  J  R# X" F238
239
240
% g. C* o1 u$ s; m0 l241
" Y9 x" ]2 d/ M* F242
. j; x; V7 @+ x; W5 K" Y% x# C- [! n243
2 ^1 O3 a- t4 `+ A  v, D+ y244
245
246
  i  c/ H  H; n! _- ]5 i247
% N! T5 A/ }: \248
249
250
251
252
+ J% l1 _5 I; B253
7 m$ f+ U; E4 c7 _254
9 g& B+ Z" G( D. M5 R& D255
256
257
% T$ C) y' V6 s. J; y. ~258
259
% O" v4 D# c! V$ z& U0 [260
261
262
263
264
* ]0 A0 K2 }2 f$ z265
8 m& O6 P7 I7 K/ g1 [: o) W- ?266
& k/ X& N5 \% i267
, a- G; }' n! T4 _268
7 r7 T7 g, n  c  }8 B269
8 M( c' [3 b; q6 D) n& s/ M( ~" T270
6 q/ p# U' m# B! S271
272
# z# t  G$ j' }0 \; T. B- U273
* ]" }$ C, ]& S, Y% ?# w274
275
3 @" Y! e" U8 v8 B; o6 r+ @276
6 t" j3 [. ^" _- X277
278
279
( V8 n- @2 O, S; e4 t& k280
- G/ T% i9 m8 h+ t* U281
282
$ ~6 D3 ~/ H( W/ B$ C% @" W' F( A283
284
% S) Z4 N' o/ ^9 o, ]0 X; C285
286
287
* \! r  X% ]6 Y5 d" W) k4 G288
289
( e" k; t) }1 ]7 n7 d( m290
291
1 y, |6 |& e! h1 A292
293
) y+ [. B) s1 a: S1 Q2 l294
( E9 K9 g" c7 W" U! V295
# }6 ?9 {7 K9 D/ j! e4 z: n* _296
297
$ g% H% }+ O8 x" U# z2 L2 E, F( x298
299
$ v. \0 e' W3 B3 u6 h4 e- q300
; X, F7 s5 k+ T3 \301
* ^6 d$ n0 p: \/ l3 P- O" T302
303
304
9 r7 Q! J; M: n305
0 t7 u9 a* R0 w- P+ ^) v6 N& J306
307
4 p' p4 e7 q8 V$ i( D/ f: w) N  O( ~  H308
309
310
311
1 z3 X* g# q  k- h- d* @5 Q312
. [/ H' B9 k, z4 ^" v. V; G313
314
' `& N/ Q4 y; I- N) V2 V315
316
317
318
319
320
321
322
323
324
, n; k& g% j. `8 b& }1 U. }5 s) G325
8 ^; f# Y2 z/ q& u326
% T& t  r! z: Y3 M327
. S3 t4 O! }% L328
329
# C* u- D1 @# A( \) ]9 G: q330
331
2 S$ M. u! e, x1 M! n332
  X% n9 [# c- x333
9 y  m8 A" j" k0 d6 h334
335
4 j( ^7 W# b1 G1 @336
$ S1 m/ c/ |- P, ^% x& W0 g) d337
338
- i, f* ?2 A! x* e. Z/ n339
5 i: F: L9 h1 F1 m8 K4 A340
& \$ d" H( G. T( ]2 k+ `& V6 s341
% j4 x% G, W- a" T342
343
344
345
346
( m* o, H6 U" W% p347
$ _7 h/ v7 A5 L7 q9 h348
$ W# y  F1 `* A. }8 Z; e9 P7 g+ A349
* j$ ~, W( I7 Y( u350
351
9 ?; k( @; q/ P* E' @- I352
/ O* e8 ]" g0 |. m: `, w4 A353
$ [9 {! J+ @: p354
" }8 Z3 R& _3 d7 O2 L* u0 ~" a355
9 Z- I9 r* ?& t# S. I7 w356
357
358
359
" ~, d. e- X+ d: A% f360
361
9 A( |# W0 o. s& J! Y362
4 E1 t- C, v- }% h5 Y, s$ n363
6 G& q) G$ y- T364
9 E0 c  S3 P( x9 M0 G" \365
/ M- q( ^) y7 U/ J' Q% z( C' l366
7 i  p' ^0 ]! ?  A0 T5 }$ V; M5 j' Q367
368
$ g- i  B" U9 q( ]0 o7 y+ N369
370
371
372
8 W6 C2 c5 J+ [  ?) A- |373
374
375
376
. Q6 B. O) m4 }377
* p. @, g9 B3 K. K6 I7 m  x378
379
380
1 v# @7 T; x% A' |8 }- r5 {9 M381
# A" J4 i1 p8 b4 ]+ t# ?) [4 X382
( b6 S% Y" s1 @4 [$ c( V. O383
384
: \$ P$ e: D% K+ r- e- A385
386
, s$ Y3 @$ d/ i; u; ?+ o# y. f% L0 z7 A387
388
389
/ p' d( @# ], j390
; J% p0 o7 v2 v( k+ H3 w391
392
4 s  O8 T; J- D4 g393
, i. Y+ o2 v/ G, ?4 L& A394
395
  M8 X& q" N# o396
- N5 f6 k1 x; Z2 p5 \) o# Q397
398
399
" m/ j' u" q: z400
401
% O8 |. S3 q1 o6 y402
  S& j' n& M' Q" Z0 s403
404
405
406
: t" E& H' f* p407
408
409
- N4 E/ E6 Z) ]3 I4 z% t1 y5 v410
411
- d4 ~: Y/ Z* z& p, ^' P1 a412
413
! `* c- q$ G6 y414
$ ]+ F. O9 t( S. D* Z+ p# ^415
  s/ w; R7 }, b# {5 z; E8 o9 J# l416
' b( q% W6 l+ B. G9 ~417
418
419
420
% ^' t8 L, Y8 |421
422
) |' k" w6 q/ X" s423
8 r! c2 }6 _/ `6 E424
( A( d2 S' J. r425
$ U) a, G+ F: N5 D; |$ ?  ^0 n426
427
428
429
430
431
432
# X* z8 m& G, P: p% ?+ Y433
# ?+ P" h. _7 z: l# o434
435
436
9 y: c/ _" a) C' b6 C437
438
) i% V3 K. ]$ h; j: k439
440
4 N# Q" S# x% j441
8 L( l, c+ o  f2 o442
3 |; |7 E6 o1 m# P443
# @2 p2 t. {; o8 d) q3 V8 t0 ?6 f444
445
446
- ~7 s  |+ w# v9 f( i0 i0 m0 O* O447
448
449
# Q! A1 Q+ C4 y; u$ _450
( r9 y. l: Z8 z" V8 T451
452
453
454
455
456
457
458
  L* ?% O2 C' C8 y: ?" u459
460
461
# O1 q0 o) `" m( x$ x462
463
464
; C8 V7 G6 m9 E3 w0 ^3 `465
7 ~) S' T+ b+ n( q* v( W' q4 p466
- c+ G+ J( d( z! m4 X467
468
" |4 Y# U4 y( Z8 A8 Z469

3 \; }" K! C$ J8 W: F7 O$ g
) d+ d/ {4 F3 C' U  ?
2 [7 \" L+ [* b/ u( M' H
* f, A* \2 C. O; g


; G! _" F& x. k/ ?; `

& }+ o7 t+ s; [( A( v1 K
+ B; V- }7 N$ }1 d
. w7 j2 h( c- S- n8 T, g

! R& s( ?+ j/ `+ x, P% a2 r
+ f( O) k. H, U; P: n



# r% }; J" G. }; e4 b
4 T8 ?& i$ C4 V$ C# `7 w5 c$ z! w
4 q/ J0 J. B; k) g/ g& U: z/ N
2 ^, J* n$ E. P' Y& T0 }$ ?+ v" h



0 H9 N1 S6 ]6 x) o+ M
" b( N& p4 M# S. H
# F5 e8 ^, |; k0 b  J————————————————
版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 w% }9 d" o9 W- R6 V) _) f6 I' ]9 B原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212

4 Y- q; E3 n, _1 U; w
0 {" F2 c: N' F3 P. `  j

/ V# m8 w2 S" d5 p7 W