Open AccessAn Angle-expressed Quantum Evolutionary Algorithm for Quadratic Knapsack Problem
Author(s) -
Hao Li
Publication year - 2019
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/631/5/052054
Subject(s) - knapsack problem , qubit , algorithm , mathematics , convergence (economics) , quadratic equation , mathematical optimization , quantum , continuous knapsack problem , evolutionary algorithm , quadratic programming , quantum computer , value (mathematics) , combinatorial optimization , polynomial time approximation scheme , physics , quantum mechanics , statistics , geometry , economics , economic growth
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.