Transcript Genetic Algorithms

CSE 6111 Advanced Algorithm Design and Analysis
Genetic Algorithms
Przemyslaw Pawluk
03-12-2007
03-12-2007
Agenda
•
•
•
•
The overview of the genetic idea
The structure of genetic algorithms
Where to use?
The genetic algorithm for Traveling
Salesman Problem
• Summary
2
The overview – definitions
• Genotype (genome) – population of abstract
representations of candidate solutions.
• Phenotype – the candidate solution.
• Fitness function – particular type of
objective function that quantifies the
optimality of the solution.
3
Generation, Selection, Modification
• The genetic algorithm usually starts from
randomly generated population.
• In each generation, the fitness of every individual
in the population is evaluated,
• Multiple individuals are stochastically selected
from the current population (based on their
fitness), and modified (recombined and possibly
randomly mutated) to form a new population.
• The new population is then used in the next
iteration of the algorithm.
4
Algorithm
Choose initial population
Evaluate the fitness of each individual in the population
Repeat until gen_no > max_gen_no or best <= 
<loop-inv: gen_no < max_gen_no and we have a set of
valid solutions and a best solution best that is not
necessarily optimal>
Select best-ranking individuals to reproduce
Breed new generation through crossover and mutation
(genetic operations) and give birth to offspring
(gen_no++)
Evaluate the individual fitnesses of the offspring (set
best)
Replace worst ranked part of population with offspring
5
Changes - Mutation, Crossover
• Mutation – the random change in the
chromosome.
i.e. Random change
Mutation
0
1
of some bits in the
representation
Crossover
• Crossover – two chromosomes change some
portion of information
6
Genotype representation
• Usually binary arrays (lists) are used, to
make the crossover operations easy
however other representation are also used.
7
Termination
• A solution is found that satisfies minimum criteria.
• Fixed number of generations reached.
• Allocated budget (computation time/money)
reached.
• The highest ranking solution's fitness is reaching
or has reached a plateau such that successive
iterations no longer produce better results.
• Manual inspection.
• Combinations of the above.
8
Applications of GA
• Designing neural networks, both
architecture and weights
• Robot trajectory
• Evolving LISP programs (genetic
programming)
• Strategy planning
• Finding shape of protein molecules
• TSP and sequence scheduling
• Functions for creating images
9
Traveling Salesman Problem
• Input – the set of cities (nodes) and the
distances between them.
• Output – the permutation of cities.
• Goal – to find the minimal Hamiltonian tour.
n-1
min
(dx x
i=1
dx x
i i+1
i
+ dx x
n 1
i+1
)
is a distance between xi and xi+1
10
Traveling Salesman Problem
• Permutation encoding used to encode
chromosomes.
• Each chromosome is a string of numbers,
which represents number of town in a entry
sequence.
Chromosome A
Chromosome B
1 5 3 2 6 4 7 9 8
8 5 6 7 2 3 1 4 9
11
TSP – crossover and mutation
• Mutation – take 2 arbitrary elements and
swap them
• Crossover
Chromosome A
Chromosome B
Offspring A
Offspring B
1
8
1
5
5
5
5
6
3
6
3
2
2
7
2
3
6
2
6
1
4
3
4
4
7 9 8
1 4 9
8 7 9
7 9 8
12
Traveling Salesman Problem
• Traveling salesman problem is NP-hard.
• The time to find the optimal solution is
exponential.
• Application of the GA can reduce the time
to polynomial, but do not guarantee that the
optimal solution will be found.
• Example: Genetic Algorithm for TSP.
13
Summary
• Improvements by crossing over
• Random mutation to avoid stucking in local
min/max
• Widely used
14
Questions
15