Thursday, 12 December 2013

Genetic Algorithms

Genetic Algorithm DNA
Genetic algorithms are possibly the most beautiful and yet easy to understand algorithms in the field of machine learning. A genetic algorithm is a population and generation based global search scheme in which it tries to find near optimal solutions to user specified problems. The scheme has been adapted from Darwinian evolution as it is supposed to take place in natural ecosystems. 

The central idea in running of a genetic algorithm is that it would start off with a randomly selected population of candidate solutions to a problem. Let us call each one of the members of such a population as an individual. Although the individual may also be called as a genome, member or a candidate solution depending upon the jargon.The algorithm checks each of the individuals for its suitability to solve the given problem and assigns it a rank accordingly. Just as it is expected to happen in Darwinian natural selection, the individuals that have better ranks are supposed to stand better chances at giving rise to progeny. To this end, the algorithm iteratively selects individuals from the population according to their ranks and creates new offspring accordingly. Offspring is created by applying genetic operators. Normally these are crossover and mutation. When the desired number of offspring individuals are produced the algorithm starts over again in evaluating the individuals of the newly formed population and ranking them and so on. This process of creating, evaluating and ranking newer populations keeps on going until the desired solution to the problem at hand is found. The algorithm stops at this stage. Following is a pseudo-code of a typical genetic algorithm:

  1. Create an initial population of individuals of size n.
  2. Evaluate each individual on the given problem and assign it a rank R.
  3. Randomly choose pairs of individuals as some function of R.
  4. Apply genetic operators of crossover and mutation on the chosen individuals to form a pair of offspring.
  5. Repeat step 4 until a new population is formed. 
  6. Go to step 2 and keep repeating till this point until the desired solution is found.
Genetic algorithms are very strong in their ability for solving intricate problems. 

Creative Commons LicensePsyops by PsyopsPrime is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Based on a work at
Permissions beyond the scope of this license may be available at
Micah’s DNA by micahb37, on Flickr
Creative Commons Attribution-Share Alike 2.0 Generic License  by  micahb37 

No comments:

Post a Comment