Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929701369413632 |
|---|---|
| author | Tseng, Kuo-Chun Lai, Wei-Chieh Chen, I-Chia Hsiao, Yun-Hsiang Chiue, Jr-Yu Huang, Wei-Chun |
| author_facet | Tseng, Kuo-Chun Lai, Wei-Chieh Chen, I-Chia Hsiao, Yun-Hsiang Chiue, Jr-Yu Huang, Wei-Chun |
| contents | In this paper, an improved version of QTS (Quantum-inspired Tabu Search) has been proposed, which enhances the utilization of population information, 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 of 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 prove that our method has better search performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_12867 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems Tseng, Kuo-Chun Lai, Wei-Chieh Chen, I-Chia Hsiao, Yun-Hsiang Chiue, Jr-Yu Huang, Wei-Chun Quantum Physics Neural and Evolutionary Computing In this paper, an improved version of QTS (Quantum-inspired Tabu Search) has been proposed, which enhances the utilization of population information, 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 of 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 prove that our method has better search performance. |
| title | Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems |
| topic | Quantum Physics Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2311.12867 |