Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Engineering
Initialization And Restart In Stochastic Local Search: Computing A Most Probable Explanation In Bayesian Networks, Ole J. Mengshoel, David C. Wilkins, Dan Roth
Initialization And Restart In Stochastic Local Search: Computing A Most Probable Explanation In Bayesian Networks, Ole J. Mengshoel, David C. Wilkins, Dan Roth
Ole J Mengshoel
For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. Two key research questions for stochastic local search algorithms are: Which algorithms are effective for initialization? When should the search process be restarted? In the present work, we investigate these research questions in the context of approximate computation of most probable explanations (MPEs) in Bayesian networks (BNs). We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary …
Constraint Handling Using Tournament Selection: Abductive Inference In Partly Deterministic Bayesian Network, Severino F. Galan, Ole J. Mengshoel
Constraint Handling Using Tournament Selection: Abductive Inference In Partly Deterministic Bayesian Network, Severino F. Galan, Ole J. Mengshoel
Ole J Mengshoel
Constraints occur in many application areas of interest to evolutionary computation. The area considered here is Bayesian networks (BNs), which is a probability-based method for representing and reasoning with uncertain knowledge. This work deals with constraints in BNs and investigates how tournament selection can be adapted to better process such constraints in the context of abductive inference. Abductive inference in BNs consists of finding the most probable explanation given some evidence. Since exact abductive inference is NP-hard, several approximate approaches to this inference task have been developed. One of them applies evolutionary techniques in order to find optimal or close-to-optimal …