I’ve been tempted to write-up a small Genetic Algorithm tutorial for some time now, but the concepts involved, and even the coding is so simple and intuitive, and there are so many good guides out there that it simply didn’t make sense to repeat what others have said so well. So what I decided to do, was to solve a simple problem with a GA, in a format that doesn’t require you to fire up your development environments, but allows you to have a close look at the code itself. Excel and VBA are a perfect combination for this purpose.

First, here are a couple of good GA tutorials:

1. Mark Obitko offers a nice tutorial on GA’s (and other machine Soft Computing methodologies).
2. AI-Junkie offers another tutorial written for beginners, along with a nice example. [http://www.ai-junkie.com/ga/intro/gat1.html]

Now you should be prepared to check out the “Hello World” program

What are we simulating?

You enter a string as a parameter in the control sheet of the Excel workbook. This will be your Goal. The genetic algorithm doesn’t know much about the string. It constantly polls the fitness function with a bunch of “bred” strings, which will return a value that shows how closely the proposed string matches the Target String (e.g. “Hello World”). The algorithm uses these fitness values to refine its search.

I complicated the search space a bit, by setting up a “Phonetic Distance” sheet. Here, consonants and vowels that sound similar have a lower distance (e.g. 1 or 2) and those that sound completely different have higher distances set (up to 5). You are welcome to change the table and see how it works out! The fitness function actually returns the summed “distance” of the word the GA proposes, to the target word by looking up every position in this table. This turns our problem into a more “real world” application and gives the search surface a more interesting shape.

The goal of the GA, is to match the Target String that you input. You can judge its performance, based on the “Best match seen” string in the control sheet.

How does it work?

You can download the excel sheet here. It contains VBA macros, so you need to enable those. In Excel (I use Office 2003, but it should work on Office 2007)  you will need to go to Tools->Macros->Security and set the security level to medium or low. You might need to restart excel using this setting and reload the sheet. I have scanned the sheet with a few anti-virus programs (Avira, AVG, Kaspersky), but you are welcome to take further precautions, by scanning the sheet before running it.

Once you open the workbook, you get the “Control” Sheet. Enter a target string that you want the algorithm to achieve (the target string is the goal) in the first field under “Parameter Value”. You can set the population size, mutation rate, crossover rate and the number of generations to run the GA in the same (shaded) column.

Then you need to click the “Initialize Random Population” so those parameters are read, and an initial population of random strings is set up. Then you can choose to either “Simulate for N Generations” or “Simulate 1 Generation”. In the first case, the algorithm will run the number of times you set in the parameters. In the second case, it will do a crossover and mutation on the current population, and report the results, then stop.

The best match to the target string can be also seen on this page, and it updates if the best individual string in the current population beats the previous best match in terms of fitness. At any time, when the simulation is not running, you can go to the “Results” sheet and have a look at the current population, and the best matches in previous populations.

Do not forget that pressing Alt+F11 enables you to see the VBA code. It’s by no means clean code, but it’s simple enough to understand or tweak. It isn’t optimized either, so if you have a slow machine, avoid simulating large populations for thousands of generations. In addition, try tweaking the Mutation and crossover rates, and let me know if you get some great values that make the algorithm converge fast. Have fun with it.