Comparison of Parallel Surrogate-Assisted Optimization Approaches

CIplus
Band 7/2018
Compa ison o Pa allel
Su oga e-Assis ed Op imiza ion
App oaches
F ede ik Rehbach, Ma in Zae e e , Joe g S o k, and Thomas Ba z-
Beiels ein
Compa ison o Pa allel Su oga e-Assis ed Op imiza ion
App oaches
F ede ik Rehbach
ede ik. ehbach@ h-koeln.de
TH Köln
Cologne, Ge many
Ma in Zae e e
ma in.zae e e @ h-koeln.de
TH Köln
Cologne, Ge many
Jö g S o k
joe g.s o k@ h-koeln.de
TH Köln
Cologne, Ge many
Thomas Ba z-Beiels ein
homas.ba z-beiels ein@ h-koeln.de
TH Köln
Cologne, Ge many
ABSTRACT
The a ailabili y o se e al CPU co es on cu en compu e s enables
pa alleliza ion and inc eases he compu a ional powe signi ican ly.
Op imiza ion algo i hms ha e o be adap ed o exploi hese highly
pa allelized sys ems and e alua e mul iple candida e solu ions in
each i e a ion. This issue is especially challenging o expensi e
op imiza ion p oblems, whe e su oga e models a e employed o
educe he load o objec i e unc ion e alua ions.
This pape compa es di e en app oaches o su oga e model-
based op imiza ion in pa allel en i onmen s. Addi ionally, an easy
o use me hod, which was de eloped o an indus ial p ojec , is
p oposed. All desc ibed algo i hms a e es ed wi h a a ie y o
s anda d benchma k unc ions. Fu he mo e, hey a e applied o
a eal-wo ld enginee ing p oblem, he elec os a ic p ecipi a o
p oblem. Expensi e compu a ional luid dynamics simula ions a e
equi ed o es ima e he pe o mance o he p ecipi a o . The ask
is o op imize a gas-dis ibu ion sys em so ha a desi ed eloci y
dis ibu ion is achie ed o he gas low h oughou he p ecipi a-
o . The as amoun o possible con igu a ions leads o a complex
disc e e alued op imiza ion p oblem. The expe imen s indica e
ha a hyb id app oach wo ks bes , which p oposes candida e solu-
ions based on di e en su oga e model-based in ill c i e ia and
e olu iona y ope a o s.
CCS CONCEPTS
•Ma hema ics o compu ing →Disc e e op imiza ion
;
•The-
o y o compu a ion →Con inuous op imiza ion
;
Gaussian
p ocesses
;
•Compu ing me hodologies →Modeling and sim-
ula ion;
Pe mission o make digi al o ha d copies o all o pa o his wo k o pe sonal o
class oom use is g an ed wi hou ee p o ided ha copies a e no made o dis ibu ed
o p o i o comme cial ad an age and ha copies bea his no ice and he ull ci a ion
on he i s page. Copy igh s o componen s o his wo k owned by o he s han ACM
mus be hono ed. Abs ac ing wi h c edi is pe mi ed. To copy o he wise, o epublish,
o pos on se e s o o edis ibu e o lis s, equi es p io speci ic pe mission and/o a
ee. Reques pe missions om [email p o ec ed].
GECCO ’18, July 15–19, 2018, Kyo o, Japan
©2018 Associa ion o Compu ing Machine y.
ACM ISBN 978-1-4503-5618-3/18/07...$15.00
h ps://doi.o g/10.1145/3205455.3205587
KEYWORDS
Op imiza ion, Su oga es, Modeling, Pa alleliza ion, Elec os a ic
P ecipi a o
ACM Re e ence Fo ma :
F ede ik Rehbach, Ma in Zae e e , Jö g S o k, and Thomas Ba z-Beiels ein.
2018. Compa ison o Pa allel Su oga e-Assis ed Op imiza ion App oaches.
In GECCO ’18: Gene ic and E olu iona y Compu a ion Con e ence, July 15–19,
2018, Kyo o, Japan. ACM, New Yo k, NY, USA, 8 pages. h ps://doi.o g/10.
1145/3205455.3205587
1 INTRODUCTION
Real-wo ld op imiza ion p oblems may equi e signi ican esou ces
o each e alua ion o a candida e solu ion. O en, such p oblems
a e based on ime consuming compu a ional luid dynamics (CFD)
simula ions, whe e a single simula ion migh ake hou s, days, o
e en weeks. Thus, e en a ew hund ed unc ion e alua ions may
esul in un imes o se e al weeks o mon hs. In p ac ice such long
ime ames a e in easible and ende he p oblems e y di icul
o sol e. Two well es ablished concep s allow o deal wi h hese
issues: su oga e model based op imiza ion (SMBO) and pa allel
compu ing.
SMBO ies o lea n a da a-d i en su oga e model which e-
places he expensi e objec i e unc ion. Unde he assump ion ha
he model is cheap o e alua e, an ex ensi e sea ch becomes easible.
Thus, p omising new solu ions can be sugges ed, e alua ed wi h
he objec i e unc ion and used o upda e he su oga e model in
an i e a i e ashion. A mo e in-dep h explana ion o SMBO and i s
applica ions can be ound in [1] and [13].
Pa allel compu ing a emp s o exploi he a ailabili y o se e al
CPU co es which can ope a e simul aneously.
While i is s aigh - o wa d o pa allelize a CFD simula ion by
sp eading i on o se e al CPU co es, he e is a limi on how many
co es can be used e icien ly o a single simula ion. Hence, wi h
inc easing numbe s o a ailable co es, i will become mo e e icien
o un se e al simula ions in pa allel. Howe e , no all exis ing
op imiza ion me hods can be applied in a pa allel manne . No ably,
he s anda d SMBO app oach does no ake signi ican ad an age
ou o a mul i-co e sys em. Despi e i s success in he domain o
expensi e objec i e unc ions, i is no e icien o p oblems whe e
pa allelized unc ion e alua ions a e possible. S anda d SMBO lacks
GECCO ’18, July 15–19, 2018, Kyo o, Japan Rehbach e al.
a s aigh o wa d app oach o gene a ing mul iple new design
poin s in each i e a ion.
In he ollowing, Sec ion 2 will gi e an o e iew on ela ed
esea ch and exis ing me hods. Sec ion 3 p esen s wo s uc u es
o using SMBO in a pa allelized en i onmen . They we e used in
an indus ial p ojec o op imizing an elec os a ic p ecipi a o
(ESP). Sec ion 4 desc ibes he ESP p oblem and i s complexi y in
de ail. An expe imen al s udy compa es he di e en me hods based
on he ESP p oblem and a i icial es unc ions and is desc ibed
in Sec ion 5. Resul s a e p esen ed and discussed in Sec ion 6. A
conclusion and an ou look a e p esen ed in Sec ion 7.
2 RELATED RESEARCH
2.1 E icien Global Op imiza ion
One equen ly used su oga e model is K iging. In K iging, an
objec i e unc ion alue can be es ima ed o a gi en new candi-
da e solu ion by building a Gaussian p ocess model, based on a
co ela ion s uc u e de i ed om he obse ed aining da a[5].
K iging is equen ly used in SMBO, because i can p o ide an es-
ima e o i s unce ain y. Condi ional on a gi en candida e solu ion,
K iging speci ies a no mal dis ibu ion o he co esponding objec-
i e alue, whe e he mean is he p edic ed alue and he s anda d
de ia ion is he unce ain y. No ably, he unce ain y es ima e can
be employed o calcula e he Expec ed Imp o emen (EI) [
11
] o a
candida e solu ion, which is used in he E icien Global Op imiza-
ion (EGO) algo i hm [
8
]. The main idea in EGO is no o sea ch he
su oga e o he poin wi h he bes p edic ed objec i e unc ion
alue. Ins ead, he unce ain y es ima ion o he model is aken in o
accoun by maximizing he EI c i e ion. In ui i ely, maximizing EI
balances explo a ion (imp o ing he model o knowledge abou he
sea ch space) and exploi a ion (imp o ing he objec i e unc ion
alue). EI inc eases when he p edic ed alue ge s be e , as well as
when he unce ain y ises.
Clea ly, EGO and EI in hei o iginal o ms a e mean o gen-
e a e a single, mos p omising design poin (i.e., he solu ion ha
maximizes EI).
2.2 In es men Po olio Imp o emen
In es men Po olio Imp o emen (IPI) ies o u he imp o e he
idea o balancing be ween explo a ion and exploi a ion o he sea ch
s a egy. U sem [
17
] sugges s ha one can judge each candida e
solu ion om he iewpoin o an in es men po olio. The candi-
da e solu ion wi h he highes p obabili y o imp o emen is seen
as a low isk in es men . Candida e solu ions which a e op imized
owa ds he highes expec ed imp o emen yield a highe isk bu
also migh lead o be e unc ion alue ou comes. Wi h IPI, i is
possible o gene a e mul iple candida e solu ions pe i e a ion on a
single su oga e model. Each o he gene a ed solu ions will aim o
a di e en isk le el. This is achie ed by ei he p e e ing solu ions
wi h a high unce ain y (EI) o solu ions wi h low unce ain y bu
a be e p edic ed alue.
IPI gene a es a se o h ee design poin s pe i e a ion: a high, a
medium, and a low isk design poin . Each o hese design poin s
is hen e alua ed sequen ially. Thus, IPI balances isks in single-
h eaded op imiza ion. Howe e , since IPI is heo e ically able o
gene a e any amoun o design poin s wi h a gi en su oga e, i
can also be employed o pa allelize an SMBO algo i hm. Then, he
amoun o gene a ed design poin s pe i e a ion is equal o he
maximum amoun o objec i e unc ion e alua ions in pa allel.
2.3 Mul i-Poin Expec ed Imp o emen (q-EI)
An in ui i e idea o pa allel SMBO is o ex end EI o poin se s. The
mul i poin expec ed imp o emen c i e ion was i s p oposed in
[
15
] and la e u he de eloped in [
6
]. I calcula es he expec ed im-
p o emen c i e ion o a se o candida e solu ions. Ginsbou ge e
al. [
6
] p o ide a comp ehensible desc ip ion o he q-EI calcula ion.
He e, q is he se -size o which EI is compu ed.
Since q-EI allows o calcula e he EI c i e ion o any numbe o
candida e solu ions, i is a e y p omising choice o pa allelized
EGO. A each i e a ion, he se o candida e solu ions ha op imizes
he q-EI c i e ion is de e mined. The se size equals he amoun o
objec i e unc ion e alua ions ha can be pe o med in pa allel.
Hence, he main di e ence be ween SMBO and SMBO wi h q-EI is
he amoun o solu ions gene a ed pe i e a ion.
One inhe en p ope y o he q-EI c i e ion is ha i a o s se s
o solu ions ha a e sp ead a om each o he in he sea ch space.
I wo o mo e candida e solu ions mo e close o each o he , hei
combined expec ed imp o emen will app oach he alue o he
bes . E ec i ely, only one poin om some small clus e would
imp o e he q-EI o he whole se , he o he s a e negligible.
2.4 Fu he App oaches
A ecen su ey o pa allel SMBO is gi en by Ha ka e al. [
7
]. They
desc ibe se e al app oaches based on Gaussian p ocess models and
unce ain y based in ill c i e ia: pa allel EGO/EI, mul i-poin p oba-
bili y o imp o emen (PI) and app oaches based con idence bounds.
Fu he mo e, he su ey discusses se e al app oaches based on mod-
els wi hou unce ain y in o ma ion, mul i-model app oaches (e.g.,
one model o each pa allel h ead), app oaches ha explo e (local)
sub-spaces o he sea ch space and discuss hyb ids o su oga e-
assis ed op imiza ion and e olu iona y compu a ion.
In addi ion, he e ha e been s udies on pa allel SMBO wi h eed
gaussian p ocess (
TGP
) [
16
]. They use a combina ion o
TGP
mod-
els oge he wi h a local pa e n sea ch op imize . Bo h o hese
echniques a e combined in o an asynch onous pa allel compu ing
en i onmen . He e, a me hod simila o he q-EI is used o gene a e
mul iple design poin s pe i e a ion, whe e candida e poin s a e
added in a sequen ial manne .
Ano he idea p oposed by Bischl e al. [
2
] is o ea he p oblem
in a mul i-objec i e manne . They sugges a numbe o po en ial
objec i es, including EI, mean, p obabili y o imp o emen , unce -
ain y ( a iance es ima e), dis ance o nea es neighbo and dis ance
o nea es be e neighbo . They epo ha a combina ion o mean,
unce ain y and dis ance o nea es neighbo pe o med bes in a
se o nume ical expe imen s.
Fu he mo e, expensi e e alua ion imes may a y, e.g., CFD
simula ions may di e in ime consump ion, depending on he e al-
ua ed candida e solu ion. To ha end, Rich e e al. [
14
] p opose an
asynch onous app oach ha a emp s o p oduce e alua ion sched-
ules ha educe he o e all ime consump ion. They use su oga e
models o app oxima e he objec i e unc ion esul s as well as o
app oxima e he equi ed esou ces.
Compa ison o Pa allel Su oga e-Assis ed Op imiza ion App oaches GECCO ’18, July 15–19, 2018, Kyo o, Japan
3 SURROGATE ASSISTED OPTIMIZATION
PARALLEL TO STANDARD OPTIMIZERS
We p opose o use a hyb id algo i hm composed o s anda d SMBO
and EAs. I is able o p oduce new candida e solu ions in wo di e -
en ways: 1) ia s anda d in ill c i e ia such as bes -p edic ed and
EA, and 2) ia e olu iona y ope a o s. A pa allel design o SMBO
was de eloped, which is able o sol e he ESP p oblem. The usage
o he bes -p edic ed in ill c i e ion, as well as he EI in ill c i e ion
a e well es ablished and yield good esul s in single h eaded ap-
plica ions. Thus, he hyb id app oach will employ hese wo in ill
c i e ia and u ilize any emaining compu a ional esou ces o op i-
miza ion wi h an EA. In he ollowing, we in oduce a synch onous
and asynch onous pa allel design o he p oposed hyb id algo i hm.
Bo h designs a ise om a op imiza ion ask in an ongoing p ojec
and a e aimed o an easy pa alleliza ion o an al eady exis ing
op imize . The basic concep is isualized in Figu e 1.
Algo i hm 1
Synch onous SMBO+EA hyb id. He e,
nini
is he
numbe o ini ial candida e solu ions, design() is a unc ion ha
p oduces an ini ial se o candida e solu ions, ain() is a p oce-
du e o ain an adequa e su oga e model, and op imize() is an
e olu iona y algo i hm implemen a ion wi h a ia ion ope a o s
eaMu a ion() and eaRecombina ion(). The unc ion e alPa allel()
ep esen s he po en ially expensi e objec i e unc ion, which al-
lows o e alua ing nsolu ions simul aneously.
1: unc ion
SMBO+EA-Sync(
nini
, design(), ain(), op imize(),
e alPa allel(), eaMu a ion(), eaRecombina ion())
2: X={x1,x2, ..., xni ni }= design(nini )
3: y= e alPa allel(X)
4: while budge no exhaus ed do
5: model = ain(X,y)
6: xs1= op imize(BP(model)) ▷op imize bes -p edic ed
7: xs2= op imize(EI(model)) ▷maximize EI
8: Xo= eaMu a ion() + eaRecombina ion()
9: Xos ={Xo,xs1,xs2}
10: yos = e alPa allel(Xos )
11: X={X,Xos }
12: y={y,yos }
13: end while
14: end unc ion
The i s , synch onous design is p esen ed in Algo i hm 1. In
di e ence o s anda d (synch onous) SMBO p ocedu es, bo h he
bes p edic ed and EI c i e ion in ill c i e ia a e u ilized o c ea e
wo candida es pe i e a ion and a se o candida es is gene a ed in
pa allel by gene ic ope a o s (mu a ion, ecombina ion). All gen-
e a ed candida es a e passed o a ask queue, which handles he
pa allel e alua ion o all candida es wi h he eal objec i e unc ion.
The nex gene a ion s a s a e all candida es a e e alua ed.
The second, asynch onous design is in oduced o accoun o he
compu a ional cos s o he su oga e model i ing and op imiza ion.
O en, su oga es a e conside ed o ha e ze o un ime since hey
a e, compa ed o he eal objec i e unc ion, e y quick o e alua e.
Howe e , hey o en demand conside able esou ces, depending
on gi en sample sizes, p oblem dimension and ype o employed
model. In he synch onous e sion, no e alua ions a e s a ed un il
Figu e 1: A su oga e model implemen ed in pa allel o he
op imiza ion algo i hm. One algo i hm is used o op imize
he su oga e. Ano he op imize (which can be ano he in-
s ance o he same op imize ), di ec ly p oposes candida e
solu ions on he objec i e unc ion. Th ough a schedule ,
bo h se s o candida e solu ions a e e alua ed. The su oga e
is upda ed wi h new da a om hese e alua ions.
he su oga e is i ed and u ilized o p opose new candida es. As
his p ocedu e is no pe o med in pa allel, a ailable esou ces a e
no used e icien ly. This is whe e an asynch onous a chi ec u e
may be bene icial.
Algo i hm 2 shows a pseudo-code implemen a ion o he asyn-
ch onous op imiza ion s uc u e. The main idea o his asynch o-
nous design is ha aining and op imiza ion o he su oga e model
can be pe o med in pa allel o he objec i e unc ion e alua ions.
In each i e a ion o he asynch onous algo i hm, a check is pe -
o med i he e ha e been any new candida e solu ions gene a ed
by he su oga e op imiza ion h ead. I so, bo h EA candida es and
su oga e candida es a e e alua ed wi h he objec i e unc ion. I
no , he ee compu a ion slo s a e illed wi h candida es gene a ed
by he gene ic ope a o s.
4 THE ESP PROBLEM
The ESP is a eal indus ial op imiza ion p oblem. The ESP is one
o he main componen s o gas cleaning sys ems. They a e used in
la ge scale coal- i ed powe plan s o o he indus ies whe e solid
pa icles ha e o be emo ed om a gas s eam. ESPs a e la ge
de ices wi h dimensions o a ound 30m
×
30m
×
50m, esul ing in
mul iple millions o eu os jus in building cos . The main ask o an
ESP is o sepa a e and ex ac pa icles om exhaus gases in o de
o educe en i onmen al pollu ion. Figu e 2 illus a es his sys em.
In he lue gas inle hood o an ESP, a gas dis ibu ion sys em
(GDS) (shown in Figu e 3) is equi ed o con ol and guide he gas
low h ough sepa a ion zones in which pa icles a e emo ed om
he exhaus gases. I no GDS is used, o i he sys em is con igu ed
poo ly, he as inle gas s eam will ush h ough he sepa a ion
zones o he ESP. This esul s in e y low sepa a ion e iciencies. In
case o a well con igu ed GDS, he in lowing gas is nicely dis ibu ed
ac oss he whole su ace o he sepa a ion zones, esul ing in high

GECCO ’18, July 15–19, 2018, Kyo o, Japan Rehbach e al.
Algo i hm 2
Asynch onous SMBO+EA hyb id. He e,
nini
is he
numbe o ini ial candida e solu ions, design() is a unc ion ha
p oduces an ini ial se o candida e solu ions, ain() is a p oce-
du e o ain an adequa e su oga e model, and op imize() is an
e olu iona y algo i hm implemen a ion wi h a ia ion ope a o s
eaMu a ion() and eaRecombina ion(). The unc ion e alPa allel()
ep esen s he po en ially expensi e objec i e unc ion, which al-
lows o e alua ing nsolu ions simul aneously.
1: unc ion
SMBO+EA-Async(
nini
, design(), ain(), op imize(),
e alPa allel(), eaMu a ion(), eaRecombina ion())
2: Xs={}
3: X={x1,x2, ..., xni ni }= design(nini )
4: y= e alPa allel(X)
5: unc ion gene a eSu oga eCandida es
6: model = ain(X,y)
7: xs1= op imize(BP(model)) ▷op imize bes -p edic ed
8: xs2= op imize(EI(model)) ▷maximize EI
9: Xs={xs1,xs2}
10: end unc ion
11: while budge no exhaus ed do
12: Xo= eaMu a ion() + eaRecombina ion()
13: Xos ={Xo,Xs}
14: yos = e alPa allel(Xos )
15: do pa allel: gene a eSu oga eCandida es()
16: X={X,Xos }
17: y={y,yos }
18: end while
19: end unc ion
Figu e 2: ESP wi h 3 sepa a ion zones. This igu e was kindly
p o ided by S einmülle Babcock En i onmen GmbH.
e iciency. Hence, he e icien ope a ion o an ESP equi es an
op imal con igu a ion o he GDS. The GDS in ou example consis s
o 49 con igu able slo s. Each o hese slo s can be con igu ed wi h
ba les, as well as blocking and pe o a ed pla es. Ba les a e me al
pla es which a e moun ed a an angle o he gene al gas low. They
a e used o edi ec a gas s eam in o a new di ec ion. Blocking
pla es comple ely block a gas s eam. Pe o a ed pla es a e used o
slow down and only pa ially block gas s eams. They a e c ea ed
by punching a g id o holes in o me al pla es. Smalle holes lead o
highe p essu e d ops and hus a slowe gas s eam. La ge holes
allow o a nea ly ee gas low. These pla es can be moun ed in o
each o he 49 con igu able slo s. Op ionally, some slo s can also be
le emp y.
He e, 40 ou o 49 o he slo s can be con igu ed wi h eigh di e -
en ypes o pla es (including emp y). The emaining nine slo s can
only be con igu ed as “ ue” o “ alse”, which indica es a blocking
pla e o an emp y slo . The as amoun o possible combina ions
o he GDS e eals a complex disc e e op imiza ion p oblem. Fo
a single e alua ion o a gi en con igu a ion, a compu a ionally
expensi e CFD simula ion is necessa y, which esul s in hou s o
compu a ion ime. Un o una ely, such la ge compu a ion imes
make he ESP p oblem unsui able o a la ge numbe o es s uns
which a e necessa y o de i e easonable conclusions abou he
pe o mance o se e al compe ing algo i hms. The e o e, a second
model wi h a la gely educed amoun o cells in he simula ion mesh
was c ea ed. By doing so, he un ime o he model was educed o
only a ew seconds pe e alua ion. This speed up comes a he cos
o educed simula ion accu acy. Howe e , he educed model s ill
cap u es some o he di icul ies and complex ea u es o he ac ual
p oblem, while enabling a de ailed expe imen al s udy. Rep oduc-
ing he ugged p oblem landscape is much mo e impo an han
he ac ual accu acy o each sample poin .
The open sou ce CFD amewo k OpenFOAM [18] was used o
implemen ou simula ions. The o iginal landscape o a eal indus-
ial p oblem is ans e ed in o a unc ion which can be e alua ed
in easonable compu a ion ime. The ESP p oblem was he e o e
conside ed as a good indus ial benchma k o his pape . Cu en ly,
he accele a ed simula ion model is used o une and ad ance he
esea ch in algo i hms o he op imiza ion o he ull long- unning
simula ion.
5 DESCRIPTION OF EXPERIMENTS
5.1 Pe o mance Measu e
One simple way o measu ing op imiza ion pe o mance is o eco d
he bes objec i e unc ion alue a ained a e a ixed numbe o
unc ion e alua ions. Fo pa allel op imiza ion, his is no sui able.
Some algo i hms a e capable o in oking mul iple objec i e unc-
ion e alua ions a once. O he algo i hms a e only able o do hese
sequen ially. Thus, algo i hms which can no pa allelize, use less
unc ion e alua ions in he same compu a ion ime, esul ing in an
un ai compa ison i only he amoun o e alua ions is conside ed.
Measu ing he o al execu ion ime o algo i hms is also no always
easible. Algo i hm un imes la gely ely on ac o s like hei im-
plemen a ion, p og amming language o he machine hey a e un
on. The e o e, a di e en app oach o pe o mance measu emen s
was chosen. Each algo i hm is gi en a ixed amoun o i e a ions
ins ead o unc ion e alua ions. Fo each i e a ion, he amoun o
possible e alua ions in pa allel is ixed. We eco d he bes objec i e
unc ion alue a ained a e a ixed numbe o i e a ions. Thus, an
algo i hm which uses all a ailable co es should be mo e e icien as
i can do mo e unc ion e alua ions.
Compa ison o Pa allel Su oga e-Assis ed Op imiza ion App oaches GECCO ’18, July 15–19, 2018, Kyo o, Japan
Figu e 3: Visualiza ion o a gas dis ibu ion sys em (GDS)
moun ed in he inle hood o o an ESP. This igu e
was kindly p o ided by S einmülle Babcock En i onmen
GmbH.
5.2 Me hods and Con igu a ions
Each op imiza ion algo i hm s a s o wi h an ini ial design o he
size o
n
, whe e
n
is he amoun o objec i e unc ion e alua ions
which a e possible in pa allel. A e he ini ializa ion, each algo-
i hm pe o ms 50 i e a ions. Depending on he alue o
n
, which is
a ied be ween 3 and 15, he algo i hms we e able o do a maximum
o 150-750 unc ion e alua ions.
Wi h his algo i hm se up, 14 di e en me hods we e compa ed,
including a se o base line compa isons, a ia ions o SMBO+EA,
IPI, and wo e sions o q-EI. An o e iew o all me hods and hei
composi ion is gi en in Table 1. All algo i hms we e implemen ed
in R. Each ime an EA was applied, he op imEA me hod o he
CEGO [
19
] package was used. The popula ion size and mu a ion
a e we e se o 20 and 0.05 espec i ely. They we e de e mined o
wo k bes in p elimina y uns. The o he pa ame e s we e kep a
he package de aul s.
In he ollowing he implemen a ion o each o he 14 me hods is
desc ibed sho ly. Two a ian s o single h eaded s anda d SMBO
we e implemen ed as a base line o he compa ison. He e, single
h eaded indica es ha no pa allel e alua ions will be pe o med.
Each a ian is based on a di e en in ill c i e ion (BP and EI),
and bo h use K iging. Hence, hey will be deno ed as K ig-BP and
K ig-EI. The op imum o he in ill c i e ia was de e mined wi h
a simple EA om he same package. To judge he pe o mance
o bo h o hese single h eaded SMBO implemen a ions, a single-
h eaded and model- ee EA is used (deno ed as EA singleCo e).
Table 1: Op imiza ion me hods. Some o he me hods a e
hyb ids, he able shows hei composi ion by de ailing he
amoun o objec i e unc ion e alua ions allowed o each
me hod. He e, nis he o al amoun o e alua ions possible
in pa allel. m=n−
3
o all cases whe e n>
3
o he wise
m=n−2,p=1 o n>3and p=0 o n=3.
Index EA BP EI Rnd.
Samp.
Space
Filling IPI q-EI
EA singleCo e 1
K ig-BP 1
K ig-EI 1
K.BP+K.EI 1 1
EA-nCo es n
K.BP+K.EI +Rnd.Samp. 1 1 n−2
K.BP+K.EI+LHS 1 1 n−2
SMBO+EA-async n−2 1 1
SMBO+EA-async+SF m1 1 p
SMBO+EA-sync n−2 1 1
SMBO+EA-sync+SF m1 1 p
IPI-n-co es n
q-EI n
q-EI-Bounded n
As ano he base line, we es a model- ee EA ha gene a es as
many indi iduals pe i e a ion as he e a e slo s o pa allel unc ion
e alua ion (EA-nCo es). The p oposed SMBO+EA algo i hm uses
bo h BP and EI oge he . Thus, o judge he EAs impac on he
hyb id algo i hm, ano he expe imen was added whe e bo h EI
and BP a e implemen ed wi hou u he algo i hms.
Me hods like la in hype cube sampling (
LHS
) a e o en a gued
o inc ease he model quali y o su oga es by gene a ing space-
illing (SD) designs in he sea ch space. This me hodology o model
quali y imp o emen s was also implemen ed in a CFD ai oil op i-
miza ion by Ma sden e al. [
10
]. To es his hypo hesis wo u he
me hods we e es ed: K.BP+K.EI+Rnd.Samp and K.BP+K.EI+LHS.
Bo h gene a e wo candida e solu ion pe i e a ion, one ia BP
and one ia EI. In K.BP+K.EI+LHS, he emaining
n−
2a ailable
e alua ion slo s a e popula ed wi h LHS. In addi ion o he La in
hype cube p ope y, he poin s a e de e mined o maximize he
dis ance o hei nea es neighbo . In K.BP+K.EI+Rnd.Samp, he
slo s a e popula ed wi h andom samples.
Fu he mo e, ou dis inc e sions o a hyb id SMBO+EA we e
es ed. Bo h he synch onous and asynch onous e sions o SMBO
+EA we e implemen ed (SMBO+EA-sync, SMBO+EA-async). In
addi ion, he bene i s o a space- illing (SF) in ill poin we e in es i-
ga ed in he SMBO+EA s uc u e. To ha end, he synch onous and
he asynch onous e sion o SMBO+EA we e ex ended as ollows.
Fi s ly, one less solu ion is gene a ed by he EA’s a ia ion ope a-
o s. This slo is illed wi h a candida e solu ion ha maximizes he
minimal dis ance o he o he candida e poin s. This app oach is
simila o he dis ance o nea es neighbo objec i e in he s udy
by Bischl e al. [
2
]. The espec i e algo i hms a e deno ed wi h
SMBO+EA-sync+SF and SMBO+EA-async+SF.
The IPI me hod and q-EI we e implemen ed as desc ibed in he
Rela ed Resea ch Sec ion 2. Since IPI was o iginally implemen ed
o gene a e mul iple candida e solu ions ha a e sequen ially e alu-
a ed, he me hodology was sligh ly al e ed. In ou implemen a ion,
GECCO ’18, July 15–19, 2018, Kyo o, Japan Rehbach e al.
he CEGO buildK iging unc ion is used o build a K iging model.
Then, an EA is used o op imize each o IPIs in ill c i e ia, so ha
n
candida e solu ions a e gene a ed in each i e a ion. They a e e al-
ua ed in pa allel and he model is ained wi h he upda ed da a
se .
Fo q-EI, we employ he sugges ed implemen a ion om Gins-
bou ge e al. [
6
], which is a ailable in he DiceK iging R-Package.
Thei implemen a ion o he q-EI in ill c i e ion was op imized by
CEGOs op imEA. Howe e , he ask o he op imiza ion was no
o sea ch a single poin , bu he bes se o poin s ha op imizes
he q-EI c i e ion. Due o he beha io o he q-EI op imiza ion in
i s es s, a second a ian o q-EI based SMBO was implemen ed,
whe e bound cons ain s a e espec ed. No e, ha o he wise all
me hods only espec bound cons ain s whe e applicable, and only
du ing design c ea ion. This issue will be discussed in mo e de ail
in Sec ion 6.
5.3 Tes Func ions
In addi ion o he eal wo ld ESP p oblem, he desc ibed me hods
we e applied o he ollowing es unc ions: Rosenb ock 2D, Ras -
igin 5D, Ras igin 10D, B anin 2D, Ha mann 6D, and Col ille 4D.
As hese addi ional unc ions a e cheap o e alua e, using su o-
ga e models o op imize hem is no e icien . Ye , we a gue ha
he esul s a e ans e able o o he mo e cos ly unc ions. Due
o he a ious landscapes and ea u es p o ided by he es unc-
ions, he expe imen s yield use ul in o ma ion on he su oga es
pe o mance. Making nume ous expe imen s on mo e expensi e
unc ions would lead o an in easible compu a ional cos . Fo each
es unc ion and me hod, 60 epea ed op imiza ion expe imen s
we e pe o med o accoun o he s ochas ic beha io o he al-
go i hms. Only 30 epea s we e done o he ESP p oblem, due o
i s la ge compu a ion imes. The q-EI a ian s we e no es ed on
he ESP p oblem. As no ed abo e, he q-EI implemen a ion om
he DiceK iging package is used. The K iging model in his pack-
age equi es ha he numbe o obse a ions a e g ea e han o
equal o he numbe o a iables. Gi en he high dimensionali y
and compu a ion cos o he ESP p oblem as well as i s disc e e
na u e, his condi ion can no be easonably sa is ied. Especially in
he ea ly s ages o he expe imen s, da a se sizes will be smalle
han equi ed.
6 RESULTS AND DISCUSSION
Ou p esen a ion o he esul s is based on a s a is ical analysis. Fo
each es -p oblem, we pe o med a s a is ical mul iple-compa isons
es . Di e ences a e judged signi ican i he co esponding p- alues
a e smalle han
α=
0
.
05. We compu ed a anking based on he
de i ed pai -wise compa isons. He e, he anking is pe o med as
ollows. Any algo i hm ha is ne e signi ican ly wo se han any
o he algo i hm ecei es ank one, and is emo ed om he lis .
O he emaining algo i hms, he ones ha a e no wo se han
any o he ecei e ank wo and a e also emo ed. This p ocedu e
epea s un il all algo i hms a e anked.
We chose o use he K uskal-Wallis es [
9
] ( o check whe he
any signi ican di e ences a e p esen ) and a co esponding pos -
hoc es based on Cono e ( o de e mine which algo i hm pai s
a e ac ually di e en ) [
3
,
4
]. We use he implemen a ions om
he PMCMR R package [
12
]. These es s we e chosen as he da a
is no no mal dis ibu ed, and is also he e oscedas ic (i.e., g oup
a iances a e no equal). Hence, pa ame ic es p ocedu es ha
assume homoscedas ic (equal a iance), no mal dis ibu ed da a
a e unsui ed. No e, ha non-pa ame ic es s a e no ee o as-
sump ions. In ac , he K uskal-Wallis es assumes ha he da a a e
andom samples, s a is ically independen wi hin each g oup and
be ween g oups, and ha e an o dinal measu emen scale [
3
, p. 289].
These assump ions should hold o he op imiza ion pe o mance
esul s we conside . An o e iew o he analysis esul s can be
ound in Table 2.
I is clea ly isible ha , as expec ed, all single h eaded base-
line implemen a ions pe o m wo s on each es unc ions. This
con i ms ha pa alleliza ion is necessa y o e icien ly op imize
in an en i onmen whe e mo e han one unc ion e alua ion is
possible a he same ime. In he i s se o esul s wi h
n=
3
pa allel e alua ions, he ESP p oblem is bes sol ed by me hods
which apply bo h EI and BP plus an addi ional me hod o speci y
he hi d poin o be e alua ed. In e es ingly, he e seem o be no
signi ican di e ences be ween me hods o de e mining he hi d
poin (EA, SF, o andom sampling). On he s anda d es unc ions
he bounded e sion o q-EI sco ed bes .
Ye , he ai ness o a compa ison o his bounded app oach is
a guable. As i s es s showed ha he o iginal implemen a ion o
he EA-op imized q-EI c i e ion yielded unsa is ac o y esul s, he
p oblem was u he in es iga ed. In many o he expe imen s, i
was obse ed, ha q-EI only posi ioned one o wo design poin s
in a easonable sea ch a ea. The o he design poin s we e a he
a sp ead ou in o egions whe e he k iging model is es ima ing
maximum unce ain y. Thus, q-EI o en yields poin s ha lie a
ou side he p e iously sampled egions. This was he main eason
o in oducing bound cons ain s o he q-EI implemen a ion. In
his algo i hm a ian , he EA which is used o op imize he q-
EI c i e ion is limi ed o a sea ch in a bounded a ea. This sol ed
he basic issues q-EI was acing and yielded much be e esul s.
Howe e , i has o be conside ed ha p oblem bounds a e no
always known a p io i, and ha he o he SMBO implemen a ions
we e no subjec o bounds (wi h he excep ion o he ini ial design
gene a ion ha is sha ed by all me hods). The s iking pe o mance
o q-EI wi h bounds and
n=
3should he e o e be conside ed wi h
ca e.
Gi en i e o mo e e alua ions in pa allel, scaling seems o be-
come an issue in IPI and q-EI as hei mean ank d ops. He e, SMBO
seems o deli e he bes esul s o he ESP-p oblem, Ras igin,
B anin and Ha mann. On he Rosenb ock and Col ille unc ions,
q-EI consis en ly deli e s he bes esul s.
Figu es 4 and 5 a e aken as examples o p esen esul s o a
gi en es unc ion and speci ic alue o
n
pa allel e alua ions in he
o m o box plo s. I can be obse ed, ha o la ge
n
, he synch o-
nous and asynch onous e sion o SMBO+EA a e no signi ican ly
dis inguishable om one ano he . Thus, since he asynch onous
e sion yields less o e all compu a ion ime, i should be p e e ed.
In cases whe e
n<
10, he synch onous model ou pe o med he
asynch onous one. The e o e, a close analysis o he compu a ion
ime educ ion h ough he asynch onous model is equi ed in o -
de o choose he bes app oach. Las ly, Figu e 5 e eals ha on he
Compa ison o Pa allel Su oga e-Assis ed Op imiza ion App oaches GECCO ’18, July 15–19, 2018, Kyo o, Japan
EA singleCo e
K ig−BP
K ig−EI
K.BP+K.EI
EA−nCo es
K.BP+K.EI+Rnd.Smpl.
K.BP+K.EI+LHS
SMBO+EA−async
SMBO+EA+SF−async
SMBO+EA−sync
SMBO+EA+SF−sync
IPI−n−co es
q−EI
q−EI−Bounded
5
10
20
50
100
objec i e unc ion alue
Pa allel e als: 15 Tes unc ion: Ras .10D
8574322111146 6
Figu e 4: Boxplo showing he op imiza ion esul s on he
10 dimensional as igin unc ion. In hese expe imen s 15
unc ion e alua ions we e possible in pa allel. Red numbe s
a he bo om indica e he gi en ank based on pai wise
mul iple-compa ison es s. NAs due o q-EI implemen a ion
on ESP p oblem, desc ibed in Sec ion 5.3.
ESP p oblem wi h
n=
15, SMBO+EA does no ou pe o m a simple
model- ee pa allelized EA.
The same is ue o
n=
10, bu no o smalle
n
. This beha -
io may be explained by he na u e o he SMBO+EA hyb id. The
numbe o solu ions sugges ed by he model is cons an (he e: wo),
whe eas he numbe o solu ions sugges ed by he EA ope a o s
inc ease wi h
n
. Hence, he hyb id will end o beha e mo e sim-
ila o a model- ee EA o la ge
n
. This indica es ha i may be
necessa y o he model-based pa o scale wi h
n
, oo, o p o ide
be e pe o mance. Hence, i may be p o i able o combine i wi h
he q-EI o IPI app oaches.
7 SUMMARY AND OUTLOOK
In conclusion, he gi en esul s show ha SMBO is e y well ap-
plicable o pa allelized se e en i onmen s. Howe e , he gi en
esul s indica e ha scaling o a high le el o pa alleliza ion is s ill
an issue in cu en s a e o he a SMBO algo i hms. Mo e u u e
esea ch in he ield o pa alleliza ion o expensi e o e alua e
objec i e unc ions is equi ed.
Fo he SMBO+EA algo i hm design, many possibili ies o u u e
imp o emen s exis . Fi s ly, selec ion c i e ia o choosing which EA
gene a ed indi iduals shall be e alua ed on he objec i e unc ion
should be compa ed and implemen ed. Tha is, he su oga e model
may be employed o selec he mo e p omising o he candida e
solu ions p oposed by he EA ope a o s.
EA singleCo e
K ig−BP
K ig−EI
K.BP+K.EI
EA−nCo es
K.BP+K.EI+Rnd.Smpl.
K.BP+K.EI+LHS
SMBO+EA−async
SMBO+EA+SF−async
SMBO+EA−sync
SMBO+EA+SF−sync
IPI−n−co es
q−EI
q−EI−Bounded
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
objec i e unc ion alue
Pa allel e als: 15 Tes unc ion: ESP
544313311112
NA NA
Figu e 5: Op imiza ion esul s on he high dimensional ESP-
p oblem. In he expe imen s 15 unc ion e alua ions we e
possible in pa allel. Red numbe s a he bo om indica e he
gi en ank based on pai wise mul iple-compa ison es s.
Also, a swi ching c i e ion be ween he synch onous and asyn-
ch onous SMBO+EA a chi ec u e should lead o be e pe o mance.
In he beginning o any op imiza ion un, ew da a poin s a e a ail-
able o i a su oga e model. Thus, each da a poin is essen ial o
model quali y. Due o he low amoun o da a a his poin , model
aining and op imiza ion equi es less ime. Howe e , wi h he
g owing amoun o e alua ed candida e solu ions, he impac o
each new candida e solu ion on he model quali y diminishes and
compu a ional cos o he model inc eases. Thus s a ing wi h he
synch onous implemen a ion and swi ching o he asynch onous
one in he la e op imiza ion p og ess should yield be e pe o -
mance.
REFERENCES
[1]
Thomas Ba z-Beiels ein and Ma in Zae e e . 2017. Model-based me hods o
con inuous and disc e e global op imiza ion. Applied So Compu ing 55 (2017),
154 – 167. h ps://doi.o g/10.1016/j.asoc.2017.01.039
[2]
Be nd Bischl, Simon Wessing, Nadja Baue , Klaus F ied ichs, and Claus Weihs.
2014. MOI-MBO: Mul iobjec i e In ill o Pa allel Model-Based Op imiza ion. In
Lea ning and In elligen Op imiza ion, Panos M. Pa dalos, Mau icio G.C. Resende,
Ch ysa is Vogia zis, and Jose L. Wal e os (Eds.). Sp inge In e na ional Publishing,
Cham, 173–186.
[3]
William Jay Cono e . 1999. P ac ical Nonpa ame ic S a is ics, 3 d Edi ion. Wiley.
[4]
William Jay Cono e and Ronald L. Iman. 1979. On mul iple-compa isons p oce-
du es. Technical Repo Tech. Rep. LA-7677-MS. Los Alamos Sci. Lab.
[5]
Alexande Fo es e , Andy Keane, e al
.
2008. Enginee ing design ia su oga e
modelling: a p ac ical guide. John Wiley & Sons.
[6]
Da id Ginsbou ge , Rodolphe Le Riche, and Lau en Ca a o. 2010. K iging is
well-sui ed o pa allelize op imiza ion. In Compu a ional In elligence in Expensi e
Op imiza ion P oblems. Sp inge , 131–162.
[7]
Raphael T. Ha ka, Diane Villanue a, and Ani ban Chaudhu i. 2016. Pa al-
lel su oga e-assis ed global op imiza ion wi h expensi e unc ions – a su -
ey. S uc u al and Mul idisciplina y Op imiza ion 54, 1 (01 Jul 2016), 3–13.