Genetic Algorithms

Genetic algorithms are a method of computing that relies on biological models to evolve solutions (if you're reading this, Dr. Koza, don't have a heart attack based on my loose definitions). Nature is great at evolution, and genetic algorithms try to capture some of the essence of natural selection and genetic evolution in computer models to help solve problems that normally couldn't be solved by standard means of computing.

Basically, genetic algorithms work like this: You take a number of informational indicators and string them all together into a bit vector, just like a strand of DNA, as shown in Figure 12.33.

This bit vector represents the strategy or coding of an algorithm or solution. You need a few of these bit vectors to start with. Then you process the bit string and whatever it represents by some objective function that scores its fitness. The results are its score. The bit vector is really a concatenation of various control variables or settings for some algorithm, and you manually come up with a few experimental sets of values to start with based on intuition or prior knowledge (if available). Then you run each set and you get the score of each. You may find that out of the five you created manually, two of them did really well and the other three did really poorly. Here's where the genetic algorithm comes in.

You could tweak the solution from there, knowing that you're on the right track, or you could let genetic algorithms do it for you. Mix the two solutions or control vectors together to create two new offspring, as shown in Figure 12.34.

To add a little bit of uncertainty, during the crossover process you flip a bit here and there to simulate mutation. Try your new solutions, along with the last generation's best solutions, and see what happens with the scores. Pick the best results out of this generation and do it again. This is the process of genetic evolution. Amazingly, the best possible solution will slowly evolve, and the result might be something you never imagined.

The key things about genetic algorithms are that they try new ideas (patterns) and they can search a very large search space that normally couldn't be searched if you went one by one. This is due to mutation, which represents completely random evolutionary events that may or may not lead to better adaptation.

So how do you use this in a game? There are millions of ways, but I'm going to give you just one to get you started. You can use the probability settings of your AI as the genetic source for digital DNA, and then take the creatures in your game that have survived the longest and merge and evolve their probabilities, thus giving the best traits to future generations. Of course, you would only do this when you needed to spawn a new creature, but you get the idea.