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.