一種新的蟻群優化算法信息素更新策略及其性能分析

摘要：針對蟻群優化算法的關鍵步驟——信息素軌跡更新過程進行了深入分析。通過理論上的證明和實驗驗證，提出了信息素軌跡更新中存在著一個利用—探索困境；在此基礎上針對這個現象提出了一種基于Metropolis接受準則的信息素更新策略，并通過在不同規模的TSP上的實驗，證明了這種新策略的有效性。

關鍵詞：蟻群優化算法； 信息素更新策略； 利用—探索困境； Metropolis接受準則

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2007)07－0086－03

0引言

在最近十幾年中，數種模仿蟻群覓食行為的算法被引用來解決組合優化問題。蟻群優化算法(ACO)包括：由M.Dorigo等人提出的Ant System和Elitist Strategy for Ant System[1~3]；Ant－Q System[4]、Ant Colony System[5，6]和B.Bullnheimer等人提出的另一種改進算法Rank－Based Version of Ant System[7]；T.Stützle等人提出的一種相當出色的改進算法MAX－MIN Ant System[8]。蟻群優化首先被應用到TSP和QAP問題中[1]，證明是相當有效的。最近，T.Stützle和M.Dorigo對一類蟻群優化算法作出了收斂性的證明[9]；C.Blum等人提出了一個蟻群優化算法超立方框架（Hypercube Framework）[10]；M.Birattari等人對于螞蟻程序方法（Ant Programming）就其作為解決由組合優化問題演繹出的多階段決策問題（Multi－Stage Decision Problem）的迭代蒙特卡羅實現（Iterated Monte Carlo Approach）提出了一個正式框架[11]。這些論文從很大程度上充實了蟻群優化算法的理論，尤其在蟻群算法的收斂性證明和通用框架的構建上，但是對于蟻群算法的闡述和分析尚未達到能建立完美的數學模型或通用框架的地步。

本文從闡述蟻群優化算法的基本框架開始，引出對蟻群算法一個重要環節——信息素軌跡更新過程的分析；進而提出了在信息素軌跡更新過程中存在著一種兩難困境，稱之為蟻群算法的利用—探索困境；針對此提出一種證明是有效的信息素軌跡更新策略，稱為基于Metropolis接受準則的信息素更新策略。

1問題與算法描述

從圖中可以看到，在第179代發現最優解后，經過了大約40代，歸一化λ分支系數就降到了1．2左右；在400代后，歸一化λ分支系數基本接近于1，算法已基本經收斂（事實上，未曾收斂的節點個數可以由(1-λbf)Ns來估算）。當然這是一個非常簡單的極小規模問題，所以算法發現了最優。筆者甚至觀察到，對于這樣的問題，在120代左右，算法也曾落入一個局優解。由于問題規模很小，算法得以跳出這個局優；如果問題規模較大，算法就極可能陷入某個局部較差的解。

本文給出其中一個節點（對應于圖2的第14節點，此節點的最優相鄰節點為7和13）更直觀的信息素分布，如圖3所示。可以更明顯地看到，節點12在100代左右曾落入一個局優解，在200代左右才正確搜索到最優，在250代基本收斂。在這里要再次強調算法跳出這個局優是由于問題規模極小，如果規模稍大，算法就極可能陷入某個局部較差的解。

廣義地說，這并不是蟻群優化算法的特質。許多非數值優化算法包括遺傳算法在內，均會存在搜索的深度和搜索廣度的沖突，這對于蟻群優化算法就是：信息素落差必須足夠大以保證算法搜索的方向（利用原有的信息）；同時信息素的落差又不能太過懸殊而使算法無法探索新解（探索新解）。所以，把這個信息素的兩難稱為利用—探索困境。一個好的算法必須給出一個均衡策略來兼顧兩者。一些相應策略也曾被提出，包括顯式限定信息素上下界、信息素混合更新策略和信息素平滑策略等[1~4，8]。在這里，提出一種基于Metropolis接受準則的信息素更新策略。

3一種新的信息素更新方法

采用上述策略是基于兩點理由。第一點理由已經在第2章給出了證明；而第二點理由將在下面予以例證。①在僅使用迄今最優解更新時，搜索將很快集中到最優解的鄰域中，限制了對潛在的更好解的搜索，進而搜索陷入差解的可能性也大大增加。②在使用該文的更新策略時，當系統溫度較高時，算法將以較大的概率接受Generate函數產生的不同解，進行廣泛的試探，能夠有效地避免算法初期陷入差解的狀況；當在系統溫度較低時，將以小概率接受Generate函數產生的不同解，算法的后期將搜索集中到迄今最優解的鄰域中，保證了算法收斂，同時縮短了算法的收斂時間，尤其是在問題規模較大時。使用TSPLIB95中不同規模的問題，給出不同更新策略的對比例證，如表1所示。

從表1的實驗結果可以看到，本文提出的基于Metropolis接受準則的信息素更新策略無疑是有效的，特別在問題規模較大時，這種策略能夠很有效地減少算法在早期落入較差解的可能性。同時對比全局+當代最優混合更新，此策略需要指定每一代的全局/當代最優的更新比例，所以Metropolis接受準則更新策略對于不同規模的問題有良好的魯棒性。

4結束語

該文通過蟻群優化算法的過程作出一個數學上的描述，特別是對于蟻群優化算法的最重要過程——信息素軌跡更新過程給出了理論分析和實驗驗證。本文提出了對于螞蟻算法的信息素更新過程中存在著一個利用—探索困境，信息素更新過程必須保證各條邊上的信息素落差足夠大從而為算法尋優提供指導，同時又必須保證各條邊上的信息素落差不至于太過懸殊而使算法無法探索新解進而陷入停滯。對于這種現象提出了一種結合了Metropolis接受準則信息素的更新策略。通過在不同規模的TSP上與以前的信息素更新策略的對比驗證，證明了新策略的有效性。新策略使得算法在運行初期能以大概率探索新解，在后期集中搜索某個區域，從而在很大程度上減少了算法因EE困境而在初期就陷入局優解的可能性，并且也能保證算法在后期的收斂并縮短算法的整體收斂時間。

本文的工作為后繼的研究提出了若干問題，包括為信息素更新過程建立完整的數學模型和提出更為魯棒的信息素更新策略。前者指的是對于信息素更新過程的公理化描述和信息素更新過程機理的完整闡述和證明；后者指的是信息素更新策略在大多數情況下，能夠作出一個最佳的均衡進而指導算法進行合理有效的搜索。

參考文獻：

[1]DORIGO M， MANIEZZO V， COLORNI A. Positive feedback as a search strategy[R].Milano:Politecnico di Milano， 1991.

[2]DORIGO M， MANIEZZO V， COLORNI A. The ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， Man， and Cybernetics: Part B， 1996，26(1):29－42.

[3]DORIGO M. Optimization， learning，and natural algorithms[D]. Milano:Politecnico di Milano，1992.

[4]GAMBARDELLA L M， DORIGO M. Ant－Q: a reinforcement learning approach to the traveling salesman problem: proc.of the 11th International Conference on Machine Learning[C]. San Francisco: Morgan Kaufmann， 1995:252－260.

[5]GAMBARDELLA L M， DORIGO M. Solving symmetric and asymmetric TSPs by ant colonies: proc.of IEEE International Conference on Evolutionary Computation[C]. Piscataway: IEEE Press， 1996:622－627.

[6]DORIGO M， GAMBARDELLAL M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation， 1997，1(1):53－66.

[7]BULLNHEIMER B， HARTL R F， STRAUSS C. A new rank based version of the ant system: a computational study[J]. Central European Journal for Operations Research and Economics， 1999，7(1): 25－38.

[8]STTZLE T， HOOS H H. Max－min ant system[J]. Future Generation Computer Systems， 2000，16(8):889－914.

[9]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.

[10]BLUM C， ROLI A， DORIG M. The hyper－cube framework for ant colony optimization[J]. IEEE Transactions on Systems， Man and Cyberetics: Part B， 2004，34(2):1161－1172.

[11]BIRATTARI M， CARO G D. DORIGO M. Toward the formal foundation of ant programming: proc.of the 3rd International Workshop on Ant Algorithms[C].London:Springer－Verlag， 2002.

[12]REINELT G. TSPLIB95[EB/OL].(1995).http://www.iwr.uni－heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”