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
No comments:
Post a Comment