离散粒子群优化算法求解旅行商问题

《离散粒子群优化算法求解旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、CN43—1258／TPISSN1007—130X计算机工程与科学COMPUTERENGINEERING＆SCIENCE2008年第30卷第10期V01．30，No．i0，2008文章编号：1007—130X(2008)10-0064—03离散粒子群优化算法求解旅行商问题ADiscreteParticleSwarmOptimizationforTSP刘伯颖1，吴敬松1．镡铁春2．李世杰1L1UB伊yin窖，WUJing-son91ICHANTie．-chun2．LIShi-jiel【1．河北工业大

2、学教务处。天津300130；2．河北工业大学外事办，天津300130)(1．SectionofTeachingAffairs，HebeiUniversityofTechnology．Tianjin300130；2．SectionofForeignMfairs，HebeiUniversityofTechnology。Tianjin300130．China)摘要：在优化领域，粒子群算法适用于求解连续优化问题，而在离散优化上的应用还相对较少。本文在介绍基本粒子群优化算法的基础上，分析了粒子群优化算法在经

3、典旅行商问题中的应用性能及粒子群算法求解旅行商问题的相关操作。使用Ulysses等标准TsP测试数据进行了相关实验，并通过不同的参数设置对实验结果进行了性能分析和比较。Abstract：Thepaperintroducesbasicparticleswarm．optimizationandanalysesitsuseinthetravelingsalesmanprob—Iern．ParticleSwarmOptimization(PSO)isanewkindofevolutionarycomput

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

5、imentsaredoneandtheresultsoftheexperimentsareanalyzed．关键词：粒子群优化；旅行商问题；离散优化Keywords：particleswalTnoptimization；travelingsalesmanproblem；discreteoptimization中图分类号：TPl8文献标识码：A1引言pso是Kennedy和Eberhart于1995年提出的[11，是一种新型的进化计算技术。它源于鸟群和鱼群群体运动行为的研究，概念简单，实现容易。短短

6、几年时间，出现了很多改进的Pso算法[21，并且已经应用于多种学科和工程领域，目前已被“国际演化计算会议”(CEC)列为讨论专题之一。PSO是函数优化的有效工具。在优化领域，PSO适用于求解连续优化问题[3．“，而在离散优化上的应用还很少[5]且效果大都不够理想，它们都是从要解决的具体问题的特点人手，有针对性地对基本PSO算法做一些局部修改来达到求解目的[6．71。为使PSO能在离散问题的解决中发挥出像解决连续问题一样的高效快速作用，本文研究如何利用粒子群算法求解TsP问题，并分析了算法的性能。2

7、基本粒子群算法PSO的基本概念源于对鸟群捕食行为的研究，它是从这种生物群行为特性中得到启发并应用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空问上的一个点，我们称之为“粒子”。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。假设在一个D维的目标搜索空间中有m个粒子组成一个群落，其中第i个粒子表示为一个D维的向量Xi=(xil，xi2，⋯，xiD)，i=1，2，⋯，m。换言之，每个粒子的位置就是一个潜在的解。将五代入一个目标函数就可以

8、计算出其适应值，根据适应值的大小衡量Xi的优劣。第i粒子的“飞翔”速度也是一个D维的向量，记为Ⅵ=(v／1，v／2，⋯，v／D)。记第i个粒子迄今为止搜索到的最优位置为pt=(pil，pi2，⋯，piD)，整个粒子迄今为止搜索到的最优位置为p。=(pgl，p92，⋯，pgD)。Kennedy和Eberhart最早提出的PSO算法采用下列公式对粒子操作：坩1=Ⅵ+d+矗×(p；一刚)+c2Xr2×(P：一X÷)(1)Xrl=Xj+"+1(2)其中，卢l，2，⋯，m；k为迭代次数，学习