skip to main content
10.1145/1143997.1144173acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

A general coarse-graining framework for studying simultaneous inter-population constraints induced by evolutionary operations

Published: 08 July 2006 Publication History

Abstract

The use of genotypic populations is necessary for adaptation in Evolutionary Algorithms. We use a technique called form-invariant commutation to study the immediate effect of evolutionary operations on populations of genotypes. This technique allows us to understand compositional changes induced by evolutionary operations in terms of constraints between populations. Deep insight into the population-level effect of some evolutionary operation is possible when multiple constraints can be derived for all pairs of pre and post operative populations; for each such pair of populations the constraints between them are then said to hold simultaneously. When selection is fitness proportional we show that any coarse-graining of the genotype set can be used to systematically derive single constraints between between all pairs of pre and post selection populations. Matters are not so simple in the case of variation. We develop an abstract condition called ambivalence and show that when a coarse-graining and a variation operation satisfy this condition then a systematic derivation of single constraints between all pairs of pre and post variation populations is possible. Finally we show that it is possible to use schema partitions to systematically derive simultaneous constraints for any combination of variation operations that are commonly used in GAs.

References

[1]
Altenberg, L. The evolution of evolvability in genetic programming. In Advances in Genetic Programming, K. E. Kinnear, Jr., Ed. MIT Press, 1994.
[2]
Contreras, A. A., Rowe, J. E., and Stephens, C. R. Coarse-graining in genetic algorithms: Some issues and examples. In GECCO (2003), pp. 874--885.
[3]
Goldberg, D. E. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, Reading, MA, 1989.
[4]
Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.
[5]
Holland, J. H. Building blocks, cohort genetic algorithms, and hyperplane-defined functions. Evolutionary Computation 8, 4 (2000), 373--391.
[6]
Holland, J. H. A derived markov process for modeling reaction networks. Evolutionary Computation 11, 4 (2003), 339--362.
[7]
Mitchell, M. An Introduction to Genetic Algorithms. The MIT Press, Cambridge, MA, 1996.
[8]
Stephens, C., and Waelbroeck, H. Schemata evolution and building blocks. Evolutionary Computation 7, 2 (1999), 109--124.
[9]
Toussaint, M. The Evolution of Genetic Representations and Modular Neural Adaptation. PhD thesis, Institut für Neuroinformatik, Ruhr-Universiät-Bochum, Germany, 2003.
[10]
Vose, M., and Wright, A. Form invariance and implicit parallelism, 2001.
[11]
Vose, M. D. The simple genetic algorithm: foundations and theory. MIT Press, 1999.
[12]
Vose, M. D. Infinite population ga tutorial. Tech. rep., The University of Tennessee, Knoxville, 2004.
[13]
Wright, A. H., Vose, M. D., and Rowe, J. E. Implicit parallelism. In GECCO (2003), pp. 1505--1517.

Cited By

View all
  • (2015)Hypomixability Elimination In Evolutionary SystemsProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725511(163-175)Online publication date: 17-Jan-2015

Index Terms

  1. A general coarse-graining framework for studying simultaneous inter-population constraints induced by evolutionary operations

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation
        July 2006
        2004 pages
        ISBN:1595931864
        DOI:10.1145/1143997
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 08 July 2006

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. coarse-graining
        2. constraints
        3. genetic algorithms
        4. schema theory

        Qualifiers

        • Article

        Conference

        GECCO06
        Sponsor:
        GECCO06: Genetic and Evolutionary Computation Conference
        July 8 - 12, 2006
        Washington, Seattle, USA

        Acceptance Rates

        GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;
        Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)0
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 05 Mar 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2015)Hypomixability Elimination In Evolutionary SystemsProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725511(163-175)Online publication date: 17-Jan-2015

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media