At the forefront of Artificial Intelligence

Home » Articles » Genetic Algorithms » Beginner

A "Hello World!" Genetic Algorithm Example

Somebody over on the Generation5 forum asked for a "Hello World!" program for genetic algorithms. I took it literally and created a very simple program (138 lines of code) that evolves the phrase "Hello world!"

Here is some sample output (best population member and the fitness are displayed):

Best: IQQte=Ygqem# (152)
Best: Crmt`!qrya+6 (148)
Best: 8ufxp+Rigfm* (140)
Best: b`hpf"woljh[ (120)
Best: b`hpf"woljh4 (81)
Best: b`hpf"woljh" (63)
Best: Kdoit!wnsk_! (24)
Best: Kdoit!wnsk_! (24)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Ifknm!vkrlf? (17)
Best: Ifknm!vkrlf? (17)
Best: Gfnio!wnskd$ (14)
Best: Ffnjo!wnskd$ (14)
Best: Hflio!wnskd$ (11)
Best: Hflio!wnskd$ (11)
Best: Kflkn wosld" (8)
Best: Ifmmo workd" (6)
Best: Hfljo wosld" (5)
Best: Hflmo workd" (4)
Best: Hflmo workd" (4)
Best: Hflmo workd" (4)
Best: Iflmo world! (3)
Best: Iflmo world! (3)
Best: Hflmo world! (2)
Best: Hflmo world! (2)
Best: Hflko world! (2)
Best: Hflko world! (2)
Best: Hdllo world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Helko world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Hello world! (0)

Genetic Algorithm

The GA has the following characteristics:

Population Size: 2048

Mutation (%): 25

Elitism (%): 10

There are a few things to note about the code as well. Firstly, we cheat slightly by fixing the size of the strings in the GA population to be the same size as the target string. This just makes the code easier to understand. Secondly, the STL container class vector is used to hold the GA details - this also makes the sorting very efficient as simple to implement. Finally, the program uses two arrays to hold the population - one for the current population, and another as the buffer to contain the next generation. At the end of each generation, the pointers are swapped round to keep things fast.

Fitness Function

Finally, a quick look at the fitness function:

void calc_fitness(ga_vector &population)
{
  string target = GA_TARGET;
  int tsize = target.size();
  unsigned int fitness;

  for (int i=0; i<GA_POPSIZE; i++) {
    fitness = 0;
    for (int j=0; j<tsize; j++) {
      fitness += abs(int(population[i].str[j] - target[j]));
    }
	
    population[i].fitness = fitness;
  }
}

Basically, all this does it go through each member of the population and compare it with the target string. It adds up the differences between the characters and uses the cumulative sum as the fitness value (therefore, the lower the value, the better).

Conclusion

Hopefully this little program serves as a decent look at how simple a GA can be to implement for a searching problem. This GA isn't the most efficient, although the use of the STL does help. Hopefully the code is ANSI compatible, although I've only tested it on Visual C++ 6.0.

gahelloworld.cpp

Submitted: 27/07/2003

Article Toolbar

BibTeX entry