遗传算法解决旅行商问题实验报告_旅行商问题遗传算法

目录

前言

问题描述

基因编码分析

路程计算

交叉函数

代码实现

结果讨论

君主固化

最后的话

参考资料

前言

遗传算法在绝大多数情况下采取二进制编码方式描述基因，也有一些采取实数方式的。今天分享的这个问题很有意思，也是一个非常经典的问题——旅行商问题。就是一个商人全国各地到处跑，他每个地方只走一遍，又想要路径最短（懒人事多），问最优解是什么。这个问题的基因编码方式非常有意思，所以想详细的记录一些。另外，本次算法的交叉过程也加入了一些自己的创新（不知道之前有同学这么试过没有），想跟大家一起分享讨论一下。如果没有遗传算法基础的同学，可以看看我之前的博客。

Python—标准遗传算法求函数最大值代码实现

Python-遗传算法君主交叉代码实现

问题描述

旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。

我认为阅读本篇博客的读者已经有了一定的遗传算法基础了，所以只说这个问题的特殊之处，不再从头到尾进行遗传算法的讲解。

基因编码分析

全国各地的位置坐标采用《智能优化算法及其matlab实例第二版》中给的坐标（它只给了31个地点，有些博客是34个，这个不影响咱理解算法）。这个问题的特殊之处是地点，31个不重复的地点，所以我们的编码方式需要跟问题匹配起来。或许二进制编码也ok吧（我没研究过），但是最直接的编码方式是什么呢？直接给31个地点编编号对吧，0~30对应起来就行，从0开始是因为Python的列表索引第一个就是0，也是为了方便我们之后的程序编写。

所以，说了这么多，我们生成的基因编码就不是一串01序列了，而是这样的：

[8, 4, 24, 1, 3, 9, 16, 17, 18, 26, 23, 30, 13, 28, 11, 10, 14, 19, 29, 27, 25, 21, 20, 15, 2, 5, 12, 7, 22, 0, 6]

没有重复吧，这个序列的顺序代表着商人行走的顺序。它就是我们的基因（染色体）。

路程计算

对问题做拆解，先是给出31个地点对应的坐标及路程计算的代码，便于大家理解。其实就是简单的平方求和再开根号。

C=[1304,2312,3639,1315,4177,2244,3712,1399,3488,1535,3326,1556, 3238,1229,4196,1044,4312 ,790,4386, 570,3007, 1970,2562,1756, 2788, 1491,2381,1676,1332, 695,3715, 1678,3918, 2179,4061, 2370, 3780, 2212,3676, 2578,4029, 2838,4263, 2931,3429, 1908,3507, 2376, 3394, 2643,3439, 3201,2935, 3240,3140, 3550,2545, 2357,2778, 2826, 2370, 2975] c=np.array(C) c=c.reshape(31,2) #转换成31个城市的坐标，我们认为城市序号从0到30对应此时的坐标

def distance(l1,l2): y=(l1[0]-l2[0])**2+(l1[1]-l2[1])**2 y=y**0.5 return y def sumdis(li): sumd=0 for i in range(len(li)-1): sumd=sumd+distance(li[i],li[i+1]) return sumd

交叉函数

这个问题的交叉过程比较特殊，因为需要将染色体交叉，同时又要保证交叉后的染色体还是0~30的位置编号不能有重复的对吧，所以需要有个去重的过程，对储存染色体的列表进行切片操作。这个过程引入了一些独特的交叉思想，其他同学的博客已经写的比较好了，我这可以推荐一下，就不再赘述了。大家看下面博客里面的顺序交叉部分就行。

遗传算法-交叉算子讲解

然后我把编写好的交叉代码也放在这供大家参考，看不习惯的话，也可以自己编写，思路一致就行。

def exchange(lis,aa): #交 # lis=lis.tolist() # aa=aa.tolist() # print(type(lis)) for i in range(len(aa)): lis.remove(aa[i]) #清楚掉lis原有的与aa重合的基因 lis.extend(aa) #将aa的基因与lis合并 # lis=np.array(lis) return lis def addpianduan(lis,pianduan,a1): lisqian=lis[0:a1] lishou=lis[a1:-1] #左开右闭 lishou.append(lis[-1]) #把最后一个加进去 lisqian.extend(pianduan) lisqian.extend(lishou) return lisqian def exchange1(lis1,lis2): #传统意义上的随机交叉 a1=random.sample(range(0,25),1)[0] a2=random.sample(range(20,31),1)[0] while a1>=a2: a1=random.sample(range(0,25),1)[0] #随机生成交叉区间 pianduan=lis1[a1:a2] pianduan1=lis2[a1:a2] for i in range(len(pianduan)): lis2.remove(pianduan[i]) #清楚掉lis重合的基因 for i in range(len(pianduan)): lis1.remove(pianduan1[i]) #清楚掉lis重合的基因 lis1=addpianduan(lis1,pianduan1,a1) #缝合染色体 lis2=addpianduan(lis2,pianduan,a1) return lis1,lis2

代码实现

先给出实现的代码，之后我会对代码中的特殊点再进行讨论的。

#%% NP=100 #初始化种群数 D=31 #单条染色体基因数目 Pc=0.8 #交叉率 Pm=0.3 #变异率 G=1000 #最大遗传代数 C=[1304,2312,3639,1315,4177,2244,3712,1399,3488,1535,3326,1556, 3238,1229,4196,1044,4312 ,790,4386, 570,3007, 1970,2562,1756, 2788, 1491,2381,1676,1332, 695,3715, 1678,3918, 2179,4061, 2370, 3780, 2212,3676, 2578,4029, 2838,4263, 2931,3429, 1908,3507, 2376, 3394, 2643,3439, 3201,2935, 3240,3140, 3550,2545, 2357,2778, 2826, 2370, 2975] c=np.array(C) c=c.reshape(31,2) #转换成31个城市的坐标，我们认为城市序号从0到30对应此时的坐标 f=[] #第一代随机种群 for i in range(NP): f.append(random.sample(range(0,31),31)) FIT=[] #适应度计算存储列表 sortf=[] trace=[] xtrace=[] xtracemin=[] test=[] for i in range(len(f)): temlist=[] for j in range(len(f[0])): temlist.append(c[f[i][j]]) #将城市序号转换成对应坐标位置 FIT.append(sumdis(temlist)) #适应度计算 sortFIT=np.sort(FIT) #升序排序 index= np.argsort(FIT) #升序对应索引 for i in range(len(f)): sortf.append(f[index[i]]) #得到升序顺序对应的种群 #%%遗传算法循环 for i in range(G): print(i) Emper=sortf[0] #产生君主 nf=sortf #出新的种群，在其基础上进行交叉、变异 for M in range(2,NP,2): p=np.random.rand() #君主交叉 if p<Pc: aaa=Emper[-10:-1] #选了染色体末尾的10个基因进行交叉 nf[M]=exchange(nf[M],aaa) # 我觉得这一步好像谈不上交叉，只是单纯地将君主染色体所占整体比重加大了 # 人为再加一手传统的交叉过程，到时候将这个过程删除，看看影响结果不 # for M in range(2,NP,2): # p=np.random.rand() #普通交叉 # if p<Pc: # nf[M],nf[M+1]=exchange1(nf[M],nf[M+1]) for M in range(1,NP): #变异 for n in range(D): p=np.random.rand() if p<Pm: a1=random.sample(range(0,31),1)[0] a2=random.sample(range(0,31),1)[0] while a1==a2: a2=random.sample(range(0,31),1)[0] temp=nf[M][a1] nf[M][a1]=nf[M][a2] nf[M][a2]=temp #交叉变异结束之后，新一代nf加上前代f共2*NP个个体进行筛选 newf=np.vstack((sortf,nf)) #垂直方向累加两个f newFIT=[] for j in range(len(newf)): temlist=[] for k in range(len(newf[0])): temlist.append(c[newf[j][k]]) #把点转换成对应坐标 newFIT.append(sumdis(temlist)) #适应度函数 sortFIT=np.sort(newFIT) #升序排序 index= np.argsort(newFIT) #升序对应索引 maxfit=max(newFIT) minfit=min(newFIT) sortf=[] for j in range(len(f)): sortf.append(newf[index[j]].tolist()) #得到升序顺序对应的种群坐标是0~30 trace.append(minfit) st=sortf[0] xtrace.append(st) plt.plot(trace,color='deepskyblue', marker='o',linewidth=2, markersize=3) plt.xlabel('Number of iterations',fontsize = 10) plt.ylabel('minyvalue',fontsize = 10) plt.savefig('pic8',bbox_inches = 'tight',pad_inches = 0,dpi =350) plt.close()

结果讨论

以上代码是最终版代码，它的收敛结果是比较理想的，先给出收敛结果大家感受一下。都是迭代1000代。miny代表总路程。

普通交叉方式

 君主交叉方式

不了解君主交叉的看我之前的博客：

Python-遗传算法君主交叉代码实现

 收敛效果更好了对吧。

这两幅图其实都是做了对整个筛选过程做了特殊处理的，没处理之前的收敛过程长下面这样：

 简直不忍直视。。。。丝毫没有收敛的迹象。

下面就是我想跟大家讨论的重点了，特殊处理的地方就在于：君主固化

先看关键代码：

for M in range(2,NP,2): p=np.random.rand() #君主交叉 if p<Pc: aaa=Emper[-10:-1] #选了染色体末尾的10个基因进行交叉 nf[M]=exchange(nf[M],aaa)

 for M in range(1,NP): #变异 for n in range(D): p=np.random.rand() if p<Pm: a1=random.sample(range(0,31),1)[0] a2=random.sample(range(0,31),1)[0] while a1==a2: a2=random.sample(range(0,31),1)[0] temp=nf[M][a1] nf[M][a1]=nf[M][a2] nf[M][a2]=temp

君主固化

我起的是这个名字哈，估计其实这个方法之前也有同学用过，但不知道叫啥名字，我就先用这个名字称呼一下。细心的同学可能发现以上两段代码的特殊之处了，为什么变异和交叉都不从第一个基因开始呢？第一个基因是通过适应度函数排序后的当前最优基因（君主），我们认为它已经很好了，所以，在制定规则的时候就说，君主这么好，那为什么还要它变异呢？把它保留下来把。我把这个保留君主的操作称为君主固化。其实跟古代的朝代更迭很像是不是？

那有的同学可能有疑惑，这样岂不是君主就一直是它了吗？其实除了君主之外的基因在不断地变异交叉，它们是在进化的，等出现了比当前君主更优的基因的时候，它就可以取代君主，成为新的君主了，是不是新的王朝推翻了旧的王朝了？

如果有同学知道这个方法更为官方的名字，欢迎告诉我一下，我感觉自己这个命名方式有点过于不专业了，但是很方便大家理解。

最后的话

欢迎大家跟我讨论，旅行商问题用遗传算法来解决还是很有意思的。也欢迎大家转载，转载请注明出处，谢谢大家。

参考资料

[1]旅行商问题——百度百科

[2]《智能优化算法及其matlab实例第二版》