x + 170 pp. U.S. $14.95 (harcover) John H. Holland, ,Adaptation in Natural and Artificial Systems (1975) The University of Michigan Press,New York.
✍ Scribed by Hugo M. Martinez
- Book ID
- 104272172
- Publisher
- Springer
- Year
- 1976
- Tongue
- English
- Weight
- 254 KB
- Volume
- 38
- Category
- Article
- ISSN
- 1522-9602
No coin nor oath required. For personal study only.
✦ Synopsis
Anyone who has encountered the apparent intractability of some of the pivotal optimization problems which occur in any of such diverse fields as control, economic planning, artificial intelligence and biological evolution will find hero a refreshing and promising approach for treating the complicating elements of high dimension, nonlinearity and uncertainty. Taking his cue from the known or suspected mechanisms of evolution and drawing from the experience of many previous theoretical efforts concerned with hierarchical representations, adaptive spaces and cellular automata, Professor Holland has conceived a disarmingly simple and elegant way of designing or hypothesizing relevant search algorithms with the goal of achieving both robustness and efficiency in their operation. They are referred to as genetic plans.
Search algorithms containing elements suggestive of evolutionary mechanisms are not new. What appears to be novel here is the conceptualization of the points of the search space as sets of strings to which the operations of crossover, inversion, point mutations, intrachromosomal duplication, translocation, etc., may be applied much as in the actual biological case. With some liberty of interpretation and notation that reflects the reviewer's interests and background, the essential idea and implications appear to be as follows.
We first imagine the original search space, whether it be of control policies, decision functions, economic policies, organisms, etc., to be characterized by n parameters P1, P2, • • •, Pn. For instance, one might be concerned with the space of decision functions all1 + a2fu + . . . + anfn which are linear combinations of a basic set of functions fl, f2, • •., fn. The parameters are the coefficients. Again, the space might consist of the genotypes composablo from n kinds of genes, with the alleles of each constituting the discrete parameter "values." Whichever the case, there is the common feature that if p~ is an allowed value for the ith parameter P~ than all permutations of the single string PlP~ • . • Pn can be regarded as representing the same point in the search space. For a k-string representation, the parameter set is partitioned into k parts and each part is given a one-string representation. Regarding a string as a "chromosome" one can thus think of the original search space as having a '°k-chromosome" representation and, correspondingly, two strings will be "homologous" if they represent the same parameter subset in the same order• Crossover between homologous strings thus results in strings homologous to each other and to the original strings.
If a k-string representation is such that each parameter is represented exactly once, then it can be thought of as a "haploid" representation. A "diploid" version results if each string is accompanied by exactly one homolog, if each parameter is represented exactly twice and if there is some "dominance rule" for removing the ambiguity, i.e., reducing the 2n parameter values to n.
Given a string representation, matters now proceed somewhat in the sense of population genetics. The start of the search assumes an initial population B(0) corresponding to a set 211