TSP、MTSP问题遗传算法详细解读及python实现.pdf
- 文档编号:18633310
- 上传时间:2023-08-23
- 格式:PDF
- 页数:8
- 大小:364.48KB
TSP、MTSP问题遗传算法详细解读及python实现.pdf
《TSP、MTSP问题遗传算法详细解读及python实现.pdf》由会员分享,可在线阅读,更多相关《TSP、MTSP问题遗传算法详细解读及python实现.pdf(8页珍藏版)》请在冰点文库上搜索。
TSP、MTSP问题遗传算法详细解读及python实现写在前遗传算法是种求解NPC问题的启发式算法,属于仿进化算法族的员。
仿进化算法是受物为启发发明的智能优化算法,往往是们发现某种物的个体虽然为较为简单,但物集群通过某种原理却能表现出智能为。
于是不同的研究不同的物为原理,受到启发发明出新的仿进化算法。
如免疫优化算法,蚁群算法,模拟退算法等,这些算法以后也会简单介绍。
本的主题是遗传算法,该算法也是受到物为启发。
物竞天择,适者存,优胜劣汰,是该优化算法的核思想。
笔者在业务中需要到遗传算法求解TSP问题,但是上能查找到的资料对遗传算法的讲解不够通俗易懂,往往上来就是遗传变异交叉,对于我这样的初学者来说有点不知所云,于是不得不直接看源码,地理解代码的意思,才弄懂了原理。
这种法对于初学者和编程基础薄弱者颇为困难,且费时费,苦不堪。
同时,由于读者可能熟练掌握的是不同的语,因此若代码是某种语编写的,那么掌握其他语的读者很可能难以吸收,浪费了资源。
此外,上关于TSP问题的资料很多,但是关于MTSP问题的资料却凤麟。
因此有了创作本的意图,旨在最通俗详尽的语深浅出地解释遗传算法解TSP、MTSP问题的原理及应遗传算法解TSP问题原理、TSP问题旅商问题,即TSP问题(TravelingSalesmanProblem)译为旅推销员问题、货郎担问题,是数学领域中著名问题之。
假设有个旅商要拜访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的包含1n(这个例为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-MappedCrossover(部分映射交叉)2.OrderCrossover(顺序交叉)3.Position-basedCrossover(基于位置的交叉)那么,在这个被选择的为种群数量m的新的种群中,如何通过上述式交叉呢?
这有个超参数pc(probabilityofcrossover)。
将种群打乱之后,随机两两组合。
每对组合以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写实现遗传算法。
/Anhighlightedblockdefcal_total_distance(routine):
Theobjectivefunction.inputroutine,returntotaldistance.cal_total_distance(np.arange(num_points)num_points,=routine.shapereturnsum(distance_matrixroutinei%num_points,routine(i+1)%num_pointsforiinrange(num_points)fromsko.GAimportGA_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)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.2MTSP问题python实现对于该MTSP问题,笔者没有找到相关的python实现包,因此只能撸代码如下:
importnumpyasnpfrommatplotlibimportpyplotaspltimportmathimportcopyimportrandomdefinit_population(length,num):
li=list(range(length)print(li)population=foriinrange(num):
foriinrange(num):
random.shuffle(li)population.append(copy.deepcopy(li)returnpopulationdefaimFunction(entity,DMAT,break_points):
标函数:
paramentity:
个体:
paramDMAT:
距离矩阵:
parambreak_points:
切断点:
return:
适应度函数值distance=0break_points.insert(0,0)break_points.append(len(entity)routes=foriinrange(len(break_points)-1):
routes.append(entitybreak_pointsi:
break_pointsi+1)#print(routes)#上代码的作是将路径拆成m段。
break_points的长度设置为k时,则将路径拆分成了k+1段,此处的k取的1。
forrouteinroutes:
if0inroute:
route.remove(0)route.insert(0,0)route.append(0)#此处给每段路径添上尾点0,因为本例所有旅商都从0这个城市出发,具体从哪出发根据实际问题修改该设定。
foriinrange(len(route)-1):
distance+=DMATroutei,routei+1return1.0/distance#返回种群所有个体的适应度列表deffitness(population,DMAT,break_points,aimFunction):
适应度:
parampopulation:
种群:
paramDMAT:
距离矩阵:
parambreak_points:
切断点:
paramaimFunction:
标函数:
return:
value=foriinrange(len(population):
value.append(aimFunction(populationi,DMAT,copy.deepcopy(break_points)#weedoutnegativevalueifvaluei0:
valuei=0returnvalue#这传的是种群和每个个体的适应度#这的轮盘赌与蚁群算法的有定区别。
这对适应度归化得到概率之后,每个个体被选中的概率就是这个概率#对每次被选中的个体的数没有限制,完全随机,限制的是选择次数n与种群数相同,使得新的种群数量与旧的种群致defselection(population,value):
#轮盘赌选择fitness_sum=foriinrange(len(value):
ifi=0:
fitness_sum.append(valuei)else:
fitness_sum.append(fitness_sumi-1+valuei)foriinrange(len(fitness_sum):
fitness_sumi/=sum(value)#selectnewpopulationpopulation_new=foriinrange(len(value):
rand=np.random.uniform(0,1)rand=np.random.uniform(0,1)forjinrange(len(value):
ifj=0:
if0randandrand=fitness_sumj:
population_new.append(populationj)else:
iffitness_sumj-1randandrand=fitness_sumj:
population_new.append(populationj)returnpopulation_new#对于被选中的双亲,随机两两组合。
并以pc的概率交配#若没有被选择交配,则直接双亲进下代。
如果被选择,则交换中间段。
defamend(entity,low,high):
修正个体:
paramentity:
个体:
paramlow:
交叉点最低处:
paramhigh:
交叉点最处:
return:
length=len(entity)cross_gene=entitylow:
high#交叉基因not_in_cross=#应交叉基因raw=entity0:
low+entityhigh:
#交叉基因foriinrange(length):
ifnotiincross_gene:
not_in_cross.append(i)error_index=foriinrange(len(raw):
ifrawiinnot_in_cross:
not_in_cross.remove(rawi)else:
error_index.append(i)foriinrange(len(error_index):
rawerror_indexi=not_in_crossientity=raw0:
low+cross_gene+rawlow:
returnentitydefcrossover(population_new,pc):
交叉:
parampopulation_new:
种群:
parampc:
交叉概率:
return:
half=int(len(population_new)/2)father=population_new:
halfmother=population_newhalf:
np.random.shuffle(father)np.random.shuffle(mother)offspring=foriinrange(half):
ifnp.random.uniform(0,1)len(fatheri)-5:
#cut2=cut1-5#else:
#cut2=cut1+5cut1=0cut2=np.random.randint(0,len(population_new0)cut2=np.random.randint(0,len(population_new0)ifcut1cut2:
cut1,cut2=cut2,cut1ifcut1=cut2:
son=fatheridaughter=motherielse:
son=fatheri0:
cut1+mothericut1:
cut2+fathericut2:
son=amend(son,cut1,cut2)daughter=motheri0:
cut1+fathericut1:
cut2+mothericut2:
daughter=amend(daughter,cut1,cut2)else:
son=fatheridaughter=motherioffspring.append(son)offspring.append(daughter)returnoffspring#这的变异是最简单的变异法则,直接随机选取两个位置上的数进交换defmutation(offspring,pm):
foriinrange(len(offspring):
ifnp.random.uniform(0,1)=pm:
position1=np.random.randint(0,len(offspringi)position2=np.random.randint(0,len(offspringi)#print(offspringi)offspringiposition1,offspringiposition2=offspringiposition2,offspringiposition1#print(offspringi)returnoffspring#主函数if_name_=_main_:
#这的graph为距离矩阵,需要定义后传DMAT=graphbreak_points=len(graph)/2#这是将所有城市从中间断开成两段。
读者可以根据需求切断成任意段(每段代表个旅商),并且可以在任意位置切断。
population=init_population(len(graph),90)t=dic_result=foriinrange(20000):
#selectionvalue=fitness(population,DMAT,break_points,aimFunction)population_new=selection(population,value)#crossoveroffspring=crossover(population_new,0.65)#mutationpopulation=mutation(offspring,0.02)#ifi%1=0:
#show_population(population)result=forjinrange(len(population):
result.append(1.0/aimFunction(populationj,DMAT,copy.deepcopy(break_points)t.append(min(result)min_entity=populationresult.index(min(result)routes=break_points_plt=copy.deepcopy(break_points)break_points_plt.insert(0,0)break_points_plt.append(len(min_entity)foriinrange(len(break_points_plt)-1):
routes.append(min_entitybreak_points_plti:
break_points_plti+1)forrouteinroutes:
if0inroute:
route.remove(0)route.remove(0)route.insert(0,0)route.append(0)dic_resultmin(result)=routesifi%400=0:
min_entity=populationresult.index(min(result)routes=break_points_plt=copy.deepcopy(break_points)break_points_plt.insert(0,0)break_points_plt.append(len(min_entity)foriinrange(len(break_points_plt)-1):
routes.append(min_entitybreak_points_plti:
break_points_plti+1)forrouteinroutes:
if0inroute:
route.remove(0)route.insert(0,0)route.append(0)forrouteinroutes:
print(route)print(min(t)#每次迭代的最优路径print(最短路径距离之和为,min(t),)plt.plot(t)#画出每次迭代的最优个体对应的环路程这我传的是个22*22的距离矩阵,读者在使时需要定义矩阵和断点。
该矩阵第元素如下:
0.00000e+00,1.00000e+00,6.83910e+04,6.81450e+04,4.29630e+04,4.13760e+04,7.52490e+04,7.09670e+04,7.82330e+04,7.34120e+04,4.08460e+04,4.09140e+04,8.49820e+04,8.49350e+04,8.18330e+04,5.04900e+04,4.71150e+04,3.36550e+04,3.35980e+04,3.16970e+04,6.96790e+04,7.21160e+04,6.93410e+04,5.62990e+04,5.16090e+04断点设置在中间,也就是22整除2,将22个点均分成两份,每份11个点,然后两位旅商分别从第个点出发,巡游各需要访问的点,再回到起点。
具体迭代过程在上中已经阐述。
最终得到的结果plot如下:
五、总结遗传算法是种仿进化启发式算法,该算法不保证搜索到最优解,但是借鉴物进化中优胜劣汰,物竞天择的思想,随机初始化个体之后使适应度函数对个体的优劣进评测,然后选择较为优秀的个体进交配,较劣的个体淘汰。
们期望优秀的个体之间交配能产更优的个体,如此代代传承进化下去,得到越来越优秀的个体。
当然,优秀的个体之间交叉之后,并不保证其后代定优于双亲,因此遗传算法也可能收敛到局部最值或者近优值。
当然,这也是所有仿进化算法的特性。
前还没有能完全解决NPC问题的有效算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- TSP MTSP 问题 遗传 算法 详细 解读 python 实现