Stopping criteria for a general model of genetic algorithm

• Autorzy: Studniarski M.
• Konferencja: Evolutionary Computation and Global Optimization 2009 / National Conference (12 ; 1-3.06.2009 ; Zawoja, Poland)
• Języki publikacji: EN

Abstrakty

EN

We consider a general Markov chain model of genetic algorithm described in [3], Chapters 5 and 6. For this model, we establish an upper bound for the number of iterations which must be executed in order to find an optimal (or approximately optimal) solution with a prescribed probability. For the classical genetic algorithm with bitwise mutation, our result reduces to the main theorem of [1] in the case of one optimal solution, and gives some improvement over it in the case of many optimal solutions.

Słowa kluczowe

EN

evolutionary computation; evolutionary algorithm; EA; genetic algorithm; Markov chains; RHS algorithm; Random Heuristic Search algorithm

PL

obliczenia ewolucyjne; algorytm ewolucyjny; algorytm genetyczny; łańcuchy Markova

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2009
• Tom: z. 169
• Strony: 173--181
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Studniarski M.

• Faculty of Mathematics and Computer Science, University of Łódź, ul. S. Banacha 22, 90-338 Łódź, Poland,

Bibliografia

• [1] D. Greenhalgh, S. Marshall, Convergence criteria for genetic algorithms, SIAM Journal on Computing 30(2000), 269-282.
• [2] G.J. Koehler, S. Bhattacharya, M.D. Vose, General cardinality genetic algorithms, Evolutionary Computation 5(1998), 439-459.
• [3] C.R. Reeves, J.E. Rowe, Genetic Algorithms - Principles and Perspectives: A Guide to GA Theory, Kluwer, Boston, 2003.
• [4] J.E. Rowe, M.D. Vose, A.H. Wright, Structural search, spaces and genetic operators, Evolutionary Computation 12(2004), 461-493.
• [5] M.D. Vose. The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, Massachusetts, 1999.