具有变异特征的蚁群算法

《具有变异特征的蚁群算法》由会员分享，可在线阅读，更多相关《具有变异特征的蚁群算法（12页珍藏版）》请在装配图网上搜索。

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

2、计算时间.计算机仿真结果表明该方法是行之有效的关键词蚁群系统，模拟进化算法，变异机制中图法分类号TP301.6AN ANT COLO NY ALGORITHM WITH MUTATION FEATURESWU Qin g-Ho ng, ZHANG Ji-Hui, and XU Xi n-He(Co ntrol & Simulation Ce nter, Northeast Un iversity, She nya ng 110006)Abstract Ant colony algorithm is a no vel simulated evoluti onary algorithm which

3、 shows many promisi ng characters, but it also has some shortco mings such as n eedi ng Ion ger computing time etc. In order to overcome this defect, a new ant colony algorithm, an ant colony algorithm with mutation features, is proposed in the paper here. Because of the in troductio n of mutatio n

4、mecha nism which makes full use of stre ngth of 2-excha nge method, it can quicke n the conv erge nee rate and decrease computi ng time. Computi ng simulatio n examples show its validity.Key words ant colony system, mutatio n mecha ni sm, simulated evoluti onary algorithm1引言本世纪50年代中期创立了仿生学，人们从生物进化的机

5、理中受到启发，提出了许 多用以解决复杂优化问题的新方法，如遗传算法、进化规划、进化策略等，并成功地应用于实际问题 】2.蚁群算法(ant colony algorithm, ACA)是最近几年才提出的一种新型的模拟进化算法，它是由意大利学者M. Dorigo , V. Maniezzo, A. Colorni 等人先提出来的】35，他们称之为蚁群系统(ant colony system),并用该方法求解TSP问题】5】、分配问题】3】、job-shop调度问题5】，取得了一系列较好的实验结果.受其影响，蚁群系统模型逐渐引起了其它研究者的注意，并用该算法来解决一些实际问题 】6】.虽然对此方法的

6、研究刚刚起步，但是这些初步研究已显示出蚁群算法在求解复杂优化问题 （ 特别是离散优化问题 ） 方面的一些优越性，证明它是一种很有发展前景的方 法. 本文对该方法作了一些研究. 文章组织结构如下：首先简要介绍一下蚁群算法的由来及其基本原理；本文第3部分介绍蚁群算法的模型及其实现；然后用实例说明基本蚁群算法的优点与不足及其改进方法；最后给出实验结果验证我们给出的蚁群算法的有效 性.2基本蚁群算法的原理人工蚁群算法是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提 出的一种基于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者M. Dorigo 等人首先提出 3.M. Dorigo 等人首次

7、提出该方法时，充分利用了蚁群搜索食物的过程与著 名的旅行商问题 （TSP） 之间的相似性，通过人工模拟蚂蚁搜索食物的过程（ 即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题，为了区别于真实蚂蚁群体系统，我们称这种算法为“人工蚁群算法”. 为了说明人工蚁群系统的原理，我们先简要介绍一下蚂蚁搜索食物的具体过程.像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁巢到食物源的最短路径，原 因是什么呢？虽然单个蚂蚁的行为极其简单，但由这样的单个简单的个体所组成的蚁 群群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还能够适应 环境的变化，如 : 在蚁群运动路

8、线上突然出现障碍物时，蚂蚁能够很快地重新找到最优 路径，蚁群是如何完成这些复杂任务的呢?所有这些问题，很早就激起了生物学家和仿生学家的强烈兴趣，仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种 称之为外激素 （pheromone） 的物质进行信息传递，从而能相互协作，完成复杂的任务. 蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起着重要的作用.蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过 程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝 着该物质强度高的方向移动 . 因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信

9、息正反馈现象 : 某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大. 蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的. 对此过程， M. Dorigo 等人在文献 7中曾用图示方式形象地描述这一过程，这里不再赘述.蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解组成的群 体的进化过程来寻求最优解，该过程包含两个基本阶段: 适应阶段和协作阶段 . 在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息 交流，以期望产生性能更好的解.3 基本蚁群系统模型及其实现为了便于理解，我们以求解平面上n个城市的TSP问题（0 , 1,，n-1表示城市序

10、号）为例说明蚁群系统模型.n个城市的TSP问题就是寻找通过 n个城市各一次且最后回到出发点的最短路径 .我们之所以选择 TSP问题，一方面是因为蚁群算法最初用于求解TSP问题，便于比较，另一方面，TSP是典型的组合优化难题，常常用来验证某一算法的有效性 . 对于其它问题,可以对此模型稍作修改便可应用 6. 虽然它们从形式上看略有不 同,但基本原理是相同的,都是通过模拟蚁群行为到达优化之目的.为模拟实际蚂蚁的行为，首先引进如下记号：设m是蚁群中蚂蚁的数量，dj=1,2,n）表示城市i和城市j之间的距璃，表示t时刻位于城市i的蚂蚁的个s1241-01.gif (547 bytes)数，表示t时刻在

11、ij连线上残留的信息量.初始时刻，各条路径上信息量相等，设t ij(0)=C(C为常数).蚂蚁k(k=1,m)在运动过程中，根据各条路径上 的信息量决定转移方向， 岂仔-表示在t时刻蚂蚁k由位置i转移到位置j的概率，02.g1241-01.gif (1690 bytes)(1)工蚁群系统具有记忆功能， tabuk随着进化过程作动态调整 p表示信息消逝程度，经过 作调整，其中，allowed=0,1,n-1-tabuk表示蚂蚁k下一步允许选择的城市.与实际蚁群不同，人tabu1,2,m)用以记录蚂蚁k当前所走过的城市，集合.随着时间的推移，以前留下的信息逐渐消逝，用参数1-n个时刻，蚂蚁完成一次

12、循环，各路径上信息量要根据下式T ij(t+n)=pT ij(t)+ Aijp (0,1)g1242-01.gif (38, bytes)A刮表示第k只蚂蚁在本次循环中留在路径 上的信息量的增量.ij上的信息量1表示本次循环中路径ijfile:/F|/qikan_htm抽取 _2000before/kjqk(200810)/jsjyjyfz/jsjy99/jsjy9910/991015.htm第 4 11 页) 2009-12-31 23:44:21计算机研究与发展991015file:/F|/qikan_htm抽取 _2000before/kjqk(200810)/jsjyjyfz/jsjy

13、99/jsjy9910/991015.htm第 # 11 页) 2009-12-31 23:44:21计算机研究与发展991015g1242-02.gif (1513 bytes)file:/F|/qikan_htm抽取 _2000before/kjqk(200810)/jsjyjyfz/jsjy99/jsjy9910/991015.htm第 # 11 页) 2009-12-31 23:44:21计算机研究与发展991015其中，Q是常数，Lk表示第k只蚂蚁在本次循环中所走路径的长度.在初始时刻02=C(c on st), ES=0?i,j=0,1,n-1).a , B分别表示蚂蚁在运动过程中

14、所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用j表示由城市i转移到城市j期望程度，可根据某种启发式算法具体确定.根据具体算法的不同那2，凰242回(F的表达形式可以不同，要根据具体问题而定M Dorigo 曾给出3种不同模刑2.分别称之为ant-cyclesystem , ant-quantity system , ant-denSis它们m勺差别在于表达式(4) 的不同.在an t-qua ntity system模型中，g1242-03.gif (1643 bytes)(5)在 an t-de nsity system模型中，g1242-04.gif (1543 bytes)(6)

15、它们的区别在于后两种模型中利用的是局部信息，而前者利用的是整体信息，在 求解TSP问题时性能较好.因而我们采用它作为基本模型.参数Q, C,a,B,p，可以用实验方法确定其最优组合.停止条件可以用固定进化代数或者当进化趋势不明显时便停止计算.由算法复杂度分析理论可知，该算法复杂度为.n3O(其中，nc表示循环次数.以上是针对求解 TSP问题说明蚁群模型的，对该模型稍作修正，便可以应用于其它问题， 这一方面已有某些较好结果出现】6,8 14基本蚁群算法的优点与不足之处为了说明基本蚁群系统的优点与不足，我们给出用基本蚁群算法求解Oliver30 TSP的典型实验结果 (见图1、表1)，该实验结果来

16、源于文献71 ,取10次实验的平均值.t1242-01.gif (2359 bytes)图1最好解进化曲线图表1蚁群算法与其它算法的比较算法基本算法2- optL-Kant colony systemn 420n ear n eighbor587437421far in sert428421420n ear in sert厂510492410space filling curve 464431421sweep486426420ran dom1212663421所谓基本算法是指最初提出的算法形式从这一系列实验结果我们可以发现，蚁群算法具有很强的发现较好解的能力，不 容易陷入局部最优，这是因为该算

17、法不仅利用了正反馈原理，在一定程度上可以加快 进化过程，而且是一种本质并行的算法，个体之间不断进行信息交流和传递，有利于 发现较好解.单个个体容易收敛于局部最优，多个个体通过合作，很快收敛于解空间的 某一子集，有利于对解空间的进一步探索，从而不容易陷入局部最优，有利于发现较 好解.但是，这种算法也存在一些缺陷，如：需要较长的搜索时间，对于这一问题，文献:9也曾经指出过，但没有提出改善方法.虽然计算机计算速度的提高和蚁群算法的本质并行性在一定程度上可以缓解这一问题，但是对于大规模优化问题，这还是一个 很大的障碍.蚁群中各个体的运动是随机的，虽然通过信息交换能够向着最优路径进化，但是 当群体规模较

18、大时，很难在较短的时间内从大量杂乱无章的路径中找出一条较好的路 径.这是因为在进化的初级阶段，各个路径上信息量相差不明显，通过信息正反馈，使 得较好路径上的信息量逐渐增大，经过较长一段时间，才能使得较好路径上的信息量 明显高于其它路径上的信息量，随着这一过程的进行，差别越来越明显，从而最终收 敛于较好的路径 .这一过程一般需要较长的时间.为了克服计算时间较长的缺陷，受到遗 传算法中的变异算子的作用的启发，我们提出一种新的蚁群进化算法一一具有变异特 征的蚁群算法我们采用逆转变异方式，设某个体所走路径为0川2“( n-1：)，(io1,i n-1 0,1,2- n-1 ),如果满足g1243-01

19、.gif (1579 bytes)其中0,1；.,n-1, 符号表示整除符号.进行操作:inversisn(Sution),函数inversion()的功能是把个体SOS+1n和s2这一段颠倒过来.女口:in versio n(2,5,0123456)=0125436其中，变异的次数是随机的 .这一过程涉及到的运算比蚁群算法中的循环过程要简 单得多，因此只需较短的时间便可完成相同次数的运算.另一方面，经过这种变异算子作用后，这一代解的性能会有明显改善，从而也能改善整个群体的性能，减少计算时 间.就此方法，我们作了大量实验例子，实验结果表明这种方法是很有效的我们的算法可以用伪代码表示为begi

20、n初始化过程：n cycle : =0;bestcycle : =0;T ij : =C；t ij=0 ；n j由某种启发式算法确定；tabu二？;while (not term in ati on con diti on)ncycle :二ncycle+1;for (in dex=0; in dex n ;i ndex+)/ ?index表示已走城市的个数7for (k=0; km; k+)以概率丁當前吨选择城市j;j 0, 1.；yns)HtabUk把所选择的城市序号加到/(动态调整集合 tabu*/计算 llndex), ij(index+n)确定本次循环中找到的最佳路径输出最佳路径及最

21、佳结果end5实验结果一方面是因NP-hard 问.这里的实我们选用 Oliver30 TSP 作为实验例子进行实验 我们之所以选用该例子， 为M. Dorigo曾经选用该例子，从而便于比较另一方面，TSP问题是典型的题，常常用来验证某一算法的有效性.我们在PC机上用C语言编程实现该算法验结果是10次实验的平均结果 （见图2、图3、图4）.t1244-01.gif (2624 bytes)图2最好解进化曲线图t1244-02.gif (2708 bytes)图3最差解进化曲线图t1244-03.gif (4274 bytes)图4所找到的最优路径表2本文算法在不同参数下的实验结果aP最短路径的

22、长度达到收敛所需要的进化代数220.542456220.9424.850120.5428.262520.9423.749520.5423.844为便于比较，我们给出由基本蚁群算法计算得到的结果（见图5、图6、表3）.ti244-04.gif (2946 bytes)图5基本算法的最好解进化曲线图t1244-05.gif (3085 bytes)图6基本算法的最差解进化曲线图表3基本蚁群算法在不同参数下的实验结果aP最短路径长度达到收敛所需要的进化代数220.5424.8350220.9427344120.5423.7342520.9430.5338| 520.5445347文献7需要经过342

23、代才能找到较好解（423.74）,而本文仅需要大约50代便可以找到同样的解.对于48个城市的TSP问题，用本文算法也得到了较好的结果（见表4）.通过对以上的实验结果比较可以看出，由于变异算子的引入，经过较少的进化代数就可以找 到相同的较好解，大大节省计算时间，对于求解大规模优化问题是十分有利的.表448个城市TSP实验结果算法aP最短路径长度达到收敛所需要的进化代数基本算法220.574.3390基本算法120.975.43571基本算法520.573.7347本文算法120.571.443本文算法520.972.747本文算法220.571.140J6结论本文提出的具有变异特征的蚁群算法，可

24、以有效地克服基本蚁群算法中计算时间 较长的缺陷，有利于实际运用.蚁群算法的研究刚刚开始，远未像 GA SA等算法那样形成系统的分析方法和坚实的数学基础，许多问题有待进一步研究. 怎样从理论上对该算法进行更深刻地研究，以及如何更有效地用蚁群算法解决实际问题将是我们进一步 研究的内容.作者单位：东北大学控制仿真中心 沈阳110006作者简介：吴庆洪，男， 业自动化等 .1967年7月生，博士研究生，主要研究方向为计算机控制、工本课题得到国家“八六三”CIMS主题资助（项目编号 863-511-9508-004）.张纪会，男，1969年10月生，博士研究生，主要研究方向为离散事件动态系统、智能生产调

25、度、智能计算等 .徐心和，男，1940年12月生，教授，博士生导师，主要研究方向为离散事件动态系统、计算机控制与仿真、混杂系统、生产调度等.参考文献1 Goldberg D E. Gen etic Algorithm in Search, Optimizati on and Machi ne Lear ning.New York: Addison Wesley, 19892 Davis L. The Handbook of Genetic Algorithms. New York: Van Nostrand Reingold, 19913 Colorni A, Dorigo M, Maniez

26、zo V. Distributed optimization by ant colonies. In:Proc 1st European Conf Artificial Life. Pa ns, Fran ce: Elsevier, 1991. 1341424 Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an ant algorithm. In: Proc PPSN92, London, 1992. 50945205 Colorni A, Dorigo M, Maniezzo V, Trubia

27、n N. Ant system for job-shop scheduling. Belgian Journal of Operations Research and Statistic Computing Science, 1994, 34(1): 439 536 Costa D, Hertz A, Dubuis O. Imbedding of a sequential algorithm within an evolutionary algorithm for coloring problem in graphs. Journal of Heuristics, 1995, 1: 1054

28、1287 Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans on SMC, 1996, 26(1): 248 418 Bilchev G, Parmee I C. Searching heavily constrained design spaces. In: Proc 22ndInt Conf CAD-95, Yelta, Ukraine, 19959 Dorigo M, Maniezzo V, Colorni A. Ant syste

29、m: An autocatalytic optimizing process. Tech Rep: 91-016, 1991原稿收到日期： 1997-11-19 ；file:/F|/qikan_htm抽取 _2000before/kjqk(200810)/jsjyjyfz/jsjy99/jsjy9910/991015.htm第 11 11 页) 2009-12-31 23:44:21计算机研究与发展991015file:/F|/qikan_htm抽取 _2000before/kjqk(200810)/jsjyjyfz/jsjy99/jsjy9910/991015.htm第 12 11 页) 2009-12-31 23:44:21计算机研究与发展991015修改稿收到日期：1999-04-08.file:/F|/qikan_htm抽取 _2000before/kjqk(200810)/jsjyjyfz/jsjy99/jsjy9910/991015.htm第 # 11 页) 2009-12-31 23:44:21