Mining Potentially Explanatory Patterns via Partial Solutions
This work addresses the issue of user confidence and understanding in genetic algorithms for combinatorial optimization, though it appears incremental as it builds on existing explainability methods.
The paper tackles the problem of improving explainability in genetic algorithms for combinatorial optimization by introducing Partial Solutions, which represent beneficial traits from the population to provide user insight and generate new solutions. Experiments on standard benchmarks show that the algorithm finds Partial Solutions that enhance explainability at reasonable computational cost without harming search performance.
Genetic Algorithms have established their capability for solving many complex optimization problems. Even as good solutions are produced, the user's understanding of a problem is not necessarily improved, which can lead to a lack of confidence in the results. To mitigate this issue, explainability aims to give insight to the user by presenting them with the knowledge obtained by the algorithm. In this paper we introduce Partial Solutions in order to improve the explainability of solutions to combinatorial optimization problems. Partial Solutions represent beneficial traits found by analyzing a population, and are presented to the user for explainability, but also provide an explicit model from which new solutions can be generated. We present an algorithm that assembles a collection of Partial Solutions chosen to strike a balance between high fitness, simplicity and atomicity. Experiments with standard benchmarks show that the proposed algorithm is able to find Partial Solutions which improve explainability at reasonable computational cost without affecting search performance.