R help - Dec 2011 - optim with simulated annealing SANN for combinatorial optimization

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(N^2)  # 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 N^2 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]]

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]]
> 
>