Applying Guided Evolutionary Simulated Annealing to cost-based abduction

Guided Evolutionary Simulated Annealing (GESA) is a parallel simulated annealing (SA) technique that is based on competition among a population of independent SA chains. In each chain, each current state, called the parent state, iteratively, generates a number of child states using a domain-dependent neighborhood operator. The most fit child is deterministically determined, and then is allowed to replace the parent with a logistic probability. The number of child states that each parent is allowed to generate in each iteration is dependent on the quality of the solutions produced by this chain in the past. We show how this technique can be applied to cost-based abduction (CBA), an important AI formalism for representing knowledge under uncertainty. Performance is evaluated using a suite of 50 randomly generated CBA instances, containing 50 hypotheses and 70 rules.