第24卷第9期计算机仿真2007年9月:1006-9348(200709-0155-03一种改进的蚁群算法在TSP问题中的应用研究刘少伟,王洁(空军工程大学导弹学院,陕西三原713800摘要:蚁群算法是近几年发展起来的一种新型的拟生态启发式算法,它已经被成功地应用在旅行商(TSP问题上。由于基本蚁群算法存在过早陷入局部最优解和收敛性较差等缺点,文中对基本蚁群算法在基于蚁群系统的基础上进行了改进,在信息素的更新和解的搜索过程中更多地关注了局部最优解的信息,以使算法尽可能地跳出局部最优,并且改进后的算法对一些关键参数更容易控制。多次实验表明改进的蚁群算法在解决TSP问题上与基本蚁群算法相比有较好的寻优能力和收敛能力。这种算法可以应用在其它组合优化问题上,有一定的工程应用价值。关键词:蚁群算法;蚁群系统;信息素;旅行商问题:TP202+.7文献标识码:AAnImprovedantColonyOptimizationAlgorithmandItsApplicationinSolvingTSPLIUShao-wei,WANG激e(TheMissileInstitute,AFEU,SanyuanShanxi713800,ChinaABSTRACT:TheAntColonyOptimization(ACOalgorithmisanewmeta-heuristicalgorithmandhasbeensuc2cessfullyusedtosolveTravelingSalesmanProblem(TSP.BecausetheclassicalACOeasilytrapsinthelocalbestsolutionandhasworseperformanceinconvergence,thepaperimprovestheclassicalACObasedontheAntColonySystem.Theinformationoflocalbestsolutionisfocusedonupdatingthepheromoneandsearchingbestsolution,andthekeyparametersarecontrolledeasilyinimprovedalgorithm.Theresultshaveshownthattheperformanceofthisal2gorithmcanbeimprovedinfindingoptimalsolutionandquickconvergenceofTSP.Itwouldbeinterestingtoapplythisalgorithmtoothercombinatorialoptimizationproblems.KEYWORDS:ACO(Antcolonyoptimizationalgorithm;ACS(Antcolonysystem;Pheromone;Travelingsales2manproblem1引言蚁群算法(ACO是受自然界中真实蚁群的集体觅实行为的启发而发展起来的一种基于群体的模拟进化算法,它是由意大利学者DorigoM.[1]在1992年最先提出来的。这种算法已经成功地被应用在TSP(TravelingSalesmanProblem以及其它组合优化的算例中,而且很多情况下其优化结果优于遗传算法(GA、模拟退火算法(SA、进化规划(EP等[2][3]。蚁群算法具有智能搜索、全局优化、鲁棒性、正反馈等优点,因此正引起国内外越来越多的专家学者的关注。但是由于蚁群算法也存在这一些缺点,比如容易过早陷入局部最优、易出现停滞等,本文提出了一种改进的蚁群算法,试图说明改进的算法在解决TSP问题上有较好的性能。2基本蚁群算法本文主要针对TSP问题来介绍蚁群算法,TSP可以用n个城市的一个有向图G=(N,A表示,其中,N={1,2,…,n},A={(i,j|i,j∈N},城市间的距离D=(dijn×n,W=(i1,i2,…,in为城市1,2,…,n的一个排列,in+1=i1。基本蚁群算法可以表述为:在算法初始时刻,在TSP图中的每一条弧(i,j赋信息素初值τij(0=c,c为常数。把m只蚂蚁随机地放在n个城市上。接下来,蚂蚁根据路径上残留的信息素τ和可见度η独立地选择下一个城市。在时刻t,蚂蚁k从城市i转移到城市j的概率pkij为:pkij=ταij(k-1ηβij(k-1∑l∈R(sταil(k-1ηβil(k-1jR∈k(s0j|RK(s(1其中,Rk(s=N-tabuk表示蚂蚁下一步允许选择的下一个收稿日期:2006-08-15修回日期:2006-08-18城市集合。列表记录了tabuk记录了蚂蚁当前走过的城市。当所有n个城市加入tabuk中时,蚂蚁k便完成了一次周游,此时蚂蚁k走过的路径便是TSP问题的一个可行解。在式(1中,一般取可见度ηij=1/dij,α为残留信息的相对重要程度,β为预见值的相对重要程度。当所有蚂蚁完成一次周游后,各路径上的信息素根据(2式更新。τij(t+n=(1-ρ3τij(t+Δτij(2Δτij=∑mk=1Δτkij(3其中ρ∈(0,1为路径上信息素的蒸发系数,Δτij表示本次迭代弧(i,j上信息素的增量。Δτkij表示第k只蚂蚁在本次迭代中留在弧(i,j上的信息素。如果蚂蚁k没有经过弧(i,j,Δτkij的值为零。Δτkij可以表示为:Δτkij=QLk蚂蚁k在本次周游中经过弧(i,j0否则(4式中,Q为正常数,Lk表示第k只蚂蚁在本次周游中走过路径的长度。在基本蚁群算法中,α、β、ρ...