一种应用于旅行商问题的莱维飞行转移规则蚁群优化算法.pdfVIP

第41卷第5期计算机应用研究Vol.41No.5

2024年5月ApplicationResearchofComputersMay2024

一种应用于旅行商问题的莱维飞行转移规则

蚁群优化算法*

丁增良，陈珏，邱禧荷

（上海工程技术大学电子电气工程学院，上海201620)

摘要：针对旅行商问题(TSP)提出了一种基于莱维飞行转移规则的蚁群优化算法。该算法结合了基于莱维

飞行和蚁群系统算法（antcolonysystem,ACS）的转移规则，形成了一种动态权重的混合转移规则，该策略能够有

效地帮助算法跳出局部最优，增强全局有哪些信誉好的足球投注网站能力。此外，随机多路径优化3-opt策略通过随机抽取部分路径与当

前最优路径组合，增加算法的多样性。当算法陷入停滞时，采用信息素平均随机重置策略重置路径上的信息素

浓度,有助于算法跳出局部最优。实验结果显示,所提算法在处理多个不同规模的TSP实例时，与最优解的误差

保持在3%以内，证明了该算法在TSP中具备出色的收敛性和避免陷入局部最优解的能力。

关键词：蚁群算法；旅行商问题；莱维飞行；3-opt

中图分类号：TP18文献标志码：A文章编号：1001-3695(2024)05-020-1420-08

doi:10.19734/j.issn.1001-3695.2023.09.0450

AntcolonyoptimizationalgorithmbasedonLévyflighttransferrulefor

solvingtravelingsalesmanproblem

DingZengliang,ChenJuet,QiuXihe

(SchoolofElectronicElectricalEngineering,ShanghaiUniversityofEngineeringScience,Shanghai201620,China)

Abstract:ThispaperproposedanantcolonyoptimizationalgorithmbasedonLévyflighttransitionrulefortheTSP.Thealgo-

rithmcombinedthetransitionrulebasedonLevyflightandACS,andformedadynamicweighthybridtransitionrule,which

couldeffectivelyhelpthealgorithmescapefromlocaloptimaandenhancetheglobalsearchability.Inaddition,therandom

multi-pathoptimization3-optstrategyincreasedthediversityofthealgorithmbyrandomlyextractingsomepathsandcombining

themwiththecurrentoptimalpath.Whenthealgorithmstagnated,itusedthepheromoneaveragerandomresetstrategytore-

setthepheromoneconcentrationonthepath,whichhelpedthealgorithmescapefromlocaloptimal.Theexpe