Simulated annealing with Threshold Accepting or Tsallis statistics

• Published in: Computer physics communications 2000-11, Vol.132 (3), p.232-240
• Main Authors: Fachat, André, Hoffmann, Karl Heinz, Franz, Astrid
• Format: Article
• Language: English
• Subjects: Computational techniques; Equilibrium states; Exact sciences and technology; Mathematical methods in physics; Monte carlo and statistical methods; Other topics in statistical physics, thermodynamics, and nonlinear dynamical systems; Physics; Probability theory, stochastic processes, and statistics; Statistical physics, thermodynamics, and nonlinear dynamical systems; Stochastic processes; Threshold Accepting; Tsallis acceptance probability
• ISSN: 0010-4655; 1879-2944
• DOI: 10.1016/S0010-4655(00)00153-3

Threshold Accepting and Tsallis statistics have shown good results when applied to optimization problems. In contrast to the Metropolis acceptance probability these two algorithms do not have detailed balance and also may have broken ergodicity. This makes it impossible to compute the equilibrium distribution analytically for general state spaces and neighborhood relations. In this paper we investigate the equilibrium properties of Threshold Accepting and Tsallis statistics numerically. For simple problems as a ladder of states both algorithms yield exponential functions as equilibrium probability distributions. However, as detailed balance does not hold, the neighborhood relation has an important influence on the resulting probability distribution. This is most obvious in systems with random energy values and random neighborhood structure.