浅谈改进的蚁群算法

摘要：蚁群算法也称蚂蚁算法，模拟生物蚂蚁觅食寻找最佳路径的行为，它由D.M等人提出。算法本质是在图中找出最佳路径。与神经网络等算法一样，是一种新的模拟进化方法。蚁群算法具有很多优良的特性和应用价值。该文对三种改进的蚁群算法进行了细致的阐述、分析与比较，得出它们的优势与不足之处。但是，基本的蚁群算法可能过早的陷入部分最优解且收敛耗时较长。

关键词：信息素；蚁群算法

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)31-0000-0c

The Analysis of Improvement of Ant Colony Algorithm

LI Yun1,2,ZHANG Yong-ping1

(1.College of Computer, China University of Mining and Technology, Xuzhou 221116, China; 2.Suqian Higher Normal School, Suqian 223800, China)

Abstract: Ant Colony Algorithm (ACA), named ant algorithm, simulates biological behavior of foraging ants to find the best path and it was proposed by D.M etc. In essence the algorithm is to find the best path. Like neural network algorithm, It is a new kind of simulated evolutionary method. It has many excellent properties and applications. This paper introduces that three kinds of basic ant colony algorithm is detailed elaborately, analysized and compared. We derive their advantages and disadvantages. Ant colony algorithm has many excellent properties and applications. However, the basic ant colony algorithm maybe premature in partial optimal solution and convergence time consuming.

Key words: information element; ant colony algorithm

早期仿生学家针对蚂蚁行为的研究发现，蚂蚁经过一条路时会释放化学物质，这些物质我们称之为信息素，蚂蚁们是依靠感知通过其它蚂蚁释放出来的信息素,沿这个路径找到食物的所在的地方，而且蚁群算法的灵感来源正是根据这种由其他蚂蚁所释放的化学物质信息来影响蚂蚁群体的路径选择的行为方式。

蚂蚁在觅食的时候一般会选择信息量大的路径前行，在行走的过程中自己也会释放信息素，这样就形成一个良性循环：路的长度越短，则选该路的蚂蚁也会越多，这样产生的信息素也越多，那么以后赶来的蚂蚁选择此路的机率相对就越高。蚂蚁算法就是模拟蚁群这一觅食行为的优化方法。

但是基本的蚁群算法在应用时常会发生停滞情况。如果遇到搜寻的空间非常小，得到的解就可能不理想；但是把搜寻空间加大，搜到的解往往会较理想，不过与此同时迭代次数会剧增。而且在搜寻时间上蚁群算法通常耗时相对较多。为此，提出了两种改进的蚂蚁系统。

1 带精英策略的蚂蚁系统（Ant system with elitist strategy）

对蚁群算法最早的改进的系统是带精英策略的蚂蚁系统(Ant System with elitist strategy，ASelite)， “精英策略”一词来源于遗传算法。总体来说，如果在遗传算法里引入一些算子（如重组因子、选择因子、突变因子），那么在某代中（既一轮循环里）的最优个体也许不会持续到下一代。精英策略引入的目的在于让某代中的最佳个体持续到下一代。类似的，对于ASelite算法，如果想让某循环找出的最佳的解能保持到下一次，我们给找到的最佳的解添加辅助的信息，按此方式求到的解就是整体最优的，帮助求出这个解的那些蚂蚁就称精英蚂蚁，其中，信息量的更新依下式计算：

τij(t+1)=ρτij (t)+τij +τij* （1.1）

其中

如果蚂蚁K在本次循环中经过边（i,j）（1.2）

否则

如果（i,j）这条边属于最优解 （1.3）

否则

其中，τ*代表通路(I,j)由精英蚂蚁释放的信息量增量，б表示精英蚂蚁的数目，L*为求得最优解中路径的长度。

我们用ASelite方法对O1iver30问题进行求解，考察求得部分最佳解的时候所需要的循环次数与精英蚂蚁的数量，得到的结果如图1所示（循环次数不超过2500）。从仿真结果我们可以得到如下结论:精英蚂蚁数是在某个范围内的，当我们选取的数量不超过该范围，那么随着数量的增加，算法寻求更优解得能力也随之加强，与此同时求解的时间也会相应缩短；如果总数（指精英蚂蚁）超过范围了，当蚂蚁数再增加时，算法寻求更优解得能力反而会减弱。

图1 局部最优解到达时的迭代次数与相应蚂蚁总量的关系（M.D,1996）

2 排序优化的蚁群系统（Ant Colony System of Sequencing Optimization ）

就像蚁群算法一样，ASelite算法也有不足之处，比如说在循环求解时，虽然总体上能提高解的质量，但是解间距相应地会缩小，会减少概率选择的差别，最终影响对更好的解得查找，因为系统无法集中在当前已找到的最好解周围。

特别是在所有的路的距离差距都很小的情况下，当各条通路距离很接近时，尤其是当大量蚂蚁顺着部分最佳通路行走时，对短的通路的加强效果就显得不明显了。

对于选择压力如何保持这个问题，遗传算法里引入排序的思想来解决，依照适应程度把蚁群分成若干类，个体的适应性比较高的话，它的名次就会相应的靠在较前面，那么它被选到的机率就会比较高一点。

我们可以把上述“排序”的思想移到蚁群系统里，称之为排序的蚁群系统(ant system basedon rank，ASrank)[18]。具体如下:在每个蚂蚁形成一条通路后，将它们按照通路距离排序(L1≤L2≤…≤Lm)，通过对蚂蚁名次μ的加权处理就可得到更新后的信息量，并且我们只研究ω只最优蚂蚁。排序中，对于前面б-1只蚂蚁，在经过的每一条边上都会遗留信息素，而且信息量与蚂蚁名词是正比关系。从而，当前求出的最佳通路的蚂蚁经过的路径也会得到一些信息素。对于这样排序和带精英混合策略系统中，更新信息素按照如下公式:

τij(t+1)=ρτij (t)+τij +τij*（2.4）

其中 ly05.tif表示б-1只蚂蚁在(i,j)两个城市间依排名来更新信息素：

若第μ只蚂蚁经过路径（i,j）（2.5）

否则

如果（i,j）这条边属于最优解（2.6）

否则

其中，μ表示最佳蚂蚁顺序号，τij μ表示由第μ只最佳蚂蚁在通路(i,j)上导致的信息量增量，Lμ是第μ只最佳蚂蚁的通路长度， τij*是精英蚂蚁在通路(i,j)上导致的信息量增量，б是精英蚂蚁个数，L*便是得到的最佳解路长。

3蚁群系统(Ant Colony system)

进一步，ACS（蚁群系统）在AS的基础上作了相应的改进，前者与后者显著不同的是:

(1) 仅增添信息素于整体最优解对应的边上

(2) 在挑选下一个城市时，算法ACS更多的利用了当前的较好解;

(3) 当蚂蚁每次从城市i行进到城市j时，边（i,j）上拥有信息素适当减小。

3.1 可行解的构造

算法ACS里，每个蚂蚁通过伪随机的方法决定接下来要到的城市，假设第K只蚂蚁在第i个城市，它选择到第1个城市的机率是q0， 1要满足的条件是让τij・ ηIUβ取值最大。按照这样的方法，蚂蚁会按机率q0把可能性最大的城市纳入解之中，再者，它会按机率(1-Q0)通过公式3.7来决定接下来要的地方j。算法ACS中，蚂蚁的状态按下式来改变:

如果q≤q0 （ 3.1）

否则

其中q0∈(0,1)为常数，q∈(0,l)是随机的数字，τiu(t)是时刻t两个城市i和u间信息素数量，ηiu是i与u的引导因子，β是引导因子的相对强弱值。为了选出下一个城市，要先生成随机数q。若q不超过常数q。，使得[τiu(t)]α[ηiu]β达到最大值的地方，就是i将选的地方，否则蚂蚁将要到达的地方将依照下式来选择：

如果j∈Jk(i) （3.2）

其它

上式里Jk(i)是第k只蚂蚁可能会到的城市总数。

3.2 ACS整体更新

算法ACS里，并不是对所有的蚂蚁都要进行整体的更新，只对最好的蚂蚁更新，并且按下面的方式来更新:

τ(i,j)(1-ρ)・τ(i,j)+ ρτ(i,j)（ 3.3）

如果（i,j）属于全局最优路径 （3.4）

否则

上式中，ρ为属于区间(0，1)内的一个常数，它和蚁群算法的基本模型AS算法中的挥发度系数作用相似。Lgh是该次循环里获得的最好的通路距离。

3.3 ACS部分更新

当全部蚂蚁完成一次移动后才进行这样更新。

τ(i,j)(1-ρ)・τ(i,j)+ ρτ(i,j) （3.5）

其中，ρ为属于区间(0，1)内的一个常数，它和蚁群算法的基本模型AS算法中的挥发度系数作用相似。τ(i,j)有以下三种不同取值方法：

(1) τ(i,j)=0;

(2) τ(i,j)= τ0，τ0通路上信息量原始值;

(3)ly11.tif ，其中的Jk(i)表示第k只蚂蚁到达城市j后接下来要到达的城市。

总的来说，法（1）的结果一般相对较差，若用法（2）和法（3）得到的结果几乎差不多，只不过法（2）的运算量要少很多，故我们通常选法（2）。

M. D把算法ACS和EP（进化规划） 、SA（模拟退火）和AG（遗传算法）等作比较，最后发现绝大多数情形下ACS具有较优的性能。对于TSP这种非对称性的问题求解时，ACS优势更加明显。表1为实验对比结果。

表1 ACS与其它几种算法在求解TSP问题的比较

从表1不难看出，算法ACS性能远远超过算法GA、AG和SA，与EP差不多。

4 总结

通过研究我们发现，蚂蚁算法寻求最佳解的能力是特别强的，原因在于它不仅是可以并行执行而且把正反馈巧妙地应用。各个蚂蚁通过信息素传递信息，它们紧密协作最终可以找到最优路径。

蚁群的特点包括分布式计算、正反馈及构建贪婪启发式的使用。分布式计算避免了早熟收敛的情况，正反馈可以让最优解被找到的更快，在求解的早期用贪婪启发式易于得到满意度高的解。一直来，三种改进的蚁群算法是已经证明的一个特别有效的算法，遗憾的是并不太完美，它的不足之处是：收敛不快而且经常发生停滞。

参考文献：

[1] 段海滨,王道波,朱家强,等.蚁群算法理论及应用研究的进展[J].控制与决策,2004,19(12):1321-1326,1340.

[2] Colony A, M.Dorigo , Maniezzo V，Distributed Optimization by Ant Colonies.Proc of 1st European Conf[J].Artificial Life.Pans,France:Elsevier,1991.

[3] Dorigo M.Optimization, learning and natural algorithms, Ph.D.Thesis,Department of Electronics, Politecnico diMilano, Italy, 1992

[4] Dorigo M, Maniezzo V,Colorni A. Ant system: optimization by a colony of cooperating agents .IEEE Transaction on systems,Man,and Cybernetics-Part B ,1996,26(1):29~41

[5] 张纪会,徐新和.一种新的进化算法-蚁群算法[J].系统工程理论与实践,1999,19(3):84-87.

[6] 段海滨,王道波,于秀芬等. 基于云模型理论的蚁群算法改进研究[J].哈尔滨工业大学学报,2005,37(1):115-119.

[7] 段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005.

收稿日期：2011-08-27

作者简介：李云（1978-），女，江苏宿迁人，讲师，硕士，主要研究方向为人工智能与信息处理。