Re: genetic algorithms for crypto analysis

>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