[1]骆剑平,李霞.求解TSP的改进混合蛙跳算法[J].深圳大学学报理工版,2010,27(2):173-179.
 LUO Jian-ping and LI Xia.Improved shuffled frog leaping algorithm for solving TSP[J].Journal of Shenzhen University Science and Engineering,2010,27(2):173-179.
点击复制

求解TSP的改进混合蛙跳算法()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第27卷
期数:
2010年2期
页码:
173-179
栏目:
光电与信息工程
出版日期:
2010-04-30

文章信息/Info

Title:
Improved shuffled frog leaping algorithm for solving TSP
文章编号:
1000-2618(2010)02-0173-07
作者:
骆剑平李霞
深圳大学信息工程学院,深圳 518060
Author(s):
LUO Jian-ping and LI Xia
College of Information Engineering,Shenzhen University,Shenzhen 518060,P.R.China
关键词:
人工智能智能计算虫群智慧混合蛙跳算法极值动力学优化模拟退火
Keywords:
artificial intelligenceintelligent computing swarm intelligenceshuffled frog leaping algorithmextremal optimizationsimulated annealing
分类号:
TP 181;TP 183
文献标志码:
A
摘要:
重新定义表示青蛙移动距离和位置的数据结构及运算符意义,提出混合蛙跳算法(shuffled frog leaping algorithm,SFLA)求解旅行商问题(traveling salesman problem,TSP)基于交换序的实现方法.把具有极强局部搜索能力的幂律极值动力学优化(power law extremal optimization,τ-EO)融合于SFLA,并针对TSP对τ-EO过程进行设计和改进.改进后的τ-EO采用新颖的组元适应度计算方法,通过定义边置换增益能量,结合模拟退火控制过程,并采取幂律定律用概率的方式选取2-opt置换产生邻域解.为避免每个族群最优解的趋同性,提出最优样本差异控制策略.通过求解TSPLIB数据库中的实例,证明该改进算法有效.
Abstract:
A novel shuffled frog-leaping algorithm (SFLA) was proposed for solving traveling salesman problem (TSP) based on the technique of exchanging order. The data structure of moving distance and position of frog and the local information exchange strategy for the SFLA were redefined. In order to improve the local search ability, the power law extremal optimization (τ-EO) was incorporated into the SFLA. The fitness for the component of a solution was carefully designed. Simulated annealing (SA) and the 2-opt move technique were used to generate neighboring solutions in the improved τ-EO. In the shuffling process of the SFLA, a diversity control scheme was presented for the local best solution in each memeplex. Experimental results show that the performance of the proposed algorrthm to solve TSP is satisfatory.

参考文献/References:

[1]Eusuff M M,Lansey K E.基于混合蛙跳算法的水分布网络设计优化[J].水源规划和管理,2003,129(3):210-225.(英文版)
[2]Moscato P.从进化、搜索、优化以及遗传算法到模因算法[R].加州理工学院关于并行计算的技术报告(826),帕萨迪纳:加州理工学院,1989.(英文版)
[3]Thai H H.基于改进的混合蛙跳算法的多变量PID控制器优化调整[C]// 信息技术国际会议论文集(ICIT).新加坡:IEEE出版社,2008:128-134.(英文版)
[4]Alireza R V.融合多目标混合蛙跳算法求解装配线排序问题[J].计算机与工业工程,2007,53:642-666.(英文版)
[5]Sun X,Wang Z Q.基于混合蛙跳算法的网络文档分类器设计[C]// 遗传进化计算国际会议论文集.荆州(中国):IEEE出版社,2008:205-208.(英文版)
[6]罗雪晖,杨烨,李霞.混合蛙跳算法求解TSP[C]// 第8届智能系统设计和应用国际国际会议论文集.台湾高雄:IEEE出版社,2008:228-232.(英文版)
[7]Boettcher S,Percus A G.基于协同进化的极值优化技术[C]// 遗传进化计算国际会议论文集.华盛顿:IEEE出版社,1999:101-106.(英文版)
[8]Wang K P,Huang L,Zhou C G.粒子群算法求解TSP[C]// 机器学习与控制国际会议论文集.西安:IEEE出版社,2003:1583-1585.(英文版)
[9]旅行商问题库[DB/OL].http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.(英文版)
[10]Zhang C S,Sun J G,Wang Y,等.一种改进的求解TSP离散粒子群优化算法[C]// 网页智能及智能代理技术国际会议论文集.硅谷(美国):IEEE出版社,2007:589-594.(英文版)
[11]Ghoseiri K,Sarhadi H.2 opt-DPX遗传局部搜索技术求解对称TSP[C]// 工业工程与工程管理国际会议论文集.新加坡:IEEE出版社,2007:903-906.
[12]罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题[J].通信学报,2009,30(7):130-135.
[13]Thiago A S,Leandro N.神经免疫算法求解路径问题[J].神经计算,2009,72:2189-2197.
[14]Dusan T,基于群智能系统的运输工程:原理及应用[J].运输研究,2008,16:651-667.
[15]Thiago A S,Leandro N.一种基于免疫系统思想的自组织神经网络算法求解TSP[J].信息科学,2009,179:1454-1468.



[1]Eusuff M M,Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Sources Planning and Management,2003,129(3):210-225.
[2]Moscato P.On evolution,search,optimization,genetic algorithms and martial arts:towards memetic algorithms[R].Technical Report Caltech Concurrent Computation Program Report(826).Pasadena:California Institute of Technology,1989.
[3]Thai H H.A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllers[C]// International Conference on Information Technology.Singapore:IEEE Press, 2008:128-134.
[4]Alireza R V.A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem[J].Computers & Industrial Engineering,2007,53:642-666.
[5]Sun X,Wang Z Q. A web document classification method based on shuffled frog leaping algorithm[C]// The 2nd International Conference on Genetic and Evolutionary Computing (WGEC 2008).Jingzhou(China):IEEE Press,2008,205-208.
[6]LUO Xue-hui,YANG Ye,LI Xia.Solving TSP with shuffled frog-leaping algorithm[C]// The 8th International Conference on Intelligent Systems Design and Applications (ISDA 2008).Taiwan Kaohsiung:IEEE Press,2008:228-232.
[7]Boettcher S,Percus A G.Extremal optimization:methods derived from co-evolution[C]// Proceedings of the Genetic and Evolutionary Computation Conference.NY:IEEE Press,1999:101-106.
[8]Wang K P,Huang L,Zhou C G.Particle swarm optimization for traveling salesman problem[C]// Proceedings of the 2nd International Conference on Machine Learning and Cybernetics.Xi’an:IEEE Press, 2003:1583-1585.
[9]Traveling Salesman Problems Library[DB/OL].http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.
[10]Zhang C S,Sun J G,Wang Y,et al.An improved discrete particle swarm optimization algorithm for TSP[C]// International Conferences on Web Intelligence and Intelligent Agent Technology Workshops.Silicon Valley(USA):IEEE Press,2007:589-594.
[11]Ghoseiri K,Sarhadi H.A 2 opt-DPX genetic local search for solving symmetric traveling salesman problem[C]// Proceedings of the 2007 IEEE IEEM.Singapore:IEEE Press,2007:903-906.
[12]LUO Xue-hui,YANG Ye,LI Xia.A modifed shuffled frog leaping algorithm for TSP[J].Journal on Communications,2009,30(7):130-135.(in Chinese)
[13]Thiago A S,Leandro N.Neuro-immune approach to solve routing problems[J].Neurocomputing,2009,72:2189-2197.
[14]Dusan T.Swarm intelligence systems for transportation engineering:principles and applications[J].Transportation Research,2008,16:651-667.
[15]Thiago A S,Leandro N.A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem[J].Information Sciences,2009,179:1454-1468.

相似文献/References:

[1]潘长城,徐晨,李国.解全局优化问题的差分进化策略[J].深圳大学学报理工版,2008,25(2):211.
 PAN Chang-cheng,XU Chen,and LI Guo.Differential evolutionary strategies for global optimization[J].Journal of Shenzhen University Science and Engineering,2008,25(2):211.
[2]张重毅,刘彦斌,于繁华,等.CDA市场环境模型进化研究[J].深圳大学学报理工版,2010,27(4):413.
 ZHANG Zhong-yi,LIU Yan-bin,YU Fan-hua,et al.Research on the evolution model of CDA market environment[J].Journal of Shenzhen University Science and Engineering,2010,27(2):413.
[3]姜建国,周佳薇,郑迎春,等.一种双菌群细菌觅食优化算法[J].深圳大学学报理工版,2014,31(No.1(001-110)):43.[doi:10.3724/SP.J.1249.2014.01043]
 Jiang Jianguo,Zhou Jiawei,Zheng Yingchun,et al.A double flora bacteria foraging optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(2):43.[doi:10.3724/SP.J.1249.2014.01043]
[4]蔡良伟,刘思麒,李霞,等.基于蚁群优化的正则表达式分组算法[J].深圳大学学报理工版,2014,31(No.3(221-330)):279.[doi:10.3724/SP.J.1249.2014.03279]
 Cai Liangwei,Liu Siqi,Li Xia,et al.Regular expression grouping algorithm based on ant colony optimization[J].Journal of Shenzhen University Science and Engineering,2014,31(2):279.[doi:10.3724/SP.J.1249.2014.03279]
[5]宁剑平,王冰,李洪儒,等.递减步长果蝇优化算法及应用[J].深圳大学学报理工版,2014,31(No.4(331-440)):367.[doi:10.3724/SP.J.1249.2014.04367]
 Ning Jianping,Wang Bing,Li Hongru,et al.Research on and application of diminishing step fruit fly optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(2):367.[doi:10.3724/SP.J.1249.2014.04367]
[6]刘万峰,李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J].深圳大学学报理工版,2015,32(No.2(111-220)):196.[doi:10.3724/SP.J.1249.2015.02000]
 Liu Wanfeng,and Li Xia,A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2015,32(2):196.[doi:10.3724/SP.J.1249.2015.02000]
[7]蔡良伟,程璐,李军,等.基于遗传算法的正则表达式规则分组优化[J].深圳大学学报理工版,2015,32(No.3(221-330)):281.[doi:10.3724/SP.J.1249.2015.03281]
 Cai Liangwei,Cheng Lu,Li Jun,et al.Regular expression grouping optimization based on genetic algorithm[J].Journal of Shenzhen University Science and Engineering,2015,32(2):281.[doi:10.3724/SP.J.1249.2015.03281]
[8]王守觉,鲁华祥,陈向东,等.人工神经网络硬件化途径与神经计算机研究[J].深圳大学学报理工版,1997,14(1):8.
 Wang Shoujue,Lu Huaxiang,Chen Xiangdong and Zeng Yujuan.On the Hardware for Artificial Neural Networks and Neurocomputer[J].Journal of Shenzhen University Science and Engineering,1997,14(2):8.
[9]陈星宇,周展,黄俊文,等.基于关键词挖掘的客户细分方法[J].深圳大学学报理工版,2017,34(No.3(221-330)):300.[doi:10.3724/SP.J.1249.2017.03300]
 Chen Xingyu,Zhou Zhan,Huang Junwen,et al.A keyword-based mining method for customer segmentation[J].Journal of Shenzhen University Science and Engineering,2017,34(2):300.[doi:10.3724/SP.J.1249.2017.03300]
[10]何玉林,等.大规模数据集聚类算法的研究进展[J].深圳大学学报理工版,2019,(No.1(1-110)):4.[doi:10.3724/SP.J.1249.2019.01004]
 HE Yulin,and HUANG Zhexue,A review on clustering algorithms for large-scale data sets[J].Journal of Shenzhen University Science and Engineering,2019,(2):4.[doi:10.3724/SP.J.1249.2019.01004]
[11]蔡良伟,李霞.基于混合蛙跳算法的作业车间调度优化[J].深圳大学学报理工版,2010,27(4):391.
 CAI Liang-wei and LI Xia.Optimization of job shop scheduling based on shuffled frog leaping algorithm[J].Journal of Shenzhen University Science and Engineering,2010,27(2):391.

备注/Memo

备注/Memo:
收稿日期:2009-12-07;修回日期:2010-03-24
基金项目:国家自然科学基金资助项目(60772148);高等学校博士点基金资助项目(200805900001)
作者简介:骆剑平(1978-),男(汉族),广东省河源市人,深圳大学博士研究生.E-mail:camelrock@126.com
通讯作者:李霞(1968-),女(汉族),深圳大学教授、博士生导师.E-mail:lixia@szu.edu.cn
更新日期/Last Update: 2010-05-08