A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.
2. Steps:
Encoding
Fitness Evaluation
Reproduction
Survivor Selection
3. Encoding:
Design alternative à individual (chromosome)
Single design choice à gene
Design objectives à fitness
Example: Problem
Schedule n jobs on m processors such that the maximum span is minimized.
Design Alternative: job i ( i=1,2,…n) is assigned to processor j (j=1,2,…,m)
Individual: A n-vector x such that xi = 1, …,or m
Design objective: minimize the maximal span
Fitness: the maximal span for each processor
4. Reproduction:
Reproduction operators
Crossover
Mutation
Crossover
Two parents produce two offspring
There is a chance that the chromosomes of the two parents are copied unmodified as offspring
There is a chance that the chromosomes of the two parents are randomly recombined (crossover) to form offspring
Generally the chance of crossover is between 0.6 and 1.0
Mutation
There is a chance that a gene of a child is changed randomly
Generally the chance of mutation is low (e.g. 0.001)
5. Reproduction Operators:
Crossover
Generating offspring from two selected parents
Single point crossover
Two point crossover (Multi point crossover)
Uniform crossover
Randomly one position in the chromosomes is chosen
Child 1 is head of chromosome of parent 1 with tail of chromosome of parent 2
Child 2 is head of 2 with tail of 1
Single point crossover
Two point crossover (Multi point crossover)
One-point crossover - Nature
Two-point crossover
Uniform crossover
A random mask is generated
The mask determines which bits are copied from one parent and which from the other parent
Bit density in mask determines how much material is taken from the other parent (takeover parameter)
Is uniform crossover better than single crossover point?
Trade off between
Exploration: introduction of new combination of features
Exploitation: keep the good features in the existing solution
Depending on coding, simple crossovers can have high chance to produce illegal offspring
E.g. in TSP with simple binary or path coding, most offspring will be illegal because not all cities will be in the offspring and some cities will be there more than once
Uniform crossover can often be modified to avoid this problem
E.g. in TSP with simple path coding:
Where mask is 1, copy cities from one parent
Where mask is 0, choose the remaining cities in the order of the other parent
Mutation
Generating new offspring from single parent
Maintaining the diversity of the individuals
Crossover can only explore the combinations of the current gene pool
Mutation can "generate” new genes
Control Parameters: population size, crossover/mutation probability
Problem specific
Increase population size
Increase diversity and computation time for each generation
Increase crossover probability
Increase the opportunity for recombination but also disruption of good combination
Increase mutation probability
Closer to randomly search
Help to introduce new gene or reintroduce the lost gene
Varies The Population:
Usually using crossover operators to recombine the genes to generate the new population, then using mutation operators on the new population
