基于粒子群的蟻群算法參數最優組合研究

俞云新,王更生

(華東交通大學信息工程學院,南昌江西330013)

Yu Yunxin,Wang Gengsheng

(School of Information Engineering,East China Jiaotong University,Nanchang 330013,China)

自1991年Dorigo,Maniezzo和Colorni等首先提出蟻群算法[1,2]以來,很多研究人員對該算法進行了研究,并成功地解決了許多組合優化問題,如TSP問題,即在給定城市個數和各城市之間距離的條件下,找到一條遍歷所有城市且每個城市只訪問一次的總路程最短的路線。蟻群算法在TSP問題應用中取得了良好的效果,但參數α,β,ρ,Q,m的設置不當可能導致算法求解速度很慢且所得解的質量特別差,對此問題,已有研究人員進行了研究,但還沒有可行的方案。本文將在已有研究成果的基礎上,對此問題進行研究。

1 蟻群算法基本原理

蟻群算法模型可以通過TSP(旅行商)問題描述[3],TSP問題是指完全遍歷 n個城市一次且僅一次所走過的最短距離。其數學模型如下。

首先引入如下符號,m表示算法中螞蟻的數量;dij(i,j=1,2,…,n)表示邊(i,j)之間的距離;n為城市個數;τij(t)表示t時刻在(i,j)上殘留的信息素量。初始時刻,各邊信息素量相等。螞蟻k在t時刻由城市i轉移到城市j的概率為

式中:ηij為先驗知識或能見度,針對具體問題根據啟發式規則而定;α為邊(i,j)上殘留信息的重要程度;β為啟發信息的重要程度;tabuk為螞蟻k的禁忌表即螞蟻k所走過的城市集。

隨著時間的推移,以前螞蟻留下的信息素逐漸消逝,用參數ρ(ρ∈(0,1))表示信息素揮發率,當螞蟻完成一次循環后,各路徑上的信息素量根據下式做調整

式中:τij(t)n表示更新后邊(i,j)上的信息素量;τij(t)o表示更新前邊(i,j)上的信息素量;Δτkij表示第k只螞蟻本次循環中留在邊(i,j)上的信息素量;Δτij表示本次循環中邊(i,j)上信息素增量;Q為常數;Lk表示第k只螞蟻在本次循環中所走過的路徑長度。當所有螞蟻都完成一次周游后,因每只螞蟻本次周游的禁忌表已滿,此時應及時清空,準備下一次周游。當周游次數達到設定值時算法結束。

經過十幾年的發展,蟻群算法有諸多改進算法[4],但息啟發式因子α、期望值啟發式因子β、信息素揮發因子ρ、螞蟻數量m和初始信息素量Q都始終是影響算法性能的重要參數,其中 α的大小反映了信息素因素的作用強度,β反映了先驗性、確定性因素的作用。ρ的大小直接關系到蟻群算法的全局搜索能力及收斂速度。此外,m和Q也是影響算法效率的重要參數。有研究成果表明[4],參數的不同取值對算法性能的影響較大,為確定使算法性能較佳的最佳組合參數,本文將提出一種解決方案。

2 “兩步走”參數最優組合確定策略

本文試圖確定蟻群算法參數的最佳組合,使得算法性能最佳,在現有研究成果的基礎上,提出“兩步走”策略,即利用基本蟻群算法確定各參數的范圍,再引入適應度函數并結合粒子群算法確定各參數的最優組合。本節將先簡單介紹粒子群優化原理,再介紹“兩步走”策略方案,最后敘述基于粒子群的蟻群算法參數最優組合確定算法。

2.1 粒子群優化原理

粒子群優化(Particle Swarm Optimization,PSO)[5]是由Kennedy和Eberhart借鑒鳥類尋找食物的自然現象提出的一類基于種群的隨機全局優化技術。在算法的每一次迭代中,粒子xi通過跟蹤其自身所找到的最優解(個體極值pbest)和整個種群目前找到的最優解(全局極值gbest),按式(5)來進行更新,從而引導粒子向最優解方向移動。

式中:vk是粒子的速度向量;xk是當前粒子的位置;c1,c2為常數,稱為學習因子;r1,r2是在(0,1)上均勻分布的隨機數;w是慣性權重。

粒子群算法的優點是簡單易實現,比較適合解決連續域組合優化問題。

2.2 “兩步走”策略具體步驟

第1步 根據基本蟻群算法,確定各參數較優范圍。已有研究成果[5-10]得到各參數的經驗值,即α=1,β=5,ρ=0.5,m=n/1.5(n為城市數),Q=100。根據專家給出的參數可取范圍,利用基本蟻群算法,確定各參數的較優區間。在計算某個參數時,其余參數均采用經驗值。

第2步 引入適應度函數概念,結合粒子群算法,確定蟻群算法參數的最佳組合,使算法性能得到提高。理論思想是將蟻群算法抽象為一個函數F,參數α,β,ρ,Q,m抽象為函數的自變量,因此參數的組合優化問題可定義為:確定自變量 α,β,ρ,m,Q的最佳組合,使函數F(α,β,ρ,m,Q)取得最優值。由于參數的組合優化問題是一個連續域的組合優化,所以本文采用前面介紹過的粒子群算法來確定各參數的最佳組合,詳細算法將在下文闡述.

2.3 基于粒子群的蟻群算法參數最優組合算法設計

為實現“兩步走”策略的實際應用,本文提出基于粒子群的蟻群算法參數最優組合算法,其思想是將蟻群算法參數作為粒子群算法的優化對象(粒子的位置),在每一次迭代過程中,使用粒子的當前位置信息來運行蟻群算法求解一標準優化問題,并使用適應度函數F(α,β,ρ,m,Q)對求解性能做出評價,從而引導各粒子向著最優的方向飛翔。算法的運算步驟如下。

步驟1 根據“兩步走”策略中的第一步,確定各參數的較優區間,編寫基本蟻群算法程序,將參數 α,β,ρ,m,Q作為入口參數以便調用。另外,為了保證數據的合理性,程序輸出的結果取每一組參數十次運行的平均值。

步驟2 設定學習因子c1,c2和慣性權重w,在各參數較優區間內,對各粒子的初始位置和速度進行隨機選取;

步驟3 使用每個粒子對應的位置信息運行蟻群優化算法,求解一標準優化問題,并使用適應度函數F(α,β,ρ,m,Q)對求解結果進行評價,得到各粒子的適應值;

步驟4 對各粒子,比較其當前位置適應值和pbest的適應值,如果更好,則用當前位置來更新pbest;

步驟5 用每個粒子的pbest的適應值與全局極值gbest的適應值比較,若更好,則更新gbest;

步驟6 按式(5),(6)對每個粒子進行速度和位置更新;

步驟7 判斷是否滿足終止條件,若滿足,則輸出全局極值gbest及粒子位置,否則轉到步驟3。

為驗證本文提出策略及算法的實用性,下節將對結合實例對策略及算法進行仿真。

3 仿真結果及性能分析

本文根據TSP問題中的Eil51數據對算法做了仿真,用C++語言為確定蟻群算法參數最優組合設計了程序并進行運算。由于這兩種算法均是集群算法,所以有大量的螞蟻個體和粒子個體而且需要迭代運行產生優化結果。因此,編程實現中的難點是算法的時間開銷問題。本文經過程序設計的優化,以及適當地減少迭代次數,使得程序在理想的時間內得到優化的結果。蟻群算法的迭代次數為300,粒子群算法的迭代次數為100,粒子群算法的參數值選為

w=1,c1=c2=2。

確定蟻群算法各參數較優區間。取 α的范圍(0,10),步長為0.5;β的范圍(0,10),步長為0.5;ρ的范圍(0,1),步長0.05,m范圍(30,50),步長為1,Q范圍(0,500),步長為10,每次迭代1 000次。平均路徑長度取10次運行結果的平均值。本文列出參數ρ對蟻群算法性能影響的結果表1及收斂趨勢圖1。

表1 ρ與平均路徑長度的關系表

為進行對比,本文將蟻群算法各參數的隨機組合得到的10個較優結果列于表2。

表2 蟻群算法參數隨機組合結果表

根據本文提出的“兩步走”策略得到的10個較優結果見表3。

表3 基于粒子群的蟻群算法參數優化最優組合結果表

兩組結果中最優路徑的收斂趨勢見圖2。

圖1 ρ與平均路徑長度的關系

圖2 兩組最優結果的收斂趨勢圖

由表2可知,各參數的不同取值,對算法的性能有較大影響;較優區間內參數的隨機組合,并不能使得算法的性能最佳。由表3可知,最佳組合的各參數值與各參數的經驗值較接近,但性能有所差別,尤其是算法所花費時間差別比較大,因此,在解決實際問題中,要根據實際問題來確定各參數的值。其中,表3的第7行數據,最優結果值(425.720)比TSP官方公布的最優結果(TSP機構公布Eil51問題的最優結果是426)要好,但花費的時間較長。對比表2和表3可得,用“兩步走”得到的參數最佳組合確實可以提高算法的性能,無論是時間還是最優解都比隨機組合的結果要優。圖2是兩組結果中最優路徑長度收斂趨勢對比,它驗證了表2和表3的對比結果。

4 結論

蟻群算法各個參數對算法性能有較大影響,參數間的隨機組合使得算法陷入局部最優,花費時間過長等等。針對這一問題,本文提出了確定參數最優組合的“兩步走”策略及基于粒子群的蟻群算法參數最優組合算法,通過TSP問題中Eil51問題進行仿真和結果比較,證明了本文提出的策略及算法可以克服蟻群算法隨機參數的缺陷。本文策略及算法得到結果在最優值,穩定性和防止停滯方面都提取得了不錯的效果,增強蟻群算法實用性,有利于蟻群算法推廣及應用。

[1]BLUM C.Ant colony optimization:Introduction and recent trends[J].Physics of Life Reviews,2005,2(4):353-373.

[2]COLORM A,DORIGOM,MINIEZZO V.Distributed optimization by ant colonies[C].Proceeding of the First Europea n Conference on Artificial Life.ParisFrance:Elsevier Publishing,1991:134-142.

[3]勞眷.蟻群算法求解TSP問題若干改進策略的研究[J].科學技術與工程.2009,9(9):2 459-2 462.

[4]李士勇.蟻群算法及其應用[M].哈爾濱:哈爾濱工業大學出版社,2004:33-34.

[5]張江維,司文建.粒子群算法求解旅行商問題程序設計[J].電腦知識與技術,2009,5(7):1 696-1 698

[6]張毅,梁艷春.蟻群算法中求解參數最優選擇分析[J].計算機應用研究,2007,24(8):70-72.

[7]段海濱,王道波,朱家強,等.蟻群算法理論及應用研究的進展[J].控制與決策,2004,19(12):1 322-1 340.

[8]楊中秋,張延華,鄭志麗.基于改進蟻群算法對最短路徑問題的分析與仿真[J].沈陽化工學院學報,2009,23(2):150-153.

[9]葉志偉,鄭肇葆.蟻群算法中參數α、β、ρ設置的研究——以TSP問題為例[J].武漢大學學報,2007,29(7):597-601.

[10]蔣玲艷,張軍,鐘樹鴻.蟻群算法的參數分析[J].計算機工程與應用,2007,43(20):31-36.