[R] Constrined dependent optimization.

[Ben Bolker]

rkevinburton at charter.net wrote:
> I am sorry but I don't see the connection. with SANN and say 3
> variables one of the steps may increment x[1] by 0.1. Not only is
> this a non-discrete integer value but even if I could coerce SANN to
> only return discrete integer values for each step in the optimization
> once x[1] was set to say 2 I would have to search the other
> "variables" for a value of 2 and exchange x[1] and which ever
> variable was two so as to maintain the property that each variable
> has a unique discrete value constained from 1 : number of varables.
> 
> Thank you.
> 
> Kevin

  If you look more closely at the docs for method="SANN" (and
the examples), you'll see that SANN allows you to pass the
"gradient" argument (gr) as a custom function to provide the
candidate distribution.  Here's an example:

N <- 10
xvec <- seq(0,1,length=N)
target <- rank((xvec-0.2)^2)

objfun <- function(x) {
  sum((x-target)^2)/1e6
}

objfun(1:100)

swapfun <- function(x,N=10) {
  loc <- sample(N,size=2,replace=FALSE)
  tmp <- x[loc[1]]
  x[loc[1]] <- x[loc[2]]
  x[loc[2]] <- tmp
  x
}

set.seed(1001)
opt1 <- optim(fn=objfun,
              par=1:N,
              gr=swapfun,method="SANN",
              control=list(trace=10))

plot(opt1$par,target)



> ---- Ben Bolker <bolker at ufl.edu> wrote:
>> 
>> 
>> rkevinburton wrote:
>>> I have an optimization question that I was hoping to get some
>>> suggestions on how best to go about sovling it. I would think
>>> there is probably a package that addresses this problem.
>>> 
>>> This is an ordering optimzation problem. Best to describe it with
>>> a simple example. Say I have 100 "bins" each with a ball in it
>>> numbered from 1 to 100. Each bin can only hold one ball. This
>>> optimization is that I have a function 'f' that this array of
>>> bins and returns a number. The number returned from
>>> f(1,2,3,4....) would return a different number from that of 
>>> f(2,1,3,4....). The optimization is finding the optimum order of
>>> these balls so as to produce a minimum value from 'f'.I cannot
>>> use the regular 'optim' algorithms because a) the values are
>>> discrete, and b) the values are dependent ie. when the "variable"
>>> representing the bin location is changed (in this example a new
>>> ball is put there) the existing ball will need to be moved to
>>> another bin (probably swapping positions), and c) each "variable"
>>> is constrained, in the example above the only allowable values 
>>> are integers from 1-100. So the problem becomes finding the
>>> optimum order of the "balls".
>>> 
>>> Any suggestions?
>>> 
>>> 
>> See method "SANN" under ?optim.
>> 
>> Ben Bolker
>> 
>> -- View this message in context:
>> http://www.nabble.com/Constrined-dependent-optimization.-tp22772520p22772795.html
>>  Sent from the R help mailing list archive at Nabble.com.
>> 
>> ______________________________________________ R-help at 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.
> 


-- 
Ben Bolker
Associate professor, Biology Dep't, Univ. of Florida
bolker at ufl.edu / www.zoology.ufl.edu/bolker
GPG key: www.zoology.ufl.edu/bolker/benbolker-publickey.asc

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 260 bytes
Desc: OpenPGP digital signature
URL: <https://stat.ethz.ch/pipermail/r-help/attachments/20090330/ab2f6fd3/attachment-0003.bin>