The impatience mechanism as a diversity maintaining and saddle crossing strategy

Karcz-Duleba, I.

International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) no. 4, pp. 905-918.

Résumé

The impatience mechanism diversifies the population and facilitates escaping from a local optima trap by modifying fitness values of poorly adapted individuals. In this paper, two versions of the impatience mechanism coupled with a phenotypic model of evolution are studied. A population subordinated to a basic version of the impatience mechanism polarizes itself and evolves as a dipole centered around an averaged individual. In the modified version, the impatience mechanism is supplied with extra knowledge about a currently found optimum. In this case, the behavior of a population is quite different than previously—considerable diversification is also observed, but the population is not polarized and evolves as a single cluster. The impatience mechanism allows crossing saddles relatively fast in different configurations of bimodal and multimodal fitness functions. Actions of impatience mechanisms are shown and compared with evolution without the impatience and with a fitness sharing. The efficiency of crossing saddles is experimentally examined for different fitness functions. Results presented in the paper confirm good properties of the impatience mechanism in diversity maintaining and saddle crossing.

Détail

Keywords: phenotypic evolution, impatience operator, extra knowledge, polarization of population, maintaining population diversity, saddle crossing
Mots-clés : ewolucja fenotypowa, wiedza dodatkowa, różnorodność populacji

Bibliographie

[1] Barabasz, B., Gajda-Zagórska, E., Migórski, S., Paszyński, M., Schaefer, R. and Smołka, M. (2014). A hybrid algorithm for solving inverse problems in elasticity, International Journal of Applied Mathematics and Computer Science 24(4): 865–886, DOI: 10.2478/amcs-2014-0064.

[2] Chen, T., He, J., Chen, G. and Yao, X. (2010). Choosing selection pressure for wide-gap problems, Theoretical Computer Science 411(6): 926–934.

[3] Chorazyczewski, A. and Galar, R. (1998). Visualization of evolutionary adaptation in Rn, in V. Porto et al. (Eds.), Evolutionary Programming VII, Springer-Verlag, London, pp. 657–668.

[4] DeJong, K. (1975). An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph.D. thesis, University of Michigan, Ann Arbour, MI.

[5] Dick, G. and Whigham, P.A. (2006). Spatially-structured evolutionary algorithms and sharing: Do they mix?, in Wang et al. (Eds.), SEAL 2006, Lecture Notes in Computer Science, Vol. 4247, Springer-Verlag, Berlin/Heidelberg, pp. 457–464.

[6] Galar, R. (1989). Evolutionary search with soft selection, Biological Cybernetics 60(5): 357–364.

[7] Galar, R. and Chorazyczewski, A. (2001). Evolutionary dynamics in space of states, Congress on Evolutionary Computation, Seoul, Korea, pp. 1366–1373.

[8] Galar, R. and Kopciuch, P. (1999). Impatience and polarization in evolutionary processes, Proceedings of the KAEiOG Conference, Potok Złoty, Poland, pp. 115–122, (in Polish).

[9] Goldberg, D. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms, in G. Rawlins (Ed.), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, pp. 69–93.

[10] Goldberg, D. and Richardson, J. (1987). Genetic algorithms with sharing for multi-modal function optimisation, Proceedings of the 2nd International Conference on Genetic Algorithms and Their Applications, Hillsdale, NJ, USA, pp. 41–49.

[11] Grosan, C. and Abraham, A. (2007). Hybrid evolutionary algorithms: Methodologies, architectures, and reviews, in A. Abraham et al. (Eds.), Hybrid Evolutionary Algorithms, Studies in Computational Intelligence, Vol. 75, Springer, Berlin/Heidelberg, pp. 1–17.

[12] Hansen, N. (2005). Compilation of results on the 2005 CEC benchmark function set, http:www.lri.fr/~hansen/cec2005compareresults.pdf.

[13] Karcz-Dulęba, I. (2004). Asymptotic behavior of discrete dynamical system generated by simple evolutionary process, International Journal of Applied Mathematics and Computer Science 14(1): 79–90.

[14] Karcz-Duleba, I. (2006). Dynamics of two-element populations in the space of population states, IEEE Transactions on Evolutionary Computation 10(2): 199–209.

[15] Karcz-Duleba, I. (2014). Impatience mechanism in saddles’ crossing, Proceedings of the 6th International Conference ECTA, Rome, Italy, Vol. 75 pp. 174–184.

[16] Kowalczuk, Z. and Białaszewski, T. (2006). Niching mechanisms in evolutionary computations, International Journal of Applied Mathematics and Computer Science 16(1): 59–84.

[17] Mengshoel, O. and Goldberg, D. (2008). The crowding approach to niching in genetic algorithms, Evolutionary Computation 16(3): 315–354.

[18] Obuchowicz, A. (1997). The evolutionary search with soft selection and deterioration of the objective function, Proceedings of the 6th International Conference on Intelligent Information Systems, Zakopane, Poland, pp. 288–295.

[19] Obuchowicz, A. and Prętki, P. (2004). Phenotypic evolution with a mutation based on symmetric α-stable distributions, International Journal of Applied Mathematics and Computer Science 14(3): 289–316.

[20] Rogers, A. and Prügel-Bennett, A. (1999). Genetic drift in genetic algorithm selection schemes, IEEE Transactions on Evolutionary Computation 3(4): 298–303.

[21] Sareni, B. and Krähenbühl, L. (1998). Fitness sharing and niching methods revisited, IEEE Transactions on Evolutionary Computation 2(3): 97–106.

[22] Tomassini, M. (2005). Spatially Structured Evolutionary Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ.

[23] Torn, A. and Zilinskas, A. (1989). Global Optimization, Springer-Verlag, New York, NY.