孫改平,劉春梅

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

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

引言

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

1 基本蟻群算法模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(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í)驗結(jié)果

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

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

4 結(jié)語

本文針對基本蟻群算法收斂時間過長和容易陷入局部最優(yōu)的不足,通過對信息素?fù)]發(fā)系數(shù)和信息素增量的改進(jìn),從實(shí)驗結(jié)果來看,較好地解決了基本蟻群算法在解決TSP問題是容易陷入局部最優(yōu)的問題,提高了算法的收斂速度,增強(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é)報,2002,(1)：31 -33

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

[7] 朱立軍,楊中秋.一種引入信息素上下界自適應(yīng)機(jī)制的蟻群算法[J].沈陽化工學(xué)報,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-),女,山西陽泉人,華北科技學(xué)院副教授,北京工業(yè)大學(xué)在讀碩士研究生,研究方向：計算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)庫。