蚁群优化算法的理论研究进展

夏小云，周育人

(1.江西理工大学 信息工程学院，江西 赣州 341000；2.华南理工大学 计算机与工程学院，广东 广州 510006；3.中山大学 数据科学与计算机学院，广东 广州 510006)

蚁群优化算法的理论研究进展

夏小云1,2，周育人3

(1.江西理工大学 信息工程学院，江西 赣州 341000；2.华南理工大学 计算机与工程学院，广东 广州 510006；3.中山大学 数据科学与计算机学院，广东 广州 510006)

摘要：蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。回顾了蚁群优化算法的收敛性分析、时间复杂度分析与近似性能分析等理论研究进展,分析了其理论研究的对象从简单的拟布尔函数转为组合优化问题以及实际应用问题。从蚁群算法理论分析方法和研究问题类型2个方面对蚁群算法的理论研究进行综述。介绍了适应值划分、漂移分析等最基本的数学分析工具,对时间复杂性及近似性能等重要问题进行了探讨。总结比较了蚁群算法求解各类问题的性能，指出这些研究能够更加深入了解蚁群算法的运行机制。最后,探讨了目前蚁群算法理论研究中亟待解决的问题,指出引入新的分析工具以及研究更为复杂的算法模型等是值得进一步研究的方向和内容。

关键词：蚁群优化算法；理论研究；组合优化；收敛性；时间复杂度；近似性能

中文引用格式：夏小云，周育人.蚁群优化算法的理论研究进展[J]. 智能系统学报， 2016, 11(1): 27-36.

英文引用格式：XIA Xiaoyun，ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI Transactions on Intelligent Systems, 2016, 11(1): 27-36.

随机启发式搜索(randomized search heuristics, RSHs)算法是近年来发展较快的研究领域,在许多应用中取得了丰富的成果。这类启发式算法主要包括随机局部搜索(randomized local search, RLS)、禁忌搜索(tabu search)、模拟退火(simulated annealing, SA) 、演化算法(evolutionary algorithms, EAs) 以及粒子群优化算法(particle swarm optimization, PSO)等。这些算法经常用来作为一些难解优化问题的近似求解方法。由于这类智能算法的智能性、普适性以及全局搜索能力,使得其为求解NP难解优化问题开辟了一条新的途径。蚁群优化算法(ant colony optimization, ACO)是这类算法的杰出代表之一。

蚁群算法是受蚂蚁群体觅食行为的启发,由意大利学者Dorigo等[1]提出的一种基于种群的模拟进化算法。蚂蚁觅食过程中借助于信息素(pheromone)这种化学物质进行信息的交流和传递,能够根据所走路径长度自主选择下一个将要行走的地方,并表现出正反馈现象。这种正反馈机制能帮助蚂蚁很快找到最优觅食路径。蚁群算法以信息素更新和概率转移为基本操作,并以此指导搜索方向。蚁群算法作为一种新型的智能仿生类进化算法,已在许多领域获得了广泛的应用。例如在TSP(traveling salesman problem)问题、二次规划问题、 函数优化、网络路由优化、机器人路径规划、数据挖掘、作业流程规划、图形着色等领域获得了广泛的应用,并取得了较好的效果,具体可以参考张军等的译著[2]。此外,国内学者段海滨等[4]对蚁群算法的应用领域的研究成果做了较全面的综述。

自从蚁群算法提出后,许多研究者在蚁群算法的设计及应用方面取得了丰富的研究成果。大量的实验也表明其针对一些优化问题的求解非常有效。然而,从理论上来看,蚁群算法缺乏比较完备的理论基础。目前更迫切地希望为该算法建立坚实的理论基础[10,13],以帮助更好地理解算法的运行机制,了解算法对于求解什么类型的问题有效。为算法的设计,参数选取以及算法的运用指明改进的方向。当前蚁群算法理论研究远远落后于算法的数值实验和真实应用,主要原因在于随机启发式算法理论分析的艰难性[15]。蚁群算法具有随机性、群体性、普适性等特性,这些特征使得算法表现出复杂的动态行为,由此引出的复杂多变的随机过程增加了算法理论分析的难度,经典算法设计与分析的方法和工具也难以直接应用于这类新型随机仿生算法。

在2006年之前,研究人员主要关注于ACO收敛性分析[19-21,26]以及ACO算法与其他优化算法的关系[25],从理论上探索算法为什么有效。 Gutjahr[19]提出了一个基于图的蚂蚁系统(graph-based ant system, GBAS), Gutjahr首次证明了该模型蚁群算法在一定条件下以概率1-ε收敛到最优解,其中ε为任意小的常数且ε>0。Stützle and Dorigo[20]等给出了普通蚁群算法(ant colony system，ACS)和MMAS(max-min ant system)的收敛性证明。 Gutjahr[21]进一步提出使用常微分方程逼近ACO随机过程,并基于此来对ACO算法的收敛速度进行粗糙的理论预测。国内学者黄翰、郝志峰等[22]根据蚁群算法的特性,基于吸收态Markov 过程的数学模型,提出了蚁群算法的收敛速度分析理论,并给出了ACO-难和ACO-易两类问题的界定方法。蚁群算法理论研究的另一个方向是将蚁群算法和其他学习算法进行比较, 如Birattari[23]、Meuleau[24]等分别建立了ACO与最优控制加强学习算法、随机梯度下降算法的联系。

近年来,以遗传算法为基础的演化算法时间复杂性研究取得了一些重要进展。以Droste[11]、Wegener[12]等为代表的德国学派分析了群体规模为1的简单爬山演化算法(1+1)EA求解一些拟布尔函数(OneMax, LeadingOnes, Trap Function)的平均计算时间,取得了一系列研究成果。He Jun和Yao Xin使用吸收马尔可夫链[16]、漂移分析[17]等工具建立演化算法时间复杂性分析模型和方法以及分析群体在演化算法时间复杂性分析中的作用[18]等。这些研究极大地激发和推动了蚁群算法的理论研究工作。

蚁群算法最初用于旅行商问题的求解,进而推广到各种组合优化问题(甚至连续函数优化问题)。Dorigo和Blum[3]总结了截至2005年蚁群算法理论研究及应用中取得的阶段性研究成果,并特别指出蚁群算法时间复杂性将是今后一个重要的、有意义的研究方向,将其列为蚁群算法理论研究的公开性问题。

时间复杂度研究是指算法找到优化问题最优解或近似最优解的计算时间,是衡量算法性能最基本、最重要的指标。W.J.Gutjahr[10]总结了截止2007年的蚁群算法时间复杂性研究成果和方法,并指出了一些发展方向。目前,蚁群算法时间复杂性研究正处于启动阶段,研究内容、深度都非常有限,很多基本问题尚未涉及。当前仅仅研究了蚂蚁规模为1的1-ANT的情形,而与真实的蚁群算法相关的问题,如多蚂蚁蚁群系统求解真实的组合优化问题等,都有待深入研究。可以预计,这些研究将会有重要意义,同时又将是富有挑战性的、艰难的工作。目前ACO算法理论研究主要是关于一些人工拟布尔函数以及一些经典的组合优化问题的时间复杂性分析。最具代表性的如国内学者Zhou Yuren[45]研究了ACO求解经典TSP问题的时间复杂度，这也是ACO算法在NP难解问题理论分析上的首项工作。

一般情况下,对于典型的难问题—NP-完全(难)(non-deterministic polynomial-complete hard)优化问题,人们找不到多项式时间的确定性算法。由于NP难解组合优化问题本身结构的复杂性,确定性算法(穷举法、分支界定、动态规划等)无法保证在多项式内获得精确解,转而寻求一些近似算法[6]。蚁群优化作为随机启发式方法,不能期待其在多项式时间内找到NP-完全(难)优化问题所有实例的精确解。实际上,蚁群算法在很多优化问题上扮演着近似算法的角色,一般用于获得满意解或者近似解。因此蚁群优化算法的近似性能分析就变得尤为重要。希望在平均多项式时间内获得近似最优或者可接受的解,对于理解蚁群算法在NP难优化问题上的工作原理以及寻求其能获得的近似性能非常关键,并将进一步推进蚁群算法的理论研究及应用进展。对于丰富和发展近似算法和组合优化理论,切实有效地解决一些实际问题具有重要现实意义。

1蚁群优化算法：模型、描述、变体

1.1优化问题及算法描述

蚁群算法是一种随机启发式搜索方法,它具有较强的鲁棒性，优良的分布式计算机制并易于与其他方法相结合等优点。目前人们对蚁群算法的研究已经由当初单一的旅行商问题(TSP)领域渗透到了多个其他应用领域[2],由解决一维、静态优化问题发展到解决多维、动态优化问题,由离散求解空间逐渐拓展到连续求解空间,使得该群智能算法在科学研究及实际问题求解中表现出了巨大的潜力和优势。

优化问题可以分为两类：连续的优化问题和离散的优化问题。连续的优化问题是指其具有连续的变量、经常需要计算导数、使用牛顿方法或者线性规划技术等。本文关注的是离散的优化问题。离散优化问题也称为组合优化问题,是指在有限的或者可数无限的潜在解集中搜索满足给定约束条件的最优解。然而,组合优化问题通常包含大量的局部极值点,而且许多组合优化问题为NP完全(难)问题。

一个组合优化问题P通常可描述为一个三元组(S,f,Ω),其中S为给定的由所有状态构成的搜索空间,f:S→R+为目标函数,一般为最大化或者最小化；Ω为可行解满足的约束条件集合。一个可行解s*∈S,如果对于最小化问题有∀s∈S,f(s*)≤f(s),对于最大化问题有∀s∈S,f(s*)≥f(s),则称s*为一个全局最优解。定义最优解集合为S*⊆S,算法的目标是从优化问题的可行解集中找到最优解s*∈S*。

蚁群算法的启发来自于一个蚂蚁群体对食物源的搜索，是一种杰出而具有代表性的群智能算法，对于其算法描述可以参考相关文献[1-5]。ACO算法有一些不同的变体,为了分析的方便，在当前理论分析方面,还是主要考虑一只蚂蚁的情况。下面给出蚁群优化算法理论研究中用到的一个简单的ACO算法(1+1)蚂蚁算法((1+1)Ant Algorithm,(1+1)AA),其类似于演化算法理论分析中的(1+1)EA。不失一般性,考虑最小化问题。(1+1)AA算法描述如下

Algorithm 1: (1+1)AA

Begin

初始化：参数设置,信息素值,选择一个初始解s，While(不满足终止条件)

使用构造过程构建一个新的解s′；

选择：如果f(s′)

End while

End

(1+1)AA算法使用简单的爬山选择策略,如果当前蚂蚁解的函数值大于新的蚂蚁解的函数值,则当前蚂蚁解被新蚂蚁解替代。以下两节分别介绍理论分析中蚁群算法解的构建以及信息素更新机制。

1.2解的构建

对于一个给定的优化问题,其解通过蚂蚁在一个具有信息素值的构造图(construction graph)的边上随机游走获得。另外,蚁群算法也使用启发式信息来指导随机游走的方向。蚂蚁从构造图的任意一个初始状态出发,随机游走到下一个邻域结点。这个移动是基于概率规则,依赖于信息素和启发式信息。

令G=(V,E)为一给定问题的构造图。τ(u,v)为边e=(u,v)∈E上的信息素值,η(u,v)为启发式信息。假设蚂蚁当前所在位置为顶点u,其允许访问的后续结点为Nu。蚂蚁在下一步访问结点v∈Nu的概率由以下公式给出：

式中：参数α表示蚂蚁在运动过程中所积累的信息素在指导蚂蚁搜索路径的相对重要性；参数β表示路径能见度的相对重要性,即表示启发式信息η(u,v)的重要性。

1.3信息素更新机制

根据信息素更新方式的不同,也就产生具有不同信息素更新机制的蚁群算法[8]。为了防止算法的早熟, Stützle 和 Hoos[9]提出了最大最小蚂蚁系统。在信息素的更新过程中,将其限制在一个最大最小信息素范围内[τmin,τmax]。根据边e=(u,v)∈E是否包含在至今最好的解x中,其信息素更新规则如下：

(1)

称使用上述信息素更新规则的(1+1)AA算法为(1+1)MMAA。 类似的(1+1)MMAA在文献[28,34]中分别叫做MMAS*和MMASbs。

2理论分析方法及数学工具

对于一个确定的优化问题,蚁群算法找到一个最优解的迭代次数用随机变量t表示。在蚁群算法的理论分析中通常需要估计最好情况、平均情况、最坏情况下，以什么样的概率Pr(t≤T)在什么样的期望运行时间E(t)内，找到什么样的解(近似解)。本节介绍一些蚁群算法的理论分析方法和基本的数学工具。不失一般性,考虑最小化问题。

2.1适应值划分

对于给定的优化问题，感兴趣的是算法找到最优解的平均迭代次数。这里介绍适应值划分技术，该技术在演化算法的理论分析中得到了成功运用。其原理是种群中最好的个体适应值一直都确保不会变差。因此通过估计最好的个体适应值变好的期望时间界来获得优化时间。这种方法称为基于适应度划分的方法(fitness-based partitions)或者适应度等级方法[14]。

定义1(适应值划分)给定一个有限的搜索空间S,不失一般性,假设函数f:S→R最小化, 考虑函数f的所有可能的不同的函数值A0,A1,…,Am,对于∀a∈Ai和∀b∈Aj,如果f(a)

对于ACO，算法每次接受优于当前最好的解，算法每次运行都朝着最优解的方向前进,如图1所示。下面给出一个简单ACO算法的期望运行时间估计的定理,其由Gutjahr和Sebastiani[34]提出。

图1　适应值划分Fig.1　Fitness values partition

2.2期望倍增距离减少

图2　期望倍增距离减少Fig.2　Expected multiplicative distance decrease

给定一个具有操作序列Op={op0,op1,op2,…,opt,…},每一操作发生的概率相同,假设为P(opt)=pm≥α(t=1,2,….)。给定任意初始解s,算法通过执行操作opt∈Op，一步一步逐渐到达最优解sopt。不失一般性,考虑最小化问题。定义优化问题的适应值函数f(st)(t=1,2,...),d(st)=f(st)-f(sopt)为第t代时的解st与目标最优解sopt相差的适应值距离。根据随机启发式算法的特点,给定不同的初始解,其求解问题的迭代次数也不一样,因此考虑的是期望迭代次数。算法找到可接受的操作,使得st+1优于st。假定算法通过执行给定的操作使得减少的期望距离至少为

(2)

由(2)得

(3)

当前解离目标最优解距离减少由两部分产生:可接受的操作和不接受的操作,而不接受的操作距离减少的贡献为0。

因此,如果d(st)>0,有

(4)

令Yt=d(st),有

2.3尾概率不等式

偏差不等式广泛应用于随机算法的分析中。在许多启发式搜索算法的例子中,对于分析启发式的典型行为是非常有用的。其通常用于估计随机变量偏离期望值的概率。

基于BIM技术的碰撞检查在工程中的应用…………………………… 王邵臻，何博，徐丽豪，蒙秋莎（3-261）

2.3.1Markov不等式

2.3.2Chebyshev不等式

切比雪夫不等式 (Chebyshev’s inequality)适用于任何的(可正可负)随机变量,有两种形式：

1)令X为一随机变量,其中E(X)=μ,Var(X)=σ2。对于k>0,

2.3.3Chernoff界

3一些理论研究结果及问题讨论

3.1参数ρ、α、β对算法性能影响

到目前为止,蚁群算法中挥发因子、信息素值控制参数、启发式信息(能见度)控制参数的设置,对于界定蚁群算法的难问题和易问题并没有从理论上真正得以解释说明。从蚁群算法求解一些实际问题的实验效果来看,信息素挥发因子是一个比较关键的参数。挥发因子越大,表现出的正反馈作用越强,以往走过的路径被再次选择的可能性就越大,搜索随机性变弱；相反,挥发因子越小,算法的随机性就越大,其全局搜索能力也就变强。信息素挥发因子设置对于算法性能影响至关重要。

蚁群算法中信息素控制参数α反映蚂蚁在行走过程中所积累的信息素对指导蚂蚁搜索方向的相对重要性,能见度控制参数β反映启发式信息对指导蚂蚁搜索方向的相对重要性。Zhou[45]通过构造TSP实例,研究了参数α和β对算法计算时间的影响,指出对于完全图实例,参数设置α=1,β=0到α=1,β=1,其期望运行时间上界也由O(n6)变为O(n5)。Kötzing等[46]通过构建一个TSP实例分析了启发式信息对于蚁群算法的性能影响,指出对于该实例取α=1,如果β=1,算法需要指数级运行时间找到最优解；如果β=n,则算法以趋近于1的概率在一次迭代就能找到最优解。

蚁群算法参数较多,设置也较复杂。目前理论分析主要通过一些构造实例来分析不同参数设置对于算法性能的影响。针对一般性的问题,参数如何设置对于蚁群算法来说是有效的,还有待于进一步深入探究。

3.2从1-ANT到n-ANT

Neumann等人[36]研究了λ-MMASIB算法求解拟布尔函数的性能。他们指出,当λ=2,也即构造2个蚂蚁解时,该算法在挥发因子足够小的情况下,能够在多项式时间内求解OneMax函数。

Attiratanasunthron和Fakcharoenphol[41]研究了ACO算法求解有向无环图单源最短路径问题的多项式时间界。特别地,对于顶点数为n，边数为m的有向无环图,具有n只蚂蚁的n-ANT算法能够在期望时间Ο(n2mlogn/ρ)内求解单源最短路径问题。

蚂蚁的数量决定了每次迭代构造的解的个数。在不同参数情况下,真实的多蚂蚁蚁群系统如何影响算法性能,如何设置蚂蚁个数,以及n-ANT算法求解组合优化问题的性能,能够在什么样的时间内获得什么样的解,是值得进一步研究的问题。

3.3从拟布尔函数到NP难问题

3.3.1拟布尔函数

以下7个函数为分析演化和蚁群算法时间复杂性的典型人工拟布尔函数：

从2006年开始,蚁群算法关于时间复杂性分析的理论研究也相继出现, Neumann[27,29]等通过模拟(1+1)EA建立了一个简单的ACO算法1-ANT分析模型,给出了1-ANT求解简单拟布尔函数OneMax平均时间复杂度为O(nlogn),并且指出挥发因子对时间复杂度起着关键性的影响。与此同时,Gutjahr[30]采用近似的常微分方程组估计算法时间复杂度,研究了GBAS和AS两个ACO算法的同一分析。 Doerr等[31]以1-ANT求解关于OneMax为例,分析了随着挥发系数的变化,1-ANT算法时间复杂度从指数时间到多项式时间的相位转移。Doerr等[32-33]研究了1-ANT算法信息素更新机制对时间复杂度的影响,指出如果挥发因子设置过小,算法很容易陷入停滞状态。对于拟布尔函数LeadingOnes和BinVal,找到最优解的期望时间也是指数级的。相反,如果参数设置合理,期望时间也从指数级降低到多项式时间。

学者们也研究了最大最小蚂蚁系统(max-min ant system ,MMAS)[9]算法的性能。该算法是蚁群优化的一个变体，其使用Best-So-Far更新机制。对于一些优化问题,最大最小蚂蚁系统能够有效地避免停滞,并能获得一个更有效的运行时间界。Gutjahr 和 Sebastiani[34]分析了MMAS在求解Needle-in-a-Haystack和LeadingOnes两个拟布尔函数的时间复杂度,并基于演化算法中适应值划分技术的基础上提出了一种ACO的时间复杂度理论分析框架,将作为一般分析的一个非常有用的工具。 2007年,Neumann等[35]将ACO算法扩展到单峰函数和高原函数的期望运行时分析上,并使用非齐次过程估计了信息素边界的首达时间,进一步研究了1-ANT算法关于LeadingOnes、Needle等其他拟布尔函数的时间复杂度；Kötzing等[37]也进一步研究了两种MMAS算法求解线性拟布尔函数的时间复杂度,并给出了求解所有线性函数的一般时间上界Ο(n3logn/ρ)。Neumann、Sudholt和Witt[38]研究了ACO与局部搜索混合算法的影响,他指出对于一些人工构造的函数,ACO算法结合局部搜索能够以较高的概率将指数时间转为多项式时间。对于另外一些函数,情况则相反。

以上所有研究分析使用的方法和工具为组合优化问题的更深层次的分析奠定了坚实的基础。

3.3.2P问题

一些确定性的算法能够在多项式时间内求解P类的组合优化问题,实验表明ACO算法进行求解也显示出了其优越性。 ACO算法在一些简单函数上的分析所使用的方法和工具,也进一步推广到实际的组合优化问题上的分析中。目前ACO算法针对多项式可求解问题的理论分析也获得了一些结果。我们并不期望蚁群优化算法在这些优化问题上能够优于那些最好的算法,而关键是对于其理论分析能够更深入地了解蚁群算法工作机制,更好指导算法的设计及应用。

最小生成树(minimum spanning trees)问题是数据结构与算法设计中一个经典的图论问题。两个著名的确定性算法Kruskal和Prim分别有最坏情况下的时间复杂度Ο((m+n)logn)和Ο(nlogn+m) (n为顶点数,m为边数)。Neumann 和 Witt[39]分析了ACO算法求解最小生成树问题的时间复杂度,其蚂蚁解的构建是基于两种不同的构造图,Broder-based和Kruskal-based,并证明了最大最小蚂蚁系统求解最小生成树问题的期望时间上界为Ο(mnlogn)。

最短路径问题的目标是搜索图中两结点之间的最短路径。Dijkstra算法是求解该问题的典型路由算法，用于计算一个节点到其他所有节点的最短路径。文献[41-43]研究了最短路径问题,并分别分析了ACO算法求解无环、有环、带有噪声情况下最短路径问题的计算时间。Attiratanasunthron和Fakcharoenphol[41]研究了ACO算法求解有向无环图单目标最短路径问题(singledestinationshortestpath,SDSP)的多项式时间界。对于顶点数为n边数为m的有向无环图，具有n只蚂蚁的n-ANT算法能够在期望时间Ο(n2mlogn/ρ)内求解单源最短路径问题。

在此基础上,Horoba和Sudholt[42]将结果扩充到最大最小蚂蚁系统(MMAS),得到MMASSDSP关于单目标最短路径(SDSP)问题和 MMASAPSP关于全部顶点对的最短路径问题(all-pairs shortest path, APSP)的计算时间上界分别为Ο(lm+n/ρ)和Ο(nlogn+logllog(Δl)/ρ),后者为目前元启发式算法(meta-heuristic)关于APSP问题最好的界。进一步,Sudholt和Thyssen[43]讨论了边权数带噪声随机最短路径问题,给出了噪声强度、近似保证以及平均时间复杂度之间的权衡关系。

最近，Lissovoi和Witt[44]研究了λ只蚂蚁的最大最小蚂蚁系统λ-MMAS算法在动态SDSP问题上的时间复杂度。他们指出每个顶点上放一定数量的蚂蚁甚至是常数只蚂蚁就能有效地求解动态SDSP问题，给出了蚂蚁数量、挥发因子及计算时间之间的关系。此外，他们还研究了MMAS算法在动态MAZE函数上的性能[47]。

3.3.3NP难问题

旅行商问题(traveling salesman problem, TSP)是组合优化中著名的NP难问题,也是蚁群算法的首个成功的测试问题。Zhou[45]首次分析了蚁群算法求解两个TSP实例的计算时间,从理论上首次证实了蚁群算法求解NP难问题的有效性,是蚁群算法关于NP难问题时间复杂性分析的首项工作。作者首次提出ACO求解TSP的严格计算时间分析,构造了完全图和非完全图的两个TSP实例,分析和估计了(1+1)MAX-MIN Ant Algorithm求解TSP实例的平均计算时间上界；同时讨论了算法中关于能见度和信息素值等控制参数的变化对算法计算时间的影响。 Kötzing等人[46]在文献[45]的基础上进行了有效的扩展,使用了一种新的蚂蚁解的构造图的方式,表明其具有更强的局部属性,并证明了能够得到一个更好的计算时间界。对于一些实例,算法容易陷入局部最优,计算时间为指数级。然而,当启发式因子足够大时,很快就能够找到最优解。

实际上,许多经典的组合优化问题都为NP难解问题[7]。由复杂性理论可知对于这类问题,不存在多项式时间的确定性算法除非P=NP。蚁群优化算法求解更多的NP难问题的性能目前还未知,这方面的工作才刚开始,对于更深入的了解蚁群算法的运行机理,求解NP难问题的性能,以及指导算法设计及应用有重要的现实意义。

表1列举了近十年来蚁群优化算法理论研究的一些典型研究成果,包括从简单的拟布尔函数到NP难问题,不同的信息素更新机制,以及参数设置对算法性能影响等方面的理论研究成果。

表1　蚁群优化算法计算复杂性理论成果

4结束语

本文从蚁群算法框架、理论分析方法以及理论研究结果等方面出发,对蚁群优化算法的理论研究进展进行了归纳和介绍。此外,还对蚁群优化算法理论研究中的若干问题进行了分析讨论。当前蚁群算法的理论研究成果仍然有限，其理论分析方法和数学工具有待进一步完善和探索。蚁群算法理论研究中还有许多亟待解决的问题。

1)蚁群算法理论分析工具还非常有限，这也是阻碍其向前发展的一个主要因素。现有的理论分析方法主要是马尔可夫链理论、适应值划分技术及漂移分析等方法。这些工具或者本身比较复杂，或者只是适应一些特殊情形的分析，甚至还需要满足一些严格的条件才能使用。因此寻求新的方法和工具也是未来的一个方向。

2)当前蚁群优化算法理论研究局限于一些简化的算法模型，基于种群的、更加复杂的构造过程还有待于进一步深入研究。对于n-ANT算法的有效性如何，是否蚂蚁的数量与算法的时间复杂度存在某种关系还未知。通过研究群体规模、构造过程、算法参数等对算法性能的影响，深入挖掘蚁群优化算法的潜能，更好地指导算法设计及应用。对于一个NP难解组合优化问题，蚁群算法能否获得比已有算法更好的近似比？如何获得更紧的时间界等，这些问题都有待于深入研究。

3)将现有蚁群优化算法的理论分析结果扩展到更多的智能算法中。目前在差分进化算法、分布评估算法、粒子群算法以及Memetic算法等随机启发式搜索的理论研究还非常有限，可以尝试将现有的理论分析结论进行有效扩展。此外，当前蚁群算法主要关注离散空间优化，可以向连续优化做进一步扩充。通过对更多算法、更多问题的研究，从中找出一些共性的东西，进一步丰富和增强群智能搜索算法的理论基础。

蚁群优化算法理论研究中涉及到的问题很多,本文不可能做到面面俱到,希望能够起到一个抛砖引玉的作用,对于今后更加深入的研究能够有所帮助和启发。

参考文献:

[1]DORIGO M, MANIEZZO V, COLORNI A. Theantsystem: An autocatalytic optimizing process Technical Report 91-016[R]. Milan, Italy: Dipartimento di Elettronica, Politecnico di Milano, 1991.

[2]DORIGO M, STUTZLE T. 蚁群优化[M]. 张军, 胡晓敏, 罗旭耀, 译. 北京: 清华大学出版社, 2007: 110-246.

[3]DORIGO M, BLUM C. Ant colony optimization theory: a survey[J]. Theoretical computer science, 2005, 344(2-3): 243-278.

[4]段海滨, 王道波, 于秀芬. 蚁群算法的研究现状及其展望[J]. 中国工程科学, 2007, 9(2): 98-102.

DUAN Haibin, WANG Daobo, YU Xiufen. Ant colony algorithm: survey and prospect[J]. Engineering science, 2007, 9(2): 98-102.

[5]NOCEDAL J, WRIGHT S J. Numerical optimization[M]. New York: Springer, 2000.

[6]VAZIRANI V V. Approximation algorithms[M]. Berlin Heidelberg: Springer, 2003.

[7]GAREY M R, JOHNSON D S. Computers and Intractability-A Guide to the Theory of NP-Completeness[M]. New York: Freeman W H and Company, 1979.

[8]COLORNI A, DORIGO M, MANIEZZO V. An investigation of some properties of an “Ant algorithm”[C]//Proceedings of Parallel Problem Solving from Nature II (PPSN 92). Brussels, Belgium, 1992: 515-526.

[9]STÜTZLE T, HOOS H H. MAX-MIN ant system[J]. Future generation computer systems, 2000, 16(8): 889-914.

[10]GUTJAHR W J. Mathematical runtime analysis of ACO algorithms: survey on an emerging issue[J]. Swarm intelligence, 2007, 1(1): 59-79.

[11]DROSTE S, JANSEN T, WEGENER I. On the analysis of the (1+1) evolutionary algorithm[J]. Theoretical computer science, 2002, 276(1-2): 51-81.

[12]WEGENER I, WITT C. On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions[J]. Journal of discrete algorithms, 2005, 3(1): 61-78.

[13]WEGENER I. Towards a theory of randomized search heuristics[M]//ROVAN B, VOJTP. Mathematical Foundations of computer science 2003. Berlin Heidelberg: Springer, 2003: 125-141.

[14]WEGENER I. Methods for the analysis of evolutionary algorithms on pseudo-boolean functions[M]//Evolutionary Optimization. Dordrecht: Kluwer Academic Publishers, 2002, 48: 349-369.

[15]BEYER H G, SCHWEFEL H P, WEGENER I. How to analyse evolutionary algorithms[J]. Theoretical computer science, 2002, 287(1): 101-130.

[16]HE J, YAO X. Towards an analytic framework for analysing the computation time of evolutionary algorithms[J]. Artificial intelligence, 2003, 145(1-2): 59-97.

[17]HE J, YAO X. Drift analysis and average time complexity of evolutionary algorithms[J]. Artificial intelligence, 2001, 127(1): 57-85.

[18]HE J, YAO X. From an individual to a population: an analysis of the first hitting time of population-based evolutionary algorithms[J]. IEEE transactions on evolutionary computation, 2002, 6(5): 495-511.

[19]GUTJAHR W J. A graph-based ant system and its convergence[J]. Future generation computer systems, 2000, 16(8): 873-888.

[20]STÜTZLE T, DORIGO M. A short convergence proof for a class of ACO algorithms[J]. IEEE transactions on evolutionary computation, 2002, 6(4): 358-365.

[21]GUTJAHR W J. On the finite-time dynamics of ant colony optimization[J]. Methodology and computing in applied probability, 2006, 8(1): 105-133.

[22]黄翰, 郝志峰, 吴春国，等. 蚁群算法的收敛速度分析[J]. 计算机学报, 2007, 30(8): 1344-1353.

HUANG Han, HAO Zhifeng, WU Chunguo, et al. The convergence speed of ant colony optimization[J]. Chinese journal of computers, 2007, 30(8): 1344-1353.

[23]BIRATTARI M, Dicaro G, DORIGO M. Toward the formal foundation of ant programming[M]//DORIGO M, DI CARO G, SAMPELS M. Ant Algorithms. Berlin Heidelberg: Springer-Verlag, 2002, 2463: 188-201.

[24]MEULEAU N, DORIGO M. Ant colony optimization and stochastic gradient descent[J]. Artificial life, 2002, 8(2): 103-121.

[25]ZLOCHIN M, BIRATTARI M, MEULEAU N, et al. Model-based search for combinatorial optimization: a critical survey[J]. Annals of operations research, 2004, 131(1-4): 373-395.

[26]GUTJAHR W J. A generalized convergence result for the graph-based ant system metaheuristic[J]. Probability in the engineering and informational sciences, 2003, 17(4): 545-569.

[27]NEUMANN F, WITT C. Runtime analysis of a simple ant colony optimization algorithm[C]//Proceedings of the 17th International Symposium on Algorithms, ISAAC 2006. Kolkata, India, 2006, 4288: 618-627.

[28]NEUMANN F, SUDHOLT D, Wit C. Comparing variants of MMAS ACO algorithms on pseudo-Boolean functions[C]//Proceedings of International Workshop, SLS 2007. Brussels, Belgium, 2007: 61-75.

[29]NEUMANN F, WITT C. Runtime analysis of a simple ant colony optimization algorithm[J]. Algorithmica, 2009, 54(2): 243-255.

[30]GUTJAHR W J. First steps to the runtime complexity analysis of ant colony optimization[J]. Computers & operations research, 2008, 35(9): 2711-2727.

[31]DOERR B, JOHANNSEN D. Refined runtime analysis of a basic ant colony optimization algorithm[C]//Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007). Singapore, 2007: 501-507.

[32]DOERR B, NEUMANN F, SUDHOLT D, et al. On the runtime analysis of the 1-ANT ACO algorithm[C]//Proceedings of Genetic and Evolutionary Computation Conference (GECCO’2007). London, England, 2007: 33-40.

[33]DOERR B, NEUMANN F, SUDHOL D, et al. Runtime analysis of the 1-ANT ant colony optimizer[J]. Theoretical computer science, 2011, 412(17): 1629-1644.

[34]GUTJAHR W J, SEBASTIANI G. Runtime analysis of ant colony optimization with best-so-far reinforcement[J]. Methodology and computing in applied probability, 2008, 10(3): 409-433.

[35]NEUMANN F, SUDHOLT D, WITT C. Analysis of different MMAS ACO algorithms on unimodal functions and plateaus[J]. Swarm intelligence, 2009, 3(1): 35-68.

[36]NEUMANN F, SUDHOLT D, WITT C. A few ants are enough: ACO with Iteration-best update[C]//Proceedings of Genetic and Evolutionary Computation Conference (GECCO’2010). Portland, USA, 2010: 63-70.

[37] KÖTZING T, NEUMANN F, SUDHOLT D, et al. Simple Max-Min ant systems and the optimization of linear pseudo-Boolean functions[C]//Proceedings of the 11th Work-shop on Foundations of Genetic Algorithms (FOGA 2011). New York, NY, USA, 2011: 209-218.

[38]NEUMANN F, SUDHOLT D, WITT C. Rigorous analyses for the combination of ant colony optimization and local search[C]//Proceedings of the 6th International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS08). Brussels, Belgium, 2008: 132-143.

[39]NEUMANN F, WITT C. Ant colony optimization and the minimum spanning tree problem[J]. Theoretical computer science, 2010, 411(25): 2406-2413.

[40]KÖTZING T, LEHRE P K, OLIVETO P S, et al. Ant colony optimization and the minimum cut problem[C]//Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO’10). New York, NY, USA, 2010: 1393-1400.

[41]ATTIRATANASUNTHRON N, FAKCHAROENPHOL J. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs[J]. Information processing letters, 2008, 105(3): 88-92.

[42]SUDHOLT D, THYSSEN C. Running time analysis of Ant Colony Optimization for shortest path problems[J]. Journal of discrete algorithms, 2012, 10: 165-180.

[43] SUDHOLT D, THYSSEN C. A simple ant colony optimizer for stochastic shortest path problems[J]. Algorithmica, 2012, 64(4): 643-672.

[44]LISSOVOI A, WITT C. Runtime analysis of ant colony optimization on dynamic shortest path problems[J]. Theoretical computer science, 2015, 561: 73-85.

[45]ZHOU Y R. Runtime analysis of an ant colony optimization algorithm for TSP instances[J]. IEEE transactions on evolutionary computation, 2009, 13(5): 1083-1092.

[46] KÖTZING T, NEUMANN F, RÖGLIN H, et al. Theoretical analysis of two ACO approaches for the traveling sales man problem[J]. Swarm intelligence, 2012, 6(1): 1-21.

[47]LISSOVOI A, WITT C. MMAS versus population-based EA on a family of dynamic fitness functions[J]. Algorithmica, 2015, doi: 10.1007/s00453-015-9975-z.

Advances in theoretical research of ant colony optimization

XIA Xiaoyun1, 2，ZHOU Yuren3

(1. School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China; 2. School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China; 3. School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China)

Abstract：Theoretical investigations of the ant colony optimization (ACO) algorithm can help to improve our understanding of the theoretical basis of the algorithm and guide its appropriate application. Theoretical research on ACO has included analyses of early convergence, time complexity, and approximation performance. Investigation objectives have ranged from simple Boolean functions, to combinatorial optimization and practical application problems, to the analysis of NP-hardness problems. In this paper, we survey state-of-the-art theoretical ACO research from two aspects: the most common mathematical techniques and those less common. In addition, we introduce two mathematical analysis tools, including fitness value partitioning and drift analysis, and discuss important ACO issues, including ACO runtime analysis and approximation performance. More specifically, we provide comparative results for ACO’s performance in solving various problems. These studies provide a direction for better understanding the working principles of ACO. Finally, we highlight further research directions, including the introduction of new analytical tools and the study of more complicated algorithmic models.

Keywords：ant colony optimization; theoretical research; combinatorial optimization; convergence; time complexity; approximation performance

DOI:10.11992/tis.201510002

收稿日期：2015-10-07. 网络出版日期：2016-01-05.

基金项目：国家自然科学基金资助项目(61170081, 61472143)；江西省自然科学基金资助项目(20151BAB217008).

通信作者：周育人.E-mail：yrzhou@scut.edu.cn.

中图分类号：TP18; TP301.6

文献标志码：A

文章编号：1673-4785(2016)01-0027-10

作者简介：

夏小云，男，1982年生，博士研究生，主要研究方向为计算智能与机器学习。

周育人，男，1965年生，教授，博士生导师，博士，主要研究方向为计算智能、数据挖掘及社会网络。主持国家、省部级项目多项，发表学术论文50余篇。

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160105.1532.006.html