offutt@caen.engin.umich.edu (daniel m offutt) (12/18/88)
In article <7034@venera.isi.edu> smoliar@vaxa.isi.edu.UUCP (Stephen Smoliar) writes: >The characterization of genetic algorithms may have reversed the cart and the >horse. Genetic algorithms may be said to have been inspired by chromosomal >behavior, but I think it would be an exaggeration to call them a simulation, >of any organic situation. Genetic algorithms are not just motivated by evolution, they are simulations of evolution including: 1. A population of linear or circular strands of DNA each modeled using a two-letter alphabet, 2. An environment modeled as a computable function which determines fitness of a chromosome, 3. Fitness-based reproduction of chromosomes (offspring), 4. Crossing over of pairs of chromosomes producing recombinants, 5. Point mutation, 6. Inversion (in some models), 7. Punctuation marking sites of possible crossing over (in some models), 8. Recessive and dominant alleles (in some models), 9. Speciation (in some models), 10. Semi-isolated subpopulations (in some models), 11. Mate-selection procedures (in some models), 12. A temporal ordering and causal connectedness among these events which correspends to the modeled events in nature: successive generations of creation, testing, recombination, reproduction, and finally deletion from the population. The world is too complex for any computer simulation to capture every aspect of evolution, or any other physical process. Consequently there are aspects of evolution not simulated (yet) in genetic algorithms, including: 1. Fertilization, 2. Spontaneous abortion, 3. Multiple chromosomes in one genotype, 4. Any of the idiosyncrasies of the generation of sex cells aside from crossing over. 5. Homologous pairs. 6. Any of the codon sequences found in DNA, aside from those coding for sites of possible crossing over. 7. Transcription. 8. Protein synthesis. 9. etc., etc. My point again is that the algorithm was copied from nature, not invented by, say, a clever operations researcher. (The formal theory of genetic algorithms is another matter. Holland (1975,1976) has proven a generalization of Fisher's (1930) classic result which is not restricted to alleles, but holds for all subsets of alleles within individual chromosomes. Genetic algorithms derive largely from this genetic search theory (GST) which falls within the field of mathematical genetics.) A "no-frills" genetic algorithm, with the basic allele-set ranking capabilities that make GA's effective function optimizers, can be implemented in one page of C code. The fundamental algorithm is simple enough that it is quite plausible that it was discovered (by nature) via a much weaker pure-random search process. The observed efficiency of genetic algorithms at locating ever-better local optima on a wide variety of complex performance surfaces, without becoming trapped on a local optimum anywhere, counts as evidence that if it were applied to optimizing performance measures defined by natural environments, it would be able to locate quite complex stable physical systems such as plants and animals. So perhaps, given the similarity of the algorithm to the natural evolutionary process, this is what has actually happened. ====================================================================== Dan Offutt offutt@caen.engin.umich.edu