Title :
Landscape analysis for hyperheuristic Bayesian Network structure learning on unseen problems
Author :
Wu, Yanghui ; McCall, John ; Corne, David ; Regnier-Coudert, Olivier
Author_Institution :
IDEAS Res. Inst., Robert Gordon Univ., Aberdeen, UK
Abstract :
Bayesian network (BN) structure learning is an NP hard problem. Search and score algorithms are one of the main approaches proposed for learning BN structure from data. Previous research has shown that the relative performances of such algorithms are problem dependent and that fitness landscape analysis can be used to characterize the difficulty of the search for different scoring functions. In this paper, we construct a classifier based on fitness landscape analysis and receiver operating characteristic curves. The classifier labels search landscapes with the most suitable scoring function. We train the classifier on a number of standard benchmark functions. The classifier forms the basis for a selective hyperheuristic algorithm. This uses an initial landscape analysis stage to select a scoring function using the classifier. The hyperheuristic algorithm is tested on a distribution of unseen problems based on mutations of the standard benchmarks. Our results establish that the hyperheuristic performs better than a uniformly random scoring function selection approach that omit the landscape analysis stage. Therefore the effects on performance of problem-dependency can be significantly reduced.
Keywords :
belief networks; computational complexity; heuristic programming; learning (artificial intelligence); pattern classification; search problems; sensitivity analysis; BN structure learning; NP hard problem; classifier; fitness landscape analysis; hyperheuristic Bayesian network structure learning; problem-dependency; receiver operating characteristic curves; score algorithm; scoring function; search algorithm; search landscape; selective hyperheuristic algorithm; Algorithm design and analysis; Bayesian methods; Benchmark testing; Classification algorithms; Prediction algorithms; Receivers; Search problems; Receiver Operating Characteristic; bayesian network structure learning; classifier; fitness landscape analysis; hyperheuristic; search-and-score algorithms;
Conference_Titel :
Evolutionary Computation (CEC), 2012 IEEE Congress on
Conference_Location :
Brisbane, QLD
Print_ISBN :
978-1-4673-1510-4
Electronic_ISBN :
978-1-4673-1508-1
DOI :
10.1109/CEC.2012.6252964