学年论文——基于蚁群算法的旅行商问题研究

《学年论文——基于蚁群算法的旅行商问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、魏倩南京信息工程大学信息与控制学院自动化系，南京210044摘要：介绍了蚂蚁算法的背景，原理及其算法流程。基于matlab软件，采用蚁群算法，求解一个具有30个城市的旅行商问题，并对算法中的三个参数设置问题进行了详细分析，讨论了单一参数变化时对算法性能的彫响，并进一步指出了算法改进的思路和方向.关键词：蚁群算法，旅行商问题，性能分析，mallabResearchonTSPBasedonAntColonyAlgorithmweiqianSchoolofinformationandcontrol,NanjingUniversityofInformationSci

2、ence&Technology,Nanjing210044ABSTRACT:Thispaperpresentsthebackgroundofantcolonyalgorithm,itsprincipleanditsalgorithmprocess.ItdiscussesthethreeparametersandtherelationshipbetweentheparameterandtheperformanceofthealgorithmwhenthealgorithmisusedtosolvetheTSPproblemof30citiesonthebasi

3、sofmatlabsoftwareindetail・Whatismore,itpointsoutthethoughtanddirectiontoimprovethemethod・Keyword:antcolonyalgorithm;travelingsalesmanproblem;performanceanalysis;matlab1.引言:研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是口组织的。许多场合，尽管这些合作是很简单的，但是其能解决复杂的问题。这种由群居性生物产生出来的一种集体性行为即群体智能,引起了包括计算机科学家在内的很多研究人

4、员的兴趣。而蚁群优化算法(AntColonyOptimization,AC0)就是一种在蚁群的群居性觅食的基础上形成的一种模拟进化算法，是20世纪90年代意大利的M.Dorigo等学者提出的，并.「L取得了较好的实验结果。受他们的影响许多的学者也在该算法I：得到了许多的研究成果⑴。10多年来，对蚁群算法的研究表明：蚁群算法不仅能够智能搜索全局最优而且具冇鲁棒性、正反馈、分布式计算、易丁•与其他算法融合等特点。利用正反馈原理可以加快进化过程，分布式计算使该算法易于并行实现，蚁群算法易于与其他算法结合可以改善算法的性能，由其鲁棒性，故在基木算法的基础上稍作修改，

5、便可以应用丁•其他问题，所以，蚁群算法问世以来，为诸多领域解决复杂优化问题提供了有力的-T•具。M.Dorigo等人将蚁群算法应用于求解旅行商问题、资源的二次分配等经典问题得到较好的结果⑵。后来的好多的学者将算法进行改进后应用丁其他方面。如：将蚁群算法改进后应用于求解连续的优化问题、智能交通、电信路由控制、机器人的路径选择以及图像分割中等⑶。10多年来，人们对于蚁群算法的研究不断深入，其解决优化问题的作用不断提高，但是蚁群算法存在搜索吋间长、易于停滞以及陷入局部最优的缺点，为了克服这些缺点不少学者提出了改进算法⑷。木文以TSP问题为例进行测试，实验结果表明此

6、算法具有较好的性质。2.TSP问题和蚁群算法2.1TSP问题TSP问题即旅行售货商问题(travelingsalesmanproblem)0描述如下：给定n个城市的集合{1,2,…，n}及城市之间环游的费用力。TSP问题是指找到一条经过每个城市至少一次只回到起点的最小费用的环游。若将每个城市看成是图上的一个顶点，费用Gjg,j5n,iH力看成连接顶点岭和岭的边上的权，则TSP问题就是在一个具有n个顶点的图上找到一条费用最小的Hamilton回路。任意两个城市A,B,如果A到B的旅行代价和B到A旅行代价相等，称这样的TSP问题是对称的TSP问题，否则称为不对称

7、的TSP问题。通常，在没有特别中明的悄况卜•所提及的TSP问题指对称的TSP间题。口TSP问题提出以来其求解方法得到了不断的改进，冃前已经可以对上万个城市的TSP问题进行求解。近年来，以蚁群行为为基础的蚁群算法已成为一种较为有效的TSP问题求解方法。2.2基本蚁群算法2.2.1蚁群算法原理蚁群算法(AntColonyalgorithm,ACA)是DorigoM等人于1991年捉出的。经观察发现，蚂蚁个体Z间是通过一种称Z为信息素(pheromone)的物质进行信息传递的。在运动过程中，蚂蚁能够在它所经过的路径上留下该种信息索，而且能够感知信息索的浓度，并以此

8、指导白己的运动方向，倾向于朝着信息素浓度高的方向移动