On Some Properties of Quantum Particles in Multi-Swarms for Dynamic Optimization

• Autorzy: Trojanowski, K.

Warianty tytułu

PL

O własnościach cząsteczek kwantowych stosowanych w wielorojach do optymalizacji dynamicznej

• Języki publikacji: EN

Abstrakty

EN

This paper studies properties of a multi-swarm system based on a concept of physical quantum particles (mQSO). Quantum particles differ from the classic ones in the way they move. As opposed to the classic view on a particle movement, where motion is controlled by linear kinematic laws, quantum particles change their location according to random distributions. The procedure of generating a new location for the quantum particle is similar to mutation operator widely used in evolutionary computation with real-valued representation. In this paper we study a set of new distributions of candidates for the quantum particle location, and we show different features of these distributions. The distributions considered in this paper are divided into two classes: those with a limited range of the new location coordinates and those without such limitations. They are tested on different types of dynamic optimization problems. Experimental verification has been based on a number of testing environments and two main versions of the algorithm: with and without mechanisms protecting against stagnation caused by convergence of sub-swarms during the search process. The experimental results show the advantages of the distribution class, in which the candidates are spread out in the entire search space, and indicate the positive and negative aspects of application of anti-convergence mechanisms.

PL

W niniejszym raporcie studiowane są właściwości systemów wielorojowych opartych na idei cząsteczek kwantowych (mQSO). W przeciwieństwie do klasycznego podejścia do ruchu cząsteczki, w którym przemieszczanie kontrolowane jest przez liniowe prawa kinematyki, kwantowe cząsteczki zmieniają swoje położenie wykorzystując rozkłady losowe. Tutaj badamy pewien zbiór nowych rozkładów kandydatów na nowe położenie cząsteczki kwantowej i demonstrujemy ich różne właściwości. Rozkłady rozpatrywane poniżej można podzielić na dwie klasy: z ograniczonym obszarem możliwych nowych położeń cząsteczki, oraz pozostałe z nieograniczonym obszarem tych położeń. Wszystkie zostały testowane na różnych typach zadań dynamicznych. Eksperymentalna weryfikacja została oparta na pewnej liczbie zadań testowych, a także na dwóch głównych wersjach algorytmu: uzwględniającego i nieuwzględniającego mechanizmy chroniące przeciwko stagnacji powodowanej przez zbieganie zbioru rozwiązań algorytmu do niewielkich obszarów dziedziny w trakcie poszukiwań. Wyniki eksperymentów wskazują przewagę tej klasy rozkładów, w której kandydaci na nowe położenie cząsteczki mogą należeć do całego zbioru poszukiwań. Wyniki pokazują też pozytywne i negatywne aspekty stosowania mechanizmów anty-zbieżnosci.

Słowa kluczowe

PL

optymalizacja rojem cząsteczek; wielorój; optymalizacja dynamiczna; cząsteczki kwantowe

EN

optimization in dynamic environments; particle swarm optimization (PSO); tracking optima in dynamic environments; multi-swarm; quantum particles

• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2009
• Tom: Nr 1016
• Strony: 1-60
• Opis fizyczny: Bibliogr. 51 poz., rys.

Twórcy

autor

Trojanowski, K.

• Instytut Podstaw Informatyki PAN 01-237 Warszawa, Ordona 21 Polska

Bibliografia

• [1] T. Blackwell. Particle swarm optimization in dynamic environmentments. In S. Yang, Y.-S. Ong, and Y. Jin, editors. Evolutionary Computation in Dynamic and Uncertain Environments, volume 51 of Studies in Computational Intelligence, pages 29-49. Springer, 2007.
• [2] T. Blackwell and P. J. Bentley. Don't push me! collision-avoiding swarms. In D. B. Fogel et al., editors, Proc. of the IEEE Congress on Evolutionary Computation, pages 1691-1696. IEEE Press, 2002.
• [3] T. Blackwell and P. J. Bentley. Dynamic search with charged swarms. In W. B. Langdon et al., editors, GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, New York, USA, 9-13 July 2002, pages 19-26. Morgan Kaufmann, 2002.
• [4] T. Blackwel and J. Branke. Multiswarms, exclusion, and anti-convergence in dynamic environments. 10(4):459 - 472, 2006.
• [5] T. Blackwell and J. Branke. Multi-swarm optimization in dynamic environments. In G. R. Raidl et al., editors, Applications of Evolutionary Computing, Evo Workshops 2004, volume 3005 of Lecture Notes in Computer Science, pages 489-500. Springer, 2004.
• [6] L O. Bohachevsky, M. E. Johnson, and M. L. Stein. Generalized simulated annealing for function optimization. Technometrics, 28 (3):209-217, Aug. 1986.
• [7] J. Branke.The moving peaks benchmark. URL http: //www. aif b. uni-karlsruhe.de/$\sim$jbr/MovPeaks/movpeaks/.
• [8] J. Branke.Memory enhanced evolutionary algorithm for changing optimization problems. In P. J. Angeline et al., editors, Proc. Congress on Evolutionary Computation, volume 3, pages 1875-1882. IEEE Press, Piscataway, NJ, 1999.
• [9] J. Branke. Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers, 2002.
• [10] D. G. Brooks and W. A. Verdini. Computational experience with generalized simulated annealing over continuous variables. Am. J. Math. Manage. Sci., 8(3-4):425-449, 1988.
• [11] J. M. Chambers, C. L. Mallows, and B. W. Stuck, A method for simulating stable random variables.   J. Amer.. Statist. Assoc., 71 (354):340-344, 1 976.
• [12] M. Clerc and J. Kennedy. The particle swaTm-explosion, stability and convergence in a multi-dimensional complex space. 2002.
• [13] L. N. de Castro and J. Timmis. An artificial immune network for multimodal function optimization. In D. B. Fogel et al., editors, Proc. of the IEEE Congress on Evolutionary Computation, pages 699-674. IEEE Press, 2002.
• [14] A. E. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in Evolutionary Algorithms. 3(2):124-141, 1999.
• [15] M. Gutowski. Levy flights as an underlying mechanizm for a global optimization algorithm.    In Proc.  5th National Conf.  on Evolutionary Computation and Global Optimisation, pages 79-86. Warsaw Univ. of Technology Publishing House, 2001. URL arXiv: math-ph/0106003vlhttp://arxiv.org/abs/math-ph/0106003.
• [16] L. Ingberg. Very fast simulated reannealing. J. Math. Comput. Model., 12(8):967-973, 1989.
• [17] S. Janson and M. Middendorf. A hierahical particle swarm optimizer for noisy and dynamic environment. Genetic Programming and Evolvable Machines, 7(4):329-354, 2006.
• [18] Y. Jin and J. Branke. Evolutionary algorithms in uncertain environments - a survey. 9(3):303-317, 2005.
• [19] T. Jones. Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, University of New Mexico, 1995.
• [20] J. Kenendy and R. C. Eberhart. Particle swarm optimization. In Proc. IEEE Int. Conf. on Neural Networks (ICNN'95), volume 4, pages 1942-1948. IEEE Service Center, Piscataway N J, 1995.
• [21] J. Kennedy. Bare bones particle swarms. In IEEE Swarm Intelligence Symposium (SIS 2003), pages 80-87. IEEE Press, 2003.
• [22] C.-Y. Lee and X. Yao. Evolutionary programming using mutations based on the levy probability distribution. 8(1):1-13, 2004.
• [23] X. Li. Adaptively choosing neighborhood bests in a particle swarm optimizer for multimodal function optimization. In K. Deb et al., editors, GECCO 2004- Proc. Conference on Genetic and Evolutionary Computation, volume 3102 of Lecture Notes in Computer Science, pages 105-116. Springer, 2004.
• [24] X. Li, J. Branke, and T. Blackwell. Particle swarm with speciation and adaptation in a dynamic environment. In M. Keijzer et al., editors, GECCO 2006: Proc. Conference on Genetic and Evolutionary Computation, pages 51-58. ACM Press, 2006.
• [25] H. Lu and W. Chen. Dynamic-objective particle swarm optimization for constrained optimization problems. J. Comb. optim., 12 (4):409-419, 2006.
• [26] G. Marsaglia. Choosing a point from the surface of a sphere. Ann. Math. Statist, 43(2):645-646, 1972.
• [27] R. W. Morrison. Designing Evolutionary Algorithms for Dynamic Environments. Springer, 2004.
• [28] W. R. Morrison. Performance measurement in dynamic environments. In GECCO 2003: Proceedings of the Bird of a Feather Work-shopSj Genetic and Evolutionary Computation Conference, pages 99-102. AAAI, 2003.
• [29] A. E. Muňoz Zavala, A. H. Aguirre, and E. R. Villa Diharce. Constrained optimization via particle evolutionary swarm optimization algorithm (PESO). In H.-G. Beyer et al., editors, GECCO 2005: Proc. Conference on Genetic and Evolutionary Computation, volume l, pages 209-216. ACM Press, 2005.
• [30] D. Nam, J.-S. Lee, and C. H. Park. n-dimensional cauchy neighbor generation for the fast simulated annealing. IEICE Trans. Inf. & Syst., E87-D(11):2499-2502, Nov. 2004.
• [31] A. Obuchowicz. Multidimensional mutations in evolutionary algorithms based on real-valued representation. Int. J. Syst. Sci., 34 (7):469 - 483, June 2003.
• [32] A. Obuchowicz. Evolutionary algorithms with mutations based on a-stable and directional distributions. In J. Arabas, editor, Proc. lOth National Conf. on Evolutionary Computation and Global Optimisation, number 160 in Prace Naukowe, Elektronika, pages 209-219. Warsaw Univ. of Technology Publishing House, 2007.
• [33] A. Obuchowicz and P. Pretki. Phenotypic evolution with a mutation based on symmetric alfa-stable distributions. Int. J. Appl. Math. Comput. Sci., 14(3):289-316, 2004.
• [34] A. Obuchowicz and P. Pretki. Isotropic symmetric a-stable mutations for evolutionary algorithms. In D. Corne et al., editor s, The 2005 IEEE Congress on Evolutionary Computation, volume l, pages 404-410. IEEE Press, 2005.
• [35] D. Parrot and X. Li. Locating and tracking multiple dynamic optima by a particle swarm model using speciation. 10(4):440 - 458, 2006.
• [36] G. T. Pulido and C. A. C. Coello. A constraint handling mechanism for particle swarm optimization. In Proc. Congress on Evolutionary Computation, volume 2, pages 1396-1403. IEEE, 2004.
• [37] T. J. Richer and T. M. Blackwell. The Levy particle swarm. In G. G. Yen et al., editors, Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pages 808-815. IEEE Press, 2006.
• [38] H. E. Romeijn and R. L. Smith. Simulated annealing for constrained global optimization. J. Global Optim., 5(2): 101-126, 1994.
• [39] I. Schoeman and A. P. Engelbrecht. Niching for dynamie environments using particle swarm optimization. In T.-D. Wang et al., editors, Simulated Evolution and Learning, 6th International Conference, SEAL 2006, Hefei, China, October 15-18, 2006, Proceedings, volume 4247 of Lecture Notes in Computer Science, pages 134-141. Springer, 2006.
• [40] H. Szu and R. Hartley. Fast simulated annealing. Phys. Lett. A, 122:157-162, June 1987.
• [41] K. Trojanowski. Tuning quantum multi-swarm optimization for dynamic tasks. In Rutkowski et al., editors, ICAISC 2008, volume 5097 of Lecture Notes in Artificial Intelligence, pages 499-510. Springer, 2008.
• [42] K. Trojanowski. Non-uniform distributions of quantum particles in multi-swarm optimization for dynamic tasks. In M. Bubak et al., editors, ICCS 2008, Part I, volume 5101 of Lecture Notes in Computer Science, pages 843-852. Springer, 2008.
• [43] K. Trojanowski. Adaptive non-uniform distribution of quantum particles in mqso. In X. Li et al., editors, SEAL 2008, volume 5361 of Lecture Notes in Computer Science, pages 91-100. Springer, 2008.
• [44] K. Trojanowski and A. Obuchowicz. Measures for non-stationary optimization tasks. In 5th ICANNGA: Artificial Neural Nets and Genetic Algorithms, pages 244-247. Springer, 2001.
• [45] J. von Neumann. Various techniques used in connection with random digits. monte carlo methods. Nat. Bureau Standards, 12:36-38, 1951.
• [46] K. Weicker. Performance measures for dynamic environments. In G. Goos et al., editors, Parallel Problem Solving from Nature -PPSN VII, volume 2439 of Lecture Notes in Computer Science, pages 64-76. Springer, 2002.
• [47] K. Weicker. Evolutionary algorithms and dynamic optimization problems. Springer, 2003.
• [48] X. Yao and Y. Liu. Fast evolutionary programming. In L. J. Fogel et al., editors, Evolutionary Programming V, pages 419-429. Cambridge, MA: MIT Press, 1996.
• [49] X. Yao and Y. Liu. Fast evolution strategies. Contr. Cybern., 26 (3):467-496, 1997.
• [50] X. Yao, Y. Liu, and G. Lin. Evolutionary programming made faster. 3(2):82-102, 1999.
• [51] B. Yuan, M. Orłowska, and S. Sadiq. Extending a class of continuous estimation of distribution algorithms to dynamic problems. Optimization Letters, 2(3):433-44, 2008.