量子啟發式禁忌搜尋演算法應用於解決0/1背包問題

Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems

邱佳慧(Chia-Hui Chiu)

指導教授 ： 周耀新

國立暨南國際大學/科技學院/資訊工程學系/碩士(2011年)

https://doi.org/10.6837/NCNU.2011.00171

摘要

本研究提出一種新的類量子演化計算，稱為量子啟發式禁忌搜尋演算法，將禁忌搜尋演算法的理論結合量子特性，例如量子疊加狀態，需藉由測量來決定是0或1的狀態，這個過程是機率的操作，因而增加鄰近解的多樣性，且利用量子旋轉閘趨使搜尋方向可以往較有吸引力的區域移動。我們將此演算法應用於求解 0/1 背包問題，並與傳統的基因演算法、禁忌搜尋演算法和量子啟發式演算法做分析比較，實驗結果顯示量子啟發式禁忌搜尋演算法優於其它啟發式演算法，證明其可以避免過早收斂而能有效地解決0/1背包問題。我們更進一步地嘗試拓展此演算法應用於不同的組合最佳化問題中，例如多限制式背包問題與旅行推銷員問題，來驗證此演算法的成效。

關鍵字

量子計算 ； 組合最佳化 ； 量子啟發式演化計算 ； 禁忌搜尋 ； 背包問題

並列摘要

In this research, we propose a novel quantum-inspired evolutionary algorithm, called quantum-inspired Tabu search (QTS). QTS is based on the classical Tabu search and the characteristic of quantum computation, such as superposition. The process of qubit measurement is a probability operation that increases the diversification, and quantum rotation gate used for searching toward the attractive regions will increase the intensification. We will present how we implement QTS to solve 0/1 knapsack problem. Furthermore, the results of experiment are also compared with other heuristic algorithms such as conventional Genetic Algorithm, Tabu Search Algorithm and the original Quantum-inspired Evolutionary Algorithm (QEA)’ experimental results. The final outcomes shows that QTS performs much better than the other on 0/1 knapsack problem, without premature convergence and with more efficiency. We further attempt to expand this algorithm applied to different combinatorial optimization problems, such as multiple knapsack problem and traveling salesman problem to verify its effectiveness.

並列關鍵字

Quantum Computing ； Combinatorial Optimization ； Quantum-inspired ； Evolutionary Algorithm ； Tabu Search ； Knapsack Problem

參考文獻

[1] H. Talbi, A. Draa and M. Batouche, “A new quantum-inspired genetic algorithm for solving the travelling salesman problem,” IEEE ICIT, vol. 3, pp. 1192 - 1197, 2004.

[2] Y. Wanga, X. Y. Fenga, Y. X. Huanga, D. B. Pub, W. G. Zhoua, Y. C. Lianga and C. G. Zhou, “A novel quantum swarm evolutionary algorithm and its applications” in Neurocomputing, January, 2007, pp. 633-640.

[3] A. Narayan and C. Patvardhan, “A novel quantum evolutionary algorithm for quadratic Knapsack problem,” in Proc. Systems, Man and Cybernetics, 2009. SMC 2009. IEEE International Conference on, pp. 1388-1392, 11-14 October 2009.

[4] B. B. Li and W. Ling, “A Hybrid Quantum-Inspired Genetic Algorithm for Multiobjective Flow Shop Scheduling,” IEEE Transactions on System, Man and Cybernetics, PART B: CYBERNETICS, vol. 37, no. 3, pp. 576-591, June 2007.

[5] K. H. Han and J. H. Kim, “Genetic quantum algorithm and its application to combinatorial optimization problem,” in Proc. 2000 Congress on Evolutionary Computation. Piscataway, NJ, IEEE Press, vol. 2, pp. 1354-1360, July 2000.