Genetic Algorithm:

Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics. As such they represent an intelligent exploitation of a random search used to solve optimization problems.

Although randomised, GAs are by no means random, instead they exploit historical information to direct the search into the region of better performance within the search space. The basic techniques of the GAs are designed to simulate processes in natural systems necessary for evolution, specially those follow the principles first laid down by Charles Darwin of "survival of the fittest.". Since in nature, competition among individuals for scanty resources results in the fittest individuals dominating over the weaker ones.

Algorithm:

After an initial population is randomly generated, the algorithm evolves the through three operators:

selection which equates to survival of the fittest;

crossover which represents mating between individuals;

mutation which introduces random modifications.

1. Selection Operator

key idea: give preference to better individuals, allowing them to pass on their genes to the next generation.

The goodness of each individual depends on its fitness.

Fitness may be determined by an objective function or by a subjective judgment.

2. Crossover Operator

Prime distinguished factor of GA from other optimization techniques

Two individuals are chosen from the population using the selection operator

A crossover site along the bit strings is randomly chosen

The values of the two strings are exchanged up to this point

If S1=000000 and s2=111111 and the crossover point is 2 then S1'=110000 and s2'=001111

The two new offspring created from this mating are put into the next generation of the population

By recombining portions of good individuals, this process is likely to create even better individuals

3. Mutation Operator

With some low probability, a portion of the new individuals will have some of their bits flipped.

Its purpose is to maintain diversity within the population and inhibit premature convergence.

Mutation alone induces a random walk through the search space

Mutation and selection (without crossover) create a parallel, noise-tolerant, hill-climbing algorithms

Effects of Genetic Operators

Using selection alone will tend to fill the population with copies of the best individual from the population

Using selection and crossover operators will tend to cause the algorithms to converge on a good but sub-optimal solution

Using mutation alone induces a random walk through the search space.

Using selection and mutation creates a parallel, noise-tolerant, hill climbing algorithm

The Algorithms

1. Randomly initialize population (t)

2. Determine fitness of population (t)

3. repeat

   i) Select parents from population (t)

   ii) Perform crossover on parents creating population (t+1)

   iii) Perform mutation of population (t+1)

   iv) Determine fitness of population (t+1)

4. until best individual is good enough