Research on 0–1 Backpack Problem based on Improved Quantum Tabu Genetic Algorithm
Yuchen Sun · 2023
The 0–1 backpack problem(0-1KP) is one of the very common combinatorial optimization problems, and is also a widely studied NP-complete problem. In this paper, we propose a Dynamic Strategy Tabu Search Operator Based Quantum Genetic Algorithm (DTS-QGA), which introduces the tabu search operator on the basis of the quantum genetic algorithm. To verify the feasibility and superiority of the algorithm, we have completed multiple independent experiments on 10 sets of 0–1 backpack test data with different data dimensions. The experiments demonstrate that the algorithm presented in this paper has a strong capability to perform global search, avoids local optima and achieves faster convergence.