求解旅行商问题的一种改进粒子群算法

《求解旅行商问题的一种改进粒子群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第19卷第5期2010年10月运筹与管理OPERATIONSRESEARCHANDMANACEMENTSCIENCEV01．19，No．5Oct．2010求解旅行商问题的一种改进粒子群算法郭崇慧1，谷超2，江贺3(1．大连理工大学系统工程研究所，辽宁大连116024；2．大连理工大学应用数学系，辽宁大连116024；3．大连理工大学软件学院，辽宁大连116024)摘要：本文研究了求解旅行商问题的粒子群算法。针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点，提出了一种改进的粒子群算法。首先，在初始种群的选取过程中，利用改进的贪婪策略直接获得具有较高性能的初始种群以提高算法

2、的搜索效率。其次，通过引入次优吸引子，使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能，有效抑制收敛过程中的停滞现象，提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性，对TSPLIB标准库中的多个实例进行了测试，并给出了数值结果。关键词：运筹学；粒子群优化；旅行商问题；贪婪策略中图分类号：0221．7文章标识码：A文章编号：1007-3221(2010)05一0020一07AnImprovedParticleSwarmOptimizationforTravelingSalesmanProblemGUOChong．huil。GUCha02。JIANGHe3(1．[n

3、stituteofSystemsEngineering，DalianUniversityofTechnology，Dalian116024，China；2．DepartmentofAppliedMathematics，DalianUniversityofTechnology，Dalian116024，China；3．SchoolofSoftware，Dalian叽niversityofTechnology，Dalian16024，China)Abstract：Thispaperdealswiththetravelingsalesmanproblemwiththeparticleswarmo

4、ptimizationalgorithm．Toovercomethedisadvantagesofprematureconvergenceandstagnationphenomenonofthestandardparticleswarmoptimizationalgorithm，thispaperproposesanimprovedparticleswarmoptimizationalgorithmforthetray—clingsalesmanproblem．Firstly，intheselectionofaninitialpopulation，amodifiedgreedystrate

5、gyisexploitedtodirectlyobtainapopulationofhigh-performanceinitialsolutionsS4)astoimprovethesearchefficiencyofthealgorithm．Secondly，throughintroducingsub—optimalattractor，theparticlesinthesearchprocesscanmakefulluseofthepopulationinformationtoenhancetheirownperformance，SOastoeffectivelyinhibitstagn

6、ationintheConvergenceprocess，andimprovethesearchabilityofthealgorithm．Finally，inordertoverifytheeffectivenessandfeasibilityoftheproposedmethod，theinstancesinthestandardlibraryTSPLIBhavebeentestedandthenu-mericalresultaregiven．Keywords：operationsresearch；particleswarmoptimization；travelingsalesmanp

7、roblem；greedystrategy0引言旅行商问题(TravelingSalesmanProblem，TSP)是经典的NP难组合优化问题之一，由于其在交通运输、物流配送以及电路板线路设计等领域内有着广泛的应用，长期以来人们一直在寻求快速、高效的求解收稿日期：2009—07．03基金项目：it家自然科学基金责助项目(10571018．70871015)；国家高技术研宄发展计划(863计划)资助项目(2008AA04