期刊文献+

求解TSP问题的离散型萤火虫群优化算法 被引量:80

Discrete Glowworm Swarm Optimization Algorithm for TSP Problem
下载PDF
导出
摘要 基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1%以下. A discrete glowworm swarm optimization (DGSO) algorithm is designed to tackle the travelling salesman prob lem. A new encoding schema and decoding schema are given with the characteristics of the TSP problem, and a new distance formu la and encoding update formula for the new algorithm are given. In order to enhance the capability of the algorithm local searching, and to speed up the algorithm convergence speed, the 2opt local search scheme is integrated into the new algorithm for solving TSP problem. The proposed algorithm was evaluated on 10 TSP test problems. The numerical experiments show that the proposed algo rithm can find the global optimal solution with less computation and evolving time. In case of large scale TSP algorithm can achieve optimal solution of the theory and the error of the optimal solution is also less than 1%.
出处 《电子学报》 EI CAS CSCD 北大核心 2012年第6期1164-1170,共7页 Acta Electronica Sinica
基金 国家自然科学基金(No.61165015) 广西自然科学基金重点项目(No.2012GXNSFDA053028) 智能感知与图像理解教育部重点实验室开放基金(No.IPIU012011001)
关键词 萤火虫群优化算法 离散萤火虫群算法 TSP问题 2-Opt discrete glowworm swarm optimization algorithm glowworm swarm optimization TSP 2-Opt
  • 相关文献

参考文献17

  • 1Yong-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. 被引量:1
  • 2Hirotaka 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. 被引量:1
  • 3Kaji 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. 被引量:1
  • 4X 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. 被引量:1
  • 5戚玉涛,焦李成,刘芳.基于并行人工免疫算法的大规模TSP问题求解[J].电子学报,2008,36(8):1552-1558. 被引量:12
  • 6K 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. 被引量:1
  • 7K 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. 被引量:1
  • 8K 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. 被引量:1
  • 9K 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. 被引量:1
  • 10K N Krishnand,D Ghose.Glowworm swarm optimisation for simultaneous capture of multiple local optima of multimodal functions[J].Swarm Intelligence,2009(3):87-124. 被引量:1

二级参考文献55

  • 1陈崚,章春芳.并行蚁群算法中的自适应交流策略(英文)[J].软件学报,2007,18(3):617-624. 被引量:10
  • 2吕强,高彦明,钱培德.共享信息素矩阵:一种新的并行ACO方法[J].自动化学报,2007,33(4):418-421. 被引量:11
  • 3钟文亮,詹志辉,郭锐鹏,胡晓敏,张军.求解TSP的交配算子设计策略[J].计算机工程与设计,2007,28(10):2408-2411. 被引量:7
  • 4J Kennedy,R C Eberhart. Particle swarm optimization[A].in: Proceedings of the IEEE International Joint Conference on Neural Networks [ C ]. Piscataway, NJ: IEEE Service Center, IEEE Press, 1995. 1942 - 1948. 被引量:1
  • 5Qingyun Yang,Jigui sun, Juyang Zhang, Chunjie Wang.A hybrid discrete particle swarm algorithm for open-shop problems [A]. Proceedings of the 6th International Conference on Simulated Evolution And Learning (SEAL 2006) [ C]. Hefei, China, LNCS 4247,2006. 158 - 165. 被引量:1
  • 6K Rameshkumar, R K Suresh, K M Mohanasundaram. Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makspan[ A ]. In: Proc. ICNC 2005 [C]. Changsha, China, LNCS 3612,2005.572 - 581. 被引量:1
  • 7Pant,M Radha, T Singh, V P.A simple diversity guided particle swarm optimization [A]. IEEE Congress on Evolutionary Computation[C]. Singapore, CEC2007. 2007. 3294 - 3299. 被引量:1
  • 8Christopher K. Monson, Kevin D. Seppi, Adaptive Diversity in PSO[ A]. Proceedings of the 8th annual conference on Genetic and evolutionary computation Seattle [ C ]. Washington, USA, 2006.59 - 66. 被引量:1
  • 9M Clerc: Discrete particle swarm optimization, illustrated by the Traveling Salesman Problem[A ]. In: New Optimization Techniques in Engineering[ C ]. Heidelberg, Germany, 2004. 219 - 239. 被引量:1
  • 10A C. Nearchou, The effect of various operators on the genetic search for large scheduling problems[J]. Int. J. Product. E-conom. 2004,88( 1 ) : 191 - 203. 被引量:1

共引文献156

同被引文献719

引证文献80

二级引证文献588

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部