An Improved Quantum Evolutionary Algorithm for High Dimension Knapsack Problem

摘要

Knapsack problem is a typical combinatorial optimization problem, which has attracted wide attention because of its simple description, difficult solution and wide application background. For the knapsack problem, we proposed an improved quantum evolutionary algorithm. In this algorithm, the qubits are initialized according to the value densities of their corresponding items, the angle of Q-gate is determinated through direct comparison between the quantum chromosome and the optimal solution, random crossover method is taken to share information among chromosomes, and Hε gate is used to prevent from premature convergence. Finally, experiment demonstrates the effectiveness of the algorithm.