Optimization by multicanonical annealing and the traveling salesman problem

Abstract

We propose a powerful and general simulated annealing method to study combinatorial optimization problems. It combines the multicanonical method, which samples directly the microcanonical entropy of the system, with an elaborate but straightforward annealing scheme. The information about the local entropy obtained during short Monte Carlo simulations is fully utilized for optimization in an iterative fashion. We present results of an extensive investigation of the traveling salesman problem in a unit square. We estimate the optimal length in the limit of a large number of cities.