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

杨利霞

基于Python实现的遗传算法求TSP问题遗传算法求TSP问题
目录
; B$ w8 q: }+ u0 f! U人工智能第四次实验报告 1
遗传算法求TSP问题 1
5 e( ^* n7 ]  _一 、问题背景 1
1.1 遗传算法简介 1
/ k9 s) t& o, p# q$ P1.2 遗传算法基本要素 2
1.3 遗传算法一般步骤 2
二 、程序说明 3
2.3 选择初始群体 4
2.4 适应度函数 4
2.5 遗传操作 4
2 M  H8 n+ L8 a  }0 T  c5 V! V2 C2.6 迭代过程 4
三 、程序测试 5
" D+ M. N' N6 h5 G# S3.1 求解不同规模的TSP问题的算法性能 5
3.2 种群规模对算法结果的影响 5
- L7 o) S7 r$ o/ J3 t2 v2 T; W3.3 交叉概率对算法结果的影响 6
3.4 变异概率对算法结果的影响 7
4 f6 |; H+ w3 c$ B+ J* v" U3.5 交叉概率和变异概率对算法结果的影响 7
四 、算法改进 8
# P$ Z2 m& M$ ?4.1 块逆转变异策略 8
4.2 锦标赛选择法 9
五 、实验总结 10
一 、问题背景
1.1遗传算法简介
遗传算法是一种进化算法，基于自然选择和生物遗传等生物进化机制的一种搜索算法，其通过选 择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的 解，再从这组改进的解出发进一步改进。在搜索过程中，它利用结构和随机的信息，是满足目标的决策 获得最大的生存可能，是一种概率型算法。
遗传算法主要借用生物中“适者生存”的原则，在遗传算法中，染色体对应的是数据或数组，通常由 一维的串结构数据来表示。串上的各个位置对应一个基因座，而各个位置上所取的值对等位基因。遗传 算法处理的是基因型个体，一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境 的适应度不同，适应度打的个体被选择进行遗传操作产生新个体。本文转载自http://www.biyezuopin.vip/onews.asp?id=16719每次选择两个染色体进行产生一组新 染色体，染色体也可能发生变异，得到下一代群体。
1.2遗传算法基本要素
, n0 _+ `4 P% e0 i% j; d3 n# [1.参数编码：可以采用位串编码、实数编码、多参数级联编码等
2.设定初始群体：
3 P) W/ m( r! I# @' r! a1.启发 / 非启发给定一组解作为初始群体
2.确定初始群体的规模
* ~; P" f; r2 |1 F9 U3 _7 n3.设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
4.设定遗传操作：
1.选择：从当前群体选出一系列优良个体，让他们产生后代个体
2.交叉：两个个体的基因进行交叉重组来获得新个体
3.变异：随机变动个体串基因座上的某些基因
8 B, S8 k; c- \$ a! Q/ p! _" e5.设定控制参数：例如变异概率、交叉程度、迭代上限等。

% d% Z( S. B1 A/ I; O/ }9 g5 dimport numpy as np
; _" u* ?! N0 Z4 O& ?import random
& @/ ^7 ~% k; t% ximport matplotlib.pyplot as plt
: ^. z6 ^& e$ T1 x0 m+ j- Oimport copy
import time
* K; w  Y1 l6 T. Q2 T8 ~
0 [% D/ P2 ]) }$ e9 }3 B  J- ~  Z9 A/ Sfrom matplotlib.ticker import MultipleLocator
from scipy.interpolate import interpolate
! B+ O4 w; o: w8 ~
$ P3 i1 ?5 j1 d2 r. }' s7 [CITY_NUM = 20
City_Map = 100 * np.random.rand(CITY_NUM, 2)
( Q, S- V& p! T% x- |, ]
9 \, [: n1 q+ s6 {DNA_SIZE = CITY_NUM     #编码长度
" [3 L5 E+ a3 p  gPOP_SIZE = 100          #种群大小
4 N7 X; ~% n4 C& v" W4 S; xCROSS_RATE = 0.6        #交叉率
MUTA_RATE = 0.2         #变异率
# A: j# [* S/ a& a7 v2 |& m4 T! r( jIterations = 1000       #迭代次数

# 根据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
9 I( }, W' _) O" r. R, t$ C        temp = City_Map
    return dis+((temp[0]-City_Map[DNA[0]][0])**2+(temp[1]-City_Map[DNA[0]][1])**2)**0.5
" V' y# d; N) N8 Z' g/ D
# 计算种群适应度，这里适应度用距离的倒数表示
def getfitness(pop):
    temp = []
    for i in range(len(pop)):
. L( L* K  U2 q' ]( q, \        temp.append(1/(distance(pop)))
3 C) R- j$ C: ~9 ^    return temp-np.min(temp) + 0.000001
2 J8 N9 j" A, F  I* B
1 Z# d" _/ X; `# b1 a2 a# 选择：根据适应度选择，以赌轮盘的形式，适应度越大的个体被选中的概率越大
' P) H- v2 Q- O* ?5 ?; {* Wdef select(pop, fitness):
    s = fitness.sum()
) n, C" {: B4 n" e    temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True,p=(fitness/s))
7 K' \& ?' I0 M$ ^: n7 W& \    p = []
4 H& z; R, I7 _    for i in temp:
( l0 `. r+ @# y- g2 w        p.append(pop)
6 k' j( h7 _, w6 C    return p
# S  ^" e1 y: J% \
# 4.2 选择：锦标赛选择法
def selectII(pop, fitness):
    p = []
    for i in range(POP_SIZE):
- U1 i9 g; Q  f6 n& @1 k0 [5 G9 g        temp1 = np.random.randint(POP_SIZE)
! g9 g3 _% @/ r" t2 @        temp2 = np.random.randint(POP_SIZE)
) p1 d# ^1 k7 \/ f4 O' h6 D        DNA1 = pop[temp1]
& C: W. f' \% Z+ M$ H* S- h        DNA2 = pop[temp2]
0 V) x& t: m$ ~4 y' A0 `        if fitness[temp1] > fitness[temp2]:
            p.append(DNA1)
        else:
4 h; Z! V% ~1 M( @: u( b            p.append(DNA2)
    return p

# 变异：选择两个位置互换其中的城市编号
6 Y6 R' b  D# J; B9 ndef mutation(DNA, MUTA_RATE):
    if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
        # 随机产生两个实数，代表要变异基因的位置，确保两个位置不同，将2个所选位置进行互换
8 s8 @+ X: N8 i$ ]2 z5 |6 h& l" d        mutate_point1 = np.random.randint(0, DNA_SIZE)
        mutate_point2 = np.random.randint(0,DNA_SIZE)
        while(mutate_point1 == mutate_point2):
; k& I/ s9 B: B, @3 R. |+ F8 Z# G            mutate_point2 = np.random.randint(0,DNA_SIZE)
3 _7 n" u& o# K/ v$ U2 s" e        DNA[mutate_point1],DNA[mutate_point2] = DNA[mutate_point2],DNA[mutate_point1]
; n, Y8 j7 O, L
( A8 ]2 \3 L( e& i( X5 }( X# 4.1 变异：在父代中随机选择两个点，然后反转之间的部分
  |0 G3 I% A8 K' G' `- Edef mutationII(DNA, MUTA_RATE):
7 W5 x% h6 h9 j8 _. M2 m    if np.random.rand() < MUTA_RATE:
        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)
1 L/ k  ^7 n7 h& I1 F& @        if(mutate_point1 > mutate_point2):
            mutate_point1, mutate_point2 = mutate_point2, mutate_point1
5 b/ B9 l0 y( X# i( W6 P5 i9 ^3 l1 ]        DNA[mutate_point1:mutate_point2].reverse()

# 4.1 变异：调用 I 和 II
def mutationIII(DNA, MUTA_RATE):
    mutationII(DNA, MUTA_RATE)
; \% x" P- N% b& N    mutation(DNA, MUTA_RATE)
; Y4 \% d9 J! V  q, x# c8 q
# 交叉变异
/ ^  U" e$ o4 x7 s# muta = 1时变异调用 mutation；
; p1 ^  C1 G; H- R# U: G# muta = 2时变异调用 mutationII；
+ J* v0 V4 n* a$ N* q4 N# muta = 3时变异调用 mutationIII
def crossmuta(pop, CROSS_RATE, muta=1):
( _& z8 p4 u+ @  _  U, b    new_pop = []
    for i in range(len(pop)):   # 遍历种群中的每一个个体，将该个体作为父代
        n = np.random.rand()
        if n >= CROSS_RATE:     # 大于交叉概率时不发生变异，该子代直接进入下一代
            temp = pop.copy()
" P- b. @5 A5 `5 X; f8 a9 @            new_pop.append(temp)
        # 小于交叉概率时发生变异
! J1 t( A! y; o' [+ j& P2 `        if n < CROSS_RATE:
! @, E2 F$ E) \8 e5 Y( s1 }            # 选取种群中另一个个体进行交叉
4 m) F2 U4 C5 |4 d+ S. y            list1 = pop.copy()
            list2 = pop[np.random.randint(POP_SIZE)].copy()
            status = True
- r, F, p! {" b$ _  X5 w            # 产生2个不相等的节点，中间部分作为交叉段，采用部分匹配交叉
            while status:
                k1 = random.randint(0, len(list1) - 1)
6 w5 s: D- s9 W6 a7 p' e% Q! I+ |                k2 = random.randint(0, len(list2) - 1)
2 u2 v6 r5 g4 {                if k1 < k2:
' q+ z* [$ j6 u/ m                    status = False
5 ]" N% e1 j. ]) f7 R: G9 y1 {
            k11 = k1

& {6 H5 @7 m7 ^% [            # 两个DNA中待交叉的片段
8 B! v6 u' ?% D! Q: @            fragment1 = list1[k1: k2]
4 V1 c$ ^( h4 a* _" w            fragment2 = list2[k1: k2]

5 g+ q0 u/ I( V" o8 L) e" c            # 交换片段后的DNA
  A: @. ]/ y/ P% [" w. H            list1[k1: k2] = fragment2
7 f4 C9 u' Y' t% t) x$ s3 h            list2[k1: k2] = fragment1
* k9 m& U0 D1 n/ V& m
( @3 L+ e: f/ I$ Z3 K            # left1就是 list1除去交叉片段后剩下的DNA片段
1 I( q5 T% P9 X# k/ O. c            del list1[k1: k2]
. a% l) ?# [9 ]" f: S            left1 = list1

            offspring1 = []
            for pos in left1:
8 h# X2 C! p) p                # 如果 left1 中有与待插入的新片段相同的城市编号
% J' V5 i* ^; r2 ~: b, D; S- p                if pos in fragment2:
1 j. Q7 o4 A# w9 E5 q2 E* v1 C2 n! F2 e, t                    # 找出这个相同的城市编号在在原DNA同位置编号的位置的城市编号
                    # 循环查找，直至这个城市编号不再待插入的片段中
. |5 I: F" s. f                    pos = fragment1[fragment2.index(pos)]
                    while pos in fragment2:
                        pos = fragment1[fragment2.index(pos)]
                    # 修改原DNA片段中该位置的城市编号为这个新城市编号
% {; |$ {- h8 ^2 T1 f. E1 T                    offspring1.append(pos)
% V2 V  E  `% {# U0 A. w                    continue
2 |8 M8 t$ E- n- w8 F9 t                offspring1.append(pos)
            for i in range(0, len(fragment2)):
0 Q$ Y8 B& e! \2 C- G2 {3 p                offspring1.insert(k11, fragment2)
                k11 += 1
7 Q. \4 Q: F' u5 J            temp = offspring1.copy()
4 ]5 M( H0 x. V4 j            # 根据 type 的值选择一种变异策略
( f2 p/ Q* A4 J0 @) y            if muta == 1:
; Y0 v) D6 b8 a% e1 b  Y! A                mutation(temp, MUTA_RATE)
) n. U2 Q8 U6 t+ B, x, ~            elif muta == 2:
+ ~6 S9 ]2 W, l: z& @! x: G3 S. ^7 N                mutationII(temp, MUTA_RATE)
            elif muta == 3:
8 v8 h" a2 M6 G  N3 O                mutationIII(temp, MUTA_RATE)
            # 把部分匹配交叉后形成的合法个体加入到下一代种群
, K8 |" L/ R2 t" Z4 g            new_pop.append(temp)
2 z/ @2 w. |6 Q  r, r7 I3 l( p7 `
    return new_pop

def print_info(pop):
( y3 ?! [- U, m0 D    fitness = getfitness(pop)
  e# {* y% z! W4 e5 S4 ^    maxfitness = np.argmax(fitness)     # 得到种群中最大适应度个体的索引
6 Q8 f. F. O7 O( B- j    print("最优的基因型：", pop[maxfitness])
    print("最短距离：",distance(pop[maxfitness]))
    # 按最优结果顺序把地图上的点加入到best_map列表中
    best_map = []
6 F& Z8 p" y+ f7 @2 P    for i in pop[maxfitness]:
! S7 {* ?6 f" w" l        best_map.append(City_Map)
    best_map.append(City_Map[pop[maxfitness][0]])
    X = np.array((best_map))[:,0]
) h8 @! T( D' z/ k    Y = np.array((best_map))[:,1]
    # 绘制地图以及路线
2 D7 Y4 O/ ?& y    plt.figure()
5 ~5 q" c+ n. d8 L1 D    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.scatter(X,Y)
( K0 h, _$ v8 R2 q  ^7 x' x$ }    for dot in range(len(X)-1):
        plt.annotate(pop[maxfitness][dot],xy=(X[dot],Y[dot]),xytext = (X[dot],Y[dot]))
2 E% z' \( G8 [2 e9 I% L2 ^# z    plt.annotate('start',xy=(X[0],Y[0]),xytext = (X[0]+1,Y[0]))
. Y3 Q7 G2 ]' ]) ]9 n    plt.plot(X,Y)

# 3.2 种群规模对算法结果的影响
def pop_size_test():
; @. x7 S' I/ ^% C% V    global POP_SIZE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
    i_list = [10, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
    b_list = []
" _/ ], M$ ^9 ?: Z+ h1 F8 T  g    t_list = []
    for i in i_list:
8 g% Y) i7 g6 P& \: g1 O2 \' |$ Z8 ?        print(i)
        POP_SIZE = i
        time_cost = 0
        min_path = 0
* \# ^% W1 D" u        for j in range(ITE):
; e; H: K# d  i& G% u            time_start = time.time()
            ans = tsp_solve()
            min_path += min(ans)
4 A8 H' y! T  f4 k            time_end = time.time()
            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
+ {' e. N! Z! X    show_test_result(i_list, b_list, t_list, "POP_SIZE")
5 y; V. N% |2 w" |. [
9 T9 S2 g2 |/ {% F# P# j( X# 3.3 交叉概率对算法结果的影响
def cross_rate_test():
    global CROSS_RATE
    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:
5 t- J" f5 N0 A9 F! y        print(i)
6 Y4 s& `, o$ }# @        CROSS_RATE = 0.05 * i
        ii_list.append(CROSS_RATE)
        time_cost = 0
; `- A2 Q5 v+ U% Z. b7 k% D        min_path = 0
        for j in range(ITE):
            time_start = time.time()
4 Q2 r! S& T7 _- W            ans = tsp_solve()
            min_path += min(ans)
; c$ |' t: |+ w, k; ]: Y            time_end = time.time()
            time_cost += time_end - time_start
. B" S  A+ y9 j$ I* ~' j6 p
        b_list.append(min_path / ITE)
" Y: w* ~- D5 `: {" ?8 U! l  @0 c4 C        t_list.append(time_cost / ITE)
    show_test_result(ii_list, b_list, t_list, "CROSS_RATE")

# 3.4 变异概率对算法结果的影响
$ P' T) P7 N4 E8 Odef muta_rate_test():
    global MUTA_RATE
    ITE = 3 # 每个值测试多次求平均数以降低随机误差
: r9 ?( I% p" z' O! u! @" h. D    i_list = range(0, 21)
0 U% D* k5 Y! g7 h3 b; u    b_list = []
    t_list = []
    ii_list = [] # [0, 0.05, 0.1, ... 0.95, 1]
    for i in i_list:
        print(i)
# x; {) W8 I% ~, G5 q        MUTA_RATE = 0.05 * i
        ii_list.append(MUTA_RATE)
        time_cost = 0
% s; z: R6 g" f        min_path = 0
* \$ j! H% b: o: H9 j$ b- k4 `        for j in range(ITE):
            time_start = time.time()
            ans = tsp_solve()
            min_path += min(ans)
            time_end = time.time()
4 d0 ?: z. ?7 e* m8 p            time_cost += time_end - time_start

        b_list.append(min_path / ITE)
        t_list.append(time_cost / ITE)
! A. Z! D( V" [    show_test_result(ii_list, b_list, t_list, "MUTA_RATE")

$ O  n0 y  ], U( h' |" A5 q# 3.5 交叉概率和变异概率对算法结果的影响
! B: S9 i3 K& u* rdef cross_muta_test():
* o; _& c* g, J  O$ F  Y8 j# U( X  ]) g5 d    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)
* E4 f; P' x; k" @1 x    Z = np.zeros(shape=(11, 11))
- W8 T6 u: [5 `- m% t
, o% r2 [' [1 M' E+ m# G/ W    global MUTA_RATE
% p8 ?% u  }+ v    global CROSS_RATE
0 D. @, k$ ^( }    for i in range(11):
        for j in range(11):
+ p" T/ P0 ^( w3 T( J; O4 D            print(str(i) + ":" + str(j))
            CROSS_RATE = X[0,i]
, ]9 Q; ?; J% h. g  G- r            MUTA_RATE = Y[0,j]
- E$ @6 b3 l) D; w5 I            ans = tsp_solve()
            Z[i, j] = min(ans)

    ax = plt.axes(projection='3d')
8 g# d% t% y0 J. V6 V9 m+ g2 c    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')
0 j; H1 l9 E4 l9 V) g    plt.show()
, N( t0 e& f% b# F3 x/ [
# 3.2-3.4 生成参数测试结果的可视化图表
def show_test_result(i_list, b_list, t_list, msg):
7 W# R# K0 }: ?# m" M    ax1 = plt.subplot(121)
; R5 Z, F4 d- V$ n    ax1.plot(i_list, b_list, 'b')
+ Q& v- ^; Y: p7 y4 h    ax1.set_xlabel(msg)
& n. z  _% k$ Y8 D0 t, L    ax1.set_ylabel("Shortest Path")

    ax2 = plt.subplot(122)
+ p' P  g% q3 z    ax2.plot(i_list, t_list, 'r')
! v' m/ r9 p' D/ I    ax2.set_xlabel(msg)
; K# ~4 Y' E# r( f( ?) T  R  X    ax2.set_ylabel("Cost Time")
3 B2 H7 g/ A! R- A( G$ q6 m$ I    plt.show()
, X# a' s; x/ e
# 求解TSP问题并返回最大值
# muta 指定变异方式，sel 指定选择方式
def tsp_solve(muta=1, sel=1):
    pop = []
$ L4 ~! h0 {4 ^& q) O    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
% i9 I5 A# y' ]0 w8 h4 E        random.shuffle(li)
/ K- C/ A& ]( W6 P$ f        l = li.copy()
        pop.append(l)
% d: @7 U$ g* E0 l. n    best_dis = []
& s+ d" {, B+ d    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
1 R2 C# A& l8 }8 C    for i in range(Iterations):  # 迭代N代
) O: r; H! Z5 R+ X8 Q; X* x  ~        pop = crossmuta(pop, CROSS_RATE, muta=muta)
        fitness = getfitness(pop)
8 z: |- v$ e/ [, \9 B        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
        if sel == 1:
            pop = select(pop, fitness)  # 选择生成新的种群
4 E3 Q# ^3 P& C  C. H  |! M1 m        elif sel == 2:
            pop = selectII(pop, fitness)  # 选择生成新的种群
  Z7 L! Q$ I* p' ~& i$ M3 f0 d: M
5 |" n. |! r. m& L    return best_dis

# 4.1 块逆转变异策略对比测试
' O% b% q+ i& l' B6 i9 z* y6 e) w0 ~7 udef opt1_test():
9 }# u; f, B7 k    ITE = 20    # 测试次数
    i_list = range(ITE)
8 i2 ~7 d/ v. ~" S    b_list = []     # 每次求出的最短路径
0 e9 O, o( D( y* E- Q$ N1 `    t_list = []     # 每次求解的耗时
1 [: h5 f9 O6 X+ b# i/ n    b_listII = []
- V% O/ o  j5 u0 L4 g    t_listII = []
    b_listIII = []
    t_listIII = []
0 R; Z4 s# E$ }( q( B% @
    for i in i_list:
        print(i)
        # I. 原两点互换异策略
/ c% O, m& {% A% m, U        time_start = time.time()
  X5 H; Q5 g9 J        b_list.append(min(tsp_solve(muta=1)))
        time_end = time.time()
4 \  ]) z7 Q6 Q5 M- ?        t_list.append(time_end - time_start)
        # II. 块逆转变异策略
        time_startII = time.time()
* X  O1 z2 \0 l+ @        b_listII.append(min(tsp_solve(muta=2)))
        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
: b# b  K/ {: Y; w        # III. 同时使用上述两种编译策略
        time_startIII = time.time()
/ Z0 {2 O* W6 G9 \$ f) S        b_listIII.append(min(tsp_solve(muta=3)))
        time_endIII = time.time()
        t_listIII.append(time_endIII - time_startIII)

    # 做排序处理，方便比较
    b_list.sort()
) S+ S* c" c* ^  F; p! N    t_list.sort()
    b_listII.sort()
: h3 _% r( c% V4 @" u/ g    t_listII.sort()
    b_listIII.sort()
    t_listIII.sort()
' n3 |8 b$ A. e* o; C
    ax1 = plt.subplot(121)
    ax1.plot(i_list, b_list, 'b', label="Origin")
. M  ]3 w) \. t/ @  A: L& K    ax1.plot(i_list, b_listII, 'r', label="Block-reversal")
    ax1.plot(i_list, b_listIII, 'g', label="Origin + Block-reversal")
2 ^; J3 F9 U8 M3 m6 Z" H    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")
' S0 _9 @7 s  c) U) D9 K    ax2.plot(i_list, t_listIII, 'g', label="Origin + Block-reversal")
5 L' s0 s9 C6 @: z  N    ax2.set_ylabel("Cost Time")
    plt.legend()
: }" `2 z0 x3 g3 W8 `    plt.show()
9 ?6 x& ?' j6 n9 @3 K
" g$ S; a( v4 p0 q; M# 4.2 锦标赛选择策略对比测试
! O, A5 A7 b3 f" G5 p) A: [def opt2_test():
    ITE = 20  # 测试次数
    i_list = range(ITE)
    b_list = []  # 每次求出的最短路径
) {# k8 C) B1 l    t_list = []  # 每次求解的耗时
6 f5 b, P7 K: V% U, M3 j    b_listII = []
# M- a2 R0 |0 v- Z; |7 Y    t_listII = []
2 L3 q* A) M# k0 @8 @2 }4 ]  e    b_listIII = []
    t_listIII = []
! C) _1 T4 n8 N* d9 W
$ c. s# x! G+ B9 |6 I7 S/ m    for i in i_list:
        print(i)
        # I. 原赌轮盘选择策略
( [# H# g' c- @        time_start = time.time()
        b_list.append(min(tsp_solve(sel=1)))
2 ^, [% s# B: ^/ ?/ @6 q- a        time_end = time.time()
        t_list.append(time_end - time_start)
        # II. 锦标赛选择策略
        time_startII = time.time()
        b_listII.append(min(tsp_solve(sel=2)))
5 _, \* x' X  c, d( r        time_endII = time.time()
        t_listII.append(time_endII - time_startII)
. [7 [& H) [& K, @: N* [        # III. 锦标赛选择策略 + 两点互换变异 + 块逆转变异策略
        time_startIII = time.time()
        b_listIII.append(min(tsp_solve(sel=2,muta=3)))
6 j. h. a1 O' M7 M' r: o4 J' {        time_endIII = time.time()
% ?5 q! g+ @3 p. e. b        t_listIII.append(time_endIII - time_startIII)

    # 做排序处理，方便比较
    b_list.sort()
    t_list.sort()
    b_listII.sort()
7 s' C2 O  r, d1 J* \    t_listII.sort()
    b_listIII.sort()
    t_listIII.sort()

    ax1 = plt.subplot(121)
8 ^( x! L% C" ^% D  e5 y4 h    ax1.plot(i_list, b_list, 'b', label="Origin")
. H( k8 @6 D/ \; Q4 [# f' o8 H    ax1.plot(i_list, b_listII, 'r', label="Tournament")
    ax1.plot(i_list, b_listIII, 'g', label="Tournament + Block-reversal + Origin")
: ?, e+ p. V4 c    ax1.set_ylabel("Shortest Path")
    ax2 = plt.subplot(122)
    ax2.plot(i_list, t_list, 'b', label="Origin")
1 @/ h' D+ a  w+ `. b5 s5 W    ax2.plot(i_list, t_listII, 'r', label="Tournament")
    ax2.plot(i_list, t_listIII, 'g', label="Tournament + Block-reversal + Origin")
3 N: c/ w+ k$ ^7 O    ax2.set_ylabel("Cost Time")
; H& l1 }8 @1 U9 h8 p# v3 E9 B- A    plt.legend()
, k8 a  w; q, ]5 Q$ S9 x    plt.show()
! S# ~$ p7 d% z' T, R( b3 M
: i) p: m1 E0 M' y0 S# 3.1 原程序的主函数 - 求解不同规模的TSP问题的算法性能
def ori_main():
    time_start = time.time()
    pop = [] # 生成初代种群pop
    li = list(range(DNA_SIZE))
. f& Q" K3 I6 [6 x* Y    for i in range(POP_SIZE):
        random.shuffle(li)
. B) u6 a' ^/ L7 ]! i' q        l = li.copy()
% X$ U, Q# ^  v3 l& N        pop.append(l)
    best_dis= []
2 {/ L8 \# l" v' k! D/ f* ?3 a    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
$ v7 F  \" a% I3 |/ X0 i" }8 x        pop = crossmuta(pop, CROSS_RATE)
5 p! c' I2 ~2 w7 u( B4 H        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
        best_dis.append(distance(pop[maxfitness]))
. @. e# g) Z1 F- w7 O/ V- L        pop = select(pop, fitness)  # 选择生成新的种群
* x4 l; L8 G$ p" k- b. t4 S
: Y" _: k  Y  F# O. Y    time_end = time.time()
    print_info(pop)
    print('逐代的最小距离：',best_dis)
9 I! ~% k# c% O$ q8 N    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
    plt.plot(range(Iterations),best_dis)

2 X* ^( F1 e/ t, B5 z  J# 4.1 块逆转变异策略运行效果展示
9 Z- G9 s* c2 _+ Z( E8 m- b4 _$ f7 M& gdef opt1_main():
    time_start = time.time()
! s2 S2 R4 F1 A6 |    pop = []    # 生成初代种群pop
    li = list(range(DNA_SIZE))
    for i in range(POP_SIZE):
        random.shuffle(li)
        l = li.copy()
/ n6 H( _, E( ^        pop.append(l)
    best_dis= []
    # 进行选择，交叉，变异，并把每代的最优个体保存在best_dis中
    for i in range(Iterations):  # 迭代N代
        pop = crossmuta(pop, CROSS_RATE, muta=3)
4 v: L) i& X/ i5 ^" L        fitness = getfitness(pop)
        maxfitness = np.argmax(fitness)
$ }7 u+ i9 |0 O0 A4 P) ?        best_dis.append(distance(pop[maxfitness]))
        pop = select(pop, fitness)  # 选择生成新的种群
, U4 {' ~9 G1 t: }& _3 i
- X7 k% V/ {! |- _    time_end = time.time()
# Q. D: K* G' {) a    print_info(pop)
# U& k  T; {& e) ]& \7 Y1 b    print('逐代的最小距离：',best_dis)
    print('Totally cost is', time_end - time_start, "s")
    plt.figure()
    plt.plot(range(Iterations),best_dis)

9 H: M" W8 U+ Y5 z( o1 B5 j9 Uif __name__ == "__main__":

5 g3 S3 [) e0 a4 q1 Q2 p    ori_main()    # 原程序的主函数
9 f5 ]* N# G8 B/ K/ n    opt1_main()   # 块逆转变异策略运行效果展示
6 b- w2 y4 m' x4 {6 x7 _# n. X    plt.show()
    plt.close()
" |- E+ W% _2 k  `
    # opt1_test()   # 块逆转变异策略对比测试
    # opt2_test()   # 锦标赛选择策略对比测试

/ h( U9 _8 m  P3 C7 N0 A  a    # pop_size_test()       # POP_SIZE 种群规模参数测试
    # cross_rate_test()     # CROSS_RATE 交叉率参数测试
! _( i! t2 [) z6 G& |" K) e    # muta_rate_test()      # MUTA_RATE 变异率参数测试
4 N. a' d3 O  r* g    # cross_muta_test()     # 交叉率和变异率双参数测试
1 F7 l6 s5 T- @5 k
* X$ O3 @; x. r' o
( q( \+ @$ l5 `3 n# z8 c  d5 [1
2
% W9 U6 |% Z7 X% `3 i: r3
/ r5 f& M5 j, P4
/ V3 R8 s9 e- }+ k$ c5
  ?2 M: [4 |5 ^# M1 {9 m9 R6
7
8
; N' v* g* f9 M  s. {. _9
10
11
- z3 \9 X0 G+ l12
13
0 J2 A2 l! N" f3 D$ D/ }/ ?. E14
15
16
! K9 }' h( R  q5 G1 N+ P. i, z17
) F, B# h8 g: W# Y$ ?$ b18
* p/ ]: m$ T! ^$ X. C5 _19
( U# P& H' A$ ]# I- h& Y20
# j/ D. w! B% u21
$ b4 ~7 w3 _( W% Z22
23
7 I' E( M& b  S9 x! v9 u24
$ _8 ?; S9 J8 i: ?25
26
27
! L3 |/ M+ U8 A! F5 G+ }28
4 ^5 L" u. _- d9 \) x+ N: O29
6 L2 d1 D4 x3 S) f) E30
. O& l. Z: q7 H+ J6 q% \0 {31
32
: f( l, V2 ^4 `% ~33
% R4 T* S+ }% w, `34
, i9 z, V4 D! P( m3 L/ X35
' ^& A! {. G( b# F1 z5 Q36
, \1 y5 j% \1 J5 f- F( p0 n& E37
38
39
! k4 ?; {/ w( E/ N. ?40
7 Q0 _% B4 @6 J  ^  G) ?$ o5 h41
- h$ ?+ A4 |8 y42
$ L0 x/ g7 C  D4 J4 p43
44
45
46
47
; g2 [# G% V: v7 p+ [# h48
49
! d" U1 j1 z$ t50
! j. E$ V- e8 B& k5 l4 h: y2 t: o51
( l- K7 H6 F* {" U3 @52
1 g# n- u% t0 a$ `53
54
% a$ C& p3 d1 c8 B. Z9 Z& A) e55
56
; E8 g& K4 @$ n+ L' ?& c57
- g( ~8 @5 b7 E7 j1 A0 W% `58
59
60
4 e( r6 L4 ]" h. t- ]. H61
7 }  Z, M6 ]  t4 N! ]- |$ h62
; b) }! A7 T6 e5 z) b63
64
& p- _: ?" \3 g- Q5 q65
66
67
68
# r  H* v* p( T# c) l69
70
3 n9 d  h8 U6 V* V5 _71
2 |# [! X8 y; F5 c0 M$ a72
; c3 r# v. V  d73
1 W2 z* t$ `7 {4 @% g% y3 V74
3 l# l% v1 S1 E7 i/ s75
76
% \# ?4 g7 U) z0 A# l77
* H3 f! t( w, O78
9 z( E6 ?4 ^* |! O# W" o! ^  F* G% Q79
80
0 w  R" k" S9 x1 T81
! K7 v: I  J3 M. }2 X/ I8 w82
3 {$ h% t$ t+ U( y83
* R9 @0 ~3 {+ y! z  f. v84
85
86
0 Z( M+ Q  D" `, Y: \87
$ k6 h( U4 z7 B* d+ L0 {88
+ N$ S6 b6 r/ W! T5 y  }( V7 v89
6 ]% }0 T3 W5 Y9 }- U90
91
92
93
94
- h' |( }- I* `: z$ J95
96
7 H; Q5 z6 E6 {1 o* i5 S' l5 z97
: v' Q1 u9 N. e% F: f7 w( H98
+ x3 p9 N" B. x; i5 y99
100
101
$ T7 \5 H& R0 ^0 X0 {. O' ?102
. q$ F: f6 Q* _1 b2 [% ]103
104
105
/ ^9 @( X1 T" L% p; |106
107
108
0 e( W; w; d6 Z6 S1 z0 O6 t; M109
5 U; c8 q# e, h8 y$ l" M) y/ }$ w110
: ^$ h% Z3 m" Z4 Z- G111
112
% B: I: G- g' T' y. I113
114
- C. X4 M+ s, q0 |7 y8 `" a115
& f  ]& T: {8 |* a7 n) W116
117
118
  d, _" m8 {: |! H* M* j1 u( v' q119
9 g. L0 P% P; p* B120
121
122
123
124
( g5 W5 V! @0 W8 }. q125
126
  D8 V" D' \) B" d9 ?2 Y4 @4 ?127
7 q) n* {# Z, ]  c: x128
8 B* C6 o* C' T: G  G129
130
131
132
133
6 O  d- g/ }2 K134
135
8 F/ l7 h9 a+ _0 o( W& H$ P5 w$ K136
137
138
139
140
141
142
143
144
. S" @* H1 a8 ^/ B8 A( p" @$ \' k145
146
, @) @: H; a) h147
) U- X/ q, R, C( u! O2 Y4 b148
149
  b% D6 K7 N) i8 h. o150
9 m8 f* o, a; b# ]4 U0 W  y151
$ ?0 f% J9 m* Z& z) B6 [152
153
154
155
156
) F- L' B: b- A, h+ v+ }! T/ |157
" R7 ]4 u' f5 A/ |+ ^/ d158
1 J3 l: D/ u$ p! i5 c/ A2 a2 N159
5 Q- m6 m* X) C, [6 u* @: `160
: ?& A( m9 J' J161
. y$ H5 R2 U1 ?' ]6 v9 o162
2 M5 v' V& \9 G. z9 r# M163
164
165
166
167
168
& g2 w( z4 \% c6 y' ?& A169
+ q# z/ k3 v) N, A! r170
! ^4 b6 [) h/ b- R171
' N1 I% L& X0 }- I; P+ r172
173
+ ?* p( j& @+ n% z0 \4 ~174
1 C- T( d, ]* A/ ]6 s175
; q. j: V8 y# Q" s! s176
177
+ g9 B# `- D; U, |178
179
( y, k$ H! u* R* D: r" D. i180
181
182
183
+ y9 q2 q  r  u. @$ x2 _! w9 i184
185
$ n3 k8 Y6 L* i4 V7 ?186
187
. @1 a( ?7 I8 F5 C3 \188
) Z; {) \" s; q189
# u: W" o; U9 V! B190
191
192
$ w7 k# r4 ^! [8 \& h193
194
195
196
197
3 G4 F: T- }3 _" b198
199
200
( G, |! C9 A9 g$ ?$ H' _201
202
/ ^& d! g2 h$ T5 T! k203
204
* {1 p0 T/ g1 t) R% S. S' R205
2 [$ I/ o0 C9 Y: p! G  p  M7 J4 P206
207
! g& j9 M2 C0 J8 p208
  h! a6 w" M6 Z9 R5 v209
210
211
212
213
$ e1 ~4 h5 J" P+ A5 f" }214
215
& ]" w  V8 A- _  X7 c9 _  c1 `! k6 y6 w216
2 g( [1 Z7 T8 {2 w217
& z, n! Q, B, y5 I4 k0 h218
& O5 _% ^, R; C219
% Q! d0 L/ ]- Y# l0 u1 |220
- m/ w" f  r" g/ d221
% K/ ~: @+ P& h$ w2 z9 P222
3 Q& k: ]# f. Q4 T% V: k; Y* x223
3 c- P" j3 ?, s9 f# ^9 T, T224
225
" z# e. |! k1 ~1 E  Q  ~2 X" U  H226
227
! T7 D0 H# m4 s1 I" B228
229
) t+ T/ v" Q' q/ S2 B8 Z230
# ]' v9 J& v( Y' h4 ^& Z231
: K; `9 B+ w6 q5 {7 A232
233
234
. t: K' J" o! W5 w235
# |8 s$ C- o3 {236
/ F0 w9 A: g- i/ d- N237
& o& ~( r% e# O* R6 }238
239
240
! E( U. A; ?9 X/ ?$ ?; P4 f8 }2 ~241
242
243
6 M- [+ \0 J6 j244
/ n# q! b% G- x+ w& V, A0 a245
' G% O6 D5 Q# L, V, s3 f% s9 Z246
247
248
5 ~" Y6 I* s$ S5 C5 h249
250
251
252
253
254
255
256
9 P. B# l0 n, P; I, J( k' [257
258
# Q. r6 Z9 X( r) S259
260
' T. x0 [( W% J261
0 j2 r. S7 [& b; m) h262
263
4 B! I6 _0 o# i' V6 J7 |4 b264
6 X5 H6 M+ T2 v265
+ x# H8 @5 H- k! C! N266
267
! Z; s8 B; \, z9 r) a4 J268
269
270
271
272
7 J1 {6 m$ [9 c1 \273
274
275
/ k% w7 q! k. \! f" n276
277
278
279
$ n7 F2 G+ @: r280
6 G6 q  b. I! g& O. K/ X, U281
282
283
5 C+ \+ ^! g& r0 y5 L284
285
286
287
7 d* ~4 f2 {! ?& N288
# r; w1 J4 \/ U7 b0 D! ~2 T/ P289
290
291
. ^8 v. l2 K# y5 e* w, G292
% j4 {4 n, ^" N3 Z4 [293
294
295
+ y2 C7 x! T3 C! N- k# C" N296
  w. C. p9 b8 I2 A# D+ L9 V& [297
298
299
300
1 d, E* Y: Y7 n, @) Y301
302
303
304
$ B0 p9 C$ T( M/ q* ^/ E, Y305
306
( s  E/ X+ i5 x* l9 z# z: B& `9 n307
308
+ V9 w+ [9 G. G) b$ `309
310
311
/ v: u% a; o( o' W/ O1 R+ s& z312
313
; c9 J, g5 F$ b1 B! o314
6 p) ~# m* U/ R/ }, w315
316
317
: g/ _) {# v8 i) s318
319
320
# H+ g% p3 k" q( F321
  y( _6 a4 s8 M: Q( R7 Y. b' j; @322
323
8 w4 ^. V8 u% V5 w1 P5 M324
, G4 N2 Q2 ~; @# ]- `% ?  ?325
* a% Q5 T8 S% k+ l* r  H326
327
328
+ B+ f6 r' v- b( S/ K; h; T- V, M$ @329
330
4 ~4 K* h' Y$ g+ Y331
332
333
2 N. o- |1 M6 ^* v/ H& v- Y1 X9 h5 o334
335
. Q9 P0 m! H& {1 R" d& v6 i& H$ ^336
337
338
# P: N- C2 @( n2 y% `1 u0 o339
340
2 B7 O( Y" ?0 w' n341
342
343
344
* p$ S4 u; ~/ ?345
346
347
" E& B5 H/ B& A( T0 O5 O348
* f. x- u8 c- n- G8 L7 ?349
350
; b5 O% R7 U! ^0 ^6 {. ?" i351
7 _4 h( ]2 W1 ?352
- ]7 J; w# D) v. c353
354
355
9 B8 v* f1 O: @5 J' E356
357
358
1 N) n. S% z* m) R5 i359
. n- ?. {: _: Y: j- k, o360
" v" h+ ?$ A$ J" _361
362
363
364
  K( p3 i- |' D! \365
366
4 S( l% Y) \# K7 w5 K* o3 r367
6 a2 W% n7 l  i/ u- X368
2 a* y- T% u; r* L2 w+ n, }369
& x* l: S- S; y370
1 u: z1 T4 J2 F4 `/ G371
372
4 r# k) t1 C8 o& W5 B373
- {9 `: b( R% v5 v* i% T5 s* @374
0 o( M0 M2 n! v' H0 `5 L" i1 \5 d375
: r5 Y& J5 R% `  X376
$ z! W1 @. e) B377
/ U& {, n, c! ?9 g. D& j6 t378
379
  w' z% f5 E! S7 K380
4 G6 }8 v. _1 ^  u: c6 c- Z, @381
$ e7 z# I( {; y$ ]4 s( s3 M5 X6 s382
( q; O9 M! A& l, t/ c# t. z383
4 K; o1 q; y, G384
% V+ ]6 L) L. b: L( g385
386
, V+ Z3 I; |) d5 V$ I387
388
389
390
7 t1 t% V, O2 L( b& j391
# Q5 p1 g( L1 l392
5 i* ]8 U# z1 O" x7 j, z; e; }% l393
394
395
3 c( e1 x# O2 C  ?5 {2 W396
397
398
399
1 J2 g$ ^, f, E( D400
9 K: _/ i: g2 |7 ^) A- k401
402
403
( y$ ~  T7 a5 B* k7 i404
405
* f% a2 i0 V& n1 _, x406
407
408
409
. [# ~7 L! R9 c0 z/ u8 M410
411
412
8 f- p% q( G- ?& v" _8 I( ~: J3 ]413
$ g. X3 I& Y/ t; _% k414
5 e$ S" n6 j4 D+ X6 J5 s415
416
0 ~" {. z. r3 i: n7 G417
1 a! j* n" u! s. Z1 Z418
, T' Q3 u; C5 z7 _$ D) y7 s: {419
# i: g; ^+ b7 w/ N( Y2 {% z420
421
7 {! }1 ~% x% V0 V# C# C+ ]6 Q422
9 A3 y  p8 ^: }  |) s423
424
425
% J! b- h" b6 I4 v3 D# h( a0 _3 }2 f426
427
0 U: H3 r1 M- N" S! s$ ^, O2 @# o" a  c2 n428
429
430
431
432
433
9 V' a+ l, y- Q: H  ]434
; q; @: N- V7 E8 H+ v& ^, t& m435
' r6 M" w2 U+ b1 V436
- y1 W) W1 ]2 Q( E$ v" E  w437
' T0 J% A% Y+ ]1 a! X- p438
439
440
441
8 r+ ?; ~/ ?! E5 x442
443
* l- N/ }0 g. x6 V444
4 _+ c* ?9 D3 m# D6 j" F445
* r' \! Q8 s4 m* B446
447
448
449
3 M: ?( w0 n$ X450
" U: ]8 L+ B8 ]5 W( {$ ?! E+ V451
- V9 R+ ?8 j' R" z  q452
453
454
; M+ v4 H. L- i8 `/ ]- L455
456
457
* D0 j7 v! c; h- t7 f% K% L458
459
460
461
462
+ I& W1 q. y5 P  T8 o463
464
465
466
& A0 Z% i4 {4 P467
468
( ~' d8 C/ w0 Z1 u. [" l469

% w4 z. k" t0 _9 N. A
( N/ F8 Z% t+ i
3 c) ]& N" T: `7 ~$ i' E8 d7 [
2 B9 v6 n8 C; t
( t7 p1 g' K. o  w( _& j
" C: I. f' N& [" e* L1 |" B

* D% J; A, ]. g* |2 g8 o, r8 _

, h( V$ m5 [  c# M" Q' m7 k4 d
. X+ T' S; z7 v5 o! e" g



+ k+ r; h' ?+ A. |
  ~/ L7 x  x9 @5 t/ p, f% l
5 b& x( h% O- e0 [4 M5 ^# u
$ T/ n  K/ E" y# Q8 {! H

3 r* Z0 i- T* }5 J& E* k

7 t- t% @7 ^8 v9 B3 i) C3 |5 p7 S
2 _3 Q! P8 z5 L# j; V


" a  d" i8 ~9 u
$ f8 m% ?( @* r* n$ ~' M1 H+ l————————————————
版权声明：本文为CSDN博主「biyezuopin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& q+ k5 Q  U! e原文链接：https://blog.csdn.net/sheziqiong/article/details/126803212


# d6 m# s% t. U1 C
# ]- c' @: Z" B7 [6 E