Using ACCESSIBILITY to assess the performance of generalized hill climbing algorithms

Sheldon H. Jacobson, Enver Yucesan

Research output: Contribution to journalConference article

Abstract

The search problem, ACCESSIBILITY, asks whether a finite sequence of events can be found such that, starting with a specific initial event, a particular state can be reached. This problem is intractable, indicating the need for heuristics to address it. One difficulty when applying heuristics to ACCESSIBILITY is assessing a priori their effectiveness, and knowing how to best adjust them to improve performance. This paper introduces the false negative probability as a performance measure for generalized hill climbing algorithms applied to discrete optimization problems, using ACCESSIBILITY as the analysis framework. The false negative probability is also used to obtain necessary convergence conditions. The implications of these results on how GHC algorithms can be effectively applied are discussed.

Original languageEnglish (US)
Pages (from-to)761-768
Number of pages8
JournalWinter Simulation Conference Proceedings
Volume1
StatePublished - Dec 1 1998
Externally publishedYes
EventProceedings of the 1998 Winter Simulation Conference, WSC. Part 1 (of 2) - Washington, DC, USA
Duration: Dec 13 1998Dec 16 1998

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Safety, Risk, Reliability and Quality
  • Chemical Health and Safety
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Using ACCESSIBILITY to assess the performance of generalized hill climbing algorithms'. Together they form a unique fingerprint.

  • Cite this