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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
目录
人工智能第四次实验报告 1
遗传算法求TSP问题 1
一 、问题背景 1
1.1 遗传算法简介 1
4 J; a1 Z* D- m* r; A: ~1.2 遗传算法基本要素 2
* k: [' m' _  g! }- n2 N6 {+ B9 r$ c1.3 遗传算法一般步骤 2
二 、程序说明 3
2.3 选择初始群体 4
2.4 适应度函数 4
3 e9 c0 N4 K4 l& \: N+ W4 m$ G2.5 遗传操作 4
! n0 B, z2 A2 C8 z/ t6 ]* w1 c9 \2.6 迭代过程 4
三 、程序测试 5
3.1 求解不同规模的TSP问题的算法性能 5
3.2 种群规模对算法结果的影响 5
2 n; p! B) u0 @* l: ~3.3 交叉概率对算法结果的影响 6
1 R6 c' u" {) ]# ]1 [% p3.4 变异概率对算法结果的影响 7
3.5 交叉概率和变异概率对算法结果的影响 7
1 z5 [* x, ]$ S' L# y4 S& B5 f四 、算法改进 8
2 b+ M( C. B8 {4.1 块逆转变异策略 8
4.2 锦标赛选择法 9
* ]) N$ ~+ K; o  \: h9 [五 、实验总结 10
一 、问题背景
9 q9 L# ^' t9 y1 [0 {: M# l' J1.1遗传算法简介
0 O9 \% n6 t0 a遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
% D$ s/ l! S' c, P+ ^3 t+ }  v, P; f1.2遗传算法基本要素
" J4 H+ \0 L( |5 b4 U1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
2.设定初始群体：
1.启发 / 非启发给定一组解作为初始群体
2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
4.设定遗传操作：
$ `& D" i( |2 J. S! J. a1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
: y1 L4 u  d: s2.交叉：两个个体的基因进行交叉重组来获得新个体
0 P. }; Q! v- z' w4 l* B3.变异：随机变动个体串基因座上的某些基因
& Y1 B. A& Z2 Y; W6 k5.设定控制参数：例如变异概率、交叉程度、迭代上限等。

import numpy as np
. @# H- ^8 e, `6 ]import random
3 D7 l" y! E2 q& x/ \import matplotlib.pyplot as plt
) U) g4 X! h* F( ?' P6 h3 limport copy
1 u  v% U  i$ O0 Zimport time

3 M1 ?+ D5 D, W# Ffrom matplotlib.ticker import MultipleLocator
7 b$ V( {' K% W; b+ s( ~$ Q& T; \from scipy.interpolate import interpolate

  L( g1 a" x5 X  w& {: ACITY_NUM = 20
City_Map = 100 * np.random.rand(CITY_NUM, 2)
- e  f/ b( _, L
DNA_SIZE = CITY_NUM     #编码长度
5 w3 _; H8 t+ n% r3 U/ SPOP_SIZE = 100          #种群大小
CROSS_RATE = 0.6        #交叉率
, \) i+ {: ?$ D/ AMUTA_RATE = 0.2         #变异率
Iterations = 1000       #迭代次数

3 x$ h) `. o/ n8 Q9 z3 R# 根据DNA的路线计算距离
2 N- Z- S/ k) k5 o' Ndef distance(DNA):
    dis = 0
) g( w  N9 z1 M7 Y  V. T    temp = City_Map[DNA[0]]
7 I' R8 Q  S) Z. w' L    for i in DNA[1:]:
        dis = dis + ((City_Map[0]-temp[0])**2+(City_Map[1]-temp[1])**2)**0.5
! c( w% t: T" p0 ]        temp = City_Map
9 d5 v/ [2 g$ r    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5
) Z1 ]- m1 F4 F; d
# 计算种群适应度，这里适应度用距离的倒数表示
# p3 X  L* s: R2 Idef getfitness(pop):
0 i) c. S4 v% s$ z* y    temp = []
3 F5 I( y2 u; c1 {% I+ w    for i in range(len(pop)):
        temp.append(1/(distance(pop)))
    return temp-np.min(temp) + 0.000001

# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
: w+ ?7 o: I/ }: Z! U" tdef select(pop, fitness):
    s = fitness.sum()
1 C0 x$ m6 D9 W2 w    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
( t1 `1 `6 C( U5 x7 ?$ C: ?: b    p = []
' t* M8 \. c" o  z  T, N    for i in temp:
        p.append(pop)
# h- {4 \# `. ?$ h    return p
# Y& G( x! p$ S0 ?  K
& |4 |) t$ o, K6 ]+ n# 4.2 选择：锦标赛选择法
def selectII(pop, fitness):
    p = []
/ S5 N# O1 ]) k' c+ Q    for i in range(POP_SIZE):
* J5 j7 h6 _5 w        temp1 = np.random.randint(POP_SIZE)
        temp2 = np.random.randint(POP_SIZE)
        DNA1 = pop[temp1]
* ?6 M; w* v& Z! H6 K        DNA2 = pop[temp2]
        if fitness[temp1] > fitness[temp2]:
            p.append(DNA1)
$ v2 P8 B1 j9 ~/ A        else:
$ i) v6 M% i( R4 I: P+ O3 N            p.append(DNA2)
    return p

# 变异：选择两个位置互换其中的城市编号
5 L8 C* o; P& ^2 r6 e# P$ _def mutation(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
        mutate_point1 = np.random.randint(0, DNA_SIZE)
$ x7 k. j  O% C2 d* U; R        mutate_point2 = np.random.randint(0,DNA_SIZE)
        while(mutate_point1 == mutate_point2):
& [7 H- H$ x2 g& w6 }            mutate_point2 = np.random.randint(0,DNA_SIZE)
/ M4 U' s# N' o5 `% b3 u- p9 O        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]

& |4 k0 h4 Q/ C& R# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
. M6 A# {  G0 E* ?) Sdef mutationII(DNA, MUTA_RATE):
* V, r! |2 j( S0 D* e6 {    if np.random.rand() < MUTA_RATE:
7 @( L6 r0 [; _' W        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0, DNA_SIZE)
! s( C0 l* Q5 X0 R" f        while (mutate_point1 == mutate_point2):
4 E# ]0 S; D, ?3 m; i6 T" g0 Y# Y( W            mutate_point2 = np.random.randint(0, DNA_SIZE)
        if(mutate_point1 > mutate_point2):
            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
! z. z' ?5 R, g4 S$ y8 R        DNA[mutate_point1:mutate_point2].reverse()
9 w' t! X  N6 `  i5 N
3 ~9 M/ l; o+ @4 c7 r4 h# 4.1 变异：调用 I 和 II
  i9 N5 E0 V6 M$ Cdef mutationIII(DNA, MUTA_RATE):
    mutationII(DNA, MUTA_RATE)
. a/ f- ?' b% }# _# r4 _+ X2 l1 f    mutation(DNA, MUTA_RATE)
% M: I3 }5 u8 \# f. W- B
# 交叉变异
. }) t" M' P7 C* k/ I4 _& M# muta = 1时变异调用 mutation；
  z" E0 _8 Q" ]# ?# muta = 2时变异调用 mutationII；
! _, ]/ }8 u3 e- s3 A+ [# muta = 3时变异调用 mutationIII
def crossmuta(pop, CROSS_RATE, muta=1):
9 Y3 l3 |% g6 [- e+ s6 P7 |" Z    new_pop = []
    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
        n = np.random.rand()
( W$ b; G+ l1 z$ U" s        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
            temp = pop.copy()
            new_pop.append(temp)
8 L/ v8 y% t4 S7 P6 v- v        # 小于交叉概率时发生变异
$ V( j" R- ~: W& m1 Z  _$ o1 ?1 s) B" z4 f        if n < CROSS_RATE:
            # 选取种群中另一个个体进行交叉
            list1 = pop.copy()
            list2 = pop[np.random.randint(POP_SIZE)].copy()
            status = True
            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
1 m0 ]/ e/ l' Y" L            while status:
5 l" n0 i, o# W- g2 [6 d                k1 = random.randint(0, len(list1) - 1)
7 `0 G  A2 j9 w/ ?1 H# R                k2 = random.randint(0, len(list2) - 1)
                if k1 < k2:
                    status = False
; N: n$ b# |/ P- o3 f" a3 [
& p! P  V9 B' _1 I: Q/ [            k11 = k1

            # 两个DNA中待交叉的片段
            fragment1 = list1[k1: k2]
            fragment2 = list2[k1: k2]

            # 交换片段后的DNA
7 K: m8 e/ [1 j+ R" P, V& l2 Y$ L            list1[k1: k2] = fragment2
            list2[k1: k2] = fragment1
, \* Y- w; |/ Y7 x, {6 f" I
            # left1就是 list1除去交叉片段后剩下的DNA片段
. u6 N2 N: I. e# o            del list1[k1: k2]
            left1 = list1

            offspring1 = []
            for pos in left1:
. V/ X/ p: S: W; P( ^                # 如果 left1 中有与待插入的新片段相同的城市编号
/ ?( D! Z/ {: k& Y                if pos in fragment2:
, G; I/ @7 ^. j# P& \9 H                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
                    # 循环查找，直至这个城市编号不再待插入的片段中
                    pos = fragment1[fragment2.index(pos)]
5 H; |" G+ p! ]* p* ^+ B  s                    while pos in fragment2:
                        pos = fragment1[fragment2.index(pos)]
                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
                    offspring1.append(pos)
                    continue
                offspring1.append(pos)
            for i in range(0, len(fragment2)):
+ q2 J+ d2 x8 c" N. `* X                offspring1.insert(k11, fragment2)
                k11 += 1
0 C) }) X9 ]9 c8 V/ S% \            temp = offspring1.copy()
            # 根据 type 的值选择一种变异策略
. U1 M' \( \1 Z% X            if muta == 1:
; c7 ?1 b: g9 o' V8 I1 X  R0 i: X                mutation(temp, MUTA_RATE)
4 g7 d0 Q$ v( o7 D2 f; }$ [$ O            elif muta == 2:
7 r$ @* K) E$ {( C+ }+ ^                mutationII(temp, MUTA_RATE)
            elif muta == 3:
' |* O6 s& O9 i5 m' D( s                mutationIII(temp, MUTA_RATE)
4 ?" j6 G- q$ Z* u            # 把部分匹配交叉后形成的合法个体加入到下一代种群
+ e6 Z3 a1 [3 j5 P- m- F7 N: ~, R            new_pop.append(temp)

7 j; i  n! A1 n2 R  e6 D% Y" s    return new_pop

def print_info(pop):
    fitness = getfitness(pop)
    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
: ?8 o- o+ o3 s    print("最优的基因型：", pop[maxfitness])
    print("最短距离：",distance(pop[maxfitness]))
6 g1 A( `1 ]4 J; \: H0 B+ d' N% B0 b- {    # 按最优结果顺序把地图上的点加入到best_map列表中
    best_map = []
    for i in pop[maxfitness]:
. A6 e% Y, A. u( P; U. h2 t; Y        best_map.append(City_Map)
* i) a) D. y3 C$ K+ K: v6 a    best_map.append(City_Map[pop[maxfitness][0]])
( a$ B! `  D1 g9 w" Y    X = np.array((best_map))[:,0]
    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
5 ~2 P$ o$ d+ T3 H/ E    plt.figure()
    plt.rcParams['font.sans-serif'] = ['SimHei']
+ k5 @  f! l: [3 K1 Y$ W    plt.scatter(X,Y)
$ y; n$ A7 _# a! I2 t    for dot in range(len(X)-1):
        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
% ~! p& W9 ?8 r0 v" I+ s" n5 s3 W    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
4 L- u+ Q( @( j/ J: H. k5 A/ L; S    plt.plot(X,Y)
; }; {% u( P7 G' `0 p. [
# 3.2 种群规模对算法结果的影响
: a3 M) G5 m! Wdef pop_size_test():
2 d& Y; Z8 M! E    global POP_SIZE
0 Q" Y) L) B. f, w$ w5 N; o    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
, A  P6 z* `4 W1 c2 ]! K$ f0 j' `' h    b_list = []
    t_list = []
6 D8 k* T4 p  m9 w    for i in i_list:
        print(i)
        POP_SIZE = i
% r& u6 Q1 A5 S        time_cost = 0
9 z. e2 C9 t7 T: ^0 z        min_path = 0
        for j in range(ITE):
( C+ |3 f# l" d- i' g            time_start = time.time()
6 N3 W8 q3 U9 A2 m: f4 M) Z            ans = tsp_solve()
! D1 i1 f; k- E; x! f' h            min_path += min(ans)
( |. z+ N$ c3 T" m  X; p            time_end = time.time()
            time_cost += time_end - time_start
( p0 p2 Q5 P0 T# D! ]/ F! B
! D: N; g# C, K! N        b_list.append(min_path / ITE)
! L* N8 {. x1 Y; z0 K) y: }0 ?        t_list.append(time_cost / ITE)
8 @3 n" O$ E  D5 i6 ^( D    show_test_result(i_list, b_list, t_list, "POP_SIZE")
4 F' ?3 _" A" {7 B
0 `, ^* C0 l- v4 B2 p6 C# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
. p! O$ e/ z% a! A* z% X    global CROSS_RATE
) B  Y+ B, L. ~( k    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
    b_list = []
6 L% |# G8 L) \9 w% [4 Q# [    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
5 O* P/ X( J" W, \    for i in i_list:
        print(i)
6 r2 J& \* q  P1 `8 |/ ]        CROSS_RATE = 0.05 * i
        ii_list.append(CROSS_RATE)
. r9 @  Q" u4 i1 X- T        time_cost = 0
        min_path = 0
        for j in range(ITE):
            time_start = time.time()
            ans = tsp_solve()
( t8 i% J5 j/ v0 s7 w            min_path += min(ans)
            time_end = time.time()
* l( f% N! J5 Q* ]; `            time_cost += time_end - time_start
9 @' T% V* J, J* |( k
        b_list.append(min_path / ITE)
$ q$ l* f4 p2 o6 T: T3 G* W        t_list.append(time_cost / ITE)
2 E+ u. n2 b3 g# \0 w: D2 |2 ?    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")
( U# L7 @; `7 Q$ ?9 \7 i7 ?
# 3.4 变异概率对算法结果的影响
def muta_rate_test():
0 d: Y& x  U/ X4 T    global MUTA_RATE
8 V) x  }8 c6 P0 M" g- h    ITE = 3 # 每个值测试多次求平均数以降低随机误差
9 \3 A: t; J3 E    i_list = range(0, 21)
$ a4 V/ p2 R- b6 G    b_list = []
    t_list = []
6 p( r8 }4 t! W0 t* C4 m    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
        MUTA_RATE = 0.05 * i
        ii_list.append(MUTA_RATE)
2 Z( `& W7 a2 }0 X" ~9 J/ P        time_cost = 0
        min_path = 0
; }* `7 f: e6 y; B4 {0 z- q        for j in range(ITE):
            time_start = time.time()
- j5 u# d/ z# H* ]' N            ans = tsp_solve()
* L. T. u9 m2 ~3 V4 i5 f            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start
; [3 g: Y2 @$ ^4 L. S
        b_list.append(min_path / ITE)
0 `7 C/ R  z  t# Z( v  G        t_list.append(time_cost / ITE)
# @. [" b  @  d1 Q* V4 h  T    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")

7 q& B1 J4 D' I; m- G" ]& M( M# 3.5 交叉概率和变异概率对算法结果的影响
' @4 ]% T4 v- [def cross_muta_test():
3 ?& ^2 }# I' B: A" F    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)
    Z = np.zeros(shape=(11, 11))

    global MUTA_RATE
5 `' H( H; @2 V  j/ A    global CROSS_RATE
8 K! S6 ?0 G( S/ A    for i in range(11):
; ]! c# J4 |, \/ X$ F) O7 x        for j in range(11):
+ \3 F& ]: X  A$ T$ e: L            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
' K. E$ Q- Y6 N) }7 V! y8 o            MUTA_RATE = Y[0,j]
            ans = tsp_solve()
            Z[i, j] = min(ans)
* R/ E6 s( p* P# p2 |, J
2 \# `" h5 A" ]! f) Q6 K    ax = plt.axes(projection='3d')
& D% f- b9 R  @7 M    ax.plot_surface(X, Y, Z, rstride=1, cstride=1,cmap='rainbow', edgecolor='none')
    ax.set_xlabel("CROSS_RATE")
    ax.set_ylabel("MUTA_RATE")
    ax.set_zlabel("Shortest_Path")
* u; Y$ q$ H$ E2 r    ax.set_title('TSP')
) o# K/ ~8 A( D/ C1 W    plt.show()

' F) d) P1 M9 [, }& @# 3.2-3.4 生成参数测试结果的可视化图表
# r9 P9 U- [  ]6 B/ j- _def show_test_result(i_list, b_list, t_list, msg):
    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b')
    ax1.set_xlabel(msg)
( K! [$ x6 `5 ]1 ^    ax1.set_ylabel("Shortest Path")
4 I  |2 M' z" Q) b- G: p1 }
    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'r')
    ax2.set_xlabel(msg)
. P4 I8 I2 \; V    ax2.set_ylabel("Cost Time")
; K5 R  G4 F4 |) V6 n  L# ~7 s. z    plt.show()

# 求解TSP问题并返回最大值
" `8 [0 W- A3 H6 _, j/ b! X$ l# muta 指定变异方式，sel 指定选择方式
4 Q* c3 a* G* n, z* ?def tsp_solve(muta=1, sel=1):
    pop = []
6 x' x9 B4 w. K% Z6 S    li = list(range(DNA_SIZE))
3 e5 b' q; T# a; U; Q    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
! q! M$ N- Q) P$ F0 B        pop.append(l)
    best_dis = []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
3 g% A& i$ O5 q# Q6 f2 B5 A8 n        pop = crossmuta(pop, CROSS_RATE, muta=muta)
        fitness = getfitness(pop)
1 }4 r; [6 z% u. G! I        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
8 d' e8 g' g" A( C5 A; F8 z. j# |        if sel == 1:
            pop = select(pop, fitness)  # 选择生成新的种群
" |7 y) A1 v' o' U/ u1 G        elif sel == 2:
6 F  }5 k" J% {0 I& \2 a3 s  m            pop = selectII(pop, fitness)  # 选择生成新的种群
4 K8 f$ H; o( N) P. z5 |1 d. d
    return best_dis
' L. Q. _6 n$ q; ?7 X
# O- m6 y' d. I- ^# 4.1 块逆转变异策略对比测试
def opt1_test():
    ITE = 20    # 测试次数
    i_list = range(ITE)
1 }; J  n. u4 a- s6 B) U$ D    b_list = []     # 每次求出的最短路径
0 V# t4 d1 H* {6 |4 ]6 M! R    t_list = []     # 每次求解的耗时
* z' F; h' v+ j' g    b_listII = []
    t_listII = []
    b_listIII = []
( x7 c) x0 R4 U    t_listIII = []
- `3 x) x! M. Y0 k, Z
    for i in i_list:
        print(i)
        # I. 原两点互换异策略
* {, s2 s( ?# w5 i' f9 m        time_start = time.time()
0 o; G1 N# h, R; Z/ p        b_list.append(min(tsp_solve(muta=1)))
6 n$ \$ S2 `3 U* q: ^0 \! z2 ~4 Z9 P0 O        time_end = time.time()
  i: H" ^2 z# T        t_list.append(time_end - time_start)
        # II. 块逆转变异策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(muta=2)))
1 p& o: z! t& o) x9 m  ^+ ]9 O        time_endII = time.time()
0 J, ~$ H" t& ?& l! ]1 g! V  {& {/ k/ F        t_listII.append(time_endII - time_startII)
        # III. 同时使用上述两种编译策略
        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(muta=3)))
        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
$ w: I6 q3 E  x2 ~
    # 做排序处理，方便比较
    b_list.sort()
    t_list.sort()
1 \( t9 J9 ?) A3 C    b_listII.sort()
    t_listII.sort()
6 m; j& p8 h; y/ u/ B    b_listIII.sort()
    t_listIII.sort()
* E7 M. Q2 ]$ V8 i
    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
) x' }3 k' T. }7 n% X9 `    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
- n! f) E2 y2 [    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")
    ax2.plot(i_list, t_listII, 'r', label="Block-reversal")
. p; g% i" [) q. X5 B! E& D    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
  l2 w- M8 V1 @1 w    ax2.set_ylabel("Cost Time")
- g! t4 j( x2 [4 x9 l) [    plt.legend()
* d$ |( Y9 v7 L6 T# K# l  _    plt.show()
4 O( l7 F* i, d- f' U/ l5 h
' E4 l, n, S8 p' Z2 k# 4.2 锦标赛选择策略对比测试
8 Z, Z% }; W! }8 ~def opt2_test():
6 Q/ Y( Y: T: d& B3 N" k8 D    ITE = 20  # 测试次数
    i_list = range(ITE)
    b_list = []  # 每次求出的最短路径
    t_list = []  # 每次求解的耗时
    b_listII = []
    t_listII = []
2 }$ e; N: y* W* q: U) e    b_listIII = []
- V& s1 |4 R( M) u# w    t_listIII = []
$ h; c# ]" Y7 G& Q  R
    for i in i_list:
        print(i)
$ T5 d3 U- n( {: h        # I. 原赌轮盘选择策略
/ t1 S" g( |* S6 ]0 D        time_start = time.time()
        b_list.append(min(tsp_solve(sel=1)))
3 p$ K! z( }1 f5 @        time_end = time.time()
" v. _9 N4 n9 }' W3 X" z% g* a8 S) C        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
) q: U5 K! B1 ]        time_startII = time.time()
" n8 @  j! ?+ N* ~        b_listII.append(min(tsp_solve(sel=2)))
7 k" x8 f5 a! E; T& K        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
  w( u0 a% C/ }  Y, F        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
        time_startIII = time.time()
% J6 U: w5 C, T5 a) _$ `        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
3 |7 j- j! h2 c7 t0 S        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)
3 y2 W1 P9 H. T- h; {, m3 C
    # 做排序处理，方便比较
    b_list.sort()
2 u5 t' g: |5 S5 O' v6 n    t_list.sort()
    b_listII.sort()
1 R' n6 B. V+ K; t3 t    t_listII.sort()
* A; G7 M6 v6 m" P2 ^+ G, y0 P, B    b_listIII.sort()
    t_listIII.sort()
: s( u/ ]+ d& T
8 y' @! k7 T- z' I( U" t2 _4 [+ m9 o    ax1 = plt.subplot(121)
$ G- z, `% ]0 r6 Q    ax1.plot(i_list, b_list, 'b', label="Origin")
, L7 p) p2 S7 L- Q' O4 J/ b    ax1.plot(i_list, b_listII, 'r', label="Tournament")
3 K8 `; s4 o, K' g    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")
    ax2.plot(i_list, t_listII, 'r', label="Tournament")
) i3 N! @0 Q5 |/ j! P- a5 Z0 s5 Q/ X    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax2.set_ylabel("Cost Time")
    plt.legend()
) g' i8 \0 {+ W# M3 s1 y; f    plt.show()

# c& [: T0 [9 ~$ Q# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
def ori_main():
. C5 H- R0 A7 W8 _+ N! l: e    time_start = time.time()
    pop = [] # 生成初代种群pop
    li = list(range(DNA_SIZE))
; f  C4 h, e  n2 T- l( V( ~    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
        pop.append(l)
    best_dis= []
* q2 ~. t& U) M9 s; e    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
' m/ i% b8 J  i8 L. B+ r    for i in range(Iterations):  # 迭代N代
& T1 E& a) B. ~        pop = crossmuta(pop, CROSS_RATE)
        fitness = getfitness(pop)
2 \% P. U  t' s) H  }. G) r        maxfitness = np.argmax(fitness)
8 H9 l6 J  i& a3 Q) E2 C        best_dis.append(distance(pop[maxfitness]))
/ Z! N* Q& J( R/ |+ A* u# V7 F        pop = select(pop, fitness)  # 选择生成新的种群

9 o! a/ ?* S/ s# F    time_end = time.time()
  s! u8 @, k) M( f8 D  D    print_info(pop)
    print('逐代的最小距离：',best_dis)
! j' j' l/ r7 @, J3 S' p    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
0 M- z5 W6 v1 _* a" F6 u+ D    plt.plot(range(Iterations),best_dis)
# o& p: p. I8 ^% z
# 4.1 块逆转变异策略运行效果展示
def opt1_main():
    time_start = time.time()
    pop = []    # 生成初代种群pop
' B0 ]1 B3 N) r' V    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
: k- @' Z/ V. N7 H3 {        l = li.copy()
        pop.append(l)
    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
. X4 R2 r+ A" Z0 f        pop = crossmuta(pop, CROSS_RATE, muta=3)
        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
3 t/ k- ?: b8 E: @        best_dis.append(distance(pop[maxfitness]))
        pop = select(pop, fitness)  # 选择生成新的种群

    time_end = time.time()
9 @7 d4 t+ _1 M/ b" t! @    print_info(pop)
    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
0 @$ H, d  [# S& i! V0 x    plt.figure()
+ \2 _+ ]9 O* A& L, U* y, @6 i8 D( P    plt.plot(range(Iterations),best_dis)

5 j- ?5 Z- V" k% h4 sif __name__ == "__main__":

    ori_main()    # 原程序的主函数
9 G" g* V; F- K3 D# c& E    opt1_main()   # 块逆转变异策略运行效果展示
    plt.show()
    plt.close()

    # opt1_test()   # 块逆转变异策略对比测试
4 n; F4 R, g. T* T5 i    # opt2_test()   # 锦标赛选择策略对比测试
+ C  x1 ^% T% \3 u
    # pop_size_test()       # POP_SIZE 种群规模参数测试
+ A' q4 j  P# C    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
  x8 A( ?% X+ r2 L0 u; K0 l    # muta_rate_test()      # MUTA_RATE 变异率参数测试
    # cross_muta_test()     # 交叉率和变异率双参数测试

, n( D) U. |! ]! B0 ^
1
2
3
4
5
6
9 E" h( N3 |' M1 D7
8
- B$ P" A* A+ Q# q& w- U9
% h! v6 H- S& ~8 u1 _% U  k. ?10
11
12
6 z1 r8 c/ W. n4 ]0 v4 ^  v% ^13
* w/ V; W, L9 M/ a7 P# t5 M14
7 P4 w: }# ?5 g' h) l4 q15
1 u7 }5 i9 j& K- d( D" w$ ?16
17
* K  K* ^: D! W0 }. J3 y18
& ~: E; M; ]- P( s19
4 j3 @: L4 q. `. W4 ]20
+ |( u, a) {+ L6 l9 ~21
22
23
24
25
26
3 i9 Z7 {1 _* e, Y- b) j27
28
29
% J3 v1 B5 y$ m3 G3 q2 _6 \30
3 A! ]9 n* J/ q; d$ u6 u31
0 Y& @8 c2 l+ l$ ?% q! n! \32
8 ]# X1 K2 G) X# `% P1 [& }8 e' a33
34
& v/ t2 l, A, g0 `/ X35
36
4 n" Z! D. h9 A% K- o3 A( Z7 p37
! L8 u' b: E" J; _& _38
39
40
4 ]( ]$ Q7 D+ n, P41
42
, E: q3 b- N" [. a# ?43
# J9 {. c! c6 R4 c# v4 W+ F44
45
, C: f# i- R8 i5 ?+ B! J46
47
/ p1 s, v9 E1 L" ]$ q; v48
49
50
51
52
0 T# i6 h, }/ n- D, v8 U53
54
55
0 S( Q( v' e! }56
) w# t8 [- G; J57
58
59
60
61
62
# ^' T1 O- E$ n/ L$ \* D# T63
64
65
66
67
7 f. ]; S! p) h, ?; i: s68
69
! q# [) n) u* ~70
71
% Z) g5 y+ D! U- h( O- r2 P72
73
74
75
76
  g9 L5 |/ @. J. t2 V5 Z% U77
78
. H% J2 m4 r+ C8 o5 j  H79
80
81
: i7 y1 A+ U9 U7 S, m, E0 e/ T82
" J; X* e( L& t" U% y6 a83
84
7 K2 X7 a3 H/ @$ ?; R85
86
87
% p& a% n  A# d& U( b88
0 p% T- j+ n, s( N0 f* t6 s89
4 U, }+ s1 N: ^" y# ?: O90
6 E% S, R8 N% k91
5 \2 I, V* q, N92
9 K" F& U6 n+ G; t# D, P93
% K; d( @0 ?5 }/ r& j) N94
95
  Y( c( r6 X1 z2 Y96
97
98
99
100
6 p$ |, Y; r2 J8 a" Z9 _101
) N9 b% H' G7 b; C9 V/ n  n2 k- `5 R102
103
6 u4 m! Y. j1 i6 ^4 i! {0 V104
105
106
107
108
109
110
111
* ~2 p. \7 f. q: ~& w9 _+ o112
+ r, t5 ?1 n: a  c113
- D0 @) M1 H0 c/ K  G$ s114
3 C9 U$ q& p9 B$ `- y* u6 B  _5 F$ n" c115
: R5 o1 A! _5 _+ i! v# ^116
& _( t; B$ C" K# K+ T& A8 r117
118
- v' U  v* q% ~) v1 p119
1 X7 f5 T/ V' B9 n: [120
121
122
( K- r, h3 A# o* g$ D8 o$ g123
124
+ D3 m' @9 ]7 r0 `, D+ `125
126
6 s" D6 @5 s) \/ {' D127
6 i; u# l9 w7 |/ i1 Z6 d128
129
* {2 A0 ~5 ?4 c& W130
" r( z# X" P9 ]) H7 R4 w5 _131
132
133
! ~4 D$ m; C2 i1 ~6 O: ], V134
! Y2 H' b3 J1 N5 A/ a. O135
136
137
! X0 O, a3 v& l) F' ]8 o138
139
" q# u+ h4 j/ I' N5 a5 {8 O140
+ Q. o1 C9 I7 q4 ^0 ]2 d141
) b8 u- Z7 v5 J7 P% Q142
143
144
/ B& E+ L  l7 K) s/ z# y145
146
$ W2 t( b3 }/ m147
' x/ v( J8 B4 j  _  E148
* F5 u: H% O% e0 V( F+ c149
6 k/ V' q  ^. ~1 ^% U4 b150
1 h8 [1 M7 Z6 K4 |6 v# S5 f/ _4 h151
152
153
3 J" o$ f  P& [154
: G; B% {% s5 i  n0 S0 c155
156
* ^+ J8 g4 Z9 P1 n% E8 \( h. d157
158
3 x# k5 e8 ^3 ~9 n8 E/ s159
6 H. L7 d9 A0 i4 {& J160
' w% i; x) w4 _5 S4 Z161
3 l) z6 ^; `  c" D5 H162
163
% y# @2 u0 Z( o5 Z9 r7 {164
  F& f- w! o+ g2 q/ @: D9 |165
+ i! ?2 j" D) Y4 x& h  S7 r166
167
' @% A+ i2 j9 m4 N: y7 f# J168
3 l9 g8 y" ~6 T4 F" Q( v! J5 z) S169
# ]2 T3 K$ T2 w; R+ F170
171
/ @& m0 p3 B! n" z) c. U172
) p% I0 y$ O! J173
174
175
176
177
) g6 i' O$ S% W2 n4 s178
* Z/ K. ^$ U8 N; Q1 N& d" x179
% Z/ r( u% N9 D& W, k+ i8 Q180
181
182
: B8 s# X- x. u3 Y" r183
) x: e- f# U! W, d$ v: W  X184
185
186
# U2 b2 L- S/ g- k! k! V187
188
189
: x* D5 X) i! Z( T( {1 W! H( R190
, }3 I0 j! e5 t3 v5 h8 m2 l' N191
3 k# r* o6 l) d3 k" S192
3 p! q; L+ _/ u' E3 E193
194
; o# V8 n; ^; m$ Q+ }' D195
196
197
198
9 [7 }* a! T  W199
8 b3 P8 m1 s% ~, d7 e+ W3 D! S( H200
201
202
' I1 K! e1 }% z+ @- _; P203
! y9 S7 }; i4 Z4 p5 A( N204
205
$ W) U; n% E) W* K( w$ d7 z206
3 B7 S8 ~6 R3 y9 m" K0 Y207
208
209
5 v; V& W. S: l% C6 Y210
, P6 C8 }# U" e) s' q211
212
: O1 q- e3 F5 }2 b' k, e% F1 L. E* D213
$ E6 o% O) v2 x2 a  l/ a  h214
215
216
217
6 S/ D% F6 L: O218
9 A' N+ e( x6 R' ]7 N219
9 m; F2 n$ Z( {3 G7 g/ F220
6 z5 X! G7 p' E9 o% \% f, d221
$ G% {% ?1 G( ?4 z2 P+ n, M9 @8 H222
9 P+ f; U/ L8 }5 Z& W5 B223
224
225
226
6 R6 r* L0 a9 f% E+ r- c0 `227
228
229
230
231
8 B( _5 ]7 f& G" e9 Q0 m# U% v232
1 D' {, |3 `7 c2 t5 B0 ?4 ?233
! d# k# D1 t1 o& N' @) O234
235
3 i5 z- E$ g- x% C236
237
238
" [# {* i# O1 s% _. [239
240
241
242
243
244
245
7 R. [! w  H2 S) R246
  `# d- O$ Q9 c( x( n9 _$ P5 i247
248
249
1 i$ V" ~$ {. }2 N" x* s& i250
( H  b2 x1 ]1 F* s251
# g3 c4 Q$ H1 \3 _  u" J252
7 F/ I: ^( m- z8 l1 F" T5 P253
254
255
256
257
1 m2 S$ C* w5 U2 S; m258
& W6 Q5 l% V" r- ~6 k4 Q259
260
261
262
5 A3 ~' p: m" \7 ^263
264
265
266
  K$ }1 [" a4 O267
0 \9 B3 K: G# f  v( i* o* R268
1 X  u) R  \/ N) u269
270
+ \/ W. c; e0 ?8 A+ o# `271
272
! m' ~, O0 u7 _4 v- v8 f273
3 q8 Q" c( J; [' G9 L274
275
276
, F1 }: o( x$ J277
278
279
( H4 l- r: |$ f* W9 c/ }3 D& R! G280
' ^) T3 E4 {9 e, \- F. C6 ]0 T281
0 ?" q5 F  H# V- w9 m282
. Z1 b" `5 [9 R; r* Z283
284
- V6 x, F+ A, O" Y1 D, j& P285
286
: h4 j6 u& B) F# O1 A* F8 P287
# v. E2 U9 a0 R# y& s288
289
: W. \. ]7 [: q2 o% ~4 \4 x5 v6 s290
291
6 g. @) M1 y, l0 B292
293
, P; M$ R( |, M" x294
' D6 z4 ]# Q( N& P) ^- B295
296
297
& b4 b- B- N* K; V/ A( u298
" q. D( e' a) |" G; W1 [8 O. d6 j. I299
/ d& {& ]  V  t300
301
! }1 ]! X( n. V* x. T- v$ J& l# ~- R. v302
303
304
305
306
3 D3 V. V! |2 w: r% R! b2 l2 C307
308
0 K5 M! A1 S. z% z% A- y309
310
311
& H  ~0 q5 m" n312
( i( x2 j# G" s# v  `8 u# L313
. V5 D2 v# p1 \314
315
# p" T  u" F6 f316
317
( G3 ^+ ^" k! z1 m318
319
320
  a+ I, Q. e  {3 G4 N" q321
322
323
324
325
326
: Y: N7 ^3 O# n' l+ F9 S327
328
" @) x( u& W" l( i6 ~329
330
331
6 `" ?/ x4 `' m% n332
! s) a" q7 n) {- V4 P333
3 m+ [! r; f, d9 L! V334
6 _) d( P0 C8 g4 B. `335
  B5 a& Z4 f4 h! g+ j336
337
, a. _+ w7 o7 v338
- p  {- `8 q/ d; S8 I0 ]339
340
  `: E# w* w0 J/ O! H341
' w0 N* h$ _6 e1 _3 h342
" v- D# v1 ?; O2 k6 e) a" a' Z& B343
344
345
  O1 C' D( l; U/ A346
347
348
/ Z$ P! ?2 O7 F: Z4 [/ f1 Q349
) b+ r. [+ D' t' L* B( }350
2 `2 V$ C+ L# V' ]351
4 B' j$ u2 S3 [5 q1 G- M352
% _5 N9 I1 |! f353
354
. k: t# Y: ]" x% }5 W5 w) w355
4 s2 C; z* \0 A- K* g: O! V; S( X356
357
358
- a9 }8 \& Y  Z2 U6 s% P% x359
360
361
: j) M9 n" ]+ Z7 w" s) H' _) {, _362
& E; {( o2 P; V3 I. n363
364
365
: o1 ^$ T' `1 ~+ |3 |  S366
367
368
369
370
371
- ?, t$ C7 |- K0 g; R372
373
" x5 y, u' x7 p, x  E. F) D& d374
375
376
) a" }4 N0 F+ y5 w/ O377
378
, ^3 j7 Z9 {( L7 O( r9 W, `1 _8 \379
. i' q0 y8 [# l/ ^( P380
9 K# X" z# Y" v: K* m1 p381
382
383
384
385
386
/ E) s" ^5 S1 ~387
388
389
3 i0 d+ }5 B: Z* {4 }% F390
8 U  ?0 N, c# o$ ~391
  F: u( a6 H- K' y: E! o# ^5 E  E9 j( H392
: @1 G3 m6 Q7 q- n8 V# e4 ~393
394
! `4 m- B, [' h0 f% H4 z395
396
397
398
399
6 Y5 e+ ]: E$ |0 G* @" J400
+ {& z1 ^# H9 X) n401
402
403
404
405
406
407
5 m# H2 T* }% ]9 g. m" V8 L' l408
409
410
411
5 L2 e& L1 K3 _. o6 d412
. @+ O" G' h, |9 Q$ B! a$ t413
1 C7 r! F2 D. {& ?# ]6 Q4 Q7 S( O! N414
415
& X. [! r5 C) m416
417
/ E  q9 L, ^; u8 B; `418
419
) _3 ^# D4 \( `2 K420
421
422
423
424
  q/ A1 `( l1 Q# d) O; i0 c425
- E) n  D& T9 A3 g: a& Y% S426
427
# X2 [' \& s9 v* ^428
0 {5 g+ L/ f( W8 P- l429
7 h( z- d& q! h' c+ B. f! n3 |430
431
432
: N) q8 c0 Z: |) K7 t( {$ l0 E: z433
7 J5 X5 \  K1 S/ y- d434
435
2 X+ w2 n$ ~$ _" B" W436
1 Q4 d+ K1 K1 D% ]3 K( P437
  M- S& x: e+ K! a% v438
439
440
- l" t  t/ t2 b, F$ _4 Q441
! ~4 B( X* x" P  Z: f4 \. O442
443
444
445
' k$ m& f; a+ V3 x* Y0 M7 D446
447
448
449
0 q; {/ S0 i) A' Y7 d: t- X; P, R- p9 _: p450
451
452
: _& a3 h' l2 ^453
3 U( z3 n- d' B( R454
6 T; S) r# r' }8 e1 k455
456
0 Z% L! k  o7 F3 y- z4 w' J457
458
4 K- k9 z$ o3 ]3 Q+ d459
460
& g$ D' O( W7 Z7 K% c3 O461
462
463
464
; G+ Y! t; S3 f. n. g, S465
$ `, e- |. a! z3 \7 q$ B466
467
468
469
4 Z0 y/ [5 r4 N' C  J' F
& J+ Z$ P4 `$ [  R6 y8 n/ \


) d% A" T7 t* I/ q, ]% _


5 N) y8 u; A" A
# X4 t; ]! ~. W) d7 K) Y
- d& _/ T% Q3 t8 `) C( w2 {( t
6 e: Y9 h. H" _) v9 Q( O( A3 I
( v+ H& `+ I6 x/ |2 s. e. e6 _


1 j3 g8 e+ l4 [# m8 w( v3 o3 A

* \' R2 V$ i9 l7 V4 `


. O% H; ?0 ?( q
2 T2 ?% f3 s0 p4 c* s7 ~! x
9 l$ E* ?8 ?! J1 s) Y% `
- A; O8 m. T; B9 [$ a( h" c
, W1 P! g4 p1 \

7 r( E: p$ |# u: c2 B8 P  w
! o6 l+ d/ \. T$ x1 \1 n' L
( v& V3 H* u3 k9 Q! I) @' s0 B9 C————————————————
" p% r- @1 S6 f  \; t8 m版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 X) q9 X) b0 ]原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212

1 V. `; s' R8 Y/ @: p

9 [7 N. v4 w3 }2 N2 ~/ [