Abstract

The development in the field of quantum computing gives us a significant edge over classical computing in terms of time and efficiency. This is particularly useful for NP-hard problems such as graph layout problems. Since many real world problems are effectively solved by genetic algorithm (GA) and the performance of GA highly depends upon the setting of its parameters, therefore this paper focuses on a Quantum Inspired Genetic Algorithm (QIGA) and develops and evaluates adaptive strategies for the same. QIGA adapts ideas of Q-bits, superposition of Q-bits from quantum computing. The effectiveness and the applicability of adaptive QIGA is demonstrated by experimental results on the benchmark Knapsack, Maxcut and Onemax combinatorial optimization problems. The results show that adaptive QIGA is superior to QIGAs.

References

• Sean Luke, Essentials of Metaheuristics: A Set of Undergraduate Lecture Notes, Department of Computer Science George Mason University, 2012.
• Ko Hisn Liang, Xin Yao and Charls S. Newton, "Adapting Self-Adaptive Parameters in Evolutionary Algorithms", Applied Intelligence, 15, 1771-180, Kulwer Academic Publisher, 2001.
• Imtiaz Korejo, Shengxiang Yang and Chaanghe Li, "A Comparative Study of Adaptive Mutation Operators for Genetic Algorithm", Metaheuristic International Conference, Hymberg, Germany July 13-16, 2009.
• B. Rylander, T. Soule, J. Foster, J. Alves-Foss, " Quantum Genetic Algorithms". In Proc. GECCO, pp. 373- 377, 2000.
• Tzung-Pei Hong , Hong-Shung Wang , Wen-Yang Lin , Wen-Yuan Lee, "Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process", Applied Intelligence, v. 16 n. 1, p. 7-17, January-February 2002.
• Huaixiao Wang, Jianyong Liu, Jun Zhi and Chengqun Fu, "The Improvement of Quantum Genetic Algorithm and Its Application on Function Optimization", Mathematical Problems in Engineering, Volume 2013, 2013.
• S. Meyer-Nieberg and H. G. Beyer, "Self- Adaptation in Evolutionary Algorithms", Studies in Computational Intelligence (SCI) 54, 47–75, Springer- Verlag Berlin Heidelberg 2007.
• Oliver Kramer, "Evolutionary Self- Adaptation: A Survey of Operators and Strategy Parameters", Evolutionary Intelligence, pp. 51-65, 2010.
• Renato Tin´os and Shengxiang Yang, "Self- Adaptation of Mutation Distribution in Evolutionary Algorithms", IEEE Congress on Evolutionary Computation, 2007.
• Bartlomeij Gloger, Lecture notes on Self Adaptive Evolutionary Algorithms,University of Paderborn, 2004.
• Wen-Yanglin, Wen-Yuanlee and Tzung-Peihong, "Adapting Crossover and Mutation Rates in Genetic Algorithms", Journal of Information Science and Engineering 19, pp. 889-903 ,2003.
• Kuk-Hyun Han and Jong-Hwan Kim, "Quantum-inspired Evolutionary Algorithm for a Class of Combinatorial Optimization", IEEE transaction on Evolutionary Computation, Vol. 6, No. 6, December 2002.
• D. Ashlock, Evolutionary Computation for Modeling and Optimization, Springer, ISBN 0-387-22196-4, 2006.
• U. V. Vazirani, lecture notes on Qubits, Quantum Mechanics, and Computers for Chem/CS/Phys191, University of California, Berkeley, 2012. www. cs. berkeley. edu/~vazirani/.
• Mark Oskin, Quantum Computing- Lecture Notes, Department of Computer Science and Engineering, University of Washington, Washington. homes. cs. washington. edu/~oskin/.
• Kuk-Hyun Han and Jong-Hwan Kim, "Analysis of Quantum Inspired Evolutionary Algorithm", Proceedings of International Conference on Artificial Intelligence, 2001.
• James E. Smith, "Self- Adaptation in Evolutionary Algorithms for Combinatorial Optimization", Adaptive and Multilevel Metaheuristics Studies in Computational Intelligence, Volume 136, 2008, pp 31-57, 2008.
• S. Uyar, G. Eryigit, S. Sariel, "An Adaptive Mutation Scheme in Genetic Algorithms for Fastening the Convergence to the Optimum", Proceedings of the 3rd Asia Pacific International Symposium on Information Technology, pp. 461–465, 2004.
• W. M. Spears,. , "Adapting Crossover in a Genetic Algorithm", Naval Research Laboratory AI Center Report AIC-92-025, Washington, DC 20375, USA, 1992.
• Hristakeva, Maya and Dipti Shrestha. "Solving the 0/1 Knapsack Problem with Genetic Algorithms. " MICS 2004 Proceedings, 2004.
• Megha Gupta, "A Fast and Efficient Genetic Algorithm to Solve 0-1 Knapsack Problem", International Journal of Digital Application & Contemporary research, Volume 1, Issue 6, January 2013.
• Enrique Alba and Bernabe Dorronsoro, Cellular Genetic Algorithms, © Springer Science+ Business Media, LLC, pp. 213-219, 2008.