魏 星，李 燕

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

0 引言

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

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

1 基本蟻群算法

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

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

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

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

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

其計算公式為：

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

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

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

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

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

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

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

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

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

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

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

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

圖1 參數(shù)ρ對算法的性能影響圖

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

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

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

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

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

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

2.4 螞蟻數(shù)量m和信息量Q的影響分析

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

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

圖2 螞蟻數(shù)量m對算法性能影響圖

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

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

3 結(jié)束語

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

[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] 劉利強,戴運桃,王麗華.蟻群算法參數(shù)優(yōu)化[J].計算機工程,2008,34(11):208-210.

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

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

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

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

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

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