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

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

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

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

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

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

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

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

8、域時得到粒子群優(yōu)化算法的局部版本。局部版本中，一般有兩種方式組成領域，一種是索引號相鄰的粒子組成領域，另一種是位置相鄰的粒子組成領域.粒子群優(yōu)化算法的領 域定義策略又可以稱為粒子群的領域拓撲結(jié)構(gòu).1.粒子群優(yōu)化算法的流程更新每個粒子火速葭的八相咻誨個粒子的燈數(shù)適應值更臚每個葭了歷史最優(yōu)也置虹虹群體的七H勢優(yōu)k割“功能：粒子群優(yōu)化算法偽代碼，說明：事例以來問題最小比為目標“參數(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是個整型參數(shù)。當 m很小的時候，陷入局優(yōu)的可能性很大。 然而，群體過大將導致 計算時間大幅增加。并且當群體樹木增長至一定水平時，再增長

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

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

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

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

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

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

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

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

18、 輸出結(jié)果。.實例驗證表一：中國31個省會城市的坐標城市序號12345678橫坐標13043639417737123488332632384196縱坐標23121315224413991535155612291044城市序號910111213141516橫坐標43124386300725622788238113323715縱坐標79057019701756149116766951678城市序號1718192021222324橫坐標39184061378036764029426334293507縱坐標21792370221225782838293119082376城市序號252627282930

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

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

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