string_guessing_tutorial

String guessing with Genetic Algorithms

We want to guess a secret phrase by evolving a random set of initial guesses.

---

The problem is somewhat 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 Vita.

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!";

// ...

vita::ga_problem prob(target.length(), {0, CHARSET.size()});

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

prob.env.individuals = 300;

Last but not least the fitness function:

vita::fitness_t f(const vita::i_ga &x)
{
  double found(0);

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

  return {found};
}

It takes an individual (i_ga) and calculates the number of matching characters (its fitness).

Now just start the evolution:

vita::ga_search<decltype(f)> search(prob, f);
auto result = search.run();

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:

• the Hacker News discussion
• string guessing doesn't work (in Python)