計算機專業(yè)畢業(yè)論文外文翻譯(含原文)_第1頁
計算機專業(yè)畢業(yè)論文外文翻譯(含原文)_第2頁
計算機專業(yè)畢業(yè)論文外文翻譯(含原文)_第3頁
計算機專業(yè)畢業(yè)論文外文翻譯(含原文)_第4頁
計算機專業(yè)畢業(yè)論文外文翻譯(含原文)_第5頁
已閱讀5頁,還剩8頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

摘要這篇文章是描述基于旅行商問題一種粒子群算法(PSO),一個不確定的搜索策略和交叉淘汰技術(shù)被用來加快收斂速度。相對于現(xiàn)有的求解TSP使用群集智能算法,有證據(jù)表明,利用粒子群算法解決問題的大小會增加。另一個基于PSO算法將其應用于采用廣義的染色體解決廣義旅行商問題。所提出的算法兩個局部搜索技術(shù)被用來加快收斂速度。數(shù)值結(jié)果表明了該方法的有效性。1介紹粒子群算法(PSO)算法,最初,是由KennedyandEberhart提出的,是一種源于成群的鳥的或魚社會行為的優(yōu)化方法。類似的,遺傳算法,該算法也是一種基于人群的優(yōu)化算法。該系統(tǒng)在初始時首先隨機生成的潛在的解決方案,然后通過迭代尋找最優(yōu)解。它通過最好的粒子尋找最優(yōu)解。相比算法PSO有著更好的智能背景和可執(zhí)行要容易得多。根據(jù)其優(yōu)勢,該算法是不僅適合于科學研究,而且工程應用。目前該算法已在該領(lǐng)域的進化計算領(lǐng)域吸引了廣大的注意,優(yōu)化和許多其他算法問題。雖然該算法為連續(xù)優(yōu)化問題了,最近,已經(jīng)有一些報告工作開始關(guān)注離散的問題。旅行商問題(TSP),在組合優(yōu)化中是一個基準許多新發(fā)展的著名和廣泛的研究,包括在進化計算中的技術(shù),如領(lǐng)域搜索(NNS),模擬退火(SA),禁忌搜索(TS),神經(jīng)網(wǎng)絡(NN),蟻群算法(ACS),遺傳算法等等。更重要的是Clerc,HendtlassandWang提出不同的粒子群算法解決TSP問題。盡管PSO能夠用于TSP,在TSP問題的規(guī)模,解決問題的報告都提到小于17個城市。從而看出解決TSP使用PSO算法是有限的。一個非常簡單而實用的TSP的延伸是廣義的TSP(GTSP),其中一組節(jié)點分為集群和目標都是為了找到一條路徑經(jīng)過所有節(jié)點的使成本最小。該GTSP代表了一種組合優(yōu)化問題,自20世紀60年代由Henry-Labordere[18],Saskena[19]和Srivastava[20]所提出的,并通過福利機構(gòu)在計算機條件下記錄平衡和訪問測序。它已許多廣泛領(lǐng)域中得到應用。正如文章[21]所提到的,“在許多現(xiàn)實世界問題中,他們是固有的層次,GTSP提供了一個比TSP更準確的模型?!币话愣?,對許多實際問題GTSP提供了更多的理想的建模工具。此外,根據(jù)我們目前的延伸在GTSP同時可以包括分組和孤立頂點。因此,GTSP包括理論上的TSP而且在GTSP在應用領(lǐng)域比TSP更廣泛的。雖然自20世紀60年代末的GTSP已提議[18-20],相關(guān)文獻是非常有限的,對TSP問題[8-14]和現(xiàn)有的算法GTSP主要基于動態(tài)規(guī)劃技術(shù)[18-20,22]。動態(tài)規(guī)劃算法的主要方法是把GTSP轉(zhuǎn)變到TSP問題,然后利用現(xiàn)有解決TSP算法。這些方法缺點是顯著的增加了問題的維數(shù)。因此雖然在理論上GTSP用來解決相應的轉(zhuǎn)變的TSP問題,其技術(shù)的局限性限制了實際的可行性。按設計廣義染色體(GA),Wuetal.[23]已經(jīng)研究出廣義染色體的遺傳算法GC能夠統(tǒng)一GTSP和TSP問題,通過引入“超級頂點”成為一個統(tǒng)一的模式。因此,一般情況下,該算法不增加解決問題的大小。在文中,兩個粒子之間的”減法”操作是修改和離散粒子群優(yōu)化方法構(gòu)建TSP問題。在該方法中也用到交叉淘汰技術(shù)。數(shù)值表明,該方法可以提高解析TSP問題的規(guī)模?;趯TSP編碼技術(shù)的在[23],另一基于PSO算法在本文提出了求解GTSP。兩個本地搜索技術(shù)還列入擬議的方法。為了測試方法的有效性,19GTSP問題測試作為研究基準。結(jié)果表明,該方法是有效解決GTSP問題的方法。將成為我們的最好知識,至今還沒有試圖提出一項基于PSO算法的GTSP。這個提議粒子群算法可以提供一個合適的方法解決GTSP。2粒子群優(yōu)化算法首先,要介紹標準粒子群優(yōu)化算法。假設搜索空間D維和m微粒形成的種群,一個粒子為一個D維的向量Xi(i=1,2....m),意思是第i個粒子在D維的搜索空間中的位置Xi=(Xi1,Xi2,….,XiD),(i=1,2….m)。每個粒子的位置都是一個潛在的解。我們通過給定的函數(shù)計算粒子的適應值fitness,當適應值比但前Xi更優(yōu),第i個粒子的飛行速度也是一個D維的向量Vi=(Vi1,Vi2,….,ViD)(i=1,2….m)。第i個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值,記為pi=(pi1,pi2,….,piD),相應的整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值,記為pg=(pg1,pg2,….,pgD)。PSO算法如下方程表示:(1)(2)式中,i=1,2,….,m,m是群體中粒子的總數(shù)。ω是[0,1]的慣性常數(shù);c1,c2是學習因子,為非負常數(shù),r1,r2是[0,1]的隨機數(shù)。程序終止的標準是pg是否滿足給定函數(shù)或給定的適應值。上文所述的算法可以被視為傳統(tǒng)的粒子群優(yōu)化,這是適用于連續(xù)的問題。然而,不能

適用于離散問題直接。針對離散問題,肯尼迪和埃伯哈特提出了離散二進制版本的PSO算法的確定粒子的運動軌跡和速度的變化概率這一點將會在一國或其他[5]。因此,在每一代中粒子的移動將被限制成0和1,Vid代表Xid的取1時的概率。公式(2)中除了pid,xig在整數(shù){0,1}內(nèi),粒子群公式保持不變。公式(1)更新為:其中S(?)是物流轉(zhuǎn)變,能夠保持vid在整數(shù){0,1},且S(vid)可被視為是一個概率。3離散的粒子群算法解決TSP3.1離散PSO算法求解TSP問題的詳解Clerc提出了一個簡單的粒子群算法求解TSP問題的概述。通過在PSO算法中對每個粒子的添加內(nèi)存的能力,Hendtlass[16]采用PSO算法解決小規(guī)模TSP的問題,并改善其性能,wang等[17]通過引入“交換操作”和“交換序列”的概念重新確定PSO的的操作者。在[16]和[17]的城市大小中都是14(雙方都選擇Burma14,基準問題TSPLIB與14個城市),而[15]是17個城市(它選定br17,一個基準問題TSPLIB與17個城市)。這就是說,在算法中城市的大小受到限制。為了擴大規(guī)模,解決問題,受到[17]中“交換操作”的啟發(fā),我們介紹置換的概念納入我們提議的離散PSO算法解決TSP問題。并且增加一個不確定性搜索

戰(zhàn)略以加快收斂速度。對以m的tsp問題,定義Xi={xi1,xi2,...xim}為第i個粒子在PSO的種群中,代表xi1→xi2。。。?!鷛im→xi1。傳統(tǒng)的PSO算法被定義為方程(1)(2)。為了能解決TSP問題,方程(1)保持不變,而第二項方程右邊的意思即Vi(k+1)改變了。因此方程(2)可以被重新定義。首先兩個粒子的減法應該被重新定義。為了表示這個問題,一些概念置換將介紹。定義1置換可以用相關(guān)符號表示。一個可以安排元素“自然”排列,然后在此基礎(chǔ)再重新排列:[12345]→[25431]用s(1)=2,s(2)=5,s(3)=4,s(4)=3,s(5)=1代表[12345]置換定義2.讓X為一集合,一個循環(huán)為一個置換,如存在X的不同元素a1,a2,…ak定義3.一個循環(huán)命令是一些元素和他平凡的軌道。一個周期k階也所謂的K-循環(huán)。一個1-循環(huán)是一個身份置換,因此任何置換可以分解一組不連續(xù)的循環(huán)(包括1-循環(huán))。定義4.給定一有限數(shù)組X={a1,a2,…,an},一個換位是一個置換f,如存在指數(shù)i,j,f(ai)=aj,f(aj)=ai,且f(ak)=ak,。一個換位是2-循環(huán)。任何循環(huán)能夠分解為一組換位。所以任何置換可以分解為一組換位。給定兩個n組有序序列A={a1,a2,…,an}和B={b1,b2,…,bn},定義以下置換為集合k為PAB最小換位的數(shù)目,即PAB=T1,T2…TK。然后我定義減法B-A=T1,T2…TK粒子的位置可被視為一個m-有序序列,所以兩個粒子位置的減法可以按上定義。定義5.對一個m-有序序列X=(x1,x2,…,xm),移動的粒子表現(xiàn)在X是SL(X,k)={x(1+k)%m,x(2+k)%m,…x(m+k)%m}。定義6.對于一個m-有序序列X=(x1,x2,…,xm),對X的跌倒順序的操作是RE(X)=(xM,xM-1,…,x1)。對一個粒子X,我們定義SL(X,k)=X和RE(X)=X定義7.給定兩個粒子位置Xi={xi1,xi2,...xim}和Xj={xji1,xj2,...xjm},定義他們的減法如下:集合r是一個實值T是一個換位,定義為其中PI是一個恒等排列。重新定義方程2中r1,r2為一個實向量,它的維數(shù)相應的換位的數(shù)目。因此方程2能夠被改寫為:慣性系數(shù)ω是一個常數(shù)小于1,項目排列的高ω可能被忽略。在本文對項目的ω-有序超過2都省略。因此我們有:圖1偽代碼刪除交叉進程圖2刪除交叉進程示意圖總之,提出的離散粒子群優(yōu)化算法在TSP問題可以概括如下(1)初始化粒子群:包括初始化每個粒子的位置和評價每個粒子的適應值fitness。在這一階段,Pg還被搜查和每個顆粒子初始位置Pi。(2)應用每個粒子的PSO優(yōu)化流程:(a)根據(jù)方程(1)-(8)對每個粒子執(zhí)行搜索過程(b)對Pg執(zhí)行刪除交叉進程;(3)判斷終止的標準,即是否迭代達到一定數(shù)量或最好適應值fitness是否到達指定的值。如果滿足標準停止該執(zhí)行,否則請轉(zhuǎn)到步驟2。3.2.數(shù)值結(jié)果為了驗證所提出的離散PSO算法,從TSPLIB圖書館[24]某些情況下被選中的模擬。實驗執(zhí)行環(huán)境在個人電腦上有2GHz處理器和128M內(nèi)存。每個實例運行100次。表1介紹了數(shù)值結(jié)果。第二欄代表每個問題(Opt)的最優(yōu)游覽距離長度,和第七的相對錯誤(Err),相對誤差的計算方法如下:Err=(Ave?Opt)/Opt×100%(9)表1顯示,擬出的離散粒子群優(yōu)化方法可用于解決TSP問題有效性。從表1可以看出,在5次測試問題,最大的相對誤差為4.1673%,平均相對誤差3.5496%??梢钥闯?,當問題的規(guī)模介于50至80,我們的結(jié)果是公平的良好的,[15-17]表明,已解決TSP問題規(guī)模均小于17個城市。很明顯該算法解決同樣規(guī)模的問題與現(xiàn)有的算法比具有優(yōu)勢。4離散粒子群優(yōu)化方法解決GTSP問題4.1.聲明廣義的TSP(GTSP)廣義旅行商問題(GTSP)

由Henry-Labordere,Saskena,Srivastava提出,在并通過福利機構(gòu)在計算機條件下記錄平衡和訪問測序。20世紀60年代。GTSP有許多廣泛的應用領(lǐng)域,如涉及旅游的問題,物流系統(tǒng)設計,后箱收集,隨機車輛路徑與arc路由,和許多其他[21,25]。在GTSP問題,候選城市劃分成若干組。一些城市可能屬于不止一個組,而其他一些城市可能只是在一個組。GTSP的目的是尋求最小的長度行周期。根據(jù)風格,存在著兩種不同類型的GTSP周期:通行路線經(jīng)過組里每個頂點。每個通行線路至少進過每個組一個頂點。為簡潔,只有第一種情況是在本文件。4.2.離散粒子群優(yōu)化方法算法的GTSP為了方便起見,Wu等提出了廣義染色體(GC)在[22]介紹了。假設有N個候選城市分為m組(包括單個城市)。即,任意給定城市ci(i=1,2,…n),一定存在至少一組弧Vj(j=1,2,…m)滿足ci∈Vj。然后遍歷由圖中m個頂點和m頂點連成m條連線。如果屬于Vj的城市數(shù)大于1和如果屬于Vj的城市成為元素,那么一組弧Vj(j=1,2,…m)被認為是一個超級頂點。如果Vj={ci}(j=1,2,…m)城市ci(i=1,2,…n)被認為是一組分散的頂點。然后頂點可以根據(jù)他們的類型分為兩類,即,超級頂點或分散的一個,定義超級定帶你的數(shù)目為,分散頂點數(shù)目為,所有的超級頂點,所有分散頂點為,相關(guān)的所有廣義的頂點被定義為,圖3.廣義染色體(10)基于wu等編碼技術(shù)等開發(fā),在[23]第2節(jié)的正文中的一部分,仍然是“置換”的概念說明,我們考慮增加兩個本地搜索的進程和發(fā)展的離散算法方法GTSP。方程(1)仍然是工作中的方法。但是通過對粒子的位置Xi和速度Vi不同于存在超頂點在GTSP問題的TSP問題。Xi代碼可命名為:正文部分如第二部分為計算粒子的速度,即:不同粒子的位置相減如方程(6)。XH不是一個不重復的序列,所以我們給于更新XH的速度如下:為了加快收斂,算法中使用了兩個局部搜索技術(shù)。首先一個地方搜索添加到頭部。對于每一個相同的頭部,最好的指數(shù)在相應超頂點是要首先搜查,然后原來的指數(shù)改為最好。上述本地搜索進程名本地搜索I,這可以被視為作為一個貪婪搜尋。第二個本地搜索行為自身搜索,這是用來交換在每個迭代中兩個廣義頂點的位置隨機。如果然后適應值fitness增加則交換保持不變,否則其他原始粒子保持不變。相應地,這是本地搜索二的命名,可以被看作是一個隨機搜索??傊?,離散粒子群優(yōu)化方法解決GTSP可描述為:(1)初始化粒子群:包括初始化每個粒子的頭部和身體,和計算每個粒子適應值fitness。然后搜索Pg和每個粒子Pi,設為初始位置。(2)適應每個粒子的算法流程(a)根據(jù)方程(17)-(18)執(zhí)行對每個粒子的搜索進程;(b)執(zhí)行局部搜索Ⅰ(c)執(zhí)行局部搜索Ⅱ(3)判斷終止條件,即是否達到給定迭代數(shù)目或是否達到給定適應值fitness。如果滿足停止執(zhí)行,否則轉(zhuǎn)到(2)。4.3.數(shù)值結(jié)果從TSPLIB圖書館[24]19實例已選定審查的有效性,提出的算法為解決GTSP問題。這些事例都最初生成的測試標準的TSP算法來測試GTSP算法。Fischetti等在[22]對“廣義subtour消除制約”提出提一個準確的分離算法。這樣我們就可以在不同的運行提供數(shù)據(jù)秩序得到相同的分割結(jié)果。同樣的(詳情可參考在第3節(jié)[22])。因此,準確分離算法可用來生成測試數(shù)據(jù)的不同的算法。在下面的實驗中,規(guī)模為80。表2列出了計算結(jié)果。第二列表明每個問題的最佳游覽的確切長度[22]。表2顯示,提出的離散粒子群優(yōu)化方法可用于解決GTSP有效性。從表2可以看出,在19測試的問題,最大相對誤差為9.69%和所有測試的平均相對誤差是4.25%。因此,計算結(jié)果是相當好的。表25.結(jié)論關(guān)于TSP的問題,通過增加了一個不確定的戰(zhàn)略加入方法中提出一種新型的離散算法。此外,通過引入廣義染色體技術(shù),該算法延伸解決廣義的TSP問題。盡我們所知,這是第一次以該算法為基礎(chǔ)的算法用于解決GTSP問題。數(shù)值結(jié)果表明,該算法有效的。它也表明,這種算法比現(xiàn)有的算法可以解決更大規(guī)模問題。參考文獻 [1]J.Kennedy,R.C.Eberhart,Particleswarmoptimization,in:ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks,Perth,Australia,vol.4,IEEEServiceCenter,Piscataway,NJ,1995,pp.1942–1948.[2]P.J.Angeline,Evolutionaryoptimizationversusparticleswarmoptimization:philosophyandperformancedifferences,EvolutionaryProgramming7(1998)601–610.[3]M.Clerc,J.Kennedy,Theparticleswarm-explosion,stability,andconvergenceinamultidimensionalcomplexspace,IEEETransactionsonEvolutionaryComputation6(2002)58–73.[4]I.C.Trelea,Theparticleswarmoptimizationalgorithm:convergenceanalysisandparameterselection,InformationProcessingLetters85(2003)317–325.[5]J.F.Chang,S.C.Chu,J.F.Roddick,J.S.Pan,Aparallelparticleswarmoptimizationalgorithmwithcommunicationstrategies,JournalofInformationScienceandEngineering4(21)(2005)809–818.[6]J.Kennedy,R.C.Eberhart,Discretebinaryversionoftheparticleswarmalgorithm,in:ProceedingsoftheIEEEInternationalConferenceonSystems,ManandCybernetics,vol.5,Orlando,Florida,USA,1997,pp.4104–4108.[7]M.Clerc,in:DiscreteParticleSwarmOptimization,illustratedbytheTravelingSalesmanProblemNewOptimizationTechniquesinEngineering,Springer,2004,pp.219–239.[8]R.E.Bellman,Dynamicprogrammingtreatmentofthetravelingsalesmanproblem,JournaloftheACM9(1962)61–63.[9]M.Bellmore,G.L.Nemhauser,Thetravelingsalesmanproblem:asurvey,OperationsResearch16(1968)538–558.[10]D.E.Goldberg,Messygeneticalgorithms:motivation,analysis,andfirstresults,ComplexSystems3(1989)493–530[11]G.Ausiello,M.Demange,L.Laura,V.Paschos,Algorithmsfortheon-linequotatravelingsalesmanproblem,InformationProcessLetters92(2004)89–94.[12]T.Munakata,Y.Nakamura,Temperaturecontrolforsimulatedannealing,PhysicalReviewE64(2001)046127.[13]F.V.Fomin,A.Lingas,Approximationalgorithmsfortimedependentorienteering,InformationProcessLetters83(2002)57–62.[14]L.Huang,C.G.Zhou,K.P.Wang,Hybridantcolonyalgorithmfortravelingsalesmanproblem,ProgressinNaturalScience4(13)(2003)295–299.[15]M.Clerc,Discreteparticleswarmoptimizationillustratedbythetravelingsalesmanproblem,,2000.[16]T.Hendtlass,PreservingDiversityinParticleSwarmOptimization,in:LectureNotesinComputerScience,vol.2718,Springer,2003,pp.4104–4108.[17]K.P.Wang,L.Huang,C.G.Zhou,W.Pang,Particleswarmoptimizationfortravelingsalesmanproblem,InternationalConferenceonMachineLearningandCybernetics3(2003)1583–1585.[18]A.L.Henry-Labordere,Therecordbalancingproblem:adynamicprogrammingsolutionofageneralizedtravelingsalesmanproblem,RIROB2(1969)43–49.[19]J.P.Saskena,Mathematicalmodelforschedulingclientsthroughwelfareagencies,CORSJ.8(

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論