Lee Altenberg's Home Page >
Papers |
E-mail me
The Evolution of Evolvability in Genetic Programming
Lee Altenberg
Chapter 3 in Advances in Genetic Programming, ed. Kenneth Kinnear. pp. 47-74. MIT Press, Cambridge, 1994.
Abstract
The notion of “evolvability” — the ability of a population to produce variants fitter than any yet existing — is developed as it applies to genetic algorithms. A theoretical analysis of the dynamics of genetic programming predicts the existence of a novel, emergent selection phenomenon: the evolution of evolvability. This is produced by the proliferation, within programs, of blocks of code that have a higher chance of increasing fitness when added to programs. Selection can then come to mold the variational aspects of the way evolved programs are represented. A model of code proliferation within programs is analyzed to illustrate this effect. The mathematical and conceptual framework includes: the definition of evolvability as a measure of performance for genetic algorithms; application of Price's Covariance and Selection Theorem to show how the fitness function, representation, and genetic operators must interact to produce evolvability — namely, that genetic operators produce offspring with fitnesses specifically correlated with their parent's fitnesses; how blocks of code emerge as a new level of replicator, proliferating as a function of their “constructional fitness”, which is distinct from their schema fitness; and how programs may change from innovative code to conservative code as the populations mature. Several new selection techniques and genetic operators are proposed in order to give better control over the evolution of evolvability and improved evolutionary performance.
Reviews
-
However, in Riedl’s work, the idea that organisms may
have properties that would increase their ability to evolve
was still articulated vaguely. Interestingly, the first clear
formalization of evolvability stems from computer science.
Lee Altenberg worked on optimization algorithms in genetic
programming and defined evolvability as “the ability of a
population to produce variants fitter than any yet existing”
(Altenberg 1994). We will stick to this general meaning of
evolvability for the purpose of this paper, in spite of later
differentiation of the term (see Pigliucci 2008). —Pavlicev and Wagner. 2012. Coming to Grips with Evolvability. Evo Edu Outreach 5:231-244.