收稿日期：2014－05－17

作者簡(jiǎn)介：姜文波(1962-)，男，黑龍江齊齊哈爾人，學(xué)士，講師，主要研究方向: 計(jì)算機(jī)軟件教學(xué)與研究、算法分析。

摘要：?jiǎn)l(fā)式蟻群算法是模擬螞蟻群體覓食行為的一種仿生智能優(yōu)化算法。該算法集結(jié)了多種仿生智能算法的優(yōu)點(diǎn)，解決了許多復(fù)雜優(yōu)化問(wèn)題，比如著名的旅行商（TSP）問(wèn)題，但啟發(fā)式蟻群算法無(wú)法避免陷入局部最優(yōu)的尋優(yōu)困境。介紹了蟻群算法的工作原理，針對(duì)蟻群算法容易陷入局部最優(yōu)的特點(diǎn)，提出通過(guò)輪盤(pán)選擇來(lái)解決求解的隨機(jī)性，從而避免陷入局部最優(yōu)的解決機(jī)制。

關(guān)鍵詞：正反饋； 隨機(jī)性； 輪盤(pán)選擇； TSP問(wèn)題

中圖分類(lèi)號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2014）03-0053-03

To Investigate the Mechanism of Ant

Colony Algorithm to Solve the Local Optimal

JIANG Wenbo

(Haikou College of Economics， Hai Kou 571127，China)

Abstract：Heuristic ant colony algorithm is a bionic intelligent optimization algorithm of ant colony foraging behavior， this algorithm brings advantages of various intelligent bionic algorithm， for solving many complex optimization problems， such as the famous traveling salesman problem (TSP)， but the heuristic ant colony algorithm can not avoid falling into local optimization problems. This paper introduces the working principle of ant colony algorithm， aiming at the characteristics of ant colony algorithm easy to fall into local optimum， presents using the roulette wheel selection to solve the stochastic solution， so as to avoid falling into local optimal solution mechanism.

Key words：Positive Feedback; Random; Roulette Wheel Selection; TSP Problem

0引言

蟻群算法(ant colony optimization， ACO)，又稱(chēng)螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。該算法由Marco Dorigo于1992年在其博士論文中提出，具體靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。

目前，針對(duì)蟻群算法的模型改進(jìn)、理論分析、并行實(shí)現(xiàn)、硬件實(shí)現(xiàn)、智能融合等方面研究［1］，已逐漸引起了眾多學(xué)者們的廣泛關(guān)注，其中的研究焦點(diǎn)之一就是如何解決蟻群算法較強(qiáng)正反饋性帶來(lái)的局部尋優(yōu)結(jié)果，本文也即基于該課題而展開(kāi)相應(yīng)的探討和研究。

1局部最優(yōu)避免原則

簡(jiǎn)單來(lái)說(shuō)，避免陷入局部最優(yōu)的方法就是隨機(jī)。在具體實(shí)現(xiàn)手段上，可以根據(jù)所采用的啟發(fā)式框架來(lái)靈活加入隨機(jī)性，而引入路徑隨機(jī)性可以形成帶有正反饋的隨機(jī)搜索算法［2］，實(shí)際原則如下:

(1)越隨機(jī)越好。沒(méi)有隨機(jī)性，一定會(huì)陷入局部最優(yōu)。為了獲得找到最優(yōu)解的更大期望值，算法中一定要有足夠的隨機(jī)性。具體體現(xiàn)為魯棒性較好，搜索時(shí)多樣性較好。算法的每一步選擇都可以考慮加入隨機(jī)性，但要控制一定的概率。比如，某個(gè)貪心策略下，是以概率1進(jìn)行某一動(dòng)作，現(xiàn)在則可考慮將其改為以概率0.999 9做之前的操作，而以剩余概率實(shí)現(xiàn)其他操作。具體參數(shù)設(shè)置需經(jīng)多次調(diào)試才能完成［3］。

(2)越不隨機(jī)越好。隨機(jī)性往往是對(duì)問(wèn)題內(nèi)在規(guī)律的一種變相利用，即在沒(méi)有找到其內(nèi)在規(guī)律的情況下，為了獲得更好的多樣性，可選擇加入隨機(jī)的策略。當(dāng)然，對(duì)給定問(wèn)題的深入研究才是解決的根本，也就是要分辨出哪些時(shí)候，某個(gè)動(dòng)作就是客觀上能?chē)?yán)格保證最優(yōu)的，而這一點(diǎn)將直接決定了算法性能。

(3)二者平衡最好。通常情況下，做好第一點(diǎn)，可以略微改善算法性能；做好第二點(diǎn)，則有可能給算法帶來(lái)質(zhì)的提高。但二者間調(diào)和后的平衡則會(huì)帶來(lái)綜合性的飛躍［4］。

綜上所述，只有在隨機(jī)和不隨機(jī)之間做好調(diào)和功夫，并且相應(yīng)地把握兩者之間的平衡，才能使算法最終獲得出色的性能［5］。

2利用輪盤(pán)選擇解決隨機(jī)性

輪盤(pán)選擇如圖1所示。假設(shè)螞蟻在D點(diǎn)，ABC為已經(jīng)去過(guò)的點(diǎn)，EFG為還未去過(guò)的點(diǎn)，現(xiàn)在螞蟻要在EFG中選擇一個(gè)點(diǎn)作為下一步要到達(dá)的點(diǎn)。

假設(shè): alpha=1.0， beta=2.0；

DE間信息素為2，DE間距離為2；

DF間信息素為5，DF間距離為2；

DG間信息素為3，DG間距離為3。

那么根據(jù)公式，E、F、G點(diǎn)被選擇的概率值分別是：圖1螞蟻路徑分布走向

Fig.1The ant path distribution trend

pro_E=2/(2*2)=0.5；

pro_F=5/(2*2)=1.25；

pro_G=3/(3*3)=0.333 3。

這樣，總的概率pro_total=pro_E+pro_F+pro_G=0.5+1.25+0.333=2.083。第3期姜文波：蟻群算法局部最優(yōu)解決機(jī)制的探討智能計(jì)算機(jī)與應(yīng)用第4卷

因此，E、F、G點(diǎn)被選擇的概率分別是：

pE=pro_E/pro_total=0.5/2.083=24%；

pF=pro_F/pro_total=1.2 5/2.083=60%；

pG=pro_G/pro_total=0.333/2.083=16%。

如圖2所示，如果螞蟻選擇向概率最大的地方前行，就應(yīng)該選擇F點(diǎn)作為下一點(diǎn)。只是這樣卻會(huì)導(dǎo)致一個(gè)問(wèn)題，就是每只螞蟻選擇的下一個(gè)點(diǎn)都是同一點(diǎn)，從而導(dǎo)致所有螞蟻尋找到相同的路徑，使得螞蟻喪失了搜尋新路徑的機(jī)會(huì)，算法也將陷入停滯。

圖2螞蟻路徑走向概率分布

Fig.2The ant path probability distribution

為了避免這個(gè)問(wèn)題，就要使用輪盤(pán)選擇來(lái)決定下一個(gè)點(diǎn)，具體方法如下：

在［0，1］之間取一個(gè)隨機(jī)數(shù)R，用R減pE，如果減去后的結(jié)果小于等于0就選取E作為下一個(gè)點(diǎn)，如果減去后還大于0，就繼續(xù)再減去pF，…，直到減去后的結(jié)果小于等于0，此時(shí)即用最后減去時(shí)的那個(gè)概率值對(duì)應(yīng)的點(diǎn)作為下一個(gè)點(diǎn)。

如圖3所示，假設(shè)［0，1］之間取得的隨機(jī)數(shù)字是0.9，則藍(lán)色的小箭頭就順時(shí)針旋轉(zhuǎn)0.9圈，可以看到藍(lán)色的小箭頭落在了G所在的扇區(qū)里，因此螞蟻就選擇G作為下一個(gè)點(diǎn)。圖3路徑走向概率輪盤(pán)分布

Fig.3The path probability distribution of wheel

而從圖4中看出，在［0，1］之間取一個(gè)隨機(jī)數(shù)，這個(gè)數(shù)字落在F區(qū)間內(nèi)的可能性最大，E次之，G最小?？梢钥闯鍪褂幂啽P(pán)選擇螞蟻向概率值大的區(qū)間行走的可能性也大，但卻也存在向概率小的地方行走的可能，這樣就可使螞蟻探索新的路徑，從而避免算法停滯或者進(jìn)入局部最優(yōu)解［6］。

圖4輪盤(pán)選擇路徑落點(diǎn)分布

Fig.4The roulette wheel selection path distribution

3“隨機(jī)性”代碼實(shí)現(xiàn)

研究以TSP問(wèn)題為例：

在使用蟻群算法解決該問(wèn)題時(shí)，需要假設(shè)prob［i］表示第i個(gè)城市被選中的概率；dbTotal表示所有城市被選中概率的累積和；N_CITY_COUNT表示城市總量；m_nAllowedCity［i］=1表示該城市沒(méi)去過(guò)。

具體的代碼實(shí)現(xiàn)為：

dbTemp=rnd(0.0，dbTotal); //取一個(gè)隨機(jī)數(shù)

for (int i=0;i

{

if (m_nAllowedCity［i］ == 1) //城市沒(méi)去過(guò)

{

dbTemp=dbTemp-prob［i］; //這個(gè)操作相當(dāng)于轉(zhuǎn)動(dòng)輪盤(pán)

if (dbTemp < 0.0) //輪盤(pán)停止轉(zhuǎn)動(dòng)，記下城市編號(hào)，直接跳出循環(huán)

{nSelectedCity=i;break; }}}

這種算法是將隨機(jī)產(chǎn)生的值dbTemp依次對(duì)每個(gè)城市被選中的概率做減法，減到第i個(gè)城市即相當(dāng)于隨機(jī)值處在第i-1個(gè)城市和第i個(gè)城市之間。假設(shè)隨機(jī)值的產(chǎn)生是沒(méi)有任何規(guī)律的，那么被選中概率大的城市，即該城市與上一個(gè)城市之間的累積和也較大，隨之被命中的概率也就較大。形象地解釋就是，這個(gè)選擇過(guò)程就相當(dāng)于轉(zhuǎn)動(dòng)一個(gè)有刻度的輪盤(pán)，雖然是隨機(jī)的，但卻也考慮到了其中每一塊的命中概率問(wèn)題［7］。

4結(jié)束語(yǔ)

蟻群算法是一種具有很強(qiáng)正反饋特點(diǎn)的算法，正是因?yàn)檫@一能力，使得蟻群算法陷入局部最優(yōu)的困境。本文探討了利用輪盤(pán)選擇使得蟻群算法成為帶有正反饋的隨機(jī)搜索算法，其隨機(jī)性和正反饋即是算法的核心，二者相輔相成，缺一不可。故而可以利用輪盤(pán)選擇機(jī)制來(lái)解決蟻群算法局部最優(yōu)的問(wèn)題。

參考文獻(xiàn)：

［1］段海濱，王道波，等.蟻群算法的研究現(xiàn)狀及其展望［J］. 中國(guó)工程科學(xué)，2007，9(2).

［2］段海濱.蟻群算法原理及其應(yīng)用［M］. 北京: 科學(xué)出版社， 2005-12.

［3］陳寶林.最優(yōu)化理論與算法(第2版)［M］. 北京:清華大學(xué)出版社， 2005(10):75-130.

［4］孫燾，王秀坤，劉業(yè)欣，等. 一種簡(jiǎn)單螞蟻算法及其收斂性分析［J］.小型微型計(jì)算機(jī)系統(tǒng)，2003，21( 8) : 1524-1526.

［5］丁建立，陳增強(qiáng)，袁著祉. 遺傳算法與螞蟻算法融合的馬爾可夫收斂性分析［J］.自動(dòng)化學(xué)報(bào)， 2004，30( 4) : 634-659.

［6］秦玲.蟻群算法的改進(jìn)與應(yīng)用［D］. 揚(yáng)州:揚(yáng)州大學(xué)， 2004.

［7］YOO J H， LA R J， MAKOWSKI A M. Convergence results for ant routing ［R］.Technical Report CSHCN 2003 - 46，Institute for Systems Research， University of Maryland，College Park (MD) ， 2003.