Interpretable decision trees to predict solution fitness

Citation

Catalano GAPI, Brownlee AEI, Cairns D & Ainslie R (2025) Interpretable decision trees to predict solution fitness. In: GECCO 2025, Malaga, Spain, 14.07.2025-18.07.2025. Association for Computing Machinery (ACM). https://doi.org/10.1145/1122445.1122456

Abstract
Metaheuristic algorithms are powerful tools for tackling complex optimization problems, but their black-box nature often hinders user trust and understanding. This paper presents a novel methodology for enhancing the explainability of metaheuristics by employing decision trees with splitting criteria based on Partial Solutions. These represent beneficial sub-structures of solutions and provide insights into the problem landscape and solution characteristics. By constructing decision trees that consider the presence or absence of specific patterns in solutions, we produce a transparent model capable of predicting solution fitness. The proposed methodology is evaluated on a diverse set of benchmark problems and metaheuristic algorithms, demonstrating its effectiveness and flexibility as a post-hoc explainability tool. Our results show that our decision trees can match and usually surpass traditional methods in predicting the fitness of candidate solutions for the tested benchmark problems, with one of our methods demonstrating an improvement between 4.4% and 9.3% in í µí± 2 predictive performance for shallower trees trained on a Genetic Algorithm's data. These trees are able to maintain competitive predictive performance while using more interpretable splitting criteria. CCS CONCEPTS • Computing methodologies → Genetic algorithms; • Theory of computation → Models of computation.

Keywords
Genetic Algorithms; Explainable AI (XAI); combinatorial optimiza- tion problems; Decision Trees; Surrogate Fitness Function

Notes
ACM ISBN 978-1-4503-XXXX-X/18/06. . . $15.00

Journal
ACM Computing Surveys