Zero-temperature scaling and simulated annealing

Abstract
Simulated annealing with a more complicated set of moves than single-spin flips is applied to the one-dimensional Ising spin glass. The explicit connection between the residual entropy at T = 0 in the simulated annealing and the number of metastable states, found previously for single-spin flips, is shown to be also true for these more complicated moves. This result together with a zero-temperature scaling argument is used to derive the degree of improvement that the inclusion of more complicated moves can produce. The results are in accord with the observations made for a number of problems in combinatorial optimization.

Résumé
Nous appliquons la technique du recuit simulé, avec des changements plus compliqués que le recouvrement d'un spin, au verre de spin d'Ising à une dimension. Nous montrons que la relation explicite entre l'entropie résiduelle à T = 0 dans le recuit simulé et le nombre d'états métastables, trouvée précédemment pour le renversement d'un seul spin, reste aussi vraie pour des changements plus compliqués. Combinant ce résultat avec un argument de loi d'échelle à température nulle, nous caractérisons l'amélioration produite par l'inclusion de changements plus compliqués. Ces résultats sont en accord avec des observations faites sur différents problèmes d'optimisation combinatoire.