Genetic Algorithm Techniques
(Page 1 of 4 )
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.
In this article series we have already covered some of the most remarkable design patterns in the world of algorithms: backtracking, divide-and-conquer, greedy, dynamic programming, and branch-and-bound. By now you should know the differences and have a clear overview of each technique along with their benefits and drawbacks.
As I already mentioned, genetic algorithms are usually pretty fast. Programming a genetic algorithm is routine most of the time; thus, implementing requires very little time, so it's cheap. Yet these tiny little algorithms always find the global optimum. However, the most important drawback of genetic algorithms (GA) is that mathematically there is no validity proof of the solution whatsoever. It doesn't always converge.
By definition, a genetic algorithm is a searching technique because it does nothing but search for the exact or appropriate (as specified within the implementation) solution from lots of possibilities. Therefore, such algorithms are used frequently in search problems and optimizations. They are part of the global search heuristic branch of mathematics.
Before we move on to presenting the basic theory of GAs we need to understand the name. Genetic algorithms are a sub-class of evolutionary algorithms because they use the exact same strategies derived from evolutionary biology. Now what exactly is evolutionary biology? That science discusses species, descents of species, and the like.
How can an algorithm design use evolutionary techniques? It's simple. Genetic algorithms rely on specific functions that are practically based on inheritance, mutation, selection, and crossover (which is genetic recombination). Genetic algorithms work with individuals from a population (chromosomes). The entire algorithm works a la evolution where the "most fit" species in the end will be the local optima or global optimum.
By now I am sure that you can imagine genetic algorithms already. That means we are ready to move on and present the main part of a genetic algorithm. Later on, we will also present a few examples to give you an overview of the entire technique, presenting the problem accompanied by the solution. Ultimately, coding GAs isn't hard; it's pretty much routine. You just need to grasp its concepts.
Next: The Theory >>
More Development Cycles Articles
More By Barzan "Tony" Antal
