An Angle-expressed Quantum Evolutionary Algorithm for Quadratic Knapsack Problem
Hao Li · IOP Conference Series Materials Science and Engineering · 2019
Abstract The quadratic knapsack problem(QKP) is a typical combinatorial optimization problem. It is arisen in many optimization fields, but there exist no pseudo-polynomial time algorithm to solve it. In this paper, we propose an angle-expressed quantum evolutionary algorithm to solve QKP. In this algorithm, the qubits are expressed in the angle and initialized according to the value densities of their corresponding items, the rotation angle of Q-gate is determined through an analytical formula, and Hε gate is used to prevent from premature convergence. For infeasible solution, a dynamic value density is introduced to choose item to be selected or dropped. Finally, experiment demonstrates the effectiveness of the algorithm.