蟻群算法用于ＴＳＰ的并行策略及模型

摘要：蟻群算法是一種元啟發式算法，其經典應用是解決旅行商問題。該算法有著先天的并行特性。介紹了該算法的兩種并行實現策略，給出了蟻群算法的并行實現模型，分析了該算法并行實現需要解決的問題。

關鍵詞：蟻群算法； 元啟發式算法； 旅行商問題； 并行計算

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2007)12-0037-04

早在1991年，意大利學者M. Dorigo等人^[1，2]就提出了蟻群優化算法——AS（ant system，螞蟻系統），并將其應用于解決計算機算法學中經典的旅行商問題（TSP）。M.Dorigo系統地闡述了蟻群算法的基本原理和數學模型，并與遺傳算法、禁忌搜索算法、模擬退火算法、爬山法等進行了仿真實驗比較；同時把單純地解決對稱TSP拓展到解決非對稱TSP、指派問題（QAP）及車間作業調度問題等，而且還對算法中初始化參數對其性能的影響進行了初步討論^[3]。2000年M.Dorigo和E.Bonabeau等人發表了蟻群算法的研究綜述，把蟻群算法的研究推向了國際學術的前沿。W.J.Gutjahr在其撰寫的技術報告^[4]和學術論文^[5]中對蟻群算法的發展史有著特殊的貢獻。首次對蟻群算法的收斂性進行了證明，把蟻群算法的行為簡化為在一幅代表所求解問題的有向圖上的行走過程，進而從有向圖論的角度對一種改進的蟻群算法——GBAS（graphbased ant system，圖搜索螞蟻系統）的收斂性進行了理論分析，證明了在一些合理的假設條件下，GBAS能夠以一定的概率收斂到所求問題的最優解。

從螞蟻系統開始，基本的蟻群算法得到了不斷的發展和完善，并在TSP以及許多實際優化問題中進一步得到了驗證。蟻群算法本身隱含著一定的并行性。單只螞蟻在一次循環中獨立于其他螞蟻。從本質上看，蟻群算法以分布式的協同優化計算方式為特征，在串行計算機上對蟻群算法的模擬不能夠真正體現蟻群算法的本質特征，因而研究蟻群算法的并行機實現具有十分重要的意義。

1蟻群算法與TSP模型

1．1蟻群算法

蟻群算法是一種受自然啟發的基于群體智能的算法。算法模型源于真實螞蟻群體搜尋食物的過程：智能螞蟻（算法中的人工螞蟻）模擬真實螞蟻從巢穴到食物所在地之間搜索最短路徑，在問題的解空間中搜索。元啟發式蟻群算法中的智能螞蟻是相互協作的智能agent，使用一組規則去產生、更改局部和全局信息，在解空間中搜索以獲得較好的解。

給定一個連通的結構圖，圖的節點是問題可行解的組成元素。蟻群算法中的人工螞蟻隨機地在圖中的邊上行走。一個組合優化問題可描述為給定一組條件約束蟻群對解的構造過程。在構造解的每一步，只有問題可行解的組成部分（TSP中為圖的節點，即城市，也稱解元素）才會被加入到當前未完成的解。圖的點集和邊集都有對應的參數（稱為信息素痕跡參數、先驗值或可見度）。這些參數被人工螞蟻用來決定從一個節點移動到另一個節點的概率。

真實蟻群在所經過的路徑上釋放一種稱為信息素的物質來標記其所走過的道路，以對后來的螞蟻進行路徑啟示。信息素痕跡參數^[6]是對這種行為的模擬。一般來說，信息素痕跡參數可以賦予點或邊（TSP中信息素值賦給點）。

先驗值或可見度均可以賦予點或邊并代表問題實例的一種預啟發式信息（在TSP中表示兩直達城市間的距離長度）。給定一個人工螞蟻集合。一般的螞蟻算法構造包括初始化階段和循環（直到結束條件滿足）階段。初始信息素參數值很小。在以后的循環過程中， 每一只螞蟻都選擇一個解元素（從當前點開始下一個最好的直達城市）加入到當前已構造的部分可行解中以最終形成好的可行解。下一個解元素的選擇依據一定的概率規則。所有螞蟻都執行同一個概率規則進行信息素痕跡的更新。該規則為

d）當并行機實現時，局部迭代若干次后需要交換信息。局部迭代次數的增大會使得蟻群算法早熟的概率增大，而局部迭代次數減少則會增加通信時間。因此需要有效地解決蟻群算法過早停滯和減少通信開銷之間的平衡問題。

參考文獻：

[1]COLORNI A， DORIGO M， MANIEZZO V， et al. Distributed optimization by ant colonies[C]//Proc of th 1st European Conference on Artificial Life. Amsterdam:Elsevier Publisling，1991:134-142.

[2]DOGIGO M. Optimization， learning and natural algorithms[D].Italy：Politecnico diMilano，1992.

[3]DORIGO M， MANIEZZO V， COLORNI A. Ant system:optimization by a colony of cooperating agents[J]. IEEE Trans on Systems，Man，and Cybernetics:Part B，1996，26(1):29-41.

[4]GUTJAHR W J. A generalized convergence result for the graph based ant system[J].Probability in the Engineering and Information Sciences，2003，17(4):545-569.

[5]GUTJAHR W J. A graphbased ant system and its convergence[J].Future Generation Computer Systems，2000，16(8):873-888.

[6]BLUM C，ROLI A. Metaheuristics in combinatorial optimization:overview and conceptual comparison[J].ACM Computing Surveys，2003，35(3):268-308.

[7]邢文訓，謝金星. 現代優化計算方法[M].北京：清華大學出版社，2005.

[8]CARO G D. Swarm intelligence[M].[S.l.]:Morgan Kaufmann Publishers， 2005.

[9]BULLNHEIMER B， KOTSIS G， STRAU C. Parallelization strategies for the ant system， TR DOM 9-97[R]. Vienna:University of Vienna，1997.

[10]DORIGO M， STUTZLE T. Ant colony optimization[M].Cambridge:MIT Press，2003.

[11]段海濱. 蟻群算法及其在高性能電動仿真轉臺參數優化中的應用研究[D]. 南京:南京航空航天大學，2005.

[12]秦玲.蟻群算法的改進與應用[D]. 揚州:揚州大學，2004.

[13]CHU S C， RODDICK J F， PAN J S， et al. Parallel ant colony systems[C]//Proc of the 14th International Symposium on Methodologies for Intelligent System. 2003:279-284.

[14]段海濱. 蟻群算法原理及其應用[M]. 北京：科學出版社，2005.

[15]GENDRON B. Parallel computing in combinatorial optimization[M].Pisa:[s.n.]，2005.

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