Home arrow Development Cycles arrow Page 2 - Genetic Algorithm Techniques
DEVELOPMENT CYCLES

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
TABLE OF CONTENTS:
  1. · Genetic Algorithm Techniques
  2. · The Theory
  3. · The Theory, Continued
  4. · Concluding Thoughts

print this article
SEARCH DEVARTICLES

Genetic Algorithm Techniques - The Theory
(Page 2 of 4 )

First, let's take a look at the necessary parts of a genetic algorithm. The most obvious one is the set of solutions that are built by chromosomes. Technically, this is what we call population. We also need a set of interesting functions, but we'll talk about those a bit later on. Now check out the following basic outline of a GA in a step-by-step approach:

1. Generate randomly the population of n chromosomes.

2. Using the fitness function, evaluate the condition of each chromosome.

3. Create the new population based on the following steps:

    a.) Select two of the most fit chromosomes as parents (criteria=their fitness)

    b.) Apply crossover recombination to generate new children.

    c.) Apply mutation on the latter two children.

    d.) Evaluate the condition of the mutated offspring. If good-accept them.

4. Replace the former population with the newly created one.

5. Verify the end conditions; if they are met, return the best solution.

6. Otherwise, go back and loop from step 2.

As you can see, we need functions and methods that generate the population, evaluate the fitness state of each chromosome, then recombine (crossover) and mutate the chromosomes, ultimately verify the end conditions, and replace, if necessary.

The crossover recombination and mutation are the most important operations of the algorithm. But first we need to understand how we "encode" the set of solutions of the problem into chromosomes. This part really depends on the problem. Basically, each chromosome is a binary string, containing bits. Each bit can be either 1 or 0, and they should "encode" some sort of characteristic. Here's an example of this.

Chromosome #1: 1100111

Chromosome #2: 1011000

Now that we have two sample chromosomes, let's apply crossover. It's important to realize that crossover recombination works on the basis of a "|" called the "crossover point." This point is used as a reference, and its position can be chosen randomly. This is why you can also gain different results by positioning the point differently. 

Chromosome #1: 110|0111

Chromosome #2: 101|1000

=========================

Child #1: 110|1000

Child #2: 101|0111

As you can see from the above example, we have chosen the position of the crossover point right after the first three digits. It could be at any other place as long as the string can be divided into two distinct segments. Crossover basically means that the first offspring contains the first half of the parent chromosome, while the end is taken from the second parent. Just the opposite is true for the second offspring. And that's it. 

Additionally, you can choose more than one crossover point. However, in that case, the recombination becomes quite complex and might even increase the complexity of the problem; additionally, more resources may be required. Picking the number of crossover points is problem-dependent. Choose wisely.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- 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 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials