1. Most of the neighbors of a low cost state, x, may have much higher costs; and 2. The problem is highly degenerate in the sense that there are states, x, with a large (sub) neighborhood of equal cost states, S(x) = fy inside N(x) and f(y) = f(x). In this case, even rejecting all the proposals that would take us out of S, would still give us a significant acceptance rate.
The best way we found to overcome these difficulties is to use a heuristic temperature dependent cost function, designed to accelerate the SA convergence to the global and to avoid premature convergence to locally optimal solutions: I(t)=1/ n* ln(t) where is the maximum objective function differencial in a single move and n is the minimum number of steps needed to connect any two states. Hence, the cooling constant, n can be interpreted as an estimate of how high a mountain we may need to climb in order to reach the optimal position, f(x; u(I))=f(x)+ (1/u(I)) u(x) Initialize parameters u and I , set a random partition, x, and initialize the auxiliary variables W, q, c, r, s, and the cost and penalty functions, f and h; For each proposed move, x->y compute the cost differentials sigma0 = f(y)-f(x) and sigma u=f(y,u)-f(x,u) Accept the move with the Metropolis probability, M(sigmau,I) If the move is accepted, update x, W, q, c, r, s, f and h; After each batch of Metropolis sampling steps, perform a cooling step update (1 + E1) ; (1 + E2) ; 0 < E1 < E2 << 1 : question- what's the best way to put E1 , E2, anyone have an idea? the original text all things related starts on page 111 - http://www.ime.usp.br/~jstern/infcomp/evli.pdf [[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.
