International Journal of Computer Applications
Optimization with Quantum Genetic Algorithm
Bhaskar Das, Utpal Roy
Abstract
Recent development in quantum technology have shown that quan-tum computer can provide a dramatic advantage over classical com-puters for some algorithms. In particular, a polynomial-time algo-rithm for factoring, a problem which was previously thought to be hard for classical computers, has recently been developed [13]. Similarly, a quantum algorithm searching for unsorted database in square root of time it would take on a classical computer has also been described by Grover [4]- [3]. Both algorithms rely upon the inherent parallelism, superposition and entanglement property of quantum computing to achieve their improvements. Since most problems of real interest for genetic algorithms have a vast search space, it seems appropriate how quantum parallelism can be ap-plied to Genetic Algorithms. In this paper we provide a brief back-ground of quantum computers. We explain why and how quan-tum algorithms provides a fundamental improvements over classi-cal ones for some problems. Further, we present here the Conven-tional Genetic Algorithm and the quantum approach of Genetical Algorithms(QGA) as well. The benefits and drawbacks of QGA are also analyzed. Moreover, this paper provides an improved version over the con-ventional QGA. This improvement originates from the best partial immigration technique applied to the quantum chromosomes. The main objective of the best partial immigration is to consider the string of qubits from the quantum chromosomes having best fit-ness and transfer the same randomly to the chromosomes of next generation for better mixing. The process is reiterated. To observe the performance the best partial immigration technique we have considered some popular optimization problems and performed the experiment on it. These problems are namely Travelling Salesman Problem(TSP), Binpacking Problem and Vertex Cover Problem. It has been observed that the obtained results outperforms the con-ventional QGA. 1.