A General Description
A genetic algorithm is a way to "teach" your computer to solve problems that a human can't do by hand. It uses the principles of Darwin's Natural Selection, or "survival of the fittest" by simulating a population of organisms with "genomes" (sample solutions) and determining each genome's "fitness" by how close it is to solving the problem. Once the fitness of each genome is obtained, the algorithm mates them, making the best fit genomes most likely to mate. (See figure 1.0) Throw in a couple of other life-like variables and you can teach your population to learn things in astonishing time.

[Figure 1.0] The Basic Genetic Algorithm. The green boxes are sample genomes and the red tags are their fitness. The goal of the GA is to find the highest binary number with 3 bits.

Determining Fitness
So far, I have only discussed the basic algorithm itself and have not talked about how it relates to the given problem. Figuring out how good a solution is for your problem is the most important factor in the Genetic Algorithm. It requires the researcher to understand what kind of solution to look for, often without knowing the actual solution. That might sound like a contradiction - you need to know what your solution looks like without knowing the actual solution. In practice, however, there are tons of problems where you can mathematically determine the fitness of each genome. There is more discussion of this in the Strategy for Determining Fitness chapter.

Selection, Mating and Mutating
While determing fitness is directly concerned with the problem, mating and mutating is not; those operators are only related to the Genetic Algorithm itself. How mating and mutating is actually done will be left to the article on it, but I here will go over why they are needed.

The goal of mating is to take two genome parents and mate them to get a child which is similar to both parents. If that child is better than the parents, it should survive longer than them. If it's not better than the parents, it will probably be replaced by better child. Now there are two parts of the mating process: selecting which parents will mate, and actually mating them. The latter process is not very complicated, actually: it's literally mixing together parts of each parent. Selecting the parents can be done in a few different methods: The Roulette Wheel and Tournament are the main ones used. Also, Speciation might be imposed in selecting parents - this is where you put similar genomes with each other to create different niches of genomes. (Defining what solutions are "similar" to each other can be a difficult process depending on the problem you're solving.)

A Plethora of Parameters
Here is a basic list of parameters that one might find in a genetic algorithm. These have nothing to do with the problem itself, but are parameters for the GA. On the right are the traditional parameters, but they certainly aren't definitive.

*These often have their own set of parameter depending on which one you choose.

In addition, you need to consider how you design your fitness function, how you might want to visualize your final solution, as well as many other factors. Since it there are so many factors the programmer needs to consider, putting together a GA can be daunting at first. Sometimes you wonder if you have a bug in the operator, if you got the parameters wrong, or if the run didn't work very well by chance. All the balancing is worth it in the end when it works, though!

What makes these so fascinating?
The idea of solving problems in a microcomputer using the principles of of the animal kingdom is a cool idea in and of itself. Computers are typically ill-fit to simulate real life because there are so many minor details that the programmer must neglect. Natural Selection, however, seems to fit nicely into an algorithm because it is elegantly simple, yet it yields a lot of apparent creativity.

From a researcher's perspective, GA's are great because they are flexible. Usually, an algorithm is a tool designed for a specific problem and is no good for other problems - but not these algorithms. The main attraction of GAs is that they are one algorithm that solves many different problems. Finding the fastest path from town to town, climbing a mountain, playing Chess, and even driving a car can be all modeled by a GA. One downside is that they are difficult and often unwieldy to program since they can get complicated in the operators and parameters.

Stochastic vs. Deterministic
The unique difference that computer scientists see with these algorithms is that they are stochastic rather than deterministic. This means that the algorithm is based on probability instead of on a fixed set of rules. A Genetic Algorithm can potentially come up with a different solution every time it is run on the same problem. (In practice, however, this is not the case - the overlapping probabilities provide small amounts of variation in the solution, but the overall solution is generally the same for each given set of parameters.) A deterministic algorithm, which are the ones taught typically at the sophomore undergraduate level, will always give the same solution to the same problem (ie the algorithm "determines" the solution).

In my case, the stochastic aspect of Genetic Algorithms are a major part of their appeal. There is something mystical about creating a system and letting it solve the problem without your intervention. At an observational level, one could say that we are using "life" to solve problems. Actually, it's thousands of probabilities that interact with each other and eventually come up with a solution, but I'd like to think of it as creating nature on a computer.

Where do GA's fall short?
To me, GA's have been summed up the best by the author David B. Fogel. Imagine the Genetic Algorithm as a Swiss Army Knife. It can do anything for you, but there is no better substitute than the right tool. A hammer's claw may be the best tool for removing a nail from wood, and tweezers are best for removing a splinter, but a Swiss Army Knife will work for both. Not to mention that GAs are considerably slower than deterministic approaches.

Even though Genetic Algorithms don't provide the fastest approach to solving problems, they can present interesting ideas for solving problems. An expert in Genetic Algorithms can make a population look creative if the right parameters are set. Also, seeing how a GA solves a problem can lead the researcher to derive a new deterministic algorithm.

News | Research | Personal Profile | Photo Album
Contact Me