蟻群優(yōu)化算法的理論研究進展

夏小云，周育人

(1.江西理工大學 信息工程學院，江西 贛州 341000；2.華南理工大學 計算機與工程學院，廣東 廣州 510006；3.中山大學 數(shù)據(jù)科學與計算機學院，廣東 廣州 510006)

蟻群優(yōu)化算法的理論研究進展

夏小云1,2，周育人3

(1.江西理工大學 信息工程學院，江西 贛州 341000；2.華南理工大學 計算機與工程學院，廣東 廣州 510006；3.中山大學 數(shù)據(jù)科學與計算機學院，廣東 廣州 510006)

摘要：蟻群優(yōu)化算法的理論研究有助于更好地理解算法的原理以及指導算法應用?；仡櫫讼伻簝?yōu)化算法的收斂性分析、時間復雜度分析與近似性能分析等理論研究進展,分析了其理論研究的對象從簡單的擬布爾函數(shù)轉為組合優(yōu)化問題以及實際應用問題。從蟻群算法理論分析方法和研究問題類型2個方面對蟻群算法的理論研究進行綜述。介紹了適應值劃分、漂移分析等最基本的數(shù)學分析工具,對時間復雜性及近似性能等重要問題進行了探討。總結比較了蟻群算法求解各類問題的性能，指出這些研究能夠更加深入了解蟻群算法的運行機制。最后,探討了目前蟻群算法理論研究中亟待解決的問題,指出引入新的分析工具以及研究更為復雜的算法模型等是值得進一步研究的方向和內容。

關鍵詞：蟻群優(yōu)化算法；理論研究；組合優(yōu)化；收斂性；時間復雜度；近似性能

中文引用格式：夏小云，周育人.蟻群優(yōu)化算法的理論研究進展[J]. 智能系統(tǒng)學報， 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.

隨機啟發(fā)式搜索(randomized search heuristics, RSHs)算法是近年來發(fā)展較快的研究領域,在許多應用中取得了豐富的成果。這類啟發(fā)式算法主要包括隨機局部搜索(randomized local search, RLS)、禁忌搜索(tabu search)、模擬退火(simulated annealing, SA) 、演化算法(evolutionary algorithms, EAs) 以及粒子群優(yōu)化算法(particle swarm optimization, PSO)等。這些算法經常用來作為一些難解優(yōu)化問題的近似求解方法。由于這類智能算法的智能性、普適性以及全局搜索能力,使得其為求解NP難解優(yōu)化問題開辟了一條新的途徑。蟻群優(yōu)化算法(ant colony optimization, ACO)是這類算法的杰出代表之一。

蟻群算法是受螞蟻群體覓食行為的啟發(fā),由意大利學者Dorigo等[1]提出的一種基于種群的模擬進化算法。螞蟻覓食過程中借助于信息素(pheromone)這種化學物質進行信息的交流和傳遞,能夠根據(jù)所走路徑長度自主選擇下一個將要行走的地方,并表現(xiàn)出正反饋現(xiàn)象。這種正反饋機制能幫助螞蟻很快找到最優(yōu)覓食路徑。蟻群算法以信息素更新和概率轉移為基本操作,并以此指導搜索方向。蟻群算法作為一種新型的智能仿生類進化算法,已在許多領域獲得了廣泛的應用。例如在TSP(traveling salesman problem)問題、二次規(guī)劃問題、 函數(shù)優(yōu)化、網(wǎng)絡路由優(yōu)化、機器人路徑規(guī)劃、數(shù)據(jù)挖掘、作業(yè)流程規(guī)劃、圖形著色等領域獲得了廣泛的應用,并取得了較好的效果,具體可以參考張軍等的譯著[2]。此外,國內學者段海濱等[4]對蟻群算法的應用領域的研究成果做了較全面的綜述。

自從蟻群算法提出后,許多研究者在蟻群算法的設計及應用方面取得了豐富的研究成果。大量的實驗也表明其針對一些優(yōu)化問題的求解非常有效。然而,從理論上來看,蟻群算法缺乏比較完備的理論基礎。目前更迫切地希望為該算法建立堅實的理論基礎[10,13],以幫助更好地理解算法的運行機制,了解算法對于求解什么類型的問題有效。為算法的設計,參數(shù)選取以及算法的運用指明改進的方向。當前蟻群算法理論研究遠遠落后于算法的數(shù)值實驗和真實應用,主要原因在于隨機啟發(fā)式算法理論分析的艱難性[15]。蟻群算法具有隨機性、群體性、普適性等特性,這些特征使得算法表現(xiàn)出復雜的動態(tài)行為,由此引出的復雜多變的隨機過程增加了算法理論分析的難度,經典算法設計與分析的方法和工具也難以直接應用于這類新型隨機仿生算法。

在2006年之前,研究人員主要關注于ACO收斂性分析[19-21,26]以及ACO算法與其他優(yōu)化算法的關系[25],從理論上探索算法為什么有效。 Gutjahr[19]提出了一個基于圖的螞蟻系統(tǒng)(graph-based ant system, GBAS), Gutjahr首次證明了該模型蟻群算法在一定條件下以概率1-ε收斂到最優(yōu)解,其中ε為任意小的常數(shù)且ε>0。Stützle and Dorigo[20]等給出了普通蟻群算法(ant colony system，ACS)和MMAS(max-min ant system)的收斂性證明。 Gutjahr[21]進一步提出使用常微分方程逼近ACO隨機過程,并基于此來對ACO算法的收斂速度進行粗糙的理論預測。國內學者黃翰、郝志峰等[22]根據(jù)蟻群算法的特性,基于吸收態(tài)Markov 過程的數(shù)學模型,提出了蟻群算法的收斂速度分析理論,并給出了ACO-難和ACO-易兩類問題的界定方法。蟻群算法理論研究的另一個方向是將蟻群算法和其他學習算法進行比較, 如Birattari[23]、Meuleau[24]等分別建立了ACO與最優(yōu)控制加強學習算法、隨機梯度下降算法的聯(lián)系。

近年來,以遺傳算法為基礎的演化算法時間復雜性研究取得了一些重要進展。以Droste[11]、Wegener[12]等為代表的德國學派分析了群體規(guī)模為1的簡單爬山演化算法(1+1)EA求解一些擬布爾函數(shù)(OneMax, LeadingOnes, Trap Function)的平均計算時間,取得了一系列研究成果。He Jun和Yao Xin使用吸收馬爾可夫鏈[16]、漂移分析[17]等工具建立演化算法時間復雜性分析模型和方法以及分析群體在演化算法時間復雜性分析中的作用[18]等。這些研究極大地激發(fā)和推動了蟻群算法的理論研究工作。

蟻群算法最初用于旅行商問題的求解,進而推廣到各種組合優(yōu)化問題(甚至連續(xù)函數(shù)優(yōu)化問題)。Dorigo和Blum[3]總結了截至2005年蟻群算法理論研究及應用中取得的階段性研究成果,并特別指出蟻群算法時間復雜性將是今后一個重要的、有意義的研究方向,將其列為蟻群算法理論研究的公開性問題。

時間復雜度研究是指算法找到優(yōu)化問題最優(yōu)解或近似最優(yōu)解的計算時間,是衡量算法性能最基本、最重要的指標。W.J.Gutjahr[10]總結了截止2007年的蟻群算法時間復雜性研究成果和方法,并指出了一些發(fā)展方向。目前,蟻群算法時間復雜性研究正處于啟動階段,研究內容、深度都非常有限,很多基本問題尚未涉及。當前僅僅研究了螞蟻規(guī)模為1的1-ANT的情形,而與真實的蟻群算法相關的問題,如多螞蟻蟻群系統(tǒng)求解真實的組合優(yōu)化問題等,都有待深入研究。可以預計,這些研究將會有重要意義,同時又將是富有挑戰(zhàn)性的、艱難的工作。目前ACO算法理論研究主要是關于一些人工擬布爾函數(shù)以及一些經典的組合優(yōu)化問題的時間復雜性分析。最具代表性的如國內學者Zhou Yuren[45]研究了ACO求解經典TSP問題的時間復雜度，這也是ACO算法在NP難解問題理論分析上的首項工作。

一般情況下,對于典型的難問題—NP-完全(難)(non-deterministic polynomial-complete hard)優(yōu)化問題,人們找不到多項式時間的確定性算法。由于NP難解組合優(yōu)化問題本身結構的復雜性,確定性算法(窮舉法、分支界定、動態(tài)規(guī)劃等)無法保證在多項式內獲得精確解,轉而尋求一些近似算法[6]。蟻群優(yōu)化作為隨機啟發(fā)式方法,不能期待其在多項式時間內找到NP-完全(難)優(yōu)化問題所有實例的精確解。實際上,蟻群算法在很多優(yōu)化問題上扮演著近似算法的角色,一般用于獲得滿意解或者近似解。因此蟻群優(yōu)化算法的近似性能分析就變得尤為重要。希望在平均多項式時間內獲得近似最優(yōu)或者可接受的解,對于理解蟻群算法在NP難優(yōu)化問題上的工作原理以及尋求其能獲得的近似性能非常關鍵,并將進一步推進蟻群算法的理論研究及應用進展。對于豐富和發(fā)展近似算法和組合優(yōu)化理論,切實有效地解決一些實際問題具有重要現(xiàn)實意義。

1蟻群優(yōu)化算法：模型、描述、變體

1.1優(yōu)化問題及算法描述

蟻群算法是一種隨機啟發(fā)式搜索方法,它具有較強的魯棒性，優(yōu)良的分布式計算機制并易于與其他方法相結合等優(yōu)點。目前人們對蟻群算法的研究已經由當初單一的旅行商問題(TSP)領域滲透到了多個其他應用領域[2],由解決一維、靜態(tài)優(yōu)化問題發(fā)展到解決多維、動態(tài)優(yōu)化問題,由離散求解空間逐漸拓展到連續(xù)求解空間,使得該群智能算法在科學研究及實際問題求解中表現(xiàn)出了巨大的潛力和優(yōu)勢。

優(yōu)化問題可以分為兩類：連續(xù)的優(yōu)化問題和離散的優(yōu)化問題。連續(xù)的優(yōu)化問題是指其具有連續(xù)的變量、經常需要計算導數(shù)、使用牛頓方法或者線性規(guī)劃技術等。本文關注的是離散的優(yōu)化問題。離散優(yōu)化問題也稱為組合優(yōu)化問題,是指在有限的或者可數(shù)無限的潛在解集中搜索滿足給定約束條件的最優(yōu)解。然而,組合優(yōu)化問題通常包含大量的局部極值點,而且許多組合優(yōu)化問題為NP完全(難)問題。

一個組合優(yōu)化問題P通常可描述為一個三元組(S,f,Ω),其中S為給定的由所有狀態(tài)構成的搜索空間,f:S→R+為目標函數(shù),一般為最大化或者最小化；Ω為可行解滿足的約束條件集合。一個可行解s*∈S,如果對于最小化問題有?s∈S,f(s*)≤f(s),對于最大化問題有?s∈S,f(s*)≥f(s),則稱s*為一個全局最優(yōu)解。定義最優(yōu)解集合為S*?S,算法的目標是從優(yōu)化問題的可行解集中找到最優(yōu)解s*∈S*。

蟻群算法的啟發(fā)來自于一個螞蟻群體對食物源的搜索，是一種杰出而具有代表性的群智能算法，對于其算法描述可以參考相關文獻[1-5]。ACO算法有一些不同的變體,為了分析的方便，在當前理論分析方面,還是主要考慮一只螞蟻的情況。下面給出蟻群優(yōu)化算法理論研究中用到的一個簡單的ACO算法(1+1)螞蟻算法((1+1)Ant Algorithm,(1+1)AA),其類似于演化算法理論分析中的(1+1)EA。不失一般性,考慮最小化問題。(1+1)AA算法描述如下

Algorithm 1: (1+1)AA

Begin

初始化：參數(shù)設置,信息素值,選擇一個初始解s，While(不滿足終止條件)

使用構造過程構建一個新的解s′；

選擇：如果f(s′)

End while

End

(1+1)AA算法使用簡單的爬山選擇策略,如果當前螞蟻解的函數(shù)值大于新的螞蟻解的函數(shù)值,則當前螞蟻解被新螞蟻解替代。以下兩節(jié)分別介紹理論分析中蟻群算法解的構建以及信息素更新機制。

1.2解的構建

對于一個給定的優(yōu)化問題,其解通過螞蟻在一個具有信息素值的構造圖(construction graph)的邊上隨機游走獲得。另外,蟻群算法也使用啟發(fā)式信息來指導隨機游走的方向。螞蟻從構造圖的任意一個初始狀態(tài)出發(fā),隨機游走到下一個鄰域結點。這個移動是基于概率規(guī)則,依賴于信息素和啟發(fā)式信息。

令G=(V,E)為一給定問題的構造圖。τ(u,v)為邊e=(u,v)∈E上的信息素值,η(u,v)為啟發(fā)式信息。假設螞蟻當前所在位置為頂點u,其允許訪問的后續(xù)結點為Nu。螞蟻在下一步訪問結點v∈Nu的概率由以下公式給出：

式中：參數(shù)α表示螞蟻在運動過程中所積累的信息素在指導螞蟻搜索路徑的相對重要性；參數(shù)β表示路徑能見度的相對重要性,即表示啟發(fā)式信息η(u,v)的重要性。

1.3信息素更新機制

根據(jù)信息素更新方式的不同,也就產生具有不同信息素更新機制的蟻群算法[8]。為了防止算法的早熟, Stützle 和 Hoos[9]提出了最大最小螞蟻系統(tǒng)。在信息素的更新過程中,將其限制在一個最大最小信息素范圍內[τmin,τmax]。根據(jù)邊e=(u,v)∈E是否包含在至今最好的解x中,其信息素更新規(guī)則如下：

(1)

稱使用上述信息素更新規(guī)則的(1+1)AA算法為(1+1)MMAA。 類似的(1+1)MMAA在文獻[28,34]中分別叫做MMAS*和MMASbs。

2理論分析方法及數(shù)學工具

對于一個確定的優(yōu)化問題,蟻群算法找到一個最優(yōu)解的迭代次數(shù)用隨機變量t表示。在蟻群算法的理論分析中通常需要估計最好情況、平均情況、最壞情況下，以什么樣的概率Pr(t≤T)在什么樣的期望運行時間E(t)內，找到什么樣的解(近似解)。本節(jié)介紹一些蟻群算法的理論分析方法和基本的數(shù)學工具。不失一般性,考慮最小化問題。

2.1適應值劃分

對于給定的優(yōu)化問題，感興趣的是算法找到最優(yōu)解的平均迭代次數(shù)。這里介紹適應值劃分技術，該技術在演化算法的理論分析中得到了成功運用。其原理是種群中最好的個體適應值一直都確保不會變差。因此通過估計最好的個體適應值變好的期望時間界來獲得優(yōu)化時間。這種方法稱為基于適應度劃分的方法(fitness-based partitions)或者適應度等級方法[14]。

定義1(適應值劃分)給定一個有限的搜索空間S,不失一般性,假設函數(shù)f:S→R最小化, 考慮函數(shù)f的所有可能的不同的函數(shù)值A0,A1,…,Am,對于?a∈Ai和?b∈Aj,如果f(a)

對于ACO，算法每次接受優(yōu)于當前最好的解，算法每次運行都朝著最優(yōu)解的方向前進,如圖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,…},每一操作發(fā)生的概率相同,假設為P(opt)=pm≥α(t=1,2,….)。給定任意初始解s,算法通過執(zhí)行操作opt∈Op，一步一步逐漸到達最優(yōu)解sopt。不失一般性,考慮最小化問題。定義優(yōu)化問題的適應值函數(shù)f(st)(t=1,2,...),d(st)=f(st)-f(sopt)為第t代時的解st與目標最優(yōu)解sopt相差的適應值距離。根據(jù)隨機啟發(fā)式算法的特點,給定不同的初始解,其求解問題的迭代次數(shù)也不一樣,因此考慮的是期望迭代次數(shù)。算法找到可接受的操作,使得st+1優(yōu)于st。假定算法通過執(zhí)行給定的操作使得減少的期望距離至少為

(2)

由(2)得

(3)

當前解離目標最優(yōu)解距離減少由兩部分產生:可接受的操作和不接受的操作,而不接受的操作距離減少的貢獻為0。

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

(4)

令Yt=d(st),有

2.3尾概率不等式

偏差不等式廣泛應用于隨機算法的分析中。在許多啟發(fā)式搜索算法的例子中,對于分析啟發(fā)式的典型行為是非常有用的。其通常用于估計隨機變量偏離期望值的概率。

基于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參數(shù)ρ、α、β對算法性能影響

到目前為止,蟻群算法中揮發(fā)因子、信息素值控制參數(shù)、啟發(fā)式信息(能見度)控制參數(shù)的設置,對于界定蟻群算法的難問題和易問題并沒有從理論上真正得以解釋說明。從蟻群算法求解一些實際問題的實驗效果來看,信息素揮發(fā)因子是一個比較關鍵的參數(shù)。揮發(fā)因子越大,表現(xiàn)出的正反饋作用越強,以往走過的路徑被再次選擇的可能性就越大,搜索隨機性變弱；相反,揮發(fā)因子越小,算法的隨機性就越大,其全局搜索能力也就變強。信息素揮發(fā)因子設置對于算法性能影響至關重要。

蟻群算法中信息素控制參數(shù)α反映螞蟻在行走過程中所積累的信息素對指導螞蟻搜索方向的相對重要性,能見度控制參數(shù)β反映啟發(fā)式信息對指導螞蟻搜索方向的相對重要性。Zhou[45]通過構造TSP實例,研究了參數(shù)α和β對算法計算時間的影響,指出對于完全圖實例,參數(shù)設置α=1,β=0到α=1,β=1,其期望運行時間上界也由O(n6)變?yōu)镺(n5)。K?tzing等[46]通過構建一個TSP實例分析了啟發(fā)式信息對于蟻群算法的性能影響,指出對于該實例取α=1,如果β=1,算法需要指數(shù)級運行時間找到最優(yōu)解；如果β=n,則算法以趨近于1的概率在一次迭代就能找到最優(yōu)解。

蟻群算法參數(shù)較多,設置也較復雜。目前理論分析主要通過一些構造實例來分析不同參數(shù)設置對于算法性能的影響。針對一般性的問題,參數(shù)如何設置對于蟻群算法來說是有效的,還有待于進一步深入探究。

3.2從1-ANT到n-ANT

Neumann等人[36]研究了λ-MMASIB算法求解擬布爾函數(shù)的性能。他們指出,當λ=2,也即構造2個螞蟻解時,該算法在揮發(fā)因子足夠小的情況下,能夠在多項式時間內求解OneMax函數(shù)。

Attiratanasunthron和Fakcharoenphol[41]研究了ACO算法求解有向無環(huán)圖單源最短路徑問題的多項式時間界。特別地,對于頂點數(shù)為n，邊數(shù)為m的有向無環(huán)圖,具有n只螞蟻的n-ANT算法能夠在期望時間Ο(n2mlogn/ρ)內求解單源最短路徑問題。

螞蟻的數(shù)量決定了每次迭代構造的解的個數(shù)。在不同參數(shù)情況下,真實的多螞蟻蟻群系統(tǒng)如何影響算法性能,如何設置螞蟻個數(shù),以及n-ANT算法求解組合優(yōu)化問題的性能,能夠在什么樣的時間內獲得什么樣的解,是值得進一步研究的問題。

3.3從擬布爾函數(shù)到NP難問題

3.3.1擬布爾函數(shù)

以下7個函數(shù)為分析演化和蟻群算法時間復雜性的典型人工擬布爾函數(shù)：

從2006年開始,蟻群算法關于時間復雜性分析的理論研究也相繼出現(xiàn), Neumann[27,29]等通過模擬(1+1)EA建立了一個簡單的ACO算法1-ANT分析模型,給出了1-ANT求解簡單擬布爾函數(shù)OneMax平均時間復雜度為O(nlogn),并且指出揮發(fā)因子對時間復雜度起著關鍵性的影響。與此同時,Gutjahr[30]采用近似的常微分方程組估計算法時間復雜度,研究了GBAS和AS兩個ACO算法的同一分析。 Doerr等[31]以1-ANT求解關于OneMax為例,分析了隨著揮發(fā)系數(shù)的變化,1-ANT算法時間復雜度從指數(shù)時間到多項式時間的相位轉移。Doerr等[32-33]研究了1-ANT算法信息素更新機制對時間復雜度的影響,指出如果揮發(fā)因子設置過小,算法很容易陷入停滯狀態(tài)。對于擬布爾函數(shù)LeadingOnes和BinVal,找到最優(yōu)解的期望時間也是指數(shù)級的。相反,如果參數(shù)設置合理,期望時間也從指數(shù)級降低到多項式時間。

學者們也研究了最大最小螞蟻系統(tǒng)(max-min ant system ,MMAS)[9]算法的性能。該算法是蟻群優(yōu)化的一個變體，其使用Best-So-Far更新機制。對于一些優(yōu)化問題,最大最小螞蟻系統(tǒng)能夠有效地避免停滯,并能獲得一個更有效的運行時間界。Gutjahr 和 Sebastiani[34]分析了MMAS在求解Needle-in-a-Haystack和LeadingOnes兩個擬布爾函數(shù)的時間復雜度,并基于演化算法中適應值劃分技術的基礎上提出了一種ACO的時間復雜度理論分析框架,將作為一般分析的一個非常有用的工具。 2007年,Neumann等[35]將ACO算法擴展到單峰函數(shù)和高原函數(shù)的期望運行時分析上,并使用非齊次過程估計了信息素邊界的首達時間,進一步研究了1-ANT算法關于LeadingOnes、Needle等其他擬布爾函數(shù)的時間復雜度；K?tzing等[37]也進一步研究了兩種MMAS算法求解線性擬布爾函數(shù)的時間復雜度,并給出了求解所有線性函數(shù)的一般時間上界Ο(n3logn/ρ)。Neumann、Sudholt和Witt[38]研究了ACO與局部搜索混合算法的影響,他指出對于一些人工構造的函數(shù),ACO算法結合局部搜索能夠以較高的概率將指數(shù)時間轉為多項式時間。對于另外一些函數(shù),情況則相反。

以上所有研究分析使用的方法和工具為組合優(yōu)化問題的更深層次的分析奠定了堅實的基礎。

3.3.2P問題

一些確定性的算法能夠在多項式時間內求解P類的組合優(yōu)化問題,實驗表明ACO算法進行求解也顯示出了其優(yōu)越性。 ACO算法在一些簡單函數(shù)上的分析所使用的方法和工具,也進一步推廣到實際的組合優(yōu)化問題上的分析中。目前ACO算法針對多項式可求解問題的理論分析也獲得了一些結果。我們并不期望蟻群優(yōu)化算法在這些優(yōu)化問題上能夠優(yōu)于那些最好的算法,而關鍵是對于其理論分析能夠更深入地了解蟻群算法工作機制,更好指導算法的設計及應用。

最小生成樹(minimum spanning trees)問題是數(shù)據(jù)結構與算法設計中一個經典的圖論問題。兩個著名的確定性算法Kruskal和Prim分別有最壞情況下的時間復雜度Ο((m+n)logn)和Ο(nlogn+m) (n為頂點數(shù),m為邊數(shù))。Neumann 和 Witt[39]分析了ACO算法求解最小生成樹問題的時間復雜度,其螞蟻解的構建是基于兩種不同的構造圖,Broder-based和Kruskal-based,并證明了最大最小螞蟻系統(tǒng)求解最小生成樹問題的期望時間上界為Ο(mnlogn)。

最短路徑問題的目標是搜索圖中兩結點之間的最短路徑。Dijkstra算法是求解該問題的典型路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。文獻[41-43]研究了最短路徑問題,并分別分析了ACO算法求解無環(huán)、有環(huán)、帶有噪聲情況下最短路徑問題的計算時間。Attiratanasunthron和Fakcharoenphol[41]研究了ACO算法求解有向無環(huán)圖單目標最短路徑問題(singledestinationshortestpath,SDSP)的多項式時間界。對于頂點數(shù)為n邊數(shù)為m的有向無環(huán)圖，具有n只螞蟻的n-ANT算法能夠在期望時間Ο(n2mlogn/ρ)內求解單源最短路徑問題。

在此基礎上,Horoba和Sudholt[42]將結果擴充到最大最小螞蟻系統(tǒng)(MMAS),得到MMASSDSP關于單目標最短路徑(SDSP)問題和 MMASAPSP關于全部頂點對的最短路徑問題(all-pairs shortest path, APSP)的計算時間上界分別為Ο(lm+n/ρ)和Ο(nlogn+logllog(Δl)/ρ),后者為目前元啟發(fā)式算法(meta-heuristic)關于APSP問題最好的界。進一步,Sudholt和Thyssen[43]討論了邊權數(shù)帶噪聲隨機最短路徑問題,給出了噪聲強度、近似保證以及平均時間復雜度之間的權衡關系。

最近，Lissovoi和Witt[44]研究了λ只螞蟻的最大最小螞蟻系統(tǒng)λ-MMAS算法在動態(tài)SDSP問題上的時間復雜度。他們指出每個頂點上放一定數(shù)量的螞蟻甚至是常數(shù)只螞蟻就能有效地求解動態(tài)SDSP問題，給出了螞蟻數(shù)量、揮發(fā)因子及計算時間之間的關系。此外，他們還研究了MMAS算法在動態(tài)MAZE函數(shù)上的性能[47]。

3.3.3NP難問題

旅行商問題(traveling salesman problem, TSP)是組合優(yōu)化中著名的NP難問題,也是蟻群算法的首個成功的測試問題。Zhou[45]首次分析了蟻群算法求解兩個TSP實例的計算時間,從理論上首次證實了蟻群算法求解NP難問題的有效性,是蟻群算法關于NP難問題時間復雜性分析的首項工作。作者首次提出ACO求解TSP的嚴格計算時間分析,構造了完全圖和非完全圖的兩個TSP實例,分析和估計了(1+1)MAX-MIN Ant Algorithm求解TSP實例的平均計算時間上界；同時討論了算法中關于能見度和信息素值等控制參數(shù)的變化對算法計算時間的影響。 K?tzing等人[46]在文獻[45]的基礎上進行了有效的擴展,使用了一種新的螞蟻解的構造圖的方式,表明其具有更強的局部屬性,并證明了能夠得到一個更好的計算時間界。對于一些實例,算法容易陷入局部最優(yōu),計算時間為指數(shù)級。然而,當啟發(fā)式因子足夠大時,很快就能夠找到最優(yōu)解。

實際上,許多經典的組合優(yōu)化問題都為NP難解問題[7]。由復雜性理論可知對于這類問題,不存在多項式時間的確定性算法除非P=NP。蟻群優(yōu)化算法求解更多的NP難問題的性能目前還未知,這方面的工作才剛開始,對于更深入的了解蟻群算法的運行機理,求解NP難問題的性能,以及指導算法設計及應用有重要的現(xiàn)實意義。

表1列舉了近十年來蟻群優(yōu)化算法理論研究的一些典型研究成果,包括從簡單的擬布爾函數(shù)到NP難問題,不同的信息素更新機制,以及參數(shù)設置對算法性能影響等方面的理論研究成果。

表1　蟻群優(yōu)化算法計算復雜性理論成果

4結束語

本文從蟻群算法框架、理論分析方法以及理論研究結果等方面出發(fā),對蟻群優(yōu)化算法的理論研究進展進行了歸納和介紹。此外,還對蟻群優(yōu)化算法理論研究中的若干問題進行了分析討論。當前蟻群算法的理論研究成果仍然有限，其理論分析方法和數(shù)學工具有待進一步完善和探索。蟻群算法理論研究中還有許多亟待解決的問題。

1)蟻群算法理論分析工具還非常有限，這也是阻礙其向前發(fā)展的一個主要因素?，F(xiàn)有的理論分析方法主要是馬爾可夫鏈理論、適應值劃分技術及漂移分析等方法。這些工具或者本身比較復雜，或者只是適應一些特殊情形的分析，甚至還需要滿足一些嚴格的條件才能使用。因此尋求新的方法和工具也是未來的一個方向。

2)當前蟻群優(yōu)化算法理論研究局限于一些簡化的算法模型，基于種群的、更加復雜的構造過程還有待于進一步深入研究。對于n-ANT算法的有效性如何，是否螞蟻的數(shù)量與算法的時間復雜度存在某種關系還未知。通過研究群體規(guī)模、構造過程、算法參數(shù)等對算法性能的影響，深入挖掘蟻群優(yōu)化算法的潛能，更好地指導算法設計及應用。對于一個NP難解組合優(yōu)化問題，蟻群算法能否獲得比已有算法更好的近似比？如何獲得更緊的時間界等，這些問題都有待于深入研究。

3)將現(xiàn)有蟻群優(yōu)化算法的理論分析結果擴展到更多的智能算法中。目前在差分進化算法、分布評估算法、粒子群算法以及Memetic算法等隨機啟發(fā)式搜索的理論研究還非常有限，可以嘗試將現(xiàn)有的理論分析結論進行有效擴展。此外，當前蟻群算法主要關注離散空間優(yōu)化，可以向連續(xù)優(yōu)化做進一步擴充。通過對更多算法、更多問題的研究，從中找出一些共性的東西，進一步豐富和增強群智能搜索算法的理論基礎。

蟻群優(yōu)化算法理論研究中涉及到的問題很多,本文不可能做到面面俱到,希望能夠起到一個拋磚引玉的作用,對于今后更加深入的研究能夠有所幫助和啟發(fā)。

參考文獻:

[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. 蟻群優(yōu)化[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]段海濱, 王道波, 于秀芬. 蟻群算法的研究現(xiàn)狀及其展望[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. 網(wǎng)絡出版日期：2016-01-05.

基金項目：國家自然科學基金資助項目(61170081, 61472143)；江西省自然科學基金資助項目(20151BAB217008).

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

中圖分類號：TP18; TP301.6

文獻標志碼：A

文章編號：1673-4785(2016)01-0027-10

作者簡介：

夏小云，男，1982年生，博士研究生，主要研究方向為計算智能與機器學習。

周育人，男，1965年生，教授，博士生導師，博士，主要研究方向為計算智能、數(shù)據(jù)挖掘及社會網(wǎng)絡。主持國家、省部級項目多項，發(fā)表學術論文50余篇。

網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160105.1532.006.html