Mining Potentially Explanatory Patterns via Partial Solutions
GianCarlo Catalano Alexander E. I. Brownlee David Cairns John McCall Russell Ainslie
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.