[R] Discrete simulated annealing

[Enrico Schumann]

On Tue, 28 May 2013, Marcus Nunes <marcus.nunes at gmail.com> writes:

> Hello all
>
> I'm trying to use simulated annealing to optimize a function. I know I can
> use ?optim with method="SANN" to do it.
>
> However, I'd like to make optim to search for the best solution among a set
> of possible points in my domain, and not informing a lower and an upper
> bound to the optmization function.
>
> Do you have an idea on how to do it?
>
> Thanks,

I have not often used optim/SANN, but you can provide a user-defined
neighbourhood function, which you can pass via the 'gr' argument to
optim.

The neighbourhood function should take a solution as argument, change it
slightly and return this changed solution.  So you have to write the
function such that it can only move from and to the "possible points"
that you specify.

A simple example: suppose the desired solution is a vector of length
three, and the "possible points" are specified as integers such that

   x[1] can be 1, 2 or 7
   x[2] can be 1:10
   x[3] can be 2, 7 or 17

Then a simple neighbour function might look like this (certainly not the
most efficient implementation, but it should give you an idea):

  neighbour <- function(x) {

      ## possible points
      pp <- list(x1 = c(1,2,7),
                 x2 = c(1:10),
                 x3 = c(2,7,17))

      ## choose element of x to change ...
      change.what <- sample.int(length(pp), 1)  

      ## ... and change it
      x[change.what] <- sample(pp[[change.what]], 1)  
      x    
  }


(x <- c(1,1,2))      ## a feasible initial solution
## [1] 1 1 2

(x <- neighbour(x))
## [1] 2 1 2

(x <- neighbour(x))
## [1] 2 9 2

(x <- neighbour(x))
## [1]  2  9 17


If upper/lower bounds are to be ignored, just set them to
ridiculously-high or low values.

-- 
Enrico Schumann
Lucerne, Switzerland
http://enricoschumann.net