On Stability and Classification Tools for Genetic Algorithms

• Autorzy: Kotowski S. , Kosiński W. , Michalewicz Z. , Synak P. , Brocki Ł.
• Języki publikacji: EN

Abstrakty

EN

Convergence of genetic algorithms in the form of asymptotic stability requirements is discussed. Some tools to measure convergence properties of genetic algorithms are introduced. A classification procedure is proposed that is based on the following conjecture: the entropy and the fractal dimension of trajectories of genetic algorithms produced by them are quantities that can characterize the algorithms. The role of these quantities as invariants of the algorithm classes is discussed together with the compression ratio of points of genetic algorithms.

Słowa kluczowe

EN

genetic algorithm; classification; convergence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 96, nr 4
• Strony: 477--491
• Opis fizyczny: Bibliogr. 21 poz., tab.

Twórcy

autor

Kotowski S.

autor

Kosiński W.

autor

Michalewicz Z.

autor

Synak P.

autor

Brocki Ł.

• Faculty of Computer Science, Polish-Japanese Institute of Information Technology, ul.Koszykowa 86, 02-008 Warsaw, Poland,

Bibliografia

• [1] Barnsley, M.F.: Lecture notes on iterated function systems, in Chaos and Fractals. The Mathematics Behind the ComputerGraphics, Proc.Symp. Appl.Math. 39, R. L. Devaney and L. Keen (eds.) American Mathematical Society, Providence, Rhode Island, pp. 127-144, 1989.
• [2] Choe, G.H.: Computational Ergodic Theory, Springer, New York 2005.
• [3] English, T.: No More Lunch: Analysis of Sequential Search, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 227-234. 2004, http://BoundedTheoretics.com/CEC04.pdf
• [4] Friedman, N.A. and Ornstein, D.S.: On isomorphisms of weak Bernoulli transformations, Adv. in Math. 5, 365-394, 1970.
• [5] Frizelle, G. and Suhov, Y.M.: An entropic measurement of queueing behaviour in a class of manufacturing operations. Proc. Royal Soc. London A (2001) 457, 1579-1601.
• [6] Harrison, J.: An introduction to fractals, in Chaos and Fractals. The Mathematics Behind the Computer Graphics, Proc.Symp. Appl. Math. 39, R. L. Devaney and L. Keen (eds.) American Mathematical Society, Providence, Rhode Island, pp. 107-126, 1989.
• [7] Igel, C. and Toussaint, M.: A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions, Journal of Mathematical Modelling and Algorithms, 3, 313-322, 2004.
• [8] Kieś, P.: Dimension of attractors generated by a genetic algorithm, in Proc. of Workshop Intelligent Information Systems IX, Bystra, Poland, June 12-16, IPI PAN, Warszawa, pp. 40-45, 2000.
• [9] Kosiński W., Socała J., and Kotowski S.: Asymptotic stability and point convergence of genetic algorithms, prepared for publication.
• [10] Kotowski S., Kosiński W., Michalewicz Z., Nowicki J., and Przepiórkiewicz B.: Fractal dimension of trajectory as invariant of genetic algorithms ICAICS, 9-th International Conference on Artifical Intelligence and Soft Computing, 2008, LNAI 5097, Springer, Berlin, Heidelberg, New York, pp. 414-425.
• [11] Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd, rev. edition, Springer, Berlin, Heidelberg, 1996.
• [12] Ornstein, D.S.: Ergodic theory, Randomness and Dynamical Systems, Yale Univ. Press, 1974.
• [13] Ossowski, A.: Statistical and topological dynamics of evolutionary algorithms, in Proc. of Workshop Intelligent Information Systems IX, Bystra, Poland, June 12-16, IPI PAN, Warszawa, pp. 94-103, 2000.
• [14] Rowe, J.E.: The dynamical system models of the simple genetic algorithm, in Theoretical Aspects of Evolutionary Computing, Leila Kallel, Bart Naudts, Alex Rogers (Eds.), Springer, 2001, pp.31-57.
• [15] Schaefer, R.: Foundations of Global Genetic Optimization, Springer Series: Studies in Computational Intelligence 74, XII, 222 p. Springer, New York, 2007.
• [16] Socała, J. and Kosiński, W.: On convergence of a simple genetic algorithm, in ICAICS, 9-th International Conference on Artifical Intelligence and Soft Computing, 2008, LNAI, vol. 5097, Springer, Berlin, Heidelberg, 2008, pp. 489-498.
• [17] Socała, J. and Kosiński, W.: Lower-bound function method in the converegence analysis of genetic algorithms, (in Polish: Zastosowanie metody funkcji dolnej do badania zbieżnóci algorytmów genetycznych,) Matematyka Stosowana. Matematyka dla Społeczeństwa, PTM, Warszawa, 8 (49), 2007 , 33-44.
• [18] Socała, J., Kosiński,W., and Kotowski, S.: On Asymptotic Behaviour of Simple Genetic Algorithms, in Polish: O asymptotycznym zachowaniu prostego algorytmu genetycznego, Matematyka Stosowana. Matematyka dla Społeczeństwa, PTM, Warszawa, 6 (47), 2005, 70-86.
• [19] Szlenk W.: An Introduction to the Theory of Smooth Dynamical Systems, PWN, Warszawa, John Wiley&Sons, Chichester, 1984.
• [20] Vose, M.D.: Modelling Simple Genetic Algorithms, Evolutionary Computation, 3 (4), 453-472, 1996.
• [21] Wolpert D.H. and MacreadyW.G.: No Free Lunch Theorems for Optimization, IEEE Transaction on Evolutionary Computation, 1 (1), 67-82, 1997, http://ic.arc.nasa.gov/people/dhw/papers/78.pdf