全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
电子学报  2012 

求解TSP问题的离散型萤火虫群优化算法

DOI: 10.3969/j.issn.0372-2112.2012.06.016, PP. 1164-1170

Keywords: 萤火虫群优化算法,离散萤火虫群算法,TSP问题,2-Opt

Full-Text   Cite this paper   Add to My Lib

Abstract:

基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1%以下.

References

[1]  戚玉涛,焦李成,刘芳.基于并行人工免疫算法的大规模TSP问题求解[J].电子学报,2008,36(8):1552-1558. Qi Yutao,Jiao Licheng,Liu Fang.Parallel artificial immune algorithm for large-scale TSP [J].Acta Electronica Sinica,2008,36(8):1552-1558.(in Chinese).
[2]  K N Krishnand,D Ghose.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics .Proceedings of IEEE Swarm Intelligence Symposium.Pisatway .Pasadena California:IEEE Press,2005.84-91.
[3]  K N Krishnanad,D Ghose.Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations [J].Robotics and Autonomous Systems,2008,56(7):549-569.
[4]  K McGill,S Taylor.Robot algorithms for localization of multiple emission sources [J].ACM Computing Surveys,2011,43(3):15:1-15:25.
[5]  Lin S,Kernigham B W.An effective heuristic algorithm for the travelling salesman problem [J].Operations Research,1973,21(2):4982-5161.
[6]  韩丽霞,王宇平.解旅行商问题的一个新的遗传算法[J].系统工程理论与实践,2007,(12):145-150. Han Lixia,Wang Yuping.A novel genetic algorithm for traveling salesman problem.systems engineering[J].Theory & Practice,2007,(12):145-150.(in Chinese)
[7]  俞靓亮,王万良,介婧.基于混合粒子群优化算法的旅行商问题求解 [J].计算机工程, 2010,36(11):183-187. Yu Liang liang,Wang Wan liang,Jie Jing.Solution of travel salesman problem based on hybrid particle swarm optimization olgorithm [J].Computer Engineering,2010,36(11):183-187.(in Chinese)
[8]  Yong-Hyun Cho.An efficient solving the travelling salesman problem:Global optimization of neural networks by using hybrid method .Traveling Salesman Problem,Theory and Applications .Switzerland:Intech Press,2010.155-176.
[9]  Hirotaka Itoh.The method of solving for travelling salesman problem using genetic algorithm with immune adjustment mechanism .Traveling Salesman Problem,Theory and Applications .Switzerland:Intech Press,2010.97-112
[10]  Kaji T.Approach by ant tabu agents for ttraveling salesman problem .Proceedings of the IEEE International Conference on Systems,Man,and Cybernetics .Tucson,AZ,USA:IEEE Press,2001.3429-3434.
[11]  X H Shi,Y C Liang,H P Lee,C Lu,Q X Wang.Particle swarm optimization-based algorithms for TSP and generalized TSP [J].Information Processing Letters,2007,103(5):169-176.
[12]  K N Krishnand,D Ghose.Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J].Multiagent and Grid Systems,2006,2(3):209-222.
[13]  K N Krishnand,D Ghose.Glowworm swarm optimisation:a new method for optimizing multi-modal functions [J].Int J Computational Intelligence Studies,2009,1(1):93-119.
[14]  K N Krishnand,D Ghose.Glowworm swarm optimisation for simultaneous capture of multiple local optima of multimodal functions [J].Swarm Intelligence,2009(3):87-124.
[15]  杨辉,康立山,陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J].计算机学报,2003,26(12):1753-1758. Yang Hui,Kang Lishan,Chen Yuping.A gene-based genetic algorithm for TSP [J].Chinese Journal of Computers,2003,26(12):1753-1758.(in Chinese)
[16]  祝崇隽,刘民,吴澄,吴晓冰.针对模糊需求的VRP的两种2-OPT算法[J].电子学报,2001,29(8):1035-1037. Zhu Chongjun,Liu Min,Wu Cheng,Wu Xiaobing.Two kinds of 2-OPT algorithm for VRP with fuzzy demand [J].Acta Electronica Sinica,2001,29(8):1035-1037.(in Chinese)
[17]  张长胜,孙吉贵,欧阳丹彤.一种自适应离散粒子群算法及其应用研究[J].电子学报,2009,37(2):299-304. Zhang Chang sheng,Sun Ji gui, OUANG Dantong.A self-adaptive discrete particle swarm optimization algorithm [J].Acta Electronica Sinica,2009,37(2):299-304.(in Chinese)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133