• / 7
  • 下载费用:10 金币  

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

关 键 词:
改进混合蛙跳算法求解旅行商问题.doc
资源描述:
2009 年 7 月 Journal on Communications July 2009第 30 卷第 7 期 通 信 学 报 Vol.30 No.7改进混合蛙跳算法求解旅行商问题罗雪晖,杨烨,李霞(深圳大学 信息工程学院,广东 深圳 518060)摘 要:以旅行商问题(TSP )为例,引入调整序思想设计了局部搜索策略,同时在全局信息交换过程中加入变异操作,提出一种改进混合蛙跳算法求解 TSP 问题。实验结果表明,与遗传算法和粒子群优化算法相比较,改进混合蛙跳算法在求解 TSP 问题上具有更好的搜索性能和顽健性。关键词:混合蛙跳算法;旅行商问题;局部搜索;全局信息交换中图分类号:TP18 文献标识码:A 文章编号:1000-436X(2009)07-0130-06Modified shuffled frog-leaping algorithm to solve traveling salesman problemLUO Xue-hui, YANG Ye, LI Xia(College of Information Engineering, Shenzhen University, Shenzhen 518060,China )Abstract: Modified shuffled frog-leaping algorithm to solve TSP was proposed, which presented the concept of adjustment sequence to design the strategy of local searching, and added the mutation operation in the global exchange of information. Experimental results indicate that, compared with genetic algorithm and particle swarm optimization algorithm, the proposed algorithm has more powerful search capability and more strong robustness in solving TSP.Key words: shuffled frog-leaping algorithm; traveling salesman problem; local search; global information exchange1 引言混合蛙跳算法是 2000 年由 Muzaffar Eusuff 和Kevin Lansey 提出的一种基于群智能的亚启发式计算优化算法,用于解决离散组合优化问题 [1]。作为一种新型的仿生物学智能优化算法,SFLA 结合了基于模因(meme)进化的模因演算法(MA, memetic algorithm)和基于群体行为的粒子群算法(PSO, particle swarm optimization)2 种群智能优化算法的优点。该算法具有概念简单,调整的参数少,计算速度快,全局搜索寻优能力强,易于实现的特点 [2]。混合蛙跳算法主要应用于解决多目标优化问题,例如水资源分配、桥墩维修、车间作业流程安排等工程实际应用问题 [3~5]。著名的旅行商问题 [6](TSP, traveling salesman problem)是一类典型组合优化问题,求得一条遍历所有城市的最短回路,属于 NP 难问题。对 TSP问题一般分为两大类的研究:一类着重于研究算法解决大规模实际问题 [7],如文献[7]中解决的 TSP问题城市规模最大达到 316 228 个,侧重点在于算法能快速地有效求得可行解;另一类则是利用TSP 问题来验证优化算法解决离散组合优化问题的有效性。几十年来,出现了很多近似优化算法用于求解 TSP 问题,基本分为 2 类:①与问题本身特征相关的局部启发式搜索算法,如 2-Opt、3-Opt 和 Lin-Kernighan(LK) [8]等。这类优化算法收稿日期:2008-08-02;修回日期:2008-11-20基金项目:国家自然科学基金资助项目(60772148)Foundation Item: The National Natural Science Foundation of China (600772148)第 7 期 罗雪晖等:改进混合蛙跳算法求解旅行商问题 ·131·多数充分利用问题本身特征的相关信息有效寻找问题的局部最优解,但是这些算法过分依赖于问题本身特征,当问题的规模扩大后,问题本身特征的相关信息更复杂,大大增加算法计算量,使得算法搜索时
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:改进混合蛙跳算法求解旅行商问题.doc
链接地址:https://www.weizhuannet.com/p-7308467.html
微传网是一个办公文档、学习资料下载的在线文档分享平台

微传网博客

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开