Ward Systems Group Logo - Artificial Intelligence, Genetic Algorithm and Neural Network Software   

Genetic Algorithms and What They Can Do For You

How Does a Genetic Algorithm Work?
A genetic algorithm solves optimization problems by creating a population or group of possible solutions to the problem. The individuals in this population will carry chromosomes that are the values of variables of the problem.

The genetic algorithm actually solves your problem by allowing the less fit individuals in the population to die (peacefully) and selectively breeding the most fit individuals (the ones that solve the problem best). This process is called selection, as in selection of the fittest. The genetic algorithm will take two fit individuals and mate them (a process called crossover). The offspring of the mated pair will receive some of the characteristics of the mother, and some of the father.

In nature, offspring often have some slight abnormalities, called mutations. Usually these mutations are disabling and inhibit the ability of the children to survive, but once in a while they improve the fitness of the individual (like toes stuck together in a web-like fashion). The genetic algorithm similarly occasionally causes mutations in its populations by randomly changing the value of a variable.

After the genetic algorithm mates fit individuals and mutates some, the population undergoes a generation change. The population will then consist of offspring plus a few of the older individuals, which the genetic algorithm allows to survive to the next generation because they are the most fit in the population, and we will want to keep them breeding. These most fit individuals are called elite individuals.

After dozens or even hundreds of "generations", a population eventually emerges wherein the individuals will solve the problem very well. In fact, the most fit (elite) individual will be an optimum or close to optimum solution.

The processes of selection, crossover, and mutation are called genetic operators.

There are many opportunities for optimization in the business world today. Some of the best known are optimizing schedules and work flow to minimize cost and time, while maximizing output.

Some of the oldest types of optimizers use simple "exhaustive search", meaning that every possible combination is tried to see what is the best one. This is a very accurate approach, since you are bound to find the best combination of variables - eventually. However, it is a very inefficient approach, because whenever there are more than a few thousand combinations, it takes too long to try them all. That is why users of exhaustive search optimizers tend to limit the number of variables they use, or tend to limit the number of values these variables can take.

The genetic algorithm, by contrast, does not try every possible combination. It attempts instead to intelligently get closer and closer to the best solution. Therefore, far more variables can be utilized, and you can allow all values of a variable. Optimization can still take a good deal of time if you give a GA a fair number of variables, but it will be doing  much more work in that amount of time.

 More efficient optimizers than exhaustive search optimizers are in use.  If they are not genetic algorithms, however, they are most likely only searching one section of the search space at a time. Genetic algorithms are searching dozens or hundreds of parts of the search space simultaneously. This means they are less likely to become stuck in "local minima" as the others quite often do. (Local minima are decent solutions that the optimizer can never get out of in order to find better solutions.)

There are yet other types of optimizers in use today that use Newtonian search techniques. While these are very fast, the biggest drawback they have is that they require the search space to be continuous or differentiable. Genetic algorithms impose no restrictions on the space they search.

 

 

Ward Systems Group, Inc.
Executive Park West
5 Hillcrest Drive
Frederick, MD 21703

Email: sales@wardsystems.com
support@wardsystems.com
Copyright 1997-2007 Ward Systems Group, Inc. All rights reserved.
Copyright Information
| Privacy Statement