一種融合加權策略及分布估計的蟻群優化算法

蔣社想

(安徽理工大學計算機科學與工程學院 安徽淮南 232001)

一種融合加權策略及分布估計的蟻群優化算法

蔣社想

(安徽理工大學計算機科學與工程學院 安徽淮南 232001)

通過對蟻群算法、加權策略、分布估算算法等進行研究和分析，首先提出將加權策略應用于蟻群算法的信息素更新，有效地提高了算法的全局收斂速度，然后將蟻群算法與分布估算算法進行融合，從而避免了由于信息素的正反饋機制而陷入局部最優的問題，仿真實驗表明該算法在收斂速度及最優路徑求解方面有較好的改進。

無線傳感網絡; 蟻群算法;分布估算算法

蟻群算法(Ant Colony Optimization, ACO)，是20世紀90年代意大利學者Marco Dorigo等人提出來的算法，是一種用于優化領域的算法，其基本原理與生物界中螞蟻的群體行為相似。每只螞蟻在覓食過程中都會在其經過的路徑上釋放一種分泌物─信息素(pheromone)，同時它也能夠識別環境中其它螞蟻釋放的信息素，信息素具有自揮發特性，隨著時間的增加以及經過的螞蟻越少信息素濃度就越低，反之濃度就越高，這樣就形成了一個正反饋機制。下面以TSP為例說明蟻群算法的基本模型。

首先將m只螞蟻隨機放置在n個城市，螞蟻k(k=1,2，…,m)根據各個城市間連接路徑上的信息素濃度決定其下一個訪問城市，設Pijk(t)表示t時刻螞蟻k從城市i轉移到城市j的概率，其計算公式為：

其中，Jk(i)表示從城市i可以直接到達的且又不在螞蟻訪問過的城市序列Rk中的城市集合，η(i,j)是一個啟發式信息，通常由η(i,j)=1/ dij直接計算,τ(i,j)表示邊(i,j)上的信息素量, 信息更新公式為：

在算法開始,問題空間中所有邊上的信息素都被賦值為τ0,τ0的選值很關鍵，如果太小，算法容易過早結束，即陷入局部最優的路徑上，反之，如果太大，信息素對搜索方向的指導作用太低，消耗的時間過長。

對于解決組合優化、網絡路由、路徑規劃等問題，由于蟻群算法具有正反饋、并行計算、強魯棒性等特點。而且相比遺傳算法，保留了基于種群的全局搜索策略，避免了復雜的遺傳操作，是一種更高效的搜索算法，但蟻群算法也存在一些缺點，如收斂速度慢、易陷入局部最優等問題。

一、融合加權策略提高收斂速度

在使用蟻群算法解決TSP問題時，路徑上的信息素和啟發式信息決定著螞蟻的前進方向，公式(1)中的Pijk(t)表示t時刻螞蟻k從城市i轉移到城市j的概率，公式(1)中的α和β是兩個預設值的參數，分別表示啟發式信息和信息素濃度的影響因子，如果α值為0時，算法將會演變成貪婪算法，如果β的值為0時，算法將快速收斂，但往往會陷入局部最優。因此蟻群算法的收斂狀況與信息素有很大關系。

在基本蟻群算法中，信息素的更新主要采用迭代最優更新規則和至今最優更新規則，如果采用迭代最優更新規則，△τij的值為1/Cbs, Cbs表示至今最優的路徑長度，如果采用至今最優更新規則，△τij的值為1/Cib,Cib表示當前迭代最優路徑長度，根據算法模型能夠發現，這兩個規則某一程度上都會影響到算法的貪心度，至今最優更新規則會加快算法收斂速度，迭代最優更新規則會有更多路徑獲取信息素。為了彌補兩種策略的確定，本文在迭代最優更新規則中引入一參數γ，主要對每次信息素濃度改變量進行加權，以增加迭代算法中最優路徑的導向性，從而加快算法的收斂速度。修改后的△τij值為1/γCib，γ的計算公式為：

式中Cib(kit)表示算法當前迭代的最優路徑長度，Cib(kit-1)為上一次迭代的最優路徑長度。算法每次迭代將會比較Cib(kit)和Cib(kit-1)的值，如果Cib(kit)＞Cib(kit-1),說明當前迭代構成的最優路徑不是最優的，此時γ＞1，△τij減小，信息素釋放量也就減小；反之，如果Cib(kit)＜ Cib(kit-1)，則說明當前迭代生成的路徑優于前次迭代，那么義γ＜1, △τij增加，釋放的信息素也就增多，螞蟻選擇此條路徑的概率增加，從而加快了算法的收斂速度。

二、融合分布估計避免陷入局部最優

分布估算算法(EDAs)，是從概率統計學角度出發，在進化算法中加入構造性模型，形成一種基于概率分析的新型算法。蟻群算法基本思想是通過不斷更新全局和局部信息量來搜尋最優路徑，而分布估算算法主要思想是通過問題解空間中個體分布的概率來求解。本文將蟻群算法融合分布估算算法，可以有效地解決蟻群算法過早收斂而陷入局部最優問題，其改進如下：

1.在搜索路徑的各個邊增加概率分布因子;

2.在信息素更新規則中考慮最優路徑上各條邊的概率分布因子；

3.當螞蟻選擇下一條路徑時，要根據Pijk(t)對各條邊上的概率分布因子進行評估。

根據以上改進，Pijk(t)的計算公式將改為：

其中P(i,j)為邊(i,j)被訪問的次數，其更新規則為：P(i,j)=P(i,j)+△P(i,j), △P(i,j)為的取值為0或1，當(i,j)邊被訪問過為1，否則為0。

對于信息素的更新規則也與基本蟻群算法不同，這里只有最優路徑上的螞蟻才能更新信息素。

隨著迭代的進行，分布在最優路徑上的信息素濃度越來越高，而此路徑被后續來的螞蟻選擇的機會也就更高，在這個運行過程，概率的分布與信息素共同引導螞蟻向最優路徑集中，這樣反復運行下去最終找到最優路徑，避免算法過早收斂，而陷入局部最優。

三、仿真實驗

為了驗證改進算法的性能，在具有Pentium(R)4 CPU3.00GHz 、2GB內存、Windows7操作系統平臺上，算法采用C語言編寫，測試用例為TSPLIB中的Eil51TSP，分別進行基本蟻群算法和本文的改進蟻群算法兩組實驗。選取的參數為：α=1、β=2，ρ=0.1，設算法最大迭代次數為1000,根據TSPLIB給出的數據，測試用例的最優路徑長度為426，通過實驗報告發現兩個算法都得到了正確結果，但改進算法的五次實驗平均最優解為429.8，而基本蟻群算法五次實驗平均最優解為431.8，這說明改進算法的穩定性較好。另外從實驗結果可以看出基本的蟻群算法查找最優路徑平均耗費時間為1.658s，而改進的算法只用了1.235s,這說明對算法的改進加快了收斂速度。

四、總結

本文提出一種新的蟻群算法優化，首先利用加權策略改進算法信息素更新，增強了最優路徑的導向性，加快了收斂速度。之后將分布估計思想融合到算法中，避免了算法過早收斂而陷入局部最優，仿真實驗表明該算法改進有一定的可行性。

[1]段海濱.蟻群算法原理及應用[M].北京:科學社會出版社,2005．

[2]王結太,許家棟等. 基于蟻群優化算法的無線傳感器網絡路由協議[J].系統仿真學報,2008,20(18):4898～4901.

[3]江海峰.無線傳感器網絡能量優化路由算法研究[D].徐州:中國礦業大學,2010.

[4]孫勇,李妮,龔光紅,韓亮.基于知識庫的動態蟻群算法[J].北京工業大學學報,2012,38(3):374-380.

A weighted fusion strategy and distribution estimation of ant colony optimization algorithm

Jiang She-xiang
(Anhui University of Science and Technology, Computer Science and Engineering College, Huainan Anhui, 232001, China)

This paper studies and analyzes the ant colony algorithm, the weighted strategy, distribution estimation algorithm, first proposed updating weighted strategy applied to the pheromone of ant colony algorithm, effectively improve the global convergence of the algorithm, and then the fusion estimation algorithm, ant colony algorithm and distribution of avoiding the due to the positive feedback mechanism of pheromones into local optimal problem, the simulation experiments show that the algorithm in convergence speed and the optimal path has better improvement.

wireless sensor network; ant colony algorithm; distribution estimation algorithm

G642.0

A

1000-9795(2014)012-000166-02

［責任編輯：周 天］

蔣社想(1981-)，男，安徽碭山人，碩士，講師，研究方向：物聯網技術、云計算技術等。

2013年安徽理工大學青年教師科學研究基金資助項目(QN201322)