基于蚁群算法的旅行商问题研究

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

1、学年论文(课程设计)题目基于蚁群算法的旅行商问题研究学生姓名魏倩学号20071336124学院信息与控制学院专业自动化指导教师申晓宁二Ｏ一Ｏ年12月3日基于蚁群算法的旅行商问题研究魏倩南京信息工程大学信息与控制学院自动化系，南京210044摘要：介绍了蚂蚁算法的背景，原理及其算法流程。基于matlab软件，采用蚁群算法，求解一个具有30个城市的旅行商问题，并对算法中的三个参数设置问题进行了详细分析，讨论了单一参数变化时对算法性能的影响,并进一步指出了算法改进的思路和方向。关键词：蚁群算法，旅行商问题，性能分析，matlabResearchonTSPBasedo

2、nAntColonyAlgorithmweiqianSchoolofinformationandcontrol,NanjingUniversityofInformationScience&Technology,Nanjing210044ABSTRACT：Thispaperpresentsthebackgroundofantcolonyalgorithm,itsprincipleanditsalgorithmprocess.Itdiscussesthethreeparametersandtherelationshipbetweentheparameterandt

3、heperformanceofthealgorithmwhenthealgorithmisusedtosolvetheTSPproblemof30citiesonthebasisofmatlabsoftwareindetail.Whatismore,itpointsoutthethoughtanddirectiontoimprovethemethod.Keyword:antcolonyalgorithm;travelingsalesmanproblem;performanceanalysis;matlab1.引言：研究群居性昆虫行为的科学家发现，昆虫在群落一级

4、上的合作基本上是自组织的。许多场合，尽管这些合作是很简单的，但是其能解决复杂的问题。这种由群居性生物产生出来的一种集体性行为即群体智能，引起了包括计算机科学家在内的很多研究人员的兴趣。而蚁群优化算法（AntColonyOptimization，ACO）就是一种在蚁群的群居性觅食的基础上形成的一种模拟进化算法，是20世纪90年代意大利的M.Dorigo等学者提出的，并且取得了较好的实验结果。受他们的影响许多的学者也在该算法上得到了许多的研究成果[1]。10多年来，对蚁群算法的研究表明：蚁群算法不仅能够智能搜索全局最优而且具有鲁棒性、正反馈、分布式计算、易于与其他

5、算法融合等特点。利用正反馈原理可以加快进化过程，分布式计算使该算法易于并行实现，蚁群算法易于与其他算法结合可以改善算法的性能，由其鲁棒性，故在基本算法的基础上稍作修改，便可以应用于其他问题，所以，蚁群算法问世以来，为诸多领域解决复杂优化问题提供了有力的工具。M.Dorigo等人将蚁群算法应用于求解旅行商问题、资源的二次分配等经典问题得到较好的结果[2]。后来的好多的学者将算法进行改进后应用于其他方面。如：将蚁群算法改进后应用于求解连续的优化问题、智能交通、电信路由控制、机器人的路径选择以及图像分割中等[3]。10多年来，人们对于蚁群算法的研究不断深入，其解决优

6、化问题的作用不断提高，但是蚁群算法存在搜索时间长、易于停滞以及陷入局部最优的缺点，为了克服这些缺点不少学者提出了改进算法[4]。本文以TSP问题为例进行测试，实验结果表明此算法具有较好的性质。2．TSP问题和蚁群算法2.1TSP问题TSP问题即旅行售货商问题(travelingsalesmanproblem)。描述如下:给定n个城市的集合{1,2,…,n}及城市之间环游的费用。TSP问题是指找到一条经过每个城市至少一次且回到起点的最小费用的环游。若将每个城市看成是图上的一个顶点,费用看成连接顶点和的边上的权,则TSP问题就是在一个具有n个顶点的图上找到一条费用

7、最小的Hamilton回路。任意两个城市A,B,如果A到B的旅行代价和B到A旅行代价相等,称这样的TSP问题是对称的TSP问题，否则称为不对称的TSP问题。通常,在没有特别申明的情况下所提及的TSP问题指对称的TSP间题。自TSP问题提出以来其求解方法得到了不断的改进，目前已经可以对上万个城市的TSP问题进行求解。近年来,以蚁群行为为基础的蚁群算法已成为一种较为有效的TSP问题求解方法。2.2基本蚁群算法2.2.1蚁群算法原理蚁群算法(AntColonyalgorithm,ACA)是DorigoM等人于1991年提出的。经观察发现,蚂蚁个体之间是通过一种称之为

8、信息素(pheromone)的物质进行