Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems
Kuo-Chun Tseng, Wei-Chieh Lai, I-Chia Chen, Yun-Hsiang Hsiao, Jr-Yu Chiue, Wei-Chun Huang · 2024
In this study, we learned more about quantum properties from quantum and metaheuristic algorithms after conducting many experiments. We then propose an improved version of Quantum-inspired Tabu Search (QTS), which en-hances the utilization of population information. The new version is called “Amplitude-Ensemble” QTS (AE-QTS). This makes AE-QTS more similar to the real quantum search algorithm, Grover Search Algorithm, in abstract concept, while keeping the simplicity of the algorithm. Later, we demonstrate the AE-QTS on the classical combinatorial optimization 0/1 knapsack problem. Experimental results show that the AE-QTS outperforms other algorithms, including the QTS, by at least an average increase of nearly 20% in all cases and even by 30% in some cases. Even as the problem complexity increases, the quality of the solutions found by our method remains superior to that of the QTS. These results confirm that our method has better search performance.