Sexual reproduction (aka string crossover)
Sexual reproduction is not string crossover. Normal reproduction in a typical GA picks two individuals from the population independently with probability related to their fitness. In sexual reproduction, the pairs are constrained such that selection is not independent e.g., 'males' mate with 'females'. Sexual reproduction is one factor that dampens premature dominance of the population by a few 'great' individuals, so that search can continue on other hills, i.e. encourages diversity and thus IS good, as was previously stated, in choppier solution spaces. Also consider the dominance mechanism supported by the diploid chromosome. One reason why double-strand species like ourselves can more rapidly adapt than haploid species. Dominance protects solutions that were good once (and might be again) from being sampled to death, by holding them in abeyance (a 'recessive' trait) in a temporarily unfavorable environment. Again, this encourages diversity by dampening premature destruction of hard won solutions. Scott Collins | "Few people realize what tremendous power there | is in one of these things." -- Willy Wonka ......................|................................................ BUSINESS. voice:408.862.0540 fax:974.6094 collins@newton.apple.com Apple Computer, Inc. 1 Infinite Loop, MS 301-2C Cupertino, CA 95014 ....................................................................... PERSONAL. voice/fax:408.257.1746 1024/669687 catalyst@netcom.com
Scott Collins discusses the contraint of crossover with the male/ female partition and dominance. This is theoretically interesting, especially to biology. I know of no theoretical proof that such constraints improve the search of choppy search spaces, and there is little empirical evidence -- this is a cutting-edge research topic. The poster who first brought up sexual reproduction was discussing it in terms of its cutting and pasting of strings: crossover. Crossover itself provides a far more general solution than simple mutating, hill-climbing algorithms; specifically GAs are better in choppy, non-continuous spaces. The empirical evidence for this is quite substantial (the literature on GAs) and there is theoretical substantiation (Holland, Goldberg, et. al.). Perhaps constraining with male/female and dominance provides even further improvement for some kinds of choppiness, as might (more generally) demes, but those are open research questions in the GA community, not immediately germane to the general question of whether GA might be useful for cryptanalysis. I'd like to hear more about the male/female partition and dominance -- on comp.ai.genetic, ga-distr, or genetic-programming which I read regularly, and are much more appropriate for discussing this issue. Nick Szabo szabo@netcom.com
participants (2)
-
collins＠newton.apple.com -
szabo＠netcom.com