进化粒子群算法在TSP中的应用

西南交通大学本科毕业设计（论文）第I页进化粒子群算法在TSP中的应用摘要粒子群优化算法是一种新型的进化计算技术，由Eberhart博士和Kennedy博士于1995年提出。PSO算法已经被证明是一种有效的全局优化方法，并且广泛应用于函数优化，神经网络训练以及模糊系统控制等领域。目前对粒子群优化算法的研究尚处于初期，它今后的发展还有许多工作需要不断充实提高。因此以粒子群优化算法为主要研究对象，寻找求解实际问题的更加有效的改进算法是很有意义的。旅行商问题(TravelingSalesmanProblem-TSP)是图论中一个经典的组合优化问题，是一个典型的NP难题，许多实际问题都可以转化为旅行商问题。本文对一种新的进化粒子群算法在TSP中的应用研究。本文首先分析了粒子群优化算法的原理，应用粒子群优化算法的步骤，以及算法中经验参数的设置，总结了目前PSO算法研究的成果，对比分析了目前对粒子群优化算法的多种改进。其次，基于对粒子群优化算法原理的分析，实现了一种基于TSP的改进的粒子群优化算法：求解TSP的混合粒子群算法，结合遗传算法、蚁群算法和模拟退火算法的思想来解决TSP问题。最后，本文将改进的粒子群算法在burma14和oliver30这两个TSP实例中进行了仿真，得到了较为满意的结果。关键词：粒子群优化算法；旅行商问题；混合粒子群算法第II页AbstractParticleSwarmOptimization(PSO)isanewkindofevolutionarycomputationandwasoriginallyintroducedbyEberhartandKennedyin1995.Ithassinceproventobeapowerfulglobaloptimizationmethod.PSOhasbeenwidelyappliedinfunctionoptimization,neuralnetworktraining,andfuzzysystemcontrol,etc.However,asPSOisanewlyemergingoptimizationmethod,therearemanyresearchworkshouldbesubstantiated.SoitisverysignificanttoseekmorepowerfulimprovedalgorithmsbasedonPSOtosolveconcreteengineeringproblems.TSP(TravelingSalesmanProblem-TSP)isaclassicgraphtheory,combinatorialoptimizationproblem,isatypicalNPproblem,manypracticalproblemscanberansformedintotravelingsalesmanproblem.Inthispaper,theevolutionofanewparticleswarmalgorithmintheapplicationofTSP.Firstly,elementsofPSOisanalyzedinthisthesis.BasedontheanalysisoncharacteristicsofPSO,thealgorithmissummarized.Theexperiencedsettingsofparametersarealsogiven.Inthethesis,thepresentproductionsofPSOaresummarizedandcompared.Secondly,basedontheprincipleofparticleswarmoptimizationanalysis,therealizationofaTSPbasedontheimprovedparticleswarmoptimizationalgorithm:SolvingtheTSPhybridparticleswarmalgorithm,combinedwithgeneticalgorithm,antcolonyalgorithmandsimulatedannealingalgorithmtosolvetheTravelingSalesmanProblem.Finally,thenewParticleSwarmOptimizationisusedtoemulateintwoofTSPexample:buram14andoliver30andobtainedsatisfactoryresults.Keywords:ParticleSwarmOptimizationTravelingSalesmanProblemHybridParticleSwarmOptimizationAlgorithm第III页目录摘要................................................................................................................................IABSTRACT..........................................................................................................................II第1章绪论.....................................................................................................................11.1引言.......................................................................................................................11.2研究背景...............................................................................................................31.2.1进化算法简介.............................................................................................31.2.2群智能简介.................................................................................................31.2.3粒子群优化算法的概述.............................................................................51.2.4旅行商问题.................................................................................................61.3粒子群优化算法的国内外研究现状.....................................................................61.4粒子群优化算法的研究意义.................................................................................8第2章粒子群优化算法.....................................................................................................92.1粒子群算法的原理.................................................................................................92.2粒子群优化算法和遗传算法(GA)的比较..........................................................112.3粒子群优化算法的特点及应用关键...................................................................122.3.1PSO的关键术语.......................................................................................132.3.2PSO算法的基本步骤和流程...................................................................132.3.3应用PSO算法步骤..................................................................................142.3.4PSO参数设置...........................................................................................15第3章PSO算法的改进算法............................................................................................173.1基于惯性权值的改进...........................................................................................173.2基于加速因子的PSO改进..................................................................................183.3基于邻近群拓扑的改进.......................................................................................183.4基于种群规模的改进...........................................................................................20第4章一种改进的求解TSP混合粒子群优化算法.......................................................214.1混合粒子群算法的概述.......................................................................................214.2变异操作...............................................................................................................214.3交叉操作...............................................................................................................224.4混合粒子群算法.......