Model-based Methods for Continuous and Discrete Global Optimization

CIplus
Band 8/2016
Model-based Me hods o Con inuous
and Disc e e Global Op imiza ion
Thomas Ba z-Beiels ein, Ma in Zae e e
Model-based Me hods o Con inuous and Disc e e
Global Op imiza ionI
Thomas Ba z-Beiels ein∗, Ma in Zae e e
TH K¨oln, Facul y o Compu e Science and Enginee ing Science, S einm¨ulle allee 1, 51643
Gumme sbach, Ge many
Abs ac
The use o su oga e models is a s anda d me hod o deal wi h complex, eal-
wo ld op imiza ion p oblems. The i s su oga e models we e applied o con-
inuous op imiza ion p oblems. In ecen yea s, su oga e models gained impo -
ance o disc e e op imiza ion p oblems. This a icle, which consis s o h ee
pa s, akes ca e o his de elopmen . The i s pa p esen s a su ey o model-
based me hods, ocusing on con inuous op imiza ion. I in oduces a axonomy,
which is use ul as a guideline o selec ing adequa e model-based op imiza ion
ools. The second pa p o ides de ails o he case o disc e e op imiza ion
p oblems. He e, six s a egies o dealing wi h disc e e da a s uc u es a e in-
oduced. A new app oach o combining su oga e in o ma ion ia s acking
is p oposed in he hi d pa . The implemen a ion o his app oach will be
a ailable in he open sou ce R package SPOT2. The a icle concludes wi h a
discussion o ecen de elopmen s and challenges in bo h applica ion domains.
Keywo ds: Su oga e, Disc e e Op imiza ion, Combina o ial Op imiza ion,
Me amodels, Machine lea ning, Expensi e op imiza ion p oblems, Model
managemen , E olu iona y compu a ion
IThis is an ex ended e sion o he con ibu ion [1]
∗Co esponding au ho . Phone: +49 2261 8196 6391
Email add esses: [email p o ec ed] (Thomas Ba z-Beiels ein),
[email p o ec ed] (Ma in Zae e e )
P ep in submi ed o Applied So Compu ing No embe 13, 2016
1. In oduc ion
Model-based op imiza ion (MBO) plays a p ominen ole in oday’s modeling,
simula ion, and op imiza ion p ocesses. I can be conside ed as he mos e icien
echnique o expensi e and ime-demanding eal-wo ld op imiza ion p oblems.
E alua ing a cheape su oga e model ins ead o he expensi e objec i e unc-5
ion may signi ican ly educe ime, space, and compu ing cos s. Especially in
he enginee ing domain, MBO is an impo an p ac ice. Recen ad ances in
compu e science, s a is ics, and enginee ing in combina ion wi h p og ess in
high-pe o mance compu ing p o ide ools o handling p oblems, which we e
conside ed unsol able only a ew decades ago.10
The i s pa o his a icle p esen s a su ey o MBO o con inuous and
disc e e global op imiza ion p oblems. Ou goal is o show connec ions and
concep ual di e ences be ween hese wo domains and o discuss p ope ies o
s a e-o - he a MBO algo i hms. Despi e i s g owing ele ance, con ibu ions
o he disc e e domain ha e been la gely dis ega ded and we e lis ed as open15
challenges. Fo example, Simpson e al. [2] p esen an in e es ing his o y o
de elopmen in he ield. Ano he su ey o me amodeling echniques, which
ocuses on he p ac i ione s pe spec i e, is gi en by Wang and Shan [3]. Bo h
o hese su eys men ion p oblems om he disc e e domain, bu do no discuss
hem in dep h.20
The e m global op imiza ion (GO) will be used o algo i hms and p oblems
whe e he goal is o ind and explo e global op imal solu ions wi h complex,
mul imodal objec i e unc ions [4]. Fu he mo e, we will ocus on GO p ob-
lems which belong o he class o di icul (expensi e) black-box unc ions, i.e.,
unc ions o which he analy ic o m is unknown. Thus, nea ly no s uc u al25
in o ma ion (e.g., numbe o local ex ema, de i a e in o ma ion) is a ailable.
This se ing a ises in many eal-wo ld sys ems when he explici o m o he
objec i e unc ion is no eadily a ailable, e.g., i he use has no access o he
sou ce code o a simula o . Su oga es a e a popula choice, because he ime
equi ed o building he su oga e is negligible compa ed o he e alua ion o 30
2
he eal-wo ld unc ion .
The emainde o his a icle is s uc u ed as ollows. Sec ion 2 in oduces
a axonomy o sea ch algo i hms and p esen s basic de ini ions. A e in oduc-
ing ins ance-based s ochas ic sea ch algo i hms, Sec ion 3 desc ibes modeling
app oaches o s ochas ic algo i hms. We di e en ia e be ween models ha use35
a dis ibu ion and models ha use an explici su oga e model. Sec ion 4 in o-
duces model-based op imiza ion, which is he i s choice o many op imiza ion
p oblems in indus y. P oblems and algo i hms om he disc e e, combina o ial
domain a e hen in oduced in Sec ion 5. Using wo MBO algo i hms, namely
E oLS and SPO, ecen ends and new de elopmen s in MBO a e desc ibed in40
Sec ion 6. Finally, a summa y and an ou look a e gi en in Sec ion 7, including
impo an challenges in con inuous and disc e e MBO.
2. Taxonomy and De ini ions
We conside he con inuous op imiza ion p oblem gi en by
Minimize: (~x) subjec o ~a ≤~x ≤~
b,
whe e :Rn→Ris e e ed o as he objec i e unc ion and ~a and ~
bdeno e
he lowe and uppe bounds o he sea ch space, espec i ely. The objec i e45
unc ion is assumed o be an expensi e- o-e alua e black-box.
In he disc e e case, ~x ∈Rnis no ue anymo e. Ra he , a candida e solu-
ion is some disc e e da a s uc u e, o objec . Typical disc e e da a s uc u es
include, e.g., o dinal in ege s, ca ego ical a iables, bina y a iables, pe mu a-
ions, s ings, ees o g aphs in gene al. In mos o hese disc e e cases, bounds50
~a and ~
ba e also no equi ed anymo e.
F om he algo i hmic pe spec i e, his su ey ocuses on sea ch heu is ics,
which a e mos ly implemen ed using s ochas ic o andom p ocedu es. De e -
minis ic, exac GO algo i hms, i.e., algo i hms p o iding heo e ical gua an ees
ha he a ained solu ion is he global one wi hin some p e-speci ied ole ance,55
a e no u he discussed [5]. The e ms “ andom” and “s ochas ic” will be used
synonymously in he emainde o his a icle.
3

Global op imiza ion
[I]
De e minis ic
[II]
S ochas ic
[II.1]
Ins ance
[II.2]
Model
[II.2.1]
Dis ibu ion
[II.2.2]
Su oga e model
[II.2.2.2]
Mul i- ideli y
[II.2.2.3]
Ensemble su oga e
[II.2.2.1]
Single su oga e
Figu e 1: An essen ial axonomy o model-based app oaches in GO. This axonomy is appli-
cable o con inuous and disc e e GO p oblems.
S ochas ic sea ch algo i hms can u he be ca ego ized as ins ance-based
o model-based algo i hms [6]. Fu he mo e, he e a e basically wo model-
based app oaches: (a) dis ibu ion-based models and (b) su oga e models. We60
conside h ee impo an ep esen a i es o su oga e model based op imiza ion:
(i) Single su oga e based op imiza ion uses one model o accele a ing he sea ch
p ocess, (ii) mul i- ideli y me amodeling uses se e al models o he same eal
sys em and plays an impo an ole in compu a ional luid dynamics (CFD)
and ini e elemen modeling (FEM) based simula ion and op imiza ion, and (iii)65
ensemble su oga e based op imiza ion combines wo o mo e di e en su oga e
models. This ca ego iza ion (o axonomy) o GO algo i hms is summa ized in
Figu e 1.
Typical si ua ions, which may occu in MBO, a e illus a ed in Figu e 2.
4
Real p ocess
CFD model
Real p ocess
Op imi-
za ion
Op imi-
za ion
Real p ocess
CFD model
Op imi-
za ion
K iging model
Real p ocess
CFD model
Op imi-
za ion
Coa se g ained
CFD model
Real p ocess
K iging model
Op imi-
za ion
A B C D E
Figu e 2: Su oga e model based op imiza ion. Do ed lines deno e he da a low, which is used
o he model building. Solid lines ep esen he op imiza ion loop. Si ua ion A illus a es an
op imiza ion loop wi hou any model. In si ua ion B, a CFD model is used o accele a e he
e alua ion o he complex eal-wo ld unc ion. K iging is used as a su oga e o accele a e his
e alua ion in si ua ion C. In addi ion o a ine g ained CFD model, a coa se g ained model is
used in he mul i- ideli y app oach (si ua ion D). Models can be s acked as shown in si ua ion
E, whe e a K iging model (su oga e) is used o accele a e he CFD simula ions.
K iging is a equen ly employed ype o su oga e model [7]. Figu e 2 shows70
(in si ua ion C) ha he K iging model can be cons uc ed as a su oga e model
o a complex eal-wo ld p ocess. Fu he mo e, a K iging model can be used as a
su oga e model o he ela i ely complex CFD simula ion model (as illus a ed
in si ua ion E). Some au ho s de ine a model as a di ec abs ac ion o eal-
wo ld p ocesses and a su oga e as a second abs ac ion, which highligh s he75
p ope ies o he model i sel . Following hese de ini ions, he K iging model in
si ua ion C is a model, whe eas he K iging model in si ua ion E is a su oga e.
As his has he po en ial o con usion, we will no use his ca ego iza ion.
Ins ead, we will use he e m “model” o a simpli ied abs ac ion o a com-
plex objec , whe eas he e m “su oga e” will be used o he subse o models,80
which can be ep esen ed by an explici unc ional ela ionship [8, 9]. Usu-
ally, a da a-d i en p ocess, which comp ehends he ollowing wo s eps, is used
o cons uc ing a su oga e: (i) gene a ion o da a h ough sampling and (ii)
ma hema ical unc ion i ing. The e ms “su oga e”, “su oga e model”, and
5
“me amodel” will be used synonymously in he ollowing.85
3. S ochas ic Sea ch Algo i hms
An i e a i e sea ch algo i hm ha uses a s ochas ic p ocedu e o gene a e
he nex i e a e is e e ed o as a s ochas ic sea ch algo i hm. The nex i e a e
can be a candida e solu ion o he GO o a p obabilis ic model, whe e solu ions
can be d awn om. S ochas ic sea ch algo i hms a e conside ed obus and easy90
o implemen , because hey do no depend on any s uc u al in o ma ion o he
objec i e unc ion, such as g adien in o ma ion o con exi y. This ea u e is
one o he main easons o he popula i y o s ochas ic sea ch in he domain o
GO.
Ins ance-based algo i hms ([II.1]) main ain a single solu ion,~x, o popula-95
ion,P( ), o candida e solu ions. The i e a ion o ime s ep is deno ed as .
The cons uc ion o new candida e solu ions depends explici ly on he p e i-
ously gene a ed solu ions. Simula ed annealing [10], e olu iona y algo i hms
(EAs) [11, 12], and abu sea ch [13] a e p ominen ep esen a i es o his ca e-
go y. The key elemen s o ins ance-based algo i hms a e shown in Algo i hm 1.100
This pseudo code ocuses on he undamen al s uc u e o he algo i hm and
skips some implemen a ion de ails, e.g., P( ) ep esen s he popula ion a ime
s ep and he co esponding unc ion alues.
Algo i hm 1 Ins ance-based algo i hm
1: = 0. P( ) = Se Ini ialPopula ion().
2: E alua e(P( )) on .
3: while no Te mina ionC i e ion() do
4: Gene a e new solu ions P0( ) acco ding o andom mechanism.
5: E alua e(P0( )) on .
6: Selec he nex popula ion P( + 1) om P( )∪P0( ).
7: = + 1.
8: end while
6
4. MBO: Model-based Algo i hms
Model-based op imiza ion algo i hms ([II.2]) gene a e a popula ion o new105
candida e solu ions P0( ) by exploi ing a model (su oga e o dis ibu ion). The
model e lec s s uc u al p ope ies o he unde lying ue unc ion . Model-
based op imiza ion algo i hms a e based on he idea ha by adap ing he model,
he sea ch is di ec ed in o egions wi h imp o ed solu ions.
One o he key ideas in MBO is he eplacemen o expensi e, high ideli y,110
ine g ained unc ion e alua ions, (~x), wi h e alua ions, ˆ
(~x), o an adequa e
cheap, low ideli y, coa se g ained model, M. An addi ional bene i can seen in
he smoo hening p ope y o he cheap model, because i uses an app oxima ion
o he possibly noisy da a [2].
This sec ion desc ibes wo di e en MBO app oaches: (i) dis ibu ion based115
([II.2.1]) and (ii) su oga e-model based op imiza ion ([II.2.2.]).
4.1. Dis ibu ion-based App oaches
I he me amodel is a dis ibu ion, he mos basic o m o an MBO can be
implemen ed as shown in Algo i hm 2:
Algo i hm 2 Dis ibu ion-based algo i hm
1: = 0. Le p( ) be a p obabili y dis ibu ion.
2: while no Te mina ionC i e ion() do
3: Randomly gene a e a popula ion o candida e solu ions P( ) om p( ).
4: E alua e(P( )) on .
5: Gene a e upda ed dis ibu ion p( + 1) wi h popula ion (samples) P( ).
6: = + 1.
7: end while
Dis ibu ion-based algo i hms gene a e a sequence o i e a es (p obabili y
dis ibu ions) {p( )}wi h he hope ha
p( )→p∗as → ∞,
7
ally, su oga e models a e assessed and chosen acco ding o hei es ima ed ue
e o [54, 55, 2]. Gene ally, a aining a su oga e model ha has minimal e o is290
he desi ed ea u e. The mean absolu e e o (L1 no m), he mean squa e e o
(MSE) (o i s pendan he oo mean squa e e o (RMSE)) a e commonly used
as pe o mance me ics. Me hods om s a is ics, s a is ical lea ning [56], and
machine lea ning [57], such as he simple holdou app oach, c oss- alida ion,
and he boo s ap a e also impo an in his con ex .295
Se e al selec ion and combina ion mechanisms o su oga es we e de eloped
in he las yea s. A simple app oach de e mines he bes model, i.e., he model
wi h he smalles p edic ion e o , and de e mines he nex candida e solu ion
based on ha model. Al e na i ely, candida e solu ions om se e al models
can be combined. Ze pa e al. [58] use mul iple su oga e models and build an300
adap i e weigh ed a e age model o he indi idual su oga es. Goel a al. [59]
explo e he possibili y o using he bes su oga e model o a weigh ed a e age
su oga e model ins ead o one single model. Model quali y, i.e., he e o s in
su oga es, is used o de e mine he weigh s assigned o each model. Sanchez e
al. [60] p esen a weigh ed-sum app oach o he selec ion o model ensembles.305
The models o he ensemble a e chosen based on hei pe o mance and he
weigh s a e adap i e and in e sely p opo ional o he local modeling e o s.
Tenne and A m ield [61] p opose a su oga e-assis ed meme ic algo i hm which
gene a es accu a e su oga es using mul iple c oss- alida ion es s.
Huang e al. [62] use se e al simula ion models o a semiconduc o manu-310
ac u ing sys em. They p opose an o dinal ans o ma ion o u ilize he esul s
om se e al cheap models. The unc ion alues o all solu ion candida es is
e alua ed on e e y cheap model and he indi iduals a e anked. The au ho s
obse e ha despi e he big bias in he esul s om he cheap models, he el-
a i e o de among solu ions is ac ually qui e accu a e. This o de can be used315
o accele a e he selec ion p ocess in EAs signi ican ly. To educe a iabili y
and bias in he esul s om he cheap models, he au ho s apply an op imal
compu ing budge alloca ion scheme.
Mul iple models can also be used o pa i ion he sea ch space. The eed
14

Gaussian p ocess app oach uses eg ession ees o pa i ion he sea ch space320
in o sepa a e egions and o i local GP su oga es in each egion [63]. Nelson
e al. [64] p opose an algo i hm, which c ea es a ee-based pa i ioning o an
ae odynamic design space and employs independen K iging su aces in each
pa i ion. Couckuy e al. [65] p opose o combine an e olu iona y model selec-
ion (EMS) algo i hm wi h he EI c i e ion in o de o dynamically selec he325
bes pe o ming su oga e model ype a each i e a ion o he EI algo i hm.
5. Su oga e Models in Disc e e Op imiza ion
Compa ed o hei equen use o eal- alued p oblem domains, su oga e
model d i en app oaches a e ela i ely sca ce in combina o ial o mixed op i-
miza ion [28]. Disc e e p oblems deal, e.g., wi h o dinal in ege s, ca ego ical330
(quali a i e) a iables, pe mu a ions, s ings, ees, o o he g aph based da a
s uc u es. They may be mixed among hemsel es, o mixed wi h con inuous
a iables. O dinal in ege a iables can o en be handled qui e simila ly o eal
alued a iables. O he s, like ees, a e oo complex o be easily ep esen ed by
nume ic ec o s.335
Few expensi e, eal-wo ld combina o ial op imiza ion p oblems ha e been
published, e.g., in he enginee ing domain [66, 67, 68, 69], bioin o ma ics [70], o
da a science [71]. No all o hem make use o su oga e models. This sca ci y is
unlikely due o a lack o p oblems in his ield. Ra he , he a ailabili y o sui able
me hods (i.e., su oga e models, ca ego y [II.2.2]) is no well known o hese340
me hods a e no easily accessible o expe s in po en ial applica ion domains.
Thus, we p o ide a su ey o su oga e modeling me hods o combina o ial,
disc e e p oblems. The gene al axonomy o hese me hods is he same as o
he con inuous case, which was illus a ed in Figu e 1.
5.1. S a egies o Dealing wi h Disc e e S uc u es345
Table 1 p esen s a abula ed o e iew o he li e a u e on disc e e, su oga e
model-based op imiza ion. This o e iew p esen s impo an s epping s ones
15
Table 1: O e iew o su oga e models in combina o ial op imiza ion. Column da a lis s da a
ype: Mixed (mix), o dinal (o d), ca ego ical (ca ), bina y (bin), pe mu a ion (pe ), signed
pe mu a ion (-pe ), ees ( e), o he (o h). Column slis s he s a egy, see Sec ion 5.1. Col-
umn dim lis s he dimensionali y o he p oblem, whe e applicable. Abb e ia ions in oduced
in he able: gene ic algo i hm (GA), non-domina ed so ing gene ic algo i hm II (NSGA2),
simula ed annealing (SA), a i icial neu al ne wo ks (ANN), an colony op imiza ion (ACO),
mul i-s a local sea ch (MLS). This able is con inued on page 17.
da a STR model op imize cos budge dim opics e .
mix,
ca , o d
1,3 K iging,
T ee
isual,
s a is ical
analysis
high ≤100 2, 9 pa ame e
uning
[72]
mix,
o d, ca
6 RBFN ES low /
∼high
560 /
280
15 /
23
benchma k,
medical image
analysis
[73]
mix,
o d, ca 3,6
Random
Fo es ,
K iging
MLS ∼high - 4-76 algo i hm uning [74]
mix
bin, ca 6RBFN +
clus e
GA low 2,000 12 benchma k,
chemical indus y
[75]
mix,
o d, ca
4 SVM NSGA2 ? 2,000 10 FEM,
mul i c i e ia
[76]
and in e es ing applica ions in he ield, hus showcasing he de elopmen . Fo
a mo e ex ensi e able we e e o he abula o e iew in he supplemen al ma-
e ial o his a icle1. In Table 1, he employed modeling s a egies, model ypes,350
op imize s, and p oblem- ela ed de ails a e speci ied. The able lis s wo ks on
(mixed) in ege p oblems, bina y ep esen a ions, pe mu a ion p oblems, ee
s uc u es, and o he ep esen a ions.
To deal wi h modeling in combina o ial sea ch spaces, a se o six s a egies
(STR) can be iden i ied in he li e a u e, which a e e e enced in column “STR”355
o Table 1:
1The abula o e iew will be kep up- o-da e on he second au ho ’s home page h ps:
//ma inzae e e .de/?page_id=134
16
Table 1: con inued
da a STR model op imize cos budge dim. opics e .
bin 1/3 ANN SA high ? 16 eal wo ld,
pump posi ioning
[77]
bin 6 RBFN GA low dim210–25 NK-Landscape [78]
-pe 2 cus om b u e
o ce
high 28 6 eal wo ld:
weld sequence
[66]
pe 6 RBFN GA low 100 30–32 benchma k [79]
pe 6 K iging GA low 100 12–32 benchma k [80]
pe 6 K iging ACO low 100 -
1,000
50–100 benchma k,
uning
[81]
e 6 RBFN GA low 100 symbolic eg ession [82]
e 5,6 k-NN GA high 30,000 pheno ypic simila i y,
gene ic p og amming
[83]
e 5 Random
Fo es
GA low 15,000 benchma k,
gene ic p og amming
[84]
STR-1 The nai e app oach: As long as he da a can s ill be ep esen ed as a
ec o (bina y a iables, in ege s, ca ego ical da a, pe mu a ions) he
modeling echnique may simply igno e he disc e e s uc u e, and wo k
as usual. A po en ial d awback o his app oach is, ha he model’s360
inpu space may ha e la ge a eas o edundancy. O else, his app oach
may c ea e la ge a eas o in easible solu ions. Depending on he op i-
mize , his may de e io a e pe o mance compa ed o mo e sophis ica ed
app oaches.
STR-2 Cus om modeling: A speci ic modeling solu ion is ailo ed o i he365
needs o a ce ain applica ion. On he one hand, his p ocedu e can be
e y e icien , because i in eg a es signi ican p io knowledge in o he
model. On he o he hand, i may in oduce bias and may be ha d o
ans e o o he applica ions o da a s uc u es. This app oach is no
applicable o ue black-box p oblems.370
17
STR-3 Inhe en ly disc e e models: Some models al eady a e disc e e in hei
own design. One example a e ee-based models, like eg ession ees
o andom o es s. On he one hand, hese models a e easy o use, be-
cause no o only mino adap a ions a e necessa y. On he o he hand,
his s a egy may ail i he disc e e s uc u es become mo e complex375
(e.g., ees o o he g aph s uc u es). Also, such models may no al-
ways p o ide desi ed ea u es, e.g., he nice p ope ies de i ed om he
unce ain y es ima es o a K iging model.
STR-4 Mapping: O en, disc e e a iables o s uc u es may be mapped o
a mo e easily handleable ep esen a ion. Examples o his app oach380
a e he andom key mapping o pe mu a ions o dummy a iables o
ca ego ical a iables. Simila ly o s a egy STR-1, his app oach may
in oduce edundancy o in easibili y in o he da a s uc u e. Es ab-
lishing easonable mappings becomes ha de o da a s uc u es wi h
inc easing complexi ies.385
STR-5 Fea u e ex ac ion: Ins ead o di ec ly modeling he ela ion be ween an
objec (o i s ep esen a ion) and i s quali y, i is possible o calcula e
eal- alued ea u es o he objec s. Fo example, some ea u es o a
ee o g aph can be ex ac ed (pa h leng hs, ee dep hs, e c.). These
nume ic ea u es can hen be modeled wi h s anda d echniques.390
STR-6 Simila i y-based modeling: Whe e a ailable, measu es o (dis)simila i y
may be used o eplace con inuous measu es ha a e, e.g., employed
in simila i y-based models like k-nea es neighbo (k-NN), suppo ec-
o machines (SVM), adial basis unc ion ne wo ks (RBFN), o K ig-
ing. While his app oach is po en ially e y powe ul, a d awback is395
he equi emen o p ope measu es. This may be p oblema ic i hese
measu es ha e o ul ill u he equi emen s, like de ini eness.
The p esen ed six s a egies a e no necessa ily mu ually exclusi e. Depending
on he poin o iew, a mapping app oach can be in e p e ed as simila i y-
18
based app oach, o ice e sa. O else, ea u es may be ex ac ed and used o 400
modeling, while a he same ime applying some inhe en ly disc e e app oach
o he da a. Thus, some me hods may ei he combine se e al s a egies, o else,
can be classi ied as belonging o se e al s a egies.
None o he six s a egies can be b oadly p e e ed o he o he s. E en he
nai e app oach may be adequa e, i he p oblem is su icien ly simple. P oblem405
ype and applica ion es ic ions will go e n he selec ion o a sui able app oach.
The subsequen sec ions p esen key cha ac e is ics o s a egies conside ed by
he au ho s o be mos ele an .
5.2. Cus om Models
One way o using su oga e-models o combina o ial p oblems is o employ410
cus omized, applica ion speci ic solu ions (STR-2). An example is he wo k by
Vou chko e al. [66]. They op imize a weld sequence, which is ep esen ed as
a signed pe mu a ion, and ind a nea -op imal welding sequence by e alua ing
only 28 ou o 46,080 possible sequences. The su oga e model eplaces an
expensi e FEM by es ima ing he in luence o each indi idual elemen in he415
weld sequence, based on he obse a ions made in p e iously es ed sequences.
In addi ion o he unc ion alues, he su oga e also exploi s in e media e e-
sul s ha e lec he impac o indi idual sequence-elemen s, depending on hei
posi ion in he weld sequence. Exploi ing hese in e media e esul s is a clea
ad an age o e mo e simple, unc ion- alue d i en app oaches. On he o he 420
hand, he applicabili y o his model is es ic ed o his speci ic se up and
canno be easily ans e ed o comple ely di e en applica ion a eas. The su -
oga e modeling app oach in [66] has since been adap ed and applied o a gi h
weld pa h op imiza ion p oblem by Asadi and Goldak [67]. Due o he na u e
o hei p oblem (numbe o weld sub-passes, o a ional symme y) only 48 se-425
quences a e possible. They e alua ed 15 o hese 48 sequences o ind an op imal
solu ion. Nguyen e al. [85] p opose o use simpli ica ions o he a ge unc ion
(a simula ion model o job shop scheduling) as a su oga e model in gene ic
p og amming. These applica ions show ha cus om models a e bene icial, i
19

domain knowledge is a ailable.430
5.3. Mapping
As s a ed in Sec ion 5.1, a equen ly chosen app oach is mapping om he
mo e complex, disc e e space o ano he mo e easy o handle space (STR-4).
Classical eg ession p o ides an es ablishes mapping app oach o dealing wi h
disc e e, ca ego ical pa ame e s, which is based on dummy a iables and con-435
as s. A ca ego ical a iable can be mapped o a se o dummy a iables, whe e
each dummy ep esen s a single le el o he o iginal a iable. This is he same as
he one-ho encoding, i.e., only one o se e al bi s can be 1. The nle els o he
ca ego ical a iable a e mapped o nbina y a iables. The bina y a iables a e
s ill disc e e, bu can be handled by s anda d eg ession app oaches. Else, one440
can map o (n−1) bina ies: The one missing le el is ep esen ed by all dummy
a iables being ze o. This is essen ially a con as . Con as a iables ep e-
sen a compa ison be ween di e en le els. Clea ly, bo h app oaches inc ease
he numbe o model pa ame e s. Dummy a iables o con as s a e p obably
among he mos equen ly applied me hods o deal wi h ca ego ical a iables,445
e.g., in he con ex o he esponse su ace me hodology [86].
Ano he example o a mapping app oach is he andom key mapping de-
eloped by Bean [87]. Random keys a e ec o s o eal numbe s om a ixed
in e al, e.g., he in e al [0,1]. To map om his eal pa ame e space o pe -
mu a ion ep esen a ions, he andom key alues a e simply so ed. Random450
keys we e o iginally de eloped o enable he applica ion o con inuous, model-
ee gene ic algo i hms o pe mu a ion p oblems. They ha e since been used
in p obabilis ic models which a e pa o EDAs, see also Sec ion 4.1 and 5.6.
No able d awbacks a e edundancy in he eal alued pa ame e space as well
as he non-bijec ion cha ac e o he mapping.455
5.4. Fea u e Ex ac ion
O he ew app oaches ha deal wi h modeling o ee- ep esen a ions (sym-
bolic eg ession, gene ic p og amming), many use ea u e ex ac ion o model-
ing. Hildeb and and B anke [83] ex ac ea u es o he pheno ypic beha io
20
o e ol ed dispa ching ules o job shop scheduling. He e, hese ea u es a e460
based on he ule decisions o a small se o e e ence si ua ions. The Euclidean
dis ance is compu ed on hese ea u es and is hen employed in a k-NN su o-
ga e model. F om a di e en poin o iew, his p ocess can as well be seen
as a pa o he (dis-)simila i y calcula ion, and hence pa o s a egy STR-6,
a he han STR-5. Hildeb and and B anke compa e he pheno ypic app oach465
o a geno ypic dis ance measu e: he s uc u al Hamming dis ance. The phe-
no ypic ea u e ex ac ion app oach has since also been in es iga ed by Nguyen
e al. [88], who imp o ed handling o eplica ions and he selec ion scheme.
Pila and Ne uda [84] ake a sligh ly di e en app oach. They ex ac ea-
u es om he geno ype o candida e solu ions, e.g., he dep h o he ee,470
summa izing s a is ics o nume ic cons an s in he ee, o he ca dinali y o
ce ain a gumen s in he ee.
Some o hese ecen app oaches use a a he simple su oga e model, i.e.,
k-NN [83, 88]. This is igh ly linked o he compa a i ely high e alua ion bud-
ge s ( ens o housands). Mo e complex models migh become oo expensi e475
when da a-sizes g ow o hese dimensions. On he o he hand, using such la ge
budge s may be necessa y due o he ex emely la ge sea ch spaces ha gene ic
p og amming is ypically dealing wi h. Compa ed o he mo e common, model-
ee gene ic p og amming app oaches, ew ens o housands o e alua ions a e
in ac a small budge .480
5.5. (Dis)simila i y based models
A p omising app oach ha ecen ly gained mo e ac ion is simila i y-based
modeling (STR-6). Fonseca e al. [89] de ined simila i y-based models as models
ha keep a memo y o solu ions and es ima e he pe o mance o new samples
by compa ing hem o ha memo y. Fonseca e al. lis i ness inhe i ance [90],485
i ness imi a ion [91, 27] and k-NN [92] as examples. They es a gene ic al-
go i hm suppo ed by a k-NN model on a se o nume ical, con inuous es
unc ions. Be na dino e al. [93] pe o m simila es s wi h a i icial immune
sys ems. In bo h cases Hamming and Euclidean dis ances a e used as mea-
21
su es o dissimila i y, showing ha his app oach does no depend on a speci ic490
measu e.
Howe e , he k-NN model is no able o p edic whe he o no a candida e
solu ion will p o ide imp o emen o e exis ing solu ions. Fo ha pu pose,
ano he se o simila i y o dis ance based models is o in e es : RBFN, SVM,
and K iging (Gaussian p ocess eg ession). Hemke [94] desc ibes in his Ph.D.495
hesis an app oach o deal wi h con inuous and o dinal in ege a iables, ap-
plied o elec ical enginee ing and wa e esou ce managemen p oblems. Thei
app oach is based on K iging, essen ially ea ing all pa ame e s wi h he same
dis ance unc ion, hence no di ec ly applicable o ca ego ical pa ame e s o
mo e complex ep esen a ions. Li e al. [73] p oposed an adap a ion o RBFNs.500
These adap a ions a e based on a weigh ed dis ance measu e, eplacing he
usual dis ance measu e employed in RBFN. Thei dis ance-based RBFN model
was es ed wi h mixed in ege op imiza ion p oblems. I has since been ap-
plied o a mul i objec i e building design op imiza ion p oblem by B ownlee
and W igh [95]. Mixed op imiza ion p oblems also a ise in algo i hm uning.505
In his con ex , Hu e [74] also used a K iging model wi h a Hamming dis ance
based co ela ion unc ion o handle ca ego ical a iables. A combina ion o
K iging and ee-based models called eed Gaussian p ocesses has been used
by Swile e al. [96]. They applied a eed Gaussian p ocess model, a K iging
model, and a smoo hing spline echnique o build su oga e models o mixed510
in ege p oblems. Coelho e al. [97] and He e a e al. [76] applied a ke nel-
based eg ession me hod o mixed- a iable op imiza ion p oblems. A di e en
app oach wi h RBFs o he case o a mixed (disc e e and con inuous) op imiza-
ion p oblem is aken by Baje and Holena [75]. Ins ead o c ea ing one RBFN
based on a weigh ed dis ance be ween candida e solu ions hey use Hamming515
dis ance o clus e he disc e e a iables, hen i a s anda d RBFN wi h he
con inuous a iables o each clus e .
Mo aglio and Ka an [78] adap ed an RBFN o a bi a y dis ance measu es
o model a bi a y combina o ial op imiza ion p oblems. Thei app oach has
also been applied o quad a ic assignmen p oblems [79]. A simila concep ual520
22
ex ension o K iging was in es iga ed by Zae e e e al. [80]. He e, K iging-
based EGO [30] showed posi i e esul s when applied o combina o ial p oblems.
Zae e e e al .[98] also showed ha maximum likelihood es ima ion (MLE) can
be used o e icien ly choose one measu e om a se o dis ance measu es.
An in es iga ion by C´ace es e al. [81] epo s nega i e esul s o he ap-525
plica ion o EGO o pe mu a ion p oblems. The e, an an colony op imiza ion
algo i hm was no ou pe o med by he K iging-based a ian o he same al-
go i hm. Smi h e al [71] desc ibe a s udy on ex emely high-dimensional es
ins ances, employing RBFN models. While he employed models showed some
p omise, a p oposed ensemble o models pe o med poo ly.530
The abo e modeling app oaches use dis ances and ke nels in a s anda d,
s aigh - o wa d way. Howe e , i is o en impo an o conside i ei he he
employed dis ances a e condi ionally nega i e semi-de ini e (CNSD) o posi i e
semi-de ini e (PSD). De ini eness is a equen equi emen o modeling me h-
ods based on dis ances o ke nels. Dealing wi h he possible inde ini eness o a535
unc ion is hence o u mos conce n. In ac , lack o de ini eness is one possible
sou ce o some p e iously obse ed nume ical p oblems, e.g., in [80, 98]. A ecen
s udy by Zae e e and Ba z-Beiels ein [99] deal wi h he issue o de ini eness
in he con ex o K iging based op imiza ion. They ans e and ex end me hods
om he ield o SVMs, which we e p e iously used o machine lea ning wi h540
s uc u ed da a, c. ., he su ey by Schlei and Tino [100]. While, o he bes
o ou knowledge, SVMs ha e a ely been used as su oga es in combina o ial
op imiza ion, hey ha e been applied o lea ning p oblems wi h combina o ial
da a (see e.g., [101, 102, 103]). Hence, hey a e a p omising choice.
Mos o he abo e e e ences make use o dis ance measu es in geno ype545
space. Fo he case o gene ic p og amming, Hildeb and and B anke [83] show,
ha a dis ance in pheno ype space may be an excellen choice, see also he
p eceding sec ion.
23
Summa izing, he con ibu ion o his a icle can be desc ibed as ollows: A
comp ehensible axonomy o MBO algo i hms o global op imiza ion p oblems
(Figu e 1) is p oposed. A su ey o SBO algo i hms, which includes he mos
ecen publica ions om con inuous and he combina o ial p oblem domains, is
gi en. Six s a egies o dealing wi h modeling in combina o ial sea ch spaces680
a e de eloped. Wo king p inciples o wo s a e-o - he-a SBO algo i hms we e
shown: (i) E oLS, which cons uc s a local me amodel o e e y new candida e
solu ion, and (ii) SPOT2, which uses a global ensemble engine o combine a
b oad a ie y o su oga e models. The su ey p esen ed in he i s sec ions
o his a icle as well as he examples in Sec ion 6 emphasize he end o685
ensemble based me amodels. Due o he eme ging- ield na u e o SBO, and
especially combina o ial SBO, se e al challenges emain o be sol ed. This
a icle concludes wi h a (subjec i e) selec ion o he mos challenging p oblems.
7.1. Model Selec ion
The selec ion o an adequa e su oga e plays a c ucial ole in he SBO p o-690
cess. The su oga e should e lec he unde lying complex p ocess as exac as
possible and should be as simple as possible. The es ima ion o he model quali y
is an open esea ch ques ion. Fo example, he de ini ion o he co esponding
aining se s o he holdou o c oss- alida ion app oaches ep esen s a c i ical
issue o he accu acy and e iciency o he su oga es. Viana and Ha ka [118]695
epo ha is is bene icial o un EGO wi h mul iple su oga es. In e es ingly,
hey also obse e ha an imp o ed global accu acy o he su oga e is no nec-
essa y o ob aining he bes esul .
The numbe o po en ial su oga e model ypes and selec ion s a egies is
huge. The ea lie men ioned s acking app oach (c . Sec ion 6.2) can p o e o be700
a help ul s a ing poin . Building s acked ensembles o su oga e models may
help o unde s and how di e en app oaches pe o m, and how hey can in e ac .
Besides p o iding mo e accu a e p edic ions, s acking may enable esea che s
o design mo e p omising modeling app oaches o complex da a s uc u es.
Model selec ion is s ill a challenging esea ch opic wi h many open ques ions,705
30

which is is especially ue in he combina o ial domain. The e, li le guidelines
a e a ailable, due o he ela i e sca ci y o publica ions.
7.2. De ini eness
In case o simila i y-based models (s a egy STR-6, see Sec ion 5.5), de ini e-
ness is a c ucial issue. While i s esul s a e a ailable o K iging models [99],710
some impo an de ails equi e u he a en ion. Fi s , mo e ex ensi e expe -
imen s a e o in e es . Secondly, mo e e icien handling o p edic ion o new
da a samples would be bene icial o pe o mance in p ac ice. And inally, a
heo e ical analysis could p o ide a mo e sound ounda ion o he exis ing ap-
p oaches.715
7.3. Dimensionali y
The ques ion o dimensionali y, i.e., he numbe o a iables, is an impo an
issue. Fo con inuous p oblems, i is o en s a ed ha dis ance-based models
like K iging pe o m poo ly o la ge dimensional p oblems. A ough h eshold
o app oxima ely 20 dimensions is equen ly speci ied o K iging, e.g., see [7].720
This is closely linked o he speci ic dis ance unc ion [130]. Fo ins ance, Man-
ha an dis ance will be less a ec ed by such issues, compa ed o Euclidean
dis ance [130]. Fo he gene al, disc e e case wi h an a bi a y dis ance unc-
ion such knowledge is o en no a ailable. A he same ime, ea u e selec ion
o o he dimensionali y educ ion me hods may no be ins an ly a ailable o 725
p oblems wi h complex, disc e e da a ep esen a ions. Thus, u he esea ch
on dimensionali y issues is ecommendable. This is especially o in e es o
high dimensional eal-wo ld p oblems as, e.g., in es iga ed by Smi h e al. [71].
Simpson e al. [2] lis some ecen app oaches o ackle his “cu se o dimension-
ali y” and p oblems ela ed o gene a e adequa e su oga es in high-dimensional730
and complex non-linea sea ch spaces.
Dimensionali y can also be in e p e ed as he numbe o samples, which leads
o addi ional challenges. Nowadays, an inc easing numbe o applica ions gene -
a e la ge da a se s. Ins ead o e y expensi e and small da a se s, huge da a se s
31
ha e o be p ocessed in his si ua ion. Se e al applica ions om bioin o ma ics,735
social media, o clima e science ely on he modeling o massi e da a se s wi h
up o billions o da a samples. Recen ly de eloped me hods ely on special ma-
ix s uc u es (K onecke o Toepli z). Fo example, Wilson e al. [131] p esen
ea ly esul s o massi ely scalable Gaussian p ocesses, which enables he use o
Gaussian p ocesses on billions o da a poin s. The de elopmen o mul i- ideli y740
su oga es, which use coa se g ained models o ob ain simila esul s as he ex-
ac model migh be e y in e es ing. Fu he mo e, me hods o da a se s ha
do no sa is y special ma ix s uc u es a e o g ea in e es .
7.4. Benchma king
An impo an issue is he se o benchma k o es unc ions, used o e alua e745
algo i hm and modeling pe o mance. P e ious app oaches y o compose a se
o es unc ions wi h many di e en ea u es, e.g., by using s ep, linea , con ex,
and sinusoidal unc ions. A mo e ecen app oach [132] uses an in ini e numbe
o es p oblem ins ances o p e en an o e i ing (o be e : o e lea ning) o
he compe ing algo i hms. The es p oblems a e based on eal-wo ld p oblem750
ins ances, which a e sys ema ically modi ied.
While benchma king is s ill no esol ed o con inuous model-based op i-
miza ion, he si ua ion is e en less se led in he disc e e domain. O he ew
published, eal-wo ld, expensi e, combina o ial p oblems, mos a e no openly
accessible. E en in case o a ailabili y, he benchma k se would be a he small755
and he expense o compu a ion would hinde b oade expe imen al s udies.
Thus, mos o he benchma k p oblems a e well known cheap- o-compu e p ob-
lems, e.g., he a eling salespe son p oblem (see he o e iew in Table 1). I
is ques ionable whe he pe o mances es ima ed o hese p oblems a e ac ually
ep esen a i e o eal-wo ld expensi e p oblems. In ac , he simple p oblem760
s uc u e may be unable o gi e p ope c edi o complex models like K iging.
This may be one eason o esul s as, e.g., obse ed by Cace es e al. [81].
32
7.5. Mul iple Objec i es
Las , bu no leas , he p oblems discussed so a o single objec i e SBO ex-
is also o model-based mul i-objec i e op imiza ion algo i hms. The ques ion765
o using global o local models is discussed in se e al publica ions, e.g., Isaacs e
al. [133] p esen a local app oach, which main ains an ex e nal a chi e, whe eas
Pila and Ne uda [134] p esen an app oach by agg ega ing me amodels o
e olu iona y mul iobjec i e and many-objec i e op imiza ion. Ho n e al. [135]
p esen a axonomy o model-based mul i-objec i e op imiza ion algo i hms,770
which can be ecommended as a s a ing poin .
Acknowledgemen s
This wo k has been suppo ed by he Bundesminis e ium ¨u Wi scha und
Ene gie unde he g an s KF3145101WM3 and KF3145103WM4. This wo k is
pa o a p ojec ha has ecei ed unding om he Eu opean Unions Ho izon775
2020 esea ch and inno a ion p og am unde g an ag eemen No 692286.
Re e ences
[1] T. Ba z-Beiels ein, A Su ey o Model-Based Me hods o Global Op i-
miza ion, in: G. Papa, M. Me nik (Eds.), Bioinspi ed Op imiza ion Me h-
ods and hei Applica ions, 2016, pp. 1–18.780
[2] T. Simpson, V. To opo , V. Balabano , F. Viana, Design and Analysis
o Compu e Expe imen s in Mul idisciplina y Design Op imiza ion: A
Re iew o How Fa We Ha e Come - O No , in: 12 h AIAA/ISSMO
Mul idisciplina y Analysis and Op imiza ion Con e ence, Ame ican Ins i-
u e o Ae onau ics and As onau ics, Res on, Vi igina, 2012, pp. 1–22.785
doi:10.2514/6.2008-5802.
[3] G. G. Wang, S. Shan, Re iew o Me amodeling Techniques in Suppo o
Enginee ing Design Op imiza ion, Jou nal o Mechanical Design 129 (4)
(2007) 370–380. doi:10.1115/1.2429697.
33
[4] M. P euss, Mul imodal Op imiza ion by Means o E olu iona y Algo-790
i hms, Na u al Compu ing Se ies, Sp inge In e na ional Publishing,
Cham, 2015. doi:10.1007/978-3-319-07407-8.
[5] A. Neumaie , Comple e sea ch in con inuous global op imiza ion and con-
s ain sa is ac ion, Ac a Nume ica 13 (2004) 271–369.
[6] M. Zlochin, M. Bi a a i, N. Meuleau, M. Do igo, Model-Based Sea ch795
o Combina o ial Op imiza ion: A C i ical Su ey, Annals o Ope a ions
Resea ch 131 (1-4) (2004) 373–395. doi:10.1023/B:ANOR.0000039526.
52305.a .
[7] A. Fo es e , A. S´obes e , A. Keane, Enginee ing Design ia Su oga e
Modelling, Wiley, 2008.800
[8] J. P. C. Kleijnen, A commen on blanning’s me amodel o sensi i i y
analysis: The eg ession me amodel in simula ion, In e aces 5 (3) (1975)
21–23.
[9] O. Ga i selo , S. P. Mohan y, E. Kougianos, A compa a i e s udy o
me amodels o as and accu a e simula ion o nano-cmos ci cui s, IEEE805
T ansac ions on Semiconduc o Manu ac u ing 25 (1) (2012) 26–36. doi:
10.1109/TSM.2011.2173957.
[10] S. Ki kpa ick, C. D. Gela , M. P. Vecchi, Op imiza ion by Simula ed
Annealing, science 220 (4598) (1983) 671–680. doi:10.1126/science.
220.4598.671.810
[11] A. E. Eiben, J. E. Smi h, In oduc ion o E olu iona y Compu ing,
Sp inge , Be lin, Heidelbe g, New Yo k, 2003.
[12] T. Ba z-Beiels ein, J. B anke, J. Mehnen, O. Me smann, E olu iona y
Algo i hms, WIREs Da a Mining and Knowledge Disco e y 4 (2014) 178–
195.815
34
[13] F. Glo e , M. Laguna, Tabu sea ch, in: C. R. Ree es (Ed.), Mode n
Heu is ic Techniques o Combina o ial P oblems, John Wiley & Sons,
Inc., New Yo k, NY, USA, 1993, Ch. Tabu Sea ch, pp. 70–150.
[14] P. La aaga, J. A. Lozano, Es ima ion o Dis ibu ion Algo i hms. A New
Tool o E olu iona y Compu a ion, Kluwe , Bos on MA, 2002.820
[15] M. Hauschild, M. Pelikan, An in oduc ion and su ey o es ima ion o dis-
ibu ion algo i hms, Swa m and E olu iona y Compu a ion 1 (3) (2011)
111–128. doi:10.1016/j.swe o.2011.08.003.
[16] J. Hu, Y. Wang, E. Zhou, M. C. Fu, S. I. Ma cus, A Su ey o Some Model-
Based Me hods o Global Op imiza ion, in: D. He n´andez-He n´andez,825
J. A. Minj´a ez-Sosa (Eds.), Op imiza ion, Con ol, and Applica ions o
S ochas ic Sys ems, Bi kh¨ause Bos on, Bos on, 2012, pp. 157–179. doi:
10.1007/978-0-8176-8337-5_10.
[17] J. Sacks, W. J. Welch, T. J. Mi chell, H. P. Wynn, Design and analysis o
compu e expe imen s, S a is ical Science 4 (4) (1989) 409–435.830
[18] K. B. W. G E P Box, On he Expe imen al A ainmen o Op imum Con-
di ions, Jou nal o he Royal S a is ical Socie y. Se ies B (Me hodological)
13 (1) (1951) 1–45.
[19] V. N. Vapnik, S a is ical lea ning heo y, Wiley (1998).
[20] J. M. Zu ada, Analog implemen a ion o neu al ne wo ks, IEEE Ci cui s835
and De ices Magazine 8 (5) (1992) 36–41. doi:10.1109/101.158511.
[21] M. J. D. Powell, Radial basis unc ions o mul i a iable in e pola ion: A
e iew, in: J. C. Mason, M. G. Cox (Eds.), Algo i hms o App oxima ion,
Cla endon P ess, New Yo k, NY, USA, 1987, pp. 143–167.
[22] M. Schonlau, Compu e Expe imen s and Global Op imiza ion, Ph.D.840
hesis, Uni e si y o Wa e loo, On a io, Canada (1997).
35

[23] D. B¨uche, N. N. Sch audolph, P. Koumou sakos, Accele a ing E olu ion-
a y Algo i hms Wi h Gaussian P ocess Fi ness Func ion Models, IEEE
T ansac ions on Sys ems, Man and Cybe ne ics, Pa C (Applica ions
and Re iews) 35 (2) (2005) 183–194. doi:10.1109/TSMCC.2004.841917.845
[24] A. B. An ognini, M. Zago aiou, Exac op imal designs o compu e ex-
pe imen s ia K iging me amodelling, Jou nal o S a is ical Planning and
In e ence 140 (9) (2010) 2607–2617. doi:10.1016/j.jspi.2010.03.027.
[25] J. P. C. Kleijnen, K iging me amodeling in simula ion: A e iew, Eu-
opean Jou nal o Ope a ional Resea ch 192 (3) (2009) 707–716. doi:850
10.1016/j.ejo .2007.10.013.
[26] T. J. San ne , B. J. Williams, W. I. No z, The Design and Analysis o
Compu e Expe imen s, Sp inge , Be lin, Heidelbe g, New Yo k, 2003.
[27] Y. Jin, A comp ehensi e su ey o i ness app oxima ion in e olu iona y
compu a ion, So Compu ing 9 (1) (2005) 3–12.855
[28] Y. Jin, Su oga e-assis ed e olu iona y compu a ion: Recen ad ances
and u u e challenges, Swa m and E olu iona y Compu a ion 1 (2) (2011)
61–70. doi:h p://dx.doi.o g/10.1016/j.swe o.2011.05.001.
[29] J. Moˇckus, On Bayesian Me hods o Seeking he Ex emum, in: Op i-
miza ion Techniques IFIP Technical Con e ence, 1974, pp. 400–404.860
[30] D. R. Jones, M. Schonlau, W. J. Welch, E icien Global Op imiza ion o
Expensi e Black-Box Func ions, Jou nal o Global Op imiza ion 13 (1998)
455–492.
[31] D. R. Jones, A Taxonomy o Global Op imiza ion Me hods Based on
Response Su aces, Jou nal o Global Op imiza ion 21 (2001) 345–383.865
[32] A. I. J. Fo es e , A. J. Keane, Recen ad ances in su oga e-based op-
imiza ion, P og ess in Ae ospace Sciences 45 (1-3) (2009) 50–79. doi:
10.1016/j.pae osci.2008.11.001.
36
[33] P. Hajela, E. Lee, Topological op imiza ion o o o c a sub loo s uc-
u es o c ashwo hiness conside a ions, Compu e s & S uc u es 64 (1-4)870
(1997) 65–76. doi:10.1016/S0045-7949(96)00143-5.
[34] A. J. Booke , J. E. Dennis J , P. D. F ank, D. B. Se a ini, V. To -
czon, Op imiza ion Using Su oga e Objec i es on a Helicop e Tes
Example, in: Compu a ional Me hods o Op imal Design and Con-
ol, Bi kh¨ause Bos on, Bos on, MA, 1998, pp. 49–58. doi:10.1007/875
978-1-4612-1780-0_3.
[35] A. J. Booke , J. E. Dennis J , P. D. F ank, D. B. Se a ini, V. To c-
zon, M. W. T osse , A igo ous amewo k o op imiza ion o expen-
si e unc ions by su oga es, S uc u al Op imiza ion 17 (1) (1999) 1–13.
doi:10.1007/BF01197708.880
[36] K. C. Giannakoglou, Design o op imal ae odynamic shapes using s ochas-
ic op imiza ion me hods and compu a ional in elligence, P og ess in
Ae ospace Sciences 38 (1) (2002) 43–76. doi:10.1016/S0376-0421(01)
00019-7.
[37] Z. Zhou, Y. S. Ong, P. B. Nai , A. J. Keane, K. Y. Lum, Combining885
Global and Local Su oga e Models o Accele a e E olu iona y Op imiza-
ion, IEEE T ansac ions on Sys ems, Man and Cybe ne ics, Pa C (Ap-
plica ions and Re iews) 37 (1) (2007) 66–76. doi:10.1109/TSMCC.2005.
855506.
[38] A. Ra le, Accele a ing he con e gence o e olu iona y algo i hms by i -890
ness landscape app oxima ion, in: A. E. Eiben, T. B¨ack, M. Schoenaue ,
H.-P. Schwe el (Eds.), Pa allel P oblem Sol ing om Na u e — PPSN
V: 5 h In e na ional Con e ence Ams e dam, The Ne he lands, P oceed-
ings, Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, 1998, pp. 87–96.
doi:10.1007/BFb0056852.895
[39] Y. Jin, M. Olho e , B. Sendho , On E olu iona y Op imiza ion wi h Ap-
p oxima e Fi ness Func ions., in: D. W. e al. (Ed.), P oceedings o he
37
Gene ic and E olu iona y Compu a ion Con e ence GECCO, San F an-
cisco, CA, USA, 2000, pp. 786–793.
[40] M. Emme ich, A. Gio is, M. ¨
Ozdemi , T. B¨ack, K. Giannakoglou,900
Me amodel-assis ed e olu ion s a egies, in: J. J. M. Gue ´os,
P. Adamidis, H. G. Beye , J. L. Fe n´andez-Villaca˜nas, H. P. Schwe el
(Eds.), Pa allel P oblem Sol ing om Na u e—PPSN VII, P oceedings
Se en h In e na ional Con e ence, G anada, Sp inge , Be lin, Heidelbe g,
New Yo k, 2002, pp. 361–370.905
[41] Y. Jin, B. Sendho , Reducing Fi ness E alua ions Using Clus e ing Tech-
niques and Neu al Ne wo k Ensembles, in: Pa allel P oblem Sol ing om
Na u e - PPSN XIII - 13 h In e na ional Con e ence, Ljubljana, Slo enia,
Sep embe 13-17, 2014. P oceedings, Sp inge Be lin Heidelbe g, Be lin,
Heidelbe g, 2004, pp. 688–699. doi:10.1007/978-3-540-24854-5_71.910
[42] J. B anke, C. Schmid , Fas e con e gence by means o i ness es ima ion,
So 9 (1) (2005) 13–20. doi:10.1007/s00500-003-0329-4.
[43] G. Sun, G. Li, S. Zhou, W. Xu, X. Yang, Q. Li, Mul i- ideli y op imiza ion
o shee me al o ming p ocess, S uc u al and Mul idisciplina y Op i-
miza ion 44 (1) (2011) 111–124. doi:10.1007/s00158-010-0596-5.915
[44] S. Ulagana han, I. Couckuy , F. Fe an i, E. Lae mans, T. Dhaene,
Pe o mance s udy o mul i- ideli y g adien enhanced k iging, S uc-
u al and Mul idisciplina y Op imiza ion 51 (5) (2014) 1017–1033. doi:
10.1007/s00158-014-1192-x.
[45] S. Koziel, A. Bekasiewicz, I. Couckuy , T. Dhaene, E icien Mul i-920
Objec i e Simula ion-D i en An enna Design Using Co-K iging, IEEE
T ansac ions on An ennas and P opaga ion 62 (11) (2014) 5900–5905.
doi:10.1109/TAP.2014.2354673.
[46] M. Kennedy, P edic ing he ou pu om a complex compu e code when
38
as app oxima ions a e a ailable, Biome ika 87 (1) (2000) 1–13. doi:925
10.1093/biome /87.1.1.
[47] A. Fo es e , A. S´obes e , A. Keane, Mul i- ideli y op imiza ion ia su -
oga e modelling, P oceedings o he Royal Socie y A: Ma hema ical,
Physical and Enginee ing Science 463 (2088) (2007) 3251–3269. doi:
10.1098/ spa.2007.1900.930
[48] L. Le G a ie , C. Cannamela, K iging-based sequen ial design s a e-
gies using as c oss- alida ion echniques wi h ex ensions o mul i- ideli y
compu e codes, a Xi .o ga Xi :1210.6187 2.
[49] S. Raza i, B. A. Tolson, D. H. Bu n, Re iew o su oga e modeling in
wa e esou ces, Wa e Resou ces Resea ch 48 (7) (2012) 1–32. doi:10.935
1029/2011WR011527.
[50] R. Tuo, C. F. J. Wu, D. Yu, Su oga e Modeling o Compu e Expe imen s
Wi h Di e en Mesh Densi ies, Technome ics 56 (3) (2014) 372–380. doi:
10.1080/00401706.2013.842935.
[51] J. P. C. Kleijnen, Design and Analysis o Simula ion Expe imen s, In e -940
na ional Se ies in Ope a ions Resea ch and Managemen Science, Sp inge
In e na ional Publishing, 2015.
[52] J. M¨ulle , C. A. Shoemake , In luence o ensemble su oga e models and
sampling s a egy on he solu ion quali y o algo i hms o compu a ion-
ally expensi e black-box global op imiza ion p oblems, Jou nal o Global945
Op imiza ion 60 (2) (2014) 123–144. doi:10.1007/s10898-014-0184-0.
[53] R. T. Ha ka, D. Villanue a, A. Chaudhu i, Pa allel 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) (2016) 3–13. doi:10.1007/
s00158-016-1432-3.950
[54] R. Jin, W. Chen, T. W. Simpson, Compa a i e s udies o me a-
modelling echniques unde mul iple modelling c i e ia, S uc u al and
39
[100] F.-M. Schlei , P. Tino, Inde ini e p oximi y lea ning: A e iew, Neu al
Compu a ion 27 (10) (2015) 2039–2096.
[101] T. G¨a ne , A su ey o ke nels o s uc u ed da a, SIGKDD Explo .
Newsl. 5 (1) (2003) 49–58.
[102] T. G¨a ne , J. Lloyd, P. Flach, Ke nels and dis ances o s uc u ed da a,1125
Machine Lea ning 57 (3) (2004) 205–232.
[103] D. Haussle , Con olu ion ke nels on disc e e s uc u es, Tech. Rep. UCSC-
CRL-99-10, Depa men o Compu e Science, Uni e si y o Cali o nia a
San a C uz (1999).
[104] S. Shakya, Deum: A amewo k o an es ima ion o dis ibu ion algo i hm1130
based on ma ko andom ields, Ph.D. hesis, School o Compu ing, Fac-
ul y o Design and Technology, The Robe Go don Uni e si y, Abe deen,
UK (2006).
[105] A. B ownlee, J. McCall, Q. Zhang, Fi ness modeling wi h ma ko ne -
wo ks, IEEE T ansac ions on E olu iona y Compu a ion 17 (6) (2013)1135
862–879.
[106] A. E. B ownlee, Mining Ma ko ne wo k su oga es o alue-added op-
imisa ion, in: P oceedings o he 2016 on Gene ic and E olu iona y
Compu a ion Con e ence Companion - GECCO 16 Companion, Asso-
cia ion o Compu ing Machine y (ACM), 2016, pp. 1267–1274. doi:1140
10.1145/2908961.2931711.
[107] S. Jiang, A. Zi e , J. Ca e , C. Pain, A. Godda d, S. F anklin, H. Phillips,
Es ima ion o dis ibu ion algo i hms o nuclea eac o uel managemen
op imisa ion, Annals o Nuclea Ene gy 33 (11–12) (2006) 1039–1057.
doi:h p://dx.doi.o g/10.1016/j.anucene.2006.03.012.1145
[108] J. Cebe io, E. I u ozki, A. Mendibu u, J. A. Lozano, A e iew on es ima-
ion o dis ibu ion algo i hms in pe mu a ion-based combina o ial op i-
46

miza ion p oblems, P og ess in A i icial In elligence 1 (1) (2012) 103–117.
doi:10.1007/s13748-011-0005-3.
[109] C. L. Mallows, Non-null anking models, Biome ika 44 (1–2) (1957) 114–1150
130.
[110] J. Cebe io, A. Mendibu u, J. A. Lozano, In oducing he mallows model on
es ima ion o dis ibu ion algo i hms, in: Neu al In o ma ion P ocessing -
18 h In e na ional Con e ence, ICONIP 2011, Sp inge Be lin Heidelbe g,
2011, pp. 461–470. doi:10.1007/978-3-642-24958-7_54.1155
[111] J. Cebe io, E. I u ozki, A. Mendibu u, J. A. Lozano, A dis ance-based
anking model es ima ion o dis ibu ion algo i hm o he lowshop
scheduling p oblem, IEEE T ansac ions on E olu iona y Compu a ion
18 (2) (2014) 286–300. doi:10.1109/TEVC.2013.2260548.
[112] R. Allmendinge , C. A. C. Coello, M. T. M. Emme ich, J. Hakanen, Y. Jin,1160
E. Rigoni, Su oga e-assis ed mul ic i e ia op imiza ion (wg6), Tech.
Rep. 1, Schloss Dags uhl–Leibniz-Zen um ue In o ma ik, Dags uhl,
Ge many (2015).
[113] M. Pelikan, D. E. Goldbe g, E. Can u-Paz, BOA: The bayesian op imiza-
ion algo i hm, in: W. Banzha , e al. (Eds.), P oceedings o he Gene ic1165
and E olu iona y Compu a ion Con e ence (GECCO’99), Mo gan Kau -
mann, 1999, pp. 525–532.
[114] P. La a˜naga, R. E xebe ia, J. A. Lozano, J. M. Pe˜na, Combina o ial
op imiza ion by lea ning and simula ion o bayesian ne wo ks, in: P o-
ceedings o he Six een h Con e ence on Unce ain y in A i icial In el-1170
ligence, UAI’00, Mo gan Kau mann Publishe s Inc., San F ancisco, CA,
USA, 2000, pp. 343–352.
[115] M. N. Le, Y. S. Ong, S. Menzel, Y. Jin, B. Sendho , E olu ion by adap ing
su oga es, E olu iona y Compu a ion 21 (2) (2013) 313–340. doi:10.
1162/e co_a_00079.1175
47
[116] M. K yszkiewicz, J. F. Pe e s, H. Rybinski, A. Skow on (Eds.), Rough
Se s and In elligen Sys ems Pa adigms, Vol. 4585 o Lec u e No es in
Compu e Science, Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, 2007.
doi:10.1007/978-3-540-73451-2.
[117] T. Ba z-Beiels ein, S acked Gene aliza ion o Su oga e Models - A P ac-1180
ical App oach, Tech. Rep. 5/2016, TH K¨oln, K¨oln (2016).
[118] F. A. Viana, R. T. Ha ka, L. T. Wa son, Why no un he e icien global
op imiza ion algo i hm wi h mul iple su oga es?, in: 51s AIAAAS-
MEASCEAHSASC S uc u es S uc u al Dynamics and Ma e ials Con-
e ence, no. Ap il, AIAA, 2010, pp. AIAA–2010.1185
[119] N. M. Alexand o , J. E. Dennis J , R. M. Lewis, V. To czon, A us -
egion amewo k o managing he use o app oxima ion models in op-
imiza ion, S uc u al Op imiza ion 15 (1) (1998) 16–23. doi:10.1007/
BF01197433.
[120] Y. S. Ong, P. B. Nai , A. J. Keane, E olu iona y Op imiza ion o Com-1190
pu a ionally Expensi e P oblems ia Su oga e Modeling, AIAA Jou nal
41 (4) (2003) 687–696. doi:10.2514/2.1999.
[121] T. Ba z-Beiels ein, Expe imen al Analysis o E olu ion S a egies—
O e iew and Comp ehensi e In oduc ion, Reihe CI. SFB 531 157/03,
Uni e si y Do mund (No . 2003).1195
[122] T. Ba z-Beiels ein, K. E. Pa sopoulos, M. N. V aha is, Design and analy-
sis o op imiza ion algo i hms using compu a ional s a is ics, Applied Nu-
me ical Analysis and Compu a ional Ma hema ics (ANACM) 1 (2) (2004)
413–433.
[123] T. Ba z-Beiels ein, C. Lasa czyk, M. P euss, Sequen ial Pa ame e Op-1200
imiza ion, in: B. McKay, e al. (Eds.), P oceedings 2005 Cong ess on
E olu iona y Compu a ion (CEC’05), Edinbu gh, Sco land, IEEE P ess,
Pisca away NJ, 2005, pp. 773–780. doi:10.1109/CEC.2005.1554761.
48
[124] F. Hu e , H. H. Hoos, K. Ley on-B own, An E alua ion o Sequen ial
Model-based Op imiza ion o Expensi e Blackbox Func ions, in: P o-1205
ceedings o he 15 h Annual Con e ence Companion on Gene ic and E o-
lu iona y Compu a ion, ACM, New Yo k, NY, USA, 2013, pp. 1209–1216.
doi:10.1145/2464576.2501592.
[125] N. Hansen, S. Finck, R. Ros, A. Auge , Real-Pa ame e Black-Box Op-
imiza ion Benchma king 2009: Noiseless Func ions De ini ions, Resea ch1210
Repo RR-6829, INRIA (2009).
[126] M. J. an de Laan, S. Dudoi , Uni ied c oss- alida ion me hodology o
selec ion among es ima o s and a gene al c oss- alida ed adap i e epsilon-
ne es ima o : Fini e sample o acle inequali ies and examples, Wo king
pape 130, Uni e si y o Cali o nia, Be keley, Di ision o Bios a is ics,1215
School o Public Heal h, Uni e si y o Cali o nia, Be keley (2003).
[127] D. H. Wolpe , S acked gene aliza ion, Neu al Ne wo ks 5 (2) (1992) 241–
259. doi:10.1016/S0893-6080(05)80023-1.
[128] M. A. Rebolledo Coy, S. K ey, T. Ba z-Beiels ein, O. Flasch, A. Fis-
chbach, J. S o k, Modeling and op imiza ion o a obus gas senso ,1220
Cologne Open Science 03/2016, TH K¨oln, Cologne (2016).
[129] D. Dougue , e-lea3d: a compu a ional-aided d ug design web
se e , Nucleic Acids Resea cha Xi :h p://na .ox o djou nals.
o g/con en /ea ly/2010/05/05/na .gkq322. ull.pd +h ml,
doi:10.1093/na /gkq322.1225
[130] C. C. Agga wal, A. Hinnebu g, D. A. Keim, On he su p ising beha io
o dis ance me ics in high dimensional space, in: Da abase Theo y —
ICDT 2001, Vol. 3, Sp inge Science + Business Media, Munich, 2001,
pp. 420–434.
[131] A. G. Wilson, C. Dann, H. Nickisch, Though s on Massi ely Scalable1230
Gaussian P ocesses, a Xi .o ga Xi :1511.01870 1.
49
[132] T. Ba z-Beiels ein, How o C ea e Gene alizable Resul s, in: J. Kacp zyk,
W. Ped ycz (Eds.), Sp inge Handbook o Compu a ional In elligence,
Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, 2015, pp. 1127–1142. doi:
10.1007/978-3-662-43505-2_56.1235
[133] A. Isaacs, T. Ray, W. Smi h, An e olu iona y algo i hm wi h spa ially
dis ibu ed su oga es o mul iobjec i e op imiza ion, in: M. Randall,
H. A. Abbass, J. Wiles (Eds.), P og ess in A i icial Li e: Thi d Aus-
alian Con e ence; ACAL 2007 Gold Coas , Aus alia, Decembe 4-6,
2007 P oceedings, Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, 2007,1240
pp. 257–268. doi:10.1007/978-3-540-76931-6_23.
[134] M. Pil´a , R. Ne uda, Agg ega e me a-models o e olu iona y mul iobjec-
i e and many-objec i e op imiza ion, Neu ocompu ing 116 (2013) 392–
402, ad anced Theo y and Me hodology in In elligen Compu ing – Se-
lec ed Pape s om he Se en h In e na ional Con e ence on In elligen 1245
Compu ing (ICIC 2011). doi:h p://dx.doi.o g/10.1016/j.neucom.
2012.06.043.
[135] D. Ho n, T. Wagne , D. Bie mann, C. Weihs, B. Bischl, Model-based
mul i-objec i e op imiza ion: Taxonomy, mul i-poin p oposal, oolbox
and benchma k, in: A. Gaspa -Cunha, C. Henggele An unes, C. C.1250
Coello (Eds.), E olu iona y Mul i-C i e ion Op imiza ion: 8 h In e na-
ional Con e ence, EMO 2015, Guima ˜aes, Po ugal, Ma ch 29 –Ap il 1,
2015. P oceedings, Pa I, Sp inge In e na ional Publishing, Cham, 2015,
pp. 64–78. doi:10.1007/978-3-319-15934-8_5.
50
Kon ak /Imp essum
Diese Ve ö en lichungen e scheinen im Rahmen de Sch i en eihe "CIplus". Alle Ve ö -
en lichungen diese Reihe können un e
h ps://cos.bibl. h-koeln.de/home
abge u en we den.
Köln, Janua 2012
Die Ve an wo ung ü den Inhal diese Ve ö en lichung lieg beim Au o .
Da um de Ve ö en lichung: 14.11.2016
He ausgebe / Edi o ship
P o . D . Thomas Ba z-Beiels ein,
P o . D . Wol gang Konen,
P o . D . Bo is Naujoks,
P o . D . Ho s S enzel
Ins i u e o Compu e Science,
Facul y o Compu e Science and Enginee ing Science,
TH Köln,
S einmülle allee 1,
51643 Gumme sbach
u l:
www.ciplus- esea ch.de
Sch i lei ung und Ansp echpa ne / Con ac edi o ’s office
P o . D . Thomas Ba z-Beiels ein,
Ins i u e o Compu e Science,
Facul y o Compu e Science and Enginee ing Science,
TH Köln,
S einmülle allee 1, 51643 Gumme sbach
phone: +49 2261 8196 6391
u l:
h p://www.spo se en.de
eMail: homas.ba z-beiels ein@ h-koeln.de
ISSN (online) 2194-2870

G an No. KF3145101WM3 and KF3145103WM4
This p ojec has ecei ed unding om he Eu opean Union’s Ho izon 2020
esea ch and inno a ion p og amme unde g an ag eemen No 692286.