Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IOP Conference Series Materials Science and Engineering

An Angle-expressed Quantum Evolutionary Algorithm for Quadratic Knapsack Problem

Hao Li

Published Oct 1, 2019• 2 citations
Publisher

Abstract

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.

DOI
10.1088/1757-899x/631/5/052054

Related papers

An Improved Quantum Evolutionary Algorithm for High Dimension Knapsack Problem

Hao Li, Lei Ma, Na Qin

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.

Frontiers in artificial intelligence and applications•Jan 1, 2017•0 citations

A novel quantum evolutionary algorithm for quadratic Knapsack problem

Apurva Narayan, C. Patvardhan

The Quadratic Knapsack Problem (QKP) deals with maximizing a quadratic objective function subject to given constraints on the capacity of the Knapsack. We assume all coefficients to be non-negative and all variables to be binary. Solution to QKP generalizes the problem of finding whether a graph contains a clique of given size. We propose in this paper a Novel Quantum Evolutionary Algorithm (NQEA) for QKPs. These algorithms are general enough and can be used for similar subsection of problems. We report in this paper solutions which lie in less than 1% of the optimal solutions. We also show that our algorithm is scalable to much larger problem sizes and is capable of exploiting the search space to its maximum.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2009•13 citations

Improved Quantum Evolutionary Algorithm for Combinatorial Optimization Problem

Rui Zhang, Hui Gao

The method of calculating rotation angle of quantum rotation gate plays an important role to the performance of quantum evolutionary algorithm (QEA). This paper proposes an improved quantum evolutionary algorithm (IQEA), whose core is that a new approach of adaptive calculating rotation angle of quantum rotation gate is designed on the basis of the probability amplitude ratio of the corresponding states. Rapid convergence and good global search capability characterize the performance of IQEA. Based on a typical combinatorial optimization problem - 0/1 knapsack problems, the influence of the relative parameter to the performance of IQEA is demonstrated, and then comparing experiments have been done. The results show that IQEA is superior to the previous quantum evolutionary algorithm.

International Conference on Machine Learning and Cybernetics•Jan 1, 2007•37 citations

Quantum-inspired evolutionary algorithm for a class of combinatorial optimization

Kuk-Hyun Han, Jong-Hwan Kim

This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, evaluation function, and population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, experiments were carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm.

IEEE Transactions on Evolutionary Computation•Dec 1, 2002•1,592 citations

A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems

Parvaz Mahdabi, Saeed Jalili, Mahdi Abadi

Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired evolutionary algorithm, called MSQIEA. To improve the performance of the algorithm, a multi-measurement operator and a new strategy for updating the rotation angle is proposed. When Q-bit individuals start to converge to their final states, the best solution is stored and all Q-bits in each Q-bit individual are reinitialized. We compare the effectiveness of MSQIEA with a popular quantum-inspired evolutionary algorithm, called QEA, for solving 0-1 knapsack problem. The experimental results show that MSQIEA outperforms QEA and finds a solution with higher profit.

Genetic and Evolutionary Computation Conference (GECCO)•Jul 12, 2008•16 citations

A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems

Parvaz Mahdabi, Mahdi Abadi, Saeed Jalili

In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search space. In the operator, first, the Q-bits of each individual in the population are updated based on the personal best measurement of that individual and the best measurement of current generation. Then, a restriction is applied to each Q-bit to prevent the premature convergence of its values. The results of experiments on the 0-1 knapsack and NK-landscapes problems show that NQEA performs better than a classical genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms, QEA and vQEA, in terms of convergence speed and accuracy.

Genetic and Evolutionary Computation Conference (GECCO)•Jul 8, 2009•7 citations
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.
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.
The Quadratic Knapsack Problem (QKP) deals with maximizing a quadratic objective function subject to given constraints on the capacity of the Knapsack. We assume all coefficients to be non-negative and all variables to be binary. Solution to QKP generalizes the problem of finding whether a graph contains a clique of given size. We propose in this paper a Novel Quantum Evolutionary Algorithm (NQEA) for QKPs. These algorithms are general enough and can be used for similar subsection of problems. We report in this paper solutions which lie in less than 1% of the optimal solutions. We also show that our algorithm is scalable to much larger problem sizes and is capable of exploiting the search space to its maximum.
The method of calculating rotation angle of quantum rotation gate plays an important role to the performance of quantum evolutionary algorithm (QEA). This paper proposes an improved quantum evolutionary algorithm (IQEA), whose core is that a new approach of adaptive calculating rotation angle of quantum rotation gate is designed on the basis of the probability amplitude ratio of the corresponding states. Rapid convergence and good global search capability characterize the performance of IQEA. Based on a typical combinatorial optimization problem - 0/1 knapsack problems, the influence of the relative parameter to the performance of IQEA is demonstrated, and then comparing experiments have been done. The results show that IQEA is superior to the previous quantum evolutionary algorithm.
This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, evaluation function, and population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, experiments were carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm.
Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired evolutionary algorithm, called MSQIEA. To improve the performance of the algorithm, a multi-measurement operator and a new strategy for updating the rotation angle is proposed. When Q-bit individuals start to converge to their final states, the best solution is stored and all Q-bits in each Q-bit individual are reinitialized. We compare the effectiveness of MSQIEA with a popular quantum-inspired evolutionary algorithm, called QEA, for solving 0-1 knapsack problem. The experimental results show that MSQIEA outperforms QEA and finds a solution with higher profit.
In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search space. In the operator, first, the Q-bits of each individual in the population are updated based on the personal best measurement of that individual and the best measurement of current generation. Then, a restriction is applied to each Q-bit to prevent the premature convergence of its values. The results of experiments on the 0-1 knapsack and NK-landscapes problems show that NQEA performs better than a classical genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms, QEA and vQEA, in terms of convergence speed and accuracy.