[R] optim with simulated annealing SANN for combinatorial optimization

[John C Nash]

A particularly unfortunate aspect of "SANN" in optim() is that it will evaluate the
objective function 'maxit' times and quit with conv=0, implying it has "converged".

The Rd file points out a number of departures of SANN from the other optimizers, but a key
one is that it does NOT return a result that can be considered as an optimum without
external testing and evaluation. When (if??) I get to a point where I'm satisfied with the
local minimizers in the optimx package, I hope to prepare a similar wrapper for the
stochastic optimizers like SANN. As with many tools in this domain, for effective use they
require more knowledge than many of their users possess, and can be dangerous because they
seem to "work".

JN


> Message: 72
> Date: Fri, 16 Dec 2011 18:41:12 +1100
> From: Dae-Jin Lee <lee.daejin at gmail.com>
> To: r-help at r-project.org
> Subject: [R] optim with simulated annealing SANN for combinatorial
> 	optimization
> Message-ID:
> 	<CAN5FGbU4DeAugYghk-AyYTFeeDgeSEpHAf1JGTPkmtD=0tgKBw at mail.gmail.com>
> Content-Type: text/plain
> 
> Hi all
> 
> I am trying to solve a combinatorial optimization problem. Basically, I can
> reduce my problem into the next problem:
> 
> 1.- Given a NxN grid of points, with some values in each cell
> 2.- Find the combination of K points on the grid such that, the maximum
> mean value is obtained
> 
> 
>  I took the Travel SalesMan problem example in ?optim documentation. I am
> not sure if I have understood correctly the SANN implementation in optim,
> as I do not see how the acceptance probability comes out. And it looks like
> I am only evaluating the criteria several times and keep the maximum at the
> end.
> 
> Thanks in advance
> 
> 
> Here is some example code in R
> 
> ####### toy example
> N=5
> K=6
> 
> new.points = expand.grid(1:N,1:N)  # grid points
> 
> set.seed(1234)
> 
> resp=rnorm(N2)  # random values on each grid cell
> 
> #######  function to generate the sequence of candidates
> generate<-function(ind){
> ####
> idx <- seq(1, nrow(new.points), by=1)   # index of 1 to N2 grid cells
> swap.points <- c(sample(ind,1),sample(idx[-c(ind)], size=1))      # swap
> between points of the initial set and other candidate
> ind[which(ind==swap.points[1])]<-idx[which(idx==swap.points[2])]
> ####
> cat("set  =",ind,"\n")
> cat("crit =",media(ind),"\n")
> cat("swap =",swap.points,"\n")
> 
> plot(new.points[,1:2],col='black',xlim=c(range(new.points[,1])),ylim=c(range(new.points[,2])))
> points(new.points[ind,1:2],col='blue',pch=19,xlim=c(range(new.points[,1])),ylim=c(range(new.points[,2])))
> return(as.numeric(ind))
> }
> 
> #######  function to calculate the mean value of the points on the grid
> media=function(sq){
> med=mean(resp[sq])
> return(as.numeric(med))
> }
> 
> #######  initial set of K candidates
> init=sample(1:K,K)
> 
> #######  run SANN
> res <- optim(init, media ,generate, method="SANN",control =
> list(maxit=20000, temp=100,tmax=1000, trace=TRUE, REPORT=1, fnscale=-1))
> new.points[sort(res$par),]
> plot(new.points,cex=.1)
> points(new.points[res$par,],col=3,lwd=3,cex=1.5)
> 
> 	[[alternative HTML version deleted]]
> 
>