[1]唐天兵　姜 淇　严 毅.混合天牛须算法解决旅行商问题[J].大众科技,2021,23(1):8-10.
　Hybrid Beetle Antennae Search Algorithm for Solving Traveling Salesman Problem[J].Popular Science & Technology,2021,23(1):8-10.
点击复制

混合天牛须算法解决旅行商问题()
分享到：

《大众科技》[ISSN:1008-1151/CN:45-1235/N]

卷:
23
期数:
2021年1
页码:
8-10
栏目:
信息技术与通信
出版日期:
2021-01-20

文章信息/Info

Title:
Hybrid Beetle Antennae Search Algorithm for Solving Traveling Salesman Problem
作者:
唐天兵　姜 淇　严 毅
（广西大学计算机与电子信息学院，广西 南宁 530004）
关键词:
天牛须算法; 倒位变异; 旅行商问题
Keywords:
beetle antennae search algorithm; inversion mutation;  traveling salesman problem
文献标志码:
A
摘要:
文章针对天牛须算法（BAS）后期收敛速度慢、寻优精度低的缺点，提出了一种融入倒位变异的天牛须算法。文章基于基本的天牛须算法，将倒位变异融入到天牛须算法中，帮助算法跳出局部最优，并给出了该算法求解旅行商问题的详细执行过程。最后，为了验证新算法的有效性，使用标准TSP库中的实例对提出的算法的性能进行了实证评估。结果表明文章对天牛须算法的改进是合理的。
Abstract:
Aiming at the disadvantages of slow convergence speed and low optimization accuracy of beetle antennae search (BAS) algorithm in the later stage, a new algorithm with inversion mutation was proposed. In this paper, based on the basic beetle antennae search algorithm, inversion mutation is incorporated into the algorithm to help the algorithm jump out of the local optimum, and the detailed implementation process of the algorithm for solving the traveling salesman problem is given. At the end of the paper, in order to verify the effectiveness of the new algorithm, an example from the standard TSP library is used to evaluate the performance of the proposed algorithm. The results show that the improvement of the article to the algorithm is reasonable.

参考文献/References:

[1] Flood M M. The traveling-salesman problem[J]. Operations research, 1956, 4(1): 61-75. [2] Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem[J]. Proceedings of the American Mathematical Society, 1956, 7(1): 48-50. [3] Shi X H, Liang Y C, Lee H P, et al. Particle swarm optimization-based algorithms for TSP and generalized TSP[J]. Information Processing Letters, 2007, 103(5): 169-176. [4] Majumdar J, Bhunia A K. Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times[J]. Journal of Computational and Applied Mathematics, 2011, 235(9): 3063-3078. [5] Little J D C, Murty K G, Sweeney D W, et al. An algorithm for the traveling salesman problem[J]. Operations Research, 1963, 11(6): 972-989. [6] 王殿超. 一种改进的遗传算法在TSP问题中的应用[J]. 辽宁工业大学学报(自然科学版)，2019，39(4): 235-239. [7] 程林辉. 禁忌搜索算法及其在TSP问题中的应用研究[J]. 大众科技，2013，15(5): 13-14. [8] 何锦福，符强，王豪东. 求解TSP问题的改进模拟退火算法[J]. 计算机时代，2019(7): 47-50. [9] 宋强. 一种求解TSP的Beam-PSO算法[J]. 武汉理工大学学报(交通科学与工程版)，2019，43(5): 816-819. [10] Wu Q, Shen X, Jin Y, et al. Intelligent beetle antennae search for UAV sensing and avoidance of obstacles[J]. Sensors, 2019, 19(8): 1758. [11] Li Q, Wei A, Zhang Z. Application of economic load distribution of power system based on BAS-PSO[C]. IOP Conference Series: Materials Science and Engineering. IOP Publishing, 2019, 490(7): 072056. [12] Wu Q, Lin H, Jin Y, et al. A new fallback beetle antennae search algorithm for path planning of mobile robots with collision-free capability[J]. Soft Computing, 2020, 24(3): 2369-2380. [13] Jiang X, Li S. Bas: Beetle antennae search algorithm for optimization problems[J]. International Journal of Robotics and Control, 2017, 1(1): 1710.

备注/Memo

备注/Memo:
【收稿日期】2020-11-08 【基金项目】广西研究生教育创新计划项目（No.JGY2019005）。 【作者简介】唐天兵（1972－），男，广西大学计算机与电子信息学院副教授，研究方向为并行计算和优化算法。 【通信作者】严毅（1971－），男，广西大学计算机与电子信息学院高级工程师，研究方向为并行计算和优化算法。
更新日期/Last Update: 2021-03-15