Sch i en eihe CIplus, Band 2/2012
Thomas Ba z-Beiels ein, Wol gang Konen, Ho s S enzel, Bo is Naujoks
Model-assis ed Mul i-c i e ia
Tuning o an E en De ec ion
So wa e unde Limi ed Budge s
Ma in Zae e e , Thomas Ba z-Beiels ein, Bo is Naujoks,
Tobias Wagne and Michael Emme ich
Model-assis ed Mul i-c i e ia Tuning o an E en
De ec ion So wa e unde Limi ed Budge s
Ma in Zae e e 1, Thomas Ba z-Beiels ein1, Bo is Naujoks1, Tobias Wagne 2,
and Michael Emme ich3
1Facul y o Compu e and Enginee ing Sciences
Cologne Uni e si y o Applied Sciences, 51643 Gumme sbach, Ge many
[email p o ec ed]
2Ins i u e o Maching Technology (ISF)
TU Do mund Uni e si y, 44227 Do mund, Ge many
[email p o ec ed]
3Leiden Ins i u e o Ad anced Compu e Science
Leiden Uni e si y, The Ne he lands,
[email p o ec ed]
Depa men o Compu e Science,
Cologne Uni e si y o Applied Sciences, Ge many.
Sch i en eihe CIplus
TR 2/2012. ISSN 2194-2870
Abs ac . Fo me ly, mul i-c i e ia op imiza ion algo i hms we e o en
es ed using ens o housands unc ion e alua ions. In many eal-wo ld
se ings unc ion e alua ions a e e y cos ly o he a ailable budge
is e y limi ed. Se e al me hods we e de eloped o sol e hese cos -
ex ensi e mul i-c i e ia op imiza ion p oblems by educing he numbe
o unc ion e alua ions by means o su oga e op imiza ion. In his s udy,
we apply di e en mul i-c i e ia su oga e op imiza ion me hods o im-
p o e ( une) an e en -de ec ion so wa e o wa e -quali y moni o ing.
Fo uning wo impo an pa ame e s o his so wa e, ou s a e-o - he-
a me hods a e compa ed: S-Me ic-Selec ion E icien Global Op imiza-
ion (SMS-EGO), S-Me ic-Expec ed Imp o emen o E icien Global
Op imiza ion SExI-EGO, Euclidean Dis ance based Expec ed Imp o e-
men Euclid-EI (he e e e ed o as MEI-SPOT due o i s implemen a-
ion in he Sequen ial Pa ame e Op imiza ion Toolbox SPOT) and a
mul i-c i e ia app oach based on SPO (MSPOT).
Analyzing he pe o mance o he di e en me hods p o ides insigh in o
he wo king-mechanisms o cu ing-edge mul i-c i e ia sol e s. As one
o he app oaches, namely MSPOT, does no conside he p edic ion
a iance o he su oga e model, i is o in e es whe he his can lead
o p ema u e con e gence on he p ac ical uning p oblem. Fu he mo e,
all ou app oaches will be compa ed o a simple SMS-EMOA o alida e
ha he use o su oga e models is jus i ied on his p oblem.
MCO uning o E en De ec ion So wa e 3
1 In oduc ion
The ime equi ed o a p ocess eedback can play a c ucial ole in many ields
o indus ial op imiza ion. Complex and expensi e eal-wo ld p ocesses o ime
consuming simula ions lead o la ge e alua ion imes. This es ic s op imiza-
ion p ocesses o only a e y limi ed numbe o such e alua ions. Mo eo e ,
almos all indus ial op imiza ion asks ea u e mo e han one quali y c i e ion.
Techniques om mul i-c i e ia decision making, e olu iona y mul i-c i e ia op-
imiza ion (EMO) in pa icula , we e de eloped du ing he las decade o sol e
such asks. The necessi y o combine EMO echniques and op imiza ion me h-
ods such as EGO [17] o SPO [1], which equi e a e y small numbe o unc ion
e alua ions only, should be sel -e iden . The applica ion o such me hods o eal-
wo ld p oblems in indus ial op imiza ion p o ides a easonable way o assess
hei easibili y. In con as o a i icial es unc ions, i allows o an assessmen
o he p ac ical ele ance o hese kinds o p oblems.
In his pape , which is an ex ended e sion o a pape submi ed o he
E olu iona y Mul i-C i e ion Op imiza ion EMO Con e ence 2013, we ocus on
ou di e en uning me hods which a e applied o une an anomaly de ec ion
so wa e o wa e quali y managemen . This p oblem is usually handled by
ecei e ope a o cha ac e is ic (ROC) analysis. Due o speci ic limi a ions o he
so wa e conce ned, his can no be applied in he classical way. Ra he , he ROC
cu e should be app oxima ed by MCO me hods. Tha means, he ROC cu e
can be in e p e ed as a Pa e o on . In e p e ing ROC cu es om he mul i-
c i e ia op imiza ion pe spec i e is an es ablished app oach in compu a ional
in elligence, see, e.g., [22].
In Sec. 2, we will summa ize he o me wo k pe o med in ele an esea ch
ields. The speci ic p oblem is p esen ed in Sec. 3. The uning algo i hms (based
on di e en SPO and EGO implemen a ions) a e desc ibed in Sec. 4. Sec ion 5
desc ibes he expe imen al se up, whe eas he analysis is p esen ed in in Sec. 6.
Finally, Sec. 7 gi es a summa y o indings. The pape concludes wi h an ou look
p esen ed in Sec. 8.
2 Fo me esea ch
Su oga e modeling is no a new opic in op imiza ion. Jin [16] p o ides a
comp ehensi e o e iew o single-objec i e op imiza ion wi h su oga e models.
While me hods like EGO o SPO o single c i e ia op imiza ion a e well es ab-
lished, he applica ion o su oga e modeling p ocedu es o mul iple objec i es
is mo e ecen .
2.1 Su oga e modeling in mul i-c i e ia op imiza ion
Se e al app oaches employ su oga e modeling in MCO, like he well es ablished
Pa EGO by Knowles [20]. An o e iew o su oga e modeling in MCO is gi en
by Knowles and Nakayama [21]. To balance explo a ion and exploi a ion wi hin
4 Zae e e e al.
a limi ed budge si ua ion, se e al me hods y o employ in ill c i e ia based
on he expec ed imp o emen (EI). Two hings a e equi ed o de ining such a
c i e ion: he de ini ion o he imp o emen and an algo i hm o compu ing i s
expec a ion [30]. The eby, nega i e imp o emen s a e no possible, domina ed
solu ions should esul in an imp o emen o ze o. As la ge a iances po en ially
esul in big imp o emen s and big de e io a ions a e no penalized, hese c i e ia
also ocus on he explo a ion o unco e ed a eas o he sea ch space. I is o
in e es o see i he addi ional explo a ion is desi able o he p oblem a hand, o
i he explo a ion p o ided by he ini ial design is al eady su icien . In pa icula ,
since explo a ion is en o ced by he equi emen o co e he whole Pa e o on
(o se ).
2.2 ROC analysis
ROC p o ides means o selec a h eshold o a classi ie based on ade-o
be ween i s T ue Posi i e Ra e (TPR) and False Posi i e Ra e (FPR). In case o
an e en de ec ion so wa e like CANARY [14, 26]4, TPR is he hi a e which
is based on he numbe o co ec ly ecognized e en s. FPR on he o he hand
is he alse ala m a e. False ala ms occu whene e he algo i hm de ec s an
e en when ac ually none exis s.
The ROC cu e shows he ade-o be ween TPR and FPR. Usually, i is
d awn based on he h eshold alue o he classi ie . This means, depending on
he chosen h eshold alue one ecei es di e en pai s o TPR/FPR alues which
can be connec ed o a cu e. To e alua e he pe o mance o a classi ie , he A ea
Unde Cu e (AUC) can be used. The wo s possible classi ie will ha e an AUC
o 0.5, since all pai s o TPR and FPR will be on he s aigh line be ween he
wo ex eme poin s o he cu e. This pe o mance would be equal o andom
guessing. The bes possible classi ie will ha e an AUC o 1, which means he e is
a con igu a ion whe e no alse ala ms occu , all e en s a e iden i ied (c . Fig. 1).
In he case o CANARY, his o m o measu ing he pe o mance can no
be used, since he h eshold alue used in CANARY canno be chosen indepen-
den ly. The e o e, each di e en se ing o he h eshold has o be conside ed as
a new classi ie . The ROC cu e can hen be used o compa e pe o mance o he
di e en classi ie s. Consequen ly, he h eshold alue is one o he pa ame e s
o be op imized.
2.3 MCO in ROC Analysis
The ROC cu e can be in e p e ed as a Pa e o on , al hough i would classi-
cally only ep esen he Pa e o on o an MCO p oblem wi h one dimensional
decision space (i.e. he decision h eshold being he only decision a iable). How-
e e , i is easonable o apply MCO me hods o o he cases, o ins ance when
4Fo documen a ion, manuals and sou ce code o CANARY see:
h ps://so wa e.sandia.go / ac/cana y
MCO uning o E en De ec ion So wa e 5
False Posi i e Ra e
0 1
AUC>0.5
0 1
AUC=0.5
T ue Posi i e Ra e
0
0
1
1
AUC=1
pe ec good andom
False Posi i e Ra e False Posi i e Ra e
E en P obabili ies
E en Th eshold
TP
FN
TN
FP
Dis ibu ion o
T ue E en s
Dis ibu ion o
Non-E en s
TP
TN
FN FP
TP
TN
Fig. 1: Rela ionship be ween h eshold and ROC cu e in he classical case. The uppe
g aphs show he dis ibu ion o he e en s o h ee di e en cases, he lowe g aphs
show he ROC cu es o he same cases. The eby, TN is T ue Nega i e, TP is T ue
Posi i e, FN is False Nega i e, FP is False Posi i e. Le mos is he case o pe ec
classi ica ion, he igh mos is andom guessing.
di e en classi ie s a e o be compa ed, o he h eshold is no independen o
he classi ica ion p ocess. This is he case in he p oblem desc ibed in his pape .
Applying MCO o ROC analysis is no a new opic. Kupinski and Anas a-
sio [22] conside ed pe o mances o he solu ions e u ned om a mul i-c i e ia
objec i e gene ic op imiza ion as se ies o op imal (sensi i i y, speci ici y) pai s,
which can be hough o as ope a ing poin s on a ROC cu e. ROC analysis has
also been in oduced o machine lea ning as desc ibed by Flach [10]. Recen ly,
Wang e al. [31] conside he ROC con ex hull (ROCCH). They use mul i-c i e ia
gene ic p og aming o app oxima e he op imal ROCCH. A su ey o MCO ap-
plica ions o ROC can be ound in he wo k o E e son e al. [9].
3 P oblem Desc ip ion
The p oblem o be sol ed in his pape is he uning o a so wa e designed
o anomaly de ec ion in wa e quali y managemen : CANARY. I was de el-
oped by he US En i onmen al P o ec ion Agency EPA and Sandia Na ional
Labo a o ies o de ec anomalies (o e en s) in wa e quali y ime se ies da a.
I implemen s se e al di e en algo i hms o ime se ies p edic ion, pa e n
ma ching, and ou lie de ec ion. The main concep is o employ a ime se ies
algo i hm o p edic he nex ime s ep, and a e wa ds o dis inguish whe he
6 Zae e e e al.
he eal alue de e io a es om he p edic ed alue su icien ly o decla e i an
ou lie o anomaly.
CANARY can use addi ional me hods o educe alse ala ms. One me hod is
o look a he equency o ou lie s in a smalle ime window, o make su e ha
isola ed de ia ions due o noise do no aise an ala m. This was ound o be no
help ul, a leas o he da a se s used in his s udy, as he da a is no ha noisy
on a smalle ime ame. Ano he me hod o educe alse ala ms would be o
compa e known non-e en pa e ns wi h cu en da a, o exclude e en s ou o
in e es . which a e no o in e es . This is impossible wi h he da a ele an o
his pape as well, as pa e n ma ching equi es knowledge abou he posi ion
o such non-e en s, which is una ailable o he da a se used.
We will une he wo ele an pa ame e s window size and h eshold alue.
The window size de ines how many alues a e used o he p edic ion, while he
h eshold alue de ines how much de ia ion be ween measu ed and p edic ed
alue a e su icien o decla e an ou lie . Bo h pa ame e s ha e p e iously been
uned in di e en ways. Fi s ly, hey ha e been uned by a s ep-by-s ep p oce-
du e [26] which un o una ely does no conside in e ac ions be ween pa ame e s.
Secondly, ano he s udy [32] uned hem wi h model based op imiza ion, con-
side ing in e ac ions, bu only used a single c i e ia app oach, which basically
combined he objec i es False Ala m Ra e and Hi Ra e o a weigh ed sum.
Usually, as desc ibed by Mu ay e al. [26], a classical ROC analysis would be
pe o med. The AUC would be used as a single quali y c i e ion. This app oach
is no pe ec ly iable in his case, as he h eshold alue is no independen o
he p edic ion p ocess. The e o e, i is a mo e easonable app oach o add he
h eshold o he lis o uned pa ame e s and apply mul i-c i e ia op imiza ion.
Fo his eason, we will mainly use MCO- e minology in he ollowing (e.g.,
Pa e o on ins ead o ROC cu e).
4 Algo i hm Desc ip ion
Fou di e en uning algo i hms a e in he ocus o his s udy. Due o he sim-
ila i y o he AUC, he hype olume is applied as a c i e ion in all bu one
o hese app oaches. Two o hem a e based on R-code (SPOT package), wo
a e MATLAB implemen a ions (SMS-EGO and SExI-EGO). All ou sha e he
ollowing basic wo k low:
1. E alua e an ini ial design o npoin s on he a ge p oblem (CANARY)
2. Build models (he e: K iging) o each objec i e
3. Use models o de e mine he nex design poin o be e alua ed
4. E alua e design poin and upda e non domina ed se
5. I e a e 2-4
The ou uning algo i hms di e in he ype o he in oked in ill c i e ion.
Th ee algo i hms use di e en mul i-c i e ia EI. The ou h is a s aigh o wa d
app oach ha , ins ead o agg ega ing he objec i e alues om he models, ies
o op imize hese sepa a ely wi h common MCO me hods.
MCO uning o E en De ec ion So wa e 7
4.1 MEI-SPOT
This mul i-c i e ia expec ed imp o emen app oach is he only app oach ha
does no use hype olume as a c i e ion. The implemen a ion is based on MAT-
LAB code o Fo es e e al. [12]. MEI-SPOT is based on he in eg a ion o e he
non-domina ed a ea and an Euclidean dis ance o he nex poin on he on .
While Fo es e e al. use a domina ing a ian (e.g. imp o emen conside s
only poin s ha domina e exis ing Pa e o-op imal solu ions), he implemen a-
ion used he e uses an augmen ing a ian (i.e. imp o emen is also epo ed
when a poin is added o he on , wi hou domina ing an exis ing Pa e o-
op imal solu ion). The di e en o mula ions o his dis inc ion a e de ailed
by Keane [19]. This app oach is ime consuming due o he in eg a ion. I can
also ha e issues wi h he scaling o di e en objec i es, since i is based on he
Euclidean dis ance.
4.2 SExI-EGO
The S-Me ic Expec ed Imp o emen [7] compu es he expec ed inc emen in
hype olume o a poin , gi en a non-domina ed se . I s exac compu a ion is
desc ibed in [8]. I is di e en iable, ewa ds high a iances [8], and is con inous
o e he whole sea ch domain. A disad an age is he high e o o i s exac
compu a ion, in pa icula when mo e han wo objec i es a e conside ed.
4.3 SMS-EGO
SMS-EGO, as sugges ed by Ponweise e al. [27], employs a hype olume based
in ill c i e ion as well. The eby, a po en ial solu ion is compu ed using he lowe
con idence bound ˆypo = ˆy−αˆs, whe e ˆyis he mean alue p edic ed by he
K iging model, ˆsis he a iance, αis a gain ac o o he a iance. This app oach
may also explo e un isi ed egions o he design space, bu wi hou equi ing
he edious in eg a ion o he p e ious app oaches. I hus scales be e wi h
inc easing objec i e dimension.
I he esul ing ˆypo is -domina ed o domina ed, SMS-EGO will assign a
penal y alue. I i is non-domina ed, he hype olume con ibu ion will be used.
This app oach a oids pla eaus o he c i e ion, bu in eg a es non di e en iable
pa s. Fo mo e de ails see Ponweise e al. [27] and Wagne e al. [30].
4.4 MSPOT
MSPOT is a mul i-c i e ia app oach based on he Sequen ial Pa ame e Op i-
miza ion Toolbox SPOT (c . Zae e e e al. [33]). I does no employ any o m o
expec ed imp o emen , o o he o ms o using he a iance o explo a ion. The
su oga e models o he di e en objec i es a e exploi ed by using a mul i-c i e ia
op imiza ion algo i hm ( o ins ance: SMS-EMOA o NSGA-II).
This will yield a popula ion o p omising poin s. One o mo e poin s o hese
a e chosen o e alua ions on he eal a ge unc ion. This selec ion is based
8 Zae e e e al.
on non-domina ed so ing and he indi idual hype olume con ibu ion. As he
o iginal app oach [33] could lead o clus e ing o solu ions in he objec i e space,
he a ailable poin s ha e o be conside ed when calcula ing he hype olume con-
ibu ions. Fo his pu pose, he known poin s a e ee alua ed on he su oga e
model.
In con as o he o he app oaches in he s udy, his one does no p omo e
explo a ion as much, since he a iance measu e compu ed by he K iging model
will no be used. On he o he hand, he app oach is no limi ed o su oga e
modeling me hods ha yield a a iance o each candida e. O cou se, he a i-
ance can easily be added o MSPOT, as well as be emo ed om SMS-EGO
(α= 0) o he in eg a ion-based algo i hms (ˆs= 0).
The op imiza ion p ocess o MSPOT is no a comple ely new idea. Espe-
cially, wo simila app oaches sugges ed p e iously ha e o be men ioned. Fi s ly,
Vou chko and Keane [29] employed NSGA-II o gene a e p omising solu ions in
a qui e simila op imiza ion loop. In con as o MSPOT, hey used Euclidean
dis ance o ensu e e enly spaced poin s on he on . Ins ead o conside ing dis-
ance o known poin s, hey sugges a la ge numbe poin s in each loop, which
also ensu es a wide sp ead on he inal on . The second simila app oach is
p esen ed by Jeong and Obayashi [15]. While hey also op imize he objec i es
sepa a ely, hey employ he single objec i e EI c i e ion o each objec i e, hus
op imizing a ec o o EI alues.
4.5 SMS-EMOA
In addi ion o he ou app oaches abo e, a simple SMS-EMOA will be conside ed
(c . Beume e al. [2]). The esul s om his op imize a e used as a baseline o
he compa ison. In gene al, su oga e op imiza ion me hods a e expec ed o
ou pe o m a non-su oga e SMS-EMOA, pa icula ly on small budge s.
5 Expe imen al Se up
The ollowing esea ch ques ions a e o be ea ed o he CANARY p oblem in
his s udy.
1. Can mul i-c i e ia me hods p oduce a on o pa ame e se ings ha help
an ope a o o choose pa ame e s o he CANARY e en de ec ion so wa e?
2. Which kind o une is ecommendable?
3. Wha aspec s o a une a ec i s pe o mance?
4. Is he use o su oga e models ad an ageous?
5. Can p e ious indings abou he une s be con i med?
6. How a e Pa e o op imal solu ions sp ead in he design space?
To answe hese ques ions, se e al expe imen s we e conduc ed. Thei se up
is desc ibed in he ollowing.
MCO uning o E en De ec ion So wa e 9
5.1 Time Se ies Da a
Two di e en se s o aw da a a e used. The i s se is used o ain CANARY
(i.e. o une he pa ame e s), he second is used o alida ion o he esul ing
se ings on unseen da a. Addi ionally, om each o hose se s, 3 di e en in-
s ances a e gene a ed, whe e each con ains simula ed (i.e. supe imposed) e en s
o be de ec ed by CANARY. The da a se s conside ed a e a ailable wi hin he
CANARY so wa e package.
T aining Da a The da a eco ded o e a i s mon h a a speci ic measu emen
s a ion is used as aining da a. Fou di e en senso alues a e used (pH-Value,
Conduc i i y, To al O ganic Ca bon, Chlo ine). The ime in e al be ween mea-
su emen s is i e minu es. This esul s in abou 9 000 ime s eps o each o he
ou senso s.
As he da a-se con ains no e en s known be o ehand (which is a ypical
p oblem o any a ailable eal-wo ld da a), e en s ha e o be simula ed and
inco po a ed in he ime se ies. The e o e, 3 da a se s a e c ea ed om he aw
da a, each con aining supe imposed squa e wa es (wi h smoo hed ansi ion) o
di e en e en s eng hs: 0.5, 1, and 1.5. These s eng hs indica e he ampli ude
o he e en s, and a e mul iplied o he s anda d de ia ion o he o iginal signal.
Figu e 2 p esen s aw da a and da a wi h e en s o wo senso alue as an
example.
As can be seen om he le pa o Fig. 2, he aw da a (i.e. wi hou e en s)
is a he s ongly a ec ed by backg ound changes. This pa icula ly holds o
he conduc i i y alues (COND), which jump om a baseline alue a ound 50
o a new baseline alue a abou 200 and back. In gene al, hese backg ound
changes a e i egula ly dis ibu ed o e ime and always swi ch back and o h
o each o he signals. Ob iously, such changes make e en de ec ion ex emely
di icul .
Valida ion Da a The alida ion da a is simila o he aining da a, as i is he
second mon h o da a om he same measu emen s a ion. As could be expec ed,
i p o ides a e y simila backg ound beha io wi h some sudden jumps. These
jumps, howe e , a e mo e nume ous han in he aining da a, which is expec ed
o lead o highe alse ala m a es on he alida ion da a.
5.2 Op imiza ion P oblem Con igu a ion
As men ioned ea lie , h ee di e en da a se s a e conside ed, each wi h a di e -
en e en s eng h. Addi ionally, CANARY is uned in 3 di e en con igu a ions,
whe e each con igu a ion uses a di e en ime se ies p edic ion algo i hm. These
a e: Time Se ies Inc emen TSI, Linea P edic ion Co ec ion Fil e LPCF and
Mul i-Va ia e Nea es Neighbo MVNN. Fo mo e de ails on hese algo i hms,
which a e implemen ed in CANARY, see he co esponding documen a ion [26]
and he manual [14]. The e o e, 3 ×3 = 9 ins ances a e o be op imized. The
16 Zae e e e al.
be conside ed ha addi ional explo a ion is al eady inhe en in he selec ion
p ocess as no one single op imum, bu a se o poin s is demanded.
To isualize he p oblem landscape, Fig. 6 shows con ou plo s o e e ence
DACE-models o each objec i e. These models we e buil by combining he de-
signs o all algo i hms and selec ing some ep esen a i es based on he dis ance
o an op imized La in hype cube design. Whe eas, he models seem o ha e a
a he unimodal shape, he e a e clus e s o op imal solu ions due o a sligh ly
oscilla ing beha io in he pla eau egions. This e ec can be obse ed using
he model p edic ions and he ac ual da a. As a consequence, he app oxima-
ion o he knee egion wi h window sizes be ween 200 and 400 and a h eshold
be ween 1.0 and 1.5 should be easy, whe eas he ex eme ones migh become a
mul imodal p oblem.
MCO uning o E en De ec ion So wa e 17
Fig. 6: P oblem landscape o bo h objec i es. Con ou s show DACE-model based on
ep esan a i es om all e alua ions on his ins ance (Algo i hm MVNN and e en
s eng h 1.5). Black do s show all eal pa e o op imal solu ions ound. G ey do s show
pa e o op imal solu ions on he model, yielded wi h g id sampling.
18 Zae e e e al.
7 Summa y
In his s udy, we es ed di e en app oaches based on su oga e op imiza ion
o une an e en de ec ion so wa e. Mos o he analysis was ocused on he
esul s o aining da a, since he esul s on alida ion da a mainly p o ided
simila esul s as on he aining da a. The su oga e op imiza ion app oaches
a e mos ly able o ou pe o m a baseline SMS-EMOA. The MEI-SPOT app oach
p o ed o be he excep ion om his obse a ion, which con i ms ea lie indings
by Wagne e al. [30]. This app oach o calcula ing he expec ed imp o emen
o mul iple c i e ia seems o be un a o able.
The e was no decisi e di e ence be ween he o he es ed app oaches, ega d-
less whe he a iance was used in he app oach (SMS-EGO and SExI-EGO) o
no (MSPOT and SMS-EGO wi h ze o gain). Plo s o he model s uc u es seem
o indica e an almos unimodal i ness landscape o bo h objec i es. This in-
dica es ha he addi ional explo a ion by a iance migh no be needed he e,
since he i ness landscape is easy o app oxima e wi hou addi ional explo a ion
o he design space.
This s udy showed ha he p oblem o uning CANARY can easonably be
sol ed by mul i-c i e ia me hods. The p oduced esul s yield easonable FPR
and TPR alues, which a e compa able o p e ious esul s achie ed by single-
objec i e op imiza ion. He e, howe e , he app oxima ion o a Pa e o on o e s
mo e lexibili y o he ope a o in cha ge.
8 Ou look
The ollowing opics will be subjec o u u e esea ch.
–Since he addi ional explo a ion by a iance does no dec ease pe o mance
signi ican ly, i migh be in e es ing o es he lowe con idence bound in
MSPOT o u u e expe imen s based on o he p oblems.
–I has o be no ed ha only poin s on he con ex hull o he Pa e o on
can be conside ed o be op imal in some sense. This is due o he ac , ha
any poin below ha hull migh be conside ed o be imp o able [11]. Fu u e
wo k should in es iga e i conca i ies in he ROC cu e can be epai ed o
he applica ion desc ibed he e.
–The concen a ion on ce ain egions o a Pa e o on migh be a opic o
u u e esea ch as well. An ope a o migh be mo e in e es ed in he knee
egion o he Pa e o on , and less on ex eme alues, which migh cause
in ole able numbe s o alse ala ms. Focusing on a subse o he Pa e o on
migh sa e u he e alua ions, hus educing he equi ed budge .
–As can be seen in Fig. 7 he K iging based app oaches gene a e simila e-
sul s, wi h one excep ion: The Maximum Likelihood Es ima ion Gaussian
P ocesses (MLEGP) a ian seems o ou pe o med by he o he wo a i-
an s. This demands u he in es iga ion. The e o e, we plan a mo e de ailed
compa ison o di e en K iging based app oaches.
MCO uning o E en De ec ion So wa e 19
emax: 0.5
emax: 1
emax: 1.5
●
●
●
●
●
●
●
●
●●
●●●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
0.75
0.80
0.85
0.75
0.80
0.85
0.90
0.80
0.84
0.88
0.92
a ype: inc
a ype: lpc
a ype: m nn
DACE
Fo es e
MLEGP
MLP
QRNN
eSVM
kSVM
MARS
RF
LM
DACE
Fo es e
MLEGP
MLP
QRNN
eSVM
kSVM
MARS
RF
LM
DACE
Fo es e
MLEGP
MLP
QRNN
eSVM
kSVM
MARS
RF
LM
Tune
Hype olume
Fig. 7: Compa ison o di e en models using he MSPOT app oach. DACE is he K ig-
ing model used in p e ious compa isons. Fo es e is a K iging model implemen ed in
SPOT based on Ma lab Code by Fo es e e al. [12]. MLEGP is he K iging implemen a-
ion Maximum Likelihood Es ima es o Gaussian P ocesses in he Rpackage mlegp [6].
MLP is a Mul i-laye pe cep on neu al ne wo k [23] om he Rpackage monmlp. QRNN
is Quan ile Reg ession Neu al Ne wo k om he q nn package [28, 4]. eSVM is a Sup-
po Vec o Machine implemen a ion in he package e1071 using LIBSVM [5]. kSVM
is a SVM in he ke nlab package [18]. MARS is Mul i a ia e Adap i e Reg ession
Splines [13] p o ided by he ea h Rpackage. RF is a Random Fo es implemen a ion
om he Rpackage andomFo es which is based on B eiman and Cu le ’s o iginal
Fo an code o classi ica ion and eg ession [3]. LM uses a Linea Model i ed wi h
he sm package [24].
20 Zae e e e al.
Acknowledgmen s This wo k has been kindly suppo ed by he Fede al Min-
is y o Educa ion and Resea ch (BMBF) unde he g an s MCIOP (FKZ 17N0311)
and CIMO (FKZ 17002X11). In addi ion, he pape is based on in es iga ions
o p ojec D5 “Syn hesis and mul i-objec i e model-based op imiza ion o p o-
cess chains o manu ac u ing pa s wi h unc ionally g aded p ope ies” as pa
o he collabo a i e esea ch cen e SFB/TR TRR 30, kindly suppo ed by he
Deu sche Fo schungsgemeinscha (DFG).
Re e ences
1. T. Ba z-Beiels ein, K. E. Pa sopoulos, and 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 Nume ical
Analysis and Compu a ional Ma hema ics (ANACM), 1(2):413–433, 2004.
2. N. Beume, B. Naujoks, and M. Emme ich. SMS-EMOA: Mul iobjec i e selec ion
based on domina ed hype olume. Eu opean Jou nal o Ope a ional Resea ch,
181(3):1653–1669, 2007.
3. L. B eiman. Random o es s. Machine Lea ning, 45(1):5 –32, 2001.
4. A. J. Cannon. Quan ile eg ession neu al ne wo ks: implemen a ion in and ap-
plica ion o p ecipi a ion downscaling. Compu e s & Geosciences, 37:1277–1284.
doi:10.1016/j.cageo.2010.07.005, 2011.
5. C.-C. Chang and C.-J. Lin. LIBSVM: A lib a y o suppo ec o machines. ACM
T ansac ions on In elligen Sys ems and Technology, 2:27:1–27:27, 2011. So wa e
a ailable a h p://www.csie.n u.edu. w/~cjlin/libs m.
6. G. M. Dancik and K. S. Do man. mlegp: s a is ical analysis o compu e models
o biological sys ems using . Bioin o ma ics, 24(17):1966–1967, 2008.
7. M. Emme ich. Single- and Mul i-objec i e E olu iona y Design Op imiza ion: As-
sis ed by Gaussian Random Field Me amodels. PhD hesis, Uni e si ¨a Do mund,
Ge many, 2005.
8. M. Emme ich, A. Deu z, and J. Klinkenbe g. Hype olume-based expec ed im-
p o emen : Mono onici y p ope ies and exac compu a ion. In E olu iona y Com-
pu a ion (CEC), 2011 IEEE Cong ess on, pages 2147–2154. IEEE, 2011.
9. R. E e son and J. Fieldsend. Mul i-objec i e op imisa ion o ecei e ope a ing
cha ac e is ic analysis. In Y. Jin, edi o , Mul i-Objec i e Machine Lea ning, ol-
ume 16 o S udies in Compu a ional In elligence, pages 533–556. Sp inge Be lin /
Heidelbe g, 2006.
10. P. A. Flach. ROC Analysis, pages 869–875. Sp inge , Decembe 2010.
11. P. A. Flach and S. Wu. Repai ing conca i ies in oc cu es. In P oceedings o
he 19 h in e na ional join con e ence on A i icial in elligence, IJCAI’05, pages
702–707, San F ancisco, CA, USA, 2005. Mo gan Kau mann Publishe s Inc.
12. A. Fo es e , A. Sobes e , and A. Keane. Enginee ing Design ia Su oga e Mod-
elling. Wiley, 2008.
13. J. H. F iedman. Mul i a ia e adap i e eg ession splines. Ann. S a ., 19(1):1–141,
1991.
14. D. B. Ha , K. A. Klise, E. D. Vug in, S. A. McKenna, and M. P. Wilson. Cana y
use ’s manual and so wa e upg ades. Technical Repo EPA/600/R-08/040A, U.S.
En i onmen al P o ec ion Agency, Washing on, DC, 2009.
15. S. Jeong and S. Obayashi. E icien global op imiza ion (EGO) o mul i-objec i e
p oblem and da a mining. In D. Co ne e al., edi o s, IEEE Cong ess on E olu-
iona y Compu a ion, pages 2138–2145. IEEE, 2005.
MCO uning o E en De ec ion So wa e 21
16. 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):3–12, 2005.
17. D. Jones, M. Schonlau, and W. Welch. E icien global op imiza ion o expensi e
black-box unc ions. Jou nal o Global Op imiza ion, 13:455–492, 1998.
18. A. Ka a zoglou, A. Smola, K. Ho nik, and A. Zeileis. ke nlab – an S4 package o
ke nel me hods in R. Jou nal o S a is ical So wa e, 11(9):1–20, 2004.
19. A. Keane. S a is ical imp o emen c i e ia o use in mul iobjec i e design op i-
misa ion. AIAA Jou nal, 44(4):879–891, 2006.
20. J. Knowles. Pa ego: A hyb id algo i hm wi h on-line landscape app oxima ion o
expensi e mul iobjec i e op imiza ion p oblems. IEEE T ansac ions on E olu ion-
a y Compu a ion, 10(1):50–66, Janua y 2006.
21. J. D. Knowles and H. Nakayama. Me a-modeling in mul iobjec i e op imiza ion.
In Mul iobjec i e Op imiza ion, pages 245–284. Sp inge , 2008.
22. M. A. Kupinski and M. A. Anas asio. Mul iobjec i e gene ic op imiza ion o diag-
nos ic classi ie s wi h implica ions o gene a ing ecei e ope a ing cha ac e is ic
cu es. IEEE T ansac ions on Medical Imaging, 18:675–685, 1999.
23. B. Lang. Mono onic mul i-laye pe cep on ne wo ks as uni e sal app oxima o s.
In W. Duch, J. Kacp zyk, E. Oja, and S. Zad ozny, edi o s, A i icial Neu al Ne -
wo ks: Fo mal Models and Thei Applica ions ICANN 2005, olume 3697 o Lec-
u e No es in Compu e Science, pages 31–37. Sp inge Be lin Heidelbe g, 2005.
24. R. V. Len h. Response-su ace me hods in R using sm (upda ed o e sion 1.40).
Technical epo , The Uni e si y o Iowa, 2010.
25. S. Lopha en, H. Nielsen, and J. Sønde gaa d. DACE—A Ma lab K iging Toolbox.
Technical Repo IMM-REP-2002-12, In o ma ics and Ma hema ical Modelling,
Technical Uni e si y o Denma k, Copenhagen, Denma k, 2002.
26. R. Mu ay, T. Hax on, S. A. McKenna, D. B. Ha , K. Klise, M. Koch, E. D. Vu-
g in, S. Ma in, M. Wilson, V. C uz, and L. Cu le . Wa e quali y e en de ec ion
sys ems o d inking wa e con amina ion wa ning sys ems—de elopmen , es -
ing, and applica ion o CANARY. Technical Repo EPA/600/R-10/036, Na ional
Homeland Secu i y Resea ch Cen e , May 2010.
27. W. Ponweise , T. Wagne , D. Bie mann, and M. Vincze. Mul iobjec i e op imiza-
ion on a limi ed budge o e alua ions using model-assis ed -me ic selec ion. In
PPSN, pages 784–794, 2008.
28. J. W. Taylo . A quan ile eg ession neu al ne wo k app oach o es ima ing he
condi ional densi y o mul ipe iod e u ns. Jou nal o Fo ecas ing, 19(4):299–311,
2000.
29. I. Vou chko and A. Keane. Mul iobjec i e op imiza ion using su oga es. In
Adap i e Compu ing in Design and Manu ac u e ACDM, pages 167–175, 2006.
30. T. Wagne , M. Emme ich, A. Deu z, and W. Ponweise . On expec ed-imp o emen
c i e ia o model-based mul i-objec i e op imiza ion. Pa allel P oblem Sol ing
om Na u e–PPSN XI, pages 718–727, 2010.
31. P. Wang, K. Tang, E. Tsang, and X. Yao. Mul iobjec i e gene ic p og amming o
maximizing ROC pe o mance. Neu ocompu ing, 2012.
32. M. Zae e e . Op imiza ion and empi ical analysis o an e en de ec ion so wa e o
wa e quali y moni o ing. Mas e ’s hesis, Cologne Uni e si y o Applied Sciences,
May 2012.
33. M. Zae e e , T. Ba z-Beiels ein, M. F iese, B. Naujoks, and O. Flasch. Mul i-
c i e ia op imiza ion o ha d p oblems unde limi ed budge s. In T. Soule e al.,
edi o s, GECCO Companion ’12: P oceedings o he ou een h in e na ional con-
e ence on Gene ic and e olu iona y compu a ion con e ence companion, pages
1451–1452, Philadelphia, Pennsyl ania, USA, July 2012. ACM.
Kon ak /Imp essum
Diese Ve ¨o en lichungen e scheinen im Rahmen de Sch i en eihe ”CIplus”. Alle
Ve ¨o en lichungen diese Reihe k¨onnen un e
www.ciplus- esea ch.de
ode un e
h p://opus.bsz-bw.de/ hk/index.php?la=de
abge u en we den.
K¨oln, Janua 2012
He ausgebe / Edi o ship
P o . D . Thomas Ba z-Beiels ein,
P o . D . Wol gang Konen,
P o . D . Ho s S enzel,
D . Bo is Naujoks
Ins i u e o Compu e Science,
Facul y o Compu e Science and Enginee ing Science,
Cologne Uni e si y o Applied Sciences,
S einm¨ulle 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 o ice
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,
Cologne Uni e si y o Applied Sciences,
S einm¨ulle allee 1, 51643 Gumme sbach
phone: +49 2261 8196 6391
u l: h p://www.gm. h-koeln.de/~ba z/
eMail: homas.ba z-beiels ein@ h-koeln.de
ISSN (online) 2194-2870
