Zastosowanie metody funkcji dolnej do badania zbieżności algorytmów genetycznych

• Autorzy: Socała J. , Kosiński W.

Warianty tytułu

EN

Lower-bound function method in the convergence analysis of genetic algorithms

• Języki publikacji: PL

Abstrakty

PL

W badaniu wielu zjawisk przyrodniczych istotną rolę odgrywają operatory Markowa, nieujemne operatory liniowe oraz ich półgrupy. W szczególności rozważana jest asymptotyczna stabilność. A. Lasota i J. A. Yorke w 1982 r. udowodnili, że warunkiem wystarczającym i koniecznym asymptotycznej stabilności dla operatora Markowa jest istnienie nietrywialnej funkcji dolnej. W niniejszej pracy pokazujemy zastosowanie metody funkcji dolnej do badania zachowania algorytmów genetycznych. Rozpatrywane w pracy algorytmy genetyczne, używane do rozwiązywania niegładkich problemów optymalizacyjnych, są wynikiem złożenia dwóch operatorów losowych: selekcji i mutacji. Złożenie tych operacji jest macierzą Markowa.

EN

Markovian operators, non-negative linear operators and its subgroups play a significant role for the description of phenomena observed in the nature. Research on asymptotic stability is one of the main issues in this respect. A. Lasota and J. A. Yorke proved in 1982 that the necessary and sufficient condition of the asymptotic stability of a Markovian operator is the existence of a non-trivial lower-bound function. In the present paper it is shown how the method of lower-bound function can be applied to the investigation of genetic algorithms. Genetic algorithms considered used for solving of non-smooth optimization problems are compositions of two random operators: selection and mutation. The compositions are Markovian matrices.

Słowa kluczowe

PL

operator Markowa; wykładnicza stacjonarność; funkcja dolna; algorytm genetyczny; mutacja; selekcja

EN

Markov operator; exponential stationarity; lower-bound function; genetic algorithm; mutation; selection

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Matematyka Stosowana : matematyka dla społeczeństwa
• Rocznik: 2007
• Tom: Nr 8
• Strony: 33--45
• Opis fizyczny: biliogr. 24 poz.

Twórcy

autor

Socała J.

autor

Kosiński W.

• Instytut Techniki i Matematyki Państwowa Wyższa Szkoła Zawodowa w Raciborzu ul. Słowackiego 55, 47-400 Racibórz,

Bibliografia

• [1] H. Amann, Fixed point theorems and nonlinear eigenvalue problems, SIAM Rev. 18 (1976), 620-709.
• [2] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
• [3] R. B. Hollstien, Artificial Genetic Adaptation in Computer Control Systems, Ph.D. Thesis, University of Michigan, 1971.
• [4] D. E. Goldberg, Algorytmy genetyczne i ich zastosowania, WNT,Warszawa, 1995.
• [5] J. Cytowski, Algorytmy genetyczne: podstawy i zastosowania, Seria: Problemy Wspłczesnej Nauki - Teoria i Zastosowania Nr 18, Akademicka Oficyna Wydawnicza PLJ, Warszawa, 1996.
• [6] P. Kieś i Z. Michalewicz, Podstawy algorytmów genetycznych, Matematyka Stosowana. Matematyka dla Społeczeństwa, 1 (44), 2000, 68-91.
• [7] W. Kosiński, S.Kotowski, J. Socała, On Asymptotic Behaviour of a Binary Genetic Algorithm. Annales UMCS, Informatica AI, 4, 2006, 180-188, Proceedings of the Scientific Session organized during XXIst Fall Meeting of the Polish Information Processing Society.
• [8] A. Lasota, Asymptotyczne własności półrup operatorów Markowa, Matematyka Stosowana. Matematyka dla Społeczeństwa, 3 (45), 2002, 39-51.
• [9] A. Lasota, J. A. Yorke, Exact dynamical systems and the Frobenius-Perron operator, Trans. Amer. Math. Soc. 273 (1982), 375-384.
• [10] A. Lasota, J. A. Yorke, Lower bound technique for Markov operators and iterated function systems, Random Comput. Dynam. 2 (1994), 41-77.
• [11] A. Lasota, J. A. Yorke, When the long-time behaviour is independent of the initial density, SIAM J. Math. Anal. 27 (1996), 221-240.
• [12] A. Lasota, R. Rudnicki, Asymptotic behaviour of semigroups of positive operators on C(X), Bull.Pol. Ac. Sci.: Math. 36 (1988), 151-159.
• [13] Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa, 1996.
• [14] R. D. Nussbaum, Eigenvectors of nonlinear positive operators and the linear Krein- Rutman theorem, Fixed Point Theory, Proc. Conf. Sherbrooke, Lecture Notes Math., Springer 886 (1980), 309-330.
• [15] J. E. Rowe, The dynamical system models of the simple genetic algorithm, w Theoretical Aspects of Evolutionary Computing, Leila Kallel, Bart Naudts, Alex Rogers (Eds.), Springer, 2001, pp. 31-57.
• [16] R. Rudnicki, Asymptotic properties of the iterates of positive operators on C(X), Bull.Pol. Ac.Sci.: Math. 34 (1986), 181-187.
• [17] J. Socała, Asymptotic behaviour of the iterates of nonnegative operators on a Banach lattice, Ann. Polon. Math 68 (1) (1998), 1-16.
• [18] J. Socała, Asymptotic behaviour of the iterates of nonnegative operators on a Banach spaces with a cone, Bull. Pol. Ac. Sci.: Math. 50 (2) (2002), 179-187.
• [19] J. Socała, Asymptotic behaviour of semigroups of nonnegative operators on a Banach lattice, Ann. Polon. Math 82 (2) (2003), 95-103.
• [20] J. Socała, W. Kosiński, S. Kotowski, O asymptotycznym zachowaniu prostego algorytmu genetycznego, Matematyka Stosowana. Matematyka dla Społeczeństwa, PTM, Warszawa, 6 (47), 2005, 70-86.
• [21] R. Schaefer, Podstawy genetycznej optymalizacji globalnej, Wydawnictwo Uniwersytetu Jagiellońskiego, Krak 2002.
• [22] M. D. Vose, The Simple Genetic Algorithm: Foundation and Theory, MIT Press, Cambridge, MA, 1999.
• [23] P. P. Zabreiko, M. A. Krasnosel'ski, Yu. V. Pokornyi, Ac ertain class of positive linear operators, Funktsional. Anal. i Prilozhen. 5 (4) (1971), 9-17 (in Russian).
• [24] A. Zalewska-Mitura, Agener alization of the lower bound function theorem for Markow operators, Univ. Iagell. Acta Math. 31 (1994), 79-85.