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

