String guessing with Genetic Algorithms

String guessing with Genetic Algorithms

The goal is to identify a secret phrase by evolving initial random guesses.

This problem is similar to:

  • Hangman: you pass a letter sequence to the person who knows the target word and the only feedback you get is how many of your letters are correct
  • Mastermind / Bulls and Cows using only the white key pegs

and is related to the Dawkins' weasel thought experiment.

So it's a good starting point for experimenting with GAs.

The ingredients of a genetic algorithm are:

  • a population of individuals (aka chromosomes);
  • a fitness function;
  • the evolution strategy.

So let's see how to specify them in Ultra.

An individual encodes a possible solution, a fixed-length string of characters in a given char-set:

const std::string target = "Hello World";
const std::string CHARSET =
  " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!";

// ...

ga::problem prob(target.length(), {0, CHARSET.size()});

The size of population, as well as many other parameters, is controlled via the parameters structure (part of the ga::problem class). 300 individuals are more than enough:

prob.params.population.individuals = 300;

Last but not least the fitness function:

double fitness(const ultra::ga::individual &x)
{
  double found(0.0);

  for (std::size_t i(0); i < target.length(); ++i)
    if (target[i] == CHARSET[x[i]])
      ++found;

  return found;
}

It evaluates an individual (ga::individual) by calculating the number of matching characters (its fitness).

Now just start the evolution:

ga::search search(prob, fitness);
auto result(search.run().best_individual);

As you can see running the code, a small population can find, in a few generations, the correct solution.

The full source for this example is contained in the examples/string_guess.cc file.

Further readings: