一種融合加權(quán)策略及分布估計(jì)的蟻群優(yōu)化算法

蔣社想

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 安徽淮南 232001)

一種融合加權(quán)策略及分布估計(jì)的蟻群優(yōu)化算法

蔣社想

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 安徽淮南 232001)

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

無(wú)線傳感網(wǎng)絡(luò); 蟻群算法;分布估算算法

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

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

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

在算法開(kāi)始,問(wèn)題空間中所有邊上的信息素都被賦值為τ0,τ0的選值很關(guān)鍵，如果太小，算法容易過(guò)早結(jié)束，即陷入局部最優(yōu)的路徑上，反之，如果太大，信息素對(duì)搜索方向的指導(dǎo)作用太低，消耗的時(shí)間過(guò)長(zhǎng)。

對(duì)于解決組合優(yōu)化、網(wǎng)絡(luò)路由、路徑規(guī)劃等問(wèn)題，由于蟻群算法具有正反饋、并行計(jì)算、強(qiáng)魯棒性等特點(diǎn)。而且相比遺傳算法，保留了基于種群的全局搜索策略，避免了復(fù)雜的遺傳操作，是一種更高效的搜索算法，但蟻群算法也存在一些缺點(diǎn)，如收斂速度慢、易陷入局部最優(yōu)等問(wèn)題。

一、融合加權(quán)策略提高收斂速度

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

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

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

二、融合分布估計(jì)避免陷入局部最優(yōu)

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

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

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

3.當(dāng)螞蟻選擇下一條路徑時(shí)，要根據(jù)Pijk(t)對(duì)各條邊上的概率分布因子進(jìn)行評(píng)估。

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

其中P(i,j)為邊(i,j)被訪問(wèn)的次數(shù)，其更新規(guī)則為：P(i,j)=P(i,j)+△P(i,j), △P(i,j)為的取值為0或1，當(dāng)(i,j)邊被訪問(wèn)過(guò)為1，否則為0。

對(duì)于信息素的更新規(guī)則也與基本蟻群算法不同，這里只有最優(yōu)路徑上的螞蟻才能更新信息素。

隨著迭代的進(jìn)行，分布在最優(yōu)路徑上的信息素濃度越來(lái)越高，而此路徑被后續(xù)來(lái)的螞蟻選擇的機(jī)會(huì)也就更高，在這個(gè)運(yùn)行過(guò)程，概率的分布與信息素共同引導(dǎo)螞蟻向最優(yōu)路徑集中，這樣反復(fù)運(yùn)行下去最終找到最優(yōu)路徑，避免算法過(guò)早收斂，而陷入局部最優(yōu)。

三、仿真實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)算法的性能，在具有Pentium(R)4 CPU3.00GHz 、2GB內(nèi)存、Windows7操作系統(tǒng)平臺(tái)上，算法采用C語(yǔ)言編寫(xiě)，測(cè)試用例為T(mén)SPLIB中的Eil51TSP，分別進(jìn)行基本蟻群算法和本文的改進(jìn)蟻群算法兩組實(shí)驗(yàn)。選取的參數(shù)為：α=1、β=2，ρ=0.1，設(shè)算法最大迭代次數(shù)為1000,根據(jù)TSPLIB給出的數(shù)據(jù)，測(cè)試用例的最優(yōu)路徑長(zhǎng)度為426，通過(guò)實(shí)驗(yàn)報(bào)告發(fā)現(xiàn)兩個(gè)算法都得到了正確結(jié)果，但改進(jìn)算法的五次實(shí)驗(yàn)平均最優(yōu)解為429.8，而基本蟻群算法五次實(shí)驗(yàn)平均最優(yōu)解為431.8，這說(shuō)明改進(jìn)算法的穩(wěn)定性較好。另外從實(shí)驗(yàn)結(jié)果可以看出基本的蟻群算法查找最優(yōu)路徑平均耗費(fèi)時(shí)間為1.658s，而改進(jìn)的算法只用了1.235s,這說(shuō)明對(duì)算法的改進(jìn)加快了收斂速度。

四、總結(jié)

本文提出一種新的蟻群算法優(yōu)化，首先利用加權(quán)策略改進(jìn)算法信息素更新，增強(qiáng)了最優(yōu)路徑的導(dǎo)向性，加快了收斂速度。之后將分布估計(jì)思想融合到算法中，避免了算法過(guò)早收斂而陷入局部最優(yōu)，仿真實(shí)驗(yàn)表明該算法改進(jìn)有一定的可行性。

[1]段海濱.蟻群算法原理及應(yīng)用[M].北京:科學(xué)社會(huì)出版社,2005．

[2]王結(jié)太,許家棟等. 基于蟻群優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].系統(tǒng)仿真學(xué)報(bào),2008,20(18):4898～4901.

[3]江海峰.無(wú)線傳感器網(wǎng)絡(luò)能量?jī)?yōu)化路由算法研究[D].徐州:中國(guó)礦業(yè)大學(xué),2010.

[4]孫勇,李妮,龔光紅,韓亮.基于知識(shí)庫(kù)的動(dòng)態(tài)蟻群算法[J].北京工業(yè)大學(xué)學(xué)報(bào),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

［責(zé)任編輯：周 天］

蔣社想(1981-)，男，安徽碭山人，碩士，講師，研究方向：物聯(lián)網(wǎng)技術(shù)、云計(jì)算技術(shù)等。

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