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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
& ^; F) S) i6 H- X: y" I/ R$ q# D目录
人工智能第四次实验报告 1
5 A/ g. {1 j$ M# x遗传算法求TSP问题 1
* ^2 g' x  t. O* d1 L- |4 U* ]一 、问题背景 1
1.1 遗传算法简介 1
. g0 A$ V+ C- w6 ?8 z1.2 遗传算法基本要素 2
  ^" B  A  w  @* x' L. A8 k/ U/ G5 `1.3 遗传算法一般步骤 2
% J9 D/ ]* i) L; m8 f二 、程序说明 3
2.3 选择初始群体 4
2.4 适应度函数 4
2.5 遗传操作 4
+ G- A. ]8 ]' u9 l; ~2.6 迭代过程 4
三 、程序测试 5
3.1 求解不同规模的TSP问题的算法性能 5
* w% E7 B# d2 {: X7 h8 {, R3.2 种群规模对算法结果的影响 5
; a- i+ V2 @5 q6 Y3.3 交叉概率对算法结果的影响 6
3.4 变异概率对算法结果的影响 7
3.5 交叉概率和变异概率对算法结果的影响 7
四 、算法改进 8
4.1 块逆转变异策略 8
/ C/ P, y  N, p+ [7 [, l4 j/ B$ o4.2 锦标赛选择法 9
0 w( _3 Y6 h8 w$ i" O9 g3 K1 ]五 、实验总结 10
一 、问题背景
. Z* O. a0 G4 m0 s( C9 ~4 v" a/ `1.1遗传算法简介
+ t9 }7 Q9 A# J/ l: q; l2 s遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
, d9 n+ z6 F  V遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
1.2遗传算法基本要素
1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
4 H2 ^$ ^, `6 R3 x2.设定初始群体：
" o$ r. b  n" Q0 e1.启发 / 非启发给定一组解作为初始群体
2.确定初始群体的规模
3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
% B- \2 C" U) V. E4 D/ }8 W8 M6 ^4.设定遗传操作：
1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
2.交叉：两个个体的基因进行交叉重组来获得新个体
  F9 _* F/ M; \3.变异：随机变动个体串基因座上的某些基因
$ n* ~* _8 S. E& b3 J5.设定控制参数：例如变异概率、交叉程度、迭代上限等。
, Y$ |$ K0 n' Q# f) d8 f) u
import numpy as np
import random
" O" e8 m! k7 gimport matplotlib.pyplot as plt
* t% j% `8 G% C& ^1 a, bimport copy
$ {/ h$ P- }% Q4 u% ~* l  Oimport time
# d2 o) `8 l! W( Y
from matplotlib.ticker import MultipleLocator
from scipy.interpolate import interpolate

% z- N( v( ]4 \/ q- f2 eCITY_NUM = 20
/ T  V" x& _% u0 pCity_Map = 100 * np.random.rand(CITY_NUM, 2)
2 i5 h$ |9 _; t! i1 k+ x2 ^
DNA_SIZE = CITY_NUM     #编码长度
! V5 n$ H) I3 B' V) NPOP_SIZE = 100          #种群大小
7 G  w) N1 b; x) S$ u; ~CROSS_RATE = 0.6        #交叉率
MUTA_RATE = 0.2         #变异率
Iterations = 1000       #迭代次数
. h4 v0 {" t) x% h. R& s) f# j8 D
! h/ ^4 H* X! K" f) F# `  x# 根据DNA的路线计算距离
def distance(DNA):
    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
. f/ \5 J9 E5 @4 W        temp = City_Map
' y' i/ p+ p7 ]/ N/ Q    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5

- h4 H. x* c' X; p' |, E# 计算种群适应度，这里适应度用距离的倒数表示
+ O' w# s+ S; o  o1 w: _' L4 m8 rdef getfitness(pop):
    temp = []
$ E  x+ y$ f+ k1 s    for i in range(len(pop)):
        temp.append(1/(distance(pop)))
( v3 ]  I- H) P% _3 f7 O. O    return temp-np.min(temp) + 0.000001
" }0 Q0 q& f  y9 @+ E/ |) M/ S3 K! Q
# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
( O1 m2 H( ~! Z) |& a; Udef select(pop, fitness):
    s = fitness.sum()
    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
) G$ @& n$ {* z& f$ o" C    p = []
    for i in temp:
        p.append(pop)
( U  q( P( h6 o( ?) J    return p
# a  l- x8 M% ]5 E$ I
" X( }" Y/ E3 q/ F* z* W* n# 4.2 选择：锦标赛选择法
; I6 g  L6 ]1 g6 c: E( d$ ~$ ndef selectII(pop, fitness):
    p = []
    for i in range(POP_SIZE):
        temp1 = np.random.randint(POP_SIZE)
6 W7 ~' V! B4 {3 F        temp2 = np.random.randint(POP_SIZE)
' `, H% V! Y7 G  @% T        DNA1 = pop[temp1]
        DNA2 = pop[temp2]
        if fitness[temp1] > fitness[temp2]:
; F/ j5 u* n2 P7 L! T6 u            p.append(DNA1)
' z* E1 ^# k0 A( B6 y+ O. i$ \: w) R        else:
: u  c2 }9 @1 F* v6 ^            p.append(DNA2)
$ |. K& v# d) l    return p

# 变异：选择两个位置互换其中的城市编号
def mutation(DNA, MUTA_RATE):
7 p8 Q% b9 u/ M* Y! M8 o2 j" q    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
& R' k9 D+ w" w5 C1 J6 ?" F        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0,DNA_SIZE)
# M9 J% Z% {0 J- z5 W        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 变异：在父代中随机选择两个点，然后反转之间的部分
def mutationII(DNA, MUTA_RATE):
6 [. r- r2 t. s5 I9 B+ a    if np.random.rand() < MUTA_RATE:
        mutate_point1 = np.random.randint(0, DNA_SIZE)
1 o( K; r) n1 z* X$ _" ~# e( r        mutate_point2 = np.random.randint(0, DNA_SIZE)
        while (mutate_point1 == mutate_point2):
            mutate_point2 = np.random.randint(0, DNA_SIZE)
: I! r' O8 w, O- C6 N1 q        if(mutate_point1 > mutate_point2):
            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
        DNA[mutate_point1:mutate_point2].reverse()
% ^. f$ w, `1 P
5 [; `) w( }* q# 4.1 变异：调用 I 和 II
- z& O, z7 O2 h! O3 g, s' A' xdef mutationIII(DNA, MUTA_RATE):
; D) V: D1 V' L2 @4 ^    mutationII(DNA, MUTA_RATE)
% q) ?1 [, w0 Y. U& v5 ?    mutation(DNA, MUTA_RATE)

( y# [4 p3 Z! D& p. H$ D# 交叉变异
* Y1 U% j& m6 L' j, I4 d# muta = 1时变异调用 mutation；
) \* c! u9 P& g7 X1 [: s; Y: s, @, v# muta = 2时变异调用 mutationII；
# muta = 3时变异调用 mutationIII
$ H1 ^/ X$ Q. v4 e8 h. ^2 B" _9 O" }3 Pdef crossmuta(pop, CROSS_RATE, muta=1):
& t" v- U* i1 g  x4 y( C2 E    new_pop = []
3 S' ?; K% H. J( G2 @) ]    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
# Y) r4 R7 r: P  c  Y1 a; L; n        n = np.random.rand()
( M2 t  X  ^) V) r$ V, C' ?        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
            temp = pop.copy()
            new_pop.append(temp)
# \1 O6 y: i) `+ A7 Q        # 小于交叉概率时发生变异
        if n < CROSS_RATE:
8 L1 G+ a/ ^) p% y  d+ j            # 选取种群中另一个个体进行交叉
            list1 = pop.copy()
            list2 = pop[np.random.randint(POP_SIZE)].copy()
. o, |: h* J) F! U+ {9 v  H            status = True
            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
            while status:
                k1 = random.randint(0, len(list1) - 1)
                k2 = random.randint(0, len(list2) - 1)
                if k1 < k2:
2 E, H7 C7 w" [4 _. A/ E' `                    status = False

: i8 S/ \4 k; i+ @            k11 = k1

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

            # 交换片段后的DNA
            list1[k1: k2] = fragment2
            list2[k1: k2] = fragment1

            # left1就是 list1除去交叉片段后剩下的DNA片段
            del list1[k1: k2]
            left1 = list1

8 ]4 `/ x: ^8 Q& j8 A            offspring1 = []
" i# j3 N- |, s6 c. L5 j0 x            for pos in left1:
, c3 Q7 J6 e% p                # 如果 left1 中有与待插入的新片段相同的城市编号
                if pos in fragment2:
                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
: G% p! w# m( G# R0 o                    # 循环查找，直至这个城市编号不再待插入的片段中
" X# @+ }. h0 s( P8 B+ `6 ?& z! M9 m                    pos = fragment1[fragment2.index(pos)]
                    while pos in fragment2:
                        pos = fragment1[fragment2.index(pos)]
9 D" ~2 \$ K) Z) L& A+ w                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
                    offspring1.append(pos)
3 k5 A" z3 v9 f( h7 G9 A                    continue
                offspring1.append(pos)
  a$ A8 i3 ^6 x4 g/ ~8 H            for i in range(0, len(fragment2)):
                offspring1.insert(k11, fragment2)
; e: R: r7 V3 k& ?" M! O                k11 += 1
4 b' I% m# Z0 j6 q$ a. b            temp = offspring1.copy()
            # 根据 type 的值选择一种变异策略
. K0 A2 t: h( q7 ^1 t' Q            if muta == 1:
6 ^# u0 s8 K: T' w/ ~, o2 T                mutation(temp, MUTA_RATE)
5 C4 v* b5 U/ b( X! P& c; C3 [% _            elif muta == 2:
2 Z$ E' ]$ g. b: q                mutationII(temp, MUTA_RATE)
            elif muta == 3:
" l6 v! f3 ~, h* \, [                mutationIII(temp, MUTA_RATE)
0 e- E5 t, i/ C' p5 ~) r            # 把部分匹配交叉后形成的合法个体加入到下一代种群
, |- ~( V, e& I4 L            new_pop.append(temp)
) _' D! }/ v5 O5 U# P6 ^) p) j
- O8 C. \1 ?; j$ t+ z    return new_pop
( C# t9 ]/ E8 K7 S
def print_info(pop):
5 j4 h, e7 j1 i, t9 L    fitness = getfitness(pop)
0 n  N' {' E( L    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
' ]$ q9 R$ d" c& G# Z    print("最优的基因型：", pop[maxfitness])
4 F4 R. H9 f( h) f0 }# }# j    print("最短距离：",distance(pop[maxfitness]))
    # 按最优结果顺序把地图上的点加入到best_map列表中
    best_map = []
' a9 P* L) _3 ~9 m4 F  I3 E    for i in pop[maxfitness]:
+ a! F9 U5 r# |7 i* I' f6 ?        best_map.append(City_Map)
    best_map.append(City_Map[pop[maxfitness][0]])
    X = np.array((best_map))[:,0]
    Y = np.array((best_map))[:,1]
3 r% |2 `: n+ k    # 绘制地图以及路线
    plt.figure()
    plt.rcParams['font.sans-serif'] = ['SimHei']
! y5 ], c4 k; y' Z    plt.scatter(X,Y)
3 l) ~6 S" ]# j6 b    for dot in range(len(X)-1):
        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
# k6 P5 N( U, n$ h1 `! Y9 `; x    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
    plt.plot(X,Y)

# 3.2 种群规模对算法结果的影响
def pop_size_test():
6 I' z6 F' C! {) O: s    global POP_SIZE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
    b_list = []
+ I( U# W* h1 E0 U. U* w; p$ U% N    t_list = []
    for i in i_list:
        print(i)
        POP_SIZE = i
        time_cost = 0
3 K$ X- o- [7 B4 {        min_path = 0
+ b( n( q. b  Q5 ^        for j in range(ITE):
$ I! w7 {$ E' O; Q            time_start = time.time()
            ans = tsp_solve()
) X" m4 @4 {- c+ d            min_path += min(ans)
, v) r4 m- ]) i" z9 {            time_end = time.time()
3 `$ b8 T4 ]/ w: }            time_cost += time_end - time_start
8 G+ L) Z) P0 }9 N
0 I' W: \1 l4 D! J6 Z, k2 U$ _        b_list.append(min_path / ITE)
  T2 Q! b4 `: X) P' z+ n        t_list.append(time_cost / ITE)
    show_test_result(i_list, b_list, t_list, "POP_SIZE")
2 V5 q7 }2 g8 K! ]+ O
# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
8 A) h" i* L; _" n/ s2 i' ~    global CROSS_RATE
2 T6 R, R* g, B4 ^; h    ITE = 3 # 每个值测试多次求平均数以降低随机误差
+ A8 I8 ?) A9 z" K7 @* F  W- w7 n    i_list = range(0, 21)
0 q  d8 n6 J2 n& w% u    b_list = []
9 N' |" e" B* W  W7 ^' v    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
5 {( a9 }( |1 u/ h- G! l    for i in i_list:
' s+ ?/ b# W( }% c3 O3 G        print(i)
        CROSS_RATE = 0.05 * i
        ii_list.append(CROSS_RATE)
        time_cost = 0
        min_path = 0
0 s; R* d/ |& u        for j in range(ITE):
            time_start = time.time()
            ans = tsp_solve()
9 f) a) W' h2 i% a9 K% B4 Y# j            min_path += min(ans)
) o2 y7 q5 _  S- C, h            time_end = time.time()
& T0 |+ ~  V6 [            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
6 L9 y' V9 U( ?/ |, q+ C    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")
" d4 N2 a6 q7 |+ |* O
# 3.4 变异概率对算法结果的影响
def muta_rate_test():
    global MUTA_RATE
# ]% w. R9 }! {4 N5 z    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = range(0, 21)
    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
        MUTA_RATE = 0.05 * i
) L2 U* D1 {% g: }& E7 l$ V  ]5 g        ii_list.append(MUTA_RATE)
. d: s$ d9 y( a9 a; h/ z        time_cost = 0
        min_path = 0
        for j in range(ITE):
# ^! x! H- T* ]; g            time_start = time.time()
            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
            time_cost += time_end - time_start

  |9 y2 f" Y, }2 o        b_list.append(min_path / ITE)
# q. y3 T/ t! `1 E( u        t_list.append(time_cost / ITE)
; _2 l8 M* z2 V$ J4 h/ O) L    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")

# 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])
( u# q/ w) r1 z, y, C; w    X, Y = np.meshgrid(s,s)
    Z = np.zeros(shape=(11, 11))

% i: o% F4 I( b  b    global MUTA_RATE
    global CROSS_RATE
    for i in range(11):
        for j in range(11):
1 y/ r4 g, p, |7 @7 h3 x            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
            MUTA_RATE = Y[0,j]
            ans = tsp_solve()
- V+ R- s0 @" w, k7 ?6 o8 O            Z[i, j] = min(ans)
0 }$ s/ J% o9 X! p. ^( }& T
, s+ p0 c8 i' f5 }0 q9 }    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")
3 P' k5 v- J1 @- Q    ax.set_zlabel("Shortest_Path")
6 n: G$ P, C# r; G6 r; ]    ax.set_title('TSP')
    plt.show()
0 J( X9 w% I0 M6 r8 B" u
# 3.2-3.4 生成参数测试结果的可视化图表
, T" ^- a; i- b2 U  Xdef show_test_result(i_list, b_list, t_list, msg):
  v; G/ N" W& |5 `0 e$ w    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b')
& D4 `+ P8 Y! \# i& C1 q8 p    ax1.set_xlabel(msg)
    ax1.set_ylabel("Shortest Path")

    ax2 = plt.subplot(122)
" `1 b( O' F. @% u& _    ax2.plot(i_list, t_list, 'r')
" h8 p5 I  f( a    ax2.set_xlabel(msg)
3 ]' @. W1 D4 y* |% u; D) {    ax2.set_ylabel("Cost Time")
8 s: P8 S& h3 {4 Z# K% W* r- H. @    plt.show()

# 求解TSP问题并返回最大值
" D& v! _! i3 E$ T; x& ?# muta 指定变异方式，sel 指定选择方式
# ~5 B0 O/ H: F. X: idef tsp_solve(muta=1, sel=1):
: U& {; }* \% h/ o+ S    pop = []
    li = list(range(DNA_SIZE))
6 k% C1 D+ ]- F$ \8 Q    for i in range(POP_SIZE):
' W+ {. ?" J! G+ M# X/ o        random.shuffle(li)
        l = li.copy()
$ X0 o: f# y; P( p        pop.append(l)
- q: I: _" H. M1 ]    best_dis = []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
7 t' D4 Q: H+ D, C% O    for i in range(Iterations):  # 迭代N代
& U: T9 D$ B& E3 b        pop = crossmuta(pop, CROSS_RATE, muta=muta)
% u! n! q' H# J: h        fitness = getfitness(pop)
7 ~7 D! L1 e- v$ g        maxfitness = np.argmax(fitness)
7 r" S) s: @4 {/ K& P3 T% R5 V5 m        best_dis.append(distance(pop[maxfitness]))
        if sel == 1:
& X' B* h/ z/ k            pop = select(pop, fitness)  # 选择生成新的种群
* `1 _" w, i% w: D" d9 |        elif sel == 2:
            pop = selectII(pop, fitness)  # 选择生成新的种群
* J) \/ t$ [8 q- d
    return best_dis

# 4.1 块逆转变异策略对比测试
def opt1_test():
    ITE = 20    # 测试次数
    i_list = range(ITE)
    b_list = []     # 每次求出的最短路径
    t_list = []     # 每次求解的耗时
0 t9 o! ?, B+ |* @, s; W; W+ b    b_listII = []
+ J3 d5 ?$ P3 t$ z    t_listII = []
7 B" `% E2 R  v9 A% u# i0 B    b_listIII = []
    t_listIII = []
5 l5 e3 \5 B1 d  g4 J5 X' j
    for i in i_list:
        print(i)
# |! R( x/ N7 P1 @) ]% N: a7 E6 W3 {        # I. 原两点互换异策略
; J7 o) F& p8 z        time_start = time.time()
        b_list.append(min(tsp_solve(muta=1)))
* n9 w$ f$ q( O, e- X# l. J! |/ t        time_end = time.time()
        t_list.append(time_end - time_start)
/ D8 g+ K  e7 v: @1 f        # II. 块逆转变异策略
        time_startII = time.time()
7 d' D6 w+ ?- c( Y7 E        b_listII.append(min(tsp_solve(muta=2)))
        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
- O+ a; Z  K6 T        # III. 同时使用上述两种编译策略
        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(muta=3)))
& ^% T& y2 ~$ ]/ f" H1 y        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)

    # 做排序处理，方便比较
4 A8 @  d' c7 v; Z# R# x    b_list.sort()
    t_list.sort()
    b_listII.sort()
    t_listII.sort()
0 @. V5 {/ B$ ^    b_listIII.sort()
    t_listIII.sort()

' X$ I; x; p+ c    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
( K. |+ t$ q% ~2 q$ z7 [/ x    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
6 l& ]5 h% w: I7 b$ Q; ]    ax1.plot(i_list, b_listIII, 'g', label="Origin + Block-reversal")
    ax1.set_ylabel("Shortest Path")
  h8 v- Y1 B( t1 v0 Z8 i    ax2 = plt.subplot(122)
* V! i; c! n" N, G. g    ax2.plot(i_list, t_list, 'b', label="Origin")
    ax2.plot(i_list, t_listII, 'r', label="Block-reversal")
: R+ g( V, T8 E4 w8 ^    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
    ax2.set_ylabel("Cost Time")
5 v: a( w  s) g0 W0 X9 L    plt.legend()
3 `9 w$ N2 `: S    plt.show()

# 4.2 锦标赛选择策略对比测试
def opt2_test():
    ITE = 20  # 测试次数
    i_list = range(ITE)
    b_list = []  # 每次求出的最短路径
" S! T3 u: k; F$ u    t_list = []  # 每次求解的耗时
" I0 F% g% ^; x# W# i/ S. H    b_listII = []
    t_listII = []
" U0 P2 b6 T, z4 F    b_listIII = []
, i( h9 \) q) J! U' u5 U    t_listIII = []
! q: U, ~3 Z3 `) c$ ^' [
    for i in i_list:
. ~2 I5 O6 g; F. K* b3 C0 Q        print(i)
: w7 M0 X! ?3 \5 `; F. \        # I. 原赌轮盘选择策略
* i0 O9 ]9 |/ |( i6 E        time_start = time.time()
3 ^  u. ?4 y/ _4 w        b_list.append(min(tsp_solve(sel=1)))
/ Q" `. Z# b) J        time_end = time.time()
        t_list.append(time_end - time_start)
6 T; [7 g. p& v6 X! j        # II. 锦标赛选择策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(sel=2)))
4 G; H% O! ^" h: |- _        time_endII = time.time()
$ {1 L5 d! j9 h        t_listII.append(time_endII - time_startII)
. e1 r* T4 w$ L  R: D2 ]0 Z        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)

5 C7 |) Q4 ?% n+ ?    # 做排序处理，方便比较
0 P2 d* ^3 U5 k( `    b_list.sort()
2 r  u3 L, `3 |3 w  v: `* ]$ k' n    t_list.sort()
    b_listII.sort()
    t_listII.sort()
( M2 l) T/ f, G& I+ u- R1 |    b_listIII.sort()
4 r9 M% i* Z- v3 H1 e8 j. k    t_listIII.sort()
7 Q( x* ?! ?- v- ?7 e
    ax1 = plt.subplot(121)
# p8 l9 L# K( o* S% `# ^    ax1.plot(i_list, b_list, 'b', label="Origin")
    ax1.plot(i_list, b_listII, 'r', label="Tournament")
5 B- e. X+ b0 U% c& ?: q& {( B    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
/ i9 e* K  q, Q2 |  d( S    ax2.plot(i_list, t_list, 'b', label="Origin")
/ b0 U; w2 [5 s8 e! C1 t" S    ax2.plot(i_list, t_listII, 'r', label="Tournament")
; \9 |% }" \+ M$ |    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
    ax2.set_ylabel("Cost Time")
    plt.legend()
& j  J$ F, f0 t  r' {! X% o    plt.show()
/ z, H! P$ S5 z' v5 i6 m
# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
, j. z( G5 i+ B; J( J- l: c0 Gdef ori_main():
    time_start = time.time()
    pop = [] # 生成初代种群pop
    li = list(range(DNA_SIZE))
+ d/ x8 Z4 q) W6 l4 C, m# @( P    for i in range(POP_SIZE):
, ]: b1 p9 C6 [: I/ }" j        random.shuffle(li)
        l = li.copy()
# i! r8 ?3 n  E) Y        pop.append(l)
    best_dis= []
1 R, U4 l8 n( T7 C    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
8 N5 I  z$ |9 P: @. {, {) t    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE)
        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
% N4 `9 y; V: F: R        best_dis.append(distance(pop[maxfitness]))
, Q% T( U$ S2 Z1 [! C2 s' Y, N        pop = select(pop, fitness)  # 选择生成新的种群

    time_end = time.time()
    print_info(pop)
    print('逐代的最小距离：',best_dis)
8 h: u' q- t3 F9 k$ O! J    print('Totally cost is', time_end - time_start, "s")
! C2 Y, q0 n$ N0 w- p5 k# W0 @9 d    plt.figure()
- O3 o" `% X2 ?1 E9 X* x; \    plt.plot(range(Iterations),best_dis)
6 G1 t4 g7 n) t' M$ O
' b0 @6 \. ?# Q7 T" l- y9 Y; n. R# 4.1 块逆转变异策略运行效果展示
9 e5 N) S3 i' f1 W9 v) I: R5 C" T4 Fdef opt1_main():
    time_start = time.time()
    pop = []    # 生成初代种群pop
( h: }! v$ B* Q! n9 ~9 n4 K4 K    li = list(range(DNA_SIZE))
9 B- f: D. D. n    for i in range(POP_SIZE):
2 M5 m, P, v, x, g/ D        random.shuffle(li)
8 \/ s3 z# m2 `% Z6 K4 ^$ Q% [9 q2 f        l = li.copy()
! Y! M5 k6 c* o1 z        pop.append(l)
    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
0 `3 R2 s% ?; ?! ]: g, v        pop = crossmuta(pop, CROSS_RATE, muta=3)
# H$ J0 \. P) w0 h! v6 Y! ~        fitness = getfitness(pop)
2 q6 d1 H6 `( P# v, _        maxfitness = np.argmax(fitness)
: G1 R* ?) w0 W( e7 p        best_dis.append(distance(pop[maxfitness]))
        pop = select(pop, fitness)  # 选择生成新的种群

    time_end = time.time()
    print_info(pop)
8 N; a1 }- ~7 Q4 j9 y    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
, Q- W: L! q) k$ V4 D0 q* e    plt.figure()
7 j$ b8 D4 N; @* ~( `7 e0 O# y    plt.plot(range(Iterations),best_dis)
2 ~" h# G, S7 V% y
if __name__ == "__main__":
4 L: r) ]* K/ U+ r" Q
7 q( {2 T2 {4 u3 p, c. I; W8 H    ori_main()    # 原程序的主函数
    opt1_main()   # 块逆转变异策略运行效果展示
    plt.show()
    plt.close()

  G$ m2 e+ o7 J- N! P" n2 H! N    # opt1_test()   # 块逆转变异策略对比测试
    # opt2_test()   # 锦标赛选择策略对比测试
; ^. ~9 ?& G, P* ~
    # pop_size_test()       # POP_SIZE 种群规模参数测试
0 b# L7 D- d% r$ X6 }2 l0 v    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
. y4 G; `/ I# `' O& P9 u    # muta_rate_test()      # MUTA_RATE 变异率参数测试
9 g9 y( z  R# T/ m# o- R    # cross_muta_test()     # 交叉率和变异率双参数测试
% W! M% A3 J/ V+ D. t

4 h/ |# x, {, t. e5 P1
# t* s$ K: f, A7 X" B* S- L0 G9 o2
3
  u/ ]+ M/ B. x: p4
5
; D1 H' D$ J0 m/ r7 S! ?6
& }( l: Q9 z; c/ B! v  w, x7
8
3 `' h- `" b4 B4 N5 [9
% a* l# ~+ L0 K( [" t10
5 N" m. `3 a$ Y% z. Z; s! Y11
12
13
14
1 a+ \: `! P! X$ H1 r' e& K15
16
8 c' J" w, W+ k5 k3 h17
, o, h/ x6 P: ^18
19
20
21
  H% k) ?% n8 U1 C22
( w) _* `- g. h: Z- `23
  a  z6 Y% V* |# V$ T' l24
25
. S% r, g- ^. v5 S" O1 E3 N, N  v26
; o( f9 P, L' ^2 E7 ?27
9 J4 M4 d- }" s/ l7 W2 w9 K28
$ u! U, v' F4 z7 |29
1 Q; I! h. L( S$ F3 d( s30
  f- C" k8 S" M31
32
! \" b6 {- ]2 o! L33
34
# t/ P7 ~. u0 V+ g6 [3 G/ z35
36
37
38
2 [3 {& w" s7 {39
, o" S4 v% q: h40
41
1 S8 u! ~: h8 c+ f7 L: Q! t5 ^42
43
* T# S6 q  d/ W: O' b) \44
45
2 A$ k% n! f# `( U46
4 ~4 V5 M8 K( _" x1 G9 G: Z47
" P+ v$ F# D. I$ M" A48
49
50
51
52
* n+ o& r: s/ a. l# Q9 z; m53
' b2 m% X1 Y) }- F6 ?54
55
* P4 {7 v: \% G3 w/ ^56
57
58
59
60
61
7 U% A0 j1 t' F/ N# c  ~62
63
64
4 z) M$ a3 ~8 \2 Z+ W65
66
0 M1 C0 J( s6 ~, n1 o8 t) P67
68
69
70
71
: c% V; y4 Q+ f- Q9 z9 Q9 Q72
73
74
75
76
77
78
79
80
81
7 x+ |( K( L- l7 v82
, ]' u, j2 S% E, a( r; L83
84
85
& K. P2 M0 d. y86
  y9 y+ {$ A2 A, p4 u/ ^3 }87
88
+ L0 {9 ^" p1 p89
90
91
92
93
7 Y- T! z3 r5 r+ `) o94
; f2 t* G( z1 }: E5 ?. \7 Q95
. b! R( k* F# n% \# T1 c& z96
8 r) \' N, b" d' T: V97
9 z& i: c& c* _9 K98
99
) f0 I0 \$ b6 W+ ?# {1 D+ O3 C100
' \1 J3 k, a; f# g0 W8 D101
' e/ H' L6 H- M: [102
103
7 |) E- r6 n9 q! O8 j, N104
9 v' R) `% f2 T, H8 U$ e4 e9 J105
( b" r- l+ l/ |' @106
107
108
- J2 v2 G( C! T1 w0 u$ a* a109
1 v. @" I  O2 L110
111
112
6 v4 z5 C$ l; U7 Z1 T9 K5 b113
+ ]# {1 w. S9 ^+ S. l0 R114
115
/ Z: h* U% O9 l) M116
: \  q2 v2 R. \* T" n* ~. Y117
% c$ V6 ~- z; ]9 d- z% g118
119
120
) x& T: Z2 p- W/ d8 J/ Q, B: ?121
122
123
124
* |) x8 k* T; h! f125
126
127
128
9 g; k0 l+ M! U. R129
130
- ^2 }) @7 }5 u7 l. ~# [3 E131
9 P1 H! {* }1 j* o+ ~* J6 m4 a132
133
/ K% \% K# V$ r( r$ B  H/ r) a  z134
7 U! z; c, N* _& B+ C5 ]  s135
9 N/ h* M1 d& o. B) F6 {136
137
138
139
# ?1 p7 d8 b; `/ ^, B* w0 v3 q7 X140
! r3 T; X. P" T0 k! w/ v4 |141
142
143
, `( L+ T$ V& t* [6 {7 [. I144
145
146
* X2 s) d- H& P+ C+ Z' ]* w% B- Y147
6 M0 A, ^& B6 R! |) }148
149
150
" }2 t& r* w* g) A# E% S: P151
152
153
! _. _$ R+ z3 ^, k  X154
155
156
3 m; v7 E0 P. s* A3 h157
$ E! M9 m6 Q  ]) @) m) I158
+ i2 T, ], R7 q+ p8 B159
160
4 o; O7 M5 Z. e161
162
163
9 H( o' ]  k& z/ ?# d- N0 u( \164
$ D/ w, X! r* }( Z( m! |165
. C# D: E% a- S166
8 E' `# D( R2 V+ i: ?/ x167
6 t. F* w6 [! |# O. i168
: f2 V  ~' g( [169
* S! R2 \2 m( S# o; w! s$ @/ Z170
# j: ?% A) I; m1 j) ^- e171
172
173
3 J$ f0 Y) R: S( u  `3 p9 ^174
175
+ u7 g2 X2 ~6 f& N3 e176
177
178
179
180
( Q, }. T) y% J. {/ F181
182
183
0 G+ T. q0 S2 X  H! Q. @184
185
186
187
188
189
190
191
192
193
194
/ g; j# o+ f+ E  U6 Q195
196
197
  s$ v, w  E$ m! `& V3 H198
199
8 C4 n* [; m+ C0 I200
9 ~7 Q3 D6 J# S0 F: t+ v3 x201
  u1 o6 ]( t  \/ O  E5 ~7 H  G202
/ M) @* @9 g9 ~203
204
. e9 O" W% F( }5 d# {205
2 [( Z$ k* m! n; z: H7 h  c- R" [206
8 {) ]4 t5 u8 d8 d' [8 j% _9 y. B207
208
% \3 [$ s9 o  n; |+ y209
210
- u  t) }/ a0 u1 o211
212
  @2 H5 c. b* j7 m5 o6 j6 v$ P- h213
214
5 C# B  D% k* g5 X; I7 u215
216
' |% i7 T, u; `4 s217
& G- E3 L( ~, H8 O$ d. v, M218
219
# t/ M. i3 o' X8 q, h& L# F* G220
! h2 }  m& E# v  f7 u3 r221
+ A  C# K6 B1 O6 q222
223
8 @' a5 q! g8 e- h+ @0 ?' H224
+ x6 Q* Z4 F/ s( [1 s225
( ?4 [: L! E9 V. Q226
( `# o3 l  _6 W$ v5 a' j227
. I- @# G7 U: `) L! P# o% p228
0 J9 M/ |+ `6 K4 U: ~229
3 U$ a2 y( S  L8 ?230
231
0 ~5 G% v; ~5 M( w- n0 @232
4 a; N! K, m- x( @3 k* T, f- T233
, h% a" {, e, l234
235
236
237
  B$ w" W0 w' E/ f- {238
2 ^. H# H7 D! Y239
240
241
& j, V5 d' f! }' u, y: n242
243
& ^" l- b- z2 F7 E! h& @' K, {244
" v( q* p6 N4 p1 j5 C: P) ~245
246
247
' s4 I% ?( o3 I248
249
' N! Y# }: C5 E) j$ A! t250
251
4 M: p4 ^/ g" d4 }. G252
253
* ^* x6 Y& G+ T3 H8 T  c& L& }254
255
256
9 b5 I$ f5 ~( b2 E# _! v- l) g/ V% x) H257
6 |8 o+ Z( ~% H6 M) g, X/ c( k9 {258
* \1 V1 {$ A6 ^2 W" d* ]: z! L259
1 n) `, q+ G! W- V+ `  a260
261
! ?" Z7 _9 `* ~0 P2 M262
2 g' H$ f" S8 Y$ O263
1 r  {* `5 N6 m3 x; P264
265
266
267
. q4 `% N  u. u: n/ p2 e268
9 [% L# h1 U" s  c9 X269
270
271
272
273
274
275
' F1 D/ s1 p) ^0 e/ I* d276
277
6 [1 U  O% l( V4 G2 o278
+ Y% U' r4 M  l8 b279
280
$ o' E& f6 s0 G' v9 |1 Z4 X* t281
282
283
8 c- m# A6 J/ X+ @; r% t1 q7 o6 l284
285
286
* V  A5 M& h& \287
288
( N' O9 N: b( o289
290
291
1 {2 r( J& n- j! s292
293
% L; n+ o: o: X% c294
295
296
297
8 w) K: A1 w& H+ i298
# w9 O5 S1 h3 Z299
300
# W5 x8 H6 S7 k9 a/ j! U301
7 o5 w4 x' z9 O& r302
303
/ H: K9 i# C+ N, N4 |304
: @  J4 c% p0 s1 ?, ~  [' a$ @305
2 C# p$ h- E- `( W/ Z. Z% R" `! V306
& l" g% }: z6 o4 U% |; k" Z307
308
- U" c2 o7 ]' c9 p% s) C0 w1 g; R309
6 B/ p6 I, C, G2 h310
311
: e/ N8 G" }& u" A& R  G# l7 O8 V  O312
313
; p7 j" |* }$ ]7 q' s! {" Z; q314
4 Y, c$ r% v7 k& x315
316
317
318
319
- v4 A- Y- C$ o  n320
; M' u$ q5 ^* S, M321
322
323
324
325
; u) L( [' P: x& q326
$ g4 p2 N* U& Z( b327
328
' F8 O) P8 o; h9 k329
330
331
332
333
- y- Q& t3 G: L9 ?- O$ m* M; Q334
. z4 v$ A% A4 U335
336
337
338
339
340
341
% ]! c( T8 z6 v' x$ p342
" B. U( @' ^' }7 L. w6 `343
344
345
346
347
348
349
350
' @1 `2 U- ?1 M& p0 Y! O) |351
# m9 j! O+ e- {* k. T352
353
354
( p, E, a# f; T8 H8 K" s3 x355
356
' W3 `3 }. [& e% s357
358
, R5 i. ^% t* i1 r$ j359
! K, l7 s6 t& d( H$ N360
/ p1 T" v& ?" |+ c$ `" R361
362
( O. M5 P" h& R  p. h2 v) a  U363
364
6 Q. T* @& G& F) x1 E* T, k365
2 R" e, [4 b* h4 M/ o366
2 F- L$ c2 X4 B! i* w' Z367
# O% T! P2 Q) c, i368
$ s1 r6 R0 f0 j369
370
371
# y0 Z* \6 K; V, }3 n6 T372
3 }1 b  i0 X1 G' M& p$ q2 e373
9 D2 J$ a9 n* A7 D5 ~8 R374
375
376
3 }$ `6 C. Q# o7 |% t# z377
378
, t# ]1 N/ x& Z. D) q/ U* `- t379
7 I; M3 K1 E; v/ B. S+ H4 b/ J380
) k  \4 ?: d3 C$ Y5 p3 x3 i# S6 V381
( j. M+ |" g  z* h4 q382
383
384
385
2 I0 W2 L) B5 {' ]386
+ _! l& Q/ f' v# f387
5 I+ S' P7 \7 h- _- G388
389
390
. D9 E! d) |3 O! W8 K( l391
) V) E- T: W$ }& f7 o# G392
393
394
0 |, {5 b. C: Z395
396
397
398
399
+ B! X9 n3 c' L! ?400
401
402
8 v# m, o2 }3 X6 D- v8 a+ H$ d# S403
404
405
$ d2 v% p/ l4 e- l! K406
407
) R- n! O4 u6 H5 t5 ~, l408
409
$ h8 w" O% y" ]5 W& C7 u410
411
9 M* J0 [( }5 F2 _: C* @  l" E5 ~412
413
414
415
416
417
418
6 u, C: L) p$ h$ a  P419
420
0 q$ U+ N3 b0 k' e/ u6 `421
422
423
424
7 g3 ?1 Y$ A/ C+ A: q; }" a* V- D425
426
' x" |' ?' |4 c; j4 ?! S427
428
, K: ?. g. n3 E0 O+ j3 _429
* }& T6 @  N& M430
4 t$ ^$ [$ T5 N. O431
9 c( M: T+ {# R& H7 i432
433
434
; _  H/ g! g$ }  G/ b' d435
436
437
' y6 ^. t) O4 q438
439
440
/ R1 v+ i( E5 M( E+ w2 H441
% f/ ]- S  b: ?5 F5 A! i442
443
3 u; y& w5 N( A1 B, D, i; B* \444
445
446
- D9 p. s" K, Q7 Y+ u$ J447
448
8 r* n: x( `6 D+ V- T4 y$ w3 `  O449
3 |1 y1 C% n! y9 {) v450
# N* [  s. l. M% l451
% E  H1 Q1 z% a- j452
7 f, Y: n) G8 o: n4 O8 w453
454
455
456
2 R4 a4 Q( i# K$ C, W457
458
459
460
461
462
/ L0 M7 d0 [. s, ^1 p5 {6 b& N4 h463
, m9 d4 J0 L0 M) ~  j% z464
9 ^9 V* _$ ~. l& J465
8 |% f6 N7 [6 b+ H466
. ?5 o, h+ e$ G' J8 f- h' ]: T+ J- e# x467
468
469

' I, Q  n- k6 ]2 Y; A1 P: w+ }8 z
' \% X* P' _" e& t! l5 r2 y, O
& t# Y1 p, I( Q; [8 J


8 j6 P, C9 v; v" I, r

+ G, D8 H. M+ F0 J5 w8 P

9 F; A4 D% L: x6 m! f- l( y

* {& p& ]3 u( k; ~, r& v

$ n: M9 W  K7 o6 R: Q
1 c/ l! e, i5 ?4 A0 ~- ~

. F' X( b0 f) U  B# v& o

, B' g  C8 L* N+ J$ L$ n9 A


! Y1 ?% }# Z+ C8 I, b4 M

3 ~( ^. ?  j% h, R
+ H* C0 A! @4 |7 I, x
3 b1 e, K$ z+ Q+ D5 U
————————————————
版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 ]) m6 ~: P( H; I. l* G原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212
2 l) p; j0 W4 S  w# B$ P4 x
- i! @- d9 ^6 `


! f4 x& b8 {# g