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
