[1]唐天兵 姜 淇 严 毅.倒位变异的人工蜂群算法求解旅行商问题[J].大众科技,2020,22(07):1-3.
　Inversion Mutation of Artificial Bee Colony Algorithm to SolveTraveling Salesman Problem[J].Popular Science & Technology,2020,22(07):1-3.
点击复制

倒位变异的人工蜂群算法求解旅行商问题()
分享到：

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

卷:
22
期数:
2020年07
页码:
1-3
栏目:
信息技术与通信
出版日期:
2020-07-20

文章信息/Info

Title:
Inversion Mutation of Artificial Bee Colony Algorithm to SolveTraveling Salesman Problem
作者:
唐天兵 姜 淇 严 毅
（广西大学计算机与电子信息学院，广西 南宁 530004）
关键词:
人工蜂群算法; 启发式倒位变异; 旅行商问题
Keywords:
artificial bee colony algorithm;  heuristic inversion mutation;  traveling salesman problem
文献标志码:
A
摘要:
旅行商问题（TSP）是在运筹学界研究了近半个世纪的基本组合优化模型。它属于 NP 难问题。目前已经证明，相对于解决诸如 TSP 的 NP 难问题的传统方法，进化算法是有效且高效的。近年来有研究者提出一种基于群体智能的人工蜂群算法（ABC），该算法借鉴了蜂群寻找最佳食物来源的决策过程，具有明确的均衡强化和多样化的策略。为了提高算法的精度，文章基于基本的人工蜂群算法，将倒位变异融入到人工蜂群算法中，给出了该算法求解旅行商问题的详细执行过程，并使用标准 TSP 库中的实例对提出的算法的性能进行了实证评估。结果表明，所提出的算法能较好地解决 TSP 问题。
Abstract:
Traveling salesman problem (TSP) is a basic combination optimization model that has been studied in the field ofoperations research for nearly half a century. It belongs to the NP hard problem. It has been proven that evolutionary algorithms are effectiveand efficient compared to traditional methods of solving NP-hard problems such as TSP. Artificial bee colony (ABC) is a group-basedoptimization algorithm proposed in recent years. This algorithm borrows from the decision-making process of bees to find the best food source.It has clear balanced strengthening and diversified strategies. In order to improve the accuracy of the algorithm, based on the basic artificial beecolony algorithm, the inversion mutation is integrated into the artificial bee colony algorithm, and the detailed implementation process of thealgorithm for solving traveling salesman problem is given. An example from standard TSP database is used to evaluate the performance of theproposed algorithm. The results show that the proposed algorithm can solve the TSP problem quickly and efficiently.

参考文献/References:

[1] Ikeda S. Corrigenda: the traveling salesman problem: aguided tour of combinatorial optimization[J]. Journal of theOperational Research Society, 1986, 37(6): 655.[2] Lin S, Kernighan B W. An effective heuristic algorithm forthe traveling salesman problem[J]. Operations Research,1973, 21(2): 498-516.[3] Shi X H, Liang Y C, Lee H P, et al. Particle swarmoptimization-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 asymmetrictraveling salesman problem with imprecise travel times[J].Journal of Computational and Applied Mathematics, 2011,235(9): 3063-3078.[5] U?r A, Aydin D. An interactive simulation and analysissoftware for solving TSP using Ant Colony Optimizationalgorithms[J]. Advances in Engineering Software, 2009,40(5): 341-349.[6] 王殿超. 一种改进的遗传算法在 TSP 问题中的应用[J].辽宁工业大学学报(自然科学版)，2019，39(4): 235-239.[7] 程林辉. 禁忌搜索算法及其在 TSP 问题中的应用研究[J].大众科技，2013(5): 13-14.[8] 何锦福，符强，王豪东. 求解 TSP 问题的改进模拟退火算法[J]. 计算机时代，2019(7): 47-50.[9] 宋强. 一种求解 TSP 的 Beam-PSO 算法[J].武汉理工大学学报(交通科学与工程版)，2019(5): 816-819.[10] 于宏涛，高立群，田卫华. 求解 TSP 的离散人工蜂群算法[J]. 东北大学学报(自然科学版)，2015(8): 1074-1079.

相似文献/References:

[1]唐天兵　朱继生　严　毅.基于量子优化的人工蜂群算法求解旅行商问题[J].大众科技,2020,22(12):7.
　An Artificial Bee Colony Algorithm Based on Quantum Optimization toSolve the Traveling Salesman Problem[J].Popular Science & Technology,2020,22(07):7.

备注/Memo

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