Transcript Selection and Recombination

Selection and
Recombination
Temi avanzati di Intelligenza Artificiale - Lecture 4
Prof. Vincenzo Cutello
Department of Mathematics and Computer Science
University of Catania
Selection and Recombination

1. Review of the previous lecture





(a) How a simple evolutionary algorithm works
(b) Some crossover and mutation operators
2. Selection and reproduction
3. Recombination
4. A sample algorithm
Selection and Recombination - Lecture 4
2
Selection and Reproduction






Selection is not normally regarded as a search operator
although it does in search significantly.
Selection can be used either before or after search operators.
When selection is used before search operators, the process of
choosing the next generation from the union of all parents and
offspring is sometimes called reproduction.
The generational gap of an EA refers to the overlap (i.e.,
individuals that did not go through any search operators)
between the old and new generations.
The two extremes are generational EAs and steady-state
EAs.
Elitism = copying the best individual to the next generation.
Selection and Recombination - Lecture 4
3
Fitness Proportional Selection




Also known as roulette wheel selection.
Use raw fitness in computing selection probabilities.
Does not allow negative fitness values.
Weakness: Domination of super individuals in early
generations and slow convergence in later
generations.
Fitness scaling has often been used in early days to
combat the two problems.
Selection and Recombination - Lecture 4
4
Fitness Scaling

Simple scaling



The ith individual's fitness is defined as:
f scaled (t) = f original (t) - f worst (t);
where t is the generation number and f worst (t) the fitness of the worst
individual so far.
Sigma scaling

The ith individual's fitness is defined as:
 f original (t )  ( f * (t )  c f (t )), if f scaled (t )  0
f scaled (t )  
0,
otherwise


where c is a constant, e.g., 2, f*(t) is the average fitness in the current
population, and f (t) is the standard deviation of the fitness in the current
population.
Selection and Recombination - Lecture 4
5

Power scaling

The ith individual's fitness is defined as:
fscaled(t) = (foriginal(t)) k
where k > 0.

Exponential scaling

The ith individual's fitness is defined as:
fscaled (t) = exp( foriginal (t)/T )
where T > 0 is the temperature, approaching zero.
Selection and Recombination - Lecture 4
6
Ranking

Linear ranking

Assume that the population size is , rank 0 indicates the worst individual and
rank -1 the best. The probability of selecting the ith individual is:
Plinear (i) 

  [rank(i) /(  1)](   )

Where  () indicates the expected number of offspring produced by the
worst (best) individuals. Note that:  1
P
i 0


linear
(i )  1
Hence  + = 2. So 1  2 and  = 2- .
Power ranking

C below is a normalising factor. 0<  < .
Ppower (i) 
  [rank(i) /(  1)]k (    )
C
Selection and Recombination - Lecture 4
7

Geometric ranking:
Pgeom (i ) 

 (1   )  1 rank (i )
C
Exponential ranking:
1  e  rank (i )
Pexp (i ) 
C

Xin Yao ranking:
PXinYao (i ) 
i 1
 1
 ( j  1)
j 0
Selection and Recombination - Lecture 4
8
Recombination for Real-valued
Representation

Discrete Recombination


does not change actual (gene) values. Very similar to the
crossover operators on binary strings.
Intermediate Recombination

does change actual (gene) values. Usually based on some
kind of average/mixture among multiple parents.
Selection and Recombination - Lecture 4
9
Discrete Recombination

Multi-point Recombination


Global Discrete Recombination


Similar to that for the binary representation.
Similar to uniform crossover for the binary
representation.
Geometric explanation.
Selection and Recombination - Lecture 4
10
Intermediate Recombination

With two parents

Given x1 and x2:
xi  x1i  (1   ) x2i ,  [0,1]

With more parents

Given x1 and x2:
xi  1x1i   2 x2i  ...
where

i
1
i
Selection and Recombination - Lecture 4
11
Other Recombination

Heuristic Recombination

Assume x2 is no worse than x1:
x   ( x2  x1 )  x2
where u is a uniformly distributed random number in [0,1].

Simplex Recombination

Randomly select a group (> 2) of parents. Assume x1 is the best individual and
x2 the worst in the group. Compute the centroid, c, of the group without x2 .
x  c  (c  x2 )

Geometric Recombination

Can be generalised to multiple parents.
x  ( x11 x21 , x12 x22 ,...)
Selection and Recombination - Lecture 4
12
Quadratic Recombination

Let xij be the j-th component of the vectors xi, i 1,2,3, j
1,…,n, where n is the dimensionality. We approximate
the position of P4 using the quadratic interpolation method as
follow.
x4, j

2
2
2
2
2
2
(
x

x
)
f
(
x
)

(
x

x
)
f
(
x
)

(
x

x
1 2, j 3, j
1
3, j
1, j
2
1, j
2, j ) f ( x3 )
 
2 ( x2, j  x3, j ) f ( x1 )  ( x3, j  x1, j ) f ( x2 )  ( x1, j  x2, j ) f ( x3 )
One offspring is generated from three parents.
Selection and Recombination - Lecture 4
13
What Does Quadratic Recombination Mean
Note that we are minimising “fitness” here
Selection and Recombination - Lecture 4
14
A Hybrid EA With Local Search



1. Initialize  individuals at random.
2. Perform local search from each individual.
3. REPEAT





(a) Generate 3 points P1 , P2 , P3 by global discrete recombination.
(b) Perform a quadratic approximation using P1 , P2 , P3 to produce a
point P4 .
(c) Perform a local search from P4 and update P4 with the search
result. (Sounds Lamarkian.)
(d) Place P1 , P2 , P3 , P4 into the population and do a ( + 4)
truncation selection.
4. UNTIL termination criteria are met.
Selection and Recombination - Lecture 4
15
Local Search With Random Memorising



Store best solutions in a memory.
Retrieve a random one (old best) when a new best solution is
found.
Search along the direction of oldnew, i.e., the direction of:
xnew  xold
s :
xnew  xold
Selection and Recombination - Lecture 4
16
Experimental Studies




18 multimodal benchmark functions.
Population size 30
Maximum function evaluation 500,000.
50 independent runs for each function.
Selection and Recombination - Lecture 4
17
Benchmark Functions (f8 - f25 )
Selection and Recombination - Lecture 4
18
Results on f8-f13
Selection and Recombination - Lecture 4
19
Results on f8-f13 with population size 50 and 60
Selection and Recombination - Lecture 4
20
Results on f14-f25
Selection and Recombination - Lecture 4
21
Results on f16-f23 with population size 10
Selection and Recombination - Lecture 4
22
Summary



Different problems require different search
operators and selection schemes. There is no
universally best one.
Using real vectors is usually more appropriate
than binary strings for function optimisation.
Many search operators are heuristics-based.
Domain knowledge can often be incorporated
into search operators and representation.
Selection and Recombination - Lecture 4
23
References


T. Bäck, D. B. Fogel, and Z. Michalewicz (eds.),
Handbook of Evolutionary Computation, IOP Publ.
Co. & Oxford University Press, 1997. Part C. (in the
School library)
K.-H. Liang, X. Yao and C. S. Newton, “Combining
landscape approximation and local search in global
optimization" Proc. of the 1999 Congress on
Evolutionary Computation, Vol. 2, IEEE Press,
Piscataway, NJ, USA, pp.1514-1520, July 1999.
Selection and Recombination - Lecture 4
24