Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms to address intractable discrete optimization problems. This paper introduces a measure for determining the expected number of iterations to visit a predetermined objective function level, given that an inferior objective function level has been reached in a finite number of iterations. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using this measure. S²A uses a fixed cooling schedule during the algorithm execution. Though S²A is probably nonconvergent, its finite-time performance can be assessed using the finite-time performance measure defined in this paper.