Statistical Mechanics: a General Approach to Combinatorial Optimization
- 168 Downloads
The aim of this work was to investigate the possibility of using statistical mechanics as an alternative framework to study complex combinatorial optimization problems. This deep connection, suggested in ref.  by analogy with the annealing of a solid, allows to design a searching procedure which generates a sequence of admissible solutions. This sequence may be viewed as the random evolution of a physical system in contact with a heat-bath. As the temperature is lowered, the solutions approach the optimal solution in such a way that a well organized structure is brought out of a very large number of unpredictable outcomes. To speed up the convergence of this process, we propose a selecting procedure which favours the choice of neighbouring trial solutions. This improved version of the simulated annealing is illustrated by two examples: the N-city Travelling Salesman Problem  and the Minimum Perfect Euclidean Matching Problem .
Unable to display preview. Download preview PDF.