蟻群優(yōu)化算法NDLACO

第24卷第3期計算機應用與軟件Vol. 24 ,No. 3.2007年3月Computer Applications and SoftwareMar.2007蟻群優(yōu)化算法NDLACO任善全呂強錢(qián)培德楊季文(蘇州大學(xué)計算機科學(xué)與技術(shù)學(xué)院江蘇省計算機信息處理技術(shù)重點(diǎn)實(shí)驗室江蘇 蘇州215006 )摘要ACO算法在解NP-hard問(wèn)題上雖然取得了廣泛應用但在解同一類(lèi)型的不同問(wèn)題時(shí)需要更改a β ρ等參數的值才能取得相應問(wèn)題的最優(yōu)解或更接近最優(yōu)解的解。通過(guò)使用最近鄰居選擇、信息素動(dòng)態(tài)更新和局部啟發(fā)搜索法對MMAS算法進(jìn)行優(yōu)化,得出NDLACO算法。此算法運用于解CVRP問(wèn)題時(shí)取得了較好的效果。在關(guān)于參數值的問(wèn)題上取得了-定的成效,也有效地解決了蟻群算法的收斂過(guò)快和早熟、停滯問(wèn)題。關(guān)鍵詞蟻群算法 NDLACO CVRPAN ANT COLONY OPTIMIZATION ALGORITHM NDLACORen ShanquanLi Qiang Qian Peide Yang Jiwen( Provincial Key Laboratory for Computer Information Pocessing Technology School of Computer Science & Technology ,Soochov Univrsiy Suzhou Jiangsu 215006 China )AbstractAlthough ACO algorithm has solved many NP-hard problems scesfully ,some parameters( a β ρ )must be changed for thesake of getting optimal results or the solutions being close to when solving different problems. This paper optimizes MMAS by using the nearestneighbor node choosing dynamic pheromone updating and local searching strategies and comes into being NDLACO algorithm ,which can getgood results in solving some instances of CVRP. This article gains some significative effects in researching the parameters ,what's more NDLA-C0 algorithm also deals with the contradiction between ant's fast convergence and stagnation effectively.KeywordsAnt colony algorithm NDLACO Capacitated VRP服停滯現象等等。以上研究對算法有-定程度的改進(jìn),但在不1引言斷強調提高收斂速度縮短螞蟻的搜索時(shí)間以便運用于解決大規模優(yōu)化問(wèn)題時(shí)常使某些路徑的信息素過(guò)度增強而導致早熟、蟻群算法ACO( Ant Colony Optimization )是近年來(lái)出現的一停滯現象使得所求解的質(zhì)量降低,以致得不到最好解或最優(yōu)種新型的模擬進(jìn)化算法。此算法已成功運用于解決幾種NP-解?？梢?jiàn)使用所得解過(guò)度強化信息素的變化來(lái)贏(yíng)得時(shí)間與所得hard的組合優(yōu)化問(wèn)題36]如旅行商問(wèn)題(TSP)車(chē)輛調度問(wèn)題解質(zhì)量的提高之間存在著(zhù)矛盾螞蟻搜索時(shí)間過(guò)短會(huì )導致解的(VRP)等顯示出蟻群算法在求解復雜優(yōu)化問(wèn)題方面的優(yōu)越質(zhì)量下降,而提高解的質(zhì)量常需要增加螞蟻的搜索時(shí)間。為此,性。近幾年來(lái)的研究成果表明蟻群算法具有很強的發(fā)現較好我們基于VRP問(wèn)題的優(yōu)化應用研究了一種基于最近鄰居選解的能力、具有分布式計算、易于與其他方法相結合和魯棒性強擇、信息素動(dòng)態(tài)更新和局部啟發(fā)搜索的蟻群算法簡(jiǎn)稱(chēng)NDLACO等優(yōu)點(diǎn)。然而,蟻群算法在搜索過(guò)程中也易于出現早熟停滯算法( ACO algorithm based on the nearest neighbor node choosing ,現象。dynamic pheromone updating and local searching )。該優(yōu)化算法使很多學(xué)者對此都提出了改進(jìn)算法避免發(fā)生信息素更新過(guò)用最近鄰節點(diǎn)選擇來(lái)縮短螞蟻的搜索時(shí)間;依據螞蟻已搜索路快出現早熟停滯現象。例如,EAS( elitist ant system )算法使用徑的分布狀況動(dòng)態(tài)更新信息素來(lái)防止出現算法的早熟停滯現取得較好解的螞蟻進(jìn)行信息素更新;RBAS( rank-based version of象使用局部啟發(fā)搜索來(lái)再次優(yōu)化螞蟻的所得解以提高所得解antsystem)算法使得每個(gè)螞蟻在更新信息素時(shí)的權重不同7];的質(zhì)量。實(shí)驗結果表明,本文提出的算法與其它最新的優(yōu)化算BWAS( best-worst ant system )算法只使用取得最好解和最差解法相比在平衡搜索時(shí)間和解的質(zhì)量這對矛盾之間和對蟻群算的螞蟻進(jìn)行信息素的更新”]文獻1 ]提出了一種相遇算法主法中參數設定的研究取得了很好的成效。要思想是使用兩個(gè)螞蟻合作完成一條 路徑的搜索來(lái)提高求解的中國煤化工速度文獻9 ]提出的MMAS( max min ant system )算法只使用取2 ACYHCNMHG研究現狀得最好解的螞蟻進(jìn)行信息素的全局更新來(lái)加速收斂控制信息素的變化范圍來(lái)克服停滯現象;文獻[ 10 ]提出了一種變異策CVRP問(wèn)題是VRP問(wèn)題的一種情況,也是VRP問(wèn)題中最基略以加快局部搜索;文獻11]提出了根據當前螞蟻所走路徑的分布情況動(dòng)態(tài)地對信息素進(jìn)行更新文獻12 ]提出了一種新收稿日期2005 -03-16。任善全碩士生主研領(lǐng)域:計算機中文穎的動(dòng)態(tài)信息素更新策略和變異策略來(lái)加速收斂速度,以期克信息處理及應用技術(shù)。160計算機應用與軟件2007年本的問(wèn)題。CVRP 問(wèn)題屬于NP-hard問(wèn)題應為T(mén)SP問(wèn)題屬于CVRP問(wèn)題的子問(wèn)題,即是CVRP問(wèn)題的一種特殊情況。實(shí)際4 NDLACO 算法設計模型上CVRP問(wèn)題比TSP問(wèn)題更難于求解。CVRP 問(wèn)題包含兩種子問(wèn)題bin-packing問(wèn)題和最短路徑問(wèn)題而TSP問(wèn)題只屬于后者4.1 最近鄰居選擇原則范疇。1999年Bullnbeimer等人提出了運用于解CVRP問(wèn)題螞設定每個(gè)站點(diǎn)i的鄰居數為n/2則站點(diǎn)i的鄰居站點(diǎn)表述群算法AS. ASm-CVRP)。此后2002 年Reimann 等對此算為sto[iIjIj=1 2 . n/2 ) xdistance( i i)表示站點(diǎn)i到站點(diǎn)法進(jìn)行了優(yōu)化稱(chēng)之為AS -CVRPsav[101 ,AS。n -CVRPsav算法j的距離每個(gè)站點(diǎn)i的鄰居站點(diǎn)以按1/distance(ij)的升序進(jìn).優(yōu)于A(yíng)Sk -CVRP算法。在2004年Karl F. Doererl]等人把并行排列,由此可見(jiàn)distance( i i)到站臺j的概率則CVRP可描述載重量為Vcap的Vsum輛車(chē)( distance( cl r2 )+distance(s. c2 s. c3 )+ distance(s_ cl p3 )))子從車(chē)站出發(fā)按照-定的規則把n個(gè)分布在不同站點(diǎn)的重量為then執行3-opt操作斷開(kāi)圖1波浪線(xiàn)部分的連接形成圖2新的循w( i=1 2.. n )的乘客接到車(chē)站處并使得Vsum輛車(chē)子所走環(huán)鏈表。的路徑短所花時(shí)間少。4.3基于均勻分 布度的選擇原則3.1 螞蟻的節點(diǎn)選擇原則5gτn°(1)n(1)j e allowed,子在站點(diǎn)i選擇下一站點(diǎn)j的依據p*( t)選擇取得p*( t)吹1)= { Eel s ζgTn°(t)m&(t)(7)值最大的節點(diǎn)j。otherwiser%1)%1)其中ξ∈(0 ,1 )為路徑( i i )的信息權重" ,當經(jīng)過(guò)路徑( i門(mén))的j∈allowed,(1)= { llwmuxrn"(1)n.(t)(1 )螞蟻的數量較多時(shí)則使5;值減小反之則增大。這樣就使得通過(guò)螞蟻較多的路徑下次被選中的幾率變小通過(guò)螞蟻較少的其中llwede,表示螞蟻k:'下-步可選擇的站臺的集合a表示路路徑下次被選擇的幾率變大。P"( 1 )表示螞蟻由站點(diǎn)i選擇站徑.上的信息量對螞蟻選擇路徑所起作用的大小mj為由站點(diǎn)i點(diǎn)j的概率最終達到螞蟻在所有的路徑上處于均勻分布的目的。使用基于均勻分布的選擇原則,有效地解決了蟻群算法加到站點(diǎn)j的希望程度通常取nη;=1/djo .速收斂和早熟、停滯的現象。3.2信息素局部更新原則(1+1)=( 1-p)r(t1)+Qrf(2)4.4信息素局部更新原則--些經(jīng)典的算法在更新信息素時(shí)要么對所有的螞蟻所經(jīng)指=rQ/L。 螞蟻h在本次循環(huán)中i和j之間(3)過(guò)的路徑增加其信息量要么只增加每代中取得最優(yōu)路徑上的信息量其余的被蒸發(fā),這些做法都采用固定的信息素增減比其中ρ∈(0 1 )表示信息量τ( 1 )隨時(shí)間的推移而衰減的程度例沒(méi)有考慮當前螞蟻搜索中所走路徑的分布情況。本算法信Q為常數Lh為螞蟻k在本次循環(huán)中已走路徑的長(cháng)度。息素的更新依據當前螞蟻所走路徑的分布情況進(jìn)行不同程度地3.3信息素全局更 新原則更新動(dòng)中國煤化工使其不至于過(guò)分集中或在每代搜索螞蟻中選擇使用取得最好解的螞蟻antBest 進(jìn)分散導MHCNMH G行全局的信息素更新。辦門(mén)- IU*0.UDrA1) 若本次迭有1/3只螞蟻選擇同一路( i j)τg"=(1-ε)ry" +eAry (i i)e antBest的解(4)Arj=1/LmBe(5)τ(1+1)={或1/5只螞蟻選擇(8)該條搜索最后一步。其中ε為全局信息素蒸發(fā)系數Lume為本代螞蟻 中求得最好解的路徑長(cháng)度。(r(1)-1*0.05r61) othervise第3期任善全等蟻群優(yōu)化算法NDLACO161由于螞蟻常選擇信息量較大的路徑,當多只螞蟻選中同一使用公式( 7 )基于均勻分布度的原則選擇下-站點(diǎn);路徑后信息量會(huì )大幅度增加就容易使多只螞蟻集中到該路徑endif上。在搜索過(guò)程中希望螞蟻處于比較均勻分布的狀況如公式使用公式( 8 )進(jìn)行信息索局部更新(局部更新)(8)所示如果某段路徑.上的螞蟻較多時(shí)在信息素更新時(shí)使之end while蒸發(fā)得多反之當某段路徑上所經(jīng)過(guò)的螞蟻數量較少時(shí)局部更end for Vsum新時(shí)信息素的蒸發(fā)就少些。MMAS算法”1信息素的局部更新使用局部啟發(fā)搜索法3-opt對所得的完整解進(jìn)行優(yōu)化;中只對信息素進(jìn)行蒸發(fā),而不進(jìn)行蒸發(fā)后的補償本算法信息i訊(q< =qo)(q為隨機數(0