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

Dianzi xuebao

A Quantum Genetic Algorithm to Solve Combinatorial Optimization Problem

Xing-Fu Wang

Published Jan 1, 2004• 17 citations
OpenAlex

Abstract

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.

Related papers

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 Improved Quantum Genetic Algorithm for Combinatorial Optimization Problems

Xihua Zou

Based on quantum genetic algorithm(QGA),a novel improved quantum genetic algorithm(NIQGA)to solve combinatorial optimization problem is proposed.To make full use of interference and entanglement characteristics of quantum state,dynamic step length in adjustment of angle of quantum gate,quantum crossover operation and quantum mutation operation are introduced,therefore high efficiency for optimization is achieved.Two typical combinatorial optimization problems—0/1 knapsack problem and route selection problem,are adopted to confirm the performance of NIQGA.Experimental results show that compared with GA and QGA,NIQGA is characterized by fast convergence rate and excellent capability on global optimization,especially better performance for combinatorial optimization problem with less correlation of genes.

Dianzi xuebao•Jan 1, 2007•15 citations

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

A Survey of Quantum Genetic Algorithm for Combinatorial Optimization Problems

Feng Mei Wei, Jian Pei Zhang, Bing Li +1 more

Combined with quantum computing and genetic algorithm, quantum genetic algorithm (QGA) shows considerable ability of parallelism. Experiments have shown that QGA performs quite well on TSP, job shop problem and some other typical combinatorial optimization problems. The other problems like nutritional diet which can be transformed into specific combinational optimization problem also can be solved through QGA smoothly. This paper sums up the main points of QGA for general combinatorial optimization problems. These points such as modeling of the problem, qubit decoding and rotation strategy are useful to enhance the convergence speed of QGA and avoid premature at the same time.

Applied Mechanics and Materials•Jun 10, 2014•2 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

An adaptive quantum evolution algorithm for 0–1 knapsack problem

Valerii M. Tkachuk

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.

System research and information technologies•Jun 20, 2018•1 citation
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.
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.
Based on quantum genetic algorithm(QGA),a novel improved quantum genetic algorithm(NIQGA)to solve combinatorial optimization problem is proposed.To make full use of interference and entanglement characteristics of quantum state,dynamic step length in adjustment of angle of quantum gate,quantum crossover operation and quantum mutation operation are introduced,therefore high efficiency for optimization is achieved.Two typical combinatorial optimization problems—0/1 knapsack problem and route selection problem,are adopted to confirm the performance of NIQGA.Experimental results show that compared with GA and QGA,NIQGA is characterized by fast convergence rate and excellent capability on global optimization,especially better performance for combinatorial optimization problem with less correlation of genes.
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.
Combined with quantum computing and genetic algorithm, quantum genetic algorithm (QGA) shows considerable ability of parallelism. Experiments have shown that QGA performs quite well on TSP, job shop problem and some other typical combinatorial optimization problems. The other problems like nutritional diet which can be transformed into specific combinational optimization problem also can be solved through QGA smoothly. This paper sums up the main points of QGA for general combinatorial optimization problems. These points such as modeling of the problem, qubit decoding and rotation strategy are useful to enhance the convergence speed of QGA and avoid premature at the same time.
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.
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.