蚁群优化算法的收敛性分析与研究

赵世安

摘 要： 蚁群算法本身存在收敛速度慢、容易陷入局部最优解的缺陷，针对该缺陷提出一些改进的蚁群优化算法。主要讨论蚁群优化算法的收敛性理论及应用，得出蚁群系统和最大最小蚂蚁系统的性能好于蚂蚁系统，而且最大最小蚂蚁系统的性能最好，蚁群系统和最大最小蚂蚁系统是值收敛的，一种特殊的[ACOgs，ρ（θ）]算法是解收敛的。

关键词： 蚁群优化算法； 收敛性； 蚁群系统； 解收敛

中图分类号： TN911.1?34； TM417 文献标识码： A 文章编号： 1004?373X（2017）19?0173?04

Analysis and research on convergence of ant colony optimization algorithm

ZHAO Shian

（School of Mathematics & Statics， Baise University， Baise 533000， China）

Abstract： The ant colony algorithm has the defect of slow convergence speed and is easy to fall into the local optimal solution， so some improved ant colony optimization algorithms are proposed to elimanite the defect. The convergence theory and application of the ant colony optimization （ACO） algorithm are discussed mainly in this paper. It is obtained that the performance of the ant colony systen and min?max ant system is higher than that of the ant system， in which the min?max ant system has the highest performance， the ant colony system and min?max ant system are convergent， and a special [ACOgs，ρ（θ）] algorithm is solution convergent.

Keywords： ant colony optimization algorithm； convergence； ant colony system； solution convergence

0 引 言

随着科学技术和现代化生产的快速发展，优化问题在各行各业中显得越来越重要，然而传统的优化方法对函数性质的要求比较高，如要求函数连续、可微等，而实际问题中，很多函数都不具有上述性质，因此在应用上有很大的局限性，而且实际问题往往很复杂，所以需要寻求新的优化方法[1?2]。随着计算机技术和人工智能技术的发展，人们提出了蚁群算法、遗传算法、粒子群算法等群智能算法，这些算法一个很重要的特点就是群集智能特性[3]。

与大多数传统确定性全局算法不同，群集算法依靠的是概率搜索方法，即不是每一步迭代都能够让算法得到更好的解[4?5]。虽然概率搜索方法需要依靠比较多的评价函数，以及需要大量的迭代步数，但是它的优点也是显著的：

（1） 群体中相互合作的个体是分布式的；

（2） 没有中心的控制，这样的系统更加具有鲁棒性；

（3） 不需要通过不同个体之间的通信，而通过非直接通信进行合作。这样的系统具有非常好的扩展性；

（4） 系统中每个个体的能力十分简单，执行的时间也非常短。实践证明，这些智能算法对解决实际问题具有很好的效果，本文主要讨论蚁群优化算法的收敛性理论及应用。

1 收敛性概述

蚂蚁系统（Ant System，AS）是第一个ACO算法，被称为基本的ACO算法，目前对于ACO算法的理论研究主要集中在算法收敛性上，在这方面文献[6]开创性地提出一种基于图的蚂蚁系统元启发式这一ACO的通用模型，该模型能够在一定条件下以任意接近1的概率收敛到最优解。但是这种模型对于条件的要求很苛刻，很难应用到实际当中去。

蚁群优化算法的收敛性包括值收敛和解收敛，值收敛评估的是任意一个最优解至少出现一次的可能性，即至少有一只蚂蚁能够找到最优解的概率；解收敛评估的是算法到达某个可以持续生产相同最优解的状态的可能性，即任意一只蚂蚁都可以找到最优解的概率。

文献[6]首先对蚁群优化算法的收敛性进行研究，提出基于图的蚂蚁系统（GBAS）。这是一种更为特殊的蚁群优化算法，适用于各种静态组合优化问题，用到的主要工具是马尔可夫过程理论，证明了算法的迭代过程是一个马尔可夫过程，并得到了如下结果：

（1） 对于固定的信息素蒸发系数，只要迭代次数足够多，某只蚂蚁找到最优解的概率会任意接近1；

（2） 对于一定量的蚂蚁和足够小的信息素蒸发系数，只要迭代次数足够多，某只蚂蚁找到最优解的概率任意接近1。

但是由于GBAS算法对于条件的要求太高，如要求问题只能有一个最优解等，而且是一种从来没有实现过的算法。上面提到的收敛指的是值收敛，Gutjahr随后又提出了GBAS算法的变种算法，GBAS/tdlb（信息素的下界与时间相关）和GBAS/tdev（信息素的蒸发速率与时间相关），并证明了它们是解收敛的。

之后，文献[7]给出两种特殊蚁群优化算法（即[ACObs，τmin]和[ACObs，τmin（θ）]）收敛性的证明。本文主要证明最大最小蚂蚁系统算法（MMAS）和蚁群系统（ACS）算法是值收敛的，并且证明一种特殊的蚁群优化算法[ACOgs，ρ（θ）]是解收敛的。

2 收敛性证明

2.1 MMAS和ACS收敛性的证明

首先证明最大最小蚂蚁系统算法是值收敛的。

命题1：在最大最小蚂蚁系统算法中，任意的一个部分解[xh]选择任意一个可行节点的概率[pmin>0。]

证明：在最大最小蚂蚁系统算法中，信息素[τij]的上下界分别为[τmax]和[τmin，]并且对于启发式因子[ηij]有，[0<ηij<∞，]由于[ηij]的个数有限，因此[ηij]有上下界，分别记为[ηmax]和[ηmin]。

假设蚂蚁已经生成了部分解[xh，]则对于下一个可选节点，最坏的情形就是[xh]的最后一个节点和该节点之间的边上，[ταijηβij=ταminτβmin，][xh]的最后一个节点和其余可选节点组成的边上[ταijηβij=ταmaxτβmax，]并且其余节点都是可选节点。因此，蚂蚁选择任意一个可行节点的概率[pmin]有如下关系：

[pmin≥pmin=ταminτβminNc-1ταmaxτβmax+ταminτβmin>0] （1）

式中：[Nc]表示节点的总数。因此，对于任意的一个部分解[xh]的选择，任意一个可行节点的概率[pmin>0。]

定理1：在最大最小蚂蚁系统算法中，令[p*（θ）]表示算法在前[θ]次迭代中至少有一次得到最优解的概率。那么，对于任意的[ε>0]和一个充分大的[θ，]以下不等式成立：[p*（θ）≥1-ε，]即[limθ→∞p*（θ）=1]。

证明：记蚂蚁生成任意一个可行解（包括最优解[s*]）的概率为[p，]由命题1可知，[p≥pnmin，]其中[n]表示可行解的长度。由于每次迭代生成最优解是相互独立的，因此，迭代[θ]后得到最优解的概率[p*（θ）]有一个下限为：[p*（θ）=1-（1-p）θ，]因此[p*（θ）≤p*（θ）≤1。]显然[limθ→∞p*（θ）=1]，所以[limθ→∞p*（θ）=1，]命题成立，最大最小蚂蚁系统算法是值收敛的。

现在证明蚁群系统算法也是值收敛的。蚁群系统算法与最大最小蚂蚁系统有很大的区别，主要表现在蚁群系统算法中引入了伪随机比例规则，并且蚁群系统算法中，局部信息素更新规则和全局信息素更新规则交替进行[8]。尽管不像最大最小蚂蚁系统算法那样对信息素的值设置了界限，但是可以证明，蚁群系统算法中信息素的值也有上下界。

命题2：在蚁群系统算法中，信息素[τij]的一个下界为[τ0]，一个上界为[qf（s*）]，其中[s*]表示全局最优解，[qf（?）]是一个取正值的递减函数，[sbestθ+1]表示第[θ+1]次迭代后得到的迄今为止最好的解。

证明：首先，在蚁群系统算法中，信息素的局部更新规则为：

[τij（θ+1）=（1+ε）?τij（θ）+ε?τ0] （2）

信息素的全局更新规则为：

[τij（θ+1）=（1-ρ）?τij（θ）+ρ?qf（sbestθ+1）] （3）

显然式（2）和式（3）具有相同的形式：

[a（θ+1）=1-ξ?a（θ）+ξ?b] （4）

由式（4）可得：

[a（θ）=1-ξθ?a（0）+b?1-1-ξθ] （5）

显然，当[a（0）>b]时，[a（θ）]是单调递减的，当[a（0）≤b]时，[a（θ）]是单调递增的，并且[limθ→∞a（θ）=b]。用数学归纳法可以证明只要取[τ0

当[θ=1]时：

[τij（1）=（1-ρ）?τ0+ρ?qf（sbest1）<（1-ρ）?qf（s*）+ρ?qf（s*）=qf（s*）] （6）

所以当[θ=1]時，假设成立。假设[θ=n]时，假设成立。

当[θ=n+1]时：

[τij（n+1）=（1-ρ）?τij（n）+ρ?qf（sbest1）<（1-ρ）?qf（s*）+ρ?qf（s*）=qf（s*）] （7）

当[θ=n+1]时，假设也成立。所以[τij]的一个上界为[qf（s*）]。

命题3：在蚁群系统算法中，任意的一个部分解[xh]选择任意一个可行节点的概率[pmin>0。]

证明：在蚁群系统算法中，由于引入了伪随机比例规则，因此如果在边[（i，j）]上，[ταij，][τβij]不是最大的，那么在最坏的情形下，蚂蚁选择这条边的概率为：

[pmin≥pmin=（1-q0）?τα0τβminNc-1?qαf（s*）?ηβmax+τα0τβmin>0] （8）

式中：[q0]为伪随机比例规则中的随机数。所以，任意的一个部分解[xh]选择任意一个可行节点的概率[pmin>0。]

定理2：在蚂蚁系统算法中，令[p*（θ）]表示算法在前[θ]次迭代中至少有一次得到最优解的概率。那么，对于任意的[ε>0]和一个充分大的[θ，]以下不等式成立：[p*（θ）≥1-ε，]即[limθ→∞p*（θ）=1]。

证明：记蚂蚁第[θ]次迭代，生成任意一条可行路径（包括最优路径）的概率为[pθ，]记[p*min=min（pmin，q0），]可知[pθ≥qm0?pn-mmin>p*minn>0]，其中，[m]表示生成一条可行路径过程中，伪随机比例选择的次数，且[0≤m≤n，][n]是解序列的长度。则：

[1-（1-p*min）θ≤1-i=1θ（1-pi）≤p*（θ）≤1] （9）

显然[limθ→∞1-（1-p*min）θ=1，]所以，[limθ→∞p*（θ）=1，]蚁群系统算法是值收敛的。

通过以上证明可知，最大最小蚂蚁系统算法和蚁群系统算法都是值收敛的，但不是解收敛的。

2.2 [ACOgs，ρ（θ）]算法收敛性的证明

最大最小蚂蚁系统算法和蚁群系统算法都属于[ACObest，τmin]类型的算法，即信息素有一个下界，而且挥发系数不随着迭代次数的改变而改变，只在当前最优解的路径上增加信息素。上面已经证明了它们都是值收敛的。[ACObest，τmin（θ）]算法是对[ACObest，τmin]算法的一种改进，即信息素的最小值可以根据迭代次数进行调整，并且允许信息素的最小值能够随着时间的推移减少到零，但是这个过程必须要足够缓慢以保证能够找到最优解。[ACOgs，ρ（θ）]算法同[ACObest，τmin]算法的思想有些类似，但它是通过改变信息素的挥发速度使信息素的值缓慢减小到0。在[ACOgs，ρ（θ）]算法中，信息素的增加同样仅仅发生在当前最优解的路径上，并且当迭代次数[θ≤θ0]时，信息素的挥发系数是常数[ρ，]当迭代次数[θ>θ0]时，信息素的挥发系数为[ρθ，]且满足：

[ρθ≤1-ln（θ）ln（θ+1）， θ=1∞ρθ=∞]

首先证明[ACOgs，ρ（θ）]是值收敛的。

定理3：[ACOgs，ρ（θ）]算法是值收敛的。

证明：考虑最坏的情形，信息素只挥发不增加。则经过[θ（θ>θ0）]次迭代之后，边[（i，j）]上的信息素浓度[τij（θ）]有如下表达式：

[τij（θ）=i=1θ（1-ρi）?τij（0）≥（1-ρ）θ0?i=θ0+1θln（i）ln（i+1）?τij（0）] （10）

记[a=（1-ρ）θ0τij（0）ln（θ0+1）]，则：

[τij（θ）≥aln（θ+1）] （11）

由于在[ACOgs，ρ（θ）]算法中信息素的全局更新规则为：

[τij（θ+1）=（1-ρθ）?τij（θ）+ρθ?qf（sbestθ+1）] （12）

很容易用数学归纳法证明[τij（θ）≤qf（s*）]，因此：

[aln（θ+1）≤τij（θ）≤qf（s*）] （13）

下面证明不能找到最优解的概率上限为0。记事件[Fθ]为第[θ]次迭代找到了最优解，则[θ=1∞?Fθ]就表示算法从来没有找到最优解，这意味着从来没有找到过任何一个最优解[s*。]因此p（[s*] is never traversed）是[p（θ=1∞?Fθ）]的一个上界。由式（13）可知蚂蚁选择任意一可选择节点的概率为：

[pmin（θ）≥pmin（θ）=ταmin（θ）τβminNc-1?ταmax（θ）?ηβmax+ταmin（θ）τβmin≥ταmin（θ）?ηβminNc?ταmax（θ）?ηβmax]

其中，[τmin≥aln（θ+1），][τmax≤qf（s*），]记[p′min（θ）=][ταmin（θ）τβminNc?ταmax（θ）?ηβmax，]则[pmin（θ）≥p′min（θ）]。因此螞蚁构建一个可行解的概率[p（θ）≥p′min（θ）n，]因此：

[ps* is never traversed≤θ=1∞1-p′min（θ） =θ=1∞1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn] （14）

只要证明无穷乘积[θ=1∞1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=0]即可，为此只要证明级数[θ=1∞ln1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=-∞]即可。

[θ=1∞ln1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=θ=1∞ln1-aln（θ+1）α?ηβminNc?ταmax（θ）?ηβmaxn] （15）

记[c=aαηβminNc?ταmax（θ）?ηβmax]，则：

[θ=1∞ln1-aln（θ+1）α?ηβminNc?ταmax（θ）?ηβmaxn=θ=1∞ln1-cln（θ+1）αn] （16）

因为对于任意的[x<1，][ln（1-x）≤-x]，所以：

[θ=1∞ln1-cln（θ+1）αn≤-cnθ=1∞1ln（θ+1）nα] （17）

而正项级数[θ=1∞1ln（θ+1）nα]发散，所以：

[ln1-cln（θ+1）αn==∞] （18）

[θ=1∞1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=0] （19）

所以，[pθ=1∞?Fθ=0，]即能够找到最优解的概率极限为1，因此，该算法是值收敛的。

下面证明算法是解收敛的，即任何一只蚂蚁找到最优解的概率极限都为1。

命题4：假设某只蚂蚁在第[θ*]次迭代中第一次找到最优解[s*]，则对任意的[τij（θ），（i，j）?s*，][limθ→∞τij（θ）=0]。

证明：假设某只蚂蚁在第[θ*]次迭代后找到了最优解[s*]，则对于任意的边[（i，j）?s*，]它上面的信息素只挥发不增加，所以再经过[k]次迭代后，这些边上的信息素[τij（θ*+k）=i=θ*+1θ*+k（1-ρi）?τij（θ*）]，因此只需要证明当[k→∞]时，[τij（θ*+k）→∞]。考虑级数[i=θ*+1∞ln（1-ρi）+lnτij（θ*）]，由于对任意的[x<1，][ln（1-x）≤-x，]所以[i=θ*+1∞ln（1-ρi）+lnτij（θ*）≤-i=θ*+1∞ρi+lnτij（θ*），]而已知[θ=1∞ρθ=∞，]所以[i=θ*+1∞ln（1-ρi）+lnτij（θ*）=-∞，][limk→∞τij（θ*+k）=0，]即[limθ→∞τij（θ）=0]。

命题5：假设某只蚂蚁在第[θ*]次迭代中第一次找到最优解[s*，]则对于任意的[τij（θ），（i，j）?s*，θ≥θ*，][τij（θ）]的极限存在。

证明：对于[（i，j）?s*，]信息素的更新方式为：

[τij（θ+1）=（1-ρθ+1）?τij（θ）+ρθ+1?qf（s*）] （20）

[τij（θ+1）-τij（θ）=ρθ+1?qf（s*）-τij（θ）>0] （21）

前面已经证明了[τij（θ）≤qf（s*）]，因此由式（21）可知[τij（θ）]是递增的，而且有上界，因此[τij（θ）]的极限存在，记为[τij]。

定理4：设[θ*]为得到最优解的迭代次数，令[p（s*，θ，k）]为任意一只蚂蚁k在第[θ]次迭代中得到最优解的概率，其中[θ>θ*]。那么有：[limθ→∞p（s*，θ，k）=1]。

证明：假设蚂蚁[k]位于节点[i]上，并且边[（i，j）]是[s*]中的边。那么蚂蚁[k]选择[（i，j）]的概率为：[p*ij（θ）=τ*ij（θ）α?ηijβτ*ij（θ）α?ηijβ+（i，h）?s*τ*ih（θ）α?ηihβ] （22）

[p*ij=limθ→∞p*ij（θ）=limθ→∞τ*ijθα?ηijβlimθ→∞τ*ijθα?ηijβ+limθ→∞（i，h）?s*τ*ih（θ）α?ηihβ=ταij?ηβijταij?ηβij+0=1]

所以，任意给定一只蚂蚁，它找出最优解的概率极限都为1，因此该算法是解收敛的。由上面的证明过程可以看出，能够保证信息素的值足够缓慢地减少到0是证明的关键。随着计算机计算能力的提高，在用蚁群优化算法解决实际问题时，为了避免解陷入局部最优，可以根据上面的思路去设计一些具有解收敛性质的算法。

3 结 论

目前ACO算法有很多的应用，当ACO算法的性能不断提高，同时从理论上对其工作原理的理解不断加深时，依然有许多领域处于研究的初始阶段，有待于人们去努力探索。本文主要证明最大最小蚂蚁系统算法（MMAS）和蚁群系统（ACS）算法是值收敛的，并且证明一种特殊的蚁群优化算法[ACOgs，ρ（θ）]是解收敛的。

随着互联网技术和社会经济的快速发展，越来越多的问题都可以归结为复杂网络的组合优化问题，传统优化算法的局限性越来越明显，蚁群优化算法等智能算法在求解这些组合优化问题的优势将会越来越明显，这必将会带来可观的经济效益。目前蚁群优化算法的应用领域主要是静态的、离散的优化问题，将蚁群优化算法应用到动态问题、随机问题和多目标问题上去将会是未来的发展趋势，同时蚁群优化算法理论性的工作也会是一个重点。

参考文献

[1] 夏小云，周育人.蚁群优化算法的理论研究进展[J].智能系统学报，2016，11（1）：27?36.

[2] 刘景巍，张迪，唐向辉，等.结合局部优化的蚁群优化算法的研究与实现[J].价值工程，2014（29）：227?229.

[3] COLORNI A， DORIGO M， MAFFIOLI F， et al. Heuristics from nature for hard combinatorial optimization problems [J]. International transactions in operational research， 1996， 3（1）： 1?21.

[4] 王芳.基于蚁群算法的TSP问题研究与实现[J].科学中国人，2014（4）：1?2.

[5] 王胜训，李艳颖.一种求解TSP的自适应蚁群优化算法[J].西安工程大学学报，2013（6）：840?844.

[6] GUTJAHR W J. A graph?based ant system and its convergence [J]. Future generation computer systems， 2000， 16（8）： 873?888.

[7] ST?TZLE T， DORIGO M. A short convergence proof for a class of ant colony optimization algorithms [J]. IEEE transactions on evolutionary computation， 2002， 6（4）： 358?365.

[8] 郑恩興，刘冉冉.蚁群算法收敛性验证系统的研究与实现[J].电子科技，2013，26（1）：138?141.

[9] 吴华锋，陈信强，毛奇凰，等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报，2013（4）：165?170.

[10] 申铉京，刘阳阳，黄永平，等.求解TSP问题的快速蚁群算法[J].吉林大学学报（工学版），2013，43（1）：147?151.