Pathologically Eclectic Rubbish Lister  
PerlMonks 
comment on 
( #3333=superdoc: print w/replies, xml )  Need Help?? 
Cool program!
The evolution of the score you see is pretty typical of genetic algorithms and genetic programs: much progress is made in the initial iterations, but it takes a lot more to gain further improvement. I just wanted to mention that the assertion by ff's professor that you only need 30 tries is patently false. If a problem has many degrees of freedon and a complex error surface, in general the amount of searching one must do is O(k^N), where N is the number of degrees of freedom and k is related to the complexity of the error surface. To see this, consider a simple example. Suppose we one have degree of freedom and we know that a good solution lies either at x = 1 or x = 1. Then we only have to search twice. Now add a similar degree of freedon y that interacts with x in a complex way. Then we would need to search (+1, +1), or 4 attempts. Adding another would need 8 attempts, and so on, yielding O(2^N) behavior. An this is just looking for a good quadrant! This blowup of search space with degrees of freedom is called the 'curse of dimensionality' and along with a complex error surface, is the basic reason that some problems are NPcomplete. Some problems have some nice large scale structure of the error surface that admit heurisitic guesses that often do well, but others, like ksatisfiability for k > 2, don't seem to. So don't throw away your simulated annealing and genetic algorithms code yet! Mark In reply to Re: Evolution in Action.
by kvale

