蚁群遗传算法对于TSP问题应用

文章编号：1007-1423（2020）25-0022-05DOI：10.3969/j.issn.1007-1423.2020.25.004改进蚁群算法在TSP问题中的应用徐书扬，王海江（浙江科技学院，杭州310023）摘要：针对蚁群算法求解TSP问题易陷入局部最优，求解结果精度低的问题，提出一种蚁群算法的改进方案以更有效地避免算法陷入局部最优，进而提高算法搜索最优路径的能力。

将TSP问题中点与点之间的距离信息引入初始各路径信息素残留量的赋值中，使得算法迭代初期各路径信息素残留量对算法的收敛更具导向性；在算法收敛到一定程度时，加快路径残留信息素的挥发速度，并减小蚂蚁走过路径所留下的信息素量，从而提高算法整体的全局搜索能力，增加探寻到潜在更优路径的可能性；当算法收敛到可能陷入局部最优的情况时，重置各路径信息素残留量，重新探寻最优路径，减小算法陷入局部收敛的概率。

通过MATLAB2018b对多个TSP实例问题进行编程求解，最终的仿真实验结果表明改进后蚁群算法能有效提高算法的正确收敛率和求解结果精确度。

关键词：蚁群算法；路径规划；局部最优；旅行商问题基金项目：浙江省基金项目：面向物联网的密文检索技术研究（No.LQ20F020010）0引言蚁群算法是一种于1992年由文献[1]用于寻找最优路径的经典概率型算法。

与其他启发式算法相比，蚁群算法具有良好的鲁棒性（可改进方向多，适用于多种问题的解决）以及优越的全局搜索能力（蚁群算法往往以全局最优为目标解决问题）。

因此，蚁群算法在多个领域中得以应用，例如：区域建设[2]、路径规划[3-6]、影像测量[7]、调度管理[8-9]等。

然而，蚁群算法也同样存在一些不足之处，例如：在处理信息量较大的问题时迭代速度过慢，算法易陷入局部最优而错过最优解，对参数的设置有很高的要求，错误的参数设置容易导致结果误差过大等[10-11]。

针对传统蚁群算法存在的问题，不少学者提出蚁群算法的改进方案来解决蚁群算法本身的缺陷。

用蚁群算法解决TSP 问题一、引言蚁群算法是一种受自然界生物行为启发而产生的“自然”算法，产生于对蚂蚁行为的研究。

蚁群中的蚂蚁以“信息素”为媒介，间接异步的相互联系。

蚂蚁在行动中，会在他们经过的地方留下一些化学物质，称为“信息素”。

这些物质能被同一种群众后来的蚂蚁感受到，并作为一种信号影响后者的行动，具体表现在后到的蚂蚁选择有这些物质的路径的可能性比选择没有这些物质的路径的可能性大的多。

后者留下的信息素会对原有的信息素进行加强，并循环下去。

这样，经过蚂蚁多的路径，后到蚂蚁选择这条路径的可能性就越来越大。

由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的信息素就越多，在下一个时间内被其他的蚂蚁选中的可能性也越大。

这个过程会持续到所有的蚂蚁都走到最短的那一条路径为止。

二、关键技术（1） 解的表达形式在应用蚁群优化算法时，只需要建立一个虚拟的始终点，相当于蚁群的巢穴和食物所在地，这样一个所经过城市的路径的排列就构成了一个解；（2） 信息素的记忆和更新在算法开始时，由于从来没有蚂蚁去寻找过路径，因此可以认为是没有任何先验信息，即每条路上的信息相等。

客观地将，信息素应该都为0，但是由于在蚁群算法中，信息素决定了蚂蚁选择这条路径的概率，因此可以认为初始信息素矩阵为：1/(*(1))0ij N N p -⎧=⎨⎩i j i j ≠=其中N 为城市数 当算法运行过程中，每次放出m 支蚂蚁，每只蚂蚁按照信息素选择路径，将其中路径最短的记录下来，对这条最短路进行信息素的加强；而对于其他路径，因为信息素的挥发，信息素浓度将会降低，更新后的信息素矩阵为： 11(1)//(1)/k ij k ij k ij p N p p ρρρ--⎧-+⎪=⎨-⎪⎩i j i j →→经过路径不经过路径其中N 为城市数，ρ为挥发系数 （3） 蚁群的规模在一般应用中，蚁群中蚂蚁的个数m 是固定数，不超过TSP 图的节点数。

三、算法实现步骤1 设定蚁群规模m ，计算次数n ，挥发系数ρ，初始化信息素矩阵，设定变量best =+∞记录全局最优解；步骤2 若n =0，推出并输出结果；否则n=n-1，分别放出m 只蚂蚁，按照信息素概率选择路径，并找出m 条路径中的当代最优路径cubest ； 步骤3 根据当代最有路径更新信息素；步骤4 如果cubest<best ，best=cubest ，执行步骤2；否则直接执行步骤2；四、结果及分析通过五个城市节点的TSP 问题的求解，其城市间的距离矩阵为：01015621008139158020156132005291550⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭蚁群算法找到的最优路径为A C B D E →→→→，总路程为43；通过试验结果发现，对于小规模的ＴＳＰ问题，蚁群算法和禁忌搜索、模拟退火算法的计算结果相似，而且耗时很短，因此该算法是合理的。

蚁群算法（ACO）解决TSP问题⼀、蚁群算法1.基本原理蚁群算法（Ant Colony Optimization，ACO）是⼀种基于种群寻优的启发式搜索算法，有意⼤利学者M.Dorigo等⼈于1991年⾸先提出。

该算法受到⾃然界真实蚁群集体在觅⾷过程中⾏为的启发，利⽤真实蚁群通过个体间的信息传递、搜索从蚁⽳到⾷物间的最短路径等集体寻优特征，来解决⼀些离散系统优化中的困难问题。

经过观察发现，蚂蚁在寻找⾷物的过程中，会在它所经过的路径上留下⼀种被称为信息素的化学物质，信息素能够沉积在路径上，并且随着时间逐步挥发。

在蚂蚁的觅⾷过程中，同⼀蚁群中的其他蚂蚁能够感知到这种物质的存在及其强度，后续的蚂蚁会根据信息素浓度的⾼低来选择⾃⼰的⾏动⽅向，蚂蚁总会倾向于向信息素浓度⾼的⽅向⾏进，⽽蚂蚁在⾏进过程中留下的信息素⼜会对原有的信息素浓度予以加强，因此，经过蚂蚁越多的路径上的信息素浓度会越强，⽽后续的蚂蚁选择该路径的可能性就越⼤。

通常在单位时间内，越短的路径会被越多的蚂蚁所访问，该路径上的信息素强度也越来越强，因此，后续的蚂蚁选择该短路径的概率也就越⼤。

经过⼀段时间的搜索后，所有的蚂蚁都将选择这条最短的路径，也就是说，当蚁巢与⾷物之间存在多条路径时，整个蚁群能够通过搜索蚂蚁个体留下的信息素痕迹，寻找到蚁巢和⾷物之间的最短路径。

蚁群算法中，蚂蚁个体作为每⼀个优化问题的可⾏解。

⾸先随机⽣成初始种群，包括确定解的个数、信息素挥发系数、构造解的结构等。

然后构造蚁群算法所特有的信息素矩阵每只妈蚁执⾏蚂蚊移动算⼦后，对整个群体的蚂蚁做⼀评价，记录最优的蚂蚁。

之后算法根据信息素更新算⼦更新信息素矩阵，⾄此种群的⼀次选代过程完成。

整个蚂蚁群体执⾏⼀定次数的选代后退出循环、输出最优解。

2.术语介绍（1）蚂蚁个体。

每只蚂蚁称为⼀个单独的个体，在算法中作为⼀个问题的解。

（2）蚂蚁群体。

⼀定数量的蚂蚁个体组合在⼀起构成⼀个群体，蚂蚁是群体的基本单位。

蚁群算法在TSP问题中的应用研究作者：刘援农来源：《硅谷》2011年第13期摘要：随着计算机技术的发展，各种算法技术也不断在更新，特别是在模仿社会性动物行为领域产生很多智能算法。

主要介绍蚁群算法，阐述其工作原理和特点及使用它求解TSP 问题的具体实现。

关键词：蚁群算法；TSP；群体智能中图分类号：TP273 文献标识码：A 文章编号：1671－7597（2011）0710108－01目前，在大力发展生物启发式计算研究的背景下，社会性动物如蚁群、蜂群、鸟群等的自组织行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的“群集智能”（swarm intelligence，简称SI）。

社会性动物的妙处在于：个体行为简单，但是集体协作工作能体现出一些复杂的智能行为，而在这些行为当中，又以蚁群在觅食过程中总能找到一条从蚁巢到食物源的最短路径最为引人注目。

受其启发，意大利学者M.Dorigo，V.Maniezzo和A.Colorni而于20世纪90年代初提出了一种新型的智能优化算法——蚁群算法。

该算法最初被用于求解著名的旅行商问题（Traveling Salesman Problem，简称TSP）并获得了较好的效果。

1 蚁群算法原理蚂蚁是群体动物，它们没有视觉但是可以通过集体配合劳动找到从巢穴到食物源的最短路径。

仿生学家经过大量研究后发现，蚂蚁在搜索食物时个体之间能通过在路径上留下的气味来进行信息传递，这种气味称作信息素（pheromone）。

在蚂蚁边运动边留下信息素，并且可以根据嗅到的信息素的浓度来进行前进路径的选择。

蚂蚁总是倾向于沿着信息素浓度高的方向来移动，而路径上的信息素会随着时间的推移而逐渐挥发。

信息素强弱指导蚂蚁行进，于是当一条路径上走过的蚂蚁越多，信息素浓度就会越强烈，后来的蚂蚁选择该路径的概率就越大。

这种群体行为构成了一种信息正反馈现象，蚂蚁就是通过这种反馈机制来进行信息交流，最终快速找到食物。

蚁群算法及其在TSP问题中的应用研究摘要：tsp问题是一类典型的np完全问题，蚁群算法是求解该问题的方法之一。

该文在研究蚁群算法的基本优化原理的基础上，建立了求解tsp 问题的数学模型，设计了一个求解tsp问题的蚁群算法程序，并通过仿真实验验证了算法的有效性，分析了蚂蚁规模、周游次数等因素对蚁群算法搜索结果所产生的影响。

关键词：tsp；蚁群算法；np完全问题中图分类号：tp301 文献标识码：a 文章编号：1009-3044（2013）13-3117-03旅行商问题（traveling salesman problem，简称tsp）是一个具有广泛应用背景和重要理论价值的组合优化问题，它已被证明属于np难题[1]。

目前对于求解该类问题的研究主要有两个方向：一是传统的数学规划方法，这种算法可以得到全局最优解，但复杂性往往难以接受，因而不适应于大规模复杂问题的求解。

二是近年来发展起来的各种仿生进化算法如遗传算法、蚁群算法等，此类算法能够在多项式时间内找到全局最优解或近似全局最优解[2]。

蚁群算法（ant colony algorithm，简称aca）是受自然界中蚂蚁集体寻食过程的启发而提出来的一种新的智能优化算法，它具有高度的本质并行性、正反馈选择、分布式计算、鲁棒性等优点，蚁群算法最早成功地应用于解决tsp问题。

本文在研究蚁群算法的基本优化原理的基础上，编写了一个基于vc的求解tsp问题的蚁群算法程序，并且通过多次实验测试，验证了算法的有效性，分析了蚂蚁规模、周游次数等因素对蚁群算法的搜索结果和效率所产生的影响。

1 tsp问题建模2 基于蚁群算法的tsp问题求解2.2蚁群算法的基本原理蚁群算法是一种源于自然生物界的新型仿生优化算法，它于20世纪90年代初由意大利学者m.dorigo，v.maniezzo首次提出[3]，蚁群算法的特点是模拟自然界中蚂蚁寻食的群体行为。

研究表明，蚂蚁会在走过的路上留下信息素，信息素会随时间的推移逐渐挥发消失，蚂蚁就是通过信息素进行信息交流。

⼈⼯智能结课作业-遗传算法粒⼦群寻优蚁群算法解决TSP问题代码已经发布到了github:如果帮到你了，希望给个star⿎励⼀下1 遗传算法1.1算法介绍遗传算法是模仿⾃然界⽣物进化机制发展起来的随机全局搜索和优化⽅法，它借鉴了达尔⽂的进化论和孟德尔的遗传学说。

其本质是⼀种⾼效、并⾏、全局搜索的⽅法，它能在搜索过程中⾃动获取和积累有关搜索空间的知识，并⾃适应的控制搜索过程以求得最优解。

遗传算法操作使⽤适者⽣存的原则，在潜在的解决⽅案种群中逐次产⽣⼀个近似最优解的⽅案，在遗传算法的每⼀代中，根据个体在问题域中的适应度值和从⾃然遗传学中借鉴来的再造⽅法进⾏个体选择，产⽣⼀个新的近似解。

这个过程导致种群中个体的进化，得到的新个体⽐原来个体更能适应环境，就像⾃然界中的改造⼀样。

遗传算法具体步骤：（1）初始化：设置进化代数计数器t=0、设置最⼤进化代数T、交叉概率、变异概率、随机⽣成M个个体作为初始种群P（2）个体评价：计算种群P中各个个体的适应度（3）选择运算：将选择算⼦作⽤于群体。

以个体适应度为基础，选择最优个体直接遗传到下⼀代或通过配对交叉产⽣新的个体再遗传到下⼀代（4）交叉运算：在交叉概率的控制下，对群体中的个体两两进⾏交叉（5）变异运算：在变异概率的控制下，对群体中的个体进⾏变异，即对某⼀个体的基因进⾏随机调整（6）经过选择、交叉、变异运算之后得到下⼀代群体P1。

重复以上（1）-（6），直到遗传代数为 T，以进化过程中所得到的具有最优适应度个体作为最优解输出，终⽌计算。

旅⾏推销员问题（Travelling Salesman Problem， TSP）：有n个城市，⼀个推销员要从其中某⼀个城市出发，唯⼀⾛遍所有的城市，再回到他出发的城市，求最短的路线。

应⽤遗传算法求解TSP问题时需要进⾏⼀些约定，基因是⼀组城市序列，适应度是按照这个基因的城市顺序的距离和分之⼀。

1.2实验代码import randomimport mathimport matplotlib.pyplot as plt#读取数据f=open("test.txt")data=f.readlines()#将cities初始化为字典，防⽌下⾯被当成列表cities={}for line in data:#原始数据以\n换⾏，将其替换掉line=line.replace("\n","")#最后⼀⾏以EOF为标志，如果读到就证明读完了，退出循环if(line=="EOF"):break#空格分割城市编号和城市的坐标city=line.split("")map(int,city)#将城市数据添加到cities中cities[eval(city[0])]=[eval(city[1]),eval(city[2])]#计算适应度，也就是距离分之⼀，这⾥⽤伪欧⽒距离def calcfit(gene):sum=0#最后要回到初始城市所以从-1，也就是最后⼀个城市绕⼀圈到最后⼀个城市for i in range(-1,len(gene)-1):nowcity=gene[i]nextcity=gene[i+1]nowloc=cities[nowcity]nextloc=cities[nextcity]sum+=math.sqrt(((nowloc[0]-nextloc[0])**2+(nowloc[1]-nextloc[1])**2)/10)return 1/sum#每个个体的类，⽅便根据基因计算适应度class Person:def__init__(self,gene):self.gene=geneself.fit=calcfit(gene)class Group:def__init__(self):self.GroupSize=100 #种群规模self.GeneSize=48 #基因数量，也就是城市数量self.initGroup()self.upDate()#初始化种群，随机⽣成若⼲个体def initGroup(self):self.group=[]i=0while(i<self.GroupSize):i+=1#gene如果在for以外⽣成只会shuffle⼀次gene=[i+1 for i in range(self.GeneSize)]random.shuffle(gene)tmpPerson=Person(gene)self.group.append(tmpPerson)#获取种群中适应度最⾼的个体def getBest(self):bestFit=self.group[0].fitbest=self.group[0]for person in self.group:if(person.fit>bestFit):bestFit=person.fitbest=personreturn best#计算种群中所有个体的平均距离def getAvg(self):sum=0for p in self.group:sum+=1/p.fitreturn sum/len(self.group)#根据适应度，使⽤轮盘赌返回⼀个个体，⽤于遗传交叉def getOne(self):#section的简称，区间sec=[0]sumsec=0for person in self.group:sumsec+=person.fitsec.append(sumsec)p=random.random()*sumsecfor i in range(len(sec)):if(p>sec[i] and p<sec[i+1]):#这⾥注意区间是⽐个体多⼀个0的return self.group[i]#更新种群相关信息def upDate(self):self.best=self.getBest()#遗传算法的类，定义了遗传、交叉、变异等操作class GA:def__init__(self):self.group=Group()self.pCross=0.35 #交叉率self.pChange=0.1 #变异率self.Gen=1 #代数#变异操作def change(self,gene):#把列表随机的⼀段取出然后再随机插⼊某个位置#length是取出基因的长度，postake是取出的位置，posins是插⼊的位置geneLenght=len(gene)index1 = random.randint(0, geneLenght - 1)index2 = random.randint(0, geneLenght - 1)newGene = gene[:] # 产⽣⼀个新的基因序列，以免变异的时候影响⽗种群 newGene[index1], newGene[index2] = newGene[index2], newGene[index1] return newGene#交叉操作def cross(self,p1,p2):geneLenght=len(p1.gene)index1 = random.randint(0, geneLenght - 1)index2 = random.randint(index1, geneLenght - 1)tempGene = p2.gene[index1:index2] # 交叉的基因⽚段newGene = []p1len = 0for g in p1.gene:if p1len == index1:newGene.extend(tempGene) # 插⼊基因⽚段p1len += 1if g not in tempGene:newGene.append(g)p1len += 1return newGene#获取下⼀代def nextGen(self):self.Gen+=1#nextGen代表下⼀代的所有基因nextGen=[]#将最优秀的基因直接传递给下⼀代nextGen.append(self.group.getBest().gene[:])while(len(nextGen)<self.group.GroupSize):pChange=random.random()pCross=random.random()p1=self.group.getOne()if(pCross<self.pCross):p2=self.group.getOne()newGene=self.cross(p1,p2)else:newGene=p1.gene[:]if(pChange<self.pChange):newGene=self.change(newGene)nextGen.append(newGene)self.group.group=[]for gene in nextGen:self.group.group.append(Person(gene))self.group.upDate()#打印当前种群的最优个体信息def showBest(self):print("第{}代\t当前最优{}\t当前平均{}\t".format(self.Gen,1/self.group.getBest().fit,self.group.getAvg())) #n代表代数，遗传算法的⼊⼝def run(self,n):Gen=[] #代数dist=[] #每⼀代的最优距离avgDist=[] #每⼀代的平均距离#上⾯三个列表是为了画图i=1while(i<n):self.nextGen()self.showBest()i+=1Gen.append(i)dist.append(1/self.group.getBest().fit)avgDist.append(self.group.getAvg())#绘制进化曲线plt.plot(Gen,dist,'-r')plt.plot(Gen,avgDist,'-b')plt.show()ga=GA()ga.run(3000)print("进⾏3000代后最优解：",1/ga.group.getBest().fit)1.3实验结果下图是进⾏⼀次实验的结果截图，求出的最优解是11271为避免实验的偶然性，进⾏10次重复实验，并求平均值，结果如下。