Home arrow Development Cycles arrow Page 3 - Genetic Algorithm Techniques

Genetic Algorithm Techniques

As a continuation to our algorithm design patterns multi-part article series, right now you are reading the Genetic Algorithm techniques segment. Genetic algorithms are important because they are used for global optimizations. In a nutshell, they pick the best solution from lots of possibilities. They are fast, requiring very few system resources, and their implementations are also quick.

Author Info:
By: Barzan "Tony" Antal
Rating: 5 stars5 stars5 stars5 stars5 stars / 11
October 07, 2008
  1. · Genetic Algorithm Techniques
  2. · The Theory
  3. · The Theory, Continued
  4. · Concluding Thoughts

print this article

Genetic Algorithm Techniques - The Theory, Continued
(Page 3 of 4 )

Mutation is interesting. It is required after each crossover recombination because it prevents the solutions from converging towards local optima/extreme. In a nutshell, mutation changes a few bits of the resulting binary strings (the offspring chromosome right after the crossover was applied). Check out the following example.

Child #1: 1101000

Child #2: 1010111


Mutated #1: 1001010

Mutated #2: 1011111

From the above you can see that mutation occurs randomly. You should be careful because mutation must occur (thus, its probability cannot be 0%) otherwise you'd fall towards the local extreme. But it cannot happen to all bits either, because that means each of the bits becomes inverted, thus no mutation in fact happens because practically inversion happens instead. Don't abuse  mutation!

The final concepts we need to talk about are the fitness function and the selection function. The fitness assignment in short means that a scalar value will relate to the fitness of each chromosome from the population. The more fit a chromosome is, chances are the more it can contribute towards the best solution (better candidate). This is again problem-dependent. But the fitness function checks the quality of the chromosomes.

Selection can happen based on many theories. Often the so-called "Roulette wheel" is used but there are alternatives. It works like this: fitness of the entire population is represented on a "roulette wheel" (pie chart), and every chromosome gets a slice -- the more fit the chromosome, the bigger the slice it receives. Now the chromosomes are "picked" randomly by spinning the wheel. As you can see, the chances are you will pick from the bigger slices given to the fitter chromosomes.

Another selection technique that we must introduce is called elitism. It also derives from evolutionary biology. In short, it means that the best chromosome survives. Here's how this applies: we make at least one copy of the best chromosome(s) and do our best to propagate them towards further population generations.

The importance of elitism is explained in the following: convergence is guaranteed. Why? Well, let's assume a global optimum is found. This will be yielded from the best individuals (candidates), meaning that thanks to elitism, further solutions will also converge to the aforementioned optimum. But be careful! The probability of conversion to any local optima is also higher due to the exact same characteristics.

Nonetheless, there are many more selection schemes. Let's name a few others: rank selection (each chromosome receives a rank based on its fitness), tournament selection (within each sub-set of candidates each chromosome "races" other chromosomes, but only one can win, meaning it earns selection), hierarchical selection, stochastic remainder sampling, generation selection, scaling selection, and so forth. Each has its benefits.

As an implementation example please check out the pseudo code algorithm below.

Procedure Genetic_algorithm()

Initialize_population P;

Fitness_evaluate P;

While NOT solution do

P' = Selection P;

Crossover P';

Mutate P';

Fitness_evaluate P';

P = Selection between P and P';

End while

End procedure

blog comments powered by Disqus

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


Popular Web Development Topics
All Web Development Tutorials