Genetic Algorithms and Adaptation

Abstract

Genetics provides us with a canonical example of a complex search through a space of ill-defined possibilities. The basic problem is one of manipulating representations — the chromosomes — so as to search out and generate useful organization — the functional properties of the organism.

Even simple models of adaptation, based on (simplified) versions of reproduction, crossover and mutation, search the space of chromosomes in a way much more subtle than a “random search with preservation of the best.” In fact, the usual notion of evolution in terms of pools of alleles falls far short of describing what happens. Rather, the system acts as if it were continually testing a wide variety of combinations of alleles for use as components in the construction of new chromosomes. (In terms familiar to geneticists, the process is searching out coadapted sets of alleles. The alleles belonging to a given coadapted set may be distributed over the chromosome, and a given allele may belong to many distinct coadapted sets.) The overall effect is one of steadily biasing the generation of chromosomes toward incorporation of combinations (components) that have proved useful in similar contexts. It can be proved that this adaptive process, though dealing with a population (sample) of size M, usefully tests and exploits information about far in excess of M³ (M cubed) distinct combinations of alleles. For populations of any considerable size this number M³ is astronomically larger than the total number of alleles in the population. The corresponding speed-up in the search rate, a property called implicit parallelism, increases the adaptive potential tremendously. Moreover the implicit parallelism makes the process all but immune to some of the difficulties — particularly, high-dimensionality, discontinuity and false peaks — that attend complex ill-defined problems.

The laws of the models we have studied constitute a set of axioms that must at least be satisfied by any more sophisticated model involving more complicated versions of the genetic operators; as a consequence the basic properties of these models — the theorems — must hold in more sophisticated models that come closer to property of these more realistic models.

It is possible to give gentic processes an algorithmic formulation that makes them available as control procedures in a wide variety of situations. By using an appropriate production (rule-based) language, it is even possible to construct sophisticated models of cognition wherein the genetic algorithm, applied to the productions, provides the system with the means of learning from experience. Such models are currently being tested. Even the early models show surprising capacities for “adaptation under sensory guidance.” Among the more important properties they exhibit are:

• (1) the ability to modify and develop decision and action sequences when payoff or feedback about performance occurs only after long sequences of context-dependent action;

• (2) the ability to generate a model for the environment based on the system’s experience, a model usable for lookahead and prediction.