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]]
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
