Transcript ppt - CSE, IIT Bombay

Memetic Algorithms
By
Anup Kulkarni(08305045)
Prashanth K(08305006)

Instructor: Prof. Pushpak Bhattacharyya
Overview

Philosophy Behind Memetics
Genetic Algorithm – Intuition and Structure
Genetic Algorithm Operators
Memetic Algorithms

TSP Using Memetic Algorithm



Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
2
Genes and biological evolution


A gene is a unit of biological information
transferred from one generation to another.
Genes determine our physical traits, what you
look like, what you inherit from either one of
your parents.
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
3
Biological
Evolution
• Natural Selection
• Survival of The Fittest
• Origin of New Species
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
4
Examples of Biological Evolution and
Natural Adaptation

Gills in Pisces

Frog Skin

Hollow Bones in Birds

Biological Evolution of Human
•
Characteristic Thumb
•
Erect Vertebral Column
•
Lower Jaw
Biological
Evolution
Cultural
Evolution..??
Source: www.wikipedia.org
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
6
Biological
Evolution
Meme..!!!
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
7
Meme

“the basic unit of cultural transmission, or
imitation”
- Richard Dawkins

“an element of culture that may be considered
to be passed on by non-genetic means”
- English Oxford Dictionary
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
8
Examples of Meme

Fashion


Science


Scientists sharing their thoughts
Literature


Latest trends are ideas of fashion designers
Novel, poetry
Music

Even birds are found to imitate songs of other birds!!!
Genes and Memes, where they are similar



Genes propagate biologically from chromosome
to chromosome
Memes propagate from brain to brain via
imitation
Survival of fittest in meme

Concept of God is survived though no scientific
evidence is present
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
10
Genes and Memes, where they differ



Genes are pre-decided
Genes are static through generations, memes
can be changed!
Memes allow improvement
After learning language, we contribute to it through
literature
 New heuristics to 8-puzzle problem solved in class
 We use this property to improve genetic
algorithms

Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
11
Genetic Algorithm


solves (typically optimization) problems by
combining features of complete solutions to
create new populations of solutions.
applicable when it is hard or unreasonable to try
to completely identify a subproblem hierarchical
structure or to approach the problem via an
exact approach.
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
12
Genetic Algorithm
Initialize population Pop
Evaluate Pop
While not
stop criterion do
Select Parents from Pop
Recombine Parents
Evaluate Pop
Return the best solution in Pop
Crossover


Purpose: to combine
features of feasible
solutions already visited
in order to provide new
potential candidate
solutions with better
objective function value.
Mechanism that restarts
the search by “exploring”
the space “between”
solutions.
parents
offspring
0000000
0001111
1111111
1110000
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
14
Mutation
■
Purpose: to introduce
new characteristics in
the population by
random
before
modifications.
after
■
Explores the
“neighborhood” of a
solution.
1 1 1 1 1 1 1
1 1 1 0 1 1 1
mutated gene value
Memetic Algorithm
Initialize population Pop
Optimize Pop(Local search)
Evaluate Pop
While not
stop criterion do
Select Parents from Pop
Recombine Parents
Optimize Pop(Local search)
Evaluate Pop
Return the best solution in Pop
Solving the Traveling salesman
problem with a Memetic Algorithm
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
17
Memetic Algo for TSP-representation





Array pop stores population
Size of pop=P
No of cities=N
Tour represented as 1234....N
Fitness function-cost of the tour
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
18
TSP - Crossover

Distance Preserving Crossover

d(p1,p2) = d(p1,child) = d(p2,child)

d(x, y) = #edges not common in x and y
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
19
Distance Preserving Crossover
Source: B. Freisleben et al, “New Genetic Local Search Operators for the Traveling
Salesman Problem”
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
20
2-OPT Search


Delete any two edges
Insert other two edges which will result in new
1
1
tour
6
2
3
2
6
3
5
5
4
4
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
21
Memetic Algorithm
Initialize population Pop
Optimize Pop(Local search)
Evaluate Pop
While not
stop criterion do
Select Parents from Pop
Recombine Parents
Optimize Pop(Local search)
Evaluate Pop
Return the best solution in Pop
Performance
Source: Slides of A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing
Hybridisation with other techniques: Memetic Algorithms
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
23
Conclusion




A genetic algorithm promises convergence
but not optimality.
But we are assured of exponential
convergence, possibly at different optimal
chromosomes.
Do very well in identifying the regions where
those optima lie.
Optimal solution=Genetic Algo + Local
Search
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
24
References

R. Dawkins, “The Selfish Gene – new edition”, Oxford
University Press, 1989 pp 189-201

David E. Goldberg, Genetic Algorithms in Search, Optimization and
Machine Learning, 1st edition, Addison-Wesley Longman Publishing
Co., 1989 pp 170-174

B. Freisleben and P. Merz, New Genetic Local Search Operators for
the Traveling Salesman Problem. In H.-M. Voigt, W. Ebeling, I.
Rechenberg, and H.-P. Schwefel, editors, Proceedings of the 4th
Conference on Parallel Problem Solving from Nature - PPSN IV,
pages 890--900. Springer, 1996

S. Lin and B. W. Kemighan, An effective heuristic algorithm for the
Traveling Salesman problem, Operation Research 21 (1973) 498516
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
25
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
26
Thank you!
Anup Kulkarni and Prashanth K, Dept of
CSE, IIT Bombay
27