Re: Genetic algorithms
I wrote a GA solver for the cryptogram competition some time back. Hrm... It
appears I haven't got the code anymore. Bother.
It wasn't terribly difficult to write, and it was a bit eerie to watch the
program converge on the solution. Euphoria's sequences make this particularly
nice to implement.
The bottleneck in the program was evaluating the solutions. To score each
solution, each word in that solution was checked to see how well it matched
against the dictionary words. Because matches could take place in any
position (ie: "luzzy" would match four characters in "fuzzy"), it had to
sequentially search the dictionary. The only optimization I could add was to
break the dictionary apart based on word length.
I also tried using a pared-down dictionary of common words at one point, the
idea being that if common words were matched, the remaining letters would
fall into place. That worked fairly well (and a lot faster), but I didn't
think it worked well enough to stand a chance of winning.
It would also occasionally get stuck between several competing solutions, with
the correct solution being pruned out early. Adding mutations helped, but
tended to cause it to take longer to find the correct solution.
I ultimately decided not to submit it because it ended up taking a couple
minutes too long to find the solutions. Still, very cool.
-- David Cuny
|
Not Categorized, Please Help
|
|
