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

Theme preservation and the evolution of representation

Published: 25 June 2005 Publication History

Abstract

In his thesis Toussaint calls for a "general project to develop theories on adaptation processes that account for the adaptation of representations". The theory developed in this paper is a contribution to this project. We first define the simple concept of a genotypic theme and define what it means for mutation operators to be theme preserving and theme altering. We use the idea of theme preservation to develop the concept of subrepresentation. Then we develop a theory that illuminates the behavior of a mutation-only fitness proportional evolutionary algorithm in which mutation preserves genotypic themes with high probability. Our theory shows that such evolutionary algorithms implicitly implement what we call subrepresentation evolving multithreaded evolution, i.e. such EAs conduct second-order search over a predetermined set of representations and exploit promising representations for first order evolutionary search. We illuminate subrepresentaiton evolving multithreaded evolution by comparing and contrasting it with the behavior of island model EAs. Our theory is immediately useful in understanding the significance of the low probability with which theme altering type 2 mutations are applied to genotypes of the evolutionary systems in Toussaint's thesis.

References

[1]
Altenberg, L. The evolution of evolvability in genetic programming. In Advances in Genetic Programming, K. E. Kinnear, Jr., Ed. MIT Press, 1994, ch. 3, pp. 47--74.
[2]
Halder, G., Callaerts, P., and Gehring, W. Induction of ectopic eyes by targeted expression of the eyeless gene in drosophilia. Science 267 (1995), 1788--1792.
[3]
Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.
[4]
Radcliffe, N. J. The algebra of genetic algorithms. Annals of Mathematics and Artificial Intelligence 10 (1994), 339--384.
[5]
Schwefel, H.-P. Evolution and Optimum Seeking. Sixth-Generation Computer Technology Series. John Wiley and Sons, New York NY, 1995.
[6]
Skolicki, Z., and De Jong, K. Improving evolutionary algorithms with multi-representation island models. In Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference (Seattle, Washington, USA, 26 July 2004), M. Keijzer, Ed.
[7]
Toussaint, M. Demonstrating the evolution of complex genetic representations: An evolution of artificial plants. In Genetic and Evolutionary Computation - GECCO-2003 (Berlin, 2003), E. Cantú-Paz, J. A. Foster, K. Deb, D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. Dowsland, N. Jonoska, and J. Miller, Eds., Springer-Verlag, pp. 86--97.
[8]
Toussaint, M. The Evolution of Genetic Representations and Modular Neural Adaptation. PhD thesis, Institut fr Neuroinformatik, Ruhr-Universit-Bochum, Germany, 2003.
[9]
Vose, M. D. The simple genetic algorithm: foundations and theory. MIT Press, Cambridge, MA, 1999.
[10]
Wagner, G. P., and Altenberg, L. Complex adaptations and the evolution of evolvability. Evolution (1996), In press.
[11]
Whitley, D. A genetic algorithm tutorial. Statistics and Computing 4 (1994), 65--85.

Cited By

View all
  • (2007)Sufficient conditions for coarse-graining evolutionary dynamicsProceedings of the 9th international conference on Foundations of genetic algorithms10.5555/1757524.1757527(35-53)Online publication date: 8-Jan-2007
  • (2007)Sufficient Conditions for Coarse-Graining Evolutionary DynamicsFoundations of Genetic Algorithms10.1007/978-3-540-73482-6_3(35-53)Online publication date: 2007
  • (2006)Compact representations as a search strategyTheoretical Computer Science10.1016/j.tcs.2006.04.005361:1(57-71)Online publication date: 28-Aug-2006

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '05: Proceedings of the 7th annual workshop on Genetic and evolutionary computation
June 2005
431 pages
ISBN:9781450378000
DOI:10.1145/1102256
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: 25 June 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. evolution of representation
  2. evolutionary algorithms
  3. theme preservation

Qualifiers

  • Article

Conference

GECCO05
Sponsor:

Acceptance Rates

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
  • (2007)Sufficient conditions for coarse-graining evolutionary dynamicsProceedings of the 9th international conference on Foundations of genetic algorithms10.5555/1757524.1757527(35-53)Online publication date: 8-Jan-2007
  • (2007)Sufficient Conditions for Coarse-Graining Evolutionary DynamicsFoundations of Genetic Algorithms10.1007/978-3-540-73482-6_3(35-53)Online publication date: 2007
  • (2006)Compact representations as a search strategyTheoretical Computer Science10.1016/j.tcs.2006.04.005361:1(57-71)Online publication date: 28-Aug-2006

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