Building blocks propagation in quantum-inspired genetic algorithm

• Autorzy: Nowotniak R. , Kucharski J.

Warianty tytułu

PL

Propagacja bloków budujących w kwantowo inspirowanym algorytmie genetycznym

• Języki publikacji: EN

Abstrakty

EN

This paper presents an analysis of building blocks propagation in Quantum-Inspired Genetic Algorithm, which belongs to a new class of metaheuristics drawing their inspiration from both biological evolution and unitary evolution of quantum systems. The expected number of quantum chromosomes matching a schema has been analyzed and a random variable corresponding to this issue has been introduced. The results have been compared with Simple Genetic Algorithm. Also, it has been presented how selected binary quantum chromosomes cover a domain of one-dimensional fitness function.

PL

W artykule została przedstawiona analiza propagacji bloków budujących w kwantowo inspirowanych algorytmie genetycznym, należącym do nowej klasy metaheurystyk przeszukiwania, czerpiących inspirację zarówno z ewolucji biologicznej, jak i z ewolucji unitarnej układów kwantowych. Została wprowadzona zmienna losowa odpowiadająca liczbie chromosomów kwantowych, pasujących do wybranego schematu oraz zostały obliczone podstawowe miary tej zmiennej. Wyniki uzyskane dla testowego problemy zostały porównane z klasycznym algorytmem genetycznym. W artykule zostało również zaprezentowane, w jaki sposób wybrane binarne chromosomy kwantowe "pokrywają" dziedzinę wybranej jedno­wymiarowej funkcji celu.

Słowa kluczowe

EN

genetic algorithms; optimization; quantum-inspired evolutionary algorithms; building blocks propagation

PL

algorytmy genetyczne; optymalizacja; kwantowo inspirowane algorytmy ewolucyjne; propagacja bloków budujących

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2010
• Tom: T. 14, z. 3/2
• Strony: 795--810
• Opis fizyczny: Bibliogr. 21 poz., rys., wykr., tab.

Twórcy

autor

Nowotniak R.

• Computer Engineering Department, Technical University of Lodz, Poland

autor

Kucharski J.

• Computer Engineering Department, Technical University of Lodz, Poland

Bibliografia

• [1] Al-Othman A.K., Al-Fares F.S., EL-Nagger K.M., Power System Security Constrained Economic Dispatch Using Real Coded Quantum Inspired Evolution Algorithm. International Journal of Electrical, Computer, and Systems Engineering, vol. 1, 2007, 4—10.
• [2] Bin L., Junan Y., Zhenąuan Z., GAQPR and its application in discovering freąuent structures in time series. Proc. of the 2003 IEEE Int. Conf. on Neural Networks & Signal Processing, vol. 1, 399-403.
• [3] Defoin-Platel M., Schliebs S., Kasabov N., A versatile quantum-inspired evolutionary algorithm. Proc. of the Int. Conf. on Evolutionary Computation. CEC, vol. 7, Singapore, September 25-28, 2007.
• [4] Goldberg D.E., Genetic Algorithms in Search and Optimization. Addison-Wesley, 1989.
• [5] Grover L.K., A fast ąuantum mechanical algorithm for database search. Proc. of 28th Annual ACM Symposium on the Theory of Computing, 1996, 212-220.
• [6] Gu J., Gu X., Gu M., A novel parallel ąuantum genetic algorithm for stochastic job shop scheduling. Journal of Mathematical Analysis and Applications, vol. 355, 2009, 63-81.
• [7] Gu J., Gu X. and Jiao B., A ąuantum genetic based scheduling algorithm for stochastic flow shop scheduling problem with random breakdown. Proc. of the 17th IFAC World Congress, 2008, 63-68.
• [8] Han K.H., Kim J.H., Genetic quantum algorithm and its application to combinatorial optimization problem. Proceedings of the 2000 Congress on Evolutionary Computation, vol. 2, 2000, 1354-1360.
• [9] Holland J.H., Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
• [10] Jeong Y., Park J., Shin J., Lee, K., A thermal unit commitment approach using an improved quantum evolutionary algorithm. Electric Power Components and Systems, vol. 37, 2009, 770-786.
• [11] Jopek Ł., Nowotniak R., Postolski M., Babout L., Janaszewski M., Zastosowanie kwantowych algorytmów genetycznych do selekcji cech. Scient. Bulletin of Academy of Science and Technology, Automatics, in print 2010 (in Polish).
• [12] Kusztelak G., Rudnicki M., Wiak S., Propagation of Building Blocks in SGA and MPGA. Lecture Notes in Computer Science, 2004, 438-443.
• [13] Mahdabi P., Abadi M., Jalili S., A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems. Proc. of the 1 lth Annual Conference on Genetic and Evolu-tionary Computation, ACM, 2009, 1807-1808.
• [14] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, New York, 1999.
• [15] Narayanan A., Moore M., Quantum-inspired genetic algorithms. In Evolutionary Computation, 1996., Proc. of IEEE Int. Conf., 1996, 61-66.
• [16] Nielsen M.A., Chuang I., Quantum computation and quantum information. Cambridge University Press, 2000.
• [17] Shor P.W., Algorithms for ąuantum computation: Discrete logarithms and factoring. 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, 124-134.
• [18] Talbi H., Batouche M., Draa A., A Quantum-Inspired Evolutionary Algorithm for Multiobjectin Image Segmentation. International Journal of Mathematical, Physical and Engineering Sciences, vol. 1, 2007, 109-114.
• [19] Wang L., Wu H., Tang F., Zheng D.Z., A hybridąuantum-inspired genetic algorithm forflowshop scheduling. Lecture Notes in Computer Science, vol. 3645, 2005, 636.
• [20] Xing H., Ji Y, Bai L., Liu X., Qu Z., Wang X., An adaptive~evolution-based ąuantum-inspired evolutionary algorithm for QoS multicasting in IP/DWDM networks: Computer Communications, vol. 32,2009, 1086-1094.
• [21] Xing H., Liu X., Jin X., Bai L., Ji Y, A multi-granulańty evolution based Quantum Genetic Algorithm for QoS multicast routing problem in WDM networks. Computer Communications, vol. 32, 2009, 386-393.