Parallel quantum-inspired genetic algorithm for combinatorial optimization problem
- 13 November 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 1422
- https://doi.org/10.1109/cec.2001.934358
Abstract
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.Keywords
This publication has 7 references indexed in Scilit:
- Representation, constraint satisfaction and the knapsack problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Quantum computing for beginnersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Topology and migration policy of fine-grained parallel evolutionary algorithms for numerical optimizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Genetic quantum algorithm and its application to combinatorial optimization problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Evolutionary Computation: Theory and ApplicationsPublished by World Scientific Pub Co Pte Ltd ,1999
- Quantum computing: an introductionComputing & Control Engineering Journal, 1999
- Evolutionary programming techniques for constrained optimization problemsIEEE Transactions on Evolutionary Computation, 1997