A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems

Hua Pei Chiang, Yao Hsin Chou, Chia Hui Chiu, Shu Yu Kuo, Yueh Min Huang

研究成果: Article同行評審

27 引文 斯高帕斯(Scopus)

摘要

In this study, we propose a novel quantum-inspired evolutionary algorithm (QEA), called quantum inspired Tabu search (QTS). QTS is based on the classical Tabu search and characteristics of quantum computation, such as superposition. The process of qubit measurement is a probability operation that increases diversification; a quantum rotation gate used to searching toward attractive regions will increase intensification. This paper will show how to implement QTS into NP-complete problems such as 0/1 knapsack problems, multiple knapsack problems and the traveling salesman problem. These problems are important to computer science, cryptography and network security. Furthermore, our experimental results on 0/1 knapsack problems are compared with those of other heuristic algorithms, such as a conventional genetic algorithm, a Tabu search algorithm and the original QEA. The final outcomes show that QTS performs much better than other heuristic algorithms without premature convergence and with more efficiency. Also on multiple knapsack problems and the traveling salesman problem QTS verify its effectiveness.

原文English
頁(從 - 到)1771-1781
頁數11
期刊Soft Computing
18
發行號9
DOIs
出版狀態Published - 2014 九月

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Geometry and Topology

指紋 深入研究「A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems」主題。共同形成了獨特的指紋。

引用此