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