Transcript Crossover

BCTCS 2005
Geometric Interpretation
of Crossover
Alberto Moraglio
[email protected]
Contents
I – Quick Preliminaries
II – Geometric Interpretation of Crossover
Extremely quick overview of its implications:
III – Unification of Major Representations
IV – Crossover Principled Design
V – Is Biological Recombination Geometric?
VI – Unity of Evolutionary Search
I. Quick Preliminaries
Evolutionary Algorithms…
• Are function optimizers
• Mimic biological evolution
• Are robust, hence preferred for real world
problems
• Have little theory to explain how and why
they work
• There are various flavours
Evolutionary Algorithm Template
Problem & representation independent
Standard representations & EAs
flavours/dialects
• Binary strings (genetic algorithms, the classic)
• Real code vectors (evolution strategies, continuous
optimization)
• Permutations (order-based GAs, combinatorial
optimization)
• Parse trees (genetic programming, evolution of computer
programs)
Algorithmically irrelevant differences:
name/authorship/solution interpretation/domain of
application
Algorithmically relevant differences:
solution representation/genetic operators
What is crossover?
100000011101000
100111100011100
100110011101000
100001100011100
Is there any
common
aspect ?
Crossover
Is it possible to give a
representationindependent definition
of crossover and
mutation?
Mutation & Crossover
for binary strings
• Mutation = bit flip at random position
101001  101101
• Crossover = selection crossover point at
random swap tails
1010|01  101000
1110|00  111001
1*10|0* 1*100*
• All offspring match the parent schema
II. Geometric Interpretation
of Crossover
Genetic operators & Neighbourhood
structure
• Forget the representation and consider the
neighbourhood structure (= search space
structure)
• Mutation: offspring are “close to” their
parent  in the direct neighbourhood
Direct Neighbour Mutation
100
000
?
Representation: Binary String
Move: Bit Flip
Neighbourhood: Hamming
001
110
010
101
111
Representation + Move =
Neighbourhood
011
Mutation: Offspring in the direct neighbourhood
What is crossover?
Neighbourhood and Crossover
Crossover idea: combining parents genotypes
to get children genotypes “somewhere in
between” them
Topologically speaking, “somewhere in
between” = somewhere on a shortest path
Why on a shortest path?
Shortest Path Crossover
011001
D0 : P1
010001
011101
011011
Parent1: 011101
Parent2: 010111
D1
010101
011111
Children: 01*1*1
010011
D2 : P2
010111
Children are on shortest paths
More than one shortest path in general
Interpretation & Generalization
• Traditional mutation & crossover have a
natural interpretation in the neighbourhood
structure in terms of closeness and
betweenness
• Given any representation plus a notion of
neighbourhood (move), mutation &
crossover operators are well-defined
From graphs to geometry
• Forget the neighbourhood structure and
consider the metric space (= space with a
notion of distance)
• The distance in the neighbourhood is the
length of the shortest path connecting two
solutions
• Mutation  Direct neighbourhood  Ball
• Crossover  All shortest paths  Line
Segment
Balls & Segments
In a metric space (S, d) the closed ball is the set of the form
B ( x; r )  { y  S | d ( x, y )  r}
where x belongs to S and r is a positive real number called the radius of the ball.
In a metric space (S, d) the line segment or closed interval is the set of the form
[ x; y ]  {z  S | d ( x, z )  d ( z, y )  d ( x, y )}
where x and y belong to S and are called extremes of the segment and identify the segment.
Squared balls & Chunky segments
Balls
100
000
101
001
111
110
3
3
011
010
3
3
B((3, 3); 1)
Euclidean space
B(000; 1)
Hamming space
B((3, 3); 1)
Manhattan space
Line segments
100
000
101
001
2
1
1
111
110
010
2
011
[000; 011] = [001; 010]
2 geodesics
Hamming space
1
3
[(1, 1); (3, 2)]
1 geodesic
Euclidean space
1
3
[(1, 1); (3, 2)] = [(1, 2); (3, 1)]
infinitely many geodesics
Manhattan space
Uniform Mutation &
Uniform Crossover
Uniform topological crossover:
fUX ( z | x, y )  Pr{UX  z | P1  x, P 2  y} 
 ( z  [ x, y ])
| [ x, y ] |
Im[UX ( x, y )]  {z  S | fUX ( z | x, y )  0}  [ x, y ]
Uniform topological ε-mutation:
fUM ( z | x )  Pr{UM  z | P  x} 
 ( z  B( x,  ))
| B( x,  ) |
Im[UM  ( x)]  {z  S | f M ( z | x)  0}  B( x,  )
Genetic operators have a geometric nature
Representation independent
and rigorous definition of
crossover and mutation in the
neighbourhood seen as a
geometric space…
This is cheating! I have
generalized from a single example
of solution representation!
III. Unification of Major
Representations & Operators
Minkowski spaces – real vectors
Balls
Representation: real vectors
Neighbourhoods: continuous (3 types)
2
2
2
Distances: Minkowski distances
2
2
2
B((2, 2); 1)
Euclidean space
B((2, 2); 1)
Chessboard space
B((2, 2); 1)
Manhattan space
Line segments
2
2
2
1
1
1
1
3
[(1, 1); (3, 2)]
1 geodesic
Euclidean space
1
3
[(1, 1); (3, 2)] = [(1, 2); (3, 1)]
infinitely many geodesics
Manhattan space
Implementation: algebraic manipulation
of real vector (equation of line passing
through two points)
Pre-existing recombination operators:
- both blend crossovers and discrete
crossovers fit geometric definition
- extended blend crossovers do not fit
1
3
[(1, 1); (3, 2)]
infinitely many geodesics
Chessboard space
Hamming spaces – binary strings
100
000
101
001
110
010
111
01
02
Representation: binary/multary strings
10
11
12
Neighbourhoods: bit-flip/site substitution
20
21
22
011
B(00;1)
Hamming space H(2,3)
B(000; 1)
Hamming space H(3,2)
100
000
101
00
01
02
10
11
12
20
21
22
001
111
110
010
00
011
[000; 011] = [001; 010]
2 geodesics
Hamming space H(3,2)
[00;11]=[01;10]
2 geodesics
Hamming space H(2,3)
Distances: Hamming distances
Implementation: symbolic manipulation of
multary strings (mask-based crossovers)
Pre-existing recombination operators:
- all binary crossovers fit the geometric
definition
Cayley spaces - permutations
Representation: permutations
abc
abc
abc
bac
acb
bac
cba
acb
bca
cab
acb
cab
bca
bac
cab
bca
cba
cba
B(abc; 1)
Adjacent swap space
B(abc; 1)
Swap space & Reversal
space
B(abc; 1)
Insertion space
abc
abc
abc
bac
acb
bac
cba
cab
bca
bca
acb
bca
cab
cab
cba
cba
[abc; bca]
1 geodesic
Adjacent swap space
bac
acb
[abc; bca]
3 geodesics
Swap space & Reversal
space
[abc; bca]
1 geodesic
Insertion space
Neighbourhoods: adj. swap, swap, reversal,
insertion
Distances: corresponding distances
Implementation: “minimal permutation
sorting by X move” algorithms:
- adj. swap = bubble sort
- swap = selection sort
- insertion = insertion sort
- reversal = approximated MPS by reversals
(NP-Hard))
Pre-existing recombination operators:
various pre-existing crossover operators are
sorting algorithm in disguise (because sorting
permutations is easier than sorting vectors of
other items)
Syntactic tree spaces
Parent 1
Representation: syntactic tree (lisp expression)
Parent 2
+
Neighbourhood: weighted sub-tree neighbourhood
*
sin
*
+
x
x
x
*
y
y
Distance: structural distance
x
*
y
Alignment
Crossover Point
Swap
y
Offspring 2
Offspring 1
*
+
x
+
*
*
sin
y
x
*
y
y
y
x
x
Implementation:
- sub-tree swap crossover
- common region mask based crossover
Pre-existing recombination operators:
- traditional crossover (non-geometric)
- homologous crossover
- the geometric framework can help to clarify what is
the landscape and distance related to homologous
crossover and a distance connected with a geometric
crossover which traditional crossover is an
approximation
Significance of Unification
• Most of the pre-existing crossover operators for
major representations fit geometric definition
• Established pre-existing operators have emerged
from experimental work done by generations of
practitioners over decades
• Geometric crossover compresses in a simple
formula an empirical phenomenon
IV. Crossover Principled
Design
Crossover Principled Design
• Domain specific solution representation is
effective
• Problem: for non-standard representations it is not
clear how crossover should look like
• But: given a combinatorial problem you may
know already a good neighbourhood structure
• Geometric Interpretation of Crossover  Give me
your neighbourhood definition and I give you a
crossover definition
Crossover Design Example
+
=?
Non-labelled graph neighbourhood
2
3
2
0
1
1
MOVE: Insert/remove
an edge
Fixed number of nodes
Offspring
+
V. Is Biological
Recombination Geometric?
Levenshtein spaces – sequences
Representation: multary sequences (DNA/amino
acids)
Parent1=AGCACACA
Parent2=ACACACTA
best inexact alignment (with
gaps):
AGCA|CAC-A  Child1=AGCACACTA
A-CA|CACTA  Child2=ACACACA
Neighbourhood: insertion + deletion + substitution
(compound edit move)
Distance: Levenshtein distance
Implementation: inexact sequence alignment
(dynamic programming) and sites exchange
(crossover mask)
Pre-existing recombination operators:
- none
- it could be a good crossover for linear GP
- it could be a better model of biological crossover to
study molecular evolution because it keeps into
account the inexact alignment due to molecular
annealing of DNA strands that produces
evolution of size variation
A simple model of (homologous)
biological recombination fits the
geometric definition under a DNA
distance used in bioinformatics
VI. Unity of Evolutionary
Search
Example of evolutionary search
Abstract convex evolutionary search
Main result: an evolutionary algorithm using
geometric crossover with any probability
distribution, any kind of representation, any
problem, any selection and replacement
mechanism, does the same search: convex search
Proof based on abstract convexity (axiomatic
geodesic convexity) and axiomatization of search
process (abstract search process)
…Nearly Over!
Future work
THEORY: Generalizing and accommodating
pre-existent theories into geometric framework
(schema theorem, fitness landscapes,
representation theories…)
PRACTICE: Testing crossover principled
design on important problems with nonstandard representation (problem domain
representation)
Questions?