TSP、MTSP问题遗传算法详细解读及python实现
写在前⾯
遗传算法是⼀种求解NPC问题的启发式算法，属于仿⽣进化算法族的⼀员。仿⽣进化算法是受⽣物⾏为启发⽽发明的智能优化算法，往往是⼈们发现某种⽣物的个体虽然⾏为较为简单，但⽣物集通过某种原理却能表现出智能⾏为。于是不同的⼈研究不同的⽣物⾏为原理，受到启发⽽发明出新的仿⽣进化算法。⽐如免疫优化算法，蚁算法，模拟退⽕算法等，这些算法以后也会简单介绍。
本⽂的主题是遗传算法，该算法也是受到⽣物⾏为启发。物竞天择，适者⽣存，优胜劣汰，是该优化算法的核⼼思想。笔者在业务中需要⽤到遗传算法求解TSP问题，但是⽹上能查到的资料对遗传算法的讲解不够通俗易懂，往往上来就是遗传变异交叉，对于我这样的初学者来说有点不知所云，于是不得不直接看源码，⼀⾏⼀⾏地理解代码的意思，才弄懂了原理。这种⽅法对于初学者和编程基础薄弱者颇为困难，⽽且费时费⼒，苦不堪⾔。同时，由于读者可能熟练掌握的是不同的语⾔，因此若代码是某⼀种语⾔编写的，那么掌握其他语⾔的读者很可能难以吸收，浪费了资源。此外，⽹上关于TSP问题的资料很多，但是关于MTSP问题的资料却凤⽑麟⾓。因此有了创作本⽂的意图，旨在⽤最通俗详尽的语⾔深⼊浅出地解释遗传算法解TSP、MTSP问题的原理及应⽤
遗传算法解TSP问题原理
⼀、TSP问题
旅⾏商问题，即TSP问题（Traveling Salesman Problem）⼜译为旅⾏推销员问题、货郎担问题，是数学领域中著名问题之⼀。假设有⼀个旅⾏商⼈要拜访n个城市，他必须选择所要⾛的路径，路径的限制是每个城市只能拜访⼀次，⽽且最后要回到原来出发的城市。路径的选择⽬标是要求得的路径路程为所有路径之中的最⼩值。
想要求解出TSP问题的最优解，⽬前唯⼀的⽅法是穷举出所有的路径。然⽽，路径的数量级是n!，也就是⽬标点数量的阶乘。当n为14
时，n!已经⼤于800亿。当n更⼤，为30，40 时，更是天⽂数字，即使计算机⼀秒钟计算⼀亿次，其求解时间也远⼤于我们的寿命。因此，穷举法解TSP问题根本不可⾏，需要别的启发式算法来代替。
⼆、遗传算法解TSP原理
2.1
笔者认为，⼤多数的遗传算法讲解让⼈难以理解的原因在于其术语名称的意义不明确，往往与其实际意义相去甚远。譬如，什么是适应度函数，什么是遗传，变异，交叉。乍⼀听总有不知所云的感觉，这跟TSP问题求最短路径有什么关系。因此本⽂将从TSP问题出发，讲解遗传算法的思想和原理。
2.2
对于TSP问题，我们拿到的是n个⽬标点的坐标，作为例⼦，我们视为⾯对的是n=10个城市。有了坐标，我们便可以计算出n个城市之间的距离，得到⼀个n*n的矩阵，这个矩阵表⽰的是城市之间两两连接形成的⽆向图，边的权重是城市之间的距离，⽽TSP问题则是从图中出⼀个包含所有城市的最⼩的环。
2.3
问题明确了，接下来就是遗传算法登场了。
2.3.1 种初始化
⾸先是初始化种，TSP⾥的初始化种其实就是⼀个长度为n=10的包含1~n(这个例⼦⾥为10)且不含重复元素的序列，其意义就是⼀个⼈从某个点出发，随机访问下⼀个未访问过的城市，直到所有的城市都访问完毕，他再从最后⼀个城市返回出发城市。他的轨迹就是⼀个包含了所有城市且没有重复访问的环。种数量设为M，那么该种初始化的意义就是M个⼈独⽴、随机、不重复地访问⼀遍各个城市，单个个体轨迹构成⼀个环。
2.3.2 适应度计算
M个个体的轨迹得到了，这些轨迹是随机游⾛得到的，当然很可能远远不包含属于最优解，⽽是⽐最优解坏得多。但是，随机游⾛的路径也有⼤有⼩，有好有坏。因此需要有⼀个函数衡量个体的好坏，也就是环路径的长短。
那么这个函数就被称为适应度函数，其功能是衡量个体的好坏。对于TSP问题，其适应度函数当然是距离相关的了。个体的好坏，衡量标准就是该个体序列的路径长度。路径越长，个体越“坏”，路径越短，个体越“好”。因此，设序列为x，那么该序列的路径长度便是d(x)，⽽适应度函数则应该取为1/d(x)，适应度越⼤，个体越优。
2.3.3 选择
有了每个个体的适应度，就能评价每个个体的好坏。物竞天择，优胜劣汰，将优秀的个体选择出来进⾏交配，以期得到更好的个体，并由此不断进化，⼀代代传承，后代不断⽐前⼀代变得更好，最终收敛，种中的某个个体达到了优秀的极限，便是最优解。
对于TSP问题，选择的具体操作是，计算出所有个体的适应度，也就是路径距离的倒数。然后将所有个体的适应度归⼀化，得到概率。然后从数量为n的个体中以赌的形式选择出若⼲个个体，视为优秀个体。
举个例⼦，为了简单起见，设种⼤⼩m=4。并计算出了四个个体的适应度分别为1，2，3，4。对适应度进⾏归⼀化得到概率：
0.1，0.2，0.3，0.4。那么这四个概率就可以构成⼀个，每个个体对应的被选择的概率分别为0.1，0.2，0.3，0.4。随后，在这个转盘上转动m次，此处为4。将选中的个体放⼊⼀个集合，未选中的个体抛弃。
注意，这是⼀种重复抽样的选择⽅式，并且重复抽到的个体不去重。每次抽样，都是相同的，并没有改变。⽐如，在这个例⼦中，种数量为4，那么就要抽取四次，那么0.4对应的个体很可能被多次抽样，⽽0.1对应的个体很可能未被抽到，直接淘汰。那么被选择的个体集合就很可能含有多个适应度为4的个体，并且被选择的集合的种数量仍旧为m，只不过抛弃了较坏的个体，⽽可能保留了多个优秀的个体。个体越优秀，被重复选择的概率就越⼤。
2.3.4 交叉（遗传）
遗传算法中的交叉属于遗传算法的核⼼以及关键步骤，其思想受启发于⽣物遗传中的染⾊体交叉。
对于TSP问题，有如下的交叉⽅式进⾏交叉。
1. Partial-Mapped Crossover（部分映射交叉）
2. Order Crossover（顺序交叉）
3. Position-based Crossover（基于位置的交叉）
那么，在这个被选择的⼤⼩为种数量m的新的种中，如何通过上述⽅式交叉呢？这⾥有⼀个超参
数pc(probability of crossover)。将种打乱之后，随机两两组合。每对组合以pc的概率采⽤上述⽅式之⼀进⾏交叉，以（1-pc）的概率不进⾏交叉，⽽是⼆者直接进⼊下⼀代。pc的值⼀般在0.5到0.9之间。
通过上述⽅式，便能产⽣⼀个同样⼤⼩为m的新的种。此刻，选择、交叉的过程已经完成，还剩最后⼀步操作——变异。
2.3.5 变异
对于上⼀步交叉得到的⼤⼩为m的种，以pm的概率选择出部分个体进⾏变异操作。选择出来的个体序列随机选择两个位置上的数进⾏交换。如，其中⼀个被选择的个体的序列为196278354，那么在这个序列中随机选择两个位置上的数，⽐如第⼆个数9和第四个数2，进⾏交换。那么得到的变异后的序列就是：126978354，变异操作完成。
2.3.6 传承
⾄此，种的迭代更新⽅式基本阐述完毕，还剩下最后⼀步操作，传承。这是说，将上⼀轮中最优的个体（对于TSP问题，也就是路径距离最短的序列），保留下来，并⽤他替换掉新产⽣的种中最差的个体。这⼀步的意义在于，上⼀轮中最优的个体被选择的⼏率也最⼤，但是它与其他个体交叉之后
得到的新个体不⼀定优于它⾃⼰。如果这样，那么这个最优的个体便被覆盖、迭代掉了，这样很可能造成下⼀代中的所有个体都⽐上⼀代的最优个体差，优秀的基因被淘汰。为了避免这样的情况，需要这⼀步传承，保证每次迭代之后的最优个体不坏于之前出现的所有个体。
三、遗传算法解TSP问题python实现
对于单纯的TSP问题，⽤python求解⾮常简便，原因在于python已有⼗分强⼤的遗传算法⼯具包，⽤户只需要将需要求解的⽬标点位置转化成n*n的距离矩阵distance_matrix，然后直接调⽤python⾥的库sko.GA即可，下⾯是⽰例代码。读者不⽤担⼼直接调包⽆法了解算法实现的细节，在下⼀节的MTSP问题本⽂将基于纯python⼿写实现遗传算法。
// An highlighted block
def cal_total_distance(routine):
'''The objective function. input routine,return total distance.
cal_total_distance(np.arange(num_points))
'''
num_points,= routine.shape
return sum([distance_matrix[routine[i % num_points], routine[(i +1)% num_points]]for i in range(num_points)])
from sko.GA import GA_TSP
#num_points为城市数量，size_pop为种数量，max_iter为迭代次数
#prob_mut为变异率
ga_tsp =GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=2000, prob_mut=1)random在python中的意思
best_points, best_distance = ga_tsp.run()
其中best_points返回的是最优路径的顺序，best_distance返回的是最优路径的距离。
⽤python⼯具包实现TSP问题就是这样简洁容易。在下⼀节，要讨论的是更为复杂的MTSP问题。
四、遗传算法解MTSP问题
4.1问题描述
问题描述：m个旅⾏商去旅游 n个城市，⼀种规定是都必须从同⼀个出发点出发，⽽且返回原出发点，需要将所有的城市遍历完毕，每个城市只能游历⼀次，但是为了路径最短可以路过这个城市多次。这个就是多旅⾏商问题。是在TSP问题的基础上进⾏了扩展。
4.2 问题分析
关于MTSP问题，可以到的资料⽐TSP要少很多。对于该问题的求解，可以基于TSP问题的思路进⾏修改。⾸先需要明确具体的业务需求，是多个旅⾏商从不同的城市出发，遍历所有的⽬标点并回到⾃⼰的原点，还是都从同⼀个点出发回到所有起点，还是回到同⼀个点但该点不是起点。另外，每个旅⾏商访问城市的数量是任意的，还是两个旅⾏商需要访问的城市数⽬是⼤致相等的，还是规定了每个旅⾏商访问的数量具体是多少？
不论问题是哪种，其思想是差不多的。本⽂以多个旅⾏商从同⼀点出发，回到同⼀个起点，且每⼈访问的城市数量相同的情形。⾸先，跟TSP问题⼀样，初始化⼤⼩为M的种，每个个体是⼀个不含重复点的长度为n的序列。然后重点是设置断点，将该序列拆分成m段，也就是旅⾏商的数量。此后，将m段序列的⾸尾都添上起点，形成m个旅⾏商各⾃的环路径，然后计算各个环的距离的总和的倒数，作为适应度函数的值，后续操作按照TSP问题的遗传算法求解即可。在本例中，考虑的m取2，两位旅⾏
商。断点取序列的中间，也就是序列平均分为两半。若读者想不限制各位旅⾏商的访问城市的数⽬相等，只需要设置断点在不同的位置即可。
4.2 MTSP问题python实现
对于该MTSP问题，笔者没有到相关的python实现包，因此只能⼿撸代码如下：
import numpy as np
from matplotlib import pyplot as plt
import math
import copy
import random
def init_population(length, num):
li = list(range(length))
print(li)
population = []
for i in range(num):
for i in range(num):
random.shuffle(li)
population.append(copy.deepcopy(li))
return population
def aimFunction(entity, DMAT, break_points):
"""
⽬标函数
:param entity: 个体
:param DMAT: 距离矩阵
:
param break_points: 切断点
:return：适应度函数值
"""
distance = 0
break_points.insert(0, 0)
break_points.append(len(entity))
routes = []
for i in range(len(break_points) - 1):
routes.append(entity[break_points[i]:break_points[i + 1]])
# print(routes)
#上⾯代码的作⽤是将路径拆成m段。break_points的长度设置为k时，则将路径拆分成了k+1段，此处的k 取的1。
for route in routes:
if 0 in route:
route.insert(0,0)
route.append(0)#此处给每段路径添上⾸尾点0，因为本例所有旅⾏商都从0这个城市出发，具体从哪⾥出发根据实际问题修改该设定。        for i in range(len(route)-1):
distance += DMAT[route[i],route[i+1]]
return 1.0/distance
#返回种所有个体的适应度列表
def fitness(population, DMAT, break_points, aimFunction):
"""
适应度
:param population: 种
:param DMAT: 距离矩阵
:param break_points：切断点
:param aimFunction: ⽬标函数
:return:
"""
value = []
for i in range(len(population)):
value.append(aimFunction(population[i], DMAT, copy.deepcopy(break_points)))
# weed out negative value
if value[i] < 0:
value[i] = 0
return value
#这⾥传⼊的是种和每个个体的适应度
#这⾥的赌与蚁算法的有⼀定区别。这⾥对适应度归⼀化得到概率之后，每个个体被选中的概率就是这个概率
#对每次被选中的个体的数⽬没有限制，完全随机，限制的是选择次数n与种数⽬相同，使得新的种数量与旧的种⼀致
def selection(population, value):
# 赌选择
fitness_sum = []
for i in range(len(value)):
if i == 0:
fitness_sum.append(value[i])
else:
fitness_sum.append(fitness_sum[i - 1] + value[i])
for i in range(len(fitness_sum)):
fitness_sum[i] /= sum(value)
# select new population
population_new = []
for i in range(len(value)):
rand = np.random.uniform(0, 1)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。