求解旅行商问题的改进果蝇算法.pdf

《求解旅行商问题的改进果蝇算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2014年8月计算机工程与设计Aug．2014第35卷第8期COMPUTERENGINEERINGANDDESIGNVo1．35No．8求解旅行商问题的改进果蝇算法王克甫，薛鹏，黄全振，李恒宇+(1．河南工程学院电气信息工程学院，河南郑州451191；2．上海大学机电工程与自动化学院，上海200072)摘要：为了有效解决经典的NP难问题一旅行商问题(travelingsalesmanproblem，TSP)，提出了一种改进的果蝇算法。针对果蝇算法存在易陷入局部最优及收敛速度慢的缺点，引入了局部最优半径的概念，以此为依据判断果蝇是否处于局部最优区域；设计了带启发式规则的变异算子，

2、对局部最优半径中选中的果蝇个体进行启发式变异，在保护最优个体的同时，也改善了种群多样性，抑制了早熟现象的产生；采用自适应步长策略，显著提高了搜索效率。对其全局收敛性进行了验证，以TSPLIB为基准与标准果蝇算法、粒子群算法进行了实验对比，对比结果验证了该算法的有效性。关键词：果蝇算法；局部最优半径；变异算子；自适应步长；旅行商问题中图法分类号：TP29；TP273文献标识号：A文章编号：1000—7024(2014)08-2789—04ImprovedfruitflyoptimizationalgorithmforTSPproblemsWANGKe-fu，XUEPeng，HUA

3、NGQuan-zhen，LIHeng—yu。+(1．SchoolofElectricalInformationEngineering，HenanInstituteofEngineering，Zhengzhou451191，China；2．SchoolofMechatronicsEngineeringandAutomation，ShanghaiUniversity，Shanghai200072，China)Abstract：ToaddressaclassicalNPhardproblemofTSP(travelingsalesmanproblem)，animprovedfruit

4、flyoptimizationalgo—rithmwasproposed．Aimingatstandardfruitflyoptimizationalgorithmhavingshortcomingsofeasilyplungingintolocaloptimalandlowconvergence-rate，theradiusoflocaloptimumwasintroduced，bywhichwhetherthefruitflywasinalocaloptimumareacouldbejudged．Meanwhile，theheuristicmutationoperatorw

5、asdesigned，thefruitfliesselectedwasmutatedbyheuristicmutationoperatorintheradiusoflocaloptimum，whichnotonlyprotectedtheoptimalindividual，butalsoimprovedthediversityofthepopulationandpreventedpremature．Furthermore，thestrategyofadaptivevariablestepsizewasadopted，whichincreasedsearchefficiencye

6、ffectively．Finally，theconvergenceofalgorithmproposedwasproved．Comparedtothestandardfruitflyopti—mizationalgorithmandtheparticleswarmoptimizationalgorithmbenchmarkedonTSPLIB，theimprovedfruitflyoptimizationalgorithmwasverifiedtobeefficient．Keywords：fruitflyoptimizationalgorithm；radiusoflocalop

7、timum；mutationoperator；adaptivevariablestepsize；TsP求解算法，总的可归为两方面：精确算法和启发式算法。0引言然而，TSP解空间随问题规模呈指数级增长，对于大规模TSP作为一类经典的NP难组合优化问题，在车辆调问题，传统精确算法很难在可接受的时间内找到最优解。度、物流配送、管道铺设、电路板布局等领域得到广泛应比如：分支一切割法，动态规划法等；而启发式算法本用，国内外学者对此已开展大量的研究工作，、并提出一些身具有一定的智能性，它们可依靠自身的这