Using ACCESSIBILITY to assess the performance of generalized hill climbing algorithms

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.