A stopping criterion for logarithmic simulated annealing


Albrecht, A. 2006. A stopping criterion for logarithmic simulated annealing. Computing. 78 (1), pp. 55-79. https://doi.org/10.1007/s00607-006-0167-1
TitleA stopping criterion for logarithmic simulated annealing
AuthorsAlbrecht, A.

We perform a convergence analysis of simulated annealing-based search for the special case of logarithmic cooling schedules. Emphasis is put on the impact of structural parameters of the underlying configuration space on the number of transitions k≥L that is sufficient to achieve a certain probability (confidence 1−δ) of being in an optimum configuration. Since such a lower bound L of the transition number depends on some constants that are difficult to calculate, we evaluate a much simplified version L'≪L of the lower bound for the problem of finding short conjunctions representing a ``positive'' Boolean vector and rejecting a set of ``negative'' Boolean vectors. The evaluation is based on computational experiments where the frequency of occurrences of configurations is calculated for simulated annealing-based search that terminates after L' transitions. The experiments produce a good correspondence between frequencies of minimum configurations and the required confidence 1−δ, i.e., our study provides empirical evidence that the relation of basic parameters in the lower bound L, if calculated for small constants assigned to the parameters and thus resulting in L', can be used as a termination criterion in simulated annealing-based search.

PublisherSpringer Verlag
Publication dates
PrintAug 2006
Publication process dates
Deposited08 Nov 2013
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1007/s00607-006-0167-1
Permalink -


  • 12
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as