蟻群算法中參數優(yōu)化及其仿真研究

魏 星，李 燕

（桂林航天工業(yè)學院 信息工程系，桂林 541004）

0 引言

2 0世紀9 0年代初，蟻群算法由意大利學者M.DORIGO[1]等人提出。算法采用正反饋機制，易于發(fā)現較好解，并且蟻群算法具有很好的通用性和魯棒性。因此，國內外很多專家學者充分利用蟻群算法的優(yōu)點解決NP-hard問題，特別是旅行商問題、網絡路由規(guī)劃等組合優(yōu)化問題。但是，在蟻群算法中，參數值的選擇直接決定了算法的好壞，而算法中不僅參數的個體取值十分重要，并且參數之間的組合取值更是直接影響著整個算法的結果，如果參數取值不當，會導致算法陷入局部最優(yōu)等問題。

針對基本蟻群算法參數取值問題，分析算法參數的設置，提出各參數之間的最佳優(yōu)化組合方案，并進行了仿真實驗，實驗結果證明了該改進方法提高了算法的效率，對蟻群算法的應用有一定的參考意義。

1 基本蟻群算法

蟻群算法是一種智能隨機搜索算法，多用于解決離散問題，算法的解是一個從初態(tài)到終態(tài)的序列，算法得到的最優(yōu)解即為最優(yōu)狀態(tài)轉移序列。在算法中螞蟻是根據系統(tǒng)路徑上的信息素強度完成狀態(tài)轉移，蟻群中每只螞蟻進行一次路徑搜索后，都會更新一次路徑上的信息素強度，進而整個蟻群進行一次更新，隨著更新搜索過程的重復，通過各個螞蟻的相互協作，最優(yōu)路徑上的信息素強度最大，該序列即為最優(yōu)解。

蟻群算法基本模型如公式(1)所示[1]：

算法執(zhí)行時，在n個節(jié)點上隨機放置m個螞蟻，每條節(jié)點間路徑都設有一個信息素初值τij(0)，另外，為了記錄螞蟻走過的城市信息，設定Tabuk為狀態(tài)序列轉移表。算法規(guī)定，每只螞蟻根據公式(1)隨機進行狀態(tài)轉移，并且約定只能由Si轉移到某個相鄰狀態(tài)Sj。狀態(tài)轉移概率pij(t)的公式：

其中：τij(t)為兩節(jié)點i、j之間的路徑信息素，ηij(t)為節(jié)點間距離因子，α為信息素重要程度，β為啟發(fā)因子重要程度，α和β均大于0，allowedk為允許螞蟻經過的集合。

信息素更新如公式(2)所示：

其計算公式為：

其中：Q是一個常數，是螞蟻某時刻經過的路徑長度。其值越小，表明信息素強度越大，更多螞蟻會通過相互通信移動到此路徑上，最后算法得到全局最優(yōu)解。

2 算法參數的最優(yōu)選擇及實驗分析

從前文的分析不難看到，在蟻群算法中，算法性能會受到α、β、ρ、m、Q等基本參數取值的影響。但是，通過大量的數學計算和分析，參數選擇尚無嚴格的理論依據，因此，本文先采用一些文獻提出的參數[3～6]，通過逐步調整各個參數的取值，再進行一系列的仿真實驗，找到蟻群算法中最佳的參數選擇。為方便實驗數據進行比較，本文后面的仿真實驗研究都是以Oliver30城市問題為例，利用蟻群中ant cycle system模型研究參數對最優(yōu)路徑的影響。

2.1 啟發(fā)因子α和期望值啟發(fā)式因子β的影響分析

在算法中，啟發(fā)式因子α描述搜索隨機性，期望值啟發(fā)因子β表示確定性因素大小，兩個因子既相關又矛盾。α取值越大，重復搜索可能性越大，從而導致隨機性降低，α取值較小，隨機性增強，但收斂速度變慢；β取值越大，局部最短路徑選擇的可能性越大，收斂速度變快，但隨機性降低，β取值較小，算法最終陷入隨機搜索，無法找到最優(yōu)解。

因此，既要加快蟻群算法收斂速度，又要找到全局最優(yōu)解，就必須使蟻群的搜索過程具有很強的隨機性，同時具有快速的收斂能力。

在蟻群算法的實際應用中，通過實驗分析可以確定啟發(fā)式因子α及期望啟發(fā)因子β取值。實驗中的參數取值為：螞蟻循環(huán)一周所釋放的總信息量Q=400，信息素衰減因子ρ=0.7，螞蟻數m=20，循環(huán)次數N=10，表1描述了參數α、β的取值對算法性能的影響，其中：平均值表示算法運行10次的最短路徑長度的平均值；最優(yōu)值、最差值分別表示算法運行10次最短路徑中的最小值和最大值。

表1 參數α、β的取值對算法性能的影響表

通過觀察表1中的實驗結果，我們不難看出，在蟻群算法中，選取不同值的啟發(fā)因子α和β，將會對算法的搜索性能產生很大的影響。其中，當α=1，β=4時，算法取得的平均值及最優(yōu)值都是最好的。另外，我們可以看到，取值在適當的范圍內，即使選擇α和β值時有不同的參數組合，但相比較而言，實驗結果表明蟻群算法也能獲得較好的結果，并且算法的收斂速度也相當接近。在ant cycle system模型中，結合實驗結果，我們可以得出：在本文的問題中，選取α∈[1.0,3.0]，β∈[2.0,5.0]范圍時，算法性能較好。

2.2 信息素揮發(fā)因子ρ的影響分析

同前文分析一樣，算法還受到另外一個參數——信息素揮發(fā)因子（用1-ρ表示）的影響[3]。信息素揮發(fā)度的取值直接影響到算法的全局搜索能力及收斂速度，如果1-ρ取值很小，隨機性增強，但收斂速度變慢，這時算法正反饋比較弱；如果1-ρ取值較大，重復搜索可能性越大，從而導致隨機性降低，影響算法全局搜索性能。

在實驗中，參數取值為:螞蟻循環(huán)一周所釋放的總信息量Q=400，α=1，β=4，螞蟻數m=20，循環(huán)次數n=10，其中：表中平均值表示將10次運行中每次得到的最短線路長的平均值。圖1表示了信息素揮發(fā)因子ρ在不同取值下，對算法性能的影響。

圖1 參數ρ對算法的性能影響圖

從圖1中不難看出，ρ的取值對算法的結果影響較大。當ρ<0.5時，收斂速度較快，但搜索結果較差。當ρ>0.8時，搜索結果較好，但收斂時間成幾何級數增長，實用性較差。由圖1可知，取值ρ∈[0.5,0.8]，算法的的全局搜索能力較強，收斂速度較快。

2.3 α、β、ρ三種因子組合對算法性能的影響分析

前文分別對α、β、ρ三種因子取值對算法的性能影響進行了分析，但實際上蟻群算法中各參數α、β、ρ的作用是緊密耦合的, 單個參數最優(yōu)，但將其組合起來未必會取得好的效果。如果α、β、ρ的參數取值不合適，會導致算法求解速度很慢，并且解的質量很差。下面我們就α、β、ρ三種因子的組合進行實驗研究，以達到最佳組合配置。

根據前文是實驗分析，就本文研究而言，α、β、ρ三種因子的最佳取值范圍分別為：α∈[1.0,3.0]，β∈[2.0,5.0]，ρ∈[0.5,0.8]，因此，我們的實驗數據取值就在此范圍內進行微調，以達到理想的數值。實驗仍以Oliver 30城市問題為例，有關算法參數為：螞蟻循環(huán)一周所釋放的總信息量Q=400，螞蟻數m=20，循環(huán)次數n=10，實驗結果如表2所示。

表2 參數α、β、ρ組合對算法性能的影響

從表2可以看出，三個參數的取值都不收斂到某個具體的數值，這是由于蟻群算法屬于隨機搜索算法，因此得到的結果也是隨機的，所以不可能產生收斂的結果。另外，根據表2中數據，我們可以確定在本文的實驗中，最佳的三個參數組合為實驗組次中的第3組，即：α=1.5，β=4.1，ρ=0.64，這時，算法的最優(yōu)值和平均值也是最好的。

2.4 螞蟻數量m和信息量Q的影響分析

在算法中，兩個參數——螞蟻數量m和信息量Q對算法性能也有影響。

對于蟻群數量m對算法性能的影響，也可以通過實驗來進行詳細的分析。在實驗中，我們選取有關參數為：螞蟻循環(huán)一周所釋放的總信息量Q=400，信息啟發(fā)式因子α=1.5，期望啟發(fā)式因子β=4.1，信息素殘留常數ρ=0.64，蟻群計算中，如果相鄰兩次搜索的最優(yōu)解誤差小于0.001[5]，算法停止。螞蟻數量選取集合為：m∈{5,10,15,20,25,30}。實驗結果如圖2所示。

圖2 螞蟻數量m對算法性能影響圖

由圖2可見，螞蟻數量對蟻群算法收斂性能的影響基本呈線性規(guī)律，當螞蟻數量m=30時，模型可以在較少的迭代次數內找到一個最佳的最優(yōu)解。所以，在蟻群算法中，螞蟻數量m過大，雖然搜索更加穩(wěn)定，也提高了全局性，但是減慢了算法收斂速度；而螞蟻數量m過小，隨機性減弱，全局性能下降，路徑上的信息量逐漸減小，最后趨于0，最終算法容易出現過早停滯的現象。所以，通過仿真實驗驗證，m的取值為[ ,2]n n 的一個整數時，算法性能較好。

另外，總信息量Q是螞蟻循環(huán)一周后，釋放在其經過路徑上的信息素總和。Q越大，算法的收斂速度越快。但是，當Q特別大時（Q>2000），此時算法容易陷于局部最優(yōu)解，算法的性能下降。因此，在實際應用中，我們一般取Q<2000，此時，算法既有較快的收斂速度，性能也較好。

3 結束語

本文在研究基本蟻群算法模型的基礎上，通過一系列仿真數值實驗，利用大量的數據分析了算法中α、β、ρ、m和Q等參數的不同取值對算法性能的影響。通過仿真實驗驗證，提出了最優(yōu)參數組合方法，對于大多數蟻群優(yōu)化問題而言，本文提出的參數優(yōu)化方法都能使算法快速、有效地找到全局最優(yōu)解，提高了算法的效率，對蟻群算法的應用有一定的參考價值。

[1] Dorigo M, Maniezzo Vittorio, Colorni Alberto. The Ant System: Optimization by a colony of cooperating agents.IEEE Transactions on Systems[J].Man, and Cybernetics-Part B,1996,26(1):1-13.

[2] 魏星,周萍.改進型蟻群算法的語音動態(tài)規(guī)劃研究[J].計算機仿真,2011,28(5):402-405,409.

[3] 劉利強,戴運桃,王麗華.蟻群算法參數優(yōu)化[J].計算機工程,2008,34(11):208-210.

[4] 詹士昌,徐婕,吳俊.蟻群算法中有關算法參數的最優(yōu)選擇[J].科技通報,2003,19(5):381-386.

[5] 甘屹,李勝.蟻群算法的參數優(yōu)化配置研究[J].制造業(yè)自動化,2011,33(3):66-69.

[6] 劉偉.蟻群算法中求解參數最優(yōu)選擇分析[J].電腦與信息技術,2011,19(1):10-12, 66.

[7] 王娟,鞏建平,馮蕾潔.一種改進的遺傳蟻群混合算法[J].制造業(yè)自動化,2014,36(2):79-80.

[8] 陳志雄,潘耘,李嫣,李晉凱.用改進蟻群算法求解無線傳感器網絡多sink節(jié)點關聯問題[J].計算機應用與軟件,2012,29(2):246-249.

[9] 田鈞.基于改進蟻群算法的物流配送應用研究[J].制造業(yè)自動化,2013,35(8):88- 90,109.