Explaining Genetic Programming-Evolved Routing Policies for Uncertain Capacitated Arc Routing Problems

—Genetic programming (GP) has been successfully used to evolve routing policies that can make real-time routing decisions for uncertain arc routing problems. Although the evolved routing policies are highly effective, they are typically very large and complex, and hard to be understood and trusted by real users. Existing studies have attempted to improve the interpretability by developing new GP approaches to evolve both effective and interpretable (e.g., with smaller program size) routing policies. However, they still have limitations due to the tradeoff between effectiveness and interpretability. To address this issue, we propose a new post-hoc explanation approach to explaining the effective but complex routing policies evolved by GP. The new approach includes a local ranking explanation and a global explanation module. The local ranking explanation uses particle swarm optimization to learn an interpretable linear model that accurately explains the local behavior of the routing policy for each decision situation. Then, the global explanation module uses a clustering technique to summarize the local explanations into a global explanation. The experimental results and case studies on the benchmark datasets show that the proposed method can obtain accurate and understandable explanations of the routing policies evolved for uncertain arc routing problems. Our explanation approach is not restricted to uncertain arc routing, but has a great potential to be generalized to other optimization and machine learning problems, such as learning classifier systems and reinforcement learning.