Optimization by Mean Field Annealing

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 degrees offreedom 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 framework forthe mean field annealing algorithm is derived, and its relationship toHopfield networks is shown. The behavior of MFA is examined both analytically and experimentally for a generic combinatorial optimizationproblem: graph bipartitioning. This analysis indicates the presence of critical temperatures which could be important inimproving the performance of neural networks.