計(jì)算機(jī)專(zhuān)業(yè)畢業(yè)論文外文翻譯(含原文)

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

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

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

由Henry-Labordere，Saskena，Srivastava提出，在并通過(guò)福利機(jī)構(gòu)在計(jì)算機(jī)條件下記錄平衡和訪(fǎng)問(wèn)測(cè)序。20世紀(jì)60年代。GTSP有許多廣泛的應(yīng)用領(lǐng)域，如涉及旅游的問(wèn)題，物流系統(tǒng)設(shè)計(jì)，后箱收集，隨機(jī)車(chē)輛路徑與arc路由，和許多其他[21,25]。在GTSP問(wèn)題，候選城市劃分成若干組。一些城市可能屬于不止一個(gè)組，而其他一些城市可能只是在一個(gè)組。GTSP的目的是尋求最小的長(zhǎng)度行周期。根據(jù)風(fēng)格，存在著兩種不同類(lèi)型的GTSP周期：通行路線(xiàn)經(jīng)過(guò)組里每個(gè)頂點(diǎn)。每個(gè)通行線(xiàn)路至少進(jìn)過(guò)每個(gè)組一個(gè)頂點(diǎn)。為簡(jiǎn)潔，只有第一種情況是在本文件。4.2.離散粒子群優(yōu)化方法算法的GTSP為了方便起見(jiàn)，Wu等提出了廣義染色體（GC）在[22]介紹了。假設(shè)有N個(gè)候選城市分為m組（包括單個(gè)城市）。即，任意給定城市ci（i=1,2,…n）,一定存在至少一組弧Vj(j=1,2,…m)滿(mǎn)足ci∈Vj。然后遍歷由圖中m個(gè)頂點(diǎn)和m頂點(diǎn)連成m條連線(xiàn)。如果屬于Vj的城市數(shù)大于1和如果屬于Vj的城市成為元素，那么一組弧Vj(j=1,2,…m)被認(rèn)為是一個(gè)超級(jí)頂點(diǎn)。如果Vj={ci}（j=1,2,…m）城市ci（i=1,2,…n）被認(rèn)為是一組分散的頂點(diǎn)。然后頂點(diǎn)可以根據(jù)他們的類(lèi)型分為兩類(lèi)，即,超級(jí)頂點(diǎn)或分散的一個(gè)，定義超級(jí)定帶你的數(shù)目為，分散頂點(diǎn)數(shù)目為，所有的超級(jí)頂點(diǎn)，所有分散頂點(diǎn)為，相關(guān)的所有廣義的頂點(diǎn)被定義為，圖3.廣義染色體（10）基于wu等編碼技術(shù)等開(kāi)發(fā)，在[23]第2節(jié)的正文中的一部分，仍然是“置換”的概念說(shuō)明，我們考慮增加兩個(gè)本地搜索的進(jìn)程和發(fā)展的離散算法方法GTSP。方程(1)仍然是工作中的方法。但是通過(guò)對(duì)粒子的位置Xi和速度Vi不同于存在超頂點(diǎn)在GTSP問(wèn)題的TSP問(wèn)題。Xi代碼可命名為：正文部分如第二部分為計(jì)算粒子的速度，即：不同粒子的位置相減如方程（6）。XH不是一個(gè)不重復(fù)的序列，所以我們給于更新XH的速度如下：為了加快收斂，算法中使用了兩個(gè)局部搜索技術(shù)。首先一個(gè)地方搜索添加到頭部。對(duì)于每一個(gè)相同的頭部，最好的指數(shù)在相應(yīng)超頂點(diǎn)是要首先搜查，然后原來(lái)的指數(shù)改為最好。上述本地搜索進(jìn)程名本地搜索I，這可以被視為作為一個(gè)貪婪搜尋。第二個(gè)本地搜索行為自身搜索，這是用來(lái)交換在每個(gè)迭代中兩個(gè)廣義頂點(diǎn)的位置隨機(jī)。如果然后適應(yīng)值fitness增加則交換保持不變，否則其他原始粒子保持不變。相應(yīng)地，這是本地搜索二的命名，可以被看作是一個(gè)隨機(jī)搜索?？傊x散粒子群優(yōu)化方法解決GTSP可描述為：(1)初始化粒子群：包括初始化每個(gè)粒子的頭部和身體，和計(jì)算每個(gè)粒子適應(yīng)值fitness。然后搜索Pg和每個(gè)粒子Pi，設(shè)為初始位置。(2)適應(yīng)每個(gè)粒子的算法流程(a)根據(jù)方程(17)-(18)執(zhí)行對(duì)每個(gè)粒子的搜索進(jìn)程；(b)執(zhí)行局部搜索Ⅰ(c)執(zhí)行局部搜索Ⅱ（3）判斷終止條件，即是否達(dá)到給定迭代數(shù)目或是否達(dá)到給定適應(yīng)值fitness。如果滿(mǎn)足停止執(zhí)行，否則轉(zhuǎn)到（2）。4.3.數(shù)值結(jié)果從TSPLIB圖書(shū)館[24]19實(shí)例已選定審查的有效性，提出的算法為解決GTSP問(wèn)題。這些事例都最初生成的測(cè)試標(biāo)準(zhǔn)的TSP算法來(lái)測(cè)試GTSP算法。Fischetti等在[22]對(duì)“廣義subtour消除制約”提出提一個(gè)準(zhǔn)確的分離算法。這樣我們就可以在不同的運(yùn)行提供數(shù)據(jù)秩序得到相同的分割結(jié)果。同樣的（詳情可參考在第3節(jié)[22]）。因此，準(zhǔn)確分離算法可用來(lái)生成測(cè)試數(shù)據(jù)的不同的算法。在下面的實(shí)驗(yàn)中，規(guī)模為80。表2列出了計(jì)算結(jié)果。第二列表明每個(gè)問(wèn)題的最佳游覽的確切長(zhǎng)度[22]。表2顯示，提出的離散粒子群優(yōu)化方法可用于解決GTSP有效性。從表2可以看出，在19測(cè)試的問(wèn)題，最大相對(duì)誤差為9.69％和所有測(cè)試的平均相對(duì)誤差是4.25％。因此，計(jì)算結(jié)果是相當(dāng)好的。表25.結(jié)論關(guān)于TSP的問(wèn)題，通過(guò)增加了一個(gè)不確定的戰(zhàn)略加入方法中提出一種新型的離散算法。此外，通過(guò)引入廣義染色體技術(shù)，該算法延伸解決廣義的TSP問(wèn)題。盡我們所知，這是第一次以該算法為基礎(chǔ)的算法用于解決GTSP問(wèn)題。數(shù)值結(jié)果表明，該算法有效的。它也表明，這種算法比現(xiàn)有的算法可以解決更大規(guī)模問(wèn)題。參考文獻(xiàn) [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(