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

IEEE Congress on Evolutionary Computation (CEC)

Genetic quantum algorithm and its application to combinatorial optimization problem

Kuk-Hyun Han, Jong-Hwan Kim

Published Nov 7, 2002• 672 citations
Publisher

Abstract

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.

DOI
10.1109/cec.2000.870809

Related papers

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

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 Random search and Greedy selection based Genetic Quantum Algorithm for combinatorial optimization

R. S. Pavithr, Gursaran

Genetic Quantum Algorithm (GQA) is an evolutionary algorithm in the class of quantum inspired evolutionary algorithms inspired by the principles of quantum computing such as Q-bits, super position, quantum gates, interference and coherence. GQA adopts Q-bit representation and applies quantum rotation gate (QR gate) as genetic operator. The performance of the quantum inspired evolutionary algorithms largely depends upon the effectiveness of quantum gates applied as the genetic operator. Researchers have attempted to improve the performance of quantum inspired evolutionary algorithms by designing various quantum evolutionary operators using different strategies. In this paper, an effort is made to study the impact of Random search based QR gate strategy in GQA, and subsequently a Random search and greedy selection based Genetic Quantum Algorithm (RSGS-GQA) is proposed. The performance of RSGS-GQA algorithm is compared with the standard quantum inspired evolutionary algorithms (QIEA) on knapsack problem. The results indicate that, the RSGS-GQA algorithm performs better than the standard QIEA variants in terms of the quality of the solution and convergence.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2013•4 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

New Method For Geometric Constraint Solving Based on the Genetic Quantum Algorithm

Chunhong Cao, Wenhui Li

This paper proposes a novel genetic quantum algorithm (GQA) to solve geometric constraint problems. Instead of binary, numeric or symbolic representation, we introduce qubit chromosome representation. GQA is based on qubit and superposition of states and is used in the process of geometric constraint solving in order to get the solution sequence. As GQA has diversity caused by the qubit representation, there is no need to use the genetic operator. Qubit chromosome can be updated by proper quantum gate in the circulation. The experiment indicates GQA can solve the geometric constraint problem effectively. Keywords Geometric constraint solving geometric decomposing genetic algorithm quantum computing genetic quantum algorithm quantum gate qubit chromosome 1. Geometric Constraint Solving Geometric constraint solving is a remarkable problem based on the constraint design. Once a user defines a series of relations, the system will satisfy the constraints by selecting proper state after the

•Jan 1, 2004•0 citations

A novel genetic algorithm based on the quantum chromosome

Shuyuan Yang, Fang Liu

The genetic algorithm is an efficient optimization tool for its independence of problems, intrinsic parallelism and inherent learning capacity; however, it has some disadvantages such as slow convergence and prematurity. In this paper, a novel algorithm, called the quantum genetic algorithm—QGA, is proposed based on the combination of the quantum theory with the evolutionary theory. By adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. The random observation simulating the quantum collapse can bring diverse individuals, and the evolution of quantum chromosome can also pilot the evolution. So it has better diversity than the classical genetic algorithm. Rapid convergence and good global search capacity characterize the performance of QGA. The paper not only proves the global convergence of the QGA, but also some simulation experiments are shown to prove its superiority over other algorithms.

Journal of Xidian University•Jan 1, 2004•13 citations
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.
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.
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.
Genetic Quantum Algorithm (GQA) is an evolutionary algorithm in the class of quantum inspired evolutionary algorithms inspired by the principles of quantum computing such as Q-bits, super position, quantum gates, interference and coherence. GQA adopts Q-bit representation and applies quantum rotation gate (QR gate) as genetic operator. The performance of the quantum inspired evolutionary algorithms largely depends upon the effectiveness of quantum gates applied as the genetic operator. Researchers have attempted to improve the performance of quantum inspired evolutionary algorithms by designing various quantum evolutionary operators using different strategies. In this paper, an effort is made to study the impact of Random search based QR gate strategy in GQA, and subsequently a Random search and greedy selection based Genetic Quantum Algorithm (RSGS-GQA) is proposed. The performance of RSGS-GQA algorithm is compared with the standard quantum inspired evolutionary algorithms (QIEA) on knapsack problem. The results indicate that, the RSGS-GQA algorithm performs better than the standard QIEA variants in terms of the quality of the solution and convergence.
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 genetic quantum algorithm (GQA) to solve geometric constraint problems. Instead of binary, numeric or symbolic representation, we introduce qubit chromosome representation. GQA is based on qubit and superposition of states and is used in the process of geometric constraint solving in order to get the solution sequence. As GQA has diversity caused by the qubit representation, there is no need to use the genetic operator. Qubit chromosome can be updated by proper quantum gate in the circulation. The experiment indicates GQA can solve the geometric constraint problem effectively. Keywords Geometric constraint solving geometric decomposing genetic algorithm quantum computing genetic quantum algorithm quantum gate qubit chromosome 1. Geometric Constraint Solving Geometric constraint solving is a remarkable problem based on the constraint design. Once a user defines a series of relations, the system will satisfy the constraints by selecting proper state after the
The genetic algorithm is an efficient optimization tool for its independence of problems, intrinsic parallelism and inherent learning capacity; however, it has some disadvantages such as slow convergence and prematurity. In this paper, a novel algorithm, called the quantum genetic algorithm—QGA, is proposed based on the combination of the quantum theory with the evolutionary theory. By adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. The random observation simulating the quantum collapse can bring diverse individuals, and the evolution of quantum chromosome can also pilot the evolution. So it has better diversity than the classical genetic algorithm. Rapid convergence and good global search capacity characterize the performance of QGA. The paper not only proves the global convergence of the QGA, but also some simulation experiments are shown to prove its superiority over other algorithms.