Article Preview
Top1. Introduction
Evolutionary Algorithms (EAs) are popular population- based meta-heuristic techniques inspired from the natural process of evolution which have been used with advantage in a large variety of applications (Goldberg, 1989; Mitchell, 1996; Bäck, Fogel, & Michalewicz, 1997a; Bäck, Hammel, & Schwefel, 1997b; Zhou, et al., 2011). However, slow convergence remains a huge problem especially for large problem instances. Quantum computers use quantum bits (qubits) as the smallest unit of information (Hey, 1999). Quantum Inspired Evolutionary Algorithms (QIEAs) (Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization, 2002) form a subclass of EAs. These exploit the advantages of quantum representation, superposition of states and operators to mitigate some of the limitations in EAs for better search and optimization (Zhang G., 2011). A variety of QIEAs, shown to be effective for search and optimization problems, have been developed. Conceptual comparison between EAs and QIEAs is summarized in Table 1.
Table 1. Comparison between EAs and QIEAs
| Similarities | Differences |
1. | Both EAs and QIEAs work with individuals and population(s) | EA represents solutions as individuals specifying parameter values of problem being solved. QIEA utilizes Q-bit strings. A Q-bit string is a superposition of all possible solutions. Thus, individuals in EAs are particular solutions in search space while the individuals in QIEAs are probabilistic representations of the search space. |
2. | Both EAs and QIEAs use operators to update individuals | Reproduction operators in EAs are applied directly on solutions while in QIEAs operators are applied on the Q-bit strings. |
3. | Both evaluate solutions to measure their fitness. | In EAs a set of good solutions are selected to be used as parents for producing better children in future generations. While in QIEAs, a few good solutions are selected, these may then be used to update Q-bit strings so that solutions closer to the best solutions found are generated in subsequent iterations. |
4. | Both generate new solutions in each iteration | In EAs, solutions are generated through reproductive operations on existing solutions while in QIEAs solutions are generated through observation on updated Q-bit individuals. |
Although QIEAs are inspired from quantum computing, they are not meant for quantum computers. QIEA is another evolutionary algorithm for a classical computer. The basic building blocks of a typical QIEA are explained as follows: