From: szabo@netcom.com (Nick Szabo)
Date: Fri, 20 Aug 93 17:11:52 PDT
To: collins@newton.apple.com (Scott Collins)
Subject: Re: genetic algorithms for crypto analysis
In-Reply-To: <9308202305.AA26160@newton.apple.com>
Message-ID: <9308210012.AA04248@netcom5.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



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