A Gentle Introduction to Sequential Parameter Optimization

CIplus, Band 1/2012 Thomas Ba z-Beiels ein, Wol gang Konen, Ho s S enzel, Bo is Naujoks A Gen le In oduc ion o Sequen ial Pa ame e Op imiza ion Thomas Ba z-Beiels ein, Ma in Zae e e A Gen le In oduc ion o Sequen ial Pa ame e Op imiza ion Thomas Ba z-Beiels ein and Ma in Zae e e Depa men o Compu e Science, Cologne Uni e si y o Applied Sciences, Ge many. Sch i en eihe CIplus TR 1/2012. ISSN 2194-2870 Abs ac The e is a s ong need o sound s a is ical analysis o simula ion and op imiza ion algo i hms. Based on his analysis, imp o ed pa ame e se - ings can be de e mined. This will be e e ed o as uning. Model-based in es iga ions a e common app oaches in simula ion and op imiza ion. The sequen ial pa ame e op imiza ion oolbox SPOT package o R[5] is a oolbox o uning and unde s anding simula ion and op imiza ion algo i hms. The oolbox includes me hods o uning based on classical eg ession and analysis o a iance echniques; ee-based models such as classi ica ion and eg essions ees (CART) and andom o es ; Gaussian p ocess models (K iging), and combina ions o di e en me a-modeling app oaches. This a icle exempli ies how an exis ing op imiza ion algo- i hm, namely simula ed annealing, can be uned using he SPOT ame- wo k. 1 In oduc ion The pe o mance o mode n sea ch heu is ics such as e olu ion s a egies (ES), di e en ial e olu ion (DE), o simula ed annealing (SANN) elies c ucially on hei pa ame e iza ions—o , s a is ically speaking, on hei ac o se ings. Finding good pa ame e se ings o an op imiza ion algo i hm will be e e ed o as uning in he emainde o his a icle. This a icle illus a es how an exis ing sea ch heu is ic can be uned using he SPOT amewo k. In o de o keep he se up as simple as possible, we will use he simula ed annealing implemen a ion, which is eely a ailable in he Rsys em [5]. This implemen a ion o he simula ed annealing heu is ic will be e e ed o as SANN in he ollowing. The e m algo i hm design summa izes ac o s ha in luence he beha io (pe o mance) o an algo i hm, whe eas p oblem design e e s o ac o s om 1 he op imiza ion (simula ion) p oblem. The ini ial empe a u e in SANN is one ypical ac o which belongs o he algo i hm design, he sea ch space dimension belongs o he p oblem design. This pape is s uc u ed as ollows. Fi s , he op imiza ion amewo k is desc ibed in Sec. 2. This amewo k consis s o h ee le els, which a e use ul o dis inguishing se e al p oblem domains. Sec ion 3 p o ides some backg ound in o ma ion abou SANN. A simple example o uning SANN is desc ibed in Sec. 4. This uning example can be used as a s a ing poin o beginne s. SPOT’s ile mode is discussed in Sec. 5. Sec ion 6 p esen s a s ep-by-s ep walk h ough he SPOT p ocedu e. How SPOT can be applied o une and analyze a bi a y algo i hms is demons a ed in Sec. 7. In con as o all hose non- de e minis ic op imiza ion p oblems, Sec. 8 explains wha changes need o be made i a de e minis ic p oblem has o be sol ed wi h SPOT. Finally, a sho summa y is p esen ed in Sec. 9. 2 Le els du ing he Tuning P ocedu e When uning an op imiza ion algo i hm, he ollowing h ee le els can be used o desc ibe he expe imen al se up (Fig. 1). (L1) The eal-wo ld sys em. This sys em allows he speci ica ion o an objec i e unc ion, say . As an example, we will use he sphe e unc ion in he ollowing. (L2) The op imiza ion algo i hm, he e SANN. I equi es he speci ica ion o algo i hm pa ame e s. (L3) The uning algo i hm, he e SPOT. An op imiza ion algo i hm (L2) equi es pa ame e s, e.g., he ini ial empe - a u e o SANN o he mu a ion a e o ES. These pa ame e s de e mine he pe o mance o he op imiza ion algo i hms. The e o e, hey should be uned o ge be e pe o mance o one algo i hm. The algo i hm is in u n used o de e mine op imal alues o he objec i e unc ion om le el (L1). 2 Objec i e Func ion L1 Op imiza ion Algo i hm L2 Tuning Algo i hm L3 SPOT Simula ed Annealing Sphe e Func ion Figu e 1: The h ee le els ha occu while uning an algo i hm ha op imizes a es unc ion. 3 Simula ed Annealing SANN Simula ed annealing is a gene ic p obabilis ic heu is ic o global op imiza- ion [4]. The name comes om annealing in me allu gy. Con olled hea ing and cooling o a ma e ial educes de ec s. Hea ing enables a oms o lea e hei ini ial posi ions (which a e local minima o hei in e nal ene gy), and con olled cooling imp o es he p obabili y o ind posi ions wi h lowe s a es o in e nal ene gy han he ini ial posi ions. The SANN algo i hm eplaces he cu en so- lu ion wi h a andomly gene a ed new solu ions. Be e solu ions a e accep ed de e minis ically, whe e wo se solu ions a e accep ed wi h a p obabili y ha depends on he di e ence be ween he co esponding unc ion alues and on a global pa ame e , which is commonly e e ed o as he empe a u e. The empe a u e is g adually dec eased du ing he op imiza ion. We conside he Rimplemen a ion o SANN, which is a ailable ia he gene al-pu pose op imiza ion unc ion op im() om he s a s package in he Rsys em. The unc ion op im() is pa ame ized as ollows > op im(pa , n, g = NULL, ..., + me hod = c("Nelde -Mead", "BFGS", "CG", "L-BFGS-B", "SANN", "B en "), + lowe = -In , uppe = In , + con ol = lis (), hessian = FALSE) He e, pa deno es ini ial alues o he pa ame e s o be op imized o e . No e, he p oblem dimension i speci ied by he leng h o his ec o , so pa =c(1,1,1,1) deno es a ou -dimensional op imiza ion p oblem. n is a unc ion o be mini- mized (o maximized), wi h i s a gumen he ec o o pa ame e s o e which minimiza ion is o ake place. g de ines a unc ion o e u n he g adien o he "BFGS", "CG" and "L-BFGS-B" me hods. I i is NULL, a ini e-di e ence app oxima ion will be used. Fo he "SANN" me hod i speci ies a unc ion o gene a e a new candida e poin . I i is NULL a de aul Gaussian Ma ko ke nel is used. The symbol . . . ep esen s u he a gumen s (op ional) ha can be be 3 passed o n and g .me hod deno es he op imiza ion me hod o be used. We will use SANN in ou examples. lowe , uppe speci y bounds on he a iables o he "L-BFGS-B" me hod, o bounds in which o sea ch o me hod "B en ". So, we will no use hese a iables in ou examples. con ol de ines a ela i ely long lis o con ol pa ame e s. We will use he ollowing pa ame e s om his lis : maxi , i.e., he maximum numbe o i e a ions, which is o SANN he maximum numbe o unc ion e alua ions. This is he s opping c i e ion. emp con ols he SANN algo i hm. I is he s a ing empe a u e o he cooling schedule wi h a de aul alue o 10. Finally, we will use max, which is he numbe o unc ion e alua ions a each empe a u e o he SANN me hod. I s de aul alue is also 10. Be o e SANN can be s a ed, he use has o speci y an objec i e unc ion . To keep hings as simple as possible, he sphe e unc ion will be used: > sphe e <- unc ion (x){ + sum(x^2) + } To ob ain ep oducible esul s, we will se he seed. > se .seed(123) Using a h ee-dimensional objec i e unc ion and he s a ing poin (ini ial alues o he pa ame e s o be op imized o e ) (−1,1,−1), we can execu e he op imiza ion uns as ollows: > es <- op im(c(-1,1,-1), sphe e, me hod="SANN", + con ol=lis (maxi =100, emp=10, max = 10)) > es $pa [1] -0.3209798 0.6608565 0.4414664 $ alue [1] 0.7346519 $coun s unc ion g adien 100 NA $con e gence [1] 0 $message NULL The bes , i.e., smalles , unc ion alue, which was ound by SANN, eads 0.7346519. The co esponding poin in he sea ch space is app oxima ely (- 0.3209798, 0.6608565, 0.4414664). No g adien in o ma ion was used and one hund ed unc ion e alua ions we e pe o med. The a iable con e gence is an in ege code, and i s alue 0 indica es success ul comple ion o he SANN un. No addi ional message is e u ned. 4 Now ha we ha e pe o med a i s un o he SANN algo i hm on ou simple es unc ion, we a e in e es ed in imp o ing SANN’s pe o mance. The SANN heu is ic equi es some pa ame e se ings, namely emp and max. I hese alues a e omi ed, a de aul alue o en is used. The ques ions is: A e he de aul algo i hm pa ame e se ings, namely emp =10 and max=10, adequa e o SANN o can hese alues be imp o ed? Tha is, we a e ying o une he SANN op imiza ion algo i hm. A ypical beginne in algo i hm uning would y o imp o e he algo i hm’s pe o mance by manually inc easing o dec easing he algo i hm pa ame e al- ues, e.g., choosing emp = 20 and max= 5. This p ocedu e is e y ime con- suming and does no allow e icien s a is ical conclusions. The e o e, we will p esen a di e en app oach, which uses he SPOT. Al hough he se up o he uning p ocedu e wi h SPOT is e y simila o he se up discussed in his sec ion, i enables deepe insigh s in o he algo i hm’s pe o mance. 4 Tuning wi h SPOT: A Fi s Example 4.1 The Objec i e Func ion (L1): Sphe e To keep he si ua ion as simple as possible, we will use he sphe e es unc ion again: (x) = n X i=1 x2 i SANN will be used o de e mine i s minimum unc ion alue. As abo e, he sphe e unc ion is de ined as > sphe e <- unc ion(x){ + sum(x^2) + } 4.2 The Op imiza ion Algo i hm (L2): SANN Again, se e al se ings ha e o be speci ied o he algo i hm o be uned. The p oblem design equi es he speci ica ion o he s a ing poin o he sea ch. No e, i s leng h de ines he p oblem dimension. > x0 <- c(-1,1,-1) #s a ing poin ha SANN uses when op imizing sphe e() Since x0 has h ee elemen s, we a e acing a h ee dimensional op imiza ion p oblem. The budge , i.e., he maximum numbe o unc ion e alua ions ha can be used by SANN is speci ied ia > maxi <- 100 As abo e, he SANN implemen a ion om he Rsys em will be used ia he op im() unc ion. We will conside wo pa ame e s: he ini ial empe a u e ( emp) and he numbe o unc ion e alua ions a each empe a u e ( max). Bo h 5 Table 1: SANN pa ame e s. The i s wo pa ame e s belong o he algo i hm design, whe eas he emaining pa ame e s a e om he p oblem design. No e, he s a ing poin de ines he p oblem dimension, i.e., by speci ying a h ee di- mensional s a ing poin he p oblem dimension is se o h ee. I no seed is speci ied, 1234 is used as he de aul seed alue. SPOT uses wo andom seeds: he i s is used by SPOT i sel , e.g., o gene a ing andomized designs. The second is used by he algo i hm Name Symbol Fac o name Ini ial empe a u e emp Numbe o unc ion e alua- ions a each empe a u e max max S a ing poin ~x0= (−1,1,−1) x0 P oblem dimension n= 3 Objec i e unc ion sphe e sphe e() Quali y measu e Expec ed pe o mance, e.g., E(y) y Ini ial seed s1234 Budge maxi = 100 maxi a e in ege alues. To in e ace wi h SPOT, a w appe unc ion spo 2Sann() can be de ined as ollows. > spo 2Sann <- unc ion(pa s,x0, n,maxi ){ + emp<-pa s[1] + max<-pa s[2] + y <- op im(x0, n, me hod="SANN", con ol=lis (maxi =maxi , emp= emp, max= max)) + e u n(y$ alue) + } No e, as explained in Sec . 3, op im(x0, n, me hod="SANN", con ol=lis (maxi =maxi , emp= emp, max= max)) is he s anda d way o s a ing SANN as an Rop imize . All pa ame e s and se ings o SANN as used o his simple example a e summa ized in Table 1. 4.3 The Tuning P ocedu e (L3): SPOT The SPOT package can be ins alled om wi hin Rusing he > ins all.packages("SPOT") command. Al e na i ely, SPOT can downloaded om he comp ehensi e R a chi e ne wo k a h p://CRAN.R-p ojec .o g/package=SPOT. The la e p ocedu e is ecommended o he expe ienced Ruse only. SPOT is one possi- ble implemen a ion o he sequen ial pa ame e op imiza ion (SPO) amewo k in oduced in [1]. Fo a de ailed documen a ion o he unc ions om he SPOT package, he eade is e e ed o he package help manuals. 6 SPOT has o be loaded o he wo kspace and a egion o in e es (ROI) has o be de ined. The ROI speci ies SPOT’s sea ch in e als o he SANN pa ame e s, i.e., o max and emp. > equi e(SPOT) > oi<-spo ROI(c(1,1),c(100,100), ype=c("INT","INT")) He e, bo h pa ame e s emp and max will be uned in he egion be ween one and 100. Finally, be o e calling SPOT, he uning p ocedu e has o be con igu ed. This is done by se ing up a con ig lis . He e, we speci y in o ma ion abou he ini ial design size (ini .design.size=4) and he numbe o me a models which a e build by SPOT (au o.loop.s eps=5). Mo e con igu a ions can be chosen, bu emain a de aul alues o his simple example. > con ig<-lis (alg. unc=spo 2Sann, + alg. oi= oi, + ini .design.size=4, + au o.loop.s eps=5) Now we a e eady o s a SPOT ia spo (). > es<-spo (spo Con ig=con ig,x0=x0, n=sphe e,maxi =maxi ) spo .R::spo s a ed 4.4 Resul s Ou pu om he SPOT un is s o ed in he es a iable which is a lis . Resul s om each SANN e alua ion a e s o ed in he es$alg.cu en Resul elemen . > s ( es$alg.cu en Resul ) 'da a. ame': 53 obs. o 9 a iables: $ Func ion: Fac o w/ 1 le el "Use SuppliedFunc ion": 1 1 1 1 1 1 1 1 1 1 ... $ XDIM : num 2 2 2 2 2 2 2 2 2 2 ... $ YDIM : in 1 1 1 1 1 1 1 1 1 1 ... $ STEP : num 0 0 0 0 0 0 0 0 1 1 ... $ SEED : num 1234 1235 1234 1235 1234 ... $ CONFIG : in 1 1 2 2 3 3 4 4 5 5 ... $ VARX1 : num 100 100 54 54 2 2 40 40 11 11 ... $ VARX2 : num 43 43 99 99 57 57 7 7 57 57 ... $ Y : num 3 2.964 3 2.964 0.176 ... SPOT gene a es many in o ma ion which can be used o a s a is ical anal- ysis. Fo example, he bes con igu a ion ound can be displayed as ollows. > bes <- es$alg.cu en Bes [n ow( es$alg.cu en Bes ),] > p in (bes ) Y VARX1 VARX2 COUNT CONFIG STEP 32 0.1578842 2 57 4 3 6 7 0.5 1.0 1.5 2.0 2.5 ● 20 40 60 80 100 20 40 60 80 100 VARX1 VARX2 Figu e 2: Con ou plo o he las me a model (Random Fo es ) used by he SPOT un when uning SANN. VARX1 is emp, VARX2 is max. Resul s can also be used o illus a e he algo i hm’s pe o mance. Se e al p e-de ined epo unc ions come wi h SPOT, e.g., he spo Repo Con ou , which gene a es he con ou plo om Fig. 2. > spo (spo Con ig=append(lis ( + epo . unc="spo Repo Con ou ", + epo .in e ac i e=F), + es), + spo Task=" ep") 5SPOT File Mode SPOT can be un in wo di e en modes1: •File mode enabled: In o ma ion a e s o ed in se e al iles, which allow an ex ensi e analysis. P e e ed mode, i SPOT is used in e ac i ely o i he un is expec ed o ake a he long. •File mode disabled: Should be used o imp o e pe o mance. Basically, a good choice when inal esul s a e impo an . The ile mode only conce ns he SPOT ou pu . These iles will be e e ed o as ou pu iles. Rega dless o he chosen ile mode, he use can selec ei he o p o ide he SPOT se ings and pa ame e s as R a iables in he wo kspace, o o p o ide e e y hing in iles. These iles will be e e ed o as inpu iles. In his sec ion i is explained how o use SPOT using inpu and ou pu iles. Fo his pu pose, he same se up as in he p e ious sec ion will be used. 1This sec ion con ains ad anced ma e ial and can be skipped du ing he i s eading. 8 6.3 The Simple Example Re isi ed—S ep-by-s ep We will use he example om Sec. 4 o illus a e he ou s eps (ini , un, seq, and ep), which we e used by SPOT. > sphe e <- unc ion(x){ + sum(x^2) + } > x0 <- c(1,-1,1) #s a ing poin ha SANN uses when op imizing sphe e() > maxi <- 100 #numbe o e alua ions o sphe e() allowed o SANN > spo 2Sann <- unc ion(pa s,x0, n,maxi ){ + emp<-pa s[1] + max<-pa s[2] + y <- op im(x0, n, me hod="SANN", + con ol=lis (maxi =maxi , + emp= emp, max= max)) + e u n(y$ alue) + } > equi e(SPOT) > oi<-spo ROI(c(1,1),c(100,100), ype=c("INT","INT")) > con ig<-lis (alg. unc=spo 2Sann, + alg. oi= oi, + ini .design.size=10, + au o.loop.ne als=20, + spo . ileMode=T + ) Now, we will execu e he i s s ep (ini ) only. > es<-spo (spo Con ig=con ig,x0=x0, n=sphe e,maxi =maxi ,spo Task="ini ") spo .R::spo s a ed The ini ial design can be isualized as ollows. > x.des<- es$alg.cu en Design$VARX1 > y.des<- es$alg.cu en Design$VARX2 > plo (y.des ~ x.des, ype="p") 15 ● ● ● ● ● ● ● ● ● ● 20 40 60 80 20 40 60 80 x.des y.des Based on hese design poin s, SPOT will un he algo i hm. The esul s o he algo i hms uns can hen be accessed. > es<-spo (spo Con ig= es,x0=x0, n=sphe e,maxi =maxi ,spo Task=" un") spo .R::spo s a ed > d . es <- es$alg.cu en Resul > p in (d . es) Func ion XDIM YDIM STEP SEED CONFIG VARX1 VARX2 Y 1 Use SuppliedFunc ion 2 1 0 1234 1 71 95 3.0000000 2 Use SuppliedFunc ion 2 1 0 1235 1 71 95 0.4653657 3 Use SuppliedFunc ion 2 1 0 1234 2 11 90 0.3945913 4 Use SuppliedFunc ion 2 1 0 1235 2 11 90 0.2432183 5 Use SuppliedFunc ion 2 1 0 1234 3 70 39 1.5021431 6 Use SuppliedFunc ion 2 1 0 1235 3 70 39 0.4653657 7 Use SuppliedFunc ion 2 1 0 1234 4 58 13 3.0000000 8 Use SuppliedFunc ion 2 1 0 1235 4 58 13 0.4653657 9 Use SuppliedFunc ion 2 1 0 1234 5 94 45 3.0000000 10 Use SuppliedFunc ion 2 1 0 1235 5 94 45 0.4653657 11 Use SuppliedFunc ion 2 1 0 1234 6 9 25 0.4996259 12 Use SuppliedFunc ion 2 1 0 1235 6 9 25 1.8288022 13 Use SuppliedFunc ion 2 1 0 1234 7 30 51 0.6428562 14 Use SuppliedFunc ion 2 1 0 1235 7 30 51 0.4653657 15 Use SuppliedFunc ion 2 1 0 1234 8 83 64 1.4493019 16 16 Use SuppliedFunc ion 2 1 0 1235 8 83 64 0.4653657 17 Use SuppliedFunc ion 2 1 0 1234 9 37 5 3.0000000 18 Use SuppliedFunc ion 2 1 0 1235 9 37 5 1.4660851 19 Use SuppliedFunc ion 2 1 0 1234 10 45 72 3.0000000 20 Use SuppliedFunc ion 2 1 0 1235 10 45 72 0.4653657 We can use esul s om he i s un o gene a e a epo . > spo (spo Con ig=append(lis ( + epo . unc="spo Repo Con ou ", + epo .in e ac i e=F), + es), + spo Task=" ep") O else we can use mo e s eps, o con inue uning he algo i hm > es<-spo (spo Con ig= es,x0=x0, n=sphe e,maxi =maxi ,spo Task="seq") > es<-spo (spo Con ig= es,x0=x0, n=sphe e,maxi =maxi ,spo Task=" un") > es<-spo (spo Con ig= es,x0=x0, n=sphe e,maxi =maxi ,spo Task="seq") > es<-spo (spo Con ig= es,x0=x0, n=sphe e,maxi =maxi ,spo Task=" un") I his is done, he esul s a e compa able o he au oma ed uning, unless he use modi ies some a iables. And his is whe e one o he main ad an ages o he s ep-by-s ep p ocedu e comes in. The use can decide o al e he nex design, ins ead o simply using wha he "seq" s ep sugges s. The use can y o emo e ou lie s which a e isible o him om he esul s o he " un" s ep. O he migh decide o change SPOT se ings like he used me a model du ing he uning, o ins ance swi ching om a simple linea model o a mo e ad anced K iging model. I migh e en be easonable o change he egion o in e es , i he use obse es ha ano he egion migh be mo e in e es ing o he uning p ocedu e. In con as o he au oma ed uning, he s ep-by-s ep app oach allows o use knowledge o be aken in o conside a ion. O cou se his needs mo e ex- pe ise o he use , bu can po en ially imp o e esul s signi ican ly. 7 In e acing SPOT: An Ex ended Example The ea lie sec ions desc ibed how o use SPOT in di e en ways o une unc- ions o algo i hms in R. Howe e , o en algo i hms a e al eady implemen ed in o he p og aming languages. The e o e, his sec ion illus a es how SPOT can be used o uning and analyzing an a bi a y algo i hm, which is execu ed wi h a call o he sys em command line. As an example, a simple e olu ion s a egy implemen ed in JAVA will be used, namely he (1+1)-ES. The (1+1)-ES c ea es one o sp ing by mu a ion in each gene a ion. I he o sp ing is be e han he pa en , i will become he nex gene a ions pa en . This s a egy has an in e nal s ep size used o mu a ion. The s ep size is mul iplied wi h he s ep size mul iplie i he success a e is highe han 1 5, and di ided by he s ep size mul iplie i i is smalle . I i is exac ly 1 5, i emains unchanged. Fo his s a egy, h ee pa ame e s can be a ied: 17 1. ini ial s ep size - Ini ial alue o he s ep size. 2. s ep size mul iplie - Pa ame e o he s ep size adap ion. 3. his o y leng h - The numbe o pas s eps conside ed o calcula ion o he success a e. 7.1 P oblem De ini ion As ea lie desc ibed o SANN, he i s s ep is o de ine he p oblem o be sol ed. He e, he p oblem is o une he (1+1)-ES on he wo dimensional sphe e unc ion (called "Ball" in he JAVA code). The s a ing poin is chosen as (-2,3), and he (1+1)-ES has a budge o 100 e alua ions on he sphe e unc ion o ind he op imum. > #choose a ge unc ion which is de ined in he ja a code > n<-"de. hkoeln.spo .objec i e unc ions.Ball" > #dimension o a ge unc ion > n=2 > #s a ing poin ha he (1+1)-ES uses when op imizing he a ge unc ino > xp0 <- "[-2.0,3.0]" > px <- 0 #indi idual p in ing mode > py <- 1 #objec i e unc ion alue p in ing mode > #s opping c i e ion: budge o (1+1)-ES > s eps <- 100 > #s opping c i e ion: minimum alue > a ge <- 1e-20 > #seed o be passed o he algo i hm > alg.seed <<- 1 7.2 In e acing wi h SPOT The second s ep is now o de ine a w appe unc ion o be called by SPOT, which will in u n call he JAVA code. The .ja ile o he JAVA code used he e has o be in he cu en wo king di ec o y. > spo 2opoes <- unc ion(pa s, ,n,xp0,px,py,s eps, a ge ){ + sigma0<-pa s[1] #ini ial s ep size + a<-pa s[2] #s ep size muliplie + g<- ound(pa s[3]) #his o y leng h, has o be in ege ! + alg.seed<<-alg.seed+1 + #No e: he used ja ile has o be in he cu en wo king di ec o y (see also: se wd(), ge wd()) + callS ing <- pas e("ja a -ja simpleOnePlusOneES.ja " + , alg.seed, s eps, a ge , , n, xp0, sigma0, a, g, px, py, sep = " ") + p in (callS ing) + y <-sys em(callS ing, in e n= TRUE) #e alua e calls ing + e u n(as.nume ic(as.cha ac e (y))) # e u n as nume ic + } 7.3 Con igu ing and Running SPOT The pa ame e s ha e o be assigned o a egion o in e es , in which hey a e uned. He e, he i s wo pa ame e s a e loa s (ini ial s ep size and s ep size mul iplie ), he hi d is an in ege (i.e. his o y leng h). > equi e(SPOT) > oi<-spo ROI(c(0.1,1,2),c(5,2,100), ype=c("FLOAT","FLOAT","INT")) 18 Finally, SPOT can be con igu ed and s a ed. A K iging model is selec ed o he sequen ial model op imiza ion. Wi h his se ing, new design poin s will be ound by applying Co a iance Ma ix Adap ion E olu ion S a egy ("cmaes") o he build model. > con ig<-lis (alg. unc=spo 2opoes, + alg. oi= oi, + seq.p edic ionModel. unc="spo P edic Fo es e ", + seq.p edic ionOp . unc="spo P edic Op Mul i", + seq.p edic ionOp .me hod="cmaes", + seq.p edic ionOp .budge =1000, + epo . unc="spo Repo Sens", + spo . ileMode=F, + io. e bosi y=3, + au o.loop.ne als=100) > spo Resul s<-spo (spo Con ig=con ig, = n,n=n,xp0=xp0,px=px,py=py,s eps=s eps, a ge = a ge ) The esul s o his uning un a e s o ed in he spo Resul s a iable, and can be p ocessed o u he analysis. Also, he "spo Repo Sens" Repo unc ion will p esen a small summa y o in luence and pe o mance o he di e en uned pa ame e s. 8 De e minis ic P oblems P e ious sec ions discussed he uning o non-de e minis ic, i.e., noisy, algo- i hms, which is he usual case when uning e olu iona y algo i hms. A e going h ough hese examples in he p e ious sec ions, his sec ion p esen s an applica ion o SPOT in a simple se ing: We will desc ibe how SPOT can be used o uning de e minis ic algo i hms. To p esen a e y simple example, SPOT will be used o minimizing he sphe e unc ion. Le el (L2) om Fig. 1 is omi ed, and he uning algo i hm o le el (L3) is applied di ec ly o he eal-wo ld sys em on le el (L1). So ins ead o uning SANN, which in u n op imizes he sphe e unc ion, SPOT ies o ind he minimum o he sphe e unc ion di ec ly. This example illus a es necessa y modi ica ions o he SPOT con igu a ion in de e minis ic se ings. Since no andomness occu s, epea s o o he mechanism o cope wi h noise a e no necessa y anymo e. The sphe e unc ion is de ined as usual: > sphe e <- unc ion(x){ + sum(x^2) + } SPOT equi es an ROI. The in e al [−5; 5] ×[−5; 5] was chosen as he egion o in e es , i.e., we a e conside ing a wo-dimensional op imiza ion p oblem. > oi<-spo ROI(c(-5,-5),c(5,5)) We can s a wi h a con igu a ion lis ha looks e y much like ea lie examples > con ig<-lis (alg. unc=sphe e, + alg. oi= oi, + seq.p edic ionModel. unc="spo P edic Fo es e ", + seq.p edic ionOp .me hod="L-BFGS-B", + spo . ileMode=F, + io. e bosi y=0, + au o.loop.ne als=25) 19 Howe e , he e a e ce ain changes o be made o con igu a ion o de e minis ic p oblems. 1. Op imal Compu a ion Budge Alloca ion is nei he necessa y no possible, so i has o be deac i a ed. Hence, we se spo .ocba o FALSE. 2. The ini ial and sequen ial design poin s do no need o be e alua ed epea - edly. The e o e, we se ini .design. epea s and seq.design.maxRepea s o one. > con ig$spo .ocba=FALSE > con ig$ini .design. epea s=1 > con ig$seq.design.maxRepea s=1 Wi h hese changes, SPOT can be s a ed and he gene a ed esul s can iewed. > es<-spo (spo Con ig=con ig) spo .R::spo s a ed > p in ( es$alg.cu en Resul [,4:9]) STEP SEED CONFIG VARX1 VARX2 Y 1 0 1234 1 2.01353063 4.45208558 23.87537164 2 0 1234 2 -3.98847824 3.95660866 31.56271072 3 0 1234 3 1.99644571 -1.15556965 5.32113668 4 0 1234 4 0.76568967 -3.77723140 14.85375770 5 0 1234 5 4.31466261 -0.57982982 18.95251607 6 0 1234 6 -4.18798826 -2.58001706 24.19573368 7 0 1234 7 -2.00878078 0.02079085 4.03563249 8 0 1234 8 3.20075959 1.38044797 12.15049857 9 0 1234 9 -1.35396278 -4.57765157 22.78810913 10 0 1234 10 -0.56244927 2.19142606 5.11869737 11 1 1234 11 -0.31929738 0.56017576 0.41574770 12 1 1234 12 0.49380446 -0.72776007 0.77347757 13 1 1234 13 0.43639658 0.86660513 0.94144642 14 2 1234 14 -0.42955831 0.06721684 0.18903845 15 2 1234 15 0.15468483 -0.48861284 0.26266991 16 2 1234 16 0.52580978 0.15022249 0.29904272 17 3 1234 17 -0.15182185 -0.09236320 0.03158083 18 3 1234 18 -0.31333973 0.14101794 0.11806785 19 3 1234 19 0.31928189 -0.19640035 0.14051402 20 4 1234 20 0.02987370 -0.12132428 0.01561202 21 4 1234 21 -0.09071041 -0.33762395 0.12221831 22 4 1234 22 -0.28203678 -0.25850504 0.14636960 23 5 1234 23 0.58639646 -0.55008131 0.64645026 24 5 1234 24 0.81520531 0.40903780 0.83187162 25 5 1234 25 0.90825434 -0.36748141 0.95996853 As can be seen, each con igu a ion es ed du ing he SPOT un was e alua ed only once. We can ex ac he bes solu ion wi h he ollowing command. 20 > bes <- es$alg.cu en Bes [n ow( es$alg.cu en Bes ),] > p in (bes ) Y VARX1 VARX2 COUNT CONFIG STEP 201 0.01561202 0.0298737 -0.1213243 1 20 6 No e, i you a e uning (op imizing) de e minis ic algo i hms o unc ions, OCBA has o be disabled. O he wise, SPOT will exi wi h a wa ning message. 9 Summa y This a icle desc ibes how SPOT can be used o uning a sea ch heu is ic, i.e., SANN. We can dis inguish h ee le els, which a e in ol ed in his uning p ocess. On le el (L1), we can speci y he eal-wo ld sys em, which includes he objec i e unc ion. The second le el (L2) con ains he op imiza ion algo i hm, which can be a s ochas ic algo i hm such as SANN. Finally, he hi d le el (L3) desc ibes he uning algo i hm, e.g., SPOT. SANN’s basic unc ionali y is in oduced and i s pa ame iza ion desc ibed. Two pa ame e s, namely maxand emp, a e c ucial o SANN’s pe o mance. Ins ead o manually uning hese wo pa ame e s, we use he SPOT o ind good pa ame e alues sys ema ically. The e o e, a simple objec i e unc ion, i.e., he sphe e unc ion, was used. This esul s in he ollowing se ing: SANN was used o op imize he sphe e unc ion, and SPOT was used o op imize SANN. To di e en ia e hese wo op imiza ions, he la e was e e ed o as uning. We also discussed SPOT’s ile mode and p esen ed a s ep-by-s ep walk h ough SPOT’s uning p ocess. The SPOT p ocess is based on he ollow- ing s eps: Ini ializa ion (spo Task=ini ), un (spo Task= un), sequen ial (spo - Task=seq), and epo (spo Task= ep). I SPOT is un au oma ically, he ollowing sequences is execu ed: ini , un, seq, un, . . ., and inally ep. How o se up an in e ace o op imiza ion algo i hms, which we e p o- g ammed in o he p og amming languages was discussed. A w appe unc ion, which execu es a JAVA p og am, was in oduced. Finally, we discussed he SPOT con igu a ion o de e minis ic algo i hms. The book [2] migh be a good s a ing poin o u he s udies. New ela ed o SPOT a e published on www.spo se en.de. Re e ences [1] Thomas 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] Thomas Ba z-Beiels ein, Ma co Chia andini, Luis Paque e, and Mike P euss, edi o s. Expe imen al Me hods o he Analysis o Op imiza ion Al- go i hms. Sp inge , Be lin, Heidelbe g, New Yo k, 2010. 21 [3] L. B eiman. Random o es s. Machine Lea ning, 45(1):5 –32, 2001. [4] S. Ki pa ick e al. Op imiza ion by simula ed annealing. Science, 220:671– 680, 1983. [5] R Co e Team. R: A Language and En i onmen o S a is ical Compu ing. R Founda ion o S a is ical Compu ing, Vienna, Aus ia, 2012. ISBN 3- 900051-07-0. 22