俞云新,王更生

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

Yu Yunxin,Wang Gengsheng

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

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

1 蟻群算法基本原理

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

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

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

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

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

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

2 “兩步走”參數(shù)最優(yōu)組合確定策略

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

2.1 粒子群優(yōu)化原理

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

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

粒子群算法的優(yōu)點是簡單易實現(xiàn),比較適合解決連續(xù)域組合優(yōu)化問題。

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

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

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

2.3 基于粒子群的蟻群算法參數(shù)最優(yōu)組合算法設(shè)計

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

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

步驟2 設(shè)定學習因子c1,c2和慣性權(quán)重w,在各參數(shù)較優(yōu)區(qū)間內(nèi),對各粒子的初始位置和速度進行隨機選取;

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

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

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

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

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

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

3 仿真結(jié)果及性能分析

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

w=1,c1=c2=2。

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

表1 ρ與平均路徑長度的關(guān)系表

為進行對比,本文將蟻群算法各參數(shù)的隨機組合得到的10個較優(yōu)結(jié)果列于表2。

表2 蟻群算法參數(shù)隨機組合結(jié)果表

根據(jù)本文提出的“兩步走”策略得到的10個較優(yōu)結(jié)果見表3。

表3 基于粒子群的蟻群算法參數(shù)優(yōu)化最優(yōu)組合結(jié)果表

兩組結(jié)果中最優(yōu)路徑的收斂趨勢見圖2。

圖1 ρ與平均路徑長度的關(guān)系

圖2 兩組最優(yōu)結(jié)果的收斂趨勢圖

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

4 結(jié)論

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

[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].科學技術(shù)與工程.2009,9(9):2 459-2 462.

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

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

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

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

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

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

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