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

学年论文(课程设计)题目基于蚁群算法的旅行商问题研究学生姓名魏倩学号20071336124学院信息与控制学院专业自动化指导教师申晓宁二Ｏ一Ｏ年12月3日基于蚁群算法的旅行商问题研究魏倩南京信息工程大学信息与控制学院自动化系，南京210044摘要：介绍了蚂蚁算法的背景，原理及其算法流程。基于matlab软件，采用蚁群算法，求解一个具有30个城市的旅行商问题，并对算法中的三个参数设置问题进行了详细分析，讨论了单一参数变化时对算法性能的影响,并进一步指出了算法改进的思路和方向。关键词：蚁群算法，旅行商问题，性能分析，matlabResearchonTSPBasedonAntColonyAlgorithmweiqianSchoolofinformationandcontrol,NanjingUniversityofInformationScience&Technology,Nanjing210044ABSTRACT：Thispaperpresentsthebackgroundofantcolonyalgorithm,itsprincipleanditsalgorithmprocess.ItdiscussesthethreeparametersandtherelationshipbetweentheparameterandtheperformanceofthealgorithmwhenthealgorithmisusedtosolvetheTSPproblemof30citiesonthebasisofmatlabsoftwareindetail.Whatismore,itpointsoutthethoughtanddirectiontoimprovethemethod.Keyword:antcolonyalgorithm;travelingsalesmanproblem;performanceanalysis;matlab1.引言：研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的。许多场合，尽管这些合作是很简单的，但是其能解决复杂的问题。这种由群居性生物产生出来的一种集体性行为即群体智能，引起了包括计算机科学家在内的很多研究人员的兴趣。而蚁群优化算法（AntColonyOptimization，ACO）就是一种在蚁群的群居性觅食的基础上形成的一种模拟进化算法，是20世纪90年代意大利的M.Dorigo等学者提出的，并且取得了较好的实验结果。受他们的影响许多的学者也在该算法上得到了许多的研究成果[1]。10多年来，对蚁群算法的研究表明：蚁群算法不仅能够智能搜索全局最优而且具有鲁棒性、正反馈、分布式计算、易于与其他算法融合等特点。利用正反馈原理可以加快进化过程，分布式计算使该算法易于并行实现，蚁群算法易于与其他算法结合可以改善算法的性能，由其鲁棒性，故在基本算法的基础上稍作修改，便可以应用于其他问题，所以，蚁群算法问世以来，为诸多领域解决复杂优化问题提供了有力的工具。M.Dorigo等人将蚁群算法应用于求解旅行商问题、资源的二次分配等经典问题得到较好的结果[2]。后来的好多的学者将算法进行改进后应用于其他方面。如：将蚁群算法改进后应用于求解连续的优化问题、智能交通、电信路由控制、机器人的路径选择以及图像分割中等[3]。10多年来，人们对于蚁群算法的研究不断深入，其解决优化问题的作用不断提高，但是蚁群算法存在搜索时间长、易于停滞以及陷入局部最优的缺点，为了克服这些缺点不少学者提出了改进算法[4]。本文以TSP问题为例进行测试，实验结果表明此算法具有较好的性质。2．TSP问题和蚁群算法2.1TSP问题TSP问题即旅行售货商问题(travelingsalesmanproblem)。描述如下:给定n个城市的集合{1,2,…,n}及城市之间环游的费用(1,,)ijCijnij。TSP问题是指找到一条经过每个城市至少一次且回到起点的最小费用的环游。若将每个城市看成是图上的一个顶点,费用(1,,)ijCijnij看成连接顶点iV和jV的边上的权,则TSP问题就是在一个具有n个顶点的图上找到一条费用最小的Hamilton回路。任意两个城市A,B,如果A到B的旅行代价和B到A旅行代价相等,称这样的TSP问题是对称的TSP问题，否则称为不对称的TSP问题。通常,在没有特别申明的情况下所提及的TSP问题指对称的TSP间题。自TSP问题提出以来其求解方法得到了不断的改进，目前已经可以对上万个城市的TSP问题进行求解。近年来,以蚁群行为为基础的蚁群算法已成为一种较为有效的TSP问题求解方法。2.2基本蚁群算法2.2.1蚁群算法原理蚁群算法(AntColonyalgorithm,ACA)是DorigoM等人于1991年提出的。经观察发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递的。在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素,而且能够感知信息素的浓度,并以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动。因此,蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的[5]。2.2.2蚁群算法基本模型以具有代表性的TSP问题为例,设有n个城市,蚂蚁数量为m,(,1,2,3....)ijdijn表示城市i和j之间的距离,()ijt表示在t时刻城市i和j之间的路径上残留的信息量,来模拟实际蚂蚁的信息素浓度。初始化时,m个蚂蚁被放置在不同的城市上,并赋予每条边上的信息量为(0)ij。蚂蚁k的tabuk(禁忌表)的第一个元素赋值为它所在的城市。用()kijPt表示在t时刻蚂蚁k由城市i转移到城市j的概率,则()(),()()()0,kijijkkisisijsallowedttjallowedttPtotherwise(1)其中kallowed表示蚂蚁k下一步允许走过的城市的集合,它随蚂蚁k的行进过程而动态改变;信息量()ijt随时间的推移会逐步衰减,,分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同作用;()ijt为由城市i转移到城市j的期望程度,可根据某种启发算法而定。经过n个时刻,蚂蚁k走完所有的点,完成一次循环。此时,要根据下面公式更新各路径上的信息量:()(1)()()ijijijtntt（2）其中1()()mkijijktt（3）表示信息素挥发系数，()kijt表示蚂蚁k在本次循环中在点i和点j之间留下的信息量,其计算方法根据计算模型而定,在最常用的antcyclesystem模型中：,()0,kkijQkijLtotherwise若蚂蚁在本次循环中经过点和（4）其中Q为常数,kL为蚂蚁k在本次循环中所走路径的长度。2.2.3蚁群算法流程步骤1：nc=0(nc为迭代步数或搜索次数);每条边上的(0)()ijc常数,并且(0)0ij;放置m个蚂蚁到n个城市上。步骤2：将各蚂蚁的初始出发点置于当前解集tabuk(s)中;对每个蚂蚁k(k=1,…,m),按概率()kijPt移至下一城市j;将城市j置于tabuk(s)中。步骤3：经过n个时刻,蚂蚁k可走完所有的城市,完成一次循环。计算每个蚂蚁走过的总路径长度kL,更新找到的最短路径。步骤4：更新每条边上的信息量()ijtn。步骤5：对每一条边置0ij;nc=nc+1。步骤6:若nc预定的迭代次数MAXNC,则转步骤2;否则,打印出最短路径,终止整个程序。2.2.4影响蚁群算法效果的因素[6](1)局部搜索策略。人工蚂蚁在选择将要行走的路线时,所采用的策略是随机的局部搜索策略。这个策略主要基于以下两点:①蚂蚁个体保留的“经验”;②问题中公开可用的信息素轨迹和局部信息。(2)蚂蚁的内部状态。内部状态主要保留了对决策有用的信息,用于计算生成解的价值、优劣度和每个执行步的贡献。(3)信息素轨迹。由于信息素轨迹的正反馈机制,选择某路径的蚂蚁越多,一个执行步得到的回报就越多,该路径对于后继蚂蚁的吸引力也就越大。(4)蚂蚁决策策略。蚂蚁的决策策略是由信息素函数与启发信息函数共同决定的,即概率表。利用基于概率的原理再配合信息素挥发机制,避免了所有蚂蚁都过早地早熟收敛。3．仿真研究3.1任务要求基于ant—cycle模型，采用蚁群算法求解具有30个城市的TSP问题。各城市坐标如下：41，94；37，84；54，67；25，62；7，64；2，99；68，58；71，44；54，62；83，69；64，60；18，54；22，60；83，46；91，38；25，38；24，42；58，69；71，71；74，78；87，76；18，40；13，40；82，7；62，32；58，35；45，21；41，26；44，35；4，50要求：1.采用Matlab7.1实现上述优化程序。给出得到的最短路径，用Matlab画出最短路径所连接的城市地图。2．分析3个参数：信息激素的启发因子、自启发量因子、信息激素残留系数取不同值时对算法性能的影响。3.2程序分析function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%%=========================================================================%%ACATSP.m%%AntColonyAlgorithmforTravelingSalesmanProblem%%-------------------------------------------------------------------------%%主要符号说明%%Cn个城市的坐标，n×2的矩阵%%NC_max最大迭代次数%%m蚂蚁个数%%Alpha表征信息素重要程度的参数%%Beta表征启发式因子重要程度的参数%%Rho信息素蒸发系数%%Q信息素增加强度系数%%R_best各代最佳路线%%L_best各代最佳路线的长度%%===================================================================C=[41，94；37，84；54，67；25，62；7，64；2，99；68，58；71，44；54，62；83，69；64，60；18，54；22，60；83，46；91，38；25，38；24，42；58，69；71，71；74，78；87，76；18，40；13，40；82，7；62，32；58，35；45，21；41，26；44，35；4，50];m=31;Alpha=1;Beta=5;Rho=.7;NC_max=30;Q=100;%%第一步：变量初始化n=size(C,1);%表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵fori=1:nforj=1:nifi~=jD(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;两个城市之间的距离elseD(i,j)=eps;endD(j,i)=D(i,j);endendEta=1./D;%Eta为启发因子，这里设为距离的倒数Tau=ones(n,n);%Tau为信息素矩阵Tabu=zeros(m,n);%存储并记录路径的生成NC=1;%迭代计数器R_best=zeros(NC_max,n);%各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度whileNC=NC_max%停止条件之一：达到最大迭代次数%%第二步：将m只蚂蚁放到