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

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

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

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

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

6、子群算法的基本思想21. 粒子群優(yōu)化算法的基本原理一個由個粒子(Particle)組成的群體(Swarm)在維搜索空間中以一定的速度飛行，每個粒子在搜索時，考慮到了自己搜索到的的歷史最好點和群體內(nèi)(或領(lǐng)域內(nèi))其它粒子的最好點，在此基礎(chǔ)上進行位置(狀態(tài)、也就是解)的變化。第個粒子的位置表示為：第個粒子的速度表示為：，第個粒子所經(jīng)歷的歷史最好點表示為：群體內(nèi)(或領(lǐng)域內(nèi))所有粒子所經(jīng)歷過的最好的點表示為：。一般來說，粒子的位置和速度都是在連續(xù)的實數(shù)空間內(nèi)進行取值，粒子的位置和速度根據(jù)如下方程進行變化 其中，為慣性權(quán)重。和稱為學習因子(Learning Factor)或加速系數(shù)(Acceleratio

7、n Coefficient)，一般為正常數(shù)。學習因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個體學習的能力，從而向自己的歷史最優(yōu)點以及群體內(nèi)或領(lǐng)域內(nèi)的歷史最優(yōu)點靠近。和通常等于2。，是在區(qū)間內(nèi)均勻分布的偽隨機數(shù)。粒子的速度被限制在一個最大的范圍內(nèi)。 當把群體內(nèi)所有粒子都作為領(lǐng)域成員時，得到粒子群優(yōu)化算法的全局版本；當群體內(nèi)部分成員組成領(lǐng)域時得到粒子群優(yōu)化算法的局部版本。局部版本中，一般有兩種方式組成領(lǐng)域，一種是索引號相鄰的粒子組成領(lǐng)域，另一種是位置相鄰的粒子組成領(lǐng)域。粒子群優(yōu)化算法的領(lǐng)域定義策略又可以稱為粒子群的領(lǐng)域拓撲結(jié)構(gòu)。12. 粒子群優(yōu)化算法的流程3. 粒子群優(yōu)化算法的主要構(gòu)成要素1. 群體大小

8、是個整型參數(shù)。當很小的時候，陷入局優(yōu)的可能性很大。然而，群體過大將導致計算時間大幅增加。并且當群體樹木增長至一定水平時，再增長將不再有顯著的作用。當=1時，PSO算法變成基于個體搜索的技術(shù)，一旦陷入局優(yōu)，將不可能跳出。當m很大時，PSO的優(yōu)化能力很好，可是收斂速度將非常慢。2. 學習因子和學習因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個體學習的能力，從而向群體內(nèi)或領(lǐng)域內(nèi)最優(yōu)點靠近。和通常都等于2，不過也可能有其他取值。但是一般等于，并且范圍在0和4之間。3. 最大速度：最大速度決定粒子在一次迭代中最大的移動距離。較大，探索能力增強，但是粒子容易飛過最好的解。較小時，開發(fā)能力增強，但是容易陷入局優(yōu)。有

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

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

11、進行了各種改進。本文采用王嵐3重新定義PSO的運算符號和規(guī)則，引入交換子和交換序的概念，構(gòu)造一種特殊的PSO用于求解TSP的方法。先對這種改進的PSO進行簡略介紹：定義1 設(shè)n個城市的TSP問題的解序列為S=（ai），i=1,2，n.定義交換子SO（i1，i2）為交換解S中的點ai1和ai2，則S=S+ SO（i1，i2）為解S經(jīng)算子SO（i1，i2）操作后的新解，這里為符號“+”賦予了新的含義.例1 有一個有5個城市的TSP問題，其解為S=（1,3,5,2,4），交換算子為SO（1，2），則S=S+SO(1,2)=(1,3,5,2,4)+SO(1,2)=(3,1,5,2,4).定義2 一個或

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

13、定義SS=SS1+SS2。SS和SS1+SS2屬于同一等價集。一般來說，SS不唯一。定義5 在交換序等價集中，擁有最少交換子的序稱為該等價集的基本交換序?？砂慈缦路椒?gòu)造一個基本交換序。設(shè)給定兩個解路徑A和B，需要構(gòu)造一個基本交換序SS，使得B+SS=A。A：（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）；同理，第三個交換子是SO（4,5），得到

14、B3=B2+SO（4,5）=A。這樣就得到一個基本交換序：SS=A-B=（SO（1,3），SO（2,3），SO（4,5）?；綪SO算法中的速度算式在基于以上交換子和交換序的概念下各符號有了新的定義。其中、仍為學習因子，、仍為 0,1內(nèi) 的隨機數(shù)；表示基本交換序以的概率保留，表示基本交換序以的概率保留。由此可以看出的值越大，保留的交換子就越多，的影響就越大；同理，的值越大， 的影響也就越大。這也正是學習因子的含義所在。求解TSP的PSO算法步驟描述如下：（1）. 初始化粒子群，即給群體中每一個粒子賦一個隨機的初始解和交換序；（2）. 如果滿足條件，轉(zhuǎn)步驟（5）；（3）. 根據(jù)粒子的當前位置，計

15、算下一個位置，即新解：i. 計算與之間的差A(yù)，A=，其中A是一個基本交換序表示A作用于得到；ii. 計算B=，其中B也是一個基本交換序；iii. 由計算出速度，并將交換序轉(zhuǎn)換為一個基本交換序；iv. 如果找到一個更好的解，則更新（4）. 如果群體找到一個更好的解，則更新，轉(zhuǎn)步驟（2）；（5）. 輸出結(jié)果。4. 實例驗證表一:中國31個省會城市的坐標城市序號12345678橫坐標13043639417737123488332632384196縱坐標23121315224413991535155612291044城市序號910111213141516橫坐標431243863007256227882

16、38113323715縱坐標79057019701756149116766951678城市序號1718192021222324橫坐標39184061378036764029426334293507縱坐標21792370221225782838293119082376城市序號25262728293031橫坐標3394343929353140254527782370縱坐標2643320132403550235728262975(表中數(shù)據(jù)來自網(wǎng)站本文以中國31個省會城市的旅行商問題作為驗證標準，驗證以上改進的粒子群算法的實用效果。編寫基于以上思想的求解中國31個城市旅行商問題的matlab程序（代碼

17、見附件），當主要參數(shù)為編號snnvmaxc1c2gnmax11003022100（其中snn為最初粒子數(shù)，vmax為最大速度， c1為粒子基于自己當前位置與自己歷史最優(yōu)位置的自我學習因子， c2 為粒子基于自己當前位置與群體最優(yōu)位置的群體學習因子，gnmax為最大迭代次數(shù)。）時，進行十次實驗，得到次數(shù)12345路徑長度3199731653318043194631056次數(shù)678910路徑長度3229833198313353241632964可知第二次得到的結(jié)果最好，其對應(yīng)的遍歷路徑為L: 6 4 11 13 29 21 5 16 14 30 15 28 26 27 25 17 24 20 19

18、 3 22 18 10 2 7 12 1 31 23 8 9 、相應(yīng)最佳粒子變化趨勢及最好路徑圖為：此結(jié)果與其他算法得到的最優(yōu)值相差較大，但是可以看出，粒子確實在往好的方面變化。因此可以嘗試改變參數(shù)，多次試驗，看能否得到更優(yōu)值。5. 算法的改進多次實驗結(jié)果如下：編號snnvmaxc1c2gnmax最優(yōu)值1100301310031556210025131003221131002013100316484100151310032649510010131003178761005131003059071005121003249181005111003316991005231003286310100533100321091115051310031178122005131003210613250513100319401430051310030050153505131003014816400513100310691730051350322221830051315029746193005132002980320300513250305982130051330029042由以上實驗結(jié)果可知，當初始化粒子總數(shù)snn為300，最大速度vmax為5，學習因子c1為1，c2為3，最大迭代次數(shù)為300時（即編號為21的實驗），得到最短遍