基于信息素改進(jìn)的蟻群算法①

孫改平,劉春梅

(1.北京工業(yè)大學(xué),北京 100124;2.華北科技學(xué)院,北京 東燕郊 101601)

基于信息素改進(jìn)的蟻群算法①

孫改平1,2②,劉春梅1,2

(1.北京工業(yè)大學(xué),北京 100124;2.華北科技學(xué)院,北京 東燕郊 101601)

蟻群算法是一種優(yōu)秀的啟發(fā)式算法,具有較強(qiáng)的魯棒性。針對(duì)基本蟻群算法在求解過(guò)程中容易出現(xiàn)收斂時(shí)間過(guò)長(zhǎng)以及容易陷入局部最優(yōu)的不足。本文提出了一種改進(jìn)的蟻群算法,該算法通過(guò)在信息素?fù)]發(fā)系數(shù)上增加一個(gè)收斂函數(shù),加快了收斂速度;通過(guò)信息素增量與優(yōu)秀路徑選擇相結(jié)合,引導(dǎo)算法收斂到最優(yōu)路徑,實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法在收斂速度和全局尋優(yōu)能力上有了較大的提高。

蟻群算法;信息素?fù)]發(fā)系數(shù);信息素增量

引言

蟻群算法(Ant Colony Algorithm,簡(jiǎn)稱(chēng)ACA)是20世紀(jì)90年代初由意大利學(xué)者Dorigo等人首先提出的一種新的啟發(fā)式優(yōu)化算法[1],是目前國(guó)內(nèi)外啟發(fā)式算法研究的熱點(diǎn)和前沿課題,它已被成功地應(yīng)用于求解TSP問(wèn)題[2]、二次分配問(wèn)題(QAP)[3]、車(chē)輛路徑問(wèn)題(VRP)[4]等NP完全問(wèn)題。實(shí)驗(yàn)表明,蟻群算法在求解復(fù)雜優(yōu)化問(wèn)題方面具有較強(qiáng)的優(yōu)越性和廣闊的應(yīng)用前景,但是由于蟻群算法也存在一些缺點(diǎn),比如：收斂時(shí)間過(guò)長(zhǎng)和容易陷入局部最優(yōu)等。為了克服這些缺點(diǎn),不少學(xué)者提出了許多改進(jìn)的蟻群算法。例如：王穎,謝劍英[5]等指出的通過(guò)自適應(yīng)地改變算法的揮發(fā)度等系數(shù),在保證收斂速度的條件下提高解的全局性。趙寶江,李士勇[6]提出了一種基于自適應(yīng)路徑選擇和信息素更新的蟻群算法,以求在加速收斂和防止早熟、停滯現(xiàn)象之間取得很好的平衡。朱立軍,楊中秋[7]提出了提出一種動(dòng)態(tài)調(diào)整路徑上信息素的上下界,使路徑上信息素永遠(yuǎn)保持在一個(gè)被允許的范圍內(nèi),從而避免使算法過(guò)早陷入局部最優(yōu)解等。在此基礎(chǔ)上,本文提出了一種改進(jìn)的蟻群算法,通過(guò)在信息素?fù)]發(fā)系數(shù)上增加一個(gè)收斂函數(shù),根據(jù)解的分布情況進(jìn)行信息素的更新,從而調(diào)整各路徑上的信息素強(qiáng)度,從而避免了局部收斂,提高全局搜索能力;通過(guò)信息素增量上的差別來(lái)增大優(yōu)秀路徑和其它路徑之間的信息素量的差距,引導(dǎo)算法收斂到最優(yōu)路徑,同時(shí)加快算法的收斂速度。

1 基本蟻群算法模型

為了能夠清楚地理解蟻群算法,以經(jīng)典的TSP問(wèn)題為例說(shuō)明蟻群算法的基本模型。n個(gè)城市的TSP問(wèn)題就是尋找通過(guò)n個(gè)城市各一次且最后回到出發(fā)點(diǎn)的最短路徑。在模擬實(shí)際螞蟻的行為時(shí),為了表述方便,引進(jìn)如下記號(hào)：設(shè)有n個(gè)城市組成的集合C,m只螞蟻,用dij(i,j=1,2,…, n)表示城市i和城市j之間的距離,ij(t)表示t時(shí)刻在城市i和城市j之間的路徑上殘留的信息素強(qiáng)度。初始時(shí)刻,各條路徑上信息素強(qiáng)度相等,設(shè)ij(0)=const(const為常數(shù))。螞蟻k(k=1, 2,…,m)在運(yùn)動(dòng)過(guò)程中,根據(jù)各條路徑上的信息素強(qiáng)度決定轉(zhuǎn)移方向,同時(shí)用禁忌表tabuk(k=1, 2,…n)來(lái)記錄螞蟻k當(dāng)前已走過(guò)的城市,集合tabuk隨著進(jìn)化過(guò)程作動(dòng)態(tài)調(diào)整。(t)表示在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率,其表示式為

其中,allowedk={C-tabuk}表示螞蟻k下一步允許選擇的城市;α為信息啟發(fā)式因子,β為期望啟發(fā)式因子,ηij(t)為啟發(fā)函數(shù),是路徑長(zhǎng)度的倒數(shù),表示式為ηij(t)=1/dij。為了避免殘留信息素過(guò)多引起殘留信息淹沒(méi)啟發(fā)信息,在每只螞蟻?zhàn)咄暌粋€(gè)循環(huán)后,要對(duì)殘留信息進(jìn)行更新處理。其表達(dá)式為

式中Δ τij(t)表示螞蟻k在本次循環(huán)中在城市i和城市j之間的路徑上留下的信息素增量,其表達(dá)式為

式中：Q是信息素強(qiáng)度,它影響算法的收斂速度;Lk是螞蟻k在本次循環(huán)中所走路徑的長(zhǎng)度。

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

在基本蟻群算法中,由于信息素?fù)]發(fā)系數(shù)的存在,使那些從未被搜索過(guò)的路徑上的信息量減小到接近于0,從而降低了算法在這些路徑上的搜索能力,反之,當(dāng)某條路徑中信息素較大時(shí),這些路徑中的信息量增大,搜索過(guò)的路徑再次被選擇的機(jī)會(huì)就會(huì)變得較大,這也影響了算法的全局搜索能力,在此通過(guò)在信息系揮發(fā)系數(shù)上增加一個(gè)收斂函數(shù)來(lái)改變信息素值,其表達(dá)式為

其中ψ(m)是一個(gè)與收斂次數(shù)m成正比的函數(shù),收斂次數(shù)m越多ψ(m)的取值越大,如：

ψ(m)=連續(xù)收斂次數(shù)m/ct

這里ct為常數(shù),這樣根據(jù)解的分布情況進(jìn)行信息素的更新,從而調(diào)整各路徑上的信息素強(qiáng)度,使螞蟻既不過(guò)分集中也不過(guò)分分散,從而避免了局部收斂,提高全局搜索能力。

在基本蟻群算法中,所有路徑的更新方法都是一樣的,沒(méi)有體現(xiàn)出優(yōu)秀路徑與包括較差路徑在內(nèi)的其它路徑在信息素量增加上的區(qū)別,尤其是當(dāng)路徑長(zhǎng)度較長(zhǎng)時(shí),每次迭代過(guò)后各條路徑上的信息素量的增量的差別并不明顯,因此各條路徑上的信息素量在一定的時(shí)間內(nèi)并沒(méi)有明顯的差距,這會(huì)降低信息素對(duì)螞蟻尋優(yōu)的引導(dǎo)作用,導(dǎo)致螞蟻對(duì)下個(gè)節(jié)點(diǎn)的選擇主要受到路徑長(zhǎng)度的影響,這種情況下,螞蟻移動(dòng)的盲目性大大增加,這在很大程度上降低了算法的收斂速度,同時(shí)各條路徑上信息素量差別的不明顯,使得優(yōu)秀路徑很難脫穎而出,而較差的路徑卻很容易干擾螞蟻的尋優(yōu),導(dǎo)致算法收斂于局部最優(yōu)。

為了通過(guò)信息素增量上的差別來(lái)增大優(yōu)秀路徑和其它路徑之間的信息素量的差距,引導(dǎo)算法收斂到最優(yōu)路徑,同時(shí)加快算法的收斂速度。根據(jù)路徑的優(yōu)秀程度的不同,在此對(duì)信息素的增量Δ τij(t)進(jìn)行改進(jìn),其表達(dá)式為

式中,BestL為從開(kāi)始至當(dāng)前代所找出的最優(yōu)路徑值,Lk為當(dāng)前代中螞蟻k所找出的路徑值。

這種改進(jìn)可以快速增加優(yōu)秀路徑上的信息量,而對(duì)非優(yōu)秀路徑上的信息素增加則不明顯,每次迭代后,每條路徑都會(huì)根據(jù)本身值的優(yōu)劣來(lái)獲得相應(yīng)的信息素增量,這樣,越優(yōu)秀的路徑每次迭代后都會(huì)獲得比較多的信息素增量,而比較差的路徑的信息素增量則相應(yīng)的較少,多次迭代后優(yōu)秀路徑和較差路徑上的信息素量就有會(huì)一定差別,這有利于排除較差路徑的干擾,大大加快了算法的尋優(yōu)速度,有利于算法快速收斂到最優(yōu)值。

改進(jìn)蟻群算法的實(shí)現(xiàn)步驟為：

(1)參數(shù)初始化

令時(shí)間t=0,循環(huán)次數(shù)Nc=0,設(shè)置最大循環(huán)次數(shù)Ncmax,將m只螞蟻隨機(jī)分配到n個(gè)城市,信息量τij(0)=const,初始時(shí)刻τij(0)=0,其中const為常數(shù)。

(2)循環(huán)次數(shù)Nc=Nc+1;

(3)螞蟻數(shù)目k=k+1;

(4)螞蟻根據(jù)公式(1)計(jì)算的概率選擇城市j并前進(jìn);

(5)修改禁忌表,將螞蟻移動(dòng)到新的城市;

(6)若城市未遍歷完,則跳轉(zhuǎn)到(4)繼續(xù)執(zhí)行;

(7)若k＜m,則跳轉(zhuǎn)到(3)繼續(xù)執(zhí)行;

(8)根據(jù)改進(jìn)公式(5)(6)更新每條路徑上的信息量;

(9)如果螞蟻全部收斂到一條路徑或循環(huán)次Nc＞Ncmax,則結(jié)束,并輸出程序結(jié)果,否則清空禁忌表并跳轉(zhuǎn)到(2)。

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

為了驗(yàn)證改進(jìn)算法的有效性,通過(guò)對(duì)TSP20、TSP30、TSP50問(wèn)題進(jìn)行實(shí)驗(yàn)仿真,參數(shù)設(shè)置為α=1,β=5,Ncmax=400,n=100,m=100,平均運(yùn)行50次作為仿真結(jié)果。本文改進(jìn)的蟻群算法與基本蟻群算法比較結(jié)果見(jiàn)表1。

表1 改進(jìn)的蟻群算法與基本蟻群算法比較

4 結(jié)語(yǔ)

本文針對(duì)基本蟻群算法收斂時(shí)間過(guò)長(zhǎng)和容易陷入局部最優(yōu)的不足,通過(guò)對(duì)信息素?fù)]發(fā)系數(shù)和信息素增量的改進(jìn),從實(shí)驗(yàn)結(jié)果來(lái)看,較好地解決了基本蟻群算法在解決TSP問(wèn)題是容易陷入局部最優(yōu)的問(wèn)題,提高了算法的收斂速度,增強(qiáng)了算法的全局尋優(yōu)能力。

[1] Dorigo M,Maniezzo V,Colorni A.Ant system：optimization by a colony of cooperating agents [J].IEEETransactions onS MC,1996,26 (1)：12-41

[2] DorigoM,Gambardella L M.Ant colony system：a cooperative learning approach to the traveling sales man problem[J].IEEE Transactions on Evolutionary Computing,1997(1)：53-66

[3] Talbi E G,Roux O,Fonlupt C,et al.Parallel ant colonies for the quadratic assignment problem [J].Future Generation Computer Systems,2001, 17(4)：441-449

[4] BullnheimerB,Hartl R F,Strauss C.An improved ant system algorithm for the vehicle routing problem[J].Annals of Operations Research,1999 (89)：319-328

[5] 王 穎,謝劍英.一種自適應(yīng)蟻群算法及其仿真研究[J].系統(tǒng)仿真學(xué)報(bào),2002,(1)：31 -33

[6] 趙寶江,李士勇,金俊.一種基于自適應(yīng)路徑選擇和信息素更新的蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(3)：12-15

[7] 朱立軍,楊中秋.一種引入信息素上下界自適應(yīng)機(jī)制的蟻群算法[J].沈陽(yáng)化工學(xué)報(bào),2009 (3)：65-68

Ant Colony Algorithm Based on Pheromone Improving

SUN Gaiping1,2,L IU Chunm ei1,2

(1.BeijingUniversity of Technology,Beijing 100124
2.North China Institute Science and Technology,Yanjiao Beijing-East 101601)

AntColonyAlgorithm is an excellent heuristic algorithm and has strong robustness.The algorithm easily gets into long convergence time and may be trapped in a local optimum.The papermakes some improvement on adding a convergence function to the pheromone volatilization coefficients,improving the convergence rate;and on guiding the algorithm converges to the optimal path by being combined pheromone incrementwith the outstanding routing.The experiment results indicate that the improved algorithm not only increases the convergence rate and also enhances the ability of searching the global optimal solution.

ant colony algorithm;the pheromone volatilization coefficients;the pheromone incremental

TP301.6

A

1672-7169(2010)01-0076-03

2009-12-27

孫改平(1969-),女,山西陽(yáng)泉人,華北科技學(xué)院副教授,北京工業(yè)大學(xué)在讀碩士研究生,研究方向：計(jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)庫(kù)。