基于粒子群优化的蚁群算法在TSP中的应用

　　第26卷　第8期

文章编号:1006-9348(2009)08-0089-03

计　算　机　仿　真

2009年8月　　

基于粒子群优化的蚁群算法在TSP中的应用

柴宝杰,刘大为

1

2

(1.牡丹江师范学院,黑龙江牡丹江157012;2.中国石油信息技术服务中心,北京100007)

摘要:结合粒子群算法的问题,提出用混合蚁群算法来求解著名的旅行商问题。问题的核心是应用粒子群算法对蚁群算法的控制参数:启发式因子、信息素挥发系数、随机性选择阈值进行优化,以及运用蚁群系统算法寻找最短路径。新算法对于蚂蚁算法中的参数调整大大减低,减少了大量盲目的实验,力求在开发最优解和探究搜索空间上找到平衡点。对旅行商问题的仿真实验表明,新算法的优化质量和效率都优于传统蚁群算法和遗传算法,接近理论最佳值。新算法也可推广用于其他NP问题的求解。

关键词:蚁群算法;蚁群系统;粒子群算法;旅行商问题中图分类号:TP30116　　文献标识码:A

ApplicationofanAntColonyAParticleSwarm

,LIUDa-wei

1

2

πsCollege,MudanjiangHeilongjiang157012,China;.mInformationTechnologyServiceCenter,Beijing100007,China)

ABSTRACT:Combinedwiththeideaoftheparticleswarmoptimization(PSO)algorithm,theantcolonyoptimiza2

tion(ACO)algorithmispresentedtosolvethewellknowntravelingsalesmanproblem(TSP).Thecoreofthisalgo2rithmisusingPSOtooptimizethecontrolparametersofACOwhichconsistofheuristicfactor,pheromoneevaporationcoefficientandthethresholdofstochasticselection,andapplyingantcolonysystemtorouting.Thenewalgorithmef2fectivelyovercomestheinfluenceofcontrolparametersofACOanddecreasesthenumbersofuselessexperiments,ai2mingtofindthebalancebetweenexploitingtheoptimalsolutionandenlargingthesearchspace.Simulationresultsshowthatthenewalgorithmhasbetteroptimizationqualityandefficiencythanthetraditionalantcolonyalgorithmandthegeneticalgorithm.ThenewalgorithmcanalsobegeneralizedtosolveotherNPproblems.

KEYWORDS:Antcolonyalgorithm;Antcolonysystem;Particleswarmalgorithm;Travelingsalesmanproblem

1　引言

近年来,启发式智能优化方法愈来愈引起人们的关注,

它们是解决NP问题的有效工具。

蚁群算法[1,2]是模拟真实蚁群觅食过程寻求最短路径的原理,由意大利学者M.Dorigo等人首先提出的一种仿生智能优化算法。参加寻径的蚂蚁通过留在链路上的信息素交互来选择新的路由,从而达到寻优的目的。其主要特点是:一个增强型学习系统,具有分布式的计算特性,具有很强的鲁棒性,易于与其它优化算法融合。但是蚁群算法在解决大型优化问题时,存在搜索空间和时间性能上的矛盾,易出现

收稿日期:2009-03-30　修回日期:2009-04-07

过早收敛于非全局最优解以及计算时间过长的弱点;而且决

定蚁群算法性能的3个控制参数启发式因子β、信息素挥发系数ρ、随机性选择阈值q0的取值缺乏理论支持,影响了算法的性能。针对以上问题,许多学者提出若干改进算法,如Dorigo和Gambardella提出的蚁群系统(AntColonySystem,

[3]

ACS),Stutzle和Hoos提出了最大-最小蚂蚁系统(Max-[4]

MinAntSystem,MMAS)等。

粒子群优化算法(ParticleSwarmOptimization,PSO)源于对鸟群捕食行为的研究,由Kennedy和Eberhart[5]共同提出的一类模拟群体智能的优化算法。与其它进化算法类似,PSO采用“群体”与“进化”的概念,主要依据个体的适应值大小进行操作。它的特点是:概念简单、容易实现,并且依赖经验参数较少。目前已成功地用于求解多种优化问题[6],尤其是函数优化。

—89—