基于初始信息素和二次揮發(fā)的改進(jìn)蟻群算法

何亮亮,王曉東

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引 言

隨著智能計(jì)算領(lǐng)域的不斷擴(kuò)大,用于解決優(yōu)化問題的蟻群算法(ACO)[1]、螢火蟲算法(FA)[2]、粒子群算法(PSO)[3]以及蝙蝠算法(BA)[4]等群體智能算法[5]不斷涌入,這類算法為解決NP-hard問題提供了較好的方法,其設(shè)計(jì)原理來源于對大自然中生物行為的效仿．蟻群算法作為最早的仿生物算法,一直備受專家學(xué)者關(guān)注．近些年,眾多學(xué)者對蟻群算法進(jìn)行了深入的研究,解決了旅行商問題[6-7]、指派問題[8]以及調(diào)度問題[9]等.目前,針對蟻群算法的改進(jìn)已有大量的研究,張飛君等[10]提出了一種相遇螞蟻算法,一次完整的周游路徑由2只相遇螞蟻共同完成,提高了算法運(yùn)行速度以及擴(kuò)大了解的搜索空間[10];楊延慶等[11]對信息素最大最小值進(jìn)行了固定,避免了路徑上信息素的差異;HUANG M等[12]針對車輛路徑問題引入了3-opt交換策略,初始規(guī)劃路徑得到了進(jìn)一步的優(yōu)化;張琦等[13]針對移動(dòng)機(jī)器人路徑規(guī)劃問題,對算法局部啟發(fā)式函數(shù)進(jìn)行了調(diào)整與改進(jìn),并且在引入交叉操作的同時(shí)調(diào)整參數(shù)值;姜坤霖等[14]在輪盤賭法的基礎(chǔ)上提出了一種新的城市選擇策略,并結(jié)合提前結(jié)束任務(wù)的方法減少了算法運(yùn)行時(shí)間;朱顥東等[15]通過選擇下一節(jié)點(diǎn)轉(zhuǎn)移規(guī)則對算法進(jìn)行了改進(jìn),提高了選擇最優(yōu)路徑的概率;胡偉[16]將蟻群算法與禁忌搜索算法相結(jié)合,改進(jìn)了蟻群算法的局部搜索能力．這些算法雖然都改善了蟻群算法的缺點(diǎn),但對初始信息素分布的改進(jìn)以及信息素的二次揮發(fā)的研究還較少．由于基本蟻群算法中的初始信息素濃度為定值,螞蟻選擇下一節(jié)點(diǎn)時(shí)僅依靠路徑的長度,而信息素的揮發(fā)發(fā)生在每條路徑上,降低了算法的尋優(yōu)效率,因此結(jié)果不一定最優(yōu);另外,隨著迭代次數(shù)的增加,后期路徑信息素殘余量較少,算法的尋優(yōu)能力也相應(yīng)減弱．為了改善以上2種狀況,本文對蟻群算法初始信息素的分布以及信息素的揮發(fā)因子進(jìn)行改進(jìn),提高了算法的收斂速度和后期的尋優(yōu)能力．

1 基本蟻群算法

蟻群算法是學(xué)者從螞蟻覓食過程受到啟示得來的一種仿生物算法．研究者發(fā)現(xiàn)螞蟻會在路徑上釋放一種信息素的激素,它會隨著時(shí)間逐漸揮發(fā),之后的螞蟻可以感覺到信息素的存在,并且沿信息素濃度較高的路徑前進(jìn)，同時(shí)繼續(xù)釋放信息素,這樣越來越多的螞蟻會聚集到一條路徑上,從而形成了正反饋機(jī)制．螞蟻根據(jù)式(1)選擇未被訪問的下一個(gè)城市,并將其添加到禁忌列表．

(1)

(2)

(3)

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

2.1 初始化信息素改進(jìn)

在基本蟻群算法中,設(shè)m為螞蟻個(gè)數(shù),n為城市數(shù)目,剛開始時(shí)的信息素量為m/cm,其中cm是由最鄰近方法構(gòu)造出來的路徑的長度．在算法初始階段,信息素濃度小,螞蟻可覺察到信息素的能力相對較弱,需要經(jīng)過一段時(shí)間的摸索,才能找出一條相對較優(yōu)路徑．在這個(gè)過程中耗費(fèi)了大量的時(shí)間,降低了算法的收斂速度．為了改善這種狀況,考慮通過路徑距離重新設(shè)定初始信息素的分布,使得算法有方向地進(jìn)行搜索,以克服搜索的盲目性．對初始信息素改進(jìn)如下:

(4)

式中:dij為螞蟻所在城市i到城市j之間所有可能的距離,min(dij)為所有可能距離中最短路徑距離．由于城市坐標(biāo)位置固定,所以全局最小距離min(dij)不變,螞蟻所選擇的路徑dij越短,初始信息素就越大,且螞蟻是在權(quán)衡全局路徑距離dij與最短路徑min(dij)的比重之后選擇路徑,從而使得算法避免盲目搜索,節(jié)省了大量的時(shí)間．

2.2 信息素?fù)]發(fā)因子

在基本蟻群算法中,信息素的更新僅對較優(yōu)路徑上的信息素進(jìn)行更新,然而最優(yōu)路徑的子路徑并不總是最短路徑,同時(shí)可能存在較長路徑,這樣會導(dǎo)致螞蟻從一開始就選錯(cuò)路徑,也就錯(cuò)過了最優(yōu)路徑．為了解決這一缺陷,文獻(xiàn)[17]引入了路徑貢獻(xiàn)度，見式(5).在最優(yōu)路徑中,找出對整體路徑貢獻(xiàn)度大于路徑貢獻(xiàn)度閾值的子路徑．并按式(6),(7)對這條子路徑上的信息素進(jìn)行二次更新：

(5)

(6)

(7)

在基本蟻群算法中,信息素?fù)]發(fā)因子為定值．由于每次迭代得到的較差解對最終結(jié)果沒有幫助,如果信息素的揮發(fā)在較差路徑上相對較慢,則殘留的信息素越多,就會影響算法尋找最優(yōu)解的速度,因此應(yīng)減慢較優(yōu)路徑信息素?fù)]發(fā)的速度,加快較差路徑上的信息素?fù)]發(fā)速度,所以針對文獻(xiàn)[17]中信息素的二次更新后的信息素考慮進(jìn)行二次揮發(fā),使得二次揮發(fā)系數(shù)與迭代次數(shù)平方成反比．隨著迭代次數(shù)的增加,揮發(fā)因子相應(yīng)減小,算法后期未走路徑上信息素?fù)]發(fā)速度相應(yīng)減慢,螞蟻感知到的信息素則相應(yīng)增多,一定程度上改善了算法后期尋優(yōu)能力弱的缺陷．因此對二次揮發(fā)因子改進(jìn)為

(8)

式中：C為以常數(shù);NC表示算法的迭代次數(shù);CDSP為路徑貢獻(xiàn)度;q0為路徑貢獻(xiàn)閾值(取常數(shù))．信息素按照式(9)進(jìn)行更新:

τij(t+n)=(1-ρ)τij(t+n)+ρ1τij(new).

(9)

3 改進(jìn)的蟻群算法步驟

Step 1:初始化蟻群算法中的參數(shù)m,α,β,η,ρ,q0、NC-max,NC=1,計(jì)算城市間的距離dij,初始信息素τij(0)按照式(4)取值;

Step 2:將m只螞蟻放置n個(gè)城市中作為起點(diǎn),為每只螞蟻建立禁忌表tabu,計(jì)算啟發(fā)因子;

Step 3:按照式(1)選擇下一個(gè)要訪問的城市j,當(dāng)螞蟻到達(dá)城市j后,將j加入到禁忌表tabu中;

Step 4:若禁忌表tabu未滿,則跳轉(zhuǎn)至Step 3;若tabu已滿,則輸出本次迭代最優(yōu)長度Length-best及最優(yōu)路徑Route-best;

Step 5:根據(jù)全局更新規(guī)則,按式(2),(3)對信息素進(jìn)行首次更新;

Step 6:按式(5)計(jì)算路徑貢獻(xiàn)度;按式(6),(7)計(jì)算新的信息素變化量Δτij(new);按式(8)得出二次揮發(fā)因子ρ1;根據(jù)全局更新規(guī)則,按式(9)對信息素進(jìn)行二次更新;

Step 7:若滿足迭代條件NC≥NC-max,則輸出最優(yōu)長度Length-best;若不滿足條件,則NC=NC+1,返回Step 2．

4 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證改進(jìn)蟻群算法的有效性,將基本蟻群算法與改進(jìn)后的算法通過TSPLIB中的4組數(shù)據(jù)Eil51、31個(gè)城市、Oliver30和Att48分別進(jìn)行尋優(yōu)搜索對比．運(yùn)行環(huán)境為Windows 10系統(tǒng)、Matlab 2016a軟件．2種算法的公共參數(shù):m=50,α=6,η=7,ρ=0.1,q0=0.4．在此參數(shù)下每組數(shù)據(jù)各運(yùn)行20次,運(yùn)行結(jié)果見表1,改進(jìn)前后蟻群算法對比如圖1，2所示.表1中最優(yōu)解和最差解分別為運(yùn)行20次后2種算法搜索到的最優(yōu)解中最好的1次和最差的1次,平均解表示運(yùn)行20次后2種算法搜索到的最優(yōu)解平均值．

(a) Eil51迭代圖 (b) 31個(gè)城市迭代圖圖 1 改進(jìn)前后蟻群算法對比Fig.1 Comparison of ant colony algorithm before and after improvement

數(shù)據(jù)算法最優(yōu)解最差解平均解平均迭代次數(shù) 31個(gè)城市基本蟻群算法16 16016 79016 25045改進(jìn)后的蟻群算法15 78816 25015 81022 Eil51基本蟻群算法467.8497.2468.322 改進(jìn)后的蟻群算法465.1496.3465.712 Oliver30基本蟻群算法434.828 6436.486 8435.439 117 改進(jìn)后的蟻群算法429.214 7435.703 9431.323 88 Att48基本蟻群算法35 768.77135 952.33235 798 62444 改進(jìn)后的蟻群算法35 137.13535 756.52335 597.56725

從表1可以看出,在31個(gè)城市數(shù)據(jù)下,基本蟻群算法得到最優(yōu)解為16 160,而改進(jìn)后的蟻群算法的最優(yōu)解為15 788,最優(yōu)解減少了372,最差解的差值為540,平均解提升了440;在Oliver30數(shù)據(jù)下,基本蟻群算法所得到最優(yōu)解為434.828 6,而改進(jìn)后的蟻群算法的最優(yōu)解為429.214 7,最優(yōu)解減少了5.613 9,最差解的差值為0.782 9,平均解提升了4.115 3;其余2組數(shù)據(jù)的最優(yōu)解和平均解比改進(jìn)前更優(yōu),改進(jìn)后的蟻群算法尋優(yōu)能力更強(qiáng);從平均迭代次數(shù)上看,31個(gè)城市數(shù)據(jù)下迭代次數(shù)縮減了23次;Eil51數(shù)據(jù)下迭代次數(shù)縮減了10次;Oliver30數(shù)據(jù)下迭代次數(shù)縮減了9次;Att48數(shù)據(jù)下迭代次數(shù)縮減了19次．4組數(shù)據(jù)改進(jìn)前后的迭代次數(shù)均有明顯的減少,改進(jìn)后的蟻群算法收斂速度更快．

2種算法對Eil51和31個(gè)城市的20次搜索最優(yōu)值中其中的一次迭代對比如圖1所示．從圖1(a)可以看出，基本蟻群算法的最優(yōu)解大于470,而改進(jìn)后的最優(yōu)解小于460;從圖1(b)圖中可以看出，基本蟻群算法最優(yōu)解大于16 100,而改進(jìn)后的最優(yōu)解明顯小于16 000;并且達(dá)到最優(yōu)解時(shí),改進(jìn)后的蟻群算法迭代曲線的拐點(diǎn)均在基本蟻群算法迭代曲線拐點(diǎn)前,說明改進(jìn)后的蟻群算法較基本蟻群算法優(yōu)先跳出局部最優(yōu)．

31個(gè)城市下蟻群算法優(yōu)化路徑如圖2所示．從圖2(a)可以看出,在中國的31個(gè)城市數(shù)據(jù)下的基本蟻群算法最優(yōu)解為16 148.379 8,最優(yōu)路線為27,28,26,25,24,20,21,22,18,3,17,19,23,11,12,14,13,7,6,5,16,4,2,8,9,10,15,1,29,30,31．從圖2(b)可以看出，在中國的31個(gè)城市數(shù)據(jù)下的改進(jìn)蟻群算法的最優(yōu)解為15 989.982 1,最優(yōu)路線為:1,15,13,12,14, 11,23,16,5,6,7,2,4,8,9,10,3,18,17,19,24,25,20,21,22,26,28,27,30,31,29,1．

(a) 基本蟻群算法路徑 (b) 改進(jìn)的蟻群算法路徑圖 2 蟻群算法優(yōu)化路徑Fig.2 Ant colony optimization path

5 結(jié) 論

(1) 在基本蟻群算法的基礎(chǔ)上,對初始信息素改進(jìn),在文獻(xiàn)[17]的基礎(chǔ)上建立了二次信息素?fù)]發(fā)因子,并通過MATLAB軟件在相同的參數(shù)條件下,對改進(jìn)的蟻群算法和基本蟻群算法進(jìn)行仿真.

(2) 改進(jìn)的蟻群算法不但繼承了算法本身的優(yōu)良性,而且彌補(bǔ)了基本蟻群算法效率低、“早熟”以及后期尋優(yōu)能力差等缺點(diǎn),改進(jìn)的蟻群算法有效可行．