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.