求解TSP问题的一种改进蚁群算法.pdf

《求解TSP问题的一种改进蚁群算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、控制理论与应用《自动化技术与应用》2010年第29卷第7期ControlTheo~andApplications求解TSP问题的一种改进蚁群算法王峰峰，王仁明，伍佳(三峡大学电气与新能源学院，湖北宜昌433002)摘要：TSP问题是典型的NP—hard组合优化问题，用蚁群算法求解此问题存在搜索时间长，容易陷入局部最优解的不足。本文提出了一种改进的蚁群算法。该算法在蚁群算法中植入遗传算法，利用遗传算法生成信息素的分布，克服了蚁群算法中搜索时问K的缺陷。此外，在蚁群算法寻优中，采用交叉和变异的策略，改善了TSP解的质量。仿真结果显示，改进的蚁群算法是有效的。关键词：蚁群算法；遗传算法；TSP问题中

2、图分类号：TP18文献标识码：A文章编号：10037241(2010)07—0001—03AnImprovedAntColonyAlgorithmforSolvingTSPWANGFeng-feng，WANGRen-ming，WUJia(CollegeofElectricalandNewEnergy,ThreeGorgesUniversity,Yichang433002China)Abstract：TSPisaclassicalNP—hardcombinatorialoptimization．Therearesomedrawbackssuchaslongtimesearchingandfall

3、intolocaloptimalsolution．ThispaperpresentsanoptimizedalgorithmforsolvingTSP．Theproposedalgorithmcombinestheantcolonyalgorithmandgeneticalgorithm．ItusesGAtogeneratethedistributionofpheromone．Inaddition，intheantcolonyalgorithm，thecrossoverandmutationstrategiesisusedtoimprovethequalityofTSPsolution．The

4、simulationresultshowsthattheimprovedalgorithmoptimizestheTSPintimeandperformance．Keywords：hntcolonyalgorithm；geneticalgorithm；TSPoptimization1引言似之处，是一种求解NP-HARD问题较有潜力的随机优化算法。然而用蚁群算法求解TSP存在搜索时间长、容旅行商问题(TravelingSalesmanProblem，TSP)是一个易于描述却难以处理的NP—HARD问题。它可描易陷入局部最优解等缺点，并且随着城市数目的增多，TSP问题求解的空间和时间复杂度呈指数级

5、增长。述为：假设有一个旅行商人从自己所在的城市出发去拜为了克服蚁群算法的缺陷，本文将遗传算法融入到访n个城市，要求每个城市只能拜访一次，而且最后要蚁群算法中[4】。首先利用遗传算法的随机搜索、快速性、回到原来出发的城市。路径的选择目标是要求一条最全局收敛性产生寻找最优路径的初始信息素分布，然后短的周游路径。由于TSP问题在智能机器人路径规划、充分利用蚁群算法的并行性、正反馈机制以及求解效城市管道铺设优化、交通运输、电路板设计以及物流配率高等特性求解出TSP的最优解。改进的算法汲取了送等领域内有着广泛的应用，因此，能快速、有效地求两种算法的优点，克服各自的缺陷。在时间效率上优于解TSP问题有着重

6、要的意义。蚁群算法，在求解效率上优于遗传算法，加快了收敛速近年来，人们从仿生学的机理中收到启发，提出了许多用于求解TSP问题的新方法，如模拟退火算法⋯1、度，较好地求解了TSP问题。遗传算法【2I、神经网络【】等。其中，由意大利学者ColorniA、DorigoM和ManiezzoV于1992年首先提出来的2改进蚁群算法的主要操作蚁群算法是基于蚂蚁觅食行为的一种仿生优化算法。改进的蚁群算法的基本思路是首先由遗传算法产该算法与自然界蚁群的觅食行为以及旅行商问题有相生较优解，较优的路径上留下信息素，其他不改变；然后让蚂蚁按照蚁群算法，完成一次遍历后，再让蚂蚁作遗收稿日期：2010-04—14传算法

7、的交叉操作和变异操作，从而得到较优的解。《自动化技术与应用》2010年第29卷第7期控制理论与应用OontrolTheoryandApplications2。1算法设计见度的相对重要性。b)信息素更新方程(1)改进算法中遗传算法的设计fl(，+刀)：ro(t)十△(2)本文以城市的遍历次序作为遗传算法的编码，适应度函数取为哈密顿圈的长度的倒数。利用rand函数随机生式中，P(0<<1)表示更新信息