A Gentle Introduction to Genetic Algorithms

By:

Noman Islam

Introduction

• A genetic algorithm is a search technique used to find true or approximate solutions to optimization and search problems
• Were formally introduced in the US in the 1970s by John Holland at University of Michigan

Introduction – continued

• Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination)

Introduction – continued

• Genetic algorithms are implemented as a computer simulation in which a population of abstract representations of candidate solutions to an optimization problem evolves toward better solutions

Introduction – continued

• The evolution usually starts from a population of randomly generated individuals(candidates) and happens in generations.
• In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly mutated) to form a new population. The new population is then used in the next iteration of the algorithm.

​

A Simple Genetic Algorithm

{

initialize population;

evaluate population;

while TerminationCriteriaNotSatisfied

{

select parents for reproduction;

perform recombination and mutation;

evaluate population;

}

}

​

Initialization of parent population

• Generate the M number of solution string known as parent population
• Mostly random

Evaluation

• Give fitness to each of the solution

Selection

• Fit solution are likely to survive and bad solution are likely to die off
• Select some of the best fit chromosomes from parent population according some selection criteria (eg. Roulette wheel selection)

Crossover/Recombination

• Exchange partial solution between pair of selected solution with some probability value eg 70%

Child Population After Crossover

Mutation

• Change the value of an allele of solution with some small probability value eg 1%
• Motivation is to explore new point in the solution space

Child Population After mutation

Replace with parent population and repeat process

• Evaluate child population and replace parent population
• Go to selection step and repeat the process until termination criteria satisfies
• Eg. Exit after given number of iteration finishes

1

2

4

6

fitness

x² example: selection

f(x) = {MAX(x²): 0 <= x <= 32 }

X² example: crossover

X² example: mutation

How GA are Different than Traditional Search Methods?

• GAs work with a coding of the parameter set, not the parameters themselves.
• GAs search from a population of points, not a single point.
• GAs use payoff information, not derivatives or auxiliary knowldege.
• GAs use probablistic transition rules, not deterministic rules.

Advantages of GA

• Very simple
• Performs well on many different types of problems
• Less susceptible to getting 'stuck' at local optima than gradient search methods.

​

Conclusion

• When to use GA?
• Alternate solutions are too slow or overly complicated
• Problem is similar to one that has already been successfully solved by using a GA
• Benefits of the GA technology meet key problem requirements
• GAs are in used in Machine Learning, Robotics, Signal Processing etc.

​

Further Readings

• Books:
• Genetic Algorithms in Search, Optimization, and Machine Learning by David E. Goldberg
• Websites:
• Applet, http://www.rennard.org/alife/english/gavintrgb.html
• http://www.wikipedia.com

​