TSP的改进蚁群算法求解及其仿真研究.pdf

《TSP的改进蚁群算法求解及其仿真研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第37卷第8期合肥工业大学学报(自然科学版)Vo1．37No．82014年8月JOURNALOFHEFEIUNIVERSITYOFTECHNOLOGYAug．2014Doi：10．3969／j．issn．1003—5060．2014．08．007TSP的改进蚁群算法求解及其仿真研究杨再甫，黄友锐，曲立国葛平平(安徽理工大学电气与信息工程学院，安徽淮南232001)摘要：蚂蚁数目是影响蚁群算法性能的重要参数，常规蚁群算法在求解TSP时易于陷入局部最优解。文章针对该问题，提出了一种蚂蚁数目动态改变的蚁群算法，即每次周游时的蚂蚁数目是在一个范围内随机取值，该改进

2、算法借用遗传算法中的排序选择策略对每次遍历时的蚂蚁位置进行初始化；分别对常规蚁群算法的TSP求解和改进蚁群算法的TSP求解进行了原理阐述，并对2种算法求解TSP的结果进行了Matlab仿真。对比仿真结果表明，改进的算法在求解TsP时，能够有效地跳出局部最优解，并能很好地收敛，它比常规蚁群算法的性能要优。关键词：常规蚁群算法；改进蚁群算法；旅行商问题；局部最优解；动态蚂蚁数目中图分类号：TP18文献标识码：A文章编号：1003—5060(2014)08-0928—05SolutionofTSPbasedonimprovedantcolonyalgorithm

3、anditssimulationYANGZai—fu，HUANGYou-rui，QULi-guo，GEPing-ping(SchoolofElectricalandInformationEngineering，AnhuiUniversityofScienceandTechnology，Huainan232001，China)Abstract：Thenumberofantsisallimportantparameterthataffectstheperformanceofantcolonyal—gorithm．Astheconventionalantcolo

4、nyalgorithmforsolvingtravellingsalesmanproblem(TSP)iseasytofallintoalocaloptimalsolution，anantcolonyalgorithmbasedondynamicchangesofthenumberofantsiSproposed。inwhicheachtravelingiStobewithrandomnumberofantsinacertainrange．Besides，therankingselectionpolicyofgeneticalgorithmisusedto

5、initializethelocationofantseachtimewhentraveling．ThetheoriesoftheconventionalantcolonyalgorithmandtheimprovedantcolonyalgorithmforsolvingTSParebothexpatiated，andtheresultsofthementionedalgorithmsforsolvingTSParesimulatedbyMatlab．Thesimulationresultsshowthattheperformanceoftheim—pr

6、ovedalgorithmisbetterthanthatoftheconventionalalgorithmsincetheimprovedalgorithmcanef—fectivelyjumpoutoflocaloptimalsolutionandhasbetterconvergenceperformance．Keywords：conventionalantcolonyalgorithm；improvedantcolonyalgorithm；travellingsalesmanproblem(TSP)；localoptimalsolution；dyn

7、amicnumberofantsTSP(travellingsalesmanproblem)的任务是配送过程中的路径选择问题，结果很实用；文献求一条从起点出发周游所有城市一次又回到起点[3]采用蚁群算法改善机器人路径规划的学习效的最短路径，该问题求解繁琐。蚁群算法(ant率；文献[4]将蚁群算法用于建筑灾难现场的逃生colonyalgorithm)是一种群智能优化算法，由文路径规划，该方法能够有效找出逃生路径，提高救献[13首次提出，并用于TSP的求解。援效率。上述都是蚁群算法求解的TSP的具体’近年来，文献[2]采用改进蚁群算法解决物流应用场合，TSP的

8、应用场合还有很多。但蚁群算收稿日期：2013—09—02；修回日期