TY - JOUR
T1 - Global optimization performance measures for generalized hill climbing algorithms
AU - Jacobson, Sheldon H.
AU - Yücesan, Enver
N1 - Funding Information:
This research has been supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007) and the National Science Foundation (DMI-9907980). The authors would like to thank the editor, Professor P.M. Pardalos, and two anonymous referees for their helpful comments and feedback on the paper that has resulted in a significantly improved manuscript.
PY - 2004/6
Y1 - 2004/6
N2 - Generalized hill climbing algorithms provide a framework for modeling several local search algorithms for hard discrete optimization problems. This paper introduces and analyzes generalized hill climbing algorithm performance measures that reflect how effectively an algorithm has performed to date in visiting a global optimum and how effectively an algorithm may perform in the future in visiting such a solution. These measures are also used to obtain a necessary asymptotic convergence (in probability) condition to a global optimum, which is then used to show that a common formulation of threshold accepting does not converge. These measures assume particularly simple forms when applied to specific search strategies such as Monte Carlo search and threshold accepting.
AB - Generalized hill climbing algorithms provide a framework for modeling several local search algorithms for hard discrete optimization problems. This paper introduces and analyzes generalized hill climbing algorithm performance measures that reflect how effectively an algorithm has performed to date in visiting a global optimum and how effectively an algorithm may perform in the future in visiting such a solution. These measures are also used to obtain a necessary asymptotic convergence (in probability) condition to a global optimum, which is then used to show that a common formulation of threshold accepting does not converge. These measures assume particularly simple forms when applied to specific search strategies such as Monte Carlo search and threshold accepting.
KW - Convergence
KW - Finite-time performance
KW - Hill climbing
KW - Local search algorithms
UR - http://www.scopus.com/inward/record.url?scp=3142748715&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=3142748715&partnerID=8YFLogxK
U2 - 10.1023/B:JOGO.0000042111.72036.11
DO - 10.1023/B:JOGO.0000042111.72036.11
M3 - Article
AN - SCOPUS:3142748715
VL - 29
SP - 173
EP - 190
JO - Journal of Global Optimization
JF - Journal of Global Optimization
SN - 0925-5001
IS - 2
ER -