Part of Advances in Neural Information Processing Systems 1 (NIPS 1988)
Griff Bilbro, Reinhold Mann, Thomas Miller, Wesley Snyder, David van den Bout, Mark White
Nearly optimal solutions to many combinatorial problems can be found using stochastic simulated annealing. This paper extends the concept of simulated annealing from its original formulation as a Markov process to a new formulation based on mean field theory. Mean field annealing essentially replaces the discrete de(cid:173) grees of freedom in simulated annealing with their average values as computed by the mean field approximation. The net result is that equilibrium at a given temperature is achieved 1-2 orders of magnitude faster than with simulated annealing. A general frame(cid:173) work for the mean field annealing algorithm is derived, and its re(cid:173) lationship to Hopfield networks is shown. The behavior of MFA is examined both analytically and experimentally for a generic combi(cid:173) natorial optimization problem: graph bipartitioning. This analysis indicates the presence of critical temperatures which could be im(cid:173) portant in improving the performance of neural networks.
STOCHASTIC VERSUS MEAN FIELD
In combinatorial optimization problems, an objective function or Hamiltonian, H(s), is presented which depends on a vector of interacting 3pim, S = {81," .,8N}, in some complex nonlinear way. Stochastic simulated annealing (SSA) (S. Kirk(cid:173) patrick, C. Gelatt, and M. Vecchi (1983)) finds a global minimum of H by com(cid:173) bining gradient descent with a random process. This combination allows, under certain conditions, choices of s which actually increa3e H, thus providing SSA with a mechanism for escaping from local minima. The frequency and severity of these uphill moves is reduced by slowly decreasing a parameter T (often referred to as the temperature) such that the system settles into a global optimum.
Two conceptual operationo; are involved in simulated annealing: a thermodatic op(cid:173) eration which schedules decreases in the temperature, and a relazation operation
92