Genetic Algorithms: A Quick Introduction

Genetic Algorithms can be used to search for solutions to problems, if we can model the solution components, and the characteristics of a good solution. They are based on the principles which govern evolution. Strong individuals in the population reproduce, passing on blended characteristics which make the next generation stronger. Sometimes mutation occurs, creating a new characteristic which may make the individual even more successful in a novel way.

To solve problems using this method, we need to express them in a model in which the solution components are represented as genes. Different combinations of solution components result in solutions of varying success. We also need a way of measuring if we have found a good solution or not. We call this function for evaluating the possible solutions the fitness function.

Step-wise description of the algorithm:

(taken from Artificial Intelligence: A New Synthesis by Nils Nilsson)

1. Start with a set of random genes, generation 0, and test them all for fitness.

2. Use the old generation to make a new generation. Choose the 10% most fit by tournament selection and transfer them directly.

3. From the remaining population, choose parent pairs using the fitness function and cross these to make new individuals.

4. Repeat until maximum iterations are complete.

In this way, the population becomes fitter and fitter according to our fitness function and we develop an individual that does what we would like.

Genetic Algorithm Diagram

This diagram illustrates the concept behind genetic algorithms

Pro’s and Cons

(taken from Applied Evolutionary Algorithms in Java by R. Ghanea-Hercock)

Pro’s:

  • Allows finding a solution to problems without performing exhaustive search
  • Less complicated way of problem solving, not requiring much analysis
  • Works intuitively

Cons:

  • Can be hard to work out how to model your problem
  • The algorithm can get stuck in a non-optimal solution

Well that rounds up this feature on Genetic Algorithms and sets the stage for future posts on how this algorithm can be used in testing and other interesting applications.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s