Theoretical analysis of steady state genetic algorithms

Alexandru Agapie; Alden H. Wright

Applications of Mathematics (2014)

  • Volume: 59, Issue: 5, page 509-525
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Agapie, Alexandru, and Wright, Alden H.. "Theoretical analysis of steady state genetic algorithms." Applications of Mathematics 59.5 (2014): 509-525. <http://eudml.org/doc/262048>.

@article{Agapie2014,
abstract = {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.},
author = {Agapie, Alexandru, Wright, Alden H.},
journal = {Applications of Mathematics},
keywords = {genetic algorithm; Markov chain; random heuristic search; genetic algorithm; Markov chain; random heuristic search},
language = {eng},
number = {5},
pages = {509-525},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Theoretical analysis of steady state genetic algorithms},
url = {http://eudml.org/doc/262048},
volume = {59},
year = {2014},
}

TY - JOUR
AU - Agapie, Alexandru
AU - Wright, Alden H.
TI - Theoretical analysis of steady state genetic algorithms
JO - Applications of Mathematics
PY - 2014
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 59
IS - 5
SP - 509
EP - 525
AB - 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.
LA - eng
KW - genetic algorithm; Markov chain; random heuristic search; genetic algorithm; Markov chain; random heuristic search
UR - http://eudml.org/doc/262048
ER -

References

top
  1. Agapie, A., 10.1007/BFb0056844, Lect. Notes Comput. Sci. 1498 (1998), 3-12. (1998) DOI10.1007/BFb0056844
  2. Agapie, A., 10.1162/106365601750190370, Evol. Comput. 9 (2001), 127-146. (2001) DOI10.1162/106365601750190370
  3. Agapie, A., 10.1080/00207160801968788, Int. J. Comput. Math. 87 (2010), 491-508. (2010) Zbl1181.62177MR2598756DOI10.1080/00207160801968788
  4. Agapie, A., Agapie, M., Rudolph, G., Zbaganu, G., 10.1109/TCYB.2013.2257748, IEEE Trans. Cybern. 43 (2013), 1462-1472. (2013) DOI10.1109/TCYB.2013.2257748
  5. Agapie, A., Agapie, M., Zbaganu, G., 10.1080/00207721.2011.605963, Int. J. Syst. Sci. 44 (2013), 502-512. (2013) MR3000764DOI10.1080/00207721.2011.605963
  6. Davis, L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York (1991). (1991) 
  7. Mitavskiy, B., Rowe, J., Wright, A. H., Schmitt, L., 10.1007/s10710-007-9038-6, Genet. Program. Evolv. Mach. 9 (2008), 109-123. (2008) DOI10.1007/s10710-007-9038-6
  8. Rudolph, G., Convergence Properties of Evolutionary Algorithms, Verlag Dr. Kovać, Hamburg (1997). (1997) 
  9. Rudolph, G., 10.1007/978-3-540-92910-9_27, Handbook of Natural Computing G. Rozenberg, T. H. W. Bäck, J. N. Kok Springer, Berlin (2012). (2012) DOI10.1007/978-3-540-92910-9_27
  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. 
  11. Vose, M. D., The Simple Genetic Algorithm. Foundations and Theory, MIT Press Cambridge (1999). (1999) Zbl0952.65048MR1713436
  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. (1989) 
  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. (2002) Zbl0987.68094

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.