Genetic Algorithms

What is a Genetic Algorithm?

Genetic Algorithms are one of a number of Artificial Intelligence tools used for search and optimization problems.  Genetic Algorithms are unique as they are based on the genetic processes of biological organisms.  In nature, organisms that are well adapted to their environment survive while those that are poorly adapted do not.  Over a series of generations, organisms become better and better adapted to their environment.  This has also been called “survival of the fittest.”  Genetic Algorithms use an abstraction of this process to “evolve” solutions to real-world problems.

Instead of a population of organisms, a Genetic Algorithm uses a population of potential solutions.  This population is then “evolved” for a number of generations.  Each generation is composed of three steps: 

• Measure the performance of the potential solutions. 

• Determine the solutions that survive and those that do not based on their performance generated in the previous step, 

• Create new potential solutions by modifying the current population.  Generally, a new solution can be created by either making a change to a single solution or by “cross breeding” two (or more) solutions. 

In each generation, the higher performing solutions produce “offspring” containing the good characteristics of their “parents”.  These good characteristics accumulate with good characteristics from other “parents”.  Over a number of generations, these changes steadily improve the performance of the population.   

This process of simulated evolution provides significant benefits: 

• Genetic Algorithms can be applied to a number of different problems successfully.  While Genetic Algorithms are not guaranteed to find the optimum solution to a particular problem, they are very good at finding acceptable solutions within an acceptable amount of time.  Hybrids of Genetic Algorithms and problem-specific algorithms have also produced good results.  
• The evolution process of Genetic Algorithms requires no human supervision.  Thus Genetic Algorithms are free from human biases.  Many Genetic Algorithm solutions are significantly different than anything seen before.  

Where have Genetic Algorithms been applied? 

Genetic Algorithms have been applied to a number of difficult optimization problems. Specific examples include the design of gas turbines, scheduling assembly lines, design of fiber-optic networks and finding the best investment plans.  They have also been used to aid other Artificial Intelligence techniques such as training Neural Networks and finding the best rules for Expert Systems. 

When are Genetic Algorithms used? 

Genetic Algorithms are generally used for problems containing little or no information on how to generate better solutions.  Problems that are appropriate for Genetic Algorithms also share the following characteristics: 

• The number of possible solutions to the problem is very large. 

• There are few heuristics or “rules of thumb” for generating good solutions. 

• Analyzing good solutions provides little information on how to generate better solutions. 

• The performance of a solution can change over time.  

How do Genetic Algorithms compare to other Artificial Intelligence techniques? 

Searching is a large component of many Artificial Intelligence techniques.  These techniques are categorized on a scale from weak to strong.  Weak search techniques contain no knowledge about the problem they are attempting to solve.  Conversely, strong search techniques contain a significant amount of knowledge concerning the problem they are attempting to solve.  

As weak search methods contain little problem-specific information they are able to solve different problems with very few changes.  The price of this generality, however, is inefficiency.  Weak search methods solve problems by testing large numbers of possible solutions.   

Conversely, strong search methods contain much more information about the problem they are designed to solve.  The search is customized to a particular problem area, allowing strong search methods to solve problems much faster than weak search methods.  However, this information is only applicable to one problem area and must be renewed for each new problem area. 

Genetic Algorithms fall between weak and strong search methods.  They can contain as little or as much information about the problem area as desired.  Usually, Genetic Algorithms contain very little problem specific information. However, for highly complex problems, more problem specific information can be added.  

The power of Genetic Algorithms is based on two synergistic principles; exploring multiple solutions at the same time and building better solutions from good ones.  Exploring multiple solutions allows information to be gathered that might otherwise be missed.  Good characteristics from these diverse areas can then be combined to form improved solutions. 

What is required to build a Genetic Algorithm? 

To use a Genetic Algorithm to solve a particular problem, three basic issues need to be addressed: 

• Some method of distinguishing between good solutions and poor solutions must be found.  This is called the evaluation function.  This function should be easy to calculate as thousands of solutions may need to be evaluated to determine the optimum solution. 

• A representation for the problem must be found.  This representation should allow small changes as well as some method of interchanging information between two potential solutions. 

• An issue related to the representation is the creation of a set of operators to make changes to potential solutions.  Most implementations of Genetic Algorithms use two operators based on processes found in nature.  These operators are called mutation and crossover.  Mutation is a simple one-point change in the genetic structure of an organism.  Crossover simulates sexual reproduction by taking two (or more) solutions and exchanging a portion of their structure after a randomly determined split point.   

The success of a Genetic Algorithm depends greatly on the interaction of the representation and the operators. The best representation of a problem allows genetic operators to be created that can change the structure of potential solutions without destroying any information that is currently there.  This emphasis on finding appropriate representations and operators is one of the biggest differences between Genetic Algorithms and most other Artificial Intelligence techniques. 

What is the conclusion? 

Genetic Algorithms are a method of optimization that is very successful in a number of complex problem areas.  Some of these areas are design, optimization, and control. The benefits of Genetic Algorithms include the ability to be used in a number of different problem areas, improvement without human supervision, and the ability to use potentially unreliable data.