二層SA-GA算法解決時間依賴中國郵路問題.doc

二層sa-ga算法解決時間依賴中國郵路問題第38卷第5期2011年5月計算機(jī)科學(xué)computersciencevo1.38no.5mav2011二層sa/ga算法解決時間依賴中國郵路問題孫景昊吳雄譚國真閏超(大連理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院大連116023)摘要中國郵路問題是圖論中的經(jīng)典問題,得到了深入研究和廣泛應(yīng)用.近年來,由于計算機(jī)網(wǎng)絡(luò)與通信,智能交通系統(tǒng)等復(fù)雜應(yīng)用領(lǐng)域的需求,研究時間依賴網(wǎng)絡(luò)中的問題具有更為重要的現(xiàn)實(shí)應(yīng)用意義.首先給出了時間依賴中國郵路問題的定義,然后證明了傳統(tǒng)中國郵路問題的定理在時間依賴中國郵路問題中不成立,最后設(shè)計了二層sa/ga算法(模擬退火/遺傳算法)來解決該問題,對隨機(jī)產(chǎn)生的實(shí)例進(jìn)行了測試,并根據(jù)問題下界對算法結(jié)果進(jìn)行了分析.關(guān)鍵詞時間依賴,中國郵路問題,模擬退火,遺傳算法中圖法分類號tp393文獻(xiàn)標(biāo)識碼atime-dependentchinesepostmanproblemsolvedbytwolayerssa/gaalgorithmsunjing-haowuxiongtanguo-zhenyanchao(schoolofcomputerscienceandtechnology,dalianuniversityoftechnology,dalian116023,china)abstractthechinesepostmanproblemisoneoftheclassicalproblemsingraphtheoryandhasbeenwidelyanddeeplyresearchedsinceitwasproposed.itisapplicableinawiderangeoffields.withtherapiddevelopmentofcomputernetworks,computercommunicationandintelligenttransportationsystem,problemsintime-dependentnetworksbecomemorerealisticthantheclassicalproblems.first,wepresentedthedefinitionoftime-dependentchinesepostmanproblem(tdcpp)andthepropertyoftdcpp.thenweshowedthattheclassicalalgorithmsofchinesepostmanproblem(cpp)cantworkinthetime-dependentcircumstances.finally,twolayerssa/gaalgorithm(simulatedannealing/geneticalgorithm)wasproposed,thisapproachwastestedonsomerandomlygenerateddata,thecomputationalresultswereanalyzedbycomparingwithlowerboundoftheproblem.kedvordstime-dependent,chinesepostmanproblem,simulatedannealing,geneticalgorithm1引言中國郵路問題(chinesepostmanproblem)是1962年由管梅谷教授首次提出的口,成為圖論中的經(jīng)典問題.該問題是在一個連通無向圖中,從給定源結(jié)點(diǎn)出發(fā),遍歷圖中每條邊至少一次,并回到源結(jié)點(diǎn),使得總的耗費(fèi)最小.該問題又被稱為無向中國郵路問題(ucpp),edmonds和johnsonc給出了ucpp最小完美匹配算法.該問題有眾多的應(yīng)用領(lǐng)域,如垃圾收集路線,掃雪車路線,郵件投遞路線,軟件測試等,因此許多學(xué)者對該問題進(jìn)行了深入的研究并提出了許多新的分類:有向中國郵路問題,混合中國郵路問題,風(fēng)向郵路問題,鄉(xiāng)村郵路問題,層次郵路問題和多郵遞員問題.有向中國郵路問題的代表性工作是edmonds和johnsonc幻;混合中國郵路問題的代表性工作是edmonds和johnson,papadimitriou,frederiekson;風(fēng)向郵路問題的代表性工作是minieka,winl,raghavachari7;鄉(xiāng)村郵路問題的代表性工作是0卜loff和ghiani.;層次郵路問題的代表性工作是dror,cabral,korteweg和volgenan;多郵遞員問題的代表性工作是frederickson和dinoahrl13l.近年來,計算機(jī)網(wǎng)絡(luò)與通信,分布式處理和智能交通系統(tǒng)(its)的興起給一些傳統(tǒng)的研究課題帶來了新的轉(zhuǎn)折:時間依賴,即網(wǎng)絡(luò)中弧的走行時間是時間的函數(shù).它在時間依賴旅行商問題(tdtsp)和時間依賴車路由問題(tdvrp)領(lǐng)域得到了深入的研究.malandraki14,15,yang-byung_1,soumia和albertov.d_li等人給出了許多整數(shù)規(guī)劃模型和算法,幾乎所有計算智能算法都被用于求解tdvrp.同樣,時間依賴網(wǎng)絡(luò)中的中國郵路問題也有著重要的實(shí)際應(yīng)用價值.比如在郵遞員投遞郵件過程中,由于交通事故,天氣變化,上下班高峰期以及其它眾多隨機(jī)因素的影響所帶來的交通密度的變化,會影響到旅行時間的變化.這樣兩點(diǎn)之間的旅行時間往往不僅僅是距離的函數(shù),還跟進(jìn)入這兩點(diǎn)之間的鏈路的時刻有關(guān).據(jù)作者所知,目前國內(nèi)外還沒有相關(guān)的工作,本文重點(diǎn)研究時間依賴無向中國郵路問題,也簡稱為時間依賴中國郵路問題(time-dependentchinesepostman到稿日期:20100619返修日期:20100929本文受國家973項目(2005cb321904),國家自然科學(xué)基金項目(60873256)資助.孫景昊(1986),男,博士生,主要研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化,數(shù)學(xué)規(guī)劃理論,e-mail;.en;吳雄(1986一),男,碩士生,主要研究方向?yàn)榫W(wǎng)絡(luò)最優(yōu)化理論;譚國真(196o一),男,博士,教授,主要研究方向?yàn)闀r變網(wǎng)絡(luò)優(yōu)化,智能交通和城市交通;閆超(1986),男,碩士,主要研究方向?yàn)橹悄芩惴??93?problem,tdcpp).第2節(jié)給出了tdcpp問題的定義和性質(zhì);第3節(jié)針對時間依賴網(wǎng)絡(luò)中國郵路問題的新性質(zhì),提出了二層sa/ga算法(模擬退火/遺傳算法);第4節(jié)是算法測試和分析;最后是結(jié)束語.2tdcpp問題的定義和性質(zhì)2.1ri1)(,pp問題的定義給定一個連通無向圖g一(,e,t),其中v是一個非空有限結(jié)點(diǎn)集;點(diǎn)1(三vxv是有限邊集;t一c()v(,口f)e),對于每條邊(,)e,c()表示遍歷邊(,)的時間函數(shù),并且c()一c().tix;pp(timedependentchinesepostmanproblem)問題就是對于給定的源結(jié)點(diǎn)vov,在g中求一條回路,該回路從vo出發(fā),經(jīng)過e中的每條邊至少一次,最終回到,且滿足總的走行時間最短.考慮邊上的旅行時間函數(shù)c()為分段函數(shù)的情況.在這種情況下,一天被劃分為若干個時間段,這在現(xiàn)實(shí)生活中很普遍,例如在城市交通網(wǎng)絡(luò)中,每天上下班高峰期會比較擁擠,其余時間相對比較通暢,這樣一天就可以劃分為3個時間段.如此以來,一旦知道了郵遞員開始遍歷某條邊(,)所處的時間段,遍歷該邊所需的時間就是確定值.這樣,就可以對原網(wǎng)絡(luò)進(jìn)行擴(kuò)展.每條邊(,)都可以用條并行的從i到的邊來取代,其中為分段函數(shù)c()所具有的時間段數(shù),每條并行邊對應(yīng)著一個時間段m.對于不同的邊,m的值可能會不同.為敘述方便起見,用m代替m來表示時間間隔的數(shù)目,這意味著原網(wǎng)絡(luò)中所有的邊具有相同的時間段數(shù).圖1給出了邊(i,)上的旅行時問函數(shù)的例子,該分段函數(shù)具有3個時間段.,()上的蘸行時阿:一:_l_i手彳一圖1邊(,j)上的旅行時間函數(shù)(m;3)2.2tdcpp問題的性質(zhì)cpp滿足如下定理:定理1c是帶正權(quán)無向連通圖g=<v,e,w>中的最優(yōu)投遞路線當(dāng)且僅當(dāng)對應(yīng)的歐拉圖g應(yīng)滿足:(1)g的每條邊在g中至多重復(fù)出現(xiàn)一次;(2)g的每個圈上在g中重復(fù)出現(xiàn)的邊的權(quán)之和不超過該圈權(quán)的一半.tdcpp的性質(zhì):在tdcpp中,定理1不成立.證明:在cpp問題中,邊的重復(fù)次數(shù)不超過1,而在tdcpp中,無論是fifo還是非fifo網(wǎng)絡(luò),都不易得出邊的重復(fù)次數(shù)的上限.構(gòu)造反例,如圖2所示.1?94?圖2不滿足傳統(tǒng)cpp邊重復(fù)至多1次的例子對于fifo網(wǎng)絡(luò),以圖2為例,假設(shè)各個邊的權(quán)值函數(shù)為:5()一1,vfo;,一,一喜:一驀g4s(t)=一顯然,最優(yōu)路徑為1351251451,總權(quán)值為16,其中(1,5)邊重復(fù)了2次.對于非fifo網(wǎng)絡(luò),仍然以圖2為例,假設(shè)各個邊的權(quán)值函數(shù)為:g3s()一1,v0;f1t一1f1f一2f1一4踟一i1oo其它g13一i1oo其它g25一i1o0其它f1一15f1一7f1一8g12一i1o0其它g45一i1oo其它g14一1oo其它顯然,最優(yōu)路徑為153152154一l,總權(quán)值為9,其中(1,5)邊重復(fù)了2次.所以在時間依賴網(wǎng)絡(luò)的中國郵路問題中,邊可以重復(fù)多次,而不是傳統(tǒng)中國郵路問題的至多重復(fù)一次.證畢.因?yàn)閏pp的算法都是基于定理1的,因此cpp的算法不適合解決tdcpp問題,下一節(jié)針對tdcpp的性質(zhì),提出了模擬退火和遺傳算法相結(jié)合的算法.3二層sa/ga算法初始化r=0,丁一丁r,一生成(3.1.1節(jié)),一xado(#b循環(huán))do(內(nèi)循環(huán))產(chǎn)生新解:)x一(3.1.2節(jié))一c(x一)一c(),用遺傳算法計算c()(3.2節(jié))初始化mo由產(chǎn)生初始種群(3.2.2節(jié))計算每個染色體的適應(yīng)度(3.2.1節(jié))do父代選擇(3.2.2節(jié))遺傳操作產(chǎn)生新種群(3.2.3節(jié))mm+1loopwhile(m<最大進(jìn)化代數(shù))ifat<othenx&stxm且n+1且x;else隨機(jī)產(chǎn)生u(o,1)令exp(-at丁r)ify<z且一+1且=endifloopwhile(n<lll終止條件不滿足)rr+1一%-1一loopwhile(tr>oll終止條件不滿足)終止條件為連續(xù)k次不接受新解圖3二層sa/ga算法的總體框架傳統(tǒng)cpp算法分為兩步:首先用floyd和最小權(quán)完美匹配算法確定問題的最優(yōu)添邊方案以形成歐拉圖,然后利用歐拉尋徑算法找一條歐拉回路.然而根據(jù)tdcpp的性質(zhì),不能應(yīng)用傳統(tǒng)算法得到tdcpp的最優(yōu)添邊方案,即使能夠確定最優(yōu)添邊方案,也要遍歷該方案的所有歐拉回路才能確定最優(yōu)解.因此設(shè)計了一種二層sa/ga算法,內(nèi)層采用ga算法確定某個添邊方案的滿意解,外層采用sa算法搜索不同的添邊方案,最后收斂到全局滿意解.而選擇sa和ga的出發(fā)點(diǎn)是把sa的概率突跳性和ga的群體并行搜索能力有機(jī)地結(jié)合起來,以提高尋優(yōu)過程的快速性和優(yōu)化度.二層sa/ga算法的總體框架如圖3所示.3.1外層模擬退火算法3.1.1初始解產(chǎn)生首先由g一(,e,t)產(chǎn)生m(時間段數(shù))個新圖一(,),一1,2,m,其中一v,一e,中每條邊的權(quán)值都是常數(shù),且v(,),c一(),<然后隨機(jī)選擇其中一個圖,用floyd和最小權(quán)完美匹配算法找到該圖的最優(yōu)添邊方案形成新的歐拉圖g.初始解就是對原圖添加重復(fù)邊形成的歐拉圖g.3.1.2新解產(chǎn)生對當(dāng)前添邊方案形成的歐拉圖進(jìn)行局部調(diào)整生成新的歐拉圖.隨機(jī)取一條邊,設(shè)選中邊的各個時問段邊權(quán)最大值為,整個網(wǎng)絡(luò)各個時間段邊權(quán)最大值中最小的為.如果選中邊沒有重復(fù),重復(fù)該邊2次;如果選中邊重復(fù)次數(shù)為1,按概率聲一exp(wn一訓(xùn))重復(fù)該邊2次;按概率1一p刪除該邊1次,然后在該邊的兩端點(diǎn)問找一條路徑,重復(fù)該路徑上的邊1次;如果選中邊重復(fù)次數(shù)大于等于2,按概率exp(zq,一)重復(fù)該邊兩次;按概率(1一p)/2刪除該邊1次,然后在該邊的兩端點(diǎn)間找一條路徑,重復(fù)該路徑上的邊1次;按概率(1一p)/2刪除該邊2次.3.2內(nèi)層遺傳算法下面根據(jù)遺傳算法的操作,以圖4為例介紹求每個添加方案形成的歐拉圖的滿意解的實(shí)現(xiàn)過程.o2圖4一個時i曰依賴網(wǎng)絡(luò)設(shè)圖4中節(jié)點(diǎn)0為初始點(diǎn),求該時間依賴網(wǎng)絡(luò)中的中國郵路問題的最優(yōu)解.這里不妨設(shè)其中一種添邊方案為(0,3)邊重復(fù)一次.對該添加方案形成的歐拉圖應(yīng)用遺傳算法找到滿意解.3.2.1編碼與適應(yīng)度函數(shù)以該添加方案的歐拉回路的節(jié)點(diǎn)遍歷次序作為遺傳算法的編碼,即0130230是一個遺傳編碼,因?yàn)槌跏键c(diǎn)不變,所以針對遺傳編碼任何操作都不能改變第一位基因.又因?yàn)槌跏键c(diǎn)和終止點(diǎn)是同一點(diǎn),所以該編碼可簡化為013023.如果某個基因前面有和它相同的基因,那么將該基因碼重復(fù)加上節(jié)點(diǎn)數(shù)(直到前面沒有相同的基因)得到新基因碼,因此前面的基因碼變?yōu)?13427.令遺傳編碼對應(yīng)的歐拉回路的遍歷時間為t(gene).由于在可行解群體的初始化,交叉操作中均隱含tix3pp問題的合法性約束,故適應(yīng)度函數(shù)取為:zt(gene),其中z為較大的數(shù),且zt(gene).3.2.2種群初始化和選擇機(jī)制開始用fleury算法產(chǎn)生初始種群,種群規(guī)模為n.保留最優(yōu)解并保留m個較優(yōu)的個體作為樣本群體,以供選擇;在每一代運(yùn)算過程中,個體被選中的概率與其在群體中的相對適應(yīng)度成正比.3.2.3交叉方法隨機(jī)在編碼中選擇一個交配區(qū)域,如兩父編碼及交配區(qū)域選定為:a:013142l7b=034l17l2將b的交配區(qū)域加到a的某一位置(如編碼末尾),a的交配區(qū)域加到b的相同位置得到:a=01342717b:034172l42在a和b中自交配區(qū)域后依次刪除與交配區(qū)相同的編碼,得到的兩子編碼為:&一034217b=031742顯然,和都是非法編碼(按編碼遍歷的不是歐拉回路),通過反用fleury算法將編碼調(diào)整為最終的合法編碼:a一034271=031472這種方法在兩父編碼相同的情況下仍能產(chǎn)生一定程度的變異效果,它對維持群體的多樣性有一定作用.4算法測試與分析算法用java編碼并在windowsxp/amd3500+中實(shí)現(xiàn),通過與問題下界比較對算法進(jìn)行了分析.4.1測試問題產(chǎn)生表1總結(jié)了隨機(jī)產(chǎn)生的tdcpp測試問題的屬性,總共產(chǎn)生了2o個測試問題,對于每個問題,給定節(jié)點(diǎn)數(shù)和邊數(shù),邊權(quán)產(chǎn)生于e2o,6o3均勻分布.表1tdcpp測試問題的屬性4.2問題下界生成策略首先由原圖g一(v,e,t)得到新圖g,一(v,),其中與相同,與e相同,中每條邊的權(quán)值都是常數(shù),且v(,)e,勺一min(co-();然后對求中國郵路問題的最優(yōu)解.最優(yōu)解即為問題下界.算法的近似度按如下計算:apro=fn/f式中,f為問題下界,是算法找到的最優(yōu)解.4.3計算結(jié)果內(nèi)層遺傳算法的參數(shù)如下:種群規(guī)模n為500,選擇概率為0,9,進(jìn)化代數(shù)為128;外層模擬退火算法終止條件為k一15.算法測試結(jié)果如表2所列.(下轉(zhuǎn)第101頁)?95?putingcfffirstinternationalconferenceoncloudcomputing.lecturenotesincomputerscience,2009:589594r18zhouguo-fu,yuanchongyi.mappingpunitytouninetj.journalofcomputerscienceandtechnology,2003,18(3):37838719chandykm,misraj.parallelprogramdesignm.ma,usa:addison-wesleypub.co.inc,19892ographvizeb/ol.,may5,2010213grappaeb/ol./john/grappa,may5,2010r22jakarta-oroeb/oi./oro/,may5,201023bjornerd,jonescb,airehinnigha,eta1.vdm87vdm-一aformalmethodatworkm.germany:springer-verlag,198724spiveyjm.theznotation:areferencemanualeb/ol.http:/spivey.orie1.ox.ac.uk/mike/zrm/,1998(上接第95頁)表2二層sa/ga算法的測試結(jié)果從表2可以得出,該算法可以在合理的時間給出很好的解.對于測試的實(shí)例,該算法的近似度在最壞情況下不大于1.47,在最好情況下不大于1.39,平均情況下不大于1.43.另外,隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,算法的執(zhí)行時間也隨之增加;因?yàn)樵撍惴ㄊ怯脝栴}下界衡量近似度,所以該算法的實(shí)際近似度要好于統(tǒng)計的結(jié)果.結(jié)束語時間依賴中國郵路問題與傳統(tǒng)中國郵路問題相比有更廣泛的應(yīng)用領(lǐng)域,更具有普遍意義.時間依賴中國郵路問題的時變特性,使得傳統(tǒng)問題的理論和算法不再適用.在分析時間依賴中國郵路問題的性質(zhì)的基礎(chǔ)上,提出了二層sa/ga算法,與已有相關(guān)算法相比,該算法能有效地解決大規(guī)模時間依賴中國郵路問題.對于具體的測試實(shí)例而言,近似度在最壞情況下不大于1.47,實(shí)現(xiàn)了結(jié)果與效率平衡的目的.該算法可以應(yīng)用到網(wǎng)絡(luò)通信,實(shí)時系統(tǒng)測試以及智能交通系統(tǒng)等眾多領(lǐng)域.參考文獻(xiàn)eli管梅谷.奇偶圖上作業(yè)法j.數(shù)學(xué),1962,1:2632752edmondsj,johnsonel.matching,eulertoursandthechinesepostmanproblemj.math.prog,1973,5:88124ispapadimitriouch.onthecomplexityofedgetraversingj.journaloftheacm,】976,23,5445444fredericksongn.approximationalgorithmsforsomepostmanproblemj.journaloftheacm,1979,26,53855453miniekae.thechinesepostmanproblemformixednetworksj.managementscience,1979,253:64364863wmz.onthewindypostmanproblemoneuleriangraphsj.mathematicalprogramming,1989,44:97一l127raghavacharib,veerasarnytj.approximationalgorithmfortheasymmetryicpostmanproblemq/proceedingsof10thannualacmsiamsymposiumondiscretalgorithms.1999:7347418orloffcsafundamentalprobleminvehicleroutingj.networks,1974,4:35649ghianiag,musmannobr.aheuristicfortheperiodicruralpostmanproblemj.computers&operationsresearch.2005,32:2192281odrorm,sternh,trudeaup.postmantouronagraphwithprecedencerelationonaresj.networks,1987,17:28329411cabralea,gendreaum,ghianig,eta1.solvingthehierarehicalchinesepostmanproblemasaruralpostmanproblemj.europeanjournalofoperationalresearch,2004,155:445o12kortewegp,volgenantt.onthehierarchicalchinesepostmanproblemwithlinearorderedclassesj.e