计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999年　第36卷　第10期　Vol.36　No.10　1999



具有变异特征的蚁群算法
吴庆洪　张纪会　徐心和
　　摘　要　蚁群算法是一种新型的模拟进化算法，初步的研究已经表明该算法具有许多优良的性质，但该算法也存在一些缺点，如计算时间较长.为了克服这一缺点，文中给出一种新的蚁群算法——具有变异特征的蚁群算法.在基本蚁群算法中引入变异机制，充分利用了2-交换法简洁高效的特点，使得该方法具有较快的收敛速度，节省计算时间.计算机仿真结果表明该方法是行之有效的.
　　关键词　蚁群系统, 模拟进化算法, 变异机制
　　中图法分类号　TP301.6
AN ANT COLONY ALGORITHM WITH MUTATION FEATURES
WU Qing-Hong, ZHANG Ji-Hui, and XU Xin-He
(Control & Simulation Center, Northeast University, Shenyang 110006)
　　Abstract　Ant colony algorithm is a novel simulated evolutionary algorithm which shows many promising characters, but it also has some shortcomings such as needing longer 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 introduction of mutation mechanism which makes full use of strength of 2-exchange method, it can quicken the convergence rate and decrease computing time. Computing simulation examples show its validity.
　　Key words　ant colony system, mutation mechanism, simulated evolutionary algorithm
1　引言
　　本世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出了许多用以解决复杂优化问题的新方法，如遗传算法、进化规划、进化策略等［1］，并成功地应用于实际问题［2］.蚁群算法(ant colony algorithm，ACA)是最近几年才提出的一种新型的模拟进化算法，它是由意大利学者M. Dorigo，V. Maniezzo，A. Colorni等人首先提出来的［3～5］，他们称之为蚁群系统(ant colony system),并用该方法求解TSP问题［5］、分配问题［3］、job-shop调度问题［5］,取得了一系列较好的实验结果.受其影响，蚁群系统模型逐渐引起了其它研究者的注意，并用该算法来解决一些实际问题［6］.虽然对此方法的研究刚刚起步，但是这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性，证明它是一种很有发展前景的方法.本文对该方法作了一些研究.文章组织结构如下：首先简要介绍一下蚁群算法的由来及其基本原理；本文第3部分介绍蚁群算法的模型及其实现；然后用实例说明基本蚁群算法的优点与不足及其改进方法；最后给出实验结果验证我们给出的蚁群算法的有效性.
2　基本蚁群算法的原理
　　人工蚁群算法是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提出的一种基于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者M. Dorigo等人首先提出［3］.M. Dorigo等人首次提出该方法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题(TSP)之间的相似性，通过人工模拟蚂蚁搜索食物的过程(即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP问题，为了区别于真实蚂蚁群体系统，我们称这种算法为“人工蚁群算法”.为了说明人工蚁群系统的原理，我们先简要介绍一下蚂蚁搜索食物的具体过程.
　　像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁巢到食物源的最短路径，原因是什么呢？虽然单个蚂蚁的行为极其简单，但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还能够适应环境的变化，如:在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径，蚁群是如何完成这些复杂任务的呢?所有这些问题，很早就激起了生物学家和仿生学家的强烈兴趣，仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递，从而能相互协作，完成复杂的任务.蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起着重要的作用.
　　蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动.因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大. 蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的.对此过程，M. Dorigo等人在文献［7］中曾用图示方式形象地描述这一过程，这里不再赘述.
　　蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段:适应阶段和协作阶段.在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解.
3　基本蚁群系统模型及其实现
　　为了便于理解，我们以求解平面上n个城市的TSP问题(0，1，…，n-1表示城市序号)为例说明蚁群系统模型.n个城市的TSP问题就是寻找通过n个城市各一次且最后回到出发点的最短路径.我们之所以选择TSP问题，一方面是因为蚁群算法最初用于求解TSP问题，便于比较，另一方面，TSP是典型的组合优化难题，常常用来验证某一算法的有效性.对于其它问题，可以对此模型稍作修改便可应用［6］.虽然它们从形式上看略有不同，但基本原理是相同的，都是通过模拟蚁群行为到达优化之目的.
　　为模拟实际蚂蚁的行为，首先引进如下记号：设m是蚁群中蚂蚁的数量，dij(i,j=1,2,…,n)表示城市i和城市j之间的距离，bi(t)表示t时刻位于城市i的蚂蚁的个数，表示t时刻在ij连线上残留的信息量.初始时刻，各条路径上信息量相等，设τij(0)=C(C为常数).蚂蚁k(k=1,2,...,m)在运动过程中,根据各条路径上的信息量决定转移方向，(t)表示在t时刻蚂蚁k由位置i转移到位置j的概率，

(1)
其中，allowedk={0,1,...,n-1}-tabuk表示蚂蚁k下一步允许选择的城市.与实际蚁群不同，人工蚁群系统具有记忆功能，tabuk(k=1,2,...,m)用以记录蚂蚁k当前所走过的城市,集合tabuk随着进化过程作动态调整.随着时间的推移，以前留下的信息逐渐消逝，用参数1-ρ表示信息消逝程度，经过n个时刻，蚂蚁完成一次循环，各路径上信息量要根据下式作调整，
τij(t+n)=ρ.τij(t)+Δτij　ρ∈(0,1)
(2)

(3)
Δ表示第k只蚂蚁在本次循环中留在路径ij上的信息量，Δ表示本次循环中路径ij上的信息量的增量.

(4)
其中，Q是常数，Lk表示第k只蚂蚁在本次循环中所走路径的长度.在初始时刻，(0)=C(const),Δ=0(i,j=0,1,...,n-1).α,β分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用.ηij表示由城市i转移到城市j期望程度，可根据某种启发式算法具体确定.根据具体算法的不同，(t)，Δ(t)及(t)的表达形式可以不同，要根据具体问题而定.M. Dorigo曾给出3种不同模型，分别称之为ant-cycle system，ant-quantity system，ant-density system［7］.它们的差别在于表达式(4)的不同.在ant-quantity system模型中，

(5)
在ant-density system模型中，

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


图1　最好解进化曲线图
表1　蚁群算法与其它算法的比较

算法基本算法①2-opt L-K
ant colony system420——
near neighbor587437421
far insert428421420
near insert510492410
space filling curve464431421
sweep486426420
random1212663421

①所谓基本算法是指最初提出的算法形式
　　从这一系列实验结果我们可以发现，蚁群算法具有很强的发现较好解的能力，不容易陷入局部最优，这是因为该算法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质并行的算法，个体之间不断进行信息交流和传递，有利于发现较好解.单个个体容易收敛于局部最优，多个个体通过合作，很快收敛于解空间的某一子集，有利于对解空间的进一步探索，从而不容易陷入局部最优，有利于发现较好解.但是，这种算法也存在一些缺陷，如:需要较长的搜索时间，对于这一问题，文献［9］也曾经指出过，但没有提出改善方法.虽然计算机计算速度的提高和蚁群算法的本质并行性在一定程度上可以缓解这一问题，但是对于大规模优化问题，这还是一个很大的障碍.
　　蚁群中各个体的运动是随机的，虽然通过信息交换能够向着最优路径进化，但是当群体规模较大时，很难在较短的时间内从大量杂乱无章的路径中找出一条较好的路径.这是因为在进化的初级阶段，各个路径上信息量相差不明显，通过信息正反馈，使得较好路径上的信息量逐渐增大，经过较长一段时间，才能使得较好路径上的信息量明显高于其它路径上的信息量，随着这一过程的进行，差别越来越明显，从而最终收敛于较好的路径.这一过程一般需要较长的时间.为了克服计算时间较长的缺陷，受到遗传算法中的变异算子的作用的启发，我们提出一种新的蚁群进化算法——具有变异特征的蚁群算法.我们采用逆转变异方式，设某个体所走路径为:i0i1i2...i(n-1),(i0,i1,...,in-1∈｛0,1,2,...,n-1｝),如果满足

其中，s1,s2∈{0,1,...,n-1}, 符号%表示整除符号.进行操作:inversion(s1，s2,solutioni), 函数inversion( )的功能是把个体solutioni的s1+1和s2这一段颠倒过来.如：
inversion(2,5,0123456)=0125436
　　其中，变异的次数是随机的.这一过程涉及到的运算比蚁群算法中的循环过程要简单得多，因此只需较短的时间便可完成相同次数的运算.另一方面，经过这种变异算子作用后，这一代解的性能会有明显改善，从而也能改善整个群体的性能，减少计算时间.就此方法，我们作了大量实验例子，实验结果表明这种方法是很有效的.　　
　　我们的算法可以用伪代码表示为
　　begin
　　初始化过程:
　　ncycle∶=0;
　　bestcycle∶=0;
　　τij∶=C；
　　Δτij=0；
　　ηij由某种启发式算法确定;
　　tabuk=；
　　while (not termination condition)
　　{ncycle∶=ncycle+1;
　　for (index=0; index<n;index++)
　　／index表示已走城市的个数*/
　　{for (k=0; k<m; k++)
　　{以概率选择城市j;
　　j∈{0, 1, ..., n-1}-tabuk
　　}
　　把所选择的城市序号加到tabuk中
　　/*(动态调整集合tabuk);*/
　　}
　　计算Δ(index),τij(index+n)
　　确定本次循环中找到的最佳路径
　　}
　　输出最佳路径及最佳结果
　　end
5　实验结果
　　我们选用Oliver30 TSP作为实验例子进行实验.我们之所以选用该例子，一方面是因为M. Dorigo曾经选用该例子，从而便于比较.另一方面，TSP问题是典型的NP-hard问题，常常用来验证某一算法的有效性.我们在PC机上用C语言编程实现该算法.这里的实验结果是10次实验的平均结果(见图2、图3、图4).


图2　最好解进化曲线图


图3　最差解进化曲线图


图4　所找到的最优路径
表2　本文算法在不同参数下的实验结果

αβρ最短路径 
的长度　达到收敛　　　　
所需要的进化代数
220.542456
220.9424.850
120.5428.262
520.9423.749
520.5423.844

　　为便于比较，我们给出由基本蚁群算法计算得到的结果(见图5、图6、表3).


图5　基本算法的最好解进化曲线图


图6　基本算法的最差解进化曲线图
表3　基本蚁群算法在不同参数下的实验结果

αβρ最短路 
径长度达到收敛　　　　
所需要的进化代数
220.5424.8350
220.9427344
120.5423.7342
520.9430.5338
520.5445347

　　文献［7］需要经过342代才能找到较好解(423.74),而本文仅需要大约50代便可以找到同样的解.对于48个城市的TSP问题，用本文算法也得到了较好的结果(见表4).通过对以上的实验结果比较可以看出，由于变异算子的引入，经过较少的进化代数就可以找到相同的较好解，大大节省计算时间，对于求解大规模优化问题是十分有利的. 
表4　48个城市TSP实验结果

算法αβρ最短路 
径长度达到收敛　　　　
所需要的进化代数
基本算法220.574.3390
基本算法120.975.4357
基本算法520.573.7347
本文算法120.571.443
本文算法520.972.747
本文算法220.571.140

6　结论
　　本文提出的具有变异特征的蚁群算法，可以有效地克服基本蚁群算法中计算时间较长的缺陷，有利于实际运用.蚁群算法的研究刚刚开始，远未像GA，SA等算法那样形成系统的分析方法和坚实的数学基础，许多问题有待进一步研究.怎样从理论上对该算法进行更深刻地研究，以及如何更有效地用蚁群算法解决实际问题将是我们进一步研究的内容. 
本课题得到国家“八六三”CIMS主题资助(项目编号863-511-9508-004).
作者简介：吴庆洪，男，1967年7月生，博士研究生，主要研究方向为计算机控制、工业自动化等.
　　　　　张纪会，男，1969年10月生,博士研究生,主要研究方向为离散事件动态系统、智能生产调度、智能计算等. 
　　　　　徐心和，男，1940年12月生,教授,博士生导师,主要研究方向为离散事件动态系统、计算机控制与仿真、混杂系统、生产调度等.
作者单位：东北大学控制仿真中心　沈阳　110006
参考文献
　1　　Goldberg D E. Genetic Algorithm in Search, Optimization and Machine Learning. New York: Addison Wesley, 1989
　2　　Davis L. The Handbook of Genetic Algorithms. New York: Van Nostrand Reingold, 1991
　3　　Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. In: Proc 1st European Conf Artificial Life. Pans, France: Elsevier, 1991. 134～142
　4　　Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an ant algorithm. In: Proc PPSN'92, London, 1992. 509～520
　5　　Colorni A, Dorigo M, Maniezzo V, Trubian N. Ant system for job-shop scheduling. Belgian Journal of Operations Research and Statistic Computing Science, 1994, 34(1): 39～53
　6　　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: 105～128
　7　　Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans on SMC, 1996, 26(1): 28～41
　8　　Bilchev G, Parmee I C. Searching heavily constrained design spaces. In: Proc 22nd Int Conf CAD-95, Yelta, Ukraine, 1995
　9　　Dorigo M, Maniezzo V, Colorni A. Ant system: An autocatalytic optimizing process. Tech Rep: 91-016, 1991 
原稿收到日期：1997-11-19；
修改稿收到日期：1999-04-08.
