Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm | Genetic Programming and Evolvable Machines Skip to main content
Springer Nature Link
Log in

Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm

  • Original Paper
  • Published:
Genetic Programming and Evolvable Machines Aims and scope Submit manuscript

Abstract

In this work, a method is presented for analysis of Markov chains modeling evolutionary algorithms through use of a suitable quotient construction. Such a notion of quotient of a Markov chain is frequently referred to as “coarse graining” in the evolutionary computation literature. We shall discuss the construction of a quotient of an irreducible Markov chain with respect to an arbitrary equivalence relation on the state space. The stationary distribution of the quotient chain is “coherent” with the stationary distribution of the original chain. Although the transition probabilities of the quotient chain depend on the stationary distribution of the original chain, we can still exploit the quotient construction to deduce some relevant properties of the stationary distribution of the original chain. As one application, we shall establish inequalities that describe how fast the stationary distribution of Markov chains modeling evolutionary algorithms concentrates on the uniform populations as the mutation rate converges to 0. Further applications are discussed. One of the results related to the quotient construction method is a significant improvement of the corresponding result of the authors’ previous conference paper [Mitavskiy et al. (2006) In: Simulated Evolution and Learning, Proceedings of SEAL 2006, Lecture Notes in Computer Science v. 4247, Springer Verlag, pp 726–733]. This papers implications are all strengthened accordingly.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Most types of recombination used in practice are pure in the sense of [16] so that they preserve the uniform populations.

  2. Recall that in the current paper, we use the m-tuple representation.

  3. In order to guarantee a unique steady state distribution, we also need to assume that the Markov chain is aperiodic. We make this assumption throughout the paper.

  4. This theorem is stated in the appendix of [3].

  5. A similar result was obtained in [2] by completely different methods.

References

  1. Schmitt, L.: Theory of genetic algorithms. Theor. Comput. Sci. 259, 1–61 (2001)

    Article  MATH  Google Scholar 

  2. Schmitt, L.: Theory of genetic algorithms ii: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling. Theor. Comput. Sci. 310, 181–231 (2004)

    Article  MATH  Google Scholar 

  3. Vose, M.: The Simple Genetic Algorithm: Foundations and Theory. MIT Press (1999)

  4. Coffey, S.: An Applied Probabilist’s Guide to Genetic Algorithms. A Thesis Submitted to The University of Dublin for the degree of Master in Science (1999)

  5. Mitavskiy, B., Rowe, J.: An Extension of Geiringer Theorem for a wide class of evolutionary search algorithms. Evol. Comput. 14(1), 87–118 (2006)

    MathSciNet  Google Scholar 

  6. Mitavskiy, B.: A schema-based version of Geiringer’s Theorem for nonlinear Genetic Programming with homologous crossover. Found. Gen. Algorithms 8, 156–175 Springer-Verlag (2005)

    Article  MathSciNet  Google Scholar 

  7. Mitavskiy, B., Rowe, J.: Some results about the Markov chains associated to GPs and general EAs. Theor. Comput. Sci. 361(1), 72–110 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  8. Davis, T., Principe, J.: A simulated annealing like convergence theory for the simple genetic algorithm. In: Belew, R., Bookers, L. (eds.) Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 174–181. Morgan Kaufmann (1991)

  9. Suzuki, J.: A further result on the Markov chain model of genetic algorithm and its application to simulated annealing-like strategy. IEEE Trans. Syst. Man Cybernet. 28(1), 95–102 (1998)

    Article  Google Scholar 

  10. Mitavskiy, B., Rowe, J., Wright, A., Schmitt, L.: Exploiting quotients of Markov chains to derive properties of the stationary distribution of the markov chain associated to an evolutionary algorithm. In: Simulated Evolution and Learning, Proceedings of SEAL 2006, Lecture Notes in Computer Science v. 4247, pp. 726–733. Springer Verlag (2006)

  11. Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs (unpublished book) (2001) http://www.stat.berkeley.edu/

  12. Rowe, J., Vose, M., Wright, A.: Differentiable coarse graining. Theor. Comput. Sci. 361, 111–129 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  13. Spears, W., De Jong, K.: Analyzing GAs using Markov chain models with semantically ordered and lumped states. In: Belew, R., Vose, M. (eds.) Foundations of Genetic Algorithms 4, pp. 85–100. Morgan Kaufmann (1997)

  14. Moey, C., Rowe, J.: Population aggregation based on fitness. Nat. Comput. 3, 5–19 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  15. Moey, C.: Investigating state aggregation for Markov models of genetic algorithms. Thesis, The University of Birmingham (2006)

  16. Radcliffe, N.: The algebra of genetic algorithms. Ann. Math. Artif. Intel. 10, 339–384 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  17. Mitavskiy, B.: Crossover invariant subsets of the search space for evolutionary algorithms. Evol. Comput. 12(1), 19–46 (2004)

    Article  Google Scholar 

  18. Antonisse, J.: A new interpretation of schema notation that overturns the binary encoding constraint. In: Schaffer, J.D. (ed.) Proceedings of the Third International Conference on Genetic Algorithms, pp. 86–97. Morgan Kaufmann (1989)

Download references

Author information

Authors and Affiliations

  1. School of Medicine, University of Sheffield, Sheffield, S10 2JF, Great Britain

    Boris Mitavskiy

  2. School of Computer Science, University of Birmingham, Birmingham, B15 2TT, Great Britain

    Jonathan E. Rowe

  3. Department of Computer Science, University of Montana, Missoula, MT, 59812, USA

    Alden Wright

  4. School of computer Science and Engineering, The University of Aizu, Aizu-Wakamatsu City, Fukushima Prefecture, 965-8580, Japan

    Lothar M. Schmitt

Authors
  1. Boris Mitavskiy
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Jonathan E. Rowe
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Alden Wright
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Lothar M. Schmitt
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Boris Mitavskiy.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mitavskiy, B., Rowe, J.E., Wright, A. et al. Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm. Genet Program Evolvable Mach 9, 109–123 (2008). https://doi.org/10.1007/s10710-007-9038-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10710-007-9038-6

Keywords