基于信息素更新和揮發(fā)因子調(diào)整的改進(jìn)蟻群算法

孟曉琳，黃天民，陳尚云

(西南交通大學(xué) 數(shù)學(xué)學(xué)院，四川 成都 611756)

0 引 言

20 世紀(jì)90年代，學(xué)者M(jìn)acro Dorigo 首先提出了蟻群算法，其迅速成為啟發(fā)式算法研究的熱點(diǎn)，它在解決傳統(tǒng)算法無(wú)法解決的組合優(yōu)化和NP 等難題上能夠取得很好的效果，并且具有解決復(fù)雜問題的能力.同時(shí)，蟻群算法的魯棒性較強(qiáng)，能進(jìn)行分布式計(jì)算，同其他優(yōu)化算法結(jié)合容易，而且算法沒有復(fù)雜的數(shù)學(xué)操作，對(duì)軟硬件要求不高，但是該算法搜索時(shí)間較長(zhǎng)，很容易陷入局部最優(yōu)解［1－2］.為了克服蟻群算法的缺點(diǎn)，許多學(xué)者對(duì)其進(jìn)行了研究，并提出了相應(yīng)的改進(jìn)算法［3－6］.在此基礎(chǔ)上，本研究提出一種將信息素局部更新和全局更新相結(jié)合，并對(duì)揮發(fā)因子ρ進(jìn)行分段設(shè)置，以此來(lái)增強(qiáng)蟻群算法的全局搜索能力，并采用TSP 實(shí)例對(duì)算法進(jìn)行驗(yàn)證，證明了本改進(jìn)算法的有效性.

1 蟻群算法的基本原理

設(shè)m 表示螞蟻的數(shù)量，dij(i，j = 1，2，…，n)表示城市i、j 之間的距離，bi(t)表示t 時(shí)刻位于城市i的螞蟻個(gè)數(shù)，則，表示t 時(shí)刻在i和j 連線上殘留的信息素，初始時(shí)刻，各路徑上的信息素濃度相等，設(shè)τij(0)= C，C 為常數(shù).

在搜索過程中，每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移概率來(lái)判斷路徑的選擇，t 時(shí)刻螞蟻k 由城市i 到j(luò) 的狀態(tài)轉(zhuǎn)移概率用來(lái)表示，

每只螞蟻對(duì)路徑做出選擇后將移動(dòng)至下一城市，并且將當(dāng)前螞蟻所在城市放入禁忌表tab uk中，當(dāng)禁忌表包含所有城市時(shí)，表示已經(jīng)完成一次迭代，計(jì)算每只螞蟻所走的路徑并保留最短路徑.

路徑上的信息素會(huì)隨著時(shí)間的推移而漸漸減弱，經(jīng)過n 個(gè)時(shí)刻，路徑ij 的信息素將按照式(2)進(jìn)行更新，式中，ρ 表示信息素?fù)]發(fā)因子，Δτij(t)表示本次迭代中路徑ij 上的信息素增量，表示第k 只螞蟻在本次迭代中留在路徑ij 上的信息素，其表達(dá)式為，

式中，Q 表示常數(shù)，Lk表示第k 只螞蟻在本次迭代中走過的路徑長(zhǎng)度［4］.

2 蟻群算法的改進(jìn)

本研究對(duì)基本蟻群算法做了2 點(diǎn)改進(jìn):其一，針對(duì)基本蟻群算法容易出現(xiàn)早熟和停滯現(xiàn)象，進(jìn)行了信息素更新的改進(jìn);其二，為了使算法的全局搜索能力和收斂速度均得到提高，進(jìn)行了信息素?fù)]發(fā)因子的改進(jìn).

2.1 信息素的局部更新與全局更新

在基本蟻群算法中，信息素的更新方式有可能導(dǎo)致這樣的現(xiàn)象:新的最優(yōu)路徑尚未出現(xiàn)時(shí)，當(dāng)前最優(yōu)路徑上的信息素就會(huì)按照信息素更新公式不斷增多.這使得當(dāng)前最優(yōu)路徑上的信息素可能會(huì)因?yàn)檫^度增多而大于新的最優(yōu)路徑上信息素，最終導(dǎo)致算法停滯.對(duì)此，本研究提出一種局部更新和全局更新信息素結(jié)合的方法，其思路是:

對(duì)于第k 只螞蟻，它每經(jīng)過一條路徑ij，設(shè)經(jīng)過該路徑的時(shí)間為n，則在時(shí)刻t + n，該路徑上的信息素會(huì)用式(4)進(jìn)行更新.

式中，ρ 為信息素?fù)]發(fā)因子;τij(0)為信息素初始值.當(dāng)螞蟻k 經(jīng)過(i，j)時(shí)，式(4)就會(huì)減小該路徑上的信息素，降低其他螞蟻選中該路徑的概率，增加探索其他邊的機(jī)會(huì).相較于基本蟻群算法，此改進(jìn)可以避免因某一路徑信息素累計(jì)量過大而導(dǎo)致算法停滯.

同時(shí)，每次迭代結(jié)束以后，對(duì)于當(dāng)前最優(yōu)路徑上的信息素用式(5)進(jìn)行全局動(dòng)態(tài)更新，

中華民族五千年的發(fā)展和奮斗史使我們清楚的明白，一個(gè)民族的物質(zhì)財(cái)富只是民族財(cái)富的外在形式，而真正起決定作用、內(nèi)在的財(cái)富是這個(gè)民族的文化，它發(fā)揮著巨大的精神作用。文化強(qiáng)則國(guó)強(qiáng)，精神富則國(guó)富。引進(jìn)劇是外來(lái)文化中獨(dú)樹一幟的新生力量，是我們接收外來(lái)文化的一種新的發(fā)展趨勢(shì)，我們應(yīng)該認(rèn)真對(duì)待，使引進(jìn)劇在馬克思主義哲學(xué)的事業(yè)下符合21世紀(jì)的東方與西方文化建設(shè)的方向，在物質(zhì)生活飛速發(fā)展的形勢(shì)下增強(qiáng)人民精神世界的獲得感、幸福感和滿足感。

式中，Δτij(t)為全局更新信息素增量，LNC為當(dāng)前迭代即第NC 次迭代的最優(yōu)路徑長(zhǎng)度，Lbest為當(dāng)前最優(yōu)路徑長(zhǎng)度.

此改進(jìn)有利于螞蟻根據(jù)當(dāng)前最優(yōu)路徑動(dòng)態(tài)地調(diào)整信息素，隨著迭代進(jìn)行，有更優(yōu)路徑出現(xiàn)后，LNC和Lbest的差值會(huì)逐漸減小.相應(yīng)地，信息素增量減小直至0，此時(shí)，當(dāng)前最優(yōu)路徑上只進(jìn)行信息素蒸發(fā).與基本蟻群算法相比，這樣能使當(dāng)前最優(yōu)路徑上的信息素濃度更為突出，但又不至于造成算法停滯，使當(dāng)前最優(yōu)路徑的變化更快地反映在信息素分布上.

2.2 分段調(diào)整信息素?fù)]發(fā)因子

蟻群算法中，信息素?fù)]發(fā)因子ρ 的大小直接關(guān)系到算法的全局搜索能力和收斂速度，基本蟻群算法中的ρ 是(0，1)區(qū)間的某個(gè)固定值.當(dāng)ρ 過小時(shí)，已經(jīng)被搜索過的路徑被再次選擇的可能性過大，容易出現(xiàn)局部收斂;反之，當(dāng)ρ 過大時(shí)，雖然可以提高算法的隨機(jī)性能和全局搜索能力，但又會(huì)使算法的收斂速度降低［6］.對(duì)此，本研究提出一種分段調(diào)整信息素?fù)]發(fā)因子的方法，即隨著迭代次數(shù)的增加，將算法分為初期、中期和后期.在算法初期，將ρ 設(shè)置為較大的值，這樣可以使算法的全局搜索能力增強(qiáng)，在中期和后期適當(dāng)減小ρ 的值，使得算法可以較快地收斂到最優(yōu)解.這樣既增加了算法的全局搜索能力，又可以在一定程度上加快算法的收斂.具體規(guī)則為，

其中，NC 表示算法的迭代次數(shù)，NC－max 表示最大迭代次數(shù).

在整個(gè)迭代過程的前四分之一，將ρ 取值為最接近1 的值0.9，可以在初始階段提高算法的全局搜索能力;然后，將ρ 設(shè)置為中間數(shù)值0.5，使算法既不至于陷入局部收斂，又能加快收斂速度;到了迭代過程的后四分之一，將ρ 值取為0.1，因?yàn)榇藭r(shí)的搜索結(jié)果已經(jīng)基本確定，適時(shí)可以加快算法的收斂速度.

2.3 算法實(shí)現(xiàn)

根據(jù)以上的改進(jìn)思路，改進(jìn)后的算法實(shí)現(xiàn)的具體步驟為:

1)參數(shù)初始化α，β，Q，NC－max，m，令迭代計(jì)數(shù)器NC = 1.

2)隨機(jī)選擇每只螞蟻的初始位置，初始化禁忌表tk，按照式(6)設(shè)置ρ 的值.

3)按照式(1)選擇路徑，將所選城市添加到tk中，并按照式(4)更新局部信息素.

4)若tk未滿則轉(zhuǎn)至步驟3)，若已滿，得出螞蟻此次的最優(yōu)路徑長(zhǎng)度LNC，并更新Lbest的值.

5)對(duì)當(dāng)前的最優(yōu)路徑按照式(5)更新全局信息素，清空tk.

6)若NC ＜NC－max，則NC = NC +1，并轉(zhuǎn)至步驟2)，開始新一次的迭代，否則算法結(jié)束，輸出最優(yōu)路徑長(zhǎng)度Lbest.

3 仿真實(shí)驗(yàn)及結(jié)果分析

在仿真實(shí)驗(yàn)中，選用TSP LIB 中的Oliver 30 和att 48 作為仿真算例，以驗(yàn)證本研究提出的改進(jìn)算法性能，并與基本蟻群算法求解Oliver30 TSP 和att48 TSP 進(jìn)行比較.

基本蟻群算法采用的參數(shù)為:α = 1，β = 2，ρ =0.5，Q = 100，NC－max = 200，m = 30［7］;本研究提出的改進(jìn)算法的參數(shù)為:α = 1，β = 2，Q = 100，NCmax = 200，m = 30.對(duì)2 種算法分別測(cè)試20 次，其結(jié)果如表1、2 所示.

表1 對(duì)Oliver30 TSP 測(cè)試20 次的結(jié)果

表2 對(duì)att48 TSP 測(cè)試20 次的結(jié)果

從表1、2 可以看出，經(jīng)過20 次的測(cè)試，采用本基本蟻群算法改進(jìn)的算法求解Oliver 30 和att 48 所得最優(yōu)值、最差值和平均值與基本蟻群算法相比均有所改善.

另外，在收斂速度上，本研究算法在150 代以內(nèi)幾乎可收斂到最優(yōu)值，但基本蟻群算法在180 代到200 代依然存在多次尚未收斂的情況.2 種算法的最短距離及收斂情況如圖1、2、3、4 所示.圖1 和圖2分別是基本蟻群算法測(cè)試att48 TSP 問題的某一次最短距離和收斂情況.

圖1 基本蟻群算法測(cè)試att48 TSP 問題的最短距離

圖2 基本蟻群算法測(cè)試att48 TSP 問題的收斂情況

圖3 和圖4 分別是改進(jìn)算法測(cè)試att48 TSP 問題的某一次最短距離和收斂情況.

圖3 改進(jìn)算法測(cè)試att48 TSP 問題的最短距離

圖4 改進(jìn)算法測(cè)試att48 TSP 問題的收斂情況

由實(shí)驗(yàn)結(jié)果可見，隨機(jī)選擇的某一次實(shí)驗(yàn)結(jié)果中，基本蟻群算法測(cè)試att 48 的最短距離是35 701.8073 km，收斂速度較慢，在迭代180 次之后仍未收斂;改進(jìn)算法測(cè)試att 48 的最短距離是34 751.3419 km，收斂速度明顯提升，在迭代150 次左右達(dá)到最優(yōu).此表明，在求解Oliver 30 和att 48 問題上，本改進(jìn)算法在求最優(yōu)解和收斂速度上有明顯優(yōu)勢(shì).

4 結(jié) 語(yǔ)

本研究通過引入信息素局部更新和全局更新相結(jié)合，以及分段式更新信息素?fù)]發(fā)因子的方法，對(duì)基本蟻群算法進(jìn)行了改進(jìn)，達(dá)到了擴(kuò)大解的搜索空間、兼顧搜索速度和搜索能力的目的.改進(jìn)算法的性能在Oliver 30 和att48 問題上已經(jīng)得到驗(yàn)證，但對(duì)于更大規(guī)模的數(shù)據(jù)，改進(jìn)的算法是否能夠使用還有待于進(jìn)一步的研究.

［1］王運(yùn)濤，姚礪，毛力.基于混合行為的自適應(yīng)蟻群算法［J］.計(jì)算機(jī)仿真，2009，26(12):151－153.

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

［3］方霞，席金菊.基于變異和啟發(fā)式選擇的蟻群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49(24):24－27.

［4］李成兵，郭瑞雪，李敏.改進(jìn)蟻群算法在旅行商問題中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2014，34(S1):131－132，165.

［5］王沛棟.改進(jìn)蟻群算法及在路徑規(guī)劃問題的應(yīng)用研究［D］.青島:中國(guó)海洋大學(xué)，2012.

［6］趙偉，蔡興盛，曲慧雁.一種基于懲罰函數(shù)和新信息素更新方式的蟻群算法［J］.計(jì)算機(jī)工程與科學(xué)，2013，35(3):103－107.

［7］葉仕通，萬(wàn)智萍.一種基于改進(jìn)全局信息素更新效率的蟻群算法及仿真［J］.計(jì)算機(jī)應(yīng)用與軟件，2014，31(1):176－179.