>>>Tutorial PPSN 2016<<<

In the above attached PDF you can find our slides for the tutorial “Meta-Model Assisted (Evolutionary) Optimization”, held at PPSN 2016.

In addition, please find below the code that is used in the tutorial’s example with R:

## Introductory comments:
##
## To run this script, you need to install R, the language for statistical computing.
## https://cran.r-project.org/
## For ease of use, you may consider RStudio IDE, but this is not required.
## https://www.rstudio.com/
## For a tutorial/introduction to R, see e.g.:
## https://cran.r-project.org/doc/manuals/r-release/R-intro.html

## Preparation:
##
## You may need to install some of the packages that this example
## for the PPSN 2016 tutorial is using. If they are available,
## the library("...") command used in the following will
## load the successfully. Otherwise you may receive an error.
## To install the required packages, uncomment the following lines:
# install.packages("SPOT") 
library("SPOT") #load required package: SPOT

## Initialize random number generator seed. Reproducibility.
set.seed(1)

## Main part
## This example should demonstrate the use of surrogate-modeling
## in optimization. To that end, we first need to define an
## optimization problem to be solved by such methods.
## Clearly, we lack the time to consider a real-world, expensive
## optimization problem. Hence, use the following simple, 
## one-dimensional test function, from the book 
## A. I. J. Forrester, A. Sobester, A. J. Keane; 
## "Engineering Design via Surrogate Modeling"; 
## Wiley (2008)

objectFun <- function(x){
	(6*x-2)^2 * sin(12*x-4)
}

## Plot the function:
par(mar=c(4,4,0.5,4),mgp=c(2,1,0))
curve(objectFun(x),0,1)

## Now, let us assume objectFun is expensive.
## First, we start with making some initial
## design of experiment, which in this case
## is simply a regular grid:
x <- seq(from=0, by=0.3,to=1)

## Evaluate with objective:
y <- sapply(x,objectFun)

## Add to plot:
points(x,y)

## Build a model (here: Kriging, with the SPOT package. 
## But plenty of alternatives available)
fit <- forrBuilder(as.matrix(x),as.matrix(y),
    control=list(uselambda=FALSE #do not use nugget effect (regularization)
    ))

## Evaluate prediction based on model fit
xtest <- seq(from=0, by=0.001,to=1)
pred <- predict(fit,as.matrix(xtest),predictAll=T)
ypred <- pred$f
spred <- pred$s

## Plot the prediction of the model:
lines(xtest,ypred,lty=2)

## Plot suggested candidate solution
points(xtest[which.min(ypred)],ypred[which.min(ypred)],col="black",pch=20)

## Calculate expected improvement (EI)
ei <- 10^(-spotInfillExpImp(ypred,spred,min(y)))
par(new = T)
plot(xtest,ei,lty=3, type="l", axes=F, xlab=NA, ylab=NA, 
     ylim=rev(range(ei)))
axis(side = 4); mtext(side = 4, line = 2, 'EI')
## but note: EI is on a different scale


## Plot suggested candidate solution, based on EI
points(xtest[which.max(ei)],ei[which.max(ei)],col="red",pch=20)
newx <- xtest[which.max(ei)]

## Add data
x <- c(x,newx)
y <- c(y,objectFun(newx))

## Now repeat the same as often as necessary:
repeatThis <- expression({
  curve(objectFun(x),0,1)
  points(x,y)
  fit <- forrBuilder(as.matrix(x),as.matrix(y),
                    control=list(uselambda=FALSE
                    ))
  xtest <- seq(from=0, by=0.001,to=1)
  pred <- predict(fit,as.matrix(xtest),predictAll=T)
  ypred <- pred$f
  spred <- pred$s
  lines(xtest,ypred,lty=2)
  points(xtest[which.min(ypred)],ypred[which.min(ypred)],col="black",pch=20)  
  ei <- 10^(-spotInfillExpImp(ypred,spred,min(y)))
  par(new = T)
  plot(xtest,ei,lty=3, type="l", axes=F, xlab=NA, ylab=NA, 
       ylim=rev(range(ei)))
  axis(side = 4); mtext(side = 4, line = 2, 'EI')
  points(xtest[which.max(ei)],ei[which.max(ei)],col="red",pch=20)
  newx <- xtest[which.max(ei)]
  x <- c(x,newx)
  y <- c(y,objectFun(newx)) }) 
eval(repeatThis) 
eval(repeatThis) 
eval(repeatThis) 
eval(repeatThis) 
eval(repeatThis) 
eval(repeatThis) 
eval(repeatThis) 
eval(repeatThis) 
## Observation: 
## EI looks noisy, strange. 
## Predicted mean has low accuracy. 
## Why?  
## If repeated to often -> Numerical issues: 
## Due to close spacing of candidates -> Problem for Kriging model
## Potential remedy: use regularization with nugget and reinterpolation.
## Note: Other interpretation of such an issue may be convergence of
## the optimization process. But this is not necessarily correct.

## repeat as often as necessary (but now with regularization):
repeatThis <- expression({
  curve(objectFun(x),0,1)
  points(x,y)
  fit <- forrBuilder(as.matrix(x),as.matrix(y),
              control=list(
              uselambda=TRUE, # Use nugget (parameter lambda)
              reinterpolate=T # Reinterpolation, to fix uncertainty estimates, etc.
                     ))
  xtest <- seq(from=0, by=0.001,to=1)
  pred <- predict(fit,as.matrix(xtest),predictAll=T)
  ypred <- pred$f
  spred <- pred$s
  lines(xtest,ypred,lty=2)
  points(xtest[which.min(ypred)],ypred[which.min(ypred)],col="black",pch=20)  
  ei <- 10^(-spotInfillExpImp(ypred,spred,min(y)))
  par(new = T)
  plot(xtest,ei,lty=3, type="l", axes=F, xlab=NA, ylab=NA, 
       ylim=rev(range(ei)))
  axis(side = 4); mtext(side = 4, line = 2, 'EI')
  points(xtest[which.max(ei)],ei[which.max(ei)],col="red",pch=20)
  newx <- xtest[which.max(ei)]
  x <- c(x,newx)
  y <- c(y,objectFun(newx))
})
eval(repeatThis)
eval(repeatThis)