Explaining Genetic Programming-Evolved Routing Policies for Uncertain Capacitated Arc Routing Problems
针对遗传规划进化出的复杂路由策略难以理解的问题，提出一种事后解释方法，包含局部排序解释和全局解释模块，实验表明能准确解释策略行为，且可推广到其他优化问题。
Genetic programming 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 genetic programming approaches to evolve both effective and interpretable (e.g., with smaller program size) routing policies. However, they still have limitations due to the trade-off 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 genetic programming. The new approach includes a local ranking explanation and a global explanation module. The local ranking explanation uses particle swarm optimisation to learn an interpretable linear model that accurately explains the local behaviour of the routing policy for each decision situation. Then, the global explanation module uses a clustering technique to summarise 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 generalised to other optimisation and machine learning problems such as learning classifier systems and reinforcement learning.