Towards explaining metaheuristic solution quality by data mining surrogate fitness models for importance of variables

Citation

Wallace A, Brownlee AEI & Cairns D (2021) Towards explaining metaheuristic solution quality by data mining surrogate fitness models for importance of variables. In: Bramer M & Ellis R (eds.) Artificial Intelligence XXXVIII. Lecture Notes in Computer Science, 13101. 41st SGAI International Conference on Artificial Intelligence, AI 2021, Cambridge, 14.12.2021-16.12.2021. Cham, Switzerland: Springer, pp. 58-72. https://doi.org/10.1007/978-3-030-91100-3_5

Abstract
Metaheuristics are randomised search algorithms that are effective at finding "good enough" solutions to optimisation problems. However, they present no justification for generated solutions and these solutions are non-trivial to analyse in most cases. We propose that identifying the combinations of variables that strongly influence solution quality, and the nature of this relationship, represents a step towards explaining the choices made by a metaheuristic. Using three benchmark problems, we present an approach to mining this information by using a "surrogate fitness function" within a metaheuristic. For each problem, rankings of the importance of each variable with respect to fitness are determined through sampling of the surrogate model. We show that two of the three surrogate models tested were able to generate variable rank-ings that agree with our understanding of variable importance rankings within the three common binary benchmark problems trialled.

Keywords
Metaheuristics; Surrogates; Optimisation; Explainability

People

Dr Sandy Brownlee

Senior Lecturer in Computing Science, Computing Science and Mathematics - Division

Dr David Cairns

Lecturer, Computing Science

Mr Aidan Wallace

Tutor, Computing Science