Performance Analysis of Quantum-Inspired Evolutionary Algorithm
Tomohisa Takata, Teijiro Isokawa, and Nobuyuki Matsui
Graduate School of Engineering, University of Hyogo, 2167 Shosha, Himeji, Hyogo 671-2280, Japan
Quantum-Inspired Evolutionary Algorithm (QEA) is an extension of evolutionary algorithm in which quantum mechanics and its representations are introduced. A chromosome in QEA is represented as a series of qubits (quantum bits), and phase-rotation gates are embedded into the selection process over generations. This algorithm has been shown to have better performances than the classical ones in small benchmark problems, but this has not yet been applied to larger scale problems. We show the performances of this QEA by solving the Knapsack problem, maximum search problem, and construction of image filter. We also investigate the diversity of individuals in a population in order to estimate the robustness against environmental changes.
-  P.W. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Proc. the 35th Annual IEEE Symposium on foundation of Computer Science, pp. 124-134, 1994.
-  T. Nitta, “Complex-Valued Neural Networks, Utilizing High-Dimensional Parameters,” Information science reference, IGI global, 2009.
-  N. Kouda, N. Matsui, H. Nishimura, and F. Peper, “Qubit Neural Network and Its Learning Efficiency,” Neural Computing and Applications, Vol.14, No.2, pp. 114-121, 2005.
-  N. Kouda, N. Matsui, and H. Nishimura, “Image Compression by Layered Quantum Neural Networks,” Neural Processing Letters, Vol.16, pp. 67-80, 2002.
-  N. Kouda, N. Matsui, H. Nishimura, and F. Peper, “An Examination of Qubit neural network in Controlling an Inverted Pendulum,” Neural Processing Letters, Vol.22, No.3, pp. 277-290, 2005.
-  A. Narayanan and M. Moore, “Quantum-inspired genetic algorithms,” Proc. IEEE Int. Conf. Evolutionary Computation, pp. 61-66, 1996.
-  K. H. Han and J. H. Kim, “Genetic quantum algorithm and its application to combinatorial optimization problem,” Proc. IEEE Congr. on Evolutionary Computation, pp. 1354-1360, 2000.
-  S. Y. Yang, M. Wang, and L. C. Jiao, “A Novel Quantum Evolutionary Algorithm and Its Application,” Proc. IEEE Congr. on Evolutionary Computation, pp. 820-826, 2004.
-  W. Liu, H. Chen, Q. Yan, Z. Liu, J. Xu, and Y. Zheng, “A Novel Quantum-Inspired Evolutionary Algorithm Based on Variable Angle-Distance Rotation,” IEEE World Congress on Computational Intelligence, No.7218, 2010.
-  T. Imabeppu, S. Nakayama, and S. Ono, “A study on a quantuminspired evolutionary algorithm based on pair swap,” Artificial Life and Robotics, Vol.12, No.1-2, pp. 148-152, 2008.
-  J. H. Holland, “Adaptation in natural and artificial systems,” University of Michigan Press, 1975.
-  L. J. Fogel et al., “Artificial Intelligence through Simulated Evolution,” John Willey & Sons, 1966.
-  I. Rechenberg, “Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution,” Ph.D. thesis, 1971.
-  T. Bäck, F. Hoffmeister, and H.-P. Schwefel, “A Survey of Evolution Strategies,” Proc. 4th Int. Conf. on Genetic Algorithms, pp. 2-9, 1991.
-  T. Isokawa, N. Matsui, H. Nishimura, and F. Peper, “Coping with Nonstationary Environments: A Genetic Algorithm Using Neutral Variation,” IEEE Trans. on Systems, Man, and Cybernetics, Vol.32, No.4, pp. 497-504, 2002.
-  N. Matsui, H. Nishimura, and T. Isokawa, “Qubit Neural Network: Its Performance and Applications,” T. Nitta (Ed.) Complex-Valued Neural Networks: Utilizing High-Dimensional Parameters, pp. 325-351, 2009.
-  S. Masunaga and T. Nagao, “Automatic construction of image transformation processes using Genetic Algorithm,” Proc. Int. Conf. on Image Processing’96, pp. 731-736, 1996.