A Parallel General Purpose
Multi-Objective Optimization
Framework, Applied to Beam
Dynamic Studies
Yves Ineichen1,2,3 , Andreas Adelmann2 , Costas Bekas3 ,
Alessandro Curioni3 , Peter Arbenz1
1
ETH Zürich
Department of Computer Science
CH-8092 Zürich, Switzerland
2
Paul Scherrer Institut
Accelerator Modelling and Advanced
Simulations
CH-5234 Villigen, Switzerland
3
IBM Research-Zurich
CH-8803 Rüschlikon, Switzerland
21st August 2012
1 / 37
Complex Decision Problem
.
Trade-off
Effect
2 / 37
Complex Decision Problem
Design and operation of particle
accelerators
Multi-Objective
Optimization
Problem
.
Visualization
Applications
MOO Algorithms
Trade-off
Simulation Codes
Effect
High performance
computing
2 / 37
.
Multi-Objective Optimization
[a short introduction]
3 / 37
Multi-Objective Optimization
Problem
Objectives
Design variables
min
.fm (x.),
s.t.
gj (x) ≥ 0,
xLi
≤ x = xi ≤
m = 1...M
j = 0...J
xU
i ,
i = 0...n
. Constraints
4 / 37
Mapping design to objective space
x2
f2
.
min
x1
Design space
.
.
min
f1
Objective space
5 / 37
Mapping design to objective space
x2
f2
.
min
x1
Design space
.
.
min
f1
Objective space
5 / 37
Optimality?
f2
performance
low
• conflicting objectives:
x∗3
high
minimize price
maximize performance
• red points are “equally optimal”:
cannot improve one point without
hurting at least one other solution
→ Pareto optimality
• blue curve is called Pareto front
x∗2
x∗1
x4
x∗0
.
low
price
high
f1
• x4 is dominated by x∗1 and x∗2
6 / 37
Preference Specification
f2
x∗a-priori
a-priori preference:
e.g. performance ≫ price → x∗a-priori
performance
high
low
.
low
price
high
f1
a-posteriori preference: → Pareto front
• provides deeper understanding of
solution space
• visualizes how choice affects design
space
7 / 37
.
Evolutionary Algorithms
[how can we solve multi-objective optimization problems?]
8 / 37
Susman
03-05
Ulunga
et al
98,99
Czyzak
et al
96-98
Susman
02-04
Suppapitnarm
et al 00
Cheng,
Li 95
PDMOSA
WMOSA
PSA
UMOSA
Bridgman
22
Charnes
et al.
67/55
Osyczka
84
SMOSA
weighted
min-max
Fonseca,
Fleming
93
Yu, Leitmann
74
exponen-tial
weighted
Ijiri 65
Charnes,
Cooper
61
weighted
product
lexicographic
goal programming
ranking
Zeleny
82
simulated
annealing
Chankong,
Haimes
83
VEGA
a priori articulation of
preference
weighted
global
criterion
bounded
objective
function
physical programming
.
weighted
sum
.
Schaf-fer
85
Gerasimov,
Repko
78
Waltz
67
Srinivas,
Deb 95
Goldberg
89
Athan,
Papalambros
96
Miettinen
99
Hwang,
Md.
Masud
79
Hwang
et al. 93
Haimes
et al. 71
Yoon 80
Chankong,
Haimes
83
Chen et
al. 00
TOPSIS
tourna-ment
selection
evolutionary
algorithms
multiobjective
.
Horn et
al. 94
.
Multiobjective
Optimization
.
Pareto-set
filter
reduce
to singleobjective
.
.
no articulation of
preference
global
criterion
min-max
.
Yu 73
.
particle
swarm
Osyczka,
Kundu
96
euclidean
distance
Ishibuchi,
Murata
96
weighted
sum
Kursawe
91
zerooneweighted
sum
Gen,
Liu 95
constr.
preemp.
goal
prog.
Schaumann et
al. 98
Pareto
fitness
func.
Moore
and
Chapman
Baumgartner
et al
objective
product
Rao and
Freiheit
91
Fieldsend and
Singh
Hu and
Eberhart
additional
techniques
•
•
•
Lexicographic
SubPopula-tion
Paretobased
Other
Comb-ined
...
Messac
et al. 03
Xiao-hua
et al.
Mahfouf
et al.
Zhang
et al.
Li
multiple Pareto solutions can be found in one run
a posteriori articulation of preference
“easier”: diversity in decision and objective space (non-linear mapping)
Cheng,
Li 96
NBI
Chow
and Tsui
Parsopoulos
et al
Rao 87
physical programming
NC
Aggregation
Davis 83
a posteriori
articulation of
preference
Ray and
Liew
Parsopoulos
et al
Osyczka
78
Straffin
93
Rao
niche
techniques
Yu, Leitmann
74
Li 92
Nash
arbitration
fitness
sharing
Zeleny
82
objective
sum
Messac
96
Cheng,
Li 97
•
•
•
•
Das,
Dennis
98
Martinez
et al. 01
Messac,
Mattson
02
Das 99
only one Pareto solution can be found in one run
preference-based (specify preference for trade-off solution)
not all can be found in non-convex MOOPS
all algorithms require a prior knowledge (weights, ε, targets)
9 / 37
Evolutionary Algorithms
Population
I3
I4
Ik
I1
Variator
Selector
I4 · Ik :
1. I4 , 2. Ik , 3. I2 , 4. I3
5. I1 , . . ., n. In
I2
=
.
10 / 37
Ranking individuals
Non-dominated sorting genetic algorithm (Nsga-II) initialization:
• count how many solutions np dominate solution p
• store all solutions p dominates in set Sp
• set k ← 0
Repeat while there exists solutions with np > 0:
• for all solutions p with np = 0:
• store solution in k-th non-dominated front
• visit all members i of Sp and reduce ni by one
• k←k+1
Order relation corresponds to index in set of non-dominated fronts
A fast and elitist multiobjective genetic algorithm: NSGA-II, K. Deb et. al., IEEE
Transactions on Evolutionary Computation, 6(2):182–197, Apr. 2002.
11 / 37
Evolutionary Algorithms
• PISA
Variator
dispatch
individuals
2 individuals
ready
NSGA-II
.
Selector
• Finite state machine
• Nsga-II selector
• access to many other selectors
• “Continuous generations”
• Independent bit mutations
• Various crossover polices
A Platform and Programming Language Independent Interface for Search
Algorithms: http://www.tik.ee.ethz.ch/pisa/
12 / 37
First Population
20
emitx [mm mrad]
15
10
5
0
0.20
.
0.22
0.24
0.26
0.28
0.30
dE [MeV]
13 / 37
649th Population
20
emitx [mm mrad]
15
10
5
0
0.20
.
0.22
0.24
0.26
0.28
0.30
dE [MeV]
Now scientist/operator can specify preference
14 / 37
.
The Framework
[how can we facilitate solving multi-objective problems?]
15 / 37
Multi-Objective Optimization
Framework
input
-
OPAL
sims
Pilot
obj
-
.
Optimizer
constr
Convex
Optimization
Algorithms
Heuristic
Algorithms
16 / 37
Master/Worker Model
Optimizers
O1
Pilot
job
queue
j2 j3 j4 j1
Workers
W1
.
Wj
Oi
r1
17 / 37
Master/Worker Model
Comp. Domain
Optimizeri [coarse]
multiple starting
points, multiple opt.
problems
Optimizer [coarse]
parallel optimizer
Forward Solverj [fine]
parallel E-T
Workers [coarse]
Corei
eval forward problem
18 / 37
.
Application
[how can we use the framework?]
19 / 37
Ingredients
1× optimization algorithm, 1× forward solver and
1× specification of optimization problem, e.g., annotating the simulation
input file:
//d1: DVAR, VARIABLE="D_LAG_RGUN",
LOWERBOUND="-0.1", UPPERBOUND="0.1";
//d2: DVAR, VARIABLE="D_LAG_B01",
LOWERBOUND="-0.1", UPPERBOUND="0.1";
//obj1: OBJECTIVE, EXPR="energy*-1";
//obj2: OBJECTIVE, EXPR="dE * meas_error("file", "rms_x")";
//objs: OBJECTIVES = (obj1, obj2);
//dvars: DVARS = (d1, d2);
//constrs: CONSTRAINTS = ();
//opt: OPTIMIZE, OBJECTIVES=objs, DVARS=dvars,
CONSTRAINTS=constrs;
20 / 37
Forward solver typically is
expensive to run..
21 / 37
Maxwell’s Equation in the
Electrostatic approximation
1,2 or 3D Field Maps &
Analytic Models (E, B)ext
Poisson Problem s.t.′ BC’s
ρ
∆ϕ′sc = −
ϵ0
→ (E, B)SC
Electro
Magneto
Optics
N-Body
Dynamics
. + Hsc
H = Hext
If E(x, t) and B(x) are known, the equation of motion can be
integrated:
• Boris-pusher (adaptive version soon!)
• Leap-Frog
• RK-4
22 / 37
and we require a massive number
of forward solves per optimization
23 / 37
Object Oriented Parallel
Accelerator Library (OPAL)
OPAL is a tool for precise charged-particle optics in large accelerator
structures and beam lines including 3D space charge.
•
•
•
•
built from the ground up as a parallel application
runs on your laptop as well as on the largest HPC clusters
uses the mad language with extensions
written in C++ using OO-techniques, hence OPAL is easy to
extend
• nightly regression tests track the code quality
OPAL: https://amas.psi.ch/OPAL
24 / 37
3D Tracker
• Huge # of macro particles (100’000 –
e−
.
100’000’000)
• Computing space-charge is expensive
e−
repulsive force of
charged particles
• Load balancing difficult
• Lots of synchronization points
.
Slow but “high resolution” forward solver
The Object Oriented Parallel Accelerator Library (OPAL), Design, Implementation
and Application, A. Adelmann et. al.
25 / 37
Envelope Tracker
y
.
x
z
•
•
•
•
•
# slices ≪ # macro particles
Analytical space-charge
Slices distributed in contiguous blocks
Load imbalance of at most 1 slice
Low number of synchronization points
Fast but “low resolution” forward solver
A fast and scalable low dimensional solver for charged particle dynamics in large
particle accelerators, Y. Ineichen et. al.
26 / 37
.
Usage
[Ferrario Matching Point]
27 / 37
Optimization Problem
min
[εx , ∆rmsx,peak , ∆εx,peak ]
//min_ex:
OBJECTIVE, EXPR="emit_x";
//peak_rms_x: FROMFILE, FILE="rms_x-err.dat";
//peak_e_x:
FROMFILE, FILE="emit_x-err.dat";
//sig_x:
DVAR, VARIABLE="SIGX", LOWERBOUND="0.000250",
UPPERBOUND="0.000250";
//sol_ks:
DVAR, VARIABLE="MSOL10_i", LOWERBOUND="110",
UPPERBOUND="120";
//lag_gun: DVAR, VARIABLE="D_LAG_GUN", LOWERBOUND="0.0",
UPPERBOUND="0.05";
//volt_gun: DVAR, VARIABLE="RACC_v", LOWERBOUND="25",
UPPERBOUND="40";
28 / 37
1.4
∆rmsx, peak [m]
1.2
1.0
0.8
0.6
0.4
0.2
0.05
.
0.10
0.15
0.20
0.25
0.30
0.35
∆εx, peak [m]
Pareto front after 1’000 generations (approx. 20 minutes on 16 cores)
29 / 37
1.4
∆rmsx, peak [m]
1.2
1.0
0.8
0.6
0.4
0.2
0.05
.
0.10
0.15
0.20
0.25
0.30
0.35
∆εx, peak [m]
Pareto front after 1’000 generations (approx. 20 minutes on 16 cores)
29 / 37
Simulation results for individual 38
30 / 37
Conclusions
Multi-Objective Optimization Problems
• omnipresent in many fields in research and design
• important in understanding problem and trade-off solutions
• expensive to solve
Framework
• closes the gap between theory and user
• combining OPAL and EA results in a viable MOOP solver for beam
dynamics
• HPC necessary to compute Pareto front in meaningful timeframe
31 / 37
Outlook
Investigate other multi-objective optimization algorithms
Run real optimization problem on massive number of cores
Visualization of results
32 / 37
This project is funded by:
IBM Research – Zurich
Paul Scherrer Institut
Acknowledgements
• OPAL developer team
• SwissFel team
• Sumin Wei
33 / 37
Backup
34 / 37
Optimization Problem
min
[energy spread, emittance]
s.t. ∂t f(x, v, t) + v · ∇x f(x, v, t) +
∇ × B = µ0 J + µ0 ε0
∂E
,
∂t
ρ
∇·E= ,
ε0
∫
ρ = −e f(x, v, t) d3 p,
E = Eext + Eself ,
q
(Etot + v × Btot ) · ∇v f(x, v, t) = 0
m0
∂B
∇×E=−
∂t
∇·B=0
∫
J = −e f(x, v, t)v d3 p
B = Bext + Bself
...
35 / 37
Envelope Equations
∑ j
d2
2c2 kp
2 d
R
+
β
γ
(β
R
)
+
R
K
=
×
i
i
i
i
i
i
i
d2 t
dt
Ri βi
j
)
(
G(∆i , Ar )
4εth
n c 1
2 G(δi , Ar )
−
(1
−
β
)
+
i
3
γi
γi
γi R3i
)
d
e0 ( ext
βi =
Ez (zi , t) + Esc
z (zi , t)
3
dt
m0 cγi
d
zi = cβi
dt
36 / 37
SwissFel 1 : Switzerland’s X-ray free-electron laser Project at PSI
• big project: > 100 people, expensive, 700 m long
• 1 Ångström
• to reach target it is of crucial importance to attain “good” beam
properties (e.g. narrow beam/small phase space volume)
.
1 http://www.psi.ch/swissfel/
37 / 37
SwissFel 1 : Switzerland’s X-ray free-electron laser Project at PSI
Calls for optimization of Injector
• Several conflicting objectives
• Key technology: multi-objective
optimization
• big project: > 100 people, expensive, 700 m long
• 1 Ångström
• to reach target it is of crucial importance to attain “good” beam
properties (e.g. narrow beam/small phase space volume)
.
1 http://www.psi.ch/swissfel/
37 / 37