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 M3 (M cubed) distinct combinations of alleles. For populations of any considerable size this number M3 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.
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Bethke, A. D. [1980]. “Genetic Algorithms as Function Optimizers.” University of Michigan Ph.D. Dissertation. Boden, M. A. [this volume]. Failure is not the spur.
Buchanan, B. G. and Mitchell, T. M. [1978]. Model-directed learning of production rules, in: “Pattern-Directed Inference Systems,” D. A. Waterman and F. Hayes-Roth, eds., Academic Press, New York.
Buchanan, B. G. [this volume].
Davis, R. and King, J. [1976]. An overview of production systems, in; “Machine Intelligence 8,” E. W. Elcock and D. Michie, eds., Wiley, New York.
De Jong, K. A. [1980]. Adaptive system design — a genetic approach, IEEE Trans. Systems, Man, and Cybernetics, 10:9.
Eigen, M. and Winkler, R. [1981]. “Laws of the Game,” Knopf, New York.
Fahlman, S. E. [1979]. “NETL: A System for Representing and Using Real-World Knowledge,” MIT Press, Cambridge.
Holland, J. H. [1975]. “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor.
Holland, J. H. [1976a]. Studies of the spontaneous emergence of self-replicating systems using cellular automata and formal grammars, in: “Automata, Languages and Development,” A. Lindenmayer and G. Rozenberg, eds., North Holland, Amsterdam.
Holland, J. H. [1976b]. Adaptation, “Progress in Theoretical Biology, 4,” R. Rosen and F. M. Snell, eds., Academic Press, New York.
Holland, J. H. [1980]. Adaptive algorithms for discovering and using general patterns in growing knowledge bases. Int. J. Policy Analysis and Information Systems, 4:3.
Holland, J. H. and Reitman, J. S. [1978]. Cognitive systems based on adaptive algorithms, “Pattern-Directed Inference Systems,” D. A. Waterman and F. Hayes-Roth, eds., Academic Press, New York.
Lenat, D. B. [1980]. The Heuristics of Nature: The Plausible Mutation of DNA. Stanford University Computer Science Department Report HPP-80–27.
Lewin, R. [1981]. Biggest challenge since the double helix. Science 212, April 3.
McDermott, J. and Forgy, C. [1978]. Production system conflict resolution strategies, “Pattern-Directed Inference Systems,” D. A. Waterman and F. Hayes-Roth, eds., Academic Press, New York.
Moorhead, P. S. and Kaplan, M. M. [1967]. “Mathematical Challenges in the Neo-Darwinian Interpretation of Evolution,” Wistar Institute Press, Philadelphia.
Simon, H. A. [1981]. “The Sciences of the Artificial,” MIT Press, Cambridge.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1984 Plenum Press, New York
About this chapter
Cite this chapter
Holland, J.H. (1984). Genetic Algorithms and Adaptation. In: Selfridge, O.G., Rissland, E.L., Arbib, M.A. (eds) Adaptive Control of Ill-Defined Systems. NATO Conference Series, vol 16. Springer, Boston, MA. https://doi.org/10.1007/978-1-4684-8941-5_21
Download citation
DOI: https://doi.org/10.1007/978-1-4684-8941-5_21
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4684-8943-9
Online ISBN: 978-1-4684-8941-5
eBook Packages: Springer Book Archive