| Title:
|
Theoretical analysis of steady state genetic algorithms (English) |
| Author:
|
Agapie, Alexandru |
| Author:
|
Wright, Alden H. |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
59 |
| Issue:
|
5 |
| Year:
|
2014 |
| Pages:
|
509-525 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Evolutionary Algorithms, also known as Genetic Algorithms in a former terminology, are probabilistic algorithms for optimization, which mimic operators from natural selection and genetics. The paper analyses the convergence of the heuristic associated to a special type of Genetic Algorithm, namely the Steady State Genetic Algorithm (SSGA), considered as a discrete-time dynamical system non-generational model. Inspired by the Markov chain results in finite Evolutionary Algorithms, conditions are given under which the SSGA heuristic converges to the population consisting of copies of the best chromosome. (English) |
| Keyword:
|
genetic algorithm |
| Keyword:
|
Markov chain |
| Keyword:
|
random heuristic search |
| MSC:
|
60J10 |
| MSC:
|
60J20 |
| MSC:
|
68T05 |
| MSC:
|
68W20 |
| MSC:
|
90C59 |
| idZBL:
|
Zbl 06391448 |
| idMR:
|
MR3255793 |
| DOI:
|
10.1007/s10492-014-0069-z |
| . |
| Date available:
|
2014-09-29T08:57:31Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143928 |
| . |
| Reference:
|
[1] Agapie, A.: Modelling genetic algorithms: From Markov chains to dependence with complete connections.Lect. Notes Comput. Sci. 1498 (1998), 3-12. 10.1007/BFb0056844 |
| Reference:
|
[2] Agapie, A.: Theoretical analysis of mutation-adaptive evolutionary algorithms.Evol. Comput. 9 (2001), 127-146. 10.1162/106365601750190370 |
| Reference:
|
[3] Agapie, A.: Estimation of distribution algorithms on non-separable problems.Int. J. Comput. Math. 87 (2010), 491-508. Zbl 1181.62177, MR 2598756, 10.1080/00207160801968788 |
| Reference:
|
[4] Agapie, A., Agapie, M., Rudolph, G., Zbaganu, G.: Convergence of evolutionary algorithms on the n-dimensional continuous space.IEEE Trans. Cybern. 43 (2013), 1462-1472. 10.1109/TCYB.2013.2257748 |
| Reference:
|
[5] Agapie, A., Agapie, M., Zbaganu, G.: Evolutionary algorithms for continuous space optimization.Int. J. Syst. Sci. 44 (2013), 502-512. MR 3000764, 10.1080/00207721.2011.605963 |
| Reference:
|
[6] Davis, L.: Handbook of Genetic Algorithms.Van Nostrand Reinhold, New York (1991). |
| Reference:
|
[7] Mitavskiy, B., Rowe, J., Wright, A. H., Schmitt, L.: Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm.Genet. Program. Evolv. Mach. 9 (2008), 109-123. 10.1007/s10710-007-9038-6 |
| Reference:
|
[8] Rudolph, G.: Convergence Properties of Evolutionary Algorithms.Verlag Dr. Kovać, Hamburg (1997). |
| Reference:
|
[9] Rudolph, G.: Stochastic convergence.Handbook of Natural Computing G. Rozenberg, T. H. W. Bäck, J. N. Kok Springer, Berlin (2012). 10.1007/978-3-540-92910-9_27 |
| Reference:
|
[10] Syswerda, G.: A study of reproduction in generational and steady state genetic algorithms.Foundations of Genetic Algorithms San Mateo, Morgan Kaufman, San Francisco, 1991 94-101. |
| Reference:
|
[11] Vose, M. D.: The Simple Genetic Algorithm. Foundations and Theory.MIT Press Cambridge (1999). Zbl 0952.65048, MR 1713436 |
| Reference:
|
[12] Whitley, D.: The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best.Proceedings of the Third International Conference on Genetic Algorithms Morgan Kaufman San Francisco (1989), 116-123. |
| Reference:
|
[13] Wright, A. H., Rowe, J.: Continuous dynamical system models of steady-state genetic algorithms.Foundations of Genetic Algorithms---6 Proc. FOGA-6, Morgan Kaufmann Publishers, Orlando (2002), 209-225. Zbl 0987.68094 |
| . |
