具有变异特征的蚁群算法

《具有变异特征的蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机研究与发展991015计算机研究与发展JOURNALOFCOMPUTERRESEARCHANDDEVELOPMENT1999年　第36卷　第10期　Vol.36No.101999具有变异特征的蚁群算法吴庆洪　张纪会　徐心和　　摘　要　蚁群算法是一种新型的模拟进化算法，初步的研究已经表明该算法具有许多优良的性质，但该算法也存在一些缺点，如计算时间较长.为了克服这一缺点，文中给出一种新的蚁群算法——具有变异特征的蚁群算法.在基本蚁群算法中引入变异机制，充分利用了2-交换法简洁高效的特点，使得该方法具有较快的收敛速度，节省计算时间.计算机仿真结果表明该方法是行之有效的.　　关键词　蚁群系统

2、,模拟进化算法,变异机制　　中图法分类号　TP301.6ANANTCOLONYALGORITHMWITHMUTATIONFEATURESWUQing-Hong,ZHANGJi-Hui,andXUXin-He(Control&SimulationCenter,NortheastUniversity,Shenyang110006)AbstractAntcolonyalgorithmisanovelsimulatedevolutionaryalgorithmwhichshowsmanypromisingcharacters,butitalsohassomeshortcomingssuchasne

3、edinglongercomputingtimeetc..Inordertoovercomethisdefect,anewantcolonyalgorithm,anantcolonyalgorithmwithmutationfeatures,isproposedinthepaperhere.Becauseoftheintroductionofmutationmechanismwhichmakesfulluseofstrengthof2-exchangemethod,itcanquickentheconvergencerateanddecreasecomputingtime.Computin

4、gsimulationexamplesshowitsvalidity.Keywordsantcolonysystem,mutationmechanism,simulatedevolutionaryalgorithm1　引言　　本世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出了许多用以解决复杂优化问题的新方法，如遗传算法、进化规划、进化策略等［1］，并成功地应用于实际问题［2］.蚁群算法(antcolonyalgorithm，ACA)是最近几年才提出的一种新型的模拟进化算法，它是由意大利学者M.Dorigo，V.Maniezzo，A.Colorni等人首先提出来的［3～5

5、］，他们称之为蚁群系统(antcolonysystem),并用该方法求解TSP问题［5］、分配问题［3］、job-shop调度问题［5］,取得了一系列较好的实验结果.受其影响，蚁群系统模型逐渐引起了其它研究者的注意，并用该算法来解决一些实际问题［6］.虽然对此方法的研究刚刚起步，但是这些初步研究已显示出蚁群算法在求解复杂file:///F

6、/qikan_htm抽取_2000before/kjqk(200810)/jsjyjyfz/jsjy99/jsjy9910/991015.htm（第1／11页）2009-12-3123:44:21计算机研究与发展991015优化问题(特别是离散优化问题)

7、方面的一些优越性，证明它是一种很有发展前景的方法.本文对该方法作了一些研究.文章组织结构如下：首先简要介绍一下蚁群算法的由来及其基本原理；本文第3部分介绍蚁群算法的模型及其实现；然后用实例说明基本蚁群算法的优点与不足及其改进方法；最后给出实验结果验证我们给出的蚁群算法的有效性.2　基本蚁群算法的原理　　人工蚁群算法是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提出的一种基于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者M.Dorigo等人首先提出［3］.M.Dorigo等人首次提出该方法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题(TSP)之间的相似性，通过人工模拟蚂蚁

8、搜索食物的过程(即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP问题，为了区别于真实蚂蚁群体系统，我们称这种算法为“人工蚁群算法”.为了说明人工蚁群系统的原理，我们先简要介绍一下蚂蚁搜索食物的具体过程.　　像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁巢到食物源的最短路径，原因是什么呢？虽然单个蚂蚁的行为极其简单，但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂