Finding Least-Cost Proofs with Population-Oriented Simulated Annealing
Ashraf M. Abdelbar, Heba A. Amer · ASME Press eBooks · 2006
Cost-based abduction (CBA) is an important problem in reasoning under uncertainty. In CBA, evidence to be explained is treated as a goal to be proven, proofs have costs based on how much needs to be assumed to complete the proof, and the set of assumptions needed to complete the least-cost proof are taken as the best explanation for the given evidence. Guided evolutionary simulated annealing (GESA) is a population-oriented simulated annealing (POSA) technique in which the amount of processing allocated to each SA process depends on the performance of that process. In previous work, we applied GESA to a suite of small CBA instances. In this paper, we present two contributions: a more accurate fitness function based on a heuristic repair technique, and an analysis of the run-length distribution (RLD) of GESA using a CBA instance that is specifically generated to be difficult.