Higher-Order Quantum-Inspired Genetic Algorithms

• Autorzy: Robert Nowotniak , Jacek Kucharski
• Języki publikacji: EN

Abstrakty

EN

This paper presents a theory and an empirical evaluation of Higher-Order Quantum-Inspired Genetic Algorithms. Fundamental notions of the theory have been introduced, and a novel Order-2 Quantum-Inspired Genetic Algorithm (QIGA2) has been presented. Contrary to all QIGA algorithms which represent quantum genes as independent qubits, in higher-order QIGAs quantum registers are used to represent genes strings which allows modelling of genes relations using quantum phenomena. Performance comparison has been conducted on a benchmark of 20 deceptive combinatorial optimization problems. It has been presented that using higher quantum orders is beneficial for genetic algorithm efficiency, and the new QIGA2 algorithm outperforms the old QIGA algorithm which was tuned in highly compute intensive metaoptimization process.(original abstract)

Słowa kluczowe

PL

Algorytmy genetyczne; Optymalizacja matematyczna; Algorytmy

EN

Genetic algorithms; Mathematical optimization; Algorithms

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 465-470

Twórcy

autor

Robert Nowotniak

• Lodz University of Technology, Poland

autor

Jacek Kucharski

• Lodz University of Technology, Poland

Bibliografia

• Chomatek L. and Rudnicki M., "Application of genetically evolved neural networks to dynamic terrain generation", Bull. Pol. Ac.: Tech. 59 (1), 3-8 (2011).
• Durrett R., Probability: Theory and Examples, International Thomson Publishing Company, 1996.
• Goldberg D. E., Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Professional, 1989.
• Grefenstette J. J., "Optimization of control parameters for genetic algorithms", IEEE Trans. Systems, Man and Cybernetics 16, 122-128 (1986).
• Han K. H. and Kim J. H., "Genetic quantum algorithm and its application to combinatorial optimization problem", Proc. Congress on Evolutionary Computation, 1354-1360 (2000).
• Han K. H. and Kim J. H., "Quantum-inspired evolutionary algorithm for a class of combinatorial optimization", IEEE Trans. Evolutionary Computation 6, 580-593 (2002).
• Holger H. H., and Stützle T., "SATLIB: An Online Resource for Research on SAT." Proceedings of Theory and Applications of Satisfiability Testing, 4th International Conference (SAT 2000).
• Holland, John H. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, 1975.
• Jantos P., Grzechca D., and Rutkowski J., "Evolutionary algorithms for global parametric fault diagnosis in analogue integrated circuits", Bull. Pol. Ac.: Tech. 60 (1), 133-142 (2012).
• Jeong Y. W., Park J. B., Shin J. R., and Lee K. Y., "A thermal unit commitment approach using an improved quantum evolutionary algorithm", Electric Power Components and Systems 37, 770-786 (2009).
• Jeżewski S., Łaski M., and Nowotniak R., "Comparison of Algorithms for Simultaneous Localization and Mapping Problem for Mobile Robot", Scientific Bulletin of Academy of Science and Technology, Automatics 14, 439-452 (2010).
• Jopek Ł, Nowotniak R., Postolski M., Babout L., and Janaszewski M., "Application of Quantum Genetic Algorithms in Feature Selection Problem", Scientific Bulletin of Academy of Science and Technology, Automatics 13(3), 1219-1231 (2009).
• Lau T., Chung C., Wong K., Chung T., and Ho S., "Quantum-inspired evolutionary algorithm approach for unit commitment", IEEE Trans. Power Systems 24, 1503-1512 (2009).
• Li B. B. and Wang L., "A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling", IEEE Trans. Systems, Man, and Cybernetics, Part B: Cybernetics 37, 576-591 (2007).
• Luke S., Essentials of metaheuristics, lulu.com, 2009.
• Manju, A., and M. J. Nigam. "Applications of quantum inspired computational intelligence: a survey." Artificial Intelligence Review (2012): 1-78.
• Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1996.
• Narayanan A. and Moore M., "Quantum-inspired genetic algorithms", Proc. IEEE Evolutionary Computation, 61-66 (1996).
• Nielsen M. and Chuang I., Quantum computation and quantum information, Cambridge University Press, 2000.
• Nowotniak R. and Kucharski J., "Building Blocks Propagation in Quantum-Inspired Genetic Algorithm", Scientific Bulletin of Academy of Science and Technology, Automatics 14, 795-810 (2010).
• Nowotniak R. and Kucharski J., "GPU-based tuning of quantum-inspired genetic algorithm for a combinatorial optimization problem." Bulletin of the Polish Academy of Sciences: Technical Sciences 60.2 (2012): 323-330.
• Nowotniak R. and Kucharski J., "Meta-optimization of Quantum-Inspired Evolutionary Algorithm", Proc. XVII Int. Conf. on Information Technology Systems, (2010).
• Nowotniak R. and Kucharski J., Convergence analysis of Quantum-Inspired Evolutionary Algorithms based on Banach fixed point theorem, Proceedings of the 2012 FIMB PhD students conference
• Pedersen M. E. H., Tuning & Simplifying Heuristical Optimization, University of Southampton, School of Engineering Sciences, 2010.
• Perone C. S., "PyEvolve: a Python open-source framework for genetic algorithms", ACM SIGEVOlution 4, 12-20 (2009).
• Slowik A., "Application of evolutionary algorithm to design minimal phase digital filters with non-standard amplitude characteristics and finite bit word length", Bull. Pol. Ac.: Tech. 59 (2), 125-135 (2011).
• Su-Hua L., Yao-Wu W., Lei P., and Xin-Yin X., "Application of quantum-inspired evolutionary algorithm in reactive power optimization", Relay 33, 30-35 (2005).
• Talbi H., Batouche M., and Draa A., "A Quantum-Inspired Evolutionary Algorithm for Multiobjective Image Segmentation", International Journal of Mathematical, Physical and Engineering Sciences 1, 109-114 (2007).
• Talbi H., Batouche M., and Draa A., "A quantum-inspired genetic algorithm for multi-source affine image registration", Image Analysis and Recognition, Springer, 147-154 (2004).
• Vlachogiannis J. G. and Lee K. Y., "Quantum-inspired evolutionary algorithm for real and reactive power dispatch", IEEE Trans. Power Systems 23, 1627-1636 (2003).
• Wang L., Wu H., Tang F., and Zheng D. Z., "A hybrid quantum-inspired genetic algorithm for flow shop scheduling", Advances in Intelligent Computing, Springer, 636-644 (2005).
• Zhang G., "Quantum-inspired evolutionary algorithms: a survey and empirical study", Journal of Heuristics, 1-49 (2010).