Phenotypic evolution with a mutation based on symmetric alpha-stable distributions

Obuchowicz, A. ; Prętki, P.

International Journal of Applied Mathematics and Computer Science, Tome 14 (2004) no. 3, pp. 289-316.

Résumé

Multidimensional Symmetric alpha-Stable (S alpha S) mutations are applied to phenotypic evolutionary algorithms. Such mutations are characterized by non-spherical symmetry for alpha2 and the fact that the most probable distance of mutated points is not in a close neighborhood of the origin, but at a certain distance from it. It is the so-called surrounding effect (Obuchowicz, 2001b; 2003b). For alpha=2, the S alpha S mutation reduces to the Gaussian one, and in the case of alpha=1, the Cauchy mutation is obtained. The exploration and exploitation abilities of evolutionary algorithms, using S alpha S mutations for different alpha, are analyzed by a set of simulation experiments. The obtained results prove the important influence of the surrounding effect of symmetric alpha-stable mutations on both the abilities considered.

Détail

Keywords: evolutionary algorithms, Levy-stable distributions, global optimization, surrounding effect
Mots-clés : algorytm ewolucyjny, dystrybucja stabilna, optymalizacja globalna

Bibliographie

[1] Bäck T. and Schwefel H.-P. (1993): An overview of evolutionary computation.—Evol. Comput., Vol. 1, No. 1, pp. 1–23.

[2] Bäck T., Fogel D.B. and Michalewicz Z. (Eds.) (1997): Handbook of Evolutionary Computation. — Oxford: Oxford University Press, NY.

[3] Chambers J.M., Mallows C.L. and Stuck B.W. (1976): A method for simulating stable random variables.—J. Amer. Statist. Assoc., Vol. 71, No. 354, pp. 340–344.

[4] Fang K.-T., Kotz S. and Ng S. (1990): Symmetric Multivariate and Related Distributions.—London: Chapman and Hall.

[5] Fogel L.J., Owens A.J. and Walsh A.J. (1966): Artificial Intelligence through Simulated Evolution.—New York: Wiley.

[6] Fogel D.B., Fogel L.J. and Atmar J.W. (1991): Meta-evolutionary programming. — Proc. 25th Asilomar Conf. Signals, Systems Computers, San Jose, pp. 540–545.

[7] Fogel D.B. (1992): An analysis of evolutionary programming. —Proc. 1st Annual Conf. Evolutionary Programming, LA Jolla, CA: Evolutionary Programming Society, pp. 43–51.

[8] Fogel D.B. (1994): An introduction to simulated evolutionary computation. — IEEE Trans. Neural Netw., Vol. 5, No. 1, pp. 3–14.

[9] Galar R. (1985): Handicapped individua in evolutionary processes. — Biol. Cybern., Vol. 51, pp. 1–9.

[10] Galar R. (1989): Evolutionary search with soft selection. — Biol. Cybern., Vol. 60, pp. 357–364.

[11] Gutowski M. (2001): Lévy flights as an underlying mechanism for a global optimization algorithm. — Proc. 5th Conf. Evolutionary Algorithms and Global Optimization, Jastrzębia Góra, Poland, pp. 79–86.

[12] Kanter M. (1975): Stable densities with change of scale and total variation inqualities. — Ann. Probab., Vol. 3, No. 4, pp. 687–707.

[13] Kappler C. (1996): Are evolutionary algorithms improved by large mutation, In: Problem Solving from Nature (PPSN) IV (H.-M. Voigt, W. Ebeling, I. Rechenberg and H.-P. Schwefel, Eds.).—Berlin: Springer, pp. 388–397.

[14] Lévy C. (1925): Calcul des Probabilités.—Paris: Gauthier Villars.

[15] Michalewicz Z. (1996): Genetic Algorithms + Data Structures = Evolution Programs.—Berlin: Springer.

[16] Nolan J.P. (2003): Stable Distributions. Models for Heavy Tailed Data.—Berlin: Springer.

[17] Obuchowicz A. (2001a): On the true nature of the multidimensional Gaussian mutation. — In: Artificial Neural Networks and Genetic Algorithms (V. Kurkova, N.C. Steel, R. Neruda and M. Karny, Eds.). — Vienna: Springer, pp.248–251.

[18] Obuchowicz A. (2001b): Mutli-dimensional Gaussian and Cauchy mutations, In: Intelligent Information Systems (M. Kłopotek, M. Michalewicz, and S.T. Wierzcho´n, Eds.). — Heidelberg: Physica–Verlag, pp. 133–142.

[19] Obuchowicz A. (2003a): Population in an ecological niche: Simulation of natural exploration. — Bull. Polish Acad. Sci., Tech. Sci., Vol. 51, No. 1, pp. 59–104.

[20] Obuchowicz A. (2003b): Multidimensional mutations in evolutionary algorithms based on real-valued representation.— Int. J. Syst. Sci., Vol. 34, No. 7, pp. 469–483.

[21] Obuchowicz A. (2003c): Evolutionary Algorithms in Global Optimization and Dynamic System Diagnosis. — Zielona Góra: Lubuskie Scientific Society.

[22] Rechenberg I. (1965): Cybernetic solution path of an experimental problem. — Roy. Aircr. Establ., Libr. Transl. 1122, Farnborough, Hants., UK.

[23] Rudolph G. (1997): Local convergence rates of simple evolutionary algorithms with Cauchy mutations.—IEEE Trans. Evolut. Comput., Vol. 1, No. 4, pp. 249–258.

[24] Schwefel H.-P. (1981): Numerical Optimization of Computer Models.—Chichester: Wiley.

[25] Samorodnitsky G. and Taqqu M.S. (1994): Stable Non-Gaussian Random Processes.—New York: Chapman Hall.

[26] Shu A. and Hartley R. (1987): Fast simulated annaeling. — Phys. Lett. A, Vol. 122, Nos. 3/4, pp. 605–614.

[27] Weron R. (1996): Correction to: On the Chambers-Mallows-Stuck method for simulating skewed stable random variables. — Res. Rep., Wrocław University of Technology, Poland.

[28] Weron R. (2001): Lévy-stable distributions revisited: tail index > 2 does not exclude the Lévy-stable regime. — Int. J. Modern Phys. C, Vol. 12, No. 2, pp. 209–223.

[29] Yao X. and Liu Y. (1996): Fast evolutionary programming, In: Evolutionary Programming V: Proc. 5th Annual Conference on Evolutionary Programming (L.J. Fogel, P.J. Angeline, and T. Bäck, Eds.). — Cambridge, MA: MIT Press, pp. 419–429.

[30] Yao X. and Liu Y. (1997): Fast evolutionary strategies.—Contr. Cybern., Vol. 26, No. 3, pp. 467–496.

[31] Yao X. and Liu Y. (1999): Evolutionary programming made faster. — IEEE Trans. Evolut. Comput., Vol. 3, No. 2, pp. 82–102.

[32] Zolotariev A. (1986): One-Dimensional Stable Distributions.— Providence: American Mathematical Society.