Incollection,
Optimization by Simulated Annealing from the Viewpoint of Glassy Dynamics
Abstract Book of the XXIII IUPAP International Conference on Statistical Physics, Genova, Italy, (9-13 July 2007)
Abstract
The optimization characteristics of finite-time simulated annealing are investigated by focusing on the relaxation properties of search dynamics. Three kinds of experiments are performed on the random Euclidean traveling salesman problem with 2-opt neighborhood structure. First, the idea of effective ergodic convergence is applied to the design of an adaptive cooling schedule and optimization performance of the resulting search algorithm is investigated under various parameter conditions. Second, a mapping-onto-minima method is used for the evaluation of local search performance of the Metropolis algorithm; there, the relaxation dynamics is observed as a transition process from basin to basin on the rugged landscape of the cost function. Finally, rate-cycling experiments are introduced and performed systematically; in these experiments, the cooling rate is changed cyclically so that the search in a specified temperature range is controlled on a fixed observation time scale. A series of experiments detects an influential temperature to the effective relaxation dynamics and the resulting good performance. This temperature is understood to be determined not from the temperature dependence of the specific heat used to identify crystallization but from that of the Deborah number used to identify glass transition.
