From: szabo@netcom.com (Nick Szabo)
Date: Fri, 20 Aug 93 15:11:17 PDT
To: hahn@lds.loral.com)
Subject: Re: genetic algorithms for crypto analysis
In-Reply-To: <930820165108.47c@lds.loral.com>
Message-ID: <9308202210.AA17612@netcom5.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



HAHN@lds.loral.com:
> [makes excellent point that given sexual reproduction, evolution
>  does not need continuous search space]
>   I don't know if such a strategy would help at all in crypto analysis,
>   or whether any genetic algorithm programs currently in use employ this
>   strategy.

Sexual reproduction (aka string crossover) is the fundamental attribute 
of GAs that distinguish them from hill-climbing algorithms; it has been in 
all GAs from their invention.  One of original works on the subject is 
now out in reprint: John Holland's _Adaptation in Natural and Artificial 
Systems_, MIT Press.  

Crossover doesn't allow magic teleportation directly to the
needle in the search space haystack.  GA leaps over gaps where the 
"crossover Hamming distance" is small, but the space need not be continuous.
Cryptanalysis where one can gain clues, partial solutions, etc. and
compose these into better solutions, might be amenable to GA.
If you can say "solution A is better than solution B" with an 
algorithm, it's a good candidate for solving with GA or GP (genetic 
programming, which works on trees instead of strings).

Nick Szabo				szabo@netcom.com