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