Explainability of non-deterministic solvers: explanatory feature generation from the data mining of the search trajectories of population-based metaheuristics.

Fyvie, Martin

Abstract

Evolutionary algorithms (EAs) are the principal focus of research study in Evolutionary Computing (EC). In EC, naturally occurring processes designed to drive success in nature are simulated for a similar purpose in numerical optimisation. Such processes include natural selection, genetic mutation and breeding of parents to pass on beneficial traits. EAs are a family of algorithms that utilise this diverse set of processes to navigate an optimisation problem's landscape using generations of solutions that evolve. This diverse set of processes often leads EAs to be considered "Black-Box" in that, due to the stochastic nature of their internal operators, generating an understanding of the reasoning behind EA decisions can be difficult. In optimisation and artificial intelligence (AI), the field of explainable AI (XAI) has grown significantly as machine learning, systems that mimic human reasoning and other AI systems have continued to be adopted into more and more user-critical applications. XAI as a research area aims, among many things, to aid in gaining a better understanding of these decision-making processes. EAs are often employed as mechanisms within explanation generation techniques such as counterfactual and fuzzy-rule refinement and were, until recently, rarely the focus of study for XAI. While there is no single mathematical theory that extends to all EAs, one commonality that extends to all population-based EAs is their generation of successive populations of solutions. These generations of solutions represent the EA's understanding of the optimisation problem at each specific point in the search and collectively represent the search trajectory of the algorithm. This thesis aims to expand on current research in the field of XAI by introducing a set of novel XAI methodologies designed specifically for use in deriving explanations directly from the search trajectories of EAs. These explanations take the form of geometrically sensitive features detected by the decomposition of the search trajectories using PCA. We show that the PCA decomposition of the search trajectories of EAs retains sufficient structure that geometrically derived features, in this case, vector similarities and component loadings, can identify low-level variable interactions and capture a similar level of information in terms of population diversity as the known method of Kullback-Liebler entropic divergence. With this ability to generate the variance-based subspaces and show that sufficient structure is retained, we are able to extend this approach to additional problem representations – real and nominal - and expand upon the initial techniques. We propose a set of novel XAI trajectory mining techniques designed to identify variable importance and to highlight differing algorithm behaviour on the same problems by highlighting both variables and components that contribute more than others to solution quality improvements at different stages of the search. Finally, we also reflect on the research project, identify areas of possible improvement and set out a range of future work to further expand on that results found in this thesis.

Citation

FYVIE, M. 2024. Explainability of non-deterministic solvers: explanatory feature generation from the data mining of the search trajectories of population-based metaheuristics. Robert Gordon University, PhD thesis. Hosted on OpenAIR [online]. Available from: https://doi.org/10.48526/rgu-wt-2565263

• Thesis Type: Thesis
• Deposit Date: Nov 1, 2024
• Publicly Available Date: Nov 1, 2024
• DOI: https://doi.org/10.48526/rgu-wt-2565263
• Keywords: Explainable artificial intelligence (XAI); Evolutionary computing; Evolutionary algorithms
• Public URL: https://rgu-repository.worktribe.com/output/2565263
• Award Date: May 31, 2024