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

Do not remove: This comment is monitored to verify that the site is working properly