Genetic Algorithms

A Genetic Algorithm searches for the possible solutions to problems using mechanics of natural selection and genetics. The results obtained from using genetic algorithms can be either good, bad or infeasible so in order to get the best solution a fitness value is added to the solution. This evaluates the fitness or “suitability” of each chromosome that makes up the population. A chromosomes represent the solutions within the algorithm which are randomly created at the beginning of a run of a genetic algorithm. The genetic algorithm then selects chromosomes from a population and combines them to produce new "offspring" chromosomes. These offspring chromosomes form a new population (or replace some of the chromosomes in the existing population) in the hope that the new population will be better than the previous ones. The chromosome is then able to store the solution which it represents and this is called representation.

Genetic algorithms produce new chromosomes by combining existing chromosomes. This operation is called crossover. A crossover rate takes parts of solution encodings from two existing parent chromosomes and combines them into a single new chromosome. This operation depends on the chromosome representation, and can be very complicated. Below is an of the crossover operation.

Given two chromosomes

10001001110010010

01010001001000011

Choose a random bit along the length, say at position 9, and swap all the bits after that point

so the above become:

10001001101000011

01010001010010010

After a crossover operation is performed a mutation operation is started.This mutation created small changes to an encoded solution.these mutations and crossover depend on the type of representation that is selected.

Fitness operations and fitness comparators are also used to manipulate chromosomes. A fitness operation measures the quality of the chromosome which is produced so that the genetic algorithm is told what to optimize. Fitness comparators compare chromosomes based on their fitness and tells the genetic algorithm whether it should minimize or maximize the fitness values of chromosomes.

Another step performed by the genetic algorithm is the production of the new introduction of new chromosomes into a population. These new chromosomes can replace an entire population or just a few chromosomes in the population. The algorithm ends when the best solution has not changed for a preset number of generations.