代码收藏家 遗传算法解决tsp问题（基于python）
目录
1.遗传算法简要介绍
简单来说，遗传算法是用于解决最优化问题的一种搜索算法。其核心基于自然界种群进化的规律，即初始种群进行交配，在基因层面上，其中会发生交叉互换、基因突变等变异，产生新一批的种群，在种群不断繁衍的过程中，“适者生存，不适者灭亡”，更符合环境要求的个体的基因保留下来的可能性更大，不适应环境的个体的基因往往不会延续下去。漫长的时间后，会筛选出一批最适应环境的种群。
基于此，当我们在解决最优化问题时，采取上述思想，将问题的解看作是“个体”，这些个体组成一个抽象的“种群”，这些解被映射成为相应的编码，于是我们就能得到由各种编码组成的“种群”。这些编码可以进行片段的交叉互换，或者其中某些数字发生“基因突变”，从而进行种群的更新。那么如何筛选更合适的个体呢？根据实际的需要与限制，我们基于编码，通过特定的函数，计算出每个个体的“适应度”，适应度更大的个体的基因（编码）被选中并保留下来的概率更大。这样经过上百次迭代后，就能得到一个接近最优解的一个种群。
详细的介绍大家可以参照这篇文章遗传算法详解 附python代码实现_重学CS的博客-CSDN博客_python遗传算法 ，文章作者将一般公式的最优化讲解到令人发指的详细与通俗易懂。如果能将这篇文章掌握，基本上可以通过遗传算法，求任何公式（n元n次方程）的最值。其中的内涵是将解从十进制数字映射成为二进制串，这其中的编码与解码过程很重要。
在这里就不展开叙述更多细节了，上面那篇文章讲的很清楚，本篇重点在于解决tsp问题。
2.tsp问题简要介绍
根据百度百科的介绍，t旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
3.遗传算法解决tsp问题的几个特殊点
这也是本篇的重点
3.1如何编码
首先要明白我们解的形式是什么，我们需要得到一条距离最短的路径。因此将这些城市编码（0、1、2……..n），以10座城市为例，我们希望得到的解或许是3 5 4 8 6 7 9 0 2 1，因此，在遗传算法中，每个个体的形式就应该是10个不重复数字的排列。好消息是这样一来不需要进行二进制编码解码了。
#初始化种群
def generate_population(self):
path=np.array(range(self.num))
self.pop=[]
for i in range(self.size_pop):
x=path.copy()
np.random.shuffle(x) #随机洗牌
self.pop.append(x)3.2距离矩阵的建立
我们该如何评价一个解的适应度？显然我们希望每个个体的路径距离越小越好，所以我们需要先得到每座城市之间的距离，将其记录在一个矩阵当中，当后续需要求一条完整路径的距离时，任意两点的距离可以直接转化为坐标（比如说，(2,6)）从这个矩阵中取出。
3.3交叉互换
如果直接确定一条染色体上的一个位置，将父本母本从这个位置开始直接交叉互换，这显然是不合理的，假如父本是 1 3 2 4，母本是 2 4 1 3，两者正好在中点切割进行交叉互换后的子代分别是1 3 1 3和 2 4 2 4，这显然是错误的！旅行商每座城市只能经过一次！所以在交换染色体片段的时候，必须要经过一个操作，就是去除重复碱基对。
TSP、MTSP问题遗传算法详细解读及python实现，这篇文章的博主给出了tsp问题遗传算法交叉互换的三种方式，这里我们选择第二种
Order Crossover（顺序交叉）
3.4基因突变
在二进制编码的情况下，要想完成基因突变，只需要将选中的染色体随机替换掉一个碱基对即可。但是在tsp问题中，如果这样做，一定会导致被选中染色体碱基对的重复！因此我们需要做的是将被选中染色体的任意两碱基对进行互换，这样就避免了重复
3.5适应度计算
我们该如何评价一个个体的基因是否适合被遗传下来呢？这就需要计算个体的适应度，适应度越高的个体，被选择的概率就越大。在tsp问题中，我们希望一个个体的路径长度越短越好，即路径越短，适应度越大，在这里，采用文章基于遗传算法求解TSP问题（旅游路径规划，Python实现，超详细，可视化，结果分析中的适应度公式来计算适应度
适应度越大的个体被选中的可能性越大，用numpy.choice来实现
idx = np.random.choice(np.arange(self.size_pop), size=self.size_pop, replace=True,
p=(self.fitness)/(fitness_sum) )4.源码
import numpy as np
class TSP:
def __init__(self, citys, maxgen=500,
size_pop=200, cross_rate=0.8,
muta_rate=0.005
):
self.maxgen = maxgen # 最大进化次数
self.size_pop = size_pop # 种群大小（染色体个数）
self.cross_rate = cross_rate # 交叉概率
self.muta_rate = muta_rate # 变异概率
self.citys = citys # 城市的坐标数据
self.num = citys.shape[0] # 城市的个数(染色体长度)
#获得距离矩阵
def matrix_distance(self):
self.distance_m=np.zeros((self.num,self.num))
for i in range(self.num):
for j in range(self.num):
self.distance_m[i][j]=np.sqrt((self.citys[i][0]-self.citys[j][0])**2+(self.citys[i][1]-self.citys[j][1])**2)
#计算某条路径的距离
def get_total_distance(self,one_path):
distance=0
for i in range(self.num-1):
distance +=self.distance_m[one_path[i]][one_path[i+1]]
distance += self.distance_m[one_path[-1]][one_path[0]]
return distance
#初始化种群
def generate_population(self):
path=np.array(range(self.num))
self.pop=[]
for i in range(self.size_pop):
x=path.copy()
np.random.shuffle(x) #随机洗牌
self.pop.append(x)
#交叉互换
def crossover(self):
self.new_pop=[]
for father in self.pop:
child=father #初步让子代获得父本染色体
if np.random.rand()<self.cross_rate:
#随机选择一个染色体作为母本
mother_index = np.random.randint(0, self.size_pop)
mother=self.pop[mother_index]
#确定切割点
left = np.random.randint(0, self.num-2)
right = np.random.randint(left + 1, self.num-1)
mother=mother.tolist()
father=father.tolist()
#切割片段
gene = mother[left:right]
child1_c = father[right:]+father[:right]
child1 = child1_c.copy()
#去除重复基因
for o in gene:
child1_c.remove(o)
child1[left:right] = gene
child1[right:] = child1_c[0:len(child1) - right]
child1[:left] = child1_c[(len(child1) - right):]
child=np.array(child1)
self.new_pop.append(child)
self.pop=self.new_pop
#变异
def mutation(self):
for i in range(self.size_pop):
if np.random.rand() < self.muta_rate:
child = self.pop[i]
u = np.random.randint(0,self.num - 2)
v = np.random.randint(u+1,self.num- 1)
child_x = child[u+1:v]
child_x=child_x[::-1]
child = np.concatenate((child[0:u+1] , child_x , child[v:]))
self.pop[i]=child
#自然选择，种群根据适应度进行更新
def select(self):
#计算每条路径的长度，放入列表
self.dis=[]
for i in range(self.size_pop):
self.dis.append(self.get_total_distance(one_path=self.pop[i]))
#根据路径长度计算每个个体的适应度
self.fitness=[]
for i in range(self.size_pop):
self.fitness.append(1/(self.dis[i]**15))
#适应度总和
fitness_sum=0
for i in range(self.size_pop):
fitness_sum+=self.fitness[i]
#根据适应度进行选择，适应度大的被选择概率大
idx = np.random.choice(np.arange(self.size_pop), size=self.size_pop, replace=True,
p=(self.fitness)/(fitness_sum) )
self.new_pop=[]
for i in idx:
self.new_pop.append(self.pop[i])
self.pop=self.new_pop
#输出当前种群中最优路径
def result_path(self):
self.index=np.argmax(self.fitness)
a="the shortest path is:"
for i in range(self.num-1):
a+=str(self.pop[self.index][i])
a+="-->"
a+=str(self.pop[self.index][-1])
print(a)
print("the total distance is",self.dis[self.index])
#主函数进行迭代
def main(citys):
SL=TSP(citys)
SL.matrix_distance()
SL.generate_population()
for i in range (SL.maxgen):
SL.crossover()
SL.mutation()
SL.select()
SL.result_path()
if __name__ == '__main__':
citys = np.array([[16.47, 96.10],[16.47, 94.44], [20.09, 92.54],
[22.39, 93.37], [25.23, 97.24], [22.00, 96.05], [20.47, 97.02],
[17.20, 96.29], [16.30, 97.38], [14.05, 98.12], [16.53, 97.38],
[21.52, 95.59], [19.41, 97.13], [20.09, 92.55]])
main(citys)
import numpy as np
class TSP:
def __init__(self, citys, maxgen=500,
size_pop=200, cross_rate=0.8,
muta_rate=0.005
):
self.maxgen = maxgen # 最大进化次数
self.size_pop = size_pop # 种群大小（染色体个数）
self.cross_rate = cross_rate # 交叉概率
self.muta_rate = muta_rate # 变异概率
self.citys = citys # 城市的坐标数据
self.num = citys.shape[0] # 城市的个数(染色体长度)
#获得距离矩阵
def matrix_distance(self):
self.distance_m=np.zeros((self.num,self.num))
for i in range(self.num):
for j in range(self.num):
self.distance_m[i][j]=np.sqrt((self.citys[i][0]-self.citys[j][0])**2+(self.citys[i][1]-self.citys[j][1])**2)
#计算某条路径的距离
def get_total_distance(self,one_path):
distance=0
for i in range(self.num-1):
distance +=self.distance_m[one_path[i]][one_path[i+1]]
distance += self.distance_m[one_path[-1]][one_path[0]]
return distance
#初始化种群
def generate_population(self):
path=np.array(range(self.num))
self.pop=[]
for i in range(self.size_pop):
x=path.copy()
np.random.shuffle(x) #随机洗牌
self.pop.append(x)
#交叉互换
def crossover(self):
self.new_pop=[]
for father in self.pop:
child=father #初步让子代获得父本染色体
if np.random.rand()<self.cross_rate:
#随机选择一个染色体作为母本
mother_index = np.random.randint(0, self.size_pop)
mother=self.pop[mother_index]
#确定切割点
left = np.random.randint(0, self.num-2)
right = np.random.randint(left + 1, self.num-1)
mother=mother.tolist()
father=father.tolist()
#切割片段
gene = mother[left:right]
child1_c = father[right:]+father[:right]
child1 = child1_c.copy()
#去除重复基因
for o in gene:
child1_c.remove(o)
child1[left:right] = gene
child1[right:] = child1_c[0:len(child1) - right]
child1[:left] = child1_c[(len(child1) - right):]
child=np.array(child1)
self.new_pop.append(child)
self.pop=self.new_pop
#变异
def mutation(self):
for i in range(self.size_pop):
if np.random.rand() < self.muta_rate:
child = self.pop[i]
u = np.random.randint(0,self.num - 2)
v = np.random.randint(u+1,self.num- 1)
child_x = child[u+1:v]
child_x=child_x[::-1]
child = np.concatenate((child[0:u+1] , child_x , child[v:]))
self.pop[i]=child
#自然选择，种群根据适应度进行更新
def select(self):
#计算每条路径的长度，放入列表
self.dis=[]
for i in range(self.size_pop):
self.dis.append(self.get_total_distance(one_path=self.pop[i]))
#根据路径长度计算每个个体的适应度
self.fitness=[]
for i in range(self.size_pop):
self.fitness.append(1/(self.dis[i]**15))
#适应度总和
fitness_sum=0
for i in range(self.size_pop):
fitness_sum+=self.fitness[i]
#根据适应度进行选择，适应度大的被选择概率大
idx = np.random.choice(np.arange(self.size_pop), size=self.size_pop, replace=True,
p=(self.fitness)/(fitness_sum) )
self.new_pop=[]
for i in idx:
self.new_pop.append(self.pop[i])
self.pop=self.new_pop
#输出当前种群中最优路径
def result_path(self):
self.index=np.argmax(self.fitness)
a="the shortest path is:"
for i in range(self.num-1):
a+=str(self.pop[self.index][i])
a+="-->"
a+=str(self.pop[self.index][-1])
print(a)
print("the total distance is",self.dis[self.index])
#主函数进行迭代
def main(citys):
SL=TSP(citys)
SL.matrix_distance()
SL.generate_population()
for i in range (SL.maxgen):
SL.crossover()
SL.mutation()
SL.select()
SL.result_path()
if __name__ == '__main__':
citys = np.array([[16.47, 96.10],[16.47, 94.44], [20.09, 92.54],
[22.39, 93.37], [25.23, 97.24], [22.00, 96.05], [20.47, 97.02],
[17.20, 96.29], [16.30, 97.38], [14.05, 98.12], [16.53, 97.38],
[21.52, 95.59], [19.41, 97.13], [20.09, 92.55]])
main(citys)
结果分析
如果每一次迭代都输出结果，可以清楚地看到路径最终都收敛。事实上，每次收敛的结果与种群大小size_pop息息相关，一开始我将种群大小设置为 200，结果每次运行虽然收敛，但是得到的结果各不相同，基本上毫无关联，说明结果陷入了局部最优解，而非全局最优解。解决方法就是把size_pop设置为500，才使得结果误差较小，趋近于全局最优解。
事实上，要想使结果更直观，最好用坐标图使结果可视化，将路线显示出来。本文仅仅展示了数字结果，这样有两个问题，一是可能起始城市不同，如8 2 3 6 和 2 3 6 8，二是顺序不同，如8 2 3 6和 6 3 2 8，其实结果的路线本质是一样的，但直观看上去不利于结果统计。
参考文章：
