求解旅行商问题的改进混合蛙跳算法.pdf

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

1、2014年第7期文章编号：1009—2552(2014)07—0050—03中图分类号：TP301．6文献标识码：A求解旅行商问题的改进混合蛙跳算法李碧，郑泓硕，何杰，郝志峰(1．广东外语外贸大学思科信息学院，广州510420；2．广东工业大学计算机学院，广州510006)摘要：混合蛙跳算法(ShuffledFrogLeapingAlgorithm，SFLA)是解决组合优化问题的有效方法，’但是应用于TSP问题时，由于SFLA没有充分利用最佳个体的优良信息，导致收敛速度太慢。文中把遗传算法(GeneticAl

2、gorithm，GA)的交叉和变异引入SFLA，提出了一种针对旅行商问题(TravelingSalesmanProblem，TSP)的改进混合蛙跳算法(ImprovedShufledFrogLeapingA1一gorithm，ISFLA)。应用于TSP的实验结果表明：ISFLA的收敛速度明显高于SFLA，同时优于GA和简单翻转算子。ISFLA不仅表现出了更快的收敛速度，而且能有效地缓解局部早熟收敛。关键词：蛙跳算法；遗传算法；旅行商问题；简单翻转算子SolvingTSPwithamodifiedshufled

3、frogleapingalgorithmUBi，ZHENGHong-shuo，HEJie，HA0Zhi．feng(1．SchoolofInformation，GuaIIgd0ngUniversityofForeignStudies，Guangzhou510420，China；2．ScholofComputer，GuangdongUniversityofTechnology，Guangzhou510006，China)Abstract：Shufledfrogleapingalgorithm(SFLA)isane

4、ffectivealgorithmtosolvecombinatorialoptimizationproblems．Butwhenappliedintravelingsalesmanproblem(TSP)itsconvergentspeedisratherlow，forSFLAfailstotakefulladvantageoftheusefulinformationinthebestindividua1．Animprovedshuffledfrogleapingalgorithm(ISFLA)ispres

5、entedthroughintroducingthecrossoverandmutationingeneticalgorithm(GA)．TheexperimentalresultsonTSPbenchmarksshowthat：ISFLAoutperformsSFLA，GA，andthesimpleinversionoperator(SimInv)，showingahigherconvergentspeedandalleviatingtheprematuremoreefectively．Keywords：s

6、hufledfrogleapingalgorithm；geneticalgorithm；travelingsalesmanproblem；simpleinversionoDerator0引言现等优点。文献[4]尝试提出了运用混合蛙跳算法组合优化(CombinatorialOptimization)问题的目求解TSP问题。本文在此基础上把遗传算法(Ge．标是从可行解集中求出目标函数下的最优解⋯。neticAlgorithm，GA)中的交叉和变异的思想引人旅行商问题(TravelingSalesmanProble

7、m，TSP)是组SFLA，提出了一种改进的混合蛙跳算法(Improved合优化中最典型的NP难问题，它的含义可以简述ShufledFrogLeapingAlgorithm，ISFLA)，旨在提高为：求出一条遍历所要求的所有城市的最短路径。SFLA的收敛速度，提高克服局部最优的能力。对TSP问题一般分为两大类的研究：一类着重于研1SFLA究算法解决大规模实际问题，侧重点在于算法能快SFLA是一种受自然生物模仿启示而产生的基速地有效求得可行解；另一类则是利用TSP问题来收稿日期：2014—03—03验证优化算法解

8、决离散组合优化问题的有效性-2J。基金项目：国家自然科学基金项目(61070033)；广东省高等学校科混合蛙跳算法(ShufledFrogLeapingAlgorithm，技创新项目(2013KJCX0073)SFLA)是一种新型的群体智能优化算法]，与其他作者简介：李碧(1973一)，男，博士，副教授，硕士生导师，研究方向为计算智能。群体智能优化算法相比，具有涉及参数少和易于实一50一于群体的协同