The Evolution of Evolvability in Genetic Programming 论文

摘要

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. LEE ALTENBERG Evolvability"Evolvability" is a concept I wish to develop as a performance measure for genetic algorithms.By evolvability I mean the ability of the genetic operator/representation scheme to produce offspring that are fitter than their parents.Clearly this is necessary for adaptation to progress.Because adaptation depends not only on how often offspring are fitter than their parents, but on how much fitter they are, the property ultimately under consideration, when speaking of evolvability, is the entire distribution of fitnesses among the offspring produced by a population.Since there is a chance that offspring are fitter than parents even in random search, good GA performance requires that the upper tail of the offspring fitness distribution be fatter than that for random search.But this excess of fitter offspring as compared with random search needn't occur with all parents.It need only occur with parents that are fitter than average, because selection is biasing the population in that direction.In other words, the action of the genetic operator on the representation needs to produce high correlations between the performance of parents and the fitness distribution of their offspring.This is shown in Section 3.2.3through an application of Price's Covariance and Selection Theorem [Price 1970].Price's Theorem in my mind serves as a fundamental theorem for genetic algorithms.This correlation property is exemplified by the Building Blocks hypothesis [Goldberg 1989].A building block is a schema [Holland 1975] from a fitter-than-average individual which, when recombined into another individual, is likely to increase its fitness.Thus a building block is defined by a correlation between parent and offspring fitnesses under recombination.A recombination operator which is able to pick out this schema from one individual and substitute it into another is then leaving intact the building blocks but producing variation in a way for which there is adaptive opportunity, namely, combining the proper building blocks.But for recombination to be of use, however, the representation must be such that building blocks -i.e.schemata which give correlated fitnesses when substituted into a chromosome by recombination -exist.Evolvability can be understood to be the most "local" or finest-grained scale for measuring performance in a genetic algorithm, whereas the production of fitter offspring over the course of a run of a GA, or many runs, are more "global", large scale performance measures.As a population evolves, the distribution of offspring fitnesses is likely to change.The global performance of a genetic algorithm depends on it maintaining the evolvability of the population as the population evolves toward the global optimum.I will explore how genetic programming, through its ability to evolve its representations, may be able to maintain or increase the evolvability of the programs as a population evolves.