魏 星，李 燕

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

0 引言

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

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

1 基本蟻群算法

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

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

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

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

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

其計(jì)算公式為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

[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] 魏星,周萍.改進(jìn)型蟻群算法的語音動(dòng)態(tài)規(guī)劃研究[J].計(jì)算機(jī)仿真,2011,28(5):402-405,409.

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

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

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

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

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

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

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