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

System research and information technologies

An adaptive quantum evolution algorithm for 0–1 knapsack problem

Valerii M. Tkachuk

Published Jun 20, 2018• 1 citation
Publisher

Abstract

Quantum Genetic Algorithm (QGA) has a number of advantages in comparison with its classical version: operating speed, small population size and auto-balance between the global search and the local search. It is based on the ideas of traditional evolutionary algorithms, applied to the quantum computations technology, which operate with quantum bits, superposition of states and quantum measurements. This paper proposes a QGA with a new adaptive quantum gate operator and a restoring technology for the quantum chromosome during the process of solving combinatorial problems with constraints. Meta-optimization of the primary algorithm parameters is used for providing the algorithm efficiency. The productiveness of the suggested approach is proven by the model studies, carried out using a wide range of test 0–1 knapsack problems.

DOI
10.20535/srit.2308-8893.2018.2.08

Related papers

Higher-order quantum genetic algorithm for 0-1 knapsack problem

Valerii M. Tkachuk, Orysya M. Tkachuk

In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In the algorithm implementation, we also use an adaptive quantum gate operator and propose a quantum chromosome recovery technology for solving constrained combinatorial optimization problems. The influence of the quantum register size on the algorithm efficiency has been investigated. The advantages of the suggested approach in comparison with the QGA traditional implementation are demonstrated on the example of multidimensional 0–1 knapsack problem and different levels of input data correlation.

System research and information technologies•Oct 16, 2018•1 citation

Parallel quantum-inspired genetic algorithm for combinatorial optimization problem

Kuk-Hyun Han, Kui-Hong Park, Ci-Ho Lee +1 more

This paper proposes a new parallel evolutionary algorithm called parallel quantum-inspired genetic algorithm (PQGA). Quantum-inspired genetic algorithm (QGA) is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. QGA is suitable for parallel structures because of rapid convergence and good global search capability. That is, QGA is able to possess the two characteristics of exploration and exploitation simultaneously. The effectiveness and the applicability of PQGA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that PQGA is superior to QGA as well as other conventional genetic algorithms.

IEEE Congress on Evolutionary Computation (CEC)•Nov 13, 2002•193 citations

An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem

Rui Wang, Ning Guo, Fenghong Xiang +1 more

An improved quantum genetic algorithm (IQGA) is proposed in this paper, which codes the chromosome with probability amplitudes represented by sine and cosine functions, and uses an adaptive strategy of the rotation angle to update the population. Then the mutation operation is considered in this improved quantum genetic algorithm (MIQGA). Rapid convergence and good global search capability characterize the performance of MIQGA. While testing, a variance function is introduced to estimate the stability of the algorithm. When solving 0-1 knapsack problem, greedy repair function is used to repair unfeasible solutions. Experimental results show MIQGA has better comprehensive performance than traditional genetic algorithm (GA), standard quantum genetic algorithm (QGA) and IQGA, especially the superiority in terms of optimization quality and population diversity.

International Conference on Measurement, Information and Control•May 1, 2012•4 citations

Genetic quantum algorithm and its application to combinatorial optimization problem

Kuk-Hyun Han, Jong-Hwan Kim

This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.

IEEE Congress on Evolutionary Computation (CEC)•Nov 7, 2002•672 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

A Quantum Genetic Algorithm to Solve Combinatorial Optimization Problem

Xing-Fu Wang

Based on quantum mutation, a quantum genetic algorithm (QGA) to solve combinatorial optimization problem is proposed.It has good features of genetic quantum algorithm (GQA) and traditional genetic algorithm,which can obtain the best solution with one chromosome in a short time.Comparing experiments have been conducted on a typical combinatorial optimization problem——0/1 knapsack problem.Experimental results have shown that the proposed quantum genetic algorithm is superior to genetic quantum algorithm and traditional genetic algorithm on performance.

Dianzi xuebao•Jan 1, 2004•17 citations
Quantum Genetic Algorithm (QGA) has a number of advantages in comparison with its classical version: operating speed, small population size and auto-balance between the global search and the local search. It is based on the ideas of traditional evolutionary algorithms, applied to the quantum computations technology, which operate with quantum bits, superposition of states and quantum measurements. This paper proposes a QGA with a new adaptive quantum gate operator and a restoring technology for the quantum chromosome during the process of solving combinatorial problems with constraints. Meta-optimization of the primary algorithm parameters is used for providing the algorithm efficiency. The productiveness of the suggested approach is proven by the model studies, carried out using a wide range of test 0–1 knapsack problems.
In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In the algorithm implementation, we also use an adaptive quantum gate operator and propose a quantum chromosome recovery technology for solving constrained combinatorial optimization problems. The influence of the quantum register size on the algorithm efficiency has been investigated. The advantages of the suggested approach in comparison with the QGA traditional implementation are demonstrated on the example of multidimensional 0–1 knapsack problem and different levels of input data correlation.
This paper proposes a new parallel evolutionary algorithm called parallel quantum-inspired genetic algorithm (PQGA). Quantum-inspired genetic algorithm (QGA) is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. QGA is suitable for parallel structures because of rapid convergence and good global search capability. That is, QGA is able to possess the two characteristics of exploration and exploitation simultaneously. The effectiveness and the applicability of PQGA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that PQGA is superior to QGA as well as other conventional genetic algorithms.
An improved quantum genetic algorithm (IQGA) is proposed in this paper, which codes the chromosome with probability amplitudes represented by sine and cosine functions, and uses an adaptive strategy of the rotation angle to update the population. Then the mutation operation is considered in this improved quantum genetic algorithm (MIQGA). Rapid convergence and good global search capability characterize the performance of MIQGA. While testing, a variance function is introduced to estimate the stability of the algorithm. When solving 0-1 knapsack problem, greedy repair function is used to repair unfeasible solutions. Experimental results show MIQGA has better comprehensive performance than traditional genetic algorithm (GA), standard quantum genetic algorithm (QGA) and IQGA, especially the superiority in terms of optimization quality and population diversity.
This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.
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.
Based on quantum mutation, a quantum genetic algorithm (QGA) to solve combinatorial optimization problem is proposed.It has good features of genetic quantum algorithm (GQA) and traditional genetic algorithm,which can obtain the best solution with one chromosome in a short time.Comparing experiments have been conducted on a typical combinatorial optimization problem——0/1 knapsack problem.Experimental results have shown that the proposed quantum genetic algorithm is superior to genetic quantum algorithm and traditional genetic algorithm on performance.