Sex in C++

Posted on May 02, 2008 by Steve

Some time ago I was clicking around Wikipedia's content on artificial intelligence and encountered the article on genetic algorithms, and decided I would use one to solve a Project Euler problem. The first task was to find a suitable problem. To be amenible to a genetic algorithm, the problem should have certain characteristics:

  • It must be possible to rate candidate solutions, with the correct solution getting the highest possible score, and incorrect candidates scoring higher if they are somehow closer to the solution. (Most AI problems, like analyzing chess positions, do not have a single correct answer, so the highest-scoring candidate found in a certain time would be the result.)

  • A candidate solution should be expressable as a series of values, something like a chromosome. It helps if all candidates have the same length and format, so the individual parts are easily interchangeable.

Read on for specific information about my algorithm for Problem #61, including spoilers if you're inclined to try this approach yourself.