A class of convergent generalized hill climbing algorithms

摘要

Generalized hill climbing (GHC) algorithms have been presented as a modeling framework for local search strategies applied to address intractable discrete optimization (minimization) problems. GHC algorithms include simulated annealing (SA), pure local search (LS), and threshold accepting (TA), among others, as special cases. A particular class of GHC algorithms is designed for discrete optimization problems where the objective function value of a globally optimal solution is known (in this case, the task is to identify an associated optimal solution). This class of GHC algorithms is shown to converge, and six examples are provided that illustrate the diversity of GHC algorithms within this class of convergent algorithms. Implications of these results are discussed.