Transcript ppt - Department of Computer Science

Effect of Spatial Locality on
An Evolutionary Algorithm
for Multimodal Optimization
EvoNum 2010
Ka-Chun Wong, Kwong-Sak Leung, and Man-Hon Wong
Department of Computer Science & Engineering
The Chinese University of Hong Kong, HKSAR, China
{kcwong, ksleung, mhwong}@cse.cuhk.edu.hk
1
Background
 Differential Evolution (DE)
• Proposed by Price and Storn in 1995
• Considered as one of the most powerful
evolutionary algorithms for real number function
optimization nowadays
• "Differential Evolution -- a simple and efficient adaptive scheme for
global optimization over continuous spaces, 1995”
2
Background

DE’s Main Idea: (DE/rand/1)
•
Generate trial vectors (v) using the following formula:
•
It elegantly replaces the two operations:


Crossover
Mutation
1. Less parameters to be tuned
2. Self-organizing ability
3
Background
http://ocw.mit.edu/NR/rdonlyres/Sloan-School-of-Management/15-099Fall2003/A40397B9-E8FB-4B45-A41B-D1F69218901F/0/ses2_storn_price.pdf
4
Motivation
 Given an optimization problem, traditional
optimization algorithms can be applied to
obtain a optimum.
 However, in the real world, we are often
interested in not only a single optimum, but
also other possible global and local optima.
5
Problem Definition
 Given a function, an algorithm should work
out all optimal points in a single run.
Six-hump Camel Back Function (http://www.it.lut.fi)
6
Previous works








AEGA (Leung et al. 2003)
SCGA (Li et al. 2002)
Crowding (Kenneth De Jong 1975)
Fitness Sharing (Goldberg et al. 1989)
CrowdingDE (R. Thomsen 2004)
SDE (Xiaodong Li 2005)
Repeated iterations (Beasley et al. 1993)
……
7
CrowdingDE
 Proposed by R. Thomsen in CEC2004
 Main Idea:
• Incorporate Crowding technique into Differential
Evolution (DE) for multimodal optimization
 An individual can only replace the most similar
individual
8
CrowdingDE
Crowding
(Crowding Factor = whole population)
9
Proposed Method
 CrowdingDE-L (CrowdingDE using Spatial Locality)
• Improve the accuracy
• A case study for incorporating “The Principle of
Locality” into CrowdingDE
^ Peter J. Denning The locality principle, 2005.
The story of the computing fundamental principle of locality of reference.
10
Proposed Method
 Observation:
• During a run, individuals around different optima
tend to exhibit different convergence rates.
• Close individuals (within the same niche) tend
to have similar:
 Step-size for improvement
• Crossover between them
is good
Individual
Optimum
11
Proposed Method

Apply spatial locality :
•
Given an parent individual, favor the close
individuals to be selected for trial vector
(offspring) generation
1. Transform the distances between the parent and
the candidate individuals to the proportion to be
selected.
2. Use the proportion to form a roulette-wheel to
select candidate individuals for trial vector
generation
12
Proposed Method
 Previous Idea:
• Randomly selects candidate individuals for trial
vector generation
 Proposed Idea:
• Apply spatial locality to select candidate
individuals for trial vector generation
13
Proposed Method

Apply spatial locality :
•
Given an parent individual, favor the close
individuals to be selected for trial vector
(offspring) generation
Individual
Optimum
14
Proposed Method
New
New
Old
15
Proposed Method
 Transformation functions
• Transform distance to proportion for selection
16
Experiments
 All algorithms were run up to maximum
40000 fitness function evaluations. The
performance measurements are obtained by
taking the average and standard deviation of
50 runs.
17
Experiments
 Performance measurements
18
Experiments
19
Experiments
20
Further Experiments
 We conducted further experiments on the
number of successful trial vector generation
• A successful trial vector generation is defined:
 The generation of a trial vector, which can replace an
individual in the parent population.
21
Further Experiments
 The proposed method (red colour) does improve
the selection of candidate individuals for trial
vector generation, comparing to the original
method (green colour)
22
Critical Thinking
 Pros:
• Simple and easy to implement
• Less parameters to be tuned
 Only one DE parameter needs to be set
 Cons:
• Computationally expensive
 Crowding Factor is set to the population size
• O(N^2)
23
Conclusion
 The experimental results should not be taken to mean that
the proposed method (CrowdingDE-L) is “better” than other
evolutionary algorithms tested for multimodal optimization.
Such a conclusion is oversimplified.
 However, it shows that the proposed method does improve
CrowdingDE for generating trial vectors.
• A case study for integrating locality principle into evolutionary
algorithm
• The numerical results can also be viewed as a valuable resource
for comparing the state-of-the-art algorithms for multimodal
optimization.
24
Future Works
 Temporal Locality
• With the success of spatial locality in this paper, other local
techniques involving the principle of locality could be further
explored and verified. For instances, besides space, temporal
locality can be integrated into evolutionary algorithms. Say,
individuals with the same age could be given higher priority for
crossovers. Mutation step size could also be linked to the previous
step sizes.
 Different distance metrics & transformation functions
• Different distance metrics could be adopted in calculating the
locality. For instances, although Euclidean distance is adopted in
this paper, it can be further generalized to p-norm distance (or
Minkowski distance).
25
Q&A
26