offutt@caen.engin.umich.edu (daniel m offutt) (12/17/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
felsenst@entropy.ms.washington.edu (Joe Felsenstein) (12/18/88)
[this one already sent also to MOLECULAR-EVOLUTION on BIONET newsgroups] I note the strong claims made for the magicality of the "genetic algorithm", e.g.: > 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 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, ... >Dan Offutt offutt@caen.engin.umich.edu I recently acted as reviewer on a paper in the optimization-by-simulated- evolution literature, and was disturbed to find in it assertions that biologists have proven that this strategy is incredibly powerful. Now we are told that computer scientists have proofs of powerfulness that we biologists should be reassured by. I suspect neither is true. Genetic systems optimize pretty well, but only when there is a rather uncomplex relationship between genotype and phenotype. In their most sophisticated form (Sewall Wright's "Shifting Balance Theory") they can only cope with moderate interaction among genetic elements. Real genetic systems mostly do not interact enormously strongly (your keratin genes which affect hair and toenails are unlikely to affect the oxygen-carrying properties of your blood, and so on). If they did not have this partial decoupling of effects, they would not evolve very well: every mutant would reduce the organism to a disorganized mess, and no progress would be made. Presumably organisms whose genes interacted to strongly just never evolved well and died out. Does anyone have real proofs that simulated evolution is much more powerful as a mathematical optimization method than biologists have concluded evolution is as a real evolutionary process? I note Offutt's citations of work by Holland, but are there others? What do they really show? I would expect SA to work pretty well, but only if the genotype-to-phenotype mapping is not too tightly interactive. It should not be the magical all-purpose optimization method everyone is looking for. Pandas can't fly. Note -- this is NOT intended as an argument against creationists. --- Joe Felsenstein, Dept. of Genetics SK-50, Univ. of Washington, Seattle WA 98195 BITNET: FELSENST@UWALOCKE INTERNET: joe@evolution.ms.washington.edu or: uw-evolution!joe@entropy.ms.washington.edu UUCP: ... uw-beaver!uw-entropy!uw-evolution!joe