Transcript Differential Evolution - Dr. Abdolreza Mirzaei

DIFFERENTIAL EVOLUTION
By Fakhroddin Noorbehbahani
1
EA course, Dr. Mirzaee
December, 2010
AGENDA

Preface

Basic Differential Evolution

Difference Vectors

Mutation

Crossover

Selection

General Differential Evolution Algorithm

Control Parameters

Geometrical Illustration

DE/x/y/z
2
AGENDA

Variations to Basic Differential Evolution

Hybrid Differential Evolution Strategies

Population-Based Differential Evolution

Self-Adaptive Differential Evolution

Differential Evolution for Discrete-Valued Problems

Constraint Handling Approaches

Comparison with other algorithms

Applications
3
PREFACE

Price and Storn in 1995 Chebychev Polynomial fitting
Problem

3rd place at the First International Contest on
evolutionary Computation (1stICEO) 1996, the best genetic
type of algorithm for solving the real-valued test function
suite.

stochastic, population-based search strategy

Main characteristics

Guide search with distance and direction information from the
current population

original DE strategies for continuous-valued landscapes
4
BASIC DIFFERENTIAL EVOLUTION



mutation is applied first to generate a trial vector,
which is then used within the crossover operator to
produce one offspring,
mutation step sizes are not sampled from a prior
known probability distribution function.
mutation step sizes are influenced by differences
between individuals of the current population
5
DIFFERENCE VECTORS

Position of individuals and fitness

Over time, as the search progresses, the distances between
individuals become smaller

The magnitude of the initial distances between individuals is
influenced by the size of the population

Distances between individuals are a very good indication of the
diversity of the current population

Use difference vector to determine the step size

total number of differential perturbations

nv is the number of differentials used

ns is the population size
6
MUTATION
7
CROSSOVER

Binomial crossover
Exponential crossover
8
SELECTION

Random Selection
To select the individuals from which difference vectors are
calculated.
 The target vector is either randomly selected or the best
individual is selected


Deterministic Selection


To construct the population for the next generation, the
offspring replaces the parent if the fitness of the offspring is
better than its parent; otherwise the parent survives to the
next generation.
This ensures that the average fitness of the population does
not deteriorate.
9
GENERAL DIFFERENTIAL EVOLUTION
ALGORITHM
10
11
CONTROL PARAMETERS

population size,ns

scale factor, β

probability of recombination,Pr
12
POPULATION SIZE

The size of the population has a direct influence
on the exploration ability of DE algorithms.

The more individuals there are in the population, the
more differential vectors are available, and the more
directions can be explored

The computational complexity per generation increases
with the size of the population.

Empirical studies provide the guideline that ns ≈ 10nx
13
SCALE FACTOR



The scaling factor, β ∈ (0,∞), controls the
amplification of the differential variations, (xi2−xi3 ).
The smaller the value of β, the smaller the mutation
step sizes

Smaller step sizes can be used to explore local areas.
slower convergence

Larger values for β facilitate exploration, but may cause the
algorithm to overshoot optima
As the population size increases, the scaling factor
should decrease.
14
RECOMBINATION PROBABILITY



This parameter controls the number of elements
of the parent, xi(t), that will change.
The higher the probability of recombination, the
more variation is introduced in the new
population, thereby increasing diversity and
increasing exploration.
Increasing pr often results in faster convergence,
while decreasing pr increases search robustness
15
GEOMETRICAL ILLUSTRATION
16
GEOMETRICAL ILLUSTRATION
17
GEOMETRICAL ILLUSTRATION
18
EXAMPLE:PEAK FUNCTION
19
GEOMETRICAL ILLUSTRATION

Generation 1: DE’s population and difference
vector distributions
20
GEOMETRICAL ILLUSTRATION

Generation 6: The population coalesces around
the two main minima
21
GEOMETRICAL ILLUSTRATION

Generation 12: The difference vector distribution
contains three main clouds – one for local
searches and two for moving between the two
main minima.
22
GEOMETRICAL ILLUSTRATION

Generation 16: The population is concentrated on
the main minimum
23
GEOMETRICAL ILLUSTRATION

Generation 20: Convergence is imminent. The
difference vectors automatically shorten for a
fine-grained, local search.
24
GEOMETRICAL ILLUSTRATION

Generation 26: The population has almost
converged.
25
GEOMETRICAL ILLUSTRATION

Generation 34: DE finds the global minimum.
26
DE/X/Y/Z

DE/best/1/z

DE/x/nv/z

DE/rand-to-best/nv/z
27
DE/X/Y/Z

DE/current-to-best/1+nv/z

DE/rand/1/bin vs. DE/current-to-best/2/bin



DE/rand/1/bin maintains good diversity
DE/current-to-best/2/bin shows good convergence
characteristics
Dynamically switch between these two strategies
28
VARIATIONS TO BASIC DIFFERENTIAL
EVOLUTION

Hybrid Differential Evolution Strategies

Gradient-Based Hybrid Differential Evolution
Acceleration operator : to improve convergence speed
 Migration operator : to improve ability for escaping local
optima


Acceleration operator


uses gradient descent to adjust the best individual toward
obtaining a better position if the mutation and crossover
operators failed to improve
x(t), replaces the worst individual in the new
population, C(t+1).
29
MIGRATION OPERATOR



Gradient decent speed up but local minima
Migration operator

increase population diversity

Generate new individual from best individuals
Applied when diversity is too small i.e.:
30
HYBRID DIFFERENTIAL EVOLUTION WITH
ACCELERATION AND MIGRATION
31
EVOLUTIONARY ALGORITHM-BASED
HYBRIDS


DE reproduction process as a crossover operator
in a simple GA
Rank-Based Crossover Operator for Differential
Evolution


To select individuals to calculate difference vectors
xi1 (t) precedes xi2 (t) if f(xi1(t)) > f(xi2(t)).
32
RANK-BASED MUTATION OPERATOR FOR
DIFFERENTIAL EVOLUTION
33
OTHER VARIATIONS TO BASIC DE

Population-Based Differential Evolution




Improve exploration by using 2 population set
Initialize with ns pairs
Rejected individual by selection put in auxiliary pop
Self-Adaptive Differential Evolution

Dynamic Parameters

Self-Adaptive Parameters
34
DIFFERENTIAL EVOLUTION FOR DISCRETEVALUED PROBLEMS

Angle Modulated DE

where x is a single element from a set of evenly separated
intervals determined by the required number of bits that
need to be generated
35
ANGLE MODULATED DIFFERENTIAL
EVOLUTION
36
BINARY DIFFERENTIAL EVOLUTION
37
CONSTRAINT HANDLING APPROACHES
Penalty methods
 Converting the constrained problem to an
unconstrained problem
 By changing the selection operator of DE,
infeasible solutions can be rejected




38
COMPARISON WITH GA AND PSO
39
COMPARISON
40
41
42
43
44
APPLICATIONS


















1) General Optimization Framework "Mystic" by Mike McKerns,
Caltech.
2) Multiprocessor synthesis.
3) Neural network learning.
4) Chrystallographic characterization.
5) Synthesis of modulators.
6) Heat transfer parameter estimation in a trickle bed reactor.
7) Scenario-Integrated Optimization of Dynamic Systems.
8) Optimal Design of Shell-and-Tube Heat Exchangers.
9) Optimization of an Alkylation Reaction.
10) Optimization of Thermal Cracker Operation.
11) Optimization of Non-Linear Chemical Processes.
12) Optimum planning of cropping patterns.
13) Optimization of Water Pumping System .
14) Optimal Design of Gas Transmission Network .
15) Differential Evolution for Multi-Objective Optimization
16) Physiochemistry of Carbon Materials.
17) Radio Network Design.
18) Reflectivity Curve Simulation.
45
COMMERCIAL SOFT
1) Built in optimizer in MATHEMATICA's function
Nminimize (since version 4.2).
 2) MATLAB's GA toolbox contains a variant of DE.
 3) Digital Filter Design.
 4) Diffraction grating design.
 5) Electricity market simulation.
 6) Auto2Fit.
 7) LMS Virtual Lab Optimization.
 8) Optimization of optical systems.
 9) Finite Element Design.

46
APPLICATION : BUMP PROBLEM
47
APPLICATION : BUMP PROBLEM
48
49
REFERENCES





[1] http://www.icsi.berkeley.edu/~storn/code.html
[2] Andries P. Engelbrecht ,(2007),Computational
Intelligence: An Introduction, 2nd Edition., ISBN: 978-0470-03561-0.
[3] Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential
Evolution: A Practical Approach to Global Optimization.
Springer. ISBN 978-3-540-20950-8.
http://www.springer.com/computer/theoretical+computer+sci
ence/foundations+of+computations/book/978-3-540-20950-8.
[4] Feoktistov, V. (2006). Differential Evolution: In Search of
Solutions. Springer. ISBN 978-0-387-36895-5.
http://www.springer.com/mathematics/book/978-0-38736895-5.
[5] J. Vesterstrom and R. Thomson, A comparative study of
differential evolution, particle swarm optimization, and
evolutionary algorithms on numerical benchmark problems,
Proc. of IEEE Congress on Evolutionary Computation,
2004,pp. 1980–1987.
50
‫يک سخن‬
‫زندگي آن چيزي است که براي تو اتفاق مي‌افتد‪ ،‬در حالي که تو سرگرم‬
‫برنامه‌ريزي‌هاي ديگري هستي‬
‫‪51‬‬
THANKS FOR YOUR ATTENTION
52