Evolving Strings
A demo of evolutionary computing
This week's star is the mongoose
Another entry in the "cute carnivore" series, we have the mongoose. Some mongooses are fairly smart and can learn simple tricks. They can be kept as pets to control vermin. (Your landlord will love you.) Mongooses giggle when mating. (I haven't tried that myself but I suspect it wouldn't go over so well.) One of their coolest features is that they are immune to snake neurotoxins because they have acetylcholine receptors! I guess that's why mongooses are sometimes used to hunt or fight venomous snakes.
This is a little demo of a genetic algorithm that evolves a pool of random strings to match one chosen by the user by using basic evolutionary rules. This is heavily inspired by descriptions and the rules themselves from the book The Computational Beauty of Nature, by Gary W. Flake.
Basically, it starts with a population of randomized strings of equal length. Each of the strings is compared to the target string and the number of correct letters is used as a "fitness" score. The "fittest" 25% of the population is then allowed to "mate" (75% chance). Mating involves randomly choosing a cut position in the strings, and swapping the left half of one with the right half of the other. Mutation then occurs in 1% of the population, with up to 5 letters being randomly changed. All other strings pass unchanged into the new population.
The simulation stops when one of the evolved strings matches the target string. On my laptop (Celeron 700Mhz), evolving a typical ~30 character string takes under 2 seconds and ~150 generations. The longest string I've evolved was the complete poem Trees by Joyce Kilmer. It took just under an hour, and over 26,000 generations.
Source code of the ga_str simulation is available in the downloads area for personal, non-commercial, and educational uses.