Transcript S07-present

An Analysis of
Edge Assembly Crossover
for the Traveling Salesman Problem
Yuichi Nagata and Shigenobu Kobayashi
IEEE, Conference on Evolutionary Computation, 1999
Genetic Algorithm
Holland, 1975 Imitation of Evolution of life form in the Nature
individuals - members of species - in the nature
model of evolution processes
where the basic operations are natural selection, crossover and mutation
Schema Theorem - analysis of reproduction model
Nothing to do with the real genetic organism
Problem Solving
Polynomial time function
y = ax2 + b
• Given constant a, b, know x, calculate y
• Find x that gives Maximum y in a given range of x
No Calculation  Search for the Solution
Search Space
•
•
•
•
For small space, use classical exhaustive techniques
For larger space, need special techniques
Analysis of space
Global Optima vs Local Optima
Stochastic
Search
Local Search Techniques
Adaptive Search Techniques
Random search
Ant Colony
Simulated Annealing
Neural Network
search space
Standard Genetic Algorithm
Step 0: Initialization
Procedure GA
begin
t := 0 ;
initialize P(t) ;
evaluate P(t) ;
while (not termination-condition) do
begin
t := t + 1
;
select P(t) from P(t-1) ;
alter P(t) ;
evaluate P(t) ;
end
end
Step 1: Selection
Step 2 : Crossover
Step 3 : Mutation
Step 4: Evaluation
Step 5 : Termination
Test
Step6: End
GAs: Terminology
Step 0: Initialization
–
–
–
–
–
–
Representation : gene, chromosome, Population
Evaluation : objective function, fitness function
Selection
Operator : crossover, mutation
Replacement : new Generation
Termination : Generation count, Convergence
Step 1: Selection
Step 2 : Crossover
Step 3 : Mutation
Step 4: Evaluation
Step 5 : Termination
Test
Step6: End
Representation
• Very crucial step
• representation should satisfy the presumption that the whole
chromosome is decomposable to building blocks
• String of genes of given alphabet:
– Binary
– Float
– Integer
• More complex representation
– matrices
– rules
– trees
Initialization of
the Starting Population
• Aspects affecting a performance of GA
– schemata sampled in the initial population
• Initialization mechanisms
– random
– informed - uses prior knowledge of the desired solution shape
• Pre-processing
– runs several short pre-processing runs
– samples the promising areas of the search space identified
during the foregone pre-processing runs
Selection
• Models nature’s survival-of-the-fittest principle
• Selection strategies:
– Roulette wheel (proportionate)
– Ranking
– Tournament
• Selection process:
– determination of Expected values: EVi = fitnessi / fitnessavg
– sampling algorithm - conversion of EVi to the actual number of
individuals
Roulette Wheel Selection
Crossover
• Provides random information exchange works on couples of individuals
• Simple 1-point crossover
Mutation
• Mutation - preserves population diversity
– works on single individual
Replacement Strategy
• Replacement strategy defines:
– how big portion of the old population will be replaced in
each generation of the new population, and
– the rule that determines which individuals from the old
population will be replaced and which individuals will be
placed in the new population
• Generational - the old population is entirely rebuilt in each
generation (short-lived species)
• Steady-state - just a few individuals are replaced in each
generation (longer-lived species)
Premature Convergence
• The ratio of the best-fit individual’s reproduction rate to
the average reproduction rate is too high
• selection kills ‘worse’ individuals too early
Theory
of
GAs
Schema Theorem
 (S )


 ( S , t  1)   ( S , t )  eval( S , t ) / F (t ) 1  pc
 o( s )  pm 
m 1


• Schema = Pattern
• Schema Theorem
– Short, low-order, above-average schemata
– receive exponentially increasing trials in subsequent generations
of a genetic algorithm
• Building Block Hypothesis
– GA seeks near-optimal performance through short, low-order,
high-performance schemata
• Schema In binary representation - 2L strings, 3L schemata
L = 7, S = (**0*1*1) - covers 24 strings
– {0,1, *}
– S = {*1*01***, 1*0*11*0, 10111011, *******1, ****0*** }
• Fitness of a schema - average fitness computed over all covered
strings
• Schema property
– order o(S )
• the length of string minus the number of *
• defining the specialty of a schema
• 8 bits : 11010011, schema and building block 1*010*1*
– defining length  (S )
• the distance between the first and the last fixed string positions
• defining the compactness of information contained in a schema
• (*11**1*0) = 6, (1******1) = 7
Selection
• eval(S,t) is the average fitness of all strings in the
population matched by the schema S at time t ;
eval( S , t )   j 1 eval(v j ) / p
p
• Expecting to have
 ( S , t  1)
strings matched by schema S
 ( S , t  1)   ( S , t ) | p(t ) | eval( S , t ) / F (t )
– the average fitness of the population F (t )  F (t ) / | p(t ) |
– becomes ;  ( S , t  1)   ( S , t )  eval( S , t ) / F (t )
Crossover
– the string is matched by these two schemata
S 0  (* * * *111* * * * * * * * * * * * * * * * * * * * * * * * * *)
S1  (111* * * * * * * * * * * * * * * * * * * * * * * * * * * *10)
survives
va  (111011111010001000110000001000110) ,
vb  (000101000010010101001010111111011)
va  (111011111010001000111010111111011) ,
vb  (000101000010010101000000001000110)
destroyed
– the probability of destruction of a schema S :
pd ( S ) 
 (S )
m 1
(S) = 7, m = 8 ?
– the probability of survival of a schema S :
ps ( S )  1 
 (S )
m 1
 (S )


 ( S , t  1)   ( S , t )  eval( S , t ) / F (t ) 1  pc
 o( s )  pm 
m 1


• Selective probability of crossover pc
p s ( S )  1  pc
 (S )
m 1
• The combined effect of selection and crossover
• a new schema growth equation :
 (S ) 

 ( S , t  1)   ( S , t )  eval( S , t ) / F (t ) 1  pc
m  1

Mutation
• All of the fixed positions of a schema must remain
unchanged to survive mutation
va  (111011101101110000100011111011110)
• mutate at least one of these bits would destroy the
schema
• the probability of destruction of a schema S :
o( s )  p m
• the probability of survival of a schema S :
1  o(s)  pm
 (S )


 ( S , t  1)   ( S , t )  eval( S , t ) / F (t ) 1  pc
 o( s )  pm 
m 1


TSP
with
GA
Path representation
(5 1 7 8 9 4 6 2 3)  5-1-7-8-9-4-6-2-3
• Crossover operators
Node Orientation vs Edge Orientation
• Mutation operators
–insertion
 5-2-1-7-8-9-4-6-2-3
–Reciprocal Exchange  5-9-7-8-1-4-6-2-3
–Inversion  5-9-8-7-1-4-6-2-3
Information of the parents transferred to offsprings
Node crossover = simple but information discarded
Edge crossover = tough but information enclosed
TSP: Edge-Recombination
Operator
a-b-c-d-e
b-d-e-c-a
b-c-e-a-d
Edge Assembly Crossover
Edge Assembly Crossover
Previous work
Exx crossover
Ex crossover
Test Library
EXX
Crossover
EX
Crossover
EXX
Crossover
att532