基于DEAP库的python进化算法-4.遗传算法求解TSP问题

1147-柳同学

发表文章数:589

热门标签

,
首页 » 算法 » 正文

一.前言

本文将介绍以下内容:

  • TSP问题的定义与运用遗传算法求解
  • 对比遗传算法与贪心算法及其改进型在用时和精确度两方面的表现
  • 探讨可能改进的方向

二.TSP问题的定义与GA求解

1.TSP问题简介

旅行商问题描述:
基于DEAP库的python进化算法-4.遗传算法求解TSP问题
基于DEAP库的python进化算法-4.遗传算法求解TSP问题

2.TSP问题的遗传算法求解

通过之前对DEAP的解读,我们很容易就能基于该框架,写出一个求解TSP问题的GA算法。

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import distance
from deap import creator,tools,base,algorithms

# 定义TSP中的基本元素

# 生成城市坐标
# [n,2]的np.array存储城市坐标,每行存储一个城市
def genCity(n,Lb = 100,Ub = 999):
    random.seed(42)
    return np.random.randint(low=Lb,high=Ub,size=(n,2))

# 计算并存储城市间距离矩阵
'''
    scipy.spatial.distance.cdist(XA, XB, metric='euclidean', *args, **kwargs)
    计算两个输入集合中的每对之间的距离
    参数:
        XA:
        XB:
        metric:要使用的距离度量
    返回矩阵
'''
def cityDistance(cities):
    return distance.cdist(cities,cities,'euclidean')

# 补全路线
# 序列编码时,缺少最后一段回到原点的距离
def completeRoute(individual):
    return individual + [individual[0]]     # 不要append

# 评价函数
# DEAP要求评价函数返回一个元祖
# 计算给定路线的长度
def routeDistance(route):
    '''
    :param route: 一条路线,一个序列
    :return: 路线长度
    '''
    if route[0] != route[-1]:
        route = completeRoute(route)
    # 存储路线长度
    routeDist = 0
    # i,j分别是相邻的坐标点
    for i,j in zip(route[0::],route[1::]):
        # 这里直接从CityDist变量中取值了
        routeDist += cityDist[i,j]
    return (routeDist),



# 设计GA算法
n_cities = 30
# 随机生成n_cities个城市坐标
cities = genCity(n_cities)

# 定义问题
creator.create('FitnessMin',base.Fitness,weights=(-1.0,))       # 单目标最优化问题-最小值
creator.create('Individual',list,fitness=creator.FitnessMin)

# 定义个体编码-随机序列编码
toolbox = base.Toolbox()
toolbox.register('indices',random.sample,range(n_cities),n_cities)      # 创建序列
toolbox.register('Individual',tools.initIterate,creator.Individual,toolbox.indices)

# 生成族群
pop_size = 100
toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)
pop = toolbox.Population(pop_size)

# 注册所需工具-评价,选择,交叉,变异
cityDist = cityDistance(cities)
toolbox.register('evaluate',routeDistance)
toolbox.register('select',tools.selTournament,tournsize=2)      # 锦标赛选择
toolbox.register('mate',tools.cxOrdered)                        # 有序交叉
toolbox.register('mutate',tools.mutShuffleIndexes,indpb=0.2)    # 乱序突变

# 数据记录
stats = tools.Statistics(key=lambda ind : ind.fitness.values)
stats.register('avg',np.mean)
stats.register('std',np.std)
stats.register('min',np.min)
stats.register('max',np.max)

# 调用内置的进化算法
# verbose=True时可以直接打印迭代过程
resultPop,logbook = algorithms.eaSimple(pop,toolbox,cxpb = 0.5,mutpb=0.2,ngen=100,stats=stats,verbose=False)

# nevals代表该迭代中调用evalute函数的次数
logbook.header = 'gen','nevals','avg','std','min','max'
print(logbook)

运行结果为:

gen	nevals	avg    	std    	min    	max    
0  	100   	13905  	987.447	11327.4	16521.7
1  	61    	13533.8	923.422	11283.5	15646.5
2  	70    	13002.9	967.082	11136  	15867.5
3  	71    	12916.6	856.845	10958.5	14876.1
4  	66    	12861.1	930.963	11037.2	15468.5
5  	56    	12748.9	916.558	10881  	14970.5
6  	62    	12747.8	871.961	10881  	14967.1
7  	72    	12607.9	910.197	10555.9	15153.9
8  	59    	12497.1	911.965	10783.3	15204.1
9  	54    	12388.3	842.306	10992.9	14890.8
10 	58    	12263.2	796.405	10178  	14155  
11 	63    	12236.1	965.314	10178  	15492  
12 	66    	11962.1	917.961	10090.6	14238.2
13 	68    	12032.9	1147.85	10057.7	15234  
14 	61    	11957.3	1142.2 	9946.57	14662.5
15 	60    	11792.6	1105.86	9770.42	14937.2
16 	57    	11724.1	1218.65	9602.84	15259  
17 	54    	11494.8	1141.5 	9602.84	15031.8
18 	64    	11677.5	1217.51	9896.24	15745.4
19 	64    	11774.3	1301.45	9684.25	15591.7
20 	63    	11375.1	1129.04	9374.93	14833.9
21 	55    	11115.8	1154.49	8875.29	14531.9
22 	54    	11133.4	1379.22	8875.29	15757  
23 	59    	10705.7	1193.61	8695.99	14909  
24 	52    	10581.9	1184.62	8695.99	14457.8
25 	54    	10514.7	1078.77	8695.99	13799.3
26 	59    	10490  	1105.01	8135.24	14191.1
27 	59    	10526.5	1089.06	8866.46	13689.4
28 	59    	10515.7	1214.76	8564.63	13735.2
29 	58    	10480.4	1166.97	8564.63	13463.3
30 	48    	10313  	1048.16	8732.43	13588.2
31 	63    	10470.5	1399.46	8732.43	14813.3
32 	54    	10326.2	1013.45	9084.97	13077.1
33 	66    	10597.8	1325.74	8761.97	14983.8
34 	54    	10421.8	1144.94	8298.04	13616.5
35 	62    	10408.3	1248.3 	8437.56	13901.5
36 	60    	10360.6	1429.68	8890.4 	16117.3
37 	61    	10537.1	1481.32	8609.69	14697.6
38 	58    	10499.8	1372.65	8320.62	14945.7
39 	53    	10286.9	1209.59	8302.42	14295.7
40 	59    	10280.1	1449.84	8302.42	14940.3
41 	64    	10175.8	1233.66	8302.42	14281  
42 	70    	10409.8	1485.82	8302.42	14267  
43 	59    	10205.6	1329.65	8302.42	14597.4
44 	56    	10112.7	1497.19	7947.92	15187.4
45 	53    	9983.19	1454.46	7947.92	14201.8
46 	65    	9963.85	1399.44	7947.92	14334.8
47 	65    	9871.06	1364.55	7947.92	15085.1
48 	52    	9971.21	1408.68	8135.39	14890  
49 	53    	9763.71	1411.7 	8093.15	14096.9
50 	56    	9581.82	1431.93	7773.34	14029.3
51 	55    	9530.54	1322.92	8105.42	13764  
52 	51    	9607.83	1649.9 	8105.42	14938.6
53 	63    	9488.71	1398.09	7650.16	13011.8
54 	52    	9393.66	1513.02	7650.16	14781.7
55 	56    	9406.05	1646.88	7650.16	14196.4
56 	55    	9516.81	1781.71	7650.16	15143.1
57 	56    	9492.04	1747.48	7650.16	13876.7
58 	68    	9742.63	1823.08	7773.34	14642.9
59 	65    	9331.65	1461.86	7773.34	14035  
60 	58    	9440.05	1576.55	7773.34	13559.7
61 	65    	9455.18	1766.67	7773.34	15889.7
62 	61    	9415.84	1577.91	7617.54	13858  
63 	66    	9695.44	1726.31	7773.34	14260.8
64 	57    	9435.75	1626.27	7697.7 	14144.8
65 	74    	9542.32	1699.96	7593.71	14171.6
66 	64    	9354.98	1684.85	7593.71	14749.2
67 	53    	9222.92	1608.2 	7356.44	14708.9
68 	57    	9253.25	1651.72	7356.44	14528  
69 	49    	9097   	1582.46	7327.67	14033.6
70 	72    	9321.56	1627.13	7327.67	13799.7
71 	67    	9361.84	1632.71	7162.99	13300.2
72 	57    	9629.4 	1884.54	7162.99	15302.9
73 	67    	9491.97	1856.38	7162.99	14706.5
74 	53    	9018.41	1513.69	7162.99	14466.6
75 	52    	8704.3 	1334.54	7162.99	14336.8
76 	62    	8925.51	1605.47	7231.18	14763.1
77 	60    	9155.62	1887.79	7231.18	15334.6
78 	60    	9029.67	1896.93	7231.18	15283.6
79 	59    	8822.48	1618.43	7192.86	13292.7
80 	72    	8792.94	1435.65	7061.91	13518.3
81 	63    	9024.41	1708.19	7061.91	13529.7
82 	52    	8676.01	1522.67	6991.89	13117.7
83 	58    	8702.32	1594.07	6991.89	13795.2
84 	59    	8839.74	1571.26	6991.89	13520.7
85 	55    	8645.57	1445.9 	6689.18	13648.1
86 	53    	8788.67	1554.28	6991.89	13433.3
87 	56    	8911.43	1796.72	7050.3 	13962.1
88 	56    	8689.47	1675.97	6995.87	13783.2
89 	66    	8737.98	1612.9 	7159.97	13994  
90 	64    	8832.29	1707.66	6913.82	13236.6
91 	69    	9020.72	1731.24	7159.8 	14517.6
92 	67    	9057.28	1702.93	7019.29	14042.2
93 	58    	9019.33	1678.86	6943.83	13899.1
94 	63    	8784.99	1670.63	6828.29	14774.9
95 	47    	8505.37	1427.31	6828.29	13624.7
96 	60    	8616.91	1618.61	6828.29	14351.2
97 	52    	8825.24	1837.8 	6828.29	14063.8
98 	72    	8838.9 	1787.68	6828.29	14480.9
99 	58    	8640.73	1563.11	6709.19	13229.3
100	64    	8421.83	1598.63	6709.19	14738.6

结果可视化代码

# 路径可视化
def plotTour(tour,cities,style = 'bo-'):
    if len(tour) > 1000:
        plt.figure(figsize=(15,10))

    start = tour[0:1]
    for i,j in zip(tour[0::],tour[1::]):
        plt.plot([cities[i,0],cities[j,0]],[cities[i,1],cities[j,1]],style)
    plt.plot(cities[start,0],cities[start,1],'rD')
    plt.axis('scaled')
    plt.axis('off')

# tour是最优路径
tour = tools.selBest(resultPop,k=1)[0]
tourDist = tour.fitness     # 评价函数那一块
tour = completeRoute(tour)
print('最优路径为:'+str(tour))
print('最优路径距离为:'+str(tourDist))
plotTour(tour,cities)
最优路径为:[5, 25, 18, 27, 13, 7, 19, 10, 2, 3, 12, 0, 16, 28, 4, 23, 14, 6, 1, 26, 8, 29, 17, 24, 22, 15, 11, 21, 20, 9, 5]
最优路径距离为:(4649.586570648632,)

基于DEAP库的python进化算法-4.遗传算法求解TSP问题
对训练过程可视化

gen = logbook.select('gen')
min = logbook.select('min')
avg = logbook.select('avg')
fig = plt.figure(figsize=(12,8))
fig.add_subplot()
plt.plot(gen,min,'r-',label = 'Min Fitness')
plt.plot(gen,avg,'b-',label= 'Avg Fitness')
plt.xlabel('Iteration')
plt.ylabel('Fitness')
plt.title('iterations_fitness_SGA')
plt.legend(loc = 'upper right')
plt.show()

基于DEAP库的python进化算法-4.遗传算法求解TSP问题

三.算法对比分析

1.最近邻算法:nn TSP

穷举法能够保证求出TSP问题的最优解,但是其耗时会随着问题规模的扩大而剧增。
假设求解一个规模为10的TSP问题需要1秒,那么可以估计对于更大规模问题,穷举法所需要的时间:
基于DEAP库的python进化算法-4.遗传算法求解TSP问题
而在应用于实际时,TSP问题的规模往往成千上万,用穷举法求解显然不现实,因此我们需要更加有效的求解方法。

在考虑问题时,一般算法设计的策略有以下几种:

  • 暴力破解:列出所有可能性,一一尝试并最终给出答案
  • 近似算法:如果问题的最优解或者准确解很难给出,那么可以尝试找出问题的次优解或近似解
  • 贪心算法:对于多步骤问题,可以在每一步都取得局部最优,并重复直到问题解决
  • 迭代算法:用一个算法求解,另一个算法来提升解的有效性
  • 聚合算法:在算法中准备一系列算法,依次尝试并取得最好结果
  • 分而治之:将一个问题划分为一系列子问题,依次求解后组合成最好结果
  • 参考已有的算法

强烈推荐Peter Norvig的[这篇文章]
其中详细分析了TSP问题的各种求解思路和python代码的实现
最近邻算法就是同时包含了近似算法和贪心算法思想的一种算法。
nn TSP可以描述为:

  • 从某个城市出发
  • 移动到离现在所处城市最近的且没有访问过的邻居

nn TSP 代码实现

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import distance

# 定义TSP中的基本元素
# 生成城市坐标
# [n,2]的np.array存储城市坐标,每行存储一个城市
def genCity(n,Lb = 100,Ub = 999):
    random.seed(42)
    return np.random.randint(low=Lb,high=Ub,size=(n,2))


# 计算并存储城市间距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,'euclidean')


# 在未访问的列表中寻找当前位置的最近邻
def nearestNeighbor(cityDist,currentPos,unvisited):
    '''

    :param cityDist: [n,n]记录城市间距离
    :param currentPos: 一个数字,指示当前位于的城市
    :param unvisited: 一个列表,指示当前可选邻居列表
    :return: 返回最近邻的索引与距离
    '''
    # 与邻居的距离
    neighborDist = cityDist[currentPos,unvisited]
    # 得到最近邻的索引
    # 贪心 -每一步最小
    neighborIdx = np.argmin(neighborDist)
    # 找到最近邻
    nextToVisit = unvisited[neighborIdx]
    # 得到与最近邻的距离
    dist = neighborDist[neighborIdx]
    return nextToVisit,dist


# 贪心算法求解TSP问题
def nnTSP(cities,start=0):
    cityList = list(range(cities.shape[0]))
    tour = [start]
    unvisited = cityList.copy()
    unvisited.remove(start)
    currentPos = start
    tourDist = 0        # 存储路线距离
    cityDist = cityDistance(cities)

    while unvisited:
        # 当unvisited不为空时,重复循环
        # 找到当前位置在unvisited中的最近邻
        nextToVisit,dist = nearestNeighbor(cityDist,currentPos,unvisited)
        tourDist += dist
        currentPos = nextToVisit
        tour.append(nextToVisit)
        unvisited.remove(nextToVisit)

    # 重新回到起点
    tour.append(start)
    tourDist += cityDist[currentPos,start]
    return tour,tourDist

# 路径可视化
def plotTour(tour,cities,style = 'bo-'):
    if len(tour) > 1000:
        plt.figure(figsize=(15,10))

    start = tour[0:1]
    for i,j in zip(tour[0::],tour[1::]):
        plt.plot([cities[i,0],cities[j,0]],[cities[i,1],cities[j,1]],style)
    plt.plot(cities[start,0],cities[start,1],'rD')
    plt.axis('scaled')
    plt.axis('off')
    plt.title('30cities_nnTSP')


n_cities = 30
# 随机生成n_cities个城市坐标
cities = genCity(n_cities)

tour,tourDist = nnTSP(cities)
print('nnTSP寻找到的最优路径:'+str(tour))
print('nnTSP寻找到最优路径的长度:'+str(tourDist))
plotTour(tour,cities)

运算结果:

nnTSP寻找到的最优路径:[0, 17, 14, 25, 22, 3, 19, 6, 23, 29, 16, 15, 11, 10, 5, 24, 21, 12, 26, 8, 27, 20, 18, 2, 28, 13, 7, 9, 1, 4, 0]
nnTSP寻找到最优路径的长度:4743.836219644864

可视化
基于DEAP库的python进化算法-4.遗传算法求解TSP问题

2.repNNTSP

从nnTSP的算法设计上可以看到,该算法求出的最优路径是和起点有关的,对于不同的起点,会产生不同的最优路径。因而一个简单的改进思路是我们以每个城市的起点进行一次nnTSP搜索,然后在所有得到的路线中选取最优。
代码实现如下:

'''
    repNNTSP
'''
import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import distance

# 定义TSP中的基本元素
# 生成城市坐标
# [n,2]的np.array存储城市坐标,每行存储一个城市
def genCity(n,Lb = 100,Ub = 999):
    random.seed(42)
    return np.random.randint(low=Lb,high=Ub,size=(n,2))


# 计算并存储城市间距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,'euclidean')


# 在未访问的列表中寻找当前位置的最近邻
def nearestNeighbor(cityDist,currentPos,unvisited):
    '''

    :param cityDist: [n,n]记录城市间距离
    :param currentPos: 一个数字,指示当前位于的城市
    :param unvisited: 一个列表,指示当前可选邻居列表
    :return: 返回最近邻的索引与距离
    '''
    # 与邻居的距离
    neighborDist = cityDist[currentPos,unvisited]
    # 得到最近邻的索引
    # 贪心 -每一步最小
    neighborIdx = np.argmin(neighborDist)
    # 找到最近邻
    nextToVisit = unvisited[neighborIdx]
    # 得到与最近邻的距离
    dist = neighborDist[neighborIdx]
    return nextToVisit,dist


# 贪心算法求解TSP问题
def nnTSP(cities,start=0):
    cityList = list(range(cities.shape[0]))
    tour = [start]
    unvisited = cityList.copy()
    unvisited.remove(start)
    currentPos = start
    tourDist = 0        # 存储路线距离
    cityDist = cityDistance(cities)

    while unvisited:
        # 当unvisited不为空时,重复循环
        # 找到当前位置在unvisited中的最近邻
        nextToVisit,dist = nearestNeighbor(cityDist,currentPos,unvisited)
        tourDist += dist
        currentPos = nextToVisit
        tour.append(nextToVisit)
        unvisited.remove(nextToVisit)

    # 重新回到起点
    tour.append(start)
    tourDist += cityDist[currentPos,start]
    return tour,tourDist

# 重复nnTSP但每次用不同的起点,挑选最佳的结果
def repNNTSP(cities):
    optimizedRoute = []     # 最优路径
    minDistance = np.Inf    # 最优路径长度
    for i in range(len(cities)):
        tour,tourDist = nnTSP(cities,start=i)
        if tourDist < minDistance:
            optimizedRoute = tour
            minDistance = tourDist
    return optimizedRoute,minDistance

# 路径可视化
def plotTour(tour,cities,style = 'bo-'):
    if len(tour) > 1000:
        plt.figure(figsize=(15,10))

    start = tour[0:1]
    for i,j in zip(tour[0::],tour[1::]):
        plt.plot([cities[i,0],cities[j,0]],[cities[i,1],cities[j,1]],style)
    plt.plot(cities[start,0],cities[start,1],'rD')
    plt.axis('scaled')
    plt.axis('off')
    plt.title('30cities_resnnTSP')



n_cities = 30
# 随机生成n_cities个城市坐标
cities = genCity(n_cities)

optimizedRoute,minDistance = repNNTSP(cities)
print('resnnTSP寻找到的最优路径:'+str(optimizedRoute))
print('resnnTSP寻找到最优路径的长度:'+str(minDistance))
plotTour(optimizedRoute,cities)

运行结果

resnnTSP寻找到的最优路径:[9, 26, 25, 27, 28, 1, 14, 16, 22, 11, 19, 23, 7, 5, 29, 3, 18, 15, 0, 2, 10, 4, 21, 17, 12, 8, 24, 13, 6, 20, 9]
resnnTSP寻找到最优路径的长度:4863.438601825542

可视化
基于DEAP库的python进化算法-4.遗传算法求解TSP问题

3.2-OPT优化

在nnTSP给出的结果中,包含了一些交叉。这些交叉会导致路径长度的增加:
基于DEAP库的python进化算法-4.遗传算法求解TSP问题
可以看到当出现X交叉时,从三角不等式可知,两根红线表示的长度一定小于两根蓝线,故而解开这样的交叉一定能减小路径长度。

我们可以考虑运用迭代思想,在使用nnTSP得到一条可行的路径之后,对路径进行优化,从而得到比nnTSP更优,同时比穷举法更快的解法。
这里我们可以在nnTSP建立了可行路径之后,选用2-Opt作为优化算法,其步骤为:
基于DEAP库的python进化算法-4.遗传算法求解TSP问题

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import distance

# 定义TSP中的基本元素
# 生成城市坐标
# [n,2]的np.array存储城市坐标,每行存储一个城市
def genCity(n,Lb = 100,Ub = 999):
    random.seed(42)
    return np.random.randint(low=Lb,high=Ub,size=(n,2))


# 计算并存储城市间距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,'euclidean')


# 在未访问的列表中寻找当前位置的最近邻
def nearestNeighbor(cityDist,currentPos,unvisited):
    '''

    :param cityDist: [n,n]记录城市间距离
    :param currentPos: 一个数字,指示当前位于的城市
    :param unvisited: 一个列表,指示当前可选邻居列表
    :return: 返回最近邻的索引与距离
    '''
    # 与邻居的距离
    neighborDist = cityDist[currentPos,unvisited]
    # 得到最近邻的索引
    # 贪心 -每一步最小
    neighborIdx = np.argmin(neighborDist)
    # 找到最近邻
    nextToVisit = unvisited[neighborIdx]
    # 得到与最近邻的距离
    dist = neighborDist[neighborIdx]
    return nextToVisit,dist

# 补全路线
# 序列编码时,缺少最后一段回到原点的距离
def completeRoute(individual):
    return individual + [individual[0]]     # 不要append

def routeDistance(route):
    '''
    :param route: 一条路线,一个序列
    :return: 路线长度
    '''
    if route[0] != route[-1]:
        route = completeRoute(route)
    # 存储路线长度
    routeDist = 0
    # i,j分别是相邻的坐标点
    for i,j in zip(route[0::],route[1::]):
        # 这里直接从CityDist变量中取值了
        routeDist += cityDist[i,j]
    return routeDist

# 贪心算法求解TSP问题
def nnTSP(cities,start=0):
    cityList = list(range(cities.shape[0]))
    tour = [start]
    unvisited = cityList.copy()
    unvisited.remove(start)
    currentPos = start
    tourDist = 0        # 存储路线距离
    cityDist = cityDistance(cities)

    while unvisited:
        # 当unvisited不为空时,重复循环
        # 找到当前位置在unvisited中的最近邻
        nextToVisit,dist = nearestNeighbor(cityDist,currentPos,unvisited)
        tourDist += dist
        currentPos = nextToVisit
        tour.append(nextToVisit)
        unvisited.remove(nextToVisit)

    # 重新回到起点
    tour.append(start)
    tourDist += cityDist[currentPos,start]
    return tour,tourDist


# 2-opt
def opt(cityDist,route,k=2):
    '''
    2-opt算法优化路径
    :param cityDist: 记录城市间距离
    :param route: 记录路径
    :param k:
    :return: 返回优化后的路径optimizedRoute及其路径长度
    '''
    nCities = len(route)    # 城市数
    optimizedRoute = route  # 最优路径
    minDistance = routeDistance(route)  # 最优路径长度

    for i in range(1,nCities-2):
        for j in range(i+k,nCities):
            if j - i == 1:
                continue

            # 两点间相隔大于1个点就翻转
            reversedRoute = route[:i] + route[::-1] + route[j:]
            reversedRouteDist = routeDistance(reversedRoute)
            # 如果翻转后路径更优,则更新路径
            if reversedRouteDist < minDistance:
                optimizedRoute = reversedRoute
                minDistance = reversedRouteDist

    return optimizedRoute,minDistance


# 路径可视化
def plotTour(tour,cities,style = 'bo-'):
    if len(tour) > 1000:
        plt.figure(figsize=(15,10))

    start = tour[0:1]
    for i,j in zip(tour[0::],tour[1::]):
        plt.plot([cities[i,0],cities[j,0]],[cities[i,1],cities[j,1]],style)
    plt.plot(cities[start,0],cities[start,1],'rD')
    plt.axis('scaled')
    plt.axis('off')
    plt.title('30cities_nnTSP')


n_cities = 30
# 随机生成n_cities个城市坐标
cities = genCity(n_cities)
cityDist = cityDistance(cities)
tour,tourDist = nnTSP(cities)

optimizedRoute,minDistance = opt(cityDist,tour)
print('opt_P寻找到的最优路径:'+str(optimizedRoute))
print('resnnTSP寻找到最优路径的长度:'+str(minDistance))
plotTour(optimizedRoute,cities)

运算结果

opt_nnTSP寻找到的最优路径:[0, 12, 17, 3, 25, 27, 11, 19, 24, 16, 8, 26, 6, 5, 9, 21, 22, 28, 18, 15, 13, 14, 29, 2, 23, 1, 10, 20, 4, 7, 0]
optnnTSP寻找到最优路径的长度:4551.5775206924045

基于DEAP库的python进化算法-4.遗传算法求解TSP问题
opt_resNNTSP

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import distance

# 定义TSP中的基本元素
# 生成城市坐标
# [n,2]的np.array存储城市坐标,每行存储一个城市
def genCity(n,Lb = 100,Ub = 999):
    random.seed(42)
    return np.random.randint(low=Lb,high=Ub,size=(n,2))


# 计算并存储城市间距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,'euclidean')


# 在未访问的列表中寻找当前位置的最近邻
def nearestNeighbor(cityDist,currentPos,unvisited):
    '''

    :param cityDist: [n,n]记录城市间距离
    :param currentPos: 一个数字,指示当前位于的城市
    :param unvisited: 一个列表,指示当前可选邻居列表
    :return: 返回最近邻的索引与距离
    '''
    # 与邻居的距离
    neighborDist = cityDist[currentPos,unvisited]
    # 得到最近邻的索引
    # 贪心 -每一步最小
    neighborIdx = np.argmin(neighborDist)
    # 找到最近邻
    nextToVisit = unvisited[neighborIdx]
    # 得到与最近邻的距离
    dist = neighborDist[neighborIdx]
    return nextToVisit,dist

# 补全路线
# 序列编码时,缺少最后一段回到原点的距离
def completeRoute(individual):
    return individual + [individual[0]]     # 不要append

def routeDistance(route):
    '''
    :param route: 一条路线,一个序列
    :return: 路线长度
    '''
    if route[0] != route[-1]:
        route = completeRoute(route)
    # 存储路线长度
    routeDist = 0
    # i,j分别是相邻的坐标点
    for i,j in zip(route[0::],route[1::]):
        # 这里直接从CityDist变量中取值了
        routeDist += cityDist[i,j]
    return routeDist

# 贪心算法求解TSP问题
def nnTSP(cities,start=0):
    cityList = list(range(cities.shape[0]))
    tour = [start]
    unvisited = cityList.copy()
    unvisited.remove(start)
    currentPos = start
    tourDist = 0        # 存储路线距离
    cityDist = cityDistance(cities)

    while unvisited:
        # 当unvisited不为空时,重复循环
        # 找到当前位置在unvisited中的最近邻
        nextToVisit,dist = nearestNeighbor(cityDist,currentPos,unvisited)
        tourDist += dist
        currentPos = nextToVisit
        tour.append(nextToVisit)
        unvisited.remove(nextToVisit)

    # 重新回到起点
    tour.append(start)
    tourDist += cityDist[currentPos,start]
    return tour,tourDist

# 重复nnTSP但每次用不同的起点,挑选最佳的结果
def repNNTSP(cities):
    optimizedRoute = []     # 最优路径
    minDistance = np.Inf    # 最优路径长度
    for i in range(len(cities)):
        tour,tourDist = nnTSP(cities,start=i)
        if tourDist < minDistance:
            optimizedRoute = tour
            minDistance = tourDist
    return optimizedRoute,minDistance


# 2-opt
def opt(cityDist,route,k=2):
    '''
    2-opt算法优化路径
    :param cityDist: 记录城市间距离
    :param route: 记录路径
    :param k:
    :return: 返回优化后的路径optimizedRoute及其路径长度
    '''
    nCities = len(route)    # 城市数
    optimizedRoute = route  # 最优路径
    minDistance = routeDistance(route)  # 最优路径长度

    for i in range(1,nCities-2):
        for j in range(i+k,nCities):
            if j - i == 1:
                continue

            # 两点间相隔大于1个点就翻转
            reversedRoute = route[:i] + route[::-1] + route[j:]
            reversedRouteDist = routeDistance(reversedRoute)
            # 如果翻转后路径更优,则更新路径
            if reversedRouteDist < minDistance:
                optimizedRoute = reversedRoute
                minDistance = reversedRouteDist

    return optimizedRoute,minDistance


# 路径可视化
def plotTour(tour,cities,style = 'bo-'):
    if len(tour) > 1000:
        plt.figure(figsize=(15,10))

    start = tour[0:1]
    for i,j in zip(tour[0::],tour[1::]):
        plt.plot([cities[i,0],cities[j,0]],[cities[i,1],cities[j,1]],style)
    plt.plot(cities[start,0],cities[start,1],'rD')
    plt.axis('scaled')
    plt.axis('off')
    plt.title('30cities_opt_resnnTSP')


n_cities = 30
# 随机生成n_cities个城市坐标
cities = genCity(n_cities)
cityDist = cityDistance(cities)
optimizedRoute,minDistance1 = repNNTSP(cities)

optimizedRoute,minDistance = opt(cityDist,optimizedRoute)
print('opt_resnnTSP寻找到的最优路径:'+str(optimizedRoute))
print('opt_resnnTSP寻找到最优路径的长度:'+str(minDistance))
plotTour(optimizedRoute,cities)

运行结果

opt_resnnTSP寻找到的最优路径:[7, 27, 6, 3, 21, 15, 14, 12, 4, 2, 13, 23, 0, 18, 11, 22, 25, 10, 1, 16, 9, 20, 24, 17, 29, 28, 5, 8, 19, 26, 7]
opt_resnnTSP寻找到最优路径的长度:3928.795216181387

可视化

基于DEAP库的python进化算法-4.遗传算法求解TSP问题
这个结果看起来已经非常像最优解了:路径没有交叉,干净利落的沿着各点形成的convexhull游走。

4.算法对比

基于DEAP库的python进化算法-4.遗传算法求解TSP问题
基于DEAP库的python进化算法-4.遗传算法求解TSP问题

小结

在随机生成的TSP问题中,我们的SGA基本上被其他算法吊打:

SGA需要的时间远大于nnTSP和repNNTSP;而且它对问题的规模更加敏感,在大规模问题上想要收敛到满意的解需要更多迭代步与更大的种群,这又会造成计算时间进一步增加;

  • 可能的改进方向之一是加入环境选择而不是用生成的子代完整替代父代,保证留下精英族群,来加速收敛;
  • 可能的改进方向之二是对种群规模、迭代步数、交叉和突变概率等超参数进行调参,以使算法在TSP问题上更快收敛,并且获得更好的结果;
  • 可能的改进方向之三在于利用问题特性,在SGA的基础上加入局部搜索算法,例如用2-OPT改善精英解;
标签:

未经允许不得转载:作者:1147-柳同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《基于DEAP库的python进化算法-4.遗传算法求解TSP问题》 发布于2020-11-24

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录