離散粒子群優(yōu)化算法求解旅行商問題

《離散粒子群優(yōu)化算法求解旅行商問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、CN43—1258／TPISSN1007—130X計(jì)算機(jī)工程與科學(xué)COMPUTERENGINEERING＆SCIENCE2008年第30卷第10期V01．30，No．i0，2008文章編號：1007—130X(2008)10-0064—03離散粒子群優(yōu)化算法求解旅行商問題ADiscreteParticleSwarmOptimizationforTSP劉伯穎1，吳敬松1．鐔鐵春2．李世杰1L1UB伊yin窖，WUJing-son91ICHANTie．-chun2．LIShi-jiel【1．河北工業(yè)大

2、學(xué)教務(wù)處。天津300130；2．河北工業(yè)大學(xué)外事辦，天津300130)(1．SectionofTeachingAffairs，HebeiUniversityofTechnology．Tianjin300130；2．SectionofForeignMfairs，HebeiUniversityofTechnology。Tianjin300130．China)摘要：在優(yōu)化領(lǐng)域，粒子群算法適用于求解連續(xù)優(yōu)化問題，而在離散優(yōu)化上的應(yīng)用還相對較少。本文在介紹基本粒子群優(yōu)化算法的基礎(chǔ)上，分析了粒子群優(yōu)化算法在經(jīng)

3、典旅行商問題中的應(yīng)用性能及粒子群算法求解旅行商問題的相關(guān)操作。使用Ulysses等標(biāo)準(zhǔn)TsP測試數(shù)據(jù)進(jìn)行了相關(guān)實(shí)驗(yàn)，并通過不同的參數(shù)設(shè)置對實(shí)驗(yàn)結(jié)果進(jìn)行了性能分析和比較。Abstract：Thepaperintroducesbasicparticleswarm．optimizationandanalysesitsuseinthetravelingsalesmanprob—Iern．ParticleSwarmOptimization(PSO)isanewkindofevolutionarycomput

4、ation，wkchhasbeenprovedtobeapowerfulglobaloptimizationmethod．Intheoptimizationfield，PSOissuitableforcontinuousoptimization，anditisrarelyusedindis—creteoptimization．Therefore，thepaperstudieshowtOusePSOinsolvingdiscreteoptimizationproblems．Andsomeexper-

5、imentsaredoneandtheresultsoftheexperimentsareanalyzed．關(guān)鍵詞：粒子群優(yōu)化；旅行商問題；離散優(yōu)化Keywords：particleswalTnoptimization；travelingsalesmanproblem；discreteoptimization中圖分類號：TPl8文獻(xiàn)標(biāo)識碼：A1引言pso是Kennedy和Eberhart于1995年提出的[11，是一種新型的進(jìn)化計(jì)算技術(shù)。它源于鳥群和魚群群體運(yùn)動行為的研究，概念簡單，實(shí)現(xiàn)容易。短短

6、幾年時(shí)間，出現(xiàn)了很多改進(jìn)的Pso算法[21，并且已經(jīng)應(yīng)用于多種學(xué)科和工程領(lǐng)域，目前已被“國際演化計(jì)算會議”(CEC)列為討論專題之一。PSO是函數(shù)優(yōu)化的有效工具。在優(yōu)化領(lǐng)域，PSO適用于求解連續(xù)優(yōu)化問題[3．“，而在離散優(yōu)化上的應(yīng)用還很少[5]且效果大都不夠理想，它們都是從要解決的具體問題的特點(diǎn)人手，有針對性地對基本PSO算法做一些局部修改來達(dá)到求解目的[6．71。為使PSO能在離散問題的解決中發(fā)揮出像解決連續(xù)問題一樣的高效快速作用，本文研究如何利用粒子群算法求解TsP問題，并分析了算法的性能。2

7、基本粒子群算法PSO的基本概念源于對鳥群捕食行為的研究，它是從這種生物群行為特性中得到啟發(fā)并應(yīng)用于求解優(yōu)化問題。在PSO中，每個(gè)優(yōu)化問題的潛在解都可以想象成d維搜索空問上的一個(gè)點(diǎn)，我們稱之為“粒子”。粒子在搜索空間中以一定的速度飛行，這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來動態(tài)調(diào)整。假設(shè)在一個(gè)D維的目標(biāo)搜索空間中有m個(gè)粒子組成一個(gè)群落，其中第i個(gè)粒子表示為一個(gè)D維的向量Xi=(xil，xi2，?，xiD)，i=1，2，?，m。換言之，每個(gè)粒子的位置就是一個(gè)潛在的解。將五代入一個(gè)目標(biāo)函數(shù)就可以

8、計(jì)算出其適應(yīng)值，根據(jù)適應(yīng)值的大小衡量Xi的優(yōu)劣。第i粒子的“飛翔”速度也是一個(gè)D維的向量，記為Ⅵ=(v／1，v／2，?，v／D)。記第i個(gè)粒子迄今為止搜索到的最優(yōu)位置為pt=(pil，pi2，?，piD)，整個(gè)粒子迄今為止搜索到的最優(yōu)位置為p。=(pgl，p92，?，pgD)。Kennedy和Eberhart最早提出的PSO算法采用下列公式對粒子操作：坩1=Ⅵ+d+?！?p；一剛)+c2Xr2×(P：一X÷)(1)Xrl=Xj+"+1(2)其中，盧l，2，?，m；k為迭代次數(shù)，學(xué)習(xí)