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

基于量子优化的人工蜂群算法求解旅行商问题()
分享到：

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

卷:
22
期数:
2020年12
页码:
7-9
栏目:
信息技术与通信
出版日期:
2020-12-20

文章信息/Info

Title:
An Artificial Bee Colony Algorithm Based on Quantum Optimization to Solve the Traveling Salesman Problem
作者:
唐天兵　朱继生　严　毅
（广西大学计算机与电子信息学院，广西 南宁 530001）
关键词:
人工蜂群算法; 量子优化; 旅行商问题
Keywords:
artificial bee colony algorithm quantum optimization traveling salesman problem
文献标志码:
A
摘要:
旅行商问题（TSP）是在运筹学界研究了近半个世纪的基本组合优化模型。它属于NP难问题。已经证明，相对于解决诸如TSP的NP难问题的传统方法，进化算法是有效且高效的。文章提出了一种基于量子激励的人工蜂群算法（QUABC）进行求解旅行商问题。在人工蜂群（ABC）优化和量子计算（QC）原理两种范式之间进行了混合。利用量子比特、态叠加和量子干涉等量子概念，并在经典的ABC算法的基础上加入量子表示的解，增强了标准ABC算法的多样性和计算能力。在一组TSPLIB的算例中对该算法进行了测试，实验结果表明，该算法能获得比较理想的结果。
Abstract:
Traveling salesman problem (TSP) is a basic combinatorial optimization model which has been studied for nearly half a century. It belongs to the NP difficult problem. It has been proved that evolutionary algorithm is effective and efficient compared with traditional methods for solving NP hard problems such as TSP. In this paper, a quantum inspired artificial bee colony algorithm (quabc) is proposed to solve the traveling salesman problem (TSP). A mixture of artificial bee colony (ABC) optimization and quantum computing (QC) principle is proposed. By using quantum concepts such as quantum bit, state superposition and quantum interference, and adding quantum representation solutions to the classical ABC algorithm, the diversity and computational power of the standard ABC algorithm are enhanced. The algorithm is tested in a group of TSPLIB examples, and the experimental results show that the algorithm can obtain ideal results.

参考文献/References:

[1] 鄂旭，盖佳妮，周津，等. 基于Hadamard门变异的量子遗传算法[J]. 控制工程，2018，25(1): 143-148. [2] 刘露萍，贾文生，蔡江华. 协同免疫量子粒子群算法求非合作博弈Nash均衡解[J]. 计算机应用与软件，2019，36(8): 203-209. [3] 周海鹏，高芹，蒋丰千，等. 自适应混沌量子粒子群算法及其在WSN覆盖优化中的应用[J]. 计算机应用，2018，38(4): 1064-1071. [4] Han K H, Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593. [5] 于宏涛，高立群，田卫华. 求解TSP的离散人工蜂群算法[J]. 东北大学学报(自然科学版)，2015，36(8): 1074-1079. [6] 翟光明，李国和，吴卫江，等. 基于Spark的人工蜂群改进算法[J]. 计算机应用，2017，37(7): 1906-1910. [7] Gündüz M, Kiran M S, Özceylan E. A hierarchic approach based on swarm intelligence to solve the traveling salesman problem[J]. Mathematics, 2015, 23(1): 215-235.

相似文献/References:

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

备注/Memo

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