資源描述：
《基于改進的粒子群優(yōu)化算法求解tsp問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、基于改進的粒子群優(yōu)化算法求解TSP問題//.paper.edu-1-中國科技論文在線基于改進的粒子群優(yōu)化算法求解TSP問題沐愛勤1,2，張瑞平1*作者簡介：沐愛勤(1978-),女,講師，碩士，主要研究方向：計算數(shù)學(xué)，智能優(yōu)化算法（1.中國礦業(yè)大學(xué)理學(xué)院，江蘇徐州221000；2.徐州空軍學(xué)院基礎(chǔ)部，江蘇徐州221000）摘要：粒子群優(yōu)化算法是一種新型的優(yōu)化算法，主要應(yīng)用于連續(xù)優(yōu)化問題，本文通過引入移動算子和移動序的概念，使粒子群優(yōu)化算法能夠處理離散問題。將改進算法與鄰域相結(jié)合應(yīng)用于旅行商問題的實驗表明該算法在求解組合優(yōu)
2、化問題上的有效性。關(guān)鍵詞：移動算子；粒子群；旅行商問題中圖分類號：TP301SolvingTravelingSalesmanProblemBasedonImprovedParticleSwarmOptimizationAlgorithmMuAiqin1,2,ZhangRuiping1(1.CollegeofScience,ChinaUniversityofMining&Technology,XuZhou,221000;2.FoundationDepartments,XuzhouAirForceAcademy,Xu
3、Zhou,221000)Abstract:PSOisanewoptimizationalgorithmwhichisappliedincontinuousoptimizations.ThispaperdiscussesthediscreteproblembyusingPSOwiththenotionofmobileoperatorsandmobilesequence.CombingtheimprovedPSOandneighborhoods,theexperimentsoftravelingsalesmanproblem
4、showthealgorithm’seffectivenessinsolvingthecombinatorialoptimizationproblem.Keywords:mobileoperators;ParticleSwarmOptimization(PSO);TravelingSalesmanProblem(TSP)0．引言粒子群算法（PSO）[1]是由心理學(xué)家Kennedy和Eberhart博士在1995年共同提出的一種新的模仿鳥群行為的智能優(yōu)化算法。與其它優(yōu)化算法相比，粒子群算法思想直觀、實現(xiàn)簡單而且具有很高的執(zhí)
5、行效率，目前已經(jīng)廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其它應(yīng)用鄰域。旅行商問題（TSP）就是一個典型的組合優(yōu)化問題。其問題可以描述如下：給定n個城市及兩兩城市之間的距離，求經(jīng)過各城市一次且僅一次的最短路徑。傳統(tǒng)的PSO算法定義于連續(xù)的函數(shù)空間，要應(yīng)用到組合優(yōu)化問題上，必須對基本PSO算法進行改造成為離散的PSO，才能應(yīng)用到問題的求解。在應(yīng)用求解TSP的問題中，由于算法有時搜索的解與最優(yōu)解之間只相差一個城市的位置，所以本文考慮引入移動算子及移動序的概念，對基本PSO算法進行改造，并將其應(yīng)用于TSP問題上。1移動
6、算子和移動序定義1設(shè)N個節(jié)點的TSP問題的解序列為),,(21Nnnns;=，Eni∈，定義移動算子),(kisv為解s中的in點移動k位（k為整數(shù)），如果0>k表示向后移動k位，反之0<k表示向前移動k??位，0=k則表示in點不移動。),('kiss+=表示解s經(jīng)過移動算子),(kisv操作后的新解。這里加號被賦予了新的含義。由于TSP問題求解的是一個H圈，解//.paper.edu-2-中國科技論文在線),,(21Nnnn;與解),,,,(1132nnnnnNN??;實際上是同一個解，所以對于
7、移動算子),(kisv可用下面圖來表示。圖1移動算子的定義如果0>k，in點逆時針移動k位，如果0<k，in點則順時針移動
8、k
9、位。例1設(shè)一個五個節(jié)點的TSP問題，)5,4,3,2,1(=s，移動算子sv)2,1(，則)5,4,1,3,2()2,1()5,4,3,2,1()2,1('=+=+=svss如果移動算子為)3,3(sv，則)5,4,2,3,1()3,3()5,4,3,2,1()3,3('=+=+=svss定義2一個或多個移動算子的有序序列就是移動序，記作v.),,,(21lsvs
10、vsvv;=其中l(wèi)svsvsv,,,21;是移動算子，它們之間的順序是有意義的。移動序作用于一個TSP解上意味著這個移動序中的所有移動算子依次作用于該解上。定義3不同的移動序作用于同一解上可能產(chǎn)生相同的新解，所有具有相同效果的移動序的集合稱為移動序的等價集。定義4若干個移動序可以合并成一個新的移動序，定義⊕為兩個移動
