Genetic Algorithms
Evolutionary algorithms have been around since the early sixties. They apply the rules of nature: evolution through selection of the fittest individuals, the individuals representing solutions to a mathematical problem. Genetic algorithms are so far generally the best and most robust kind of evolutionary algorithms. They were invented by John Holland and presented in his book "Adaption in Natural and Artificial Systems" from 1975.
What makes a GA special?
What are the trademarks of a genetic algorithm (GA)? A GA is heuristic, which means it estimates a solution. You won't know if you get the exact solution, but that may be a minor concern. In fact, most real-life problems are like that: you estimate a solution rather than calculating it exactly.
For most problems you don't have any formula for solving the problem because it is too complex, or if you do, it just takes too long to calculate the solution exactly. An example could be space optimization - it is very difficult to find the best way to put objects of varying size into a room so they take as little space as possible. The most feasible approach then is to use a heuristic method.
Genetic algorithms are different from other heuristic methods in several ways. The most important difference is that a GA works on a population of possible solutions, while other heuristic methods use a single solution in their iterations. Another difference is that GAs are probabilistic (stochastic), not deterministic.
Each individual in the GA population represents a possible solution to the problem. The suggested solution is coded into the "genes" of the individual. One individual might have these genes: "1100101011", another has these: "0101110001" (just examples). The values (0 or 1) and their position in the "gene string" tells the genetic algorithm what solution the individual represents.
Here comes the clever part: you apply the rules of evolution to the individuals. You find the individuals you think are the best suggestions to your problem and then combine these individuals into new individuals. Using this method repeatedly, the population will hopefully evolve good solutions. Specifically, the elements of a GA are: selection (according to some measure of fitness), cross-over (a method of reproduction, "mating" the individuals into new individuals), and mutation (adding a bit of random noise to the off-spring, changing their "genes"). As you can see, Darwin's principles have been a major inspiration to GAs.
What makes a GA "genetic"?
The algorithm must have these elements to be "genetic":
- A mathematical representation for the solutions. This is a string of values.
A value in a certain position has a special meaning (just like our genes do). Keeping the
space optimization problem in mind, we could have a string representing how to position
3 boxes in x,y,z coordinates. For simplicity, each coordinate is represented by a
decimal number, so position 1 tells us the x coordinate of box 1, position 2 is the
y coordinate of box 1, and position 3 is the z coordinate of box 1. Position 4 would then
be the x coordinate of box 2, etc.
It could look something like this (the 9 digit string is the "gene string"
representing a specific solution):
- A method of creating the initial population. You determine how many individuals you want. If you have an idea of the best solution you can initialize the individuals accordingly. However, most of the time you are probably better off by simply starting with random values.
- A method for measuring the fitness. You have to have a measure of fitness in order to select the best individuals. In this example the obvious measure is how much free space the proposed solution will offer. The more free space, the better the solution is.
- Genetic functions. These are the selection, cross-over, and mutation methods mentioned before. I will explain them below; for now it is enough to say that they recombine existing individuals into new individuals, representing new solutions.
- A number of parameters. You have to determine in advance the size of the population, the number of parents to select, the mutation rate, etc.
This flowchart illustrates the basic steps in a GA:
The genetic operations of a GA
Here's how the genetic operations of the GA work:
The selection chooses the fittest individuals. You will need a method to calculate this fitness. Let's use the space optimization example. The fitness method simply calculates the amount of free space each individual/solution offers. The best are selected for further iteration.
The cross-over is the method for combining those selected individuals into new individuals. Remember that the individuals are simply strings of values. The cross-over splits up the "parent" individuals and recombines them. Here's an example of how two "parents" cross over to make two "children":
The mutation simply adds some noise to "genes" of the individuals (usually the "children"). It is a way of varying the "gene pool" to provide some protection against "in-breeding."
Note that the methods mentioned are just one way of making the GA work. There are many different methods of selection (how many parents to select? Kill the parents after cross-over? How to measure the fitness? etc.), many methods of cross-over (number of cross-over points, how to reassemble cross-over parts), and many methods of mutation (random noise, swapping values, no mutation, who to mutate, etc.).
The choice of methods will depend on the nature of the problem and your personal preferences.
Advantages and disadvantages of GAs
A GA has a number of advantages. It can quickly scan a vast solution set. Bad proposals do not effect the end solution negatively as they are simply discarded. The inductive nature of the GA means that it doesn't have to know any rules of the problem - it works by its own internal rules. This is very useful for complex or loosely defined problems.
GAs have drawbacks too, of course. While the great advantage of GAs is the fact that they find a solution through evolution, this is also the biggest disadvantage. Evolution is inductive; in nature life does not evolve towards a good solution - it evolves away from bad circumstances. This can cause a species to evolve into an evolutionary dead end. Likewise, GAs risk finding a suboptimal solution.
Consider this example: a GA must find the highest point in a landscape. The algorithm will favor solutions that lie on a peak (a hill or whatever). As the individuals gradually begin to propose solutions in the same vicinity (somewhere on the peak), they begin to look alike. In the end you may have individuals that are almost identical. The best of these suggest the top of the peak as the solution. But what if there is another, higher peak at the other end of our map? It is too hard for the individuals to venture away from their current peak. The ones that do will be eliminated, because their solution is worse than the ones we have. An individual might get "lucky", but that would mean its "genes" are very different from the rest of the population, so this is unlikely. In other words, the algorithm produces a suboptimal solution - and we may not even know it.
For more on GAs, see the page on classifier systems.
For an example program using a GA, go to my Delphi page and download the Travelling Salesman program (for Windows).