Warwick Business School
Juergen Branke, Sergio Morales-‐Enciso
Warwick Business School
Outline
� Mo8va8on � Evolu8onary op8misa8on in dynamic
environments � Efficient Global Op8misa8on (EGO) � Extensions to dynamic environments � Experimental results � Conclusion
Warwick Business School
Mo+va+on
� Many op8misa8on problems are dynamic � Scheduling � Pickup & delivery � Changing quality of raw material � …
� Problem changes from finding the op8mum to tracking the op8mum
Warwick Business School
Nature is able to adapt
Evolu+onary algorithms seem promising!
Warwick Business School
Evolu+onary algorithms are not Convergence of popula8on limits adaptability
Warwick Business School
Possible Remedies
1. Restart aPer a change (only choice if changes are too severe)
But: Too slow
2. Generate diversity aPer a change – Hypermuta8on [Cobb 1990]
But: Randomisa8on destroys informa8on, only local search or similar to restart
Warwick Business School
Possible Remedies (2) 3. Maintain diversity throughout the run
� Random Immigrants [Grefenste\e 1992] � Thermodynamical GA [Mori et al. 1996]
But: Disturbes op8misa8on process
4. Memory-‐enhanced EAs – Implicit memory [Goldberg & Smith 1987, Lewis et al. 1998]
• Redundant gene8c representa8on (e.g. diploid)
– Explicit memory [Ramsey & Grefenste\e 1993, Branke 1999, Yang 2008] • Explicit rules which informa8on to store in and retrieve from the memory
But: Only useful when op8mum reappears at old loca8on, Problem of convergence remains
Warwick Business School
Possible Remedies (3)
5. Mul8-‐Popula8on approaches � Maintain different subpopula8ons on different
peaks ○ adap8ve memory ○ able to detect new op8ma ○ distance/similarity metric required
� Self-‐Organizing Scouts [Branke et al. 2000 � ClusteringPSO [Yang&Li 2010, Li & Yang 2012]
Maintains and updates memory of several good regions
Warwick Business School
Only few evalua+ons possible
� Limited 8me � Expensive black-‐box op8misa8on problem
Warwick Business School
Efficient Global Op+misa+on (EGO)
� Fit a Gaussian Process (GP) to data � Response model provides informa8on about
� expected value � uncertainty
� Use response model to determine next data point
� Expected improvement makes explicit trade-‐off between explora8on and exploita8on
Warwick Business School
Efficient Global Op+misa+on (EGO)
� Fit a Gaussian Process (GP) to data
where
f(~x) ⇠ GP
�m(~x), K(~x, ~x
0)�
m(~x) = 0
~
K =
2
64k(~x1, ~x1) · · · k(~x1, ~xn)
.... . .
...k(~xn, ~x1) · · · k(~xn, ~xn)
3
75
k(~x, ~x
0)| {z }kernel
= �
2
f|{z}max cov
exp
✓�
DX
d=1
(xd � x
0d)
2
2 `
2
d|{z}length scale
◆+ �
2
n�(~x,
~
x
0)| {z }measurement noise
Warwick Business School
Example: GP in 1 dimension
0 1 2 3 4 5 6
!1
!0.5
0
0.5
1
1.5
Effect of length scale: L=0.5
Warwick Business School
Adapta+on to dynamic environments How to integrate knowledge from history? a) Designate old date as less reliable (noisy) b) Add 8me as addi8onal dimension c) Modify mean prior
Warwick Business School
� Noise level s2 is user-‐specified parameter
a) Add noise to old samples
k(~x, ~x
0) = �
2
f|{z}max cov
exp
✓�
DX
d=1
(xd � x
0d)
2
2 `
2
d|{z}length scale
◆+ �
2
n(⌧)�(~x,
~
x
0)| {z }measurement noise
�2n(⌧) = (⌧c � ⌧)s2
Warwick Business School
Effect of noise
0 1 2 3 4 5 6
!50
0
50
100
150
200
250
Effect on noise level: !n = 0
0 1 2 3 4 5 6
0
50
100
150
200
250
Effect on noise level: !n = 1
0 1 2 3 4 5 6
0
50
100
150
200
250
300
Effect on noise level: !n = 5
0 1 2 3 4 5 6
0
50
100
150
200
Effect on noise level: !n = 20
Warwick Business School
Example
!3 !2 !1 0 1 2 3!6
!4
!2
0
2
4
6
Sample space [x]
Ob
ject
ive
fu
nct
ion
[y]
0
0.05
0.1
0.15
0.2
0.25
0.3
Exp
ect
ed
imp
rove
me
nt
!3 !2 !1 0 1 2 3!6
!4
!2
0
2
4
6
Sample space [x]
Ob
ject
ive
fu
nct
ion
[y]
0.5
1
1.5
2
2.5
3
3.5
4
Exp
ect
ed
imp
rove
me
nt
!3 !2 !1 0 1 2 3!6
!4
!2
0
2
4
6
Sample space [x]
Obje
ctiv
e funct
ion [y]
0
0.2
0.4
0.6
0.8
1
1.2
1.4
Exp
ect
ed im
pro
vem
ent
!3 !2 !1 0 1 2 3!6
!4
!2
0
2
4
6
Sample space [x]
Obje
ctiv
e funct
ion [y]
0
0.05
0.1
0.15
0.2
0.25
Exp
ect
ed im
pro
vem
ent
Warwick Business School
b) Addi+onal dimension
� Time stamp as addi8onal dimension
� Length scale parameter is learned by GP
k(~x, ~x
0) = �
2
f|{z}max cov
exp
✓�
D+1X
d=1
(xd � x
0d)
2
2 `
2
d|{z}length scale
◆
Warwick Business School
c) Transferring the mean prior
� Instead of a zero mean prior, take the best es8mate of the previous epoch as a prior mean func8on
f(~x) ⇠ GP
�f⌧�1(~x), K⌧ (~x, ~x
0)�
8 ⌧ > 0
Warwick Business School
Measuring performance
� Average error – If every solu8on is tested in real world
� Offline error – If best so far solu8on is tested in real world
� Best before change – If op8miza8on is done before a solu8on is implemented
Warwick Business School
Moving Peaks Benchmark [Branke1999]
� Several peaks, changing in � Loca8on � Height � Width
� Used here: � 5 peaks � 1 D � Change every 25 evalua8ons
Warwick Business School
Offline error
0 200 400 600 800 1000 1200 1400 1600 1800 20000
5
10
15
20
25
30
35
40
45
50
Function Evaluations
Off
line
err
or
Offline error. R=128, Hist=1 epoch. vLength=1.0, height severity=2.0 width severity = 0.01; D=1
ResetIgnoreDIN(S
n=4)
TasD+1Reset*PSMP
Warwick Business School
Final offline error
0
5
10
15
20
RANDOM RESET IGNORE RESET* DIN (S_n=4) TasD+1 PSMP
Offlin
e e
rror
Performance comparison of 7 models. R=128, Hist=1 epochvlength = 1.0; height severity=2.0; width severity = 0.01; D=1
Warwick Business School
0 5000
20
40
60
Function Evaluations
Curr
ent err
or
0 5000
20
40
60
Function Evaluations
Curr
ent err
or
Current error. R=128, Hist=1 epoch. vLength=1.0, height severity=2.0 width severity = 0.01; D=1
0 5000
20
40
60
Function Evaluations
Curr
ent err
or
0 5000
20
40
60
Function Evaluations
Curr
ent err
or
0 5000
20
40
60
Function Evaluations
Curr
ent err
or
0 5000
20
40
60
Function EvaluationsC
urr
ent err
or
Reset Ignore DIN(Sn=4)
TasD+1 Reset* PSMP
Warwick Business School
Conclusion
� With appropriate adjustments, evolu8onary computa8on is able to con8nuously adapt
� Proposed new variants of EGO for dynamic op8misa8on problems
� Results show benefit of transferring informa8on from previous epochs
� Promising for applica8ons where very few func8on evalua8ons are possible
Warwick Business School
Future work
� Move to GP variants that can deal with larger dimensionality and more datapoints
� Learning of noise parameter � Test on other func8ons