Genetic Algorithms crossover and mutation with basic algorithm steps

Crossover Probability (Pc)

•Crossover probability is a parameter to describe how often crossover will be performed. The probability varies from 0 to 1.

•It is the ratio of the number of pairs to be crossed to some fixed population.

•Typically for a population size of 30 to 200, cross over probability will be 0.5 to 1

Mutation

•After crossover, the strings are subjected to mutation.

•Mutation prevents the algorithm to be trapped in a local minimum.

•If crossover is supposed to exploit the current solution to find better ones, mutation is supposed to help for the exploration of the whole search space. 

•Mutation is viewed as a background operator to maintain genetic diversity in the population.

•It introduces new genetic structures in the population by randomly modifying some of its building blocks.

•For binary representation, a simple mutation can consist in inverting the value of each gene with a small probability.

•The probability is usually taken about 1/L, where L is the length of the chromosome

•Typically the simple GA uses the mutation rates varying from 0.001 to 0.5

Example:

1010010

        ↓

1010110

•  Mutation is also used to maintain diversity in the population.

•Example

0110 1011

0011 1101

0001 0110

0111 1100

• All four strings have 0 in the left most bit position, if true optimum solution requires 1 in that place, then we need mutation operator

Search Termination (Convergence Criteria)

In short, the various stopping condition are listed as follows:

• Maximum generations–The genetic algorithm stops when the specified number of generation’s have evolved.

• Elapsed time–The genetic process will end when a specified time has elapsed.

   Note: If the maximum number of generation has been reached before the specified time has elapsed, the process will end

No change in fitness–The genetic process will end if there is no change to the population’s best fitness for a specified number of generations.

Note: If the maximum number of generation has been reached before the specified number of generation with no changes has been reached, the process will end.

• Stall generations–The algorithm stops if there is no improvement in the objective function for a sequence of consecutive generations of length Stall generations.

Basic Algorithm

Step1: Choose a coding to represent problem parameters, a selection operator, a            crossover operator and a mutation operator.

•Choose population size, crossover probability, and mutation probability.

•Initialize a random population of string size L.

•Choose a maximum allowable generation number tmax. Set t=0

Step 2: Evaluate each string in the population

Step3: If t>tmax or other termination criteria is satisfied, Terminate.

Step 4: Perform reproduction on the population

Step 5: Perform crossover on random pairs of strings

Step 6: Perform mutation

Step 7: Evaluate strings in the new population. Set t=t+1 and go to step3