Explaining solutions for decision support via Partial Solutions

Abstract

Optimisation problems arise across numerous domains, with metaheuristics being widely adopted due to their flexibility and ease of use. Although the metaheuristic framework is relatively simple, the search process is sufficiently complex that it is effectively a black box. Users are often forced to accept results at face value despite the risks of faulty implementations, non-determinism, and unintended biases. To address these limitations, this research introduces an explainability framework for metaheuristics by extracting human-interpretable insights from generated solutions.

Central to the proposed methodology is the novel concept of Partial Solutions—defined and implemented as part of this work—which represent understandable sub-structures within metaheuristic solutions associated with high fitness. To find these patterns, we use a multi-objective search method that leverages information relating to their complexity, fitness, and structure. The resulting patterns offer trade-offs between objectives, and each can be post-processed into an explanation. To quantify the “structure” of Partial Solutions, we developed two novel linkage learning methods and a new linkage evaluation procedure, which offers a superior trade-off between accuracy and execution time compared with existing methods.

The utility and domain-agnostic nature of this framework are demonstrated and evaluated across several distinct applications. First, the methodology was applied to a complex industrial optimisation problem posed by British Telecom (BT), yielding insightful explanations. Second, the framework was adapted for a recommender system model, successfully generating explanations that satisfy stakeholder objectives. Furthermore, the same underlying methodology was utilised to construct transparent models for predicting solution fitness.

To conclude, Partial Solutions are a flexible tool for explainability. They are shown to recover known patterns within benchmark problems, and to be applicable and insightful in large and complex problems such as British Telecom’s Staff Rostering. Our methodology can also be used beyond metaheuristics; for example, we apply it to a recommender system to produce domain-specific explanations. Finally, Partial Solutions can be used to predict fitness: we show that decision trees based on Partial Solutions are competitive with traditional approaches.

We conclude the thesis with reflections on whether our objectives have been achieved, and possible future work. Partial Solutions may be used to implement efficient and more understandable metaheuristics, and the applicability of the explanations produced may be expanded beyond combinatorial optimisation.