Sch i en eihe CIplus, Band 1/2013
He ausgebe : T. Ba z-Beiels ein, W. Konen, H. S enzel, B. Naujoks
A Gen le In oduc ion o
Mul i-C i e ia Op imiza ion wi h
SPOT
Ma in Zae e e , Bo is Naujoks, Thomas Ba z-Beiels ein
A Gen le In oduc ion o Mul i-C i e ia
Op imiza ion wi h SPOT
Ma in Zae e e , Bo is Naujoks, and Thomas Ba z-Beiels ein
Facul y o Compu e and Enginee ing Sciences
Cologne Uni e si y o Applied Sciences, 51643 Gumme sbach, Ge many
i s name.las name@ h-koeln.de
Sch i en eihe CIplus
TR 1/2013. ISSN 2194-2870
Abs ac . Mul i-c i e ia op imiza ion has gained inc easing a en ion
du ing he las decades. This a icle exempli ies mul i-c i e ia ea u es,
which a e implemen ed in he s a is ical so wa e package SPOT. I de-
sc ibes ela ed so wa e packages such as mco and emoa and gi es a
comp ehensi e in oduc ion o simple mul i c i e ia op imiza ion asks.
Se e al hands-on examples a e used o illus a ion. The a icle is well-
sui ed as a s a ing poin o pe o ming mul i-c i e ia op imiza ion asks
wi h SPOT.
1 Mul i C i e ia Op imiza ion: A Simple Example
Op imiza ion in gene al is ully in eg a ed in o odays li e. We decide o he
bes p ize when compa ing simila g oce ies o choose he bes quali y when
compa ing di e en jacke s. Howe e , such decisions a e gene ally mo e di icul ,
mo e complex han jus deciding ei he o he bes p ice o he bes quali y.
Some so o comp omise solu ion migh be p e e able. This is whe e mul i-
c i e ia op imiza ion comes in o play.
O cou se, he same holds o indus ial p ocesses. Inpu ma e ial has o be
selec ed and he p ocess i sel can be s ee ed in di e en di ec ions ia con ol-
ling some inpu a iables. All hese decisions will in luence he quali y o he
inal p oduc , whe eas quali y can be exp essed in o m o di e en c i e ia o
objec i es (e.g., p ice, obus ness, speed). As a consequence, a decision ega ding
he abo e men ioned inpu pa ame e s can a ely be made wi hou conside ing
mul iple c i e ia a once.
The e a e some aspec s ha make such decisions mo e complica ed han
classical single objec i e p oblems. The mos appa en one is he loss o o al
o de . Compa ing wo p oduc s o p ocesses jus based on hei p ice is easy.
The cheape is he be e . I quali y comes in o play, li e is much ha de . Se e al
p oduc s migh exis which ep esen di e en comp omises be ween quali y and
p ice. Fo example, le us conside he choice o selec ing a ca . Ca no. 1 may be
he cheapes , bu also he one wi h he highes milage, whe eas ca no. 2 is he
one wi h he leas milage bu also mos expensi e one. The e may exis se e al
MCO wi h SPOT 3
mo e ca s which ep esen di e en comp omises be ween milage and p ice. An
example o ha si ua ion is ep esen ed in Fig. 1.
P ice [€]
Milage
[l / 100 km]
20.000 30.000
5
15
10
25000
Fig. 1: G aphical compa ison o 6 ca s, ega ding p ice and milage.
These solu ions canno be so ed by hei ela i e quali y o each o he since
he wo goals (milage and p ice) a e con lic ing. The o al o de o solu ions is
los . Only he ca ma ked by he ed do is clea ly wo se, because he e exis
ca s which a e be e wi h ega ds o bo h objec i es.
O cou se, hings ge mo e di icul (and e en mo e compu a ionally expen-
si e) i mo e han jus wo c i e ia ha e o be conside ed. Fo example, one could
conside addi ional c i e ia like en i onmen al sus ainabili y o sa e y o he ca .
A he same ime, his decision p ocess can be made ega ding di e en inpu
pa ame e s. Fo he consume , he choice ha a ec s he di e en c i e ia is
me ely ha o he six ca s a ailable. Fo he p oduce o he ca s, he ca s can
be de ined by di e en pa ame e s like hei ma e ial, shape o ype o mo o .
The ield o Mul i C i e ia Op imiza ion (MCO) deals wi h ha ype o
p oblems. The Sequen ial Pa ame e Op imiza ion Toolbox o e s me hods om
ha ield, which employ su oga e models o speed up he op imiza ion p og ess.
The ollowing Sec. 2in oduces he ield o MCO as well as he nomencla u e.
A e wa ds, Sec. 3p esen s he p og amming en i onmen R and some basic
ools o MCO in ha en i onmen . To gi e an easy o use example, Sec. 4
in oduces a simple MCO es unc ion, and shows how o op imize his wi h
4 Zae e e e al.
classical MCO algo i hms. The e y same es unc ions is op imized wi h he
Sequen ial Pa ame e Op imiza ion Toolbox SPOT in Sec. 5. To gi e mo e de ails
on he usage o SPOT addi ional ea u es a e shown in Sec. 6. Finally, he eade
can es his unde s anding o he p esen ed in o ma ion in Sec. 7.
2 Sho o e iew on MCO
Conside ing only one objec i e in applied op imiza ion is a simpli ica ion ha
does no mi o he complexi y o he unde lying applica ion in mos (o almos
all) cases. No mally, mo e han one and up o hund eds o housands o objec i es
1, . . . , nneed o be conside ed. The mos common way o deal wi h mul iple
objec i es appea s o be agg ega ion, e.g., o a weigh ed sum (x) = Piwi i(x).
In con as , mul i-c i e ia o mul iobjec i e op imiza ion (MCO) o e s a di e en
way o handle mul iple objec i es in a mo e p incipled, maybe mo e e ec i e way.
In MCO, a well-known concep is Pa e o dominance, i.e., a solu ion x om a
decision space Adomina es ano he solu ion y∈Ai xis be e in a leas one
dimension o he decision space and no wo se in all he o he s. Mo e o mally
and conside ing minimiza ion, his eads (A⊂Rn,i, j ∈ {1, . . . , n}):
x≺yi ∀i: i(x)≤ i(y)∧
∃j: j(x)< j(y).
I a solu ion xis no domina ed by any o he solu ion in he sea ch space (o
gene a ed by he algo i hm), i is said o be nondomina ed, i.e.
∀y∈A:y6≺ x.
This concep allows o anking se s o solu ions in he mul i-dimensional
objec i e space. As a consequence, MCO algo i hms aim o a se A∗o solu ions
wi h he p ope y ha e e y wo solu ions xand y om A∗a e mu ually non-
domina ed, i.e.
y6≺ x∧x6≺ y.
A se {x∈A| 6 ∃y∈A:y≺x}o such solu ions is also called a Pa e o- on .
Coming back o he ca example om abo e, all bu he ca ma ked in ed
in Fig. 1a e non-domina ed, and hus ep esen he Pa e o- on . The ed poin
is domina ed by wo o he do s.
2.1 E olu iona y Mul iobjec i e Op imiza ion Algo i hms
Beside he shee numbe o objec i es, he e is a s uc u al change in he s ep
om one o mo e objec i es. The s ic o de o solu ions in he single-objec i e
objec i e space u ns o a pa ial o de in he mul i-objec i e objec i e space
(wi h espec o Pa e o dominance). This is one o he easons why popula ion-
based op imiza ion app oaches like EA a e e y success ul in ackling MCO
MCO wi h SPOT 5
p oblems. This s uc u al change also implies ha besides Pa e o dominance a
seconda y quali y indica o is equi ed o anking and hus o ank-based selec-
ion in an EA. As a esul , e olu iona y mul iobjec i e op imiza ion algo i hms
(EMOA) became e y popula o e he las decade(Deb,2001a;Coello Coello
e al.,2007).
Such algo i hms always keep a se o solu ions, also called a popula ion,
du ing he op imiza ion un and hus p o ide a decision make wi h a se o
compa ably good, non-domina ed solu ions, no jus one inal bes like in single-
objec i e op imiza ion. As a consequence, he decision make has he chance and
he bu den o choose he inal solu ion, he one o eally implemen , om a se
o such solu ions.
In ecen yea s, he hype olume indica o u ned om a equen ly used
quali y indica o o a well-es ablished selec ion ope a o o EMOA (Zi zle &
Thiele,1998;Zi zle ,1999). The hype olume o a Pa e o on A∗is de ined
as he n-dimensional olume o he space spanned by he Pa e o on and a
e e ence poin y e , which needs o be de ined by he use :
Λ [
a∈A∗
{y0|a≺y0≺y e }!
wi h Λ being he Lebesgue measu e o he gi en se .
Maximiza ion o he hype olume co e ed by he popula ion esul s in max-
imiza ion o possible ade-o s. Implici ly his co e s he adi ional goals o
con e gence o he solu ion se o he op imal on as well as good solu ion
sp ead. Mos p ominen ins ances o hype olume based selec ion MCO algo-
i hms a e SMS-EMOA (Beume e al.,2007a), Hyp-E (Bade & Zi zle ,2011),
as well as MO-CMA-ES (Igel e al.,2007).
The (µ+ 1) selec ion mechanism in SMS-EMOA (c . Alg. 1) p o ides an
elegan way o enla ge and diminish he popula ion size online. The e o e his
algo i hm is used o he p esen s udy.
Algo i hm 1: SMS-EMOA
1P0←ini () ; // Ini ialize µindi iduals andomly
2 ←0 ;
3 epea
4q +1 ←gene a e(P ) ; // Gene a e o sp ing by a ia ion
5P +1 ← educe(P ∪ {q +1}) ; // Selec new popula ion
6 ← + 1
7un il s opc i e ium eached;
In Algo i hm 2
∆S(s, RI) := S(RI)− S(RI {s}) (1)
6 Zae e e e al.
Algo i hm 2: Reduce(Q)
1R ← as -nondomina ed-so (Q) ; // all Inon-domina ed on s o Q
2 ←a gmins∈RI[∆S(s, RI)] ; // elimina e elemen wi h lowes ∆S(s, RI)
3Q0←Q { } e u n Q0
calcula es he sole con ibu ion o a single solu ion s o he hype olume o a
Pa e o on RI.
MCO wi h SPOT 7
3 MCO in R: Language, Packages, Algo i hms
In R, he open sou ce p og amming en i onmen o s a is ical compu ing,
some packages implemen unc ionali y o MCO1. We in oduce h ee packages,
which implemen se e al impo an unc ions and algo i hms. The e a e mo e
MCO- ele an packages, which a e no co e ed he e. We encou age addi ional
esea ch o in e es ed use s2.
3.1 The mco package
The mco package p o ides se e al unc ions conce ning MCO wi h gene ic
algo i hms. Mos impo an ly, i p o ides an implemen a ion o he NSGA2 algo-
i hm. Se e al measu es o a Pa e o on s quali y a e a ailable as unc ions (e.g.,
Sp ead, Hype olume, Epsilon-Indica o ). Addi ionally, se e al ypical MCO es
unc ions a e p o ided (e.g., ZDT1-3).
3.2 The emoa package
The emoa package p o ides se e al use ul unc ions, including se e al mea-
su es like hype olume con ibu ion o c owding dis ance. I also has se e al es
unc ions ha a e no in he mco package.
3.3 The SPOT package
The SPOT package p o ides mainly he means o do mul i objec i e su oga e
model based op imiza ion. Addi ionally, i uses he emoa package o cons uc
a e y basic SMS-EMOA implemen a ion. Mo e in o ma ion will be gi en in
sec ion 5.
4 A simple Tes unc ion: ZDT2
The es unc ion used in he ollowing examples is pa o he ”mco” R-
package3. In his example, i is expec ed ha his package is al eady ins alled.
To ins all, uncommen he i s wo lines below. The mco package also con ains
he NSGA2 algo i hm (Deb,2001b). SPOT should be loaded, oo, o he pu pose
o op imiza ion.
> #ins all.packages("mco")
> #ins all.packages("SPOT")
> equi e("mco")
> equi e(SPOT)
1R, and all packages men ioned in his documen , a e a ailable om he CRAN
pla o m: h p://c an. -p ojec .o g/
2The h p://www. seek.o g/ home page migh be a i s s a poin o a sea ch on
MCO in R.
3h p://c an. -p ojec .o g/web/packages/mco/
8 Zae e e e al.
The ZDT unc ions a e MCO es unc ions wi h scalable decision space di-
mension n(Zi zle e al.,2000). To gua an ee a low numbe o unc ion e alua-
ions as well as easy isualiza ion o esul s, bo h, he dimension o he decision
and he objec i e space a e se o 2 in ollowing example. The unc ion ZDT2
R2→R2is de ined as:
1=x1
g= 1 + 9x2
2=g 1−x1
g2!
0≤x1≤1
0≤x2≤1
Bo h objec i es 1and 2ha e o be minimized. In he R-package mean(), he
ZDT2 unc ion can be called as ollows.
> x=c(0.5,0.4) #Inpu ec o
> y=zd 2(x)
> p in (y)
[1] 0.500000 4.545652
The objec i e space o he ZDT2 unc ion can be isualized in sepa a e
su ace plo s. The e o e, we will conside he ollowing unc ion: R2→R:
(x1, x2)7→ 1(x1, x2). No e, we will use he apply(x) command o de ine
an anonymous unc ion.
> apply(x,1, )
will apply o ows o x,
> apply(x,2, )
will apply o columns o x.
> ## De ine unc ion ha calls ZDT2 in a ec o ized manne
> ## bu e u ns only i s objec i e:
> ZDT2obj1= unc ion(x)apply(x,1,zd 2)[1,]
> ## Plo i s objec i e in gi en bounda ies
> ## (lo o lowe , up o uppe )
> spo Su Con ou ( =ZDT2obj1,lo=c(0,0),up=c(1,1))
MCO wi h SPOT 9
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.2 0.4 0.6 0.8 1.0
0.0
0.2
0.4
0.6
0.8
1.0
x1
x2
To isualize he impac o he second objec i e, we will conside he ollowing
unc ion: R2→R: (x1, x2)7→ 2(x1, x2):
> ## De ine unc ion ha calls ZDT2 in a ec o ized manne ,
> ## bu e u ns only second objec i e:
> ZDT2obj2= unc ion(x)apply(x,1,zd 2)[2,]
> ## Plo second objec i e in gi en bounda ies
> ## (lo o lowe , up o uppe )
> spo Su Con ou ( =ZDT2obj2,lo=c(0,0),up=c(1,1))
16 Zae e e e al.
> spo (spo Con ig=append(lis ( epo . unc="spo Repo Con ou ",
+ epo .in e ac i e=FALSE), es2),spo Task=" ep")
0
2
4
6
8
10
●
●
●
●●●●● ●
●
● ●● ●
●●
●●●●
0.0 0.4 0.8
0.0
0.2
0.4
0.6
0.8
1.0
p edic ed Model: Y.2
VARX1
VARX2
0.0
0.2
0.4
0.6
0.8
1.0
●
●
●
●●●●● ●
●
● ●● ●
●●
●●●●
0.0 0.4 0.8
0.0
0.2
0.4
0.6
0.8
1.0
p edic ed Model: Y.1
VARX1
VARX2
In hese con ou plo s, c osses indica e a poin sampled on he a ge unc ion
and black do s (he e: e y close o he ho izon al axis) indica e poin s ha belong
o he app oxima ed Pa e o on .
Wi h he abo e se ing o epo .in e ac i e = FALSE, he su ace plo s
will always show he beha io o he i s wo op imized pa ame e s. I mo e
han wo a e op imized, he use can use a simple GUI (see Fig. 2) o choose
wo pa ame e s o plo ing:
> spo (spo Con ig=append(lis ( epo . unc="spo Repo Con ou ",
+ epo .in e ac i e=TRUE), es2),spo Task=" ep")
Fig. 2: Twiddle in e ace
He e, he use can choose which pa ame e s o plo , using he slide s aand b.
Slide Cspeci ies which poin om he Pa e o on should be used o de e mine
he emaining pa ame e s, which a e assumed o be cons an o he plo . When
jus wo pa ame e s a e op imized, his choice has no in luence.
6.2 Di e en models o each objec i e
In he abo e examples, each objec i e was modeled by he same chosen su o-
ga e modeling echnique. I could howe e occu , ha he use wishes o model
MCO wi h SPOT 17
he i s objec i e wi h a K iging model and he second wi h a Random Fo es
model.
This is possible, by using he ollowing con igu a ion:
> con ig$seq.p edic ionModel. unc="spo P edic MCO"
> con ig$mco.con igs=lis (lis (seq.p edic ionModel. unc="spo P edic Fo es e "),
+ lis (seq.p edic ionModel. unc="spo P edic RandomFo es "))
> es3<-spo (spo Con ig=con ig)
spo .R::spo s a ed
> es3$mco.h olume
[1] 110.097
He e, he mco.con igs elemen is a me a-lis con aining se e al con igu a ion lis s.
Any se ings no speci ied in mco.con igs will be aken om he main con ig-
u a ion lis (he e: con ig) o se o de aul alues. Ins ead o selec ing di e en
models, one can use he mco.con igs me a lis o choose di e en se ings o
wo models o he same ype.
7 Tasks
Imagine you ha e wo a ge unc ions, bo h wi h a sphe ical shape, bu wi h
hei cen e a di e en poin s. Assume ha bo h unc ions a e de ined as:
1(x1, x2)=(x1−2)2+ (x2+ 4)2(2)
2(x1, x2)=(x1+ 1)2+ (x2−3)2(3)
Toge he , hese unc ions o m a wo-objec i e op imiza ion p oblem, whe e
bo h 1and 2a e minimized. Please y o sol e he ollowing asks:
1. Implemen he op imiza ion p oblem in R.
2. Plo he a ge unc ions sepa a ely.
3. Wi hou using he compu e any u he , wha do you expec he Pa e o
on o look like? Desc ibe and/o d aw you idea.
4. Op imize he p oblem, using he NSGA2 Algo i hm in R.
5. Plo Pa e o on and Pa e o se o he NSGA2 esul s.
6. Op imize he p oblem using SPOT.
7. Plo he Pa e o on and se , compa e wi h NSGA2 esul s. Why do esul s
di e ? Also, Compa e wi h expec a ion om ques ion 3.
8. Plo he su oga e models wi h SPOT and check whe he hey ep esen he
ac ual a ge unc ions. I no , why?
9. In you opinion, which is he mos sui ed way o sol e his speci ic op imiza-
ion p oblem, and why?
8 Solu ions
Solu ions o he asks can be eques ed om he au ho s ia E-Mail.
Bibliog aphy
Bade , J. & Zi zle , E. (2011). HypE: An Algo i hm o Fas Hype olume-Based
Many-Objec i e Op imiza ion. E olu iona y Compu a ion, 19(1), 45–76.
Ba z-Beiels ein, T., Lasa czyk, C., & P euß, M. (2005). Sequen ial pa ame e
op imiza ion. In B. McKay & o he s (Eds.), P oceedings 2005 Cong ess on
E olu iona y Compu a ion (CEC’05), Edinbu gh, Sco land, olume 1 (pp. 773–
780). Pisca away NJ: IEEE P ess.
Beume, N., Naujoks, B., & Emme ich, M. (2007a). 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.
Beume, N., Naujoks, B., & Emme ich, M. (2007b). 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.
Chen, C. H. (1995). An e ec i e app oach o sma ly alloca e compu ing budge
o disc e e e en simula ion. In P oceedings o he 34 h IEEE Con e ence on
Decision and Con ol (pp. 2598–2605).
Coello Coello, C. A., Van Veldhuizen, D. A., & Lamon , G. B. (2007). E olu-
iona y Algo i hms o Sol ing Mul i-Objec i e P oblems. Sp inge , New Yo k,
2nd edi ion.
Deb, K. (2001a). Mul i-Objec i e Op imiza ion using E olu iona y Algo i hms.
Wiley-In e science Se ies in Sys ems and Op imiza ion. New Yo k NY: Wiley,
1 edi ion.
Deb, K. (2001b). Mul i-Objec i e Op imiza ion using E olu iona y Algo i hms.
New Yo k NY: Wiley.
F iedman, J. H. (1991). Mul i a ia e adap i e eg ession splines. Ann. S a .,
19(1), 1–141.
Igel, C., Hansen, N., & Ro h, S. (2007). Co a iance Ma ix Adap a ion o
Mul i-objec i e Op imiza ion. E olu iona y Compu a ion, 15(1), 1–28.
Zi zle , E. (1999). E olu iona y Algo i hms o Mul iobjec i e Op imiza ion:
Me hods and Applica ions. PhD hesis, Swiss Fede al Ins i u e o Technol-
ogy (ETH), Zu ich, Swi ze land.
Zi zle , E., Deb, K., & Thiele, L. (2000). Compa ison o Mul iobjec i e E o-
lu iona y Algo i hms: Empi ical Resul s. E olu iona y Compu a ion, 8(2),
173–195.
Zi zle , E. & Thiele, L. (1998). Mul iobjec i e Op imiza ion Using E olu iona y
Algo i hms—A Compa a i e S udy. In A. E. Eiben (Ed.), Pa allel P oblem
Sol ing om Na u e (PPSN V) (pp. 292–301).: Sp inge , Be lin.
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
