蟻群算法局部最優(yōu)解決機制的探討

收稿日期：2014－05－17

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

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

關鍵詞：正反饋； 隨機性； 輪盤選擇； TSP問題

中圖分類號：TP312文獻標識碼：A文章編號：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)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。該算法由Marco Dorigo于1992年在其博士論文中提出，具體靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。

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

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

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

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

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

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

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

2利用輪盤選擇解決隨機性

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

假設: alpha=1.0， beta=2.0；

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

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

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

那么根據(jù)公式，E、F、G點被選擇的概率值分別是：圖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)解決機制的探討智能計算機與應用第4卷

因此，E、F、G點被選擇的概率分別是：

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所示，如果螞蟻選擇向概率最大的地方前行，就應該選擇F點作為下一點。只是這樣卻會導致一個問題，就是每只螞蟻選擇的下一個點都是同一點，從而導致所有螞蟻尋找到相同的路徑，使得螞蟻喪失了搜尋新路徑的機會，算法也將陷入停滯。

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

Fig.2The ant path probability distribution

為了避免這個問題，就要使用輪盤選擇來決定下一個點，具體方法如下：

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

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

Fig.3The path probability distribution of wheel

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

圖4輪盤選擇路徑落點分布

Fig.4The roulette wheel selection path distribution

3“隨機性”代碼實現(xiàn)

研究以TSP問題為例：

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

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

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

for (int i=0;i

{

if (m_nAllowedCity［i］ == 1) //城市沒去過

{

dbTemp=dbTemp-prob［i］; //這個操作相當于轉動輪盤

if (dbTemp < 0.0) //輪盤停止轉動，記下城市編號，直接跳出循環(huán)

{nSelectedCity=i;break; }}}

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

4結束語

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

參考文獻：

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

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

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

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

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

［6］秦玲.蟻群算法的改進與應用［D］. 揚州:揚州大學， 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.