Statistical mechanics of combinatorial optimization

Abstract

A theoretical criterion is offered for the design of a temperature schedule for simulated annealing. It is based on a measure of distance in probability space. Implementation requires a knowledge of the heat capacity and the relaxation time. A method of calculating these quantities for a combinatorial problem is outlined. The theoretical structure involved seems to point to an information-theoretic measure of computational effort in certain probabilistic algorithms. DOI: http://dx.doi.org/10.1103/PhysRevA.37.1351 © 1988 The American Physical Society