蟻群算法研究現狀及發展

摘 要:蟻群算法是一類模擬生物群體突現聚集行為的新型機器學習技術。本文回顧了蟻群算法的主要概念，總結了蟻群算法與其他智能方法的融合，介紹了一種基于群體蟻群算法的硬件實現方法，最后對蟻群算法的發展方向提出了預測。

關鍵詞:蟻群算法智能方法優化硬件實現

中圖分類號:O224文獻標識碼:A文章編號:1674-098X(2011)07(c)-0132-02

在社會科學和工程技術的發展中，需要解決問題的復雜性、約束性、非線性，建模困難等問題日漸突出。多年來，人們一直致力于尋找一種有效處理此類問題的方法。蟻群算法最初是由意大利學者Macro Dorigo等人在螞蟻覓食行為的啟發下而提出的一種新型的元啟發式算法，隨著研究的逐步深入，Macro Dorigo與其合作者于1991年設計出了第一個蟻群優化算法——蟻群系統[1]。經過十幾年的發展，蟻群算法在理論和實際應用上取得了長足的發展。近幾年來，由于它在知識發現、數據挖掘、故障檢測、路徑規劃等領域的廣泛應用，研究逐漸趨熱。

蟻群算法通過模擬螞蟻在尋找食物過程當中，通過個體行為影響的累積，最后形成群體行為，從而找到適合問題的最優解。本文介紹了蟻群算法的基本理論，總結了國內外的研究現狀，最后對蟻群算法未來的研究方向提出了預測。

1 蟻群算法簡介[2]

1.1 信息素

單個螞蟻在行為過程中釋放一種化學物質，群體中的其他個體根據環境中的這種物質可以找到食物和窩之間的最短路徑，我們稱這種物質為信息素。

1.2 信息素更新

路徑上的信息素量隨著螞蟻的選擇以及隨時間的推移而產生的增加和消失的現象稱為信息素更新。

螞蟻完成一步或對所有路徑上的節點遍歷之后，要對路徑上的信息進行更新。因此，定義信息量的計算公式為:

(1)

(2)

式中:Tij(t+n)表示t+n時刻在節點i到節點j的路徑上的信息素更新;ρ表示信息素揮發系數;△Tij(t)表示循環中節點i到節點j的路徑上信息素的增量;表示第k只螞蟻在循環中的節點i到節點j的路徑上留下的信息素。

1.3 路徑選擇概率

螞蟻根據路徑上信息素的濃郁程度，按概率選擇路徑。

設網格G=(v，A，d)其中，d是A的權函數，目標是找到訪問每個節點一次的最短回路。每條路徑都有信息素變量Tij，Tij會隨著迭代次數的增加而變化。表示在t時刻螞蟻k從城市i轉移到城市j的概率:

(3)

allowdk表示螞蟻k下一步可走節點的集合，а表示信息量對螞蟻選擇路徑的作用大小，ηij表示螞蟻從節點轉移到城市的期望，β表示ηij的作用。

2 蟻群算法與其它智能算法的融合

2.1 蟻群算法與遺傳算法

遺傳算法作為仿生態進化算法的一種，具有天生隱含并行性和強大的全局搜索能力，最初是由密歇根大學Holland教授創建的。它通過模擬自然界中，生物競爭產生出適者生存的進化原理來得到解空間的全局最優解。遺傳算法的特點很多，通過將遺傳算法與蟻群算法融合，可以更有效解決蟻群算法中的很多問題。文獻[3]通過利用遺傳算法首先對工程設計中的連續空間問題進行優化，然后采用蟻群算法再對所得結果進行精確化，從而解決了蟻群算法不能很好應對連續空間求解的問題。文獻[4]通過利用遺傳算法的快速的全局搜索能力結合蟻群算法的優秀正反饋能力提出了一種改進的蟻群算法，并應用于TSP問題中，取得了很好的效果。文獻[5]通過引入遺傳算法中的雜交算子，提出了一種帶雜交算子的蟻群算法，從而有效的解決了進化過程中收斂速度慢且精度不高的問題。

2.2 蟻群算法與神經網絡

神經網絡通過模擬人的直覺思維方式進行工作，通過網絡的參數設置，達到不同的效果[6]。但是，神經網絡在有冗余屬性時，存在訓練時間長，收斂速度慢等問題。且在處理經典的旅行商問題中，容易陷入局部極小點等問題。文獻[7]通過利用蟻群算法對特征參數進行屬性約簡，從而刪除非必要屬性，然后再將結果輸入到神經網絡中訓練。通過這樣的組合，達到了簡化神經網絡處理數據的維數，提高了網絡的訓練效率，并將方法運用到柴油機的故障診斷中，取得了良好的訓練效果，最終提高了故障分類的準確性。文獻[8]提出了一種基于蟻群算法的Hopfiled神經網絡，通過引入蟻群算法，提高了神經網絡的收斂速度，且比原方法易于跳出局部最優，最后應用于多空間站的路徑規劃中。BP神經網絡作為人工神經網絡中一種應用最廣泛的多層前饋神經網絡，在實際應用中同樣存在學習效率低，易于陷入局部極小的問題。文獻[9]在分析了蟻群算法的優點之后，將蟻群算法融合入BP網絡的網絡權值訓練中，從而使蟻群神經網絡既能滿足廣泛的映射能力，又能達到快速及全局收斂的要求。

2.3 蟻群算法與粗糙集理論

粗糙集理論[10]是由波蘭數學家Pawlak Z于1982年提出的，通過引入數學中的等價關系，對特定空間進行劃分，采用這樣的方法達到利用已知的知識庫描述模糊不確定信息的目的。粗糙集理論中，屬性約簡是其核心內容，目的是導出相關決策表中的決策規則。但由于屬性組合的爆炸，找出決策表的最小約簡就成為了NP-hard問題，所以單純依賴粗糙集理論解決實際問題存在很多困難。蟻群算法作為進化算法的一種，在組合優化，路徑選擇等問題上有較強的適應性，但同時存在搜索時間長、易于停滯等問題。通過將蟻群算法與粗糙集理論結合，可以很好的解決兩種問題中各自的不足。文獻[11]在回顧了粗糙集屬性約簡方法以及蟻群算法的基礎上，提出了一種基于量子蟻群算法的粗糙集屬性約簡方法，該方法利用量子旋轉門實現螞蟻的移動，從而在螞蟻數目相同時，使搜索空間加倍。同時，充分利用了蟻群算法搜索效率高又能滿足得到最小屬性集的要求。文獻[12]在分析了蟻群算法的仿真實驗之后，發現存在多種不確定因素影響信息素的更新，為了找出各因素對算法影響的重要性，引入粗糙集理論，最后發現:螞蟻數量和信息素初始濃度的設置對蟻群算法的影響是全局性的，會影響所有節點間查找最短路徑的正確性和執行時間;而信息素的衰減與增長對蟻群算法的影響則是局部性的。文獻在得到這些結論之后，確定了蟻群算法的改進原則:當算法路徑搜索準確度不高且收斂速度慢，則應調整全局性參數，包括螞蟻數量和初始信息素濃度;當算法需要提高實時性要求，應先調整初始信息素濃度然后再調整螞蟻數量;當需要提高搜索的準確度時，應同時調整信息素更新的速度。

3 蟻群算法的硬件實現

FPGA(Field Programmable GateArrays)是一種可編程使用的信號處理器件，用戶可通過改變配置信息對其功能進行定義，以滿足設計需求。作為專用集成電路(ASIC)領域中的一種半定制電路，它與傳統數字電路系統相比，FPGA具有可編程、高集成度、高速和高可靠性等優點，通過配置器件內部的邏輯功能和輸入/輸出端口，將原來電路板級的設計放在芯片中進行，提高了電路性能，降低了印刷電路板設計的工作量和難度，有效提高了設計的靈活性和效率[13]。

文獻[14]詳細的介紹了如何利用FPGA實現蟻群算法，它采用易于FPGA實現的群體蟻群算法，設計了其中的群體生成模塊、群體更新模塊、行為模塊、評價模塊以及算法進程的控制模塊(圖1)。

其中群體模塊包括一個群矩陣Q=[qij]n×k，矩陣是由j=0列的精英螞蟻和列中的FIFO序列構成。其中每一個qij都對應了一個工作數目。行為模塊中接收群體模塊中的個體，并模仿螞蟻行為過程，當迭代結束時，評價模塊即得到本次迭代的最優解，并送入群體模塊中。行為模塊可以同時讓m個螞蟻同時工作，實現了硬件上的并行性。

由于FPGA資源的限制，在蟻群算法的選擇中，文獻沒有采取其他性能更優的算法。與用軟件實現群體蟻群算法相比，利用FPGA硬件的高速性，以及軟件的靈活性，很好的解決了傳統設計方法在高速及靈活兩者不能兼得的局面。

4 蟻群算法存在的問題和發展趨勢

4.1 存在的問題

蟻群算法的研究成果令人矚目，但作為一種較新的理論，它依然存在一些問題。

(1)對于大規模組合優化問題，算法的計算時間而且復雜。由于蟻群算法的時間復雜度是，因此在處理較大規模的組合優化問題時，運算量較大，時間較長。

(2)算法容易在某個或某些局部最優解的鄰域附近發生停滯現象，造成早熟收斂，即搜索進行到一定程度后，所有螞蟻發現的解完全一致，不能繼續對解空間進一步搜索，不利于發現全局最優解。

(3)不能較好的解決連續域問題。

(4)由于蟻群算法中螞蟻個體的運動過程的隨機性，當群體規模設置較大時，很難在較短時間內從雜亂無章的路徑中找出一條較好的路徑。

(5)信息素更新策略，路徑搜索策略和最優解保留策略都帶有經驗性，沒有經過嚴格的理論論證。因此基本蟻群算法的求解效率不高、收斂性較差、求解結果具有較大的分散性。

4.2 發展趨勢

隨著蟻群算法在工程實踐中應用的深入和系統復雜性的增加，需要處理的數據量也越來越大，這些問題的影響日益突出，使得單純一到兩種智能方法往往不能很好的解決問題。由于蟻群算法易與其他進化算法或者局部搜索算法結合。所以如何根據實際情況融合多種智能方法必將成為今后蟻群算法新的研究熱點。

目前，蟻群算法的研究大多集中在算法、模型的更新，以及軟件的開發上，所處理的數據也都是靜態的。硬件的運行速度要高于軟件，如何利用硬件的優勢，利用DSP，FPGA和PLC等硬件實現蟻群算法，并使它能夠應用于實時系統將是以后研究的一個方向。

參考文獻

[1]Colorni A，Dorigo M，Maniezzo V，et al.Distributed optimization by ant colonies [A].Proceedings of ECAL91(European Conference on Artificial Life) [C].Paris，France:1991:134～142.

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

[3]Bilchev G and Parmee I C.Searching heavily constrained design spaces[C].In Proc.of 22nd Int.Conf，Computer Aided Design 95.Yelta:Ukraine，1995:230～235.

[4]Marcin L P，Tony W.Using genetic algorithms to optimize ACS-TSP[C].Proc of 3rd Int workshop ANTS.Brussels， 2002:282～287.

[5]陳燁.帶雜交算子的蟻群算法[J].計算機工程，2001，27(12):74～76.

[6]Zurada J M.Introduction to Artificial Neural System[M]. West Publishing Company，1992.

[7]張揚，曲延濱.基于蟻群算法與神經網絡的機械故障診斷方法[J].機床與液壓，2007，35(7):241～244.

[8]金飛虎，郭琦.基于蟻群算法的Hopfield神經網絡在多空間站路徑規劃的應用研究[J].計算機應用研究，2010，27(1):51～53.

[9]汪怔江，張洪偉，雷彬.基于蟻群算法的神經網絡在企業資信評估中的應用[J].計算機應用，2007，27(12):3142～3144.

[10] Pawlak Z. Rough sets[J].International J of Computer and Information Sciences，1982，11(5):341～356.

[11]袁浩.基于量子蟻群算法的粗糙集屬性約簡方法[J].計算機工程與科學，2010，32(5):82～84.

[12]王天擎.基于粗糙集的蟻群算法不確定性分析[J].計算機工程與設計，2008，29(24):6337～6339.

[13]Slimane-Kadi， M，Brasen，D.and Saucier G.A fast-FPGA prototyping system that uses inexpensive high-performance FPIC.Proc.2nd Annual Workshop on FPGAs，Berkeley，1994:147～156.

[14]B.Scheuermann，K.So，M.Guntsch，M.Middendorf.FPGA implementation of population-based ant colony optimization[J].Applied Soft Computing，2004，4:303～322.