Transcript PPT

Genetic Algorithms
What is a GA
Terms and definitions
Basic algorithm
What is a GA




Searches for good solutions among
possible solutions.
Uses evolutionary mechanisms including
natural selection, reproduction, mutation
The best possible solution may be missed
Useful in problems that are too big or too
difficult to solve with conventional
techniques.
2
Terms and definitions (1)


A solution is coded by a string , also called
chromosome. The words string and
chromosome are used interchangeably
A strings fitness is a measure of how good
a solution it codes. Fitness is calculated by
a fitness function.
3
Terms and definitions (2)

Selection: The procedure to choose parents

Roulette wheel selection is a way of picking out


a string from among a group of strings (a
population).
A wedge on a roulette wheel proportional to the
string's fitness.
A 'fit' string is more likely to be chosen than an
'unfit' string.
4
Terms and definitions (3)


Crossover is the procedure by which two
chromosomes mate to create a new offspring
chromosome
parent 1 is copied of up to a randomly chosen
point, and parent 2 is copied from that point
onwards.
Parent 1
Parent 2
Offspring1
Offspring2
1
0
1
0
0
1
0
1
0
1
0
1
|110
|100
100
110
5
Terms and definitions (4)


Mutation : with a certain probability flip a
bit in the offspring
Various ways to implement mutation,
optional.
6
Basic Genetic Algorithm
1.
2.
3.
4.
Start: Generate random population of n
chromosomes (suitable solutions for the
problem)
Fitness: Evaluate the fitness f(x) of each
chromosome x in the population
New population: Create a new population
by repeating following steps until the new
population is complete
Test: If the end condition is satisfied, stop,
and return the best solution in current
population
7
New population



Selection: Select two parent chromosomes from a
population according to their fitness (the better
fitness, the bigger chance to be selected)
Crossover: With a crossover probability cross over
the parents to form a new offspring (children). If no
crossover was performed, offspring is an exact copy
of parents.
Mutation: With a mutation probability mutate new
offspring at each locus (position in chromosome).
8
Termination Criteria



after a pre-specified number of
generations
when an individual solution reaches a
pre-specified level of fitness
when the variation of individuals from
one generation to the next reaches a
pre-specified level of stability, e.g. all
become equal
9
Issues to Address


How to represent an individual
How to choose

the fitness function

the selection method

the crossover method

the frequency of mutations
10
More on Selection





Roulette Wheel Selection: proportional to the
fitness
Rank Selection: rank is assigned based on
fitness, then choose proportional to the rank
Steady-State Selection: sort and always choose
the best
Elitism: copy the best individuals in the next
generation
Tournament selection
11
More on Crossover








Random point of split
Fixed point of split
Single point: split in two
Two points: split in three
Uniform: bits are chosen randomly
Arithmetic crossover: the offspring is a result of some
arithmetic operation
Two parents
Three parents
12
Applications


Optimization problems
Search in a pool of candidate
solutions
Tutorial:
http://cs.felk.cvut.cz/~xobitko/ga/
13