O asymptotycznym zachowaniu prostego algorytmu genetycznego

• Autorzy: Socała J. , Kosiński W. , Kotowski S.
• Języki publikacji: PL

Abstrakty

PL

W pracy zdefiniowano prosty algorytm genetyczny w terminach skończonego multizbioru potencjalnych rozwiązań (osobników danej populacji), na którym są określone operacje krzyżowania, mutacji i selekcji, każda z pewnym prawdopodobieństwem. Działając złożeniem tych operacji na dowolną populację, tworzymy nową populację. Istnienie funkcji przystosowania (dopasowania), określonej na osobnikach populacji, pozwala powiązać prawdopodobieństwo selekcji osobników do nowej populacji z wartościami, jakie funkcja przystosowania przyjmuje na osobniku. Przejście z jednej generacji do drugiej jest realizowane przez operator działający na wektory probabilistyczne charakteryzujące rozkład prawdopodobieństwa pojawienia się każdej z możliwych populacji. Jest to operator Markowa. W teorii operatorów Markowa oraz operatorów dodatnich znanych jest wiele twierdzeń dotyczących istnienia punktów stałych oraz zbieżności ciągu iteracji operatora. Korzystając z tych wyników, znaleźliśmy warunki wystarczające i konieczne stabilności operatora Markowa związanego z pewną klasą algorytmów genetycznych.

EN

The simple genetic algorithm (SGA) and its convergence analysis are main subjects of the article. The SGA is defined on a finite multi-set of potential problem solutions (individuals) together with crossover, mutation and selection operators, each with prescribed probability. The selection operation acts on the basis of the fitness function defined on potential solutions (individuals), and is fundamental for the problem considered. Generation of a new population from the given one is realized by the action of the composition of those operators. The composition is written in the form of a transition operator acting on probability vectors which describe probability distributions of each population. The transition operator is a Markov one. Thanks to the well-developed theory of Markov operators new conditions for stability of the transition operator are formulated. The results obtained are related to the class of genetic operators.

Słowa kluczowe

PL

populacja; krzyżowanie; mutacja; selekcja; operator Markowa; stabilność; zbieżność; rozkład graniczny; algorytm genetyczny; prosty algorytm genetyczny

EN

population; crossover; mutation; selection; Markov operator; stability; convergence; limit distribution; simple genetic algorithm

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Matematyka Stosowana : matematyka dla społeczeństwa
• Rocznik: 2005
• Tom: Nr 6
• Strony: 70--86
• Opis fizyczny: bibliogr. 16 poz.

Twórcy

autor

Socała J.

• Instytut Matematyki, Uniwersytet Śląski, ul. Bankowa 14, 40-007 Katowice

autor

Kosiński W.

• Centrum Badawcze, Polsko-Japońska Wyższa Szkoła Technik Komputerowych, ul. Koszykowa 86, 02-008 Warszawa
• Instytut Mechaniki Środowiska i Informatyki Stosowanej, Uniwersytet Kazimierza Wielkiego, ul. Chodkiewicza 30, 85-064 Bydgoszcz

autor

Kotowski S.

• Zakład Sterowania i Dynamiki Układów, Instytut Podstawowych Problemów Techniki PAN, ul. Świętokrzyska 21, 00-049 Warszawa

Bibliografia

• [1] A. Lasota, Asymptotyczne własności półgrup operatorow Markowa, Mat. Stos. 3 (2002), 39-51.
• [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] P. Kieś, Z. Michalewicz, Podstawy algorytmów genetycznych, Mat. Stos. 1 (2000), 68-91.
• [5] Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa, 1996.
• [6] D. E. Goldberg, Algorytmy genetyczne i ich zastosowania, WNT, Warszawa, 1995.
• [7] J. Cytowski, Algorytmy genetyczne: podstawy i zastosowania, Seria: ProblemyWspółczesnej Nauki-Teoria i Zastosowania Nr 18, Akademicka Oficyna Wydawnicza PLJ, Warszawa, 1996.
• [8] M. D. Vose, The Simple Genetic Algorithm: Foundation and Theory, MIT Press, Cambridge, MA, 1999.
• [9] A. Lasota, J. A. Yorke, Exact dynamical systems and the Frobenius-Perron operator, Trans. Amer. Math. Soc. 273 (1982), 375-384.
• [10] J. E. Rowe, The dynamical system models of the simple genetic algorithm, w: Theoretical Aspects of Evolutionary Computing, L. Kallel i in. (red.), Springer, 2001, 31-57.
• [11] R. Schaefer, Podstawy genetycznej optymalizacji globalnej, Wydawnictwo Uniwersytetu Jagiellońskiego, Kraków 2002.
• [12] R. Rudnicki, On asymptotic stability and sweeping for Markov operators, Bull. Polish Acad. Sci. Math. 43 (1995), 245-262.
• [13] J. Socała, Asymptotic behaviour of the iterates of nonnegative operators on a Banach lattice, Ann. Polon. Math. 68 (1998), 1-16.
• [14] S. Kotowski, J. Socała, W. Kosiński, Z. Michalewicz, Markovian model of Simple genetic algorithms and its asymptotic behaviour, przesłana do publikacji do Fund. Inform., 2005.
• [15] J. Socała, Markovian approach to genetic algorithms, przesłana do publikacji, 2005.
• [16] S. Kotowski, Klasyfikacja algorytmów genetycznych, w przygotowaniu, 2005.