Finite-time performance analysis of static simulated annealing algorithms

Jeffrey E. Orosz, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

Generalized climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Current theoretical results are based on the assumption that the goal when addressing such problems is to find a globally optimal solution. However, from a practical point of view, solutions that are close enough to a globally optimal solution (where close enough is measured in terms of the objective function value) for a discrete optimization problem may be acceptable. This paper introduces β-acceptable solutions, where β is a value greater than or equal to the globally optimal objective function value. Moreover, measures for assessing the finite-time performance of GHC algorithms, in terms of identifying β-acceptable solutions, are defined. A variation of simulated annealing (SA), termed static simulated annealing (S2A), is analyzed using these measures. S2A uses a fixed cooling schedule during the algorithm's execution. Though S2A is provably noncovergent, its finite-time performance can be assessed using the finite-time performance measures defined in terms of identifying β-acceptable solutions. Computational results with a randomly generated instance of the traveling salesman problem are reported to illustrate the results presented. These results show that upper and lower estimates for the number of iterations to reach a β-acceptable solution within a specified number of iterations can be obtained, and that these estimates are most accurate for moderate and high fixed temperature values for the S2A algorithm.

Original languageEnglish (US)
Article number390815
Pages (from-to)21-53
Number of pages33
JournalComputational Optimization and Applications
Volume21
Issue number1
DOIs
StatePublished - 2002

Keywords

  • Cooling schedules
  • Finite-time performance
  • Local search algorithms
  • Simulated annealing

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Finite-time performance analysis of static simulated annealing algorithms'. Together they form a unique fingerprint.

Cite this