Landscape Analysis for Hyperheuristic Bayesian Network Structure Learning on Unseen Problems

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.