Beyond Particular Problem Instances: How to Create Meaningful and Generalizable Results

Sch i en eihe CIplus, Band 3/2012
Thomas Ba z-Beiels ein, Wol gang Konen, Ho s S enzel, Bo is Naujoks
Beyond Pa icula P oblem
Ins ances: How o C ea e
Meaning ul and Gene alizable
Resul s
Thomas Ba z-Beiels ein
Beyond Pa icula P oblem Ins ances: How o
C ea e Meaning ul and Gene alizable Resul s
Thomas Ba z-Beiels ein
www.spo se en.de
Facul y o Compu e and Enginee ing Sciences
Cologne Uni e si y o Applied Sciences,
51643 Gumme sbach, Ge many
Sch i en eihe CIplus
TR 3/2012. ISSN 2194-2870
Abs ac . Compu a ional in elligence me hods ha e gained impo ance
in se e al eal-wo ld domains such as p ocess op imiza ion, sys em iden-
i ica ion, da a mining, o s a is ical quali y con ol. Tools a e missing,
which de e mine he applicabili y o compu a ional in elligence me hods
in hese applica ion domains in an objec i e manne . S a is ics p o ide
me hods o compa ing algo i hms on ce ain da a se s. In he pas , se -
e al es sui es we e p esen ed and conside ed as s a e o he a . How-
e e , he e a e se e al d awbacks o hese es sui es, namely: (i) p oblem
ins ances a e somehow a i icial and ha e no di ec link o eal-wo ld se -
ings; (ii) since he e is a ixed numbe o es ins ances, algo i hms can
be i ed o uned o his speci ic and e y limi ed se o es unc ions;
(iii) s a is ical ools o compa isons o se e al algo i hms on se e al es
p oblem ins ances a e ela i ely complex and no easily o analyze. We
p opose a me hodology o o e come hese di icul ies. I is based on s an-
da d ideas om s a is ics: analysis o a iance and i s ex ension o mixed
models. This pape combines essen ial ideas om wo app oaches: p ob-
lem gene a ion and s a is ical analysis o compu e expe imen s.
1 In oduc ion
Compu a ional in elligence (CI) me hods ha e gained impo ance in se e al eal-
wo ld domains such as p ocess op imiza ion, sys em iden i ica ion, da a mining,
o s a is ical quali y con ol. Tools a e missing, which de e mine he applicabili y
o CI me hods in hese applica ion domains in an objec i e manne . S a is ics
p o ide me hods o compa ing algo i hms on ce ain da a se s. In he pas ,
se e al es sui es we e p esen ed and conside ed as s a e o he a . Howe e ,
he e a e se e al d awbacks o hese es sui es, namely:
–p oblem ins ances a e somehow a i icial and ha e no di ec link o eal-wo ld
se ings;
–since he e is a ixed numbe o es ins ances, algo i hms can be i ed o
uned o his speci ic and e y limi ed se o es unc ions. As a consequence,
s udies (benchma ks) p o ide insigh how hese algo i hms pe o m on his
speci ic se o es ins ances, bu no insigh on how hey pe o m in gene al;
Beyond Pa icula P oblem Ins ances 3
–s a is ical ools o compa isons o se e al algo i hms on se e al es p oblem
ins ances a e ela i ely complex and no easily o analyze.
We p opose a me hodology o o e come hese di icul ies. I is based on ideas
p esen ed in Ma co Chia andini’s and Yu i Goegebeu ’s seminal publica ion [10].
This me hodology, which gene a es p oblem classes a he han use one ins ance,
is cons uc ed as ollows. Fi s , we p e-p ocess he unde lying eal-wo ld da a.
In a second s ep, ea u es om hese da a a e ex ac ed. This ex ac ion elies
on he assump ion ha ma hema ical a iables can be used o ep esen eal-
wo ld ea u es. Since we a e using ime-se ies da a, s anda d ools om ime-
se ies analysis a e applicable. Fo example, decomposi ion echniques can be
applied o model he unde lying da a s uc u es. We ob ain an analy ic model o
he da a. Then, we pa ame ize his model. Based on his pa ame iza ion and
andomiza ion, we can gene a e in ini ely many new p oblem ins ances. F om
his in ini e se , we can d aw a limi ed numbe o p oblem ins ances which will
be used o he compa ison. Since p oblem ins ances a e selec ed andomly, we
apply andom and mixed models o he analysis [14]. Mixed models include ixed
and andom e ec s. A ixed e ec is an unknown cons an . I s es ima ion om
he da a is a common p ac ice in analysis o a iance (ANOVA) o eg ession.
A andom e ec is a andom a iable. We a e es ima ing he pa ame e s ha
desc ibe i s dis ibu ion, because—in con as o ixed e ec s—i makes no sense
o es ima e he andom e ec i sel .
We will p esen da a used in case s udies om d inking wa e managemen ,
ene gy p oduc ion, and inance. These examples co e se e al applica ion do-
mains and illus a es ha ou app oach is no limi ed o one speci ic p oblem
ins ance only. Fu he p oblem domains can be added in an gene ic manne . This
a icle combines ideas om wo app oaches: p oblem gene a ion and s a is ical
analysis o compu e expe imen s. The gene a ion o es p oblems, which a e
well- ounded and ha e p ac ical ele ance, is an on-going ield o esea ch o
se e al decades. [13] p esen a p oblem ins ance (landscape) gene a o ha is
pa ame e ized by a small numbe o pa ame e s, and he alues o hese pa am-
e e s ha e a di ec and in ui i e in e p e a ion in e ms o he geome ic ea u es
o he landscapes ha hey p oduce. The wo k p esen ed by Chia andini and
Goegebeu [10] p o ides he basis o ou s a is ical analysis. They p esen a sys-
ema ic and well-de eloped amewo k o mixed models. We will combine his
amewo k wi h ideas p esen ed in [5]. Basically, his a icle ies o ind answe s
o he ollowing undamen al ques ions in expe imen al esea ch.
(Q-1) How o gene a e p oblem ins ances?
(Q-2) How o gene alize expe imen al esul s?
The a icle is s uc u ed as ollows. Sec ion 2 in oduces eal-wo ld p oblems
and desc ibes a axonomy o hei ypical ea u es. Algo i hms and ypical ea-
u es a e desc ibed in Sec . 3. Objec i e unc ions and s a is ical models a e
in oduced in Sec . 4. These models ake p oblem and algo i hm ea u es in o
conside a ion. Sec ion 5 p esen s case s udies, which illus a e ou me hodology.
This a icle closes wi h a summa y and an ou look.
4 T.Ba z-Beiels ein
2 Fea u es o Real-Wo ld P oblems
2.1 P oblem Classes and Ins ances
Nowadays, i is a common p ac ice in op imiza ion o choose a ixed se o p ob-
lem ins ances in ad ance and o apply classical ANOVA o eg ession analysis.
In many expe imen al s udies a ew p oblem ins ances πi(i= 1,2, . . . , q)a e
used and esul s o some uns o he algo i hms αj(j= 1,2, . . . , h) on hese in-
s ances a e collec ed. The ins ances can be ea ed as blocks and all algo i hms
a e un on each single ins ance. Resul s a e g ouped pe ins ance πi. Analyses o
hese expe imen s shed some ligh on he pe o mance o he algo i hms on hose
speci ic ins ances. Howe e , he in e es o he esea che should no be jus he
pe o mance o he algo i hms on hose speci ic ins ances chosen, bu a he on
he gene aliza ion o he esul s o he en i e class Π. Gene aliza ions abou he
algo i hm’s pe o mance on new p oblem ins ances a e di icul o impossible in
his se ing.
Based on ideas om Chia andini and Goegebeu [10], o o e come his di -
icul y, we p opose he ollowing app oach: A small se o p oblem ins ances
{πi∈Π|i= 1,2, . . . , q}is chosen a andom om a la ge se , o class Π, o pos-
sible ins ances o he p oblem. P oblem ins ances a e conside ed as ac o le els.
Howe e , his ac o is o a di e en na u e om he ixed algo i hmic ac o s in
he classical ANOVA se ing. Indeed, he le els a e chosen a andom and he
in e es is no in hese speci ic le els bu in he p oblem class Π om which hey
a e sampled. The e o e, he le els and he ac o a e andom. Consequen ly, ou
esul s a e no based on a limi ed, ixed numbe o p oblem ins ances. They a e
andomly d awn om an in ini e se , which enables gene aliza ion.
2.2 Fea u e Ex ac ion and Ins ance Gene a ion
A p oblem class Πcan be gene a ed in di e en manne s. We will conside a i-
icial and na u al p oblem class gene a o s. A i icially gene a ed p oblems allow
ea u e gene a ion based on some p ede ined cha ac e is ics. They a e basically
heo y d i en, i.e., he esea che de ines ce ain ea u es such as linea i y o
mul i modali y. Based on hese ea u es, a model ( o mula) is cons uc ed. By
in eg a ing pa ame e s in o his o mula, many p oblem ins ances can be gen-
e a ed by pa ame e a ia ion. We will exempli y his app oach in he ollowing
pa ag aph. The second way, which will gene a e na u al p oblem classes, uses
a wo-s age app oach. Fi s , ea u es a e ex ac ed om he eal-wo ld sys em.
Based on his ea u e se , a model is de ined. Adding pa ame e s o his model,
new p oblem ins ances can be gene a ed. The e is also a hi d way o "gene a e"
es ins ances: i we a e lucky, many da a a e a ailable. In his case, we can
sample a limi ed numbe o p oblem ins ances om he la ge se o eal-wo ld
da a. The s a is ical analysis is simila o hese h ee cases.
A i icial Tes Func ions Se e al p oblem ins ance gene a o s ha e been p o-
posed o e he las yea s. Fo example, [13] p esen a landscape es gene a o ,
Beyond Pa icula P oblem Ins ances 5
which can be used o se up p oblem ins ances o con inuous, bound-cons ained
op imiza ion p oblems.
To keep his a icle ocused, we will p opose a simple es p oblem ins ance
gene a o , which is based on ime-se ies decomposi ion. Inspi ed by he ha monic
seasonal ime se ies model wi h sseasons, which can be o mula ed as
Y( ) = m( ) +
[s/2]
X
k=1
{sksin(2πk /s) + ckcos(2πk /s)}+Z( ),(1)
whe e m( )deno es he end and Z( ) he e o , we will de ine he ollowing
unc ion gene a o Y(·)
Y(x) = |b0+b1x+b2x2+ sin(b3πx/12) + cos(b4πx/12) + |,(2)
whe e he bi’s a e independen wi h bi∼ U[0, wi]and ∼ N(0,1) o i=
0,1,...,4.
The ec o w= (w0, w1, w2, w3, w4)0is used o de ine p oblem classes Π.
P oblem ins ances πcan be d awn om each ins ance class. Using di e en
andom seeds o a ixed win (2) esul s in di e en p oblem ins ances. These
ins ances will be ea ed as le els o ac o s in he s a is ical analysis. Ob iously,
min(y(x)) ≥0. Nine ypical p oblem ins ances a e illus a ed in Fig. 1. We con-
side he p oblem class Π1, which is based on w= (−0.1,0.01,0.001,10.0,10.0)0.
We will use his p oblem ins ance gene a o in Sec . 5 o demons a e ou ap-
p oach.
Na u al P oblem Classes This sec ion exempli ies he h ee undamen al
s eps o gene a ing eal-wo ld p oblem (RWP) ins ances, namely
1. Desc ibing he eal-wo ld sys em and i s da a
2. Fea u e ex ac ion and model cons uc ion
3. Ins ance gene a ion
We will illus a e his p ocedu e by using he classic Box and Jenkins ai line
da a [9]. These da a con ain he mon hly o als o in e na ional ai line passen-
ge s, 1949 o 1960.
> s (Ai Passenge s)
Time-Se ies [1:144] om 1949 o 1961: 112 118 132 129 121 135 148 148 136 119 ...
The ea u e ex ac ion is based on me hods om ime-se ies analysis. Because o
i s simplici y he Hol -Win e s me hod is popula in many applica ion domains.
I is able o adap o changes in ends and seasonal pa e ns. The mul iplica i e
Hol -Win e s p edic ion unc ion ( o ime se ies wi h pe iod leng h p) is
ˆ
Y +h= (a +hb )s −p+1+(h−1) mod p,

6 T.Ba z-Beiels ein
−100 0 50 100
0 2 4 6 8 10
−120:120
his. (−120:120)
−100 0 50 100
0 2 4 6 8 10
−120:120
his. (−120:120)
−100 0 50 100
02468
−120:120
his. (−120:120)
−100 0 50 100
0123456
−120:120
his. (−120:120)
−100 0 50 100
0 5 10 15
−120:120
his. (−120:120)
−100 0 50 100
0 1 2 3 4 5 6
−120:120
his. (−120:120)
−100 0 50 100
0.0 1.0 2.0 3.0
−120:120
his. (−120:120)
−100 0 50 100
0 2 4 6 8 12
−120:120
his. (−120:120)
−100 0 50 100
0 1 2 3 4 5
−120:120
his. (−120:120)
Fig. 1. Nine ins ances om p oblem class Π1. A i icial p oblem ins ances a e based
on a ha monic ime se ies model. The ec o w= (−0.1,0.01,0.001,10.0,10.0)0was
used o scaling he pa ame e s in (2). The ini ial ES popula ion is gene a ed in he
in e al [100; 120].
Beyond Pa icula P oblem Ins ances 7
whe e a ,b and s a e gi en by
a =α(Y /s −p) + (1 −α)(a −1+b −1)
b =β(a −a −1) + (1 −β)b −1
s =γ(Y /a ) + (1 −γ)s −p
The op imal alues o α,βand γa e de e mined by minimizing he squa ed
one-s ep p edic ion e o . New p oblem ins ances can be gene a ed as ollows.
The pa ame e s α,β, and γa e es ima ed om o iginal ime-se ies da a Y .
To gene a e new p oblem ins ances, hese pa ame e s can be sligh ly modi ied.
Based on hese modi ied alues, he model is e- i ed. Finally, we can ex ac
he new ime se ies. He e, we plo he o iginal da a, he Hol -Win e s p edic ions
and he modi ied ime se ies.
> gene a eHW <- unc ion(a,b,c){
+ ## Es ima ion
+ m <- Hol Win e s(Ai Passenge s, seasonal = "mul ")
+ ## Ex ac ion
+ alpha0<-m$alpha
+ be a0<-m$be a
+ gamma0<-m$gamma
+ ## Modi ica ion
+ alpha1 <- alpha0*a
+ be a1 <- be a0*b
+ gamma1 <- gamma0*c
+ ## Re-es ima ion
+ m1 <- Hol Win e s(Ai Passenge s, alpha=alpha1
+ , be a = be a1, gamma = gamma1)
+ ## Ins ance gene a ion
+ plo (Ai Passenge s)
+ lines( i ed(m)[,1], col = 1, l y=2, lw=2)
+ lines( i ed(m1)[,1], col = 1, l y = 3, lw =2)
+ }
> gene a eHW(a=.05,b=.025,c=.5)
One ypical esul om his ins ance gene a ion is shown in Fig. 2.
To illus a e he wide applicabili y o his app oach, we will lis u he eal-
wo k p oblem domains, which a e subjec o ou cu en esea ch.
Sma Me e ing. The de elopmen o accu a e o ecas ing me hods o elec i-
cal ene gy consump ion p o iles is an impo an ask. Accu a e consump-
ion p o ile o ecas ing enables in elligen con ol o enewable ene gy sou ce
in as uc u e, such as s o age powe plan s, and he e o e con ibu es o
a smalle ca bon oo p in . Accu a e consump ion p o ile o ecas ing also
enables ene gy consume s o accu a ely assess he e u n on in es men o
measu es o inc ease ene gy e iciency. We conside ime se ies collec ed om
a manu ac u ing p ocess. Each ime se ies con ains qua e -hou ly samples
8 T.Ba z-Beiels ein
Time
Ai Passenge s
1950 1952 1954 1956 1958 1960
100 200 300 400 500 600
Fig. 2. Hol -Win e s p oblem ins ance gene a o . The solid line ep esen s he eal
da a, he do ed line p edic ions om he Hol -Win e s model and he ine do ed line
modi ied p edic ions, espec i ely.
o he ene gy consump ion o a bake y. A de ailed da a desc ip ion can be
ound in [2].
Wa e Indus y. Cana y is a so wa e de eloped by he Uni ed S a es En i-
onmen al P o ec ion Agency (US EPA) and Sandia Na ional Labo a o ies.
I s pu pose is o de ec e en s in he con ex o wa e con amina ion. An
e en is in his con ex de ined as a ce ain ime pe iod whe e a con ami-
nan de e io a es he wa e quali y signi ican ly. Dis inguishing e en s om
(i) backg ound changes, (ii) main enance and modi ica ion due o ope a ion,
and (iii) ou lie s is an essen ial ask, which was implemen ed in he Ca-
na y so wa e. The e o e, de ia ions a e compa ed o egula pa e ns and
sho e m changes. The co esponding da a con ains mul i- a ia e ime-
se ies da a. I is a selec ion o a la ge da ase shipped wi h he open sou ce
E en De ec ion So wa e CANARY de eloped by US EPA and Sandia Na-
ional Labo a o ies [16].
Finance. The da a a e eal-wo ld da a om in aday o eign exchange (FX)
ading. The FX ma ke is a inancial ma ke o ading cu encies o enable
in e na ional ade and in es men . I is he la ges and mos liquid inancial
ma ke in he wo ld. Cu encies can be aded ia a wide a ie y o di e en
inancial ins umen s, anging om simple spo ades o e o highly complex
de i a i es. We a e using h ee o eign exchange (cu ency a e) ime se ies
collec ed om Bloombe g. Each ime se ies con ains hou ly samples o he
change in cu ency exchange a e [11].
Now ha we ha e demons a ed he applicabili y o ou app oach o a well
known ime se ies and lis ed ime se ies, which a e subjec o ou cu en e-
sea ch, we will in oduce he op imiza ion algo i hm.
Beyond Pa icula P oblem Ins ances 9
3 Algo i hm Fea u es
3.1 Fac o s and Le els
E olu iona y algo i hms (EA) belong o he la ge class o bio-inspi ed sea ch
heu is ics. They combine speci ic componen s, which may be quali a i e, like he
ecombina ion ope a o o quan i a i e, like he popula ion size. Ou in e es
is in unde s anding he con ibu ion o hese componen s. In s a is ical e ms,
hese componen s a e called ac o s. The in e es is in he e ec s o he speci ic
le els chosen o hese ac o s. Hence, we say ha he le els and consequen ly he
ac o s a e ixed. Al hough mode n sea ch echniques like sequen ial pa ame e
op imiza ion o Pa e o gene ic p og amming allow mul i-objec i e pe o mance
measu es (solu ion quali y e sus a iabili y o desc ip ion leng h), we es ic
ou sel es o analyze he e ec o hese ac o s on a uni a ia e measu e o pe -
o mance. We will use he quali y o he solu ions e u ned by he algo i hm a
e mina ion as he pe o mance measu e.
3.2 Example: E olu ion S a egy
E olu ion s a egies (ES) a e p ominen ep esen a i es o e olu iona y algo-
i hms, which includes gene ic algo i hms and gene ic p og amming as well [15].
E olu ion s a egies a e applied o ha d eal- alued op imiza ion p oblems. Mu-
a ion is pe o med by adding a no mally dis ibu ed andom alue o each
ec o componen . The s anda d de ia ion o hese andom alues is modi ied
by sel -adap a ion. E olu ion s a egies can use a popula ion o se e al solu ions.
Each solu ion is conside ed as as indi idual and consis s o objec and s a egy
a iables. Objec a iables ep esen he posi ion in he sea ch space, whe eas
s a egy a iables s o e he s ep sizes, i.e., he s anda d de ia ions o he mu a-
ion. We a e analyzing he ES basic a ian , which has been p oposed in [8]. I is
unde s ood as popula ion based s ochas ic di ec sea ch algo i hm—no exclud-
ing popula ion sizes o one as e.g. ea u ed in simple e olu ion s a egies— ha
in some sense mimics he na u al e olu ion.
Besides ini ializa ion and e mina ion as necessa y cons i uen s o e e y al-
go i hm, ES consis o h ee impo an ac o s: A numbe o sea ch ope a o s,
an imposed con ol low (Figu e 3), and a ep esen a ion ha maps adequa e
a iables o implemen able solu ion candida es.
Al hough di e en ES may pu di e en emphasis on he sea ch ope a o s
mu a ion and ecombina ion, hei gene al e ec s a e no in ques ion. Mu a ion
means neighbo hood based mo emen in sea ch space ha includes he explo-
a ion o he "ou e space" cu en ly no co e ed by a popula ion, whe eas e-
combina ion ea anges exis ing in o ma ion and so ocuses on he "inne space".
Selec ion is mean o in oduce a bias owa ds be e i ness alues; GAs do so
by egula ing he c osso e ia ma ing selec ion, ESs u ilize he en i onmen al
selec ion.
A conc e e ES may con ain speci ic mu a ion, ecombina ion, o selec ion
ope a o s, o call hem only wi h a ce ain p obabili y, bu he con ol low is
16 T.Ba z-Beiels ein
We will demons a e, how hese es ima o s can be calcula ed in R. Fi s , he
ANOVA model is build. Then, we ex ac he mean squa ed alues, i.e., MSA
( ea men ) and MSE (e o ). The es ima o s o he a iance componen s can
be calcula ed as ollows. F om (10) we ob ain an es ima o o he i s a iance
componen ˆσ2as he mean squa ed e o and om (11), we ob ain he second
componen ˆσ2
τ. The model a iance can be de e mined as a .A + a .B. Finally,
he mean µ om (8) can ex ac ed.
> samp.ao <- ao (yLog ~ Seed, da a=samp.d )
> (M1 <- ano a(samp.ao ))
Analysis o Va iance Table
Response: yLog
D Sum Sq Mean Sq F alue P (>F)
Seed 8 48.832 6.1040 1.0707 0.4048
Residuals 36 205.230 5.7008
> (MSA <- M1[1,3])
[1] 6.10401
> (MSE <- M1[2,3])
[1] 5.700838
> <-leng h(unique(samp.d $algSeed))
> q <- nle els(samp.d $ Seed)
> ( a .A <- (MSA - MSE)/( ))
[1] 0.0806345
> ( a .E <- MSE)
[1] 5.700838
> a .A + a .E
[1] 5.781472
> coe (samp.ao )[1]
(In e cep )
-1.136131
The p alue in he ANOVA able is calcula ed as
> 1-p (MSA/MSE,q-1,q*( -1))
[1] 0.4047883

Beyond Pa icula P oblem Ins ances 17
The MSA alue will be s o ed o he calcula ion o con idence in e als.
> MSA.ano a <- MSA
In some cases, he s anda d ANOVA, which was used in ou example, p o-
duces a nega i e es ima e o a a iance componen . This can be seen in (11): I
MSe >MS ea , nega i e alues occu . By de ini ion, a iance componen s a e
posi i e. Me hods, which always yield posi i e a iance componen s ha e been
de eloped. He e, we will use es ic ed maximum likelihood es ima o s (REML).
The ANOVA me hod o a iance componen es ima ion, which is a me hod o
momen s p ocedu e, and REML es ima ion may lead o di e en esul s.
Res ic ed maximum likelihood. Based on he same da a, we i he andom-
e ec s model (8) using he unc ion lme () om he Rpackage lme4 [7]:
> lib a y(lme4)
> samp.lme <- lme (yLog~ 1 +(1| Seed),da a=samp.d )
> p in (samp.lme , digi s = 4, co = FALSE)
Linea mixed model i by REML
Fo mula: yLog ~ 1 + (1 | Seed)
Da a: samp.d
AIC BIC logLik de iance REMLde
211.8 217.2 -102.9 205.6 205.8
Random e ec s:
G oups Name Va iance S d.De .
Seed (In e cep ) 2.6196e-11 5.1182e-06
Residual 5.7741e+00 2.4029e+00
Numbe o obs: 45, g oups: Seed, 9
Fixed e ec s:
Es ima e S d. E o alue
(In e cep ) -1.3528 0.3582 -3.776
Fi s , he model o mula ( yLog ∼1 + (1| Seed) ) is shown. The da a is
g ouped by Seed, because p oblem ins ances πia e gene a ed using (2) wi h
nine di e en seeds. The ixed e ec is he in e cep , which is ep esen ed by
he symbol 1in he o mula. The e m (1| Seed) indica es ha he da a
is g ouped by Seed. The 1is indica ing ha he andom e ec is cons an
wi hin each g oup. In o ma ion abou measu es o he i ing (AIC, BIC, e c.)
a e displayed nex . Ou mains in e es lies on he nex lines o he ou pu , which
a e labeled Random e ec s. He e we ind he es ima es o pa ame e s ela ed o
he andom e ec s and he e o dis ibu ions, i.e., he a iances o he p oblem
ins ances, i.e., τo Seed and he algo i hm, i.e., o Residual. This shows ha
he a iabili y in he esponse obse a ions can be a ibu ed o he a iabili y
o he algo i hm.
18 T.Ba z-Beiels ein
SAMP-4 Hypo hesis Tes ing Tes ing hypo heses abou indi idual ea men s
(ins ances) is useless, because he p oblem ins ances πia e he e conside ed as
samples om some la ge popula ion o ins ances Π. We es hypo heses abou
he a iance componen σ2
τ, i.e., he null hypo hesis
H0:σ2
τ= 0 is es ed e sus he al e na i e H1:σ2
τ>0.(12)
Unde H0, all ea men s a e iden ical, i.e., σ2
τis e y small. Based on (9), we
conclude ha E(MS ea ) = σ2+ σ2
τand E(MSe ) = σ2a e simila . Unde he
al e na i e, a iabili y exis s be ween ea men s. S anda d analysis shows ha
SSe /σ2is dis ibu ed as chi-squa e wi h q( −1) deg ees o eedom. Unde H0,
he a io
F0=
SS ea
q−1
SSe
q( −1)
=MS ea
MSe
is dis ibu ed as Fq−1,q( −1). To es hypo heses in (8), we equi e ha τ1, . . . , τq
a e i.i.d. N(0, σ2
τ),εij,i= 1, . . . , q,j= 1, . . . , , a e i.i.d. N(0, σ2), and all τi
and εij a e independen o each o he .
These conside a ions lead o he decision ule o ejec H0a he signi icance
le el αi
0> F(1 −α;q−1, q( −1)),(13)
whe e 0is he ealiza ion o F0 om he obse ed da a. An in ui i e mo i a ion
o he o m o s a is ic F0can be ob ained om he expec ed mean squa es.
Unde H0bo h MS ea and MSe es ima e σ2in an unbiased way, and F0can be
expec ed o be close o one. On he o he hand, la ge alues o F0gi e e idence
agains H0.
Based on (9), we can de e mine he Fs a is ic and he p alues:
> VC <- Va Co (samp.lme )
> (sigma. au <- as.nume ic(a (VC$ Seed,"s dde ")))
[1] 5.118205e-06
> (sigma <- as.nume ic(a (VC,"sc")))
[1] 2.402944
> q <- nle els(samp.d $ Seed)
> <- leng h(unique(samp.d $algSeed))
> (MSA <- sigma^2+ *sigma. au^2)
[1] 5.774142
> (MSE <- sigma^2)
[1] 5.774142
Now we can de e mine he p alue based on (13):
Beyond Pa icula P oblem Ins ances 19
> 1-p (MSA/MSE,q-1,q*( -1))
[1] 0.4529257
Since he p alue is la ge, he null hypo hesis H0:σ2
τ= 0 om (12) can no be
ejec ed, i.e., we conclude ha he e is no ins ance e ec . A simila conclusion
was ob ained om he ANOVA me hod o a iance componen es ima ion.
SAMP-5 Con idence In e als and P edic ion An unbiased es ima o o he o e -
all mean µis Pq
i=1 P
j=1 yij/(q ). I can be shown ha i s es ima ed s anda d
e o is gi en by se(ˆµ) = pMS ea /q and ha
¯
Y·· −µ
pMS ea /q ∼ (q−1).
Hence, [10, p. 232] show ha con idence limi s o µcan be de i ed as
¯y·· ± (1 −α/2; q−1)pMS ea /q . (14)
We conclude his case s udy wi h p edic ion o he algo i hm’s pe o mance
on a new ins ance. Based on (14), he 95% con idence in e al can be calcula ed
as ollows.
> s <- sq (MSA/(q* ))
> Y.. <- mean(samp.d $yLog)
> qs <- q (1-0.025, )
> c( exp(Y.. - qs * s), exp(Y.. + qs * s))
[1] 0.1029441 0.6492394
Since we pe o med he analysis on log da a, he exp() unc ion was applied o
he inal esul . Hence, 95% con idence in e al o µis [0.10; 0.65].
Using he ANOVA esul s om abo e, we ob ain he ollowing con idence
in e al o he pe o mance o he ES:
> s <- sq (MSA.ano a/(q* ))
> Y.. <- mean(samp.d $yLog)
> qs <- q (1-0.025,5)
> c( exp(Y.. - qs * s), exp(Y.. + qs * s))
[1] 0.1003084 0.6662989
Second SAMP Example The ES pa ame iza ion emains unchanged, bu
he pa ame iza ion o he p oblem ins ances was modi ied. Nine p oblems in-
s ances πi(i= 1,2,...,9) we e gene a ed, using he p oblem pa ame e ec o
(−0.1,−0.1,−0.001, .10,2)×i2. The esul ing ealiza ions a e illus a ed in Fig. 5.
20 T.Ba z-Beiels ein
−100 0 50 100
02468
−120:120
his. (−120:120)
−100 0 50 100
0 20 40 60
−120:120
his. (−120:120)
−100 0 50 100
0 40 80 120
−120:120
his. (−120:120)
−100 0 50 100
0 20 40 60
−120:120
his. (−120:120)
−100 0 50 100
0 200 400
−120:120
his. (−120:120)
−100 0 50 100
0 200 400
−120:120
his. (−120:120)
−100 0 50 100
0 100 200 300
−120:120
his. (−120:120)
−100 0 50 100
0 200 600
−120:120
his. (−120:120)
−100 0 50 100
0 50 150 250
−120:120
his. (−120:120)
Fig. 5. Second se o p oblem ins ances Π2. The ES shows di e en pe o mances on
his se o p oblem ins ances.
> s (samp2.d )
'da a. ame': 45 obs. o 4 a iables:
$ y : num 0.0315 0.1171 0.0136 1.8438 0.5961 ...
$ Seed : Fac o w/ 9 le els "1","2","3","4",..: 1 1 1 1 1 2 2 2 2 2 ...
$ algSeed: Fac o w/ 5 le els "1","2","3","4",..: 1 2 3 4 5 1 2 3 4 5 ...
$ yLog : num -3.456 -2.145 -4.299 0.612 -0.517 ...
Again, we es he alidi y o he model assump ions by gene a ing no mal
quan ile plo s (QQ plo s) as shown in Fig. 6.
We conside he classical ANOVA i s .
> samp2.ao <- ao (yLog ~ Seed, da a=samp2.d )
> (M2 <- ano a(samp2.ao ))
Analysis o Va iance Table
Response: yLog
D Sum Sq Mean Sq F alue P (>F)
Seed 8 82.830 10.3538 5.9856 6.805e-05 ***
Residuals 36 62.272 1.7298
---
Signi . codes: 0 '***'0.001 '**'0.01 '*'0.05 '.'0.1 ' ' 1
Beyond Pa icula P oblem Ins ances 21
●●
●
●
●
●
●
●●
●●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
−2 −1 0 1 2
0 5 10 15 20
(a)
Theo e ical Quan iles
Sample Quan iles
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●●
−2 −1 0 1 2
−4 −2 0 2
(b)
Theo e ical Quan iles
Sample Quan iles
Fig. 6. Quan ile-Quan ile (Q-Q) plo s o he second SAMP example: (a) be o e he
log ans o ma ion, (b) a e he log ans o ma ion is applied o he da a.
> (MSA <- M2[1,3])
[1] 10.35378
> (MSE <- M2[2,3])
[1] 1.729791
> <-leng h(unique(samp2.d $algSeed))
> q <- nle els(samp2.d $ Seed)
Following (11), he a iance componen s ˆ
σ2
τ( a .A) and ˆσ2( a .E) can be
de e mined as ollows.
> ( a .A <- (MSA - MSE)/( ))
[1] 1.724798
> ( a .E <- MSE)
[1] 1.729791
Tha is, we ha e ˆσ2
τ= 0.08 and σ2= 5.7. The p alue is

22 T.Ba z-Beiels ein
> 1-p (MSA/MSE,q-1,q*( -1))
[1] 6.805386e-05
We ob ain he ollowing con idence in e al.
> s <- sq (MSA/(q* ))
> Y.. <- mean(samp2.d $yLog)
> qs <- q (1-0.025,5)
> c( exp(Y.. - qs * s), exp(Y.. + qs * s))
[1] 0.4260439 5.0171031
REML Nex , we conside he es ic ed maximum likelihood app oach.
Linea mixed model i by REML
Fo mula: yLog ~ 1 + (1 | Seed)
Da a: samp2.d
AIC BIC logLik de iance REMLde
173.1 178.5 -83.55 167.5 167.1
Random e ec s:
G oups Name Va iance S d.De .
Seed (In e cep ) 1.7248 1.3133
Residual 1.7298 1.3152
Numbe o obs: 45, g oups: Seed, 9
Fixed e ec s:
Es ima e S d. E o alue
(In e cep ) 0.3798 0.4797 0.792
The s a is ical analysis e eals ha he a iabili y in he esponse obse a ions
can be a ibu ed o he a iabili y in he p oblem ins ances. We con inue by
compu ing he Fs a is ic and he p alue.
> VC <- Va Co (samp2.lme )
> ( a .A <- (as.nume ic(a (VC$ Seed,"s dde ")))^2)
[1] 1.724797
> ( a .E <- (as.nume ic(a (VC,"sc")))^2)
[1] 1.729791
> q <- nle els(samp2.d $ Seed)
> <- leng h(unique(samp2.d $algSeed))
> (MSA <- a .E+ * a .A)
[1] 10.35378
Beyond Pa icula P oblem Ins ances 23
> (MSE <- a .E)
[1] 1.729791
> 1-p (MSA/MSE,q-1,q*( -1))
[1] 6.805392e-05
The esul ing p alue gi es eason o ejec ing he null hypo heses H0:σ2
τ= 0
as shown in (12), i.e., we conclude ha he e migh be ins ance e ec s. The
co esponding 95% con idence in e al o new p oblem ins ances is la ge , which
also indica es ha he e a e pe o mance di e ences. Based on (14), we ob ain
he ollowing con idence in e al o he pe o mance o he ES:
[1] 0.4260439 5.0171029
Con idence in e als om he REML and ANOVA me hods a e e y simila .
5.3 MAMP: Mul iple Algo i hms, Mul iple P oblems:
In his case s udy, we demons a e how he ma ginal model (7) can be ex ended
o he case whe e se e al algo i hms a e applied o he same ins ance. We add
ixed e ec s in he condi ional s uc u e o (6). Nex , we illus a e how his leads
na u ally o a mixed model.
Ins ead o one ixed algo i hm, we conside se e al algo i hms o algo i hms
wi h se e al pa ame e s. Bo h si ua ions can be ea ed while conside ing algo-
i hms as le els o a ixed ac o , whe eas p oblem ins ances a e d awn andomly
om some popula ion o ins ances Π.
MAMP-1 Algo i hm and P oblem Ins ances
MAMP-2 Valida ion o he Model Assump ions
MAMP-3 Building he Model and ANOVA
MAMP-4 Hypo hesis Tes ing
a) Random e ec s
b) Fixed e ec s
c) Back- i ing ( o mul iple ixed ac o s)
MAMP-5 Con idence In e als and P edic ion
MAMP-1 Algo i hm and P oblem Ins ances In he i s design we aim a com-
pa ing he pe o mance o he ES wi h di e en ecombina ion ope a o s o e
an ins ance class. Mo e p ecisely, we ha e he ollowing ac o s:
–algo i hm: ou ES ins ances using ecombina ion ope a o s {1,2,3,4}
–ins ances: nine ins ances andomly sampled om he class Π1as illus a ed
in Fig. 1 wi h p oblem pa ame e s (-0.1, 0.01, 0.001, 10.0, 10.0)
– eplica es: i e
> s (mamp.d )
24 T.Ba z-Beiels ein
'da a. ame': 180 obs. o 5 a iables:
$ y : num 0.001725 0.008679 0.001094 0.010323 0.000853 ...
$ s eco : Fac o w/ 4 le els "1","2","3","4": 1 1 1 1 1 2 2 2 2 2 ...
$ Seed : Fac o w/ 9 le els "1","2","3","4",..: 1 1 1 1 1 1 1 1 1 1 ...
$ algSeed: Fac o w/ 5 le els "1","2","3","4",..: 1 2 3 4 5 1 2 3 4 5 ...
$ yLog : num -6.36 -4.75 -6.82 -4.57 -7.07 ...
As can be seen om he s ou pu , 4×9×5 = 180 da a we e used in his
s udy.
MAMP-2 Valida ion o he Model Assump ions Again, we es he alidi y o he
model assump ions by gene a ing no mal quan ile plo s (QQ plo s) as shown in
Fig. 6.
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●
●
●
●●
−2 −1 0 1 2
0.00 0.02 0.04 0.06 0.08
(a)
Theo e ical Quan iles
Sample Quan iles
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
−2 −1 0 1 2
−10 −8 −6 −4
(b)
Theo e ical Quan iles
Sample Quan iles
Fig. 7. Quan ile-Quan ile (Q-Q) plo s o he MAMP example: (a) be o e he log ans-
o ma ion, (b) a e he log ans o ma ion is applied o he da a. Al hough he e is
s ill an ou lie in he log ans o med da a, we will use he ans o med da a.
Nex , we plo he esul s o each g oup. A i s isual inspec ion, which
plo s he pe o mance o he algo i hm wi hin each p oblem ins ance, is shown
in Fig. 8.
> lib a y(la ice)
> p in (xyplo (yLog ~ s eco | Seed, da a=mamp.d ,
Beyond Pa icula P oblem Ins ances 25
s eco
y
−10
−8
−6
−4
1 2 3 4
●
●
●
●
●●
●
●
●
●●
●
●
●
●●
●
●
●
●
1
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
2
1234
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
3
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
4
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
5
−10
−8
−6
−4
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
6
−10
−8
−6
−4
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
7
1234
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
8
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
9
Fig. 8. Fou algo i hms (ES wi h modi ied ecombina ion ope a o s) on nine es p ob-
lem ins ances. Each panel ep esen s one p oblem ins ance. Pe o mance is plo ed
agains he le el o he ecombina ion ope a o .
32 T.Ba z-Beiels ein
MAMP-4b) Hypo hesis Tes ing: Fixed Fac o E ec s Rega ding ixed ac o s, we
a e in e es ed in es ing o di e ences in he ac o le el means µ+αi. These
es s can be o mula ed in he hypo hesis es ing amewo k as:
H0:αi= 0 ∀iagains H1:∃αj6= 0 (18)
He e, we a e using he es s a is ic om [14, p. 523] o es ing ha he means
o he ixed ac o e ec s a e equal:
> ano a(mamp.lme )
Analysis o Va iance Table
D Sum Sq Mean Sq F alue
s eco 3 13.5 4.51 2.35
Based on he F0 alue, we calcula e he p alue o he es on he ixed-e ec
e m.
> h <- nle els(mamp.d $s eco)
> q <- nle els(mamp.d $ Seed)
> ano a(mamp.lme )$"F alue"
[1] 2.35
> 1 - p (ano a(mamp.lme )$"F alue", h-1, (h-1)*(q-1))
[1] 0.0981
The ob ained p alue 0.1is only o mino signi icance. I does no gi e clea
e idence ha s eco should be included in he model. Howe e , he impac o
he p oblem ins ances is negligible, because he co esponding p alues a e sig-
ni ican ly la ge han ze o.
We can es ima e he ixed ac o e ec s ˆαjin he mixed model as
ˆαj=¯
Y·j·−¯
Y···
Using sum o con as s implies ha Pαj= 0. The poin es ima es o he mean
algo i hm pe o mance wi h he j h ixed ac o se ing can be ob ained by µ·j=
µ+αj. The co esponding ixed e ec s a e shown in he Fixed e ec s sec ion o
he ou pu om m2a <- lme (yLog ∼s eco + (1| Seed) + (1| Seed:s eco),
da a=d ) on page 30. Fo example, we ob ain he ollowing alue: s eco1 = -
0.35. Usually, we a e in e es ed in he ma ginal mean µ·j=µ+αj, whose bes
es ima o is
ˆµ·j=Y·j·.
> (Y.j. <- wi h(mamp.d ,agg ega e(yLog,lis (s eco=s eco),mean)))
s eco x
1 1 -5.82
2 2 -5.65
3 3 -5.18
4 4 -5.23

Beyond Pa icula P oblem Ins ances 33
MAMP-5 Con idence In e als and P edic ion Finally, we gene a e pai ed com-
pa isons plo s, which a e based on con idence in e als. The con idence in e al
a e de e mined wi h he Va Co () unc ion, which ex ac s es ima ed a iances,
s anda d de ia ions, and co ela ions o he andom-e ec s e ms.
> VC<-Va Co (mamp.lme )
> sigma.gamma<-as.nume ic(a (VC$" Seed:s eco","s dde "))
> sigma<-as.nume ic(a (VC,"sc"))
> MSAB <- sigma^2 + * sigma.gamma^2
> Y.j. <- wi h(mamp.d ,agg ega e(yLog,lis (alg=s eco),mean))
> s <- sq (2)*sq (MSAB/(q* ))
> T <- q ukey(1-0.05,h,(h-1)*(q-1))/sq (2)
> Y.j.$lowe <- Y.j.$x - 0.5 * T * s
> Y.j.$uppe <- Y.j.$x + 0.5 * T * s
> Y.j.
alg x lowe uppe
1 1 -5.82 -6.22 -5.42
2 2 -5.65 -6.06 -5.25
3 3 -5.18 -5.58 -4.77
4 4 -5.23 -5.63 -4.83
No e, ha he in e cep e m ˆµ=−5.4694 can be added o he es ima ed
ixed e ec s o ob ain he Y· alues, e.g., −5.82 = −5.4694 −0.35 o −5.65 =
−5.4694 −0.1841.
The w appe unc ion in e als() om Chia andini and Goegebeu [10]
was used o isualizing hese con idence in e als as shown in Fig. 10. Again,
x
1
2
3
4
−6.0 −5.5 −5.0
●
●
●
●
Fig. 10. Pai ed compa ison plo s. Resul s om ou ES ins ances wi h di e en ecom-
bina ion ope a o s a e shown in his plo .
34 T.Ba z-Beiels ein
he la ges di e ence occu s be ween no (1) and in e media e (3) ecombina ion
o he s a egy a iables.
Second Example MAMP: ES on Simple Tes Da a Se In he p e ious
case s udy, one ixed ac o was used. We now discuss he case MAMP wi h h ee
ixed ac o s.
MAMP-1 Algo i hm and P oblem Ins ances
–algo i hm: wo ES mu a ion ope a o s {1,2}
–algo i hm: ou ES ecombina ion ope a o s o s a egy a iables {1,2,3,4}
–algo i hm: ou ES ecombina ion ope a o s o objec a iables {1,2,3,4}
–ins ance: nine ins ances andomly sampled om he class (-0.1, 0.01,
0.001, 10.0, 10.0)
– eplica es: i e
The 32 possible combina ions gi e ise o 32 algo i hms o es .
> s (mamp2.d )
'da a. ame': 1440 obs. o 6 a iables:
$ y : num 0.1218 0.0123 0.4072 0.2941 1.2331 ...
$ mu : Fac o w/ 2 le els "1","2": 1 1 1 1 1 1 1 1 1 1 ...
$ s eco : Fac o w/ 4 le els "1","2","3","4": 1 1 1 1 1 1 1 1 1 1 ...
$ o eco : Fac o w/ 4 le els "1","2","3","4": 1 1 1 1 1 2 2 2 2 2 ...
$ Seed : Fac o w/ 9 le els "1","2","3","4",..: 1 1 1 1 1 1 1 1 1 1 ...
$ algSeed: Fac o w/ 5 le els "1","2","3","4",..: 1 2 3 4 5 1 2 3 4 5 ...
He e, 2×4×4×9×5 = 1440 algo i hm uns we e pe o med.
MAMP-2 Valida ion o he Model Assump ions The Q-Q plo e eals he non-
no mali y o he o iginal da a. As in he p e ious case s udies, a loga i hmic
ans o ma ion imp o es he no mali y. Howe e , e en he log ans o med da a
show de ia ions om no mali y, especially in he ails o he dis ibu ion.
MAMP-3 Building he Model and ANOVA The a iance decomposi ion, which
was in oduced in he p e ious case s udy, was used. The a iabili y in he
pe o mance measu e is decomposed acco ding o he mixed-e ec s ANOVA
model and he model equa ion (15) is used. We will use likelihood- a io es s o
de e mine signi ican ac o and in e ac ion e ec s.
MAMP-4a) Hypo hesis Tes ing: Random E ec s We include all second o de
in e ac ions in ou models.
> mamp2.lm <- lm(yLog ~ (mu + s eco + o eco)^2, da a = mamp2.d )
> mamp2.lme 1 <- lme (yLog ~ (mu + s eco + o eco)^2 + (1| Seed),
da a = mamp2.d , REML = FALSE)
Beyond Pa icula P oblem Ins ances 35
> mamp2.lme 2 <- lme (yLog ~ (mu + s eco + o eco)^2 + (1| Seed) +
(1| Seed:mu ) +(1| Seed:s eco) + (1| Seed:o eco),
da a = mamp2.d , REML = FALSE)
> LRT <- as.nume ic(2 * (logLik(mamp2.lme 2) - logLik(mamp2.lm)))
> 1-pchisq(LRT,1)
[1] 8.5e-12
The likelihood a io es e eals ha he andom ac o p oblem ins ance is
signi ican and ha he e is a leas one signi ican in e ac ion be ween ixed
algo i hm ac o s and andom p oblem ins ance ac o s. The analysis based on
ano a() gi es a simila esul .
> ano a(mamp2.lme 2, mamp2.lme 1)
Da a: mamp2.d
Models:
mamp2.lme 1: yLog ~ (mu + s eco + o eco)^2 + (1 | Seed)
mamp2.lme 2: yLog ~ (mu + s eco + o eco)^2 + (1 | Seed) + (1 | Seed:mu ) +
mamp2.lme 2: (1 | Seed:s eco) + (1 | Seed:o eco)
D AIC BIC logLik Chisq Chi D P (>Chisq)
mamp2.lme 1 25 5958 6090 -2954
mamp2.lme 2 28 5938 6086 -2941 26.1 3 9.1e-06
The e o e, we conclude ha he andom ac o ins ance is signi ican .
MAMP-4b) Hypo hesis Tes ing: Fixed E ec s We conside he ixed e ec s nex .
The LMERCon enienceFunc ions p o ides many ools o he analysis o mixed
models. He e, we will use he pame . nc() o compu ing uppe - and lowe -
bound p alues o he ANOVA and he amoun o de iance explained (%) o
each ixed-e ec o an lme model.
> mamp2. ixed <- lme (yLog ~ (mu + s eco + o eco)^2 + (1| Seed) +
(1| Seed:mu ) +(1| Seed:s eco) + (1| Seed:o eco)
, da a = mamp2.d )
> lib a y(LMERCon enienceFunc ions)
> pame . nc(mamp2. ixed)
D Sum Sq Mean Sq F alue uppe .den.d uppe .p. al
mu 1 1046.1 1046.12 307.626 1417 0.0000
s eco 3 29.4 9.82 2.886 1417 0.0345
o eco 3 91.0 30.34 8.922 1417 0.0000
mu :s eco 3 11.6 3.85 1.134 1417 0.3343
mu :o eco 3 943.9 314.63 92.519 1417 0.0000
s eco:o eco 9 19.1 2.12 0.624 1417 0.7773
lowe .den.d lowe .p. al expl.de .(%)
mu 1318 0.0000 10.889
36 T.Ba z-Beiels ein
s eco 1318 0.0346 0.306
o eco 1318 0.0000 0.948
mu :s eco 1318 0.3343 0.120
mu :o eco 1318 0.0000 9.825
s eco:o eco 1318 0.7773 0.199
The analysis yields ha mu ,o eco, and hei in e ac ion migh be signi ican .
We use in e ac ion plo s (Fig. 11) o illus a e his beha io .
−6
−5
−4
−3
−2
o eco
mean o yLog
1 2 3 4
mu
1
2
Fig. 11. In e ac ion plo s. The solid line ep esen s esul s wi h mu a ion, whe eas he
do ed line illus a es esul s ob ained wi hou mu a ion. Since we a e conside ing a
minimiza ion p oblem, esul s wi h mu a ion a e be e han wi hou mu a ion. Re-
combina ion shows possible in e ac ions, e.g., modi ying he ecombina ion ope a o
om dominan (2) o in e media e (3) imp o es he ES pe o mance, i no mu a ion
is used. I wo sens he pe o mance, i mu a ion is used.
The analysis clea ly demons a es ha mu a ion should be used, whe eas
ecombina ion wo sens algo i hm’s pe o mance. Howe e , his esul canno be
gene alized, because we we conside ing a one-dimensional es unc ion only. I
no mu a ion is used, in e media e ecombina ion o he objec a iables imp o es
algo i hm’s pe o mance.
MAMP-4c) Back- i ing The unc ion b Fixe LMER_F. nc back- i s an ini ial
lme model on uppe - o lowe -bound p alues.
> mamp2.lme 3 <- lme (yLog ~ (mu + s eco + o eco)^2 + (1| Seed) +
(1| Seed:mu ) +(1| Seed:s eco) + (1| Seed:o eco) , da a = mamp2.d )
Beyond Pa icula P oblem Ins ances 37
Fi s , we upda e ini ial model on immed da a.
> d . immed = om . nc(mamp2.lme 3, mamp2.d , im = 2.5)
n. emo ed = 50
pe cen . emo ed = 3.47
> mamp2.d = d . immed$da a
> mamp2.lme 4 = upda e(mamp2.lme 3)
Nex , we back i ixed e ec s.
> mamp2.lme 5 = b Fixe LMER_F. nc(mamp2.lme 4, log. ile = FALSE
, ll = FALSE, alpha=0.005)
p ocessing model e ms o in e ac ion le el 2
i e a ion 1
p- alue o e m "s eco:o eco" = 0.5 > 0.005
no pa o highe -o de in e ac ion
emo ing e m
i e a ion 2
p- alue o e m "mu :s eco" = 0.0182 > 0.005
no pa o highe -o de in e ac ion
emo ing e m
p ocessing model e ms o in e ac ion le el 1
i e a ion 3
p- alue o e m "s eco" = 0.0057 > 0.005
no pa o highe -o de in e ac ion
emo ing e m
p uning andom e ec s s uc u e ...
no hing o p une
> pame . nc(mamp2.lme 5)
D Sum Sq Mean Sq F alue uppe .den.d uppe .p. al
mu 1 1701.0 1701.0 757.59 1382 0e+00
o eco 3 45.2 15.1 6.71 1382 2e-04
mu :o eco 3 916.5 305.5 136.07 1382 0e+00
lowe .den.d lowe .p. al expl.de .(%)
mu 1283 0e+00 20.363
o eco 1283 2e-04 0.541
mu :o eco 1283 0e+00 10.972
As in he ull model (mamp2. ixed), mos o he a iance is explained by
mu a ion and he in e ac ion be ween mu a ion and ecombina ion o he objec
a iables. This si ua ion was also illus a ed in Fig. 11.

38 T.Ba z-Beiels ein
MAMP-5 Con idence In e als and P edic ion We will conside he a e age al-
go i hm pe o mance on he nine p oblem ins ances in Fig. 12. These da a a e
agg ega ed o de e mine con idence in e als, which a e plo ed in Fig. 13. Bo h
igu es suppo he assump ion ha mu a ion imp o es he algo i hm’s pe o -
mance. An e olu ion s a egy wi h mu a ion, no ecombina ion o s a egy a i-
ables, and disc e e ecombina ion o he objec a iables pe o ms easonably
well. Again, he Rcode w i en by Ma co Chia andini and Yu i Goegebeu [10]
was used o de e mine con idence in e als and o gene a e he plo s.
6 Summa y and Ou look
This pape ies o ind answe s o he ollowing undamen al ques ions in ex-
pe imen al esea ch.
(Q-1) How o gene a e p oblem ins ances?
(Q-2) How o gene alize expe imen al esul s?
In o de o answe ques ion (Q-1), we p opose a h ee-s age-app oach:
1. Desc ibing he eal-wo ld sys em and i s da a
2. Fea u e ex ac ion and model cons uc ion
3. Ins ance gene a ion
We demons a ed how eal-wo ld p oblem ins ances wi h ea u es om he ime-
se ies domain can be gene a ed. In his se ing, he p oposed app oach wo ks
e y good. Since his app oach uses a model, say M, o gene a e new p oblem
ins ances, one concep ual p oblem a ises: This app oach is no applicable, i he
inal goal is he de e mina ion o a model o he da a, because Mis pe de ini ion
he bes model in his case and he sea ch o good models will esul in M. Bu
he e is a simple solu ion o his p oblem. In his case, he ea u e ex ac ion and
model gene a ion should be skipped and he o iginal da a should be modi ied
by adding some noise o pe o ming ans o ma ions on he da a. Howe e , i
applicable, he model-based app oach is p e e ed, because i sheds some ligh
on he unde lying p oblem s uc u e. Fo example, seasonali y e ec s can be
p ecisely modi ied, which esul s in an be e unde s anding o he eal-wo ld
p oblem and i s s uc u e.
As a es - unc ion se andomly gene a ed es unc ions a e used. Algo i hms
wi h di e en pa ame e iza ions a e es ed on his se o p oblem ins ances. This
expe imen al se up equi es modi ied s a is ics, so-called andom-e ec s models
o mixed models. This app oach may lead o objec i e e alua ions and compa -
isons. I no mali y assump ions a e me , con idence in e als can be de e mined,
which " o ecas " he beha io o an algo i hm on unseen p oblem ins ances. Fu -
he mo e, esul s can be gene alized in eal-wo ld se ings. This gi es an answe
o ques ion (Q-2).
No e, he unde lying algo i hm and p oblem designs we e chosen o didac i-
cal pu pose. These da a a e sui able o illus a ing key ea u es o he p oposed
me hods. The e o e, algo i hm and p oblem designs we e selec ed as simple as
Beyond Pa icula P oblem Ins ances 39
yLog
2−1−2
2−2−1
2−2−2
2−1−1
2−4−2
2−3−1
2−4−1
2−1−4
2−1−3
2−3−2
2−4−4
2−3−4
2−4−3
2−2−3
2−3−3
2−2−4
1−2−3
1−2−4
1−4−4
1−1−4
1−3−4
1−1−3
1−4−3
1−3−3
1−2−1
1−1−2
1−4−2
1−3−1
1−2−2
1−3−2
1−1−1
1−4−1
−10 −8 −6 −4 −2 0
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
1
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
2
−10 −8 −6 −4 −2 0
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
3
2−1−2
2−2−1
2−2−2
2−1−1
2−4−2
2−3−1
2−4−1
2−1−4
2−1−3
2−3−2
2−4−4
2−3−4
2−4−3
2−2−3
2−3−3
2−2−4
1−2−3
1−2−4
1−4−4
1−1−4
1−3−4
1−1−3
1−4−3
1−3−3
1−2−1
1−1−2
1−4−2
1−3−1
1−2−2
1−3−2
1−1−1
1−4−1
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
4
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
5
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
6
2−1−2
2−2−1
2−2−2
2−1−1
2−4−2
2−3−1
2−4−1
2−1−4
2−1−3
2−3−2
2−4−4
2−3−4
2−4−3
2−2−3
2−3−3
2−2−4
1−2−3
1−2−4
1−4−4
1−1−4
1−3−4
1−1−3
1−4−3
1−3−3
1−2−1
1−1−2
1−4−2
1−3−1
1−2−2
1−3−2
1−1−1
1−4−1
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
7
−10 −8 −6 −4 −2 0
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
8
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
9
Fig. 12. Compa ison o he mean alues. Algo i hms a e classi ied as ollows:
mu -s eco-o eco wi h mu ∈ {no, yes}and eco ∈ {no, disc , in e 1, in e 2}. Algo-
i hm ins ance 2-1-2 pe o ms easonably well, i.e., mu a ion, no ecombina ion o
s a egy a iables and disc e e ecombina ion o objec a iables.
40 T.Ba z-Beiels ein
log(y)
2−1−2
2−2−1
2−1−1
2−2−2
2−4−1
2−3−1
2−4−2
2−4−4
2−3−2
2−1−3
2−1−4
2−3−4
2−4−3
2−2−3
2−3−3
2−2−4
1−2−3
1−2−4
1−1−3
1−3−4
1−4−3
1−1−4
1−4−4
1−3−3
1−2−1
1−1−2
1−4−2
1−3−2
1−2−2
1−1−1
1−4−1
1−3−1
−6 −4 −2
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
1, 9 ins .
Fig. 13. Compa ison o he con idence in e als. Algo i hms a e classi ied as in Fig. 12:
mu -s eco-o eco wi h mu ∈ {no, yes}and eco ∈ {no, disc , in e 1, in e 2}. 2-1-2
pe o ms easonably well, i.e., mu a ion, no ecombina ion o s a egy a iables and
disc e e ecombina ion o objec a iables. No e, he e we a e conside ing he p ob-
lem class Π1in con as o Fig. 12, whe e nine ins ances o his p oblem class we e
compa ed.
Beyond Pa icula P oblem Ins ances 41
possible. I was no ou in en ion o p esen a de ailed analysis o sea ch heu is-
ics in his pape .
Tuning p ocedu es such as sequen ial pa ame e op imiza ion [3] can bene i
om his amewo k as ollows: The algo i hm is uned as usually on a ixed se
o es p oblem ins ances. In a second s ep, he gene alizabili y o he esul s
has o be demons a ed on andomly gene a ed p oblem ins ances. Fu u e in-
es iga ions migh conside s uc u al p ope ies o he se o p oblem ins ances,
e.g., linea i y: i π1∈Πand p2∈Π, hen (aπ1+bπ2)∈Π? And, las bu no
leas , he concep o algo i hm based alida ion [12, 4] will be used o u he
in es iga ions.
The so wa e, which was used in his s udy, will be in eg a ed in o he R
package SPOT [6].
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 and he co esponding Rcode
is based on Ma co Chia andini’s and Yu i Goegebeu ’s publica ion Mixed Models
o he Analysis o Op imiza ion Algo i hms [10]. The au ho highly app ecia es
hei wo k.
Re e ences
1. T. Ba z-Beiels ein. Expe imen al Resea ch in E olu iona y Compu a ion—The
New Expe imen alism. Na u al Compu ing Se ies. Sp inge , Be lin, Heidelbe g,
New Yo k, 2006.
2. T. Ba z-Beiels ein, M. F iese, B. Naujoks, and M. Zae e e . SPOT applied o
non-s ochas ic op imiza ion p oblems—an expe imen al s udy. In K. Rod iguez
and C. Blum, edi o s, GECCO 2012 La e b eaking abs ac s wo kshop, pages 645–
646, Philadelphia, Pennsyl ania, USA, July 2012. ACM.
3. T. Ba z-Beiels ein, C. Lasa czyk, and M. P euss. The sequen ial pa ame e
op imiza ion oolbox. In T. Ba z-Beiels ein, M. Chia andini, L. Paque e, and
M. P euss, edi o s, Expe imen al Me hods o he Analysis o Op imiza ion Algo-
i hms, pages 337–360. Sp inge , Be lin, Heidelbe g, New Yo k, 2010.
4. T. Ba z-Beiels ein, S. Ma kon, and M. P euß. Algo i hm based alida ion o a
simpli ied ele a o g oup con olle model. In T. Iba aki, edi o , P oceedings 5 h
Me aheu is ics In e na ional Con e ence (MIC’03), pages 06/1–06/13 (CD–ROM),
Kyo o, Japan, 2003.
5. T. Ba z-Beiels ein and M. P euss. Au oma ic and in e ac i e uning o algo i hms.
In N. K asnogo and P. L. Lanzi, edi o s, GECCO (Companion), pages 1361–1380.
ACM, 2011.
6. T. Ba z-Beiels ein and M. Zae e e . A gen le in oduc ion o sequen ial pa ame e
op imiza ion. Technical Repo TR 01/2012, CIplus, 2012.
7. D. M. Ba es. lme4: Mixed-e ec s modeling wi h R. 2010.
8. H.-G. Beye and H.-P. Schwe el. E olu ion s a egies—A comp ehensi e in oduc-
ion. Na u al Compu ing, 1:3–52, 2002.
9. G. E. P. Box, G. M. Jenkins, and G. C. Reinsel. Time Se ies Analysis, Fo ecas ing
and Con ol. Holden-Day, 1976.