基于粒子群的蟻群算法參數(shù)最優(yōu)組合研究

俞云新,王更生

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

Yu Yunxin,Wang Gengsheng

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

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

1 蟻群算法基本原理

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

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

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

隨著時(shí)間的推移,以前螞蟻留下的信息素逐漸消逝,用參數(shù)ρ(ρ∈(0,1))表示信息素?fù)]發(fā)率,當(dāng)螞蟻完成一次循環(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)中所走過的路徑長度。當(dāng)所有螞蟻都完成一次周游后,因每只螞蟻本次周游的禁忌表已滿,此時(shí)應(yīng)及時(shí)清空,準(zhǔn)備下一次周游。當(dāng)周游次數(shù)達(dá)到設(shè)定值時(shí)算法結(jié)束。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟3 使用每個(gè)粒子對(duì)應(yīng)的位置信息運(yùn)行蟻群優(yōu)化算法,求解一標(biāo)準(zhǔn)優(yōu)化問題,并使用適應(yīng)度函數(shù)F(α,β,ρ,m,Q)對(duì)求解結(jié)果進(jìn)行評(píng)價(jià),得到各粒子的適應(yīng)值;

步驟4 對(duì)各粒子,比較其當(dāng)前位置適應(yīng)值和pbest的適應(yīng)值,如果更好,則用當(dāng)前位置來更新pbest;

步驟5 用每個(gè)粒子的pbest的適應(yīng)值與全局極值gbest的適應(yīng)值比較,若更好,則更新gbest;

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

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

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

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

本文根據(jù)TSP問題中的Eil51數(shù)據(jù)對(duì)算法做了仿真,用C++語言為確定蟻群算法參數(shù)最優(yōu)組合設(shè)計(jì)了程序并進(jìn)行運(yùn)算。由于這兩種算法均是集群算法,所以有大量的螞蟻個(gè)體和粒子個(gè)體而且需要迭代運(yùn)行產(chǎn)生優(yōu)化結(jié)果。因此,編程實(shí)現(xiàn)中的難點(diǎn)是算法的時(shí)間開銷問題。本文經(jīng)過程序設(shè)計(jì)的優(yōu)化,以及適當(dāng)?shù)販p少迭代次數(shù),使得程序在理想的時(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次運(yùn)行結(jié)果的平均值。本文列出參數(shù)ρ對(duì)蟻群算法性能影響的結(jié)果表1及收斂趨勢(shì)圖1。

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

[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ìn)策略的研究[J].科學(xué)技術(shù)與工程.2009,9(9):2 459-2 462.

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

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

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

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

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

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

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