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

