Recasting Deterministic Annealing as Constrained Optimization

Several parallel analogue algorithms, based upon mean field theory approximations to an underlying statistical mechanics formulation, now exist for finding approximate solutions to difficult combinatorial optimisation problems such as the Travelling Salesman (TSP). These methods have also found application in such areas as speech and vision processing, as well as in adaptive learning and clustering algorithms. However, they all suffer from the substantial drawback of requiring an externally imposed “annealing” schedule similar to that used in simulated annealing. I show in this paper that any given “deterministic” (or “mean field theory”) annealing algorithm can be combined in an extremely natural way with notions from the areas of constrained optimisation (Lagrange multipliers) and adaptive simulated annealing to yield a single homogeneous and parallel relaxation technique for optimisation. In particular, an externally prescribed annealing schedule is no longer required, which gives rise to somewhat more efficient procedures. The results of numerical simulations on 50-city TSP problems are presented, which show that the ensuing algorithms are typically an order of magnitude faster than the mean field algorithms alone. An analysis of the methods is presented which shows how their efficiency arises, and which also displays a mechanism allowing some unwanted local minima in the mean field theory methods to be avoided, thus leading, on occasion, to {\it qualitatively} superior solutions as well. This behavior is illustrated by the ability of the new algorithms to locate a higher quality solution than deterministic annealing for a well-known 100-city instance of the TSP.