蟻群算法是什么

蟻群算法是一種群智能算法，也是啟發(fā)式算法?；驹韥碓从谧匀唤缥浵佉捠车淖疃搪窂皆?。

（一）蟻群算法的由來

蟻群算法最早是由Marco Dorigo等人在1991年提出，他們在研究新型算法的過程中，發(fā)現(xiàn)蟻群在尋找食物時，通過分泌一種稱為信息素的生物激素交流覓食信息從而能快速的找到目標，據(jù)此提出了基于信息正反饋原理的蟻群算法。

蟻群算法的基本思想來源于自然界螞蟻覓食的最短路徑原理，根據(jù)昆蟲科學家的觀察，發(fā)現(xiàn)自然界的螞蟻雖然視覺不發(fā)達，但它們可以在沒有任何提示的情況下找到從食物源到巢穴的最短路徑，并在周圍環(huán)境發(fā)生變化后，自適應地搜索新的最佳路徑。

螞蟻在尋找食物源的時候，能在其走過的路徑上釋放一種叫信息素的激素，使一定范圍內(nèi)的其他螞蟻能夠察覺到。當一些路徑上通過的螞蟻越來越多時，信息素也就越來越多，螞蟻們選擇這條路徑的概率也就越高，結(jié)果導致這條路徑上的信息素又增多，螞蟻走這條路的概率又增加，生生不息。這種選擇過程被稱為螞蟻的自催化行為。對于單個螞蟻來說，它并沒有要尋找最短路徑，只是根據(jù)概率選擇；對于整個蟻群系統(tǒng)來說，它們卻達到了尋找到最優(yōu)路徑的客觀上的效果。這就是群體智能。

（二）蟻群算法能做什么

蟻群算法根據(jù)模擬螞蟻尋找食物的最短路徑行為來設計的仿生算法，因此一般而言，蟻群算法用來解決最短路徑問題，并真的在旅行商問題（TSP，一個尋找最短路徑的問題）上取得了比較好的成效。目前，也已漸漸應用到其他領域中去，在圖著色問題、車輛調(diào)度問題、集成電路設計、通訊網(wǎng)絡、數(shù)據(jù)聚類分析等方面都有所應用。

（三）蟻群算法的流程步驟

這里以TSP問題為例，算法設計的流程如下：

步驟1：對相關參數(shù)進行初始化，包括蟻群規(guī)模、信息素因子、啟發(fā)函數(shù)因子、信息素揮發(fā)因子、信息素常數(shù)、最大迭代次數(shù)等，以及將數(shù)據(jù)讀入程序，并進行預處理：比如將城市的坐標信息轉(zhuǎn)換為城市間的距離矩陣。

步驟2：隨機將螞蟻放于不同出發(fā)點，對每個螞蟻計算其下個訪問城市，直到有螞蟻訪問完所有城市。

步驟3：計算各螞蟻經(jīng)過的路徑長度Lk，記錄當前迭代次數(shù)最優(yōu)解，同時對路徑上的信息素濃度進行更新。

步驟4：判斷是否達到最大迭代次數(shù)，若否，返回步驟2；是，結(jié)束程序。

步驟5：輸出結(jié)果，并根據(jù)需要輸出尋優(yōu)過程中的相關指標，如運行時間、收斂迭代次數(shù)等。

要用到的符號說明：

?

初始時刻螞蟻被放在不同的城市，且各城市路徑上的信息素濃度為0。

由于蟻群算法涉及到的參數(shù)蠻多的，且這些參數(shù)的選擇對程序又都有一定的影響，所以選擇合適的參數(shù)組合很重要。蟻群算法有個特點就是在尋優(yōu)的過程中，帶有一定的隨機性，這種隨機性主要體現(xiàn)在出發(fā)點的選擇上。蟻群算法正是通過這個初始點的選擇將全局尋優(yōu)慢慢轉(zhuǎn)化為局部尋優(yōu)的。參數(shù)設定的關鍵就在于在“全局”和“局部”之間建立一個平衡點。

（四）蟻群算法的關鍵參數(shù)

在蟻群算法的發(fā)展中，關鍵參數(shù)的設定有一定的準則，一般來講遵循以下幾條：

盡可能在全局上搜索最優(yōu)解，保證解的最優(yōu)性；

算法盡快收斂，以節(jié)省尋優(yōu)時間；

盡量反應客觀存在的規(guī)律，以保證這類仿生算法的真實性。

蟻群算法中主要有下面幾個參數(shù)需要設定：

（下面列的是一些書上的主要結(jié)論，實驗過程就不舉例了，具體參考《MATLAB在數(shù)學建模中的應用》）

螞蟻數(shù)量：

設M表示城市數(shù)量，m表示螞蟻數(shù)量。m的數(shù)量很重要，因為m過大時，會導致搜索過的路徑上信息素變化趨于平均，這樣就不好找出好的路徑了；m過小時，易使未被搜索到的路徑信息素減小到0，這樣可能會出現(xiàn)早熟，沒找到全局最優(yōu)解。一般上，在時間等資源條件緊迫的情況下，螞蟻數(shù)設定為城市數(shù)的1.5倍較穩(wěn)妥。

信息素因子：

信息素因子反映了螞蟻在移動過程中所積累的信息量在指導蟻群搜索中的相對重要程度，其值過大，螞蟻選擇以前走過的路徑概率大，搜索隨機性減弱；值過小，等同于貪婪算法，使搜索過早陷入局部最優(yōu)。實驗發(fā)現(xiàn)，信息素因子選擇［1，4］區(qū)間，性能較好。

啟發(fā)函數(shù)因子：

啟發(fā)函數(shù)因子反映了啟發(fā)式信息在指導蟻群搜索過程中的相對重要程度，其大小反映的是蟻群尋優(yōu)過程中先驗性和確定性因素的作用強度。過大時，雖然收斂速度會加快，但容易陷入局部最優(yōu)；過小時，容易陷入隨機搜索，找不到最優(yōu)解。實驗研究發(fā)現(xiàn)，當啟發(fā)函數(shù)因子為［3，4.5］時，綜合求解性能較好。

信息素揮發(fā)因子：

信息素揮發(fā)因子表示信息素的消失水平，它的大小直接關系到蟻群算法的全局搜索能力和收斂速度。實驗發(fā)現(xiàn)，當屬于［0.2，0.5］時，綜合性能較好。

信息素常數(shù)：

這個參數(shù)為信息素強度，表示螞蟻循環(huán)一周時釋放在路徑上的信息素總量，其作用是為了充分利用有向圖上的全局信息反饋量，使算法在正反饋機制作用下以合理的演化速度搜索到全局最優(yōu)解。值越大，螞蟻在已遍歷路徑上的信息素積累越快，有助于快速收斂。實驗發(fā)現(xiàn)，當值屬于［10，1000］時，綜合性能較好。

最大迭代次數(shù)：

最大迭代次數(shù)值過小，可能導致算法還沒收斂就已結(jié)束；過大則會導致資源浪費。一般最大迭代次數(shù)可以取100到500次。一般來講，建議先取200，然后根據(jù)執(zhí)行程序查看算法收斂的軌跡來修改取值。

?