計(jì)算智能課程設(shè)計(jì)-粒子群優(yōu)化算法求解旅行商問題-Matlab實(shí)現(xiàn)

1、摘要：TSP是一個(gè)典型的 NPCI可題。本文首先介紹旅行商問題和粒子群優(yōu)化算法的基本概念。然后構(gòu)造一種基于交換子和交換序口概念的粒子群優(yōu)化算法，通過控制學(xué)習(xí)因子 勒和7、最大速度Vmax ,嘗試求解旅行商問題。本文以中國(guó)31個(gè)省會(huì)城市為例，通過 MATLA叫程實(shí)施對(duì)旅行商問題的求解，得到了一定優(yōu)化程度的路徑，是粒子群優(yōu)化算法在TSP問題中運(yùn)用的一次大膽嘗試。關(guān)鍵字：TSP問題；粒子群優(yōu)化算法；MATLAB中國(guó)31個(gè)城市TSP.粒子群優(yōu)化算法求解旅行商問題1.引言.旅行商問題的概述旅行商問題,即TSP問題(Traveling Salesman Problem)又譯為旅行推銷員問題貨郎擔(dān) 問題，是

2、數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值TSP問題是一個(gè)組合優(yōu)化問題，其描述非常簡(jiǎn)單，但最優(yōu)化求解非常困難，若用窮舉法搜索，對(duì)N個(gè)城市需要考慮 N!種情況并兩兩對(duì)比，找出最優(yōu)，其算法復(fù)雜性呈指數(shù)增長(zhǎng)，即所謂“指數(shù)爆炸”.所以，尋求和研究 TSP問題的有效啟發(fā)式算法，是問題的關(guān)鍵。.粒子群優(yōu)化算法的概述粒子群優(yōu)化算法(Particle Swarm optimization,PSO )又翻譯為粒子群算法、微粒群算法、 或微粒群優(yōu)化算法。是通

3、過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算 法。通常認(rèn)為它是群集智能(Swarm intelligence, SI )的一種。它可以被納入多主體優(yōu)化系統(tǒng)(Multiagent Optimization System, MAOS )。粒子群優(yōu)化算法是由Eberhart 博士和 Kennedy博士發(fā)明.PSO模擬鳥群的捕食行為。一群鳥在隨機(jī)搜索食物，在這個(gè)區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里.但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu) 策略是什么呢.最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問題.PSO中，每個(gè)

4、優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為 粒子所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值 (fitnessvalue),每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離.然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索 .PSO初始化為一群隨機(jī)粒子(隨機(jī)解),然后通過迭代找到最優(yōu)解，在每一次疊代中，粒子通過跟蹤兩個(gè) 極值”來更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解，這個(gè)解叫做個(gè)體極值pBest,另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值 gBesto另外也可以不用整個(gè)種群而只是用其中一部分最優(yōu)粒子的鄰居，那么在所有鄰居中的極值就是局部極值。.粒子群優(yōu)化算法求解旅行商問題旅行商問

5、題是一個(gè)典型的、易于描述卻難于處理的組合優(yōu)化問題，并且是一個(gè)NP完全難題，其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長(zhǎng)的，對(duì)n個(gè)城市而言，可能的路徑總(n-1) !。隨著n的增加，路徑數(shù)將按數(shù)率急劇增長(zhǎng)，即所謂的“指數(shù)爆炸”，所以一般很難精確地求出其最優(yōu)解，因而尋找出其有效的近似求解算法就具有重要的理論意義。而粒子群優(yōu)化算法是解決復(fù)雜問題的有效方法，自然也能應(yīng)用于解決旅行商問題。PSO模擬鳥群的捕食行為。一群鳥在隨機(jī)搜索食物，在這個(gè)區(qū)域里只有一塊食物。所有2的鳥都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn).那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)

6、域。2.粒子群算法的基本思想.粒子群優(yōu)化算法的基本原理一個(gè)由m個(gè)粒子（Particle）組成的群體（Swarm）在D維搜索空間中以一定的速度飛行， 每個(gè)粒子在搜索時(shí)， 考慮到了自己搜索到的的歷史最好點(diǎn)和群體內(nèi)（或領(lǐng)域內(nèi)）其它粒子的最好點(diǎn)，在此基礎(chǔ)上進(jìn)行位置（狀態(tài)、也就是解）的變化。第i個(gè)粒子的位置表示為：x （x，xi2，加）第i個(gè)粒子的速度表示為：vi （Vii，Vi2，ViD）, 1 d D第i個(gè)粒子所經(jīng)歷的歷史最好點(diǎn)表示為1 i m： Pi （Pi1,Pi21 ,Pd）群體內(nèi)（或領(lǐng)域內(nèi)）所有粒子所經(jīng)歷過的最好的點(diǎn)表示為：仇（Pg1，d2，,PgD）o一般來說，粒子的位置和速度都是在連續(xù)的

7、實(shí)數(shù)空間內(nèi)進(jìn)行取值，粒子的位置和速度根據(jù)如下方程進(jìn)行變化k 1kkkkkVdVidCi（PidXd）C2 （PgdXd）k 1 xid其中，為慣性權(quán)重.g和C2稱為學(xué)習(xí)因子（ Learning Factor）或加速系數(shù)（AccelerationCoefficient）, 一般為正常數(shù)。學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力， 從而向自己的歷史最優(yōu)點(diǎn)以及群體內(nèi)或領(lǐng)域內(nèi)的歷史最優(yōu)點(diǎn)靠近。5和5通常等于2.,U0,1，是在0,1區(qū)間內(nèi)均勻分布的偽隨機(jī)數(shù)。粒子的速度被限制在一個(gè)最大Vmax的范圍內(nèi).當(dāng)把群體內(nèi)所有粒子都作為領(lǐng)域成員時(shí)，得到粒子群優(yōu)化算法的全局版本；當(dāng)群體內(nèi)部分成員組成領(lǐng)

8、域時(shí)得到粒子群優(yōu)化算法的局部版本。局部版本中，一般有兩種方式組成領(lǐng)域，一種是索引號(hào)相鄰的粒子組成領(lǐng)域，另一種是位置相鄰的粒子組成領(lǐng)域.粒子群優(yōu)化算法的領(lǐng) 域定義策略又可以稱為粒子群的領(lǐng)域拓?fù)浣Y(jié)構(gòu).1.粒子群優(yōu)化算法的流程更新每個(gè)粒子火速葭的八相咻誨個(gè)粒子的燈數(shù)適應(yīng)值更臚每個(gè)葭了歷史最優(yōu)也置虹虹群體的七H勢(shì)優(yōu)k割“功能：粒子群優(yōu)化算法偽代碼，說明：事例以來問題最小比為目標(biāo)“參數(shù)：N為群悻規(guī)模procedure PSOfar eac- particle finitialize velocity Vj ar；C position Xi tar pirticlfi iE,ja；Ydta pftrt i

9、 c i 5 4nd 巴商t pltest J Xiend forqiest= rr.i r f pilest?1while njL m8口for L- 1 to WUJate the velociLy and position of particle iEvluJte pdirticle iif fit (Ai) gBes t1： pBesti:end fornd whilprint 中熱fSTnd procadurA.粒子群優(yōu)化算法的主要構(gòu)成要素群體大小mm是個(gè)整型參數(shù)。當(dāng) m很小的時(shí)候，陷入局優(yōu)的可能性很大。 然而，群體過大將導(dǎo)致 計(jì)算時(shí)間大幅增加。并且當(dāng)群體樹木增長(zhǎng)至一定水平時(shí)，再增長(zhǎng)

10、將不再有顯著的作用。當(dāng)m=1時(shí)，PSO算法變成基于個(gè)體搜索的技術(shù)，一旦陷入局優(yōu)，將不可能跳出。當(dāng)m很大時(shí)，PSO的優(yōu)化能力很好，可是收斂速度將非常慢.學(xué)習(xí)因子c1和c2學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向群體內(nèi)或 領(lǐng)域內(nèi)最優(yōu)點(diǎn)靠近。g和C2通常都等于2,不過也可能有其他取值。但是一般Ci等于C2,并且范圍在0和4之間。最大速度：ax最大速度決定粒子在一次迭代中最大的移動(dòng)距離。Vmax較大，探索能力增強(qiáng)，但是粒子容易飛過最好的解。1_較小時(shí)，開發(fā)能力增強(qiáng)，但是容易陷入局優(yōu).有分析和實(shí)驗(yàn) 表明，設(shè)定Vmax的作用可以通過慣性權(quán)重的調(diào)整來實(shí)現(xiàn)。所以現(xiàn)在的實(shí)驗(yàn)基本上使用 Vm

11、ax進(jìn)行初始化，將Vmax設(shè)定為每維變量的變化范圍，而不必進(jìn)行細(xì)致的選擇與調(diào)節(jié)。 4.慣性權(quán)重智能優(yōu)化方法的運(yùn)行是否成功，探索能力和開發(fā)能力的平衡是非常關(guān)鍵的。對(duì)于 粒子群優(yōu)化算法來說，這兩種能力的平衡就是靠慣性權(quán)重來實(shí)現(xiàn)的。較大的慣性權(quán)重使 粒子在自己原來的方向上具有更大的速度，從而在原方向上飛行更遠(yuǎn)，具有更好的搜索能力；較小的慣性權(quán)重使粒子繼承了較少的原方向上的速度，從而飛行較近，具有更 好的開發(fā)能力。通過調(diào)節(jié)慣性權(quán)重能夠調(diào)節(jié)粒子群的搜索能力。.領(lǐng)域拓?fù)浣Y(jié)構(gòu)全局版本粒子群優(yōu)化算法將整個(gè)群體作為粒子的領(lǐng)域，速度快，不過有時(shí)會(huì)陷入 局優(yōu)；局部版本粒子群優(yōu)化算法將索引號(hào)相近或者位置相近的個(gè)體作為

12、粒子的領(lǐng)域， 收斂速度慢一點(diǎn)，不過很難陷入局部最優(yōu)。顯然，全局版本的粒子群優(yōu)化算法可以看作 局部版本粒子群優(yōu)化算法的一個(gè)特例，即將整個(gè)群體都作為領(lǐng)域. 停止準(zhǔn)則一般使用最大迭代次數(shù)或可以接受的滿意解作為停止準(zhǔn)則.粒子空間的初始化較好地選擇粒子的初始化空間，將大大縮短收斂時(shí)間。這是問題依賴的。.粒子群算法求解旅行商問題的流程粒子群優(yōu)化算法雖然成功地應(yīng)用于連續(xù)優(yōu)化的問題中，而在離散上的研究和應(yīng)用還很 少，尤其是用PSO解決TSP問題是一個(gè)新的研究方向 。最初的PSO是用來解決連續(xù)空間的問題的，為了適合求解TSP問題，人們對(duì)算法進(jìn)行了各種改進(jìn).本文采用王嵐3重新定義PSO的運(yùn)算符號(hào)和規(guī)則，引入交換子

13、和交換序的概念， 構(gòu)造一種特殊的 PSO用于求解TSP的方法。先對(duì)這種改進(jìn)的 PSO進(jìn)行簡(jiǎn)略介紹：定義1設(shè)n個(gè)城市的TSP問題的解序列為S=(聞，i=1, 2,，n.定義交換子SO (ii, i2)為交換解S中的點(diǎn)aii和ai2,則S=S+ SO (ii,i2)為解S經(jīng)算子SO (ii, i2)操作后的新解, 這里為符號(hào)“ +”賦予了新的含義.例1有一個(gè)有5個(gè)城市的TSP問題，其解為 S=(1, 3,5, 2,4),交換算子為 SO(1, 2)： 則 S =S+SO(12) =(1 , 3,5, 2, 4) +SO(1, 2) = (3, 1, 5, 2,4)。定義2 一個(gè)或多個(gè)交換子的有序隊(duì)

14、列就是交換序，記作SS其中，SS=(S。，SQ,，SOn),SOi, SO2,，SOn是交換子，它們之間的順序是有意義的。交換序作用于一個(gè) TSP解上意味著這個(gè)交換序中的所有交換子依次作用于該解上，即S=S+SS=S +SQ, SO2,，SOn)= (S+SO) +SQ+S。定義3不同的交換序作用于同一解上可能產(chǎn)生相同的新解，所有有相同效果的交換序的集合稱為交換序的等價(jià)集.定義4若干個(gè)交換序可以合并成一個(gè)新的交換序，定義為兩個(gè)交換序的合并算子。例2設(shè)兩個(gè)交換序SS和S0按先后順序作用于解 S上，得到新解S。假設(shè)另外有一個(gè) 交換序SS作用于同一解上，能夠得到相同的解 S,可定義SS =SSSSo

15、 SSW SS+S8屬于同 一等價(jià)集.一般來說，s$t唯一。定義5在交換序等價(jià)集中，擁有最少交換子的序稱為該等價(jià)集的基本交換序。可按如 下方法構(gòu)造一個(gè)基本交換序設(shè)給定兩個(gè)解路徑 A和B,需要構(gòu)造一個(gè)基本交換序SS,使得B+SS=AA: (1,2,3, 4, 5) ; B: (2, 3,1,5, 4)可以看出,A (1) =B(3)=1所以第一個(gè)交換子是 SO (1,3), B1=B+SO(1,3)，得到 B1 (1,3, 2,5, 4); A(2) =B1(3)=2,所以第二個(gè)交換子是 SO(2, 3), B2=B1+SO(2,3)，得到 B2= ( 1, 2,3,5,4); 同理，第三個(gè)交換

16、子是 SO (4,5),得到B3=B2+SO (4,5) =A.這樣就得到一個(gè)基本交換序：基本pso算法中的速度算式vd1vidSS=A-B= (SO(1,3), SO (2, 3), SO(4, 5).G 2； W) g (pkd xd)在基于以上交換子和交換序的概念下各符號(hào)有了新的定義。其中G、C2仍為學(xué)習(xí)因子,仍為0,1 內(nèi)的隨機(jī)數(shù)；c1(dX：)表示基本交換序 ：X：)以J的概率保留，g (pgd xd)表示基本交換序(pkd xd)以C2的概率保留。由此可以看出g的值越大，：Xid)保留的交換子就越多，pd的影響就越大；同理，C2的值越大，p；d的影響也就越大。這也正是學(xué)習(xí)因子的含義

17、所在。求解TSP的PSO算法步驟描述如下：.初始化粒子群，即給群體中每一個(gè)粒子賦一個(gè)隨機(jī)的初始解和交換序；.如果滿足條件，轉(zhuǎn)步驟(5);.根據(jù)粒子的當(dāng)前位置 xd ,計(jì)算下一個(gè)位置X：1,即新解：計(jì)算pid與xd之間的差A(yù), A=(p： Xid)淇中A是一個(gè)基本交換序表示A作用于Xid得到pid ；計(jì)算B=(pkd Xid),其中B也是一個(gè)基本交換序；.1k 1k,kkk kk 1 tz a-k 1 卡上由VdVdG(pidXd)C2(pgdXd )計(jì)算出速度Vid，并將父換序Vid轉(zhuǎn)換為一個(gè)基本交換序；如果找到一個(gè)更好的解，則更新pi.如果群體找到一個(gè)更好的解，則更新pg ,轉(zhuǎn)步驟(2);.

18、 輸出結(jié)果。.實(shí)例驗(yàn)證表一：中國(guó)31個(gè)省會(huì)城市的坐標(biāo)城市序號(hào)12345678橫坐標(biāo)13043639417737123488332632384196縱坐標(biāo)23121315224413991535155612291044城市序號(hào)910111213141516橫坐標(biāo)43124386300725622788238113323715縱坐標(biāo)79057019701756149116766951678城市序號(hào)1718192021222324橫坐標(biāo)39184061378036764029426334293507縱坐標(biāo)21792370221225782838293119082376城市序號(hào)252627282930

19、31橫坐標(biāo)3394343929353140254527782370縱坐標(biāo)2643320132403550235728262975（表中數(shù)據(jù)來自網(wǎng)站 http : /view/c7a78f0b581b6bd97f19ea55.html）本文以中國(guó)31個(gè)省會(huì)城市的旅行商問題作為驗(yàn)證標(biāo)準(zhǔn)，驗(yàn)證以上改進(jìn)的粒子群算法的實(shí)用效果。編寫基于以上思想的求解中國(guó)31個(gè)城市旅行商問題的 matlab程序（代碼見附件），當(dāng)主要參數(shù)為值優(yōu)最代每4x 102343533y標(biāo)坐縱市城5004000350030002500200015001000050迭代數(shù)10010002000300040005000城市橫坐標(biāo)x此結(jié)果與

20、其他算法得到的最優(yōu)值相差較大,但是可以看出，粒子確實(shí)在往好的方面變編psnnvmaxC1C2gnmax11003022100（其中snn為最初粒子數(shù)，vmax為最大速度，ci為粒子基于自己當(dāng)前位置與自己歷史最優(yōu)位置的自我學(xué)習(xí)因子，C2為粒子基于自己當(dāng)前位置與群體最優(yōu)位置的群體學(xué)習(xí)因子，gnmax為最大迭代次數(shù)。）時(shí)，進(jìn)行十次實(shí)驗(yàn)得到次數(shù)12345路徑長(zhǎng)度3199731653318043194631056次數(shù)678910路徑長(zhǎng)度3229833198313353241632964可知第二次得到的結(jié)果最好，其對(duì)應(yīng)的遍歷路徑為L(zhǎng):641113292151614301528262725172420193

21、22181027121312389卜相應(yīng)最佳粒子變化趨勢(shì)及最好路徑圖為:化。因此可以嘗試改變參數(shù)，多次試驗(yàn)，看能否得到更優(yōu)值。.算法的改進(jìn)多次實(shí)驗(yàn)結(jié)果如下:編RsnnvmaxCiC2gnmax最優(yōu)值1100301310031556210025131003221131002013100316484100151310032649510010131003178761005131003059071005121003249181005111003316991005231003286310100533100321091115051310031178122005131003210613250513100319401430051310030050153505131003014816400513100310691730051350322221830051315029746193005132002980320300513250305982130051330029042由以上實(shí)驗(yàn)結(jié)果可知，當(dāng)初始化粒子總數(shù)snn為300,最大速度vmax為5,學(xué)習(xí)因子C1為1, C2為