Shaolin Wang Wins the ECOM Track Best Paper Award at GECCO 2022

Congratulations to Shaolin Wang for winning the ECOM track Best Paper Award at the ACM Genetic and Evolutionary Computation Conference (GECCO) 2022 for their paper “Local Ranking Explanation for Genetic Programming Evolved Routing Policies for Uncertain Capacitated Arc Routing Problems”.

Abstract

The Uncertain Capacitated Arc Routing Problem (UCARP) is a well-known combinatorial optimisation problem that has many real-world applications. Genetic Programming is usually utilised to handle UCARP by evolving effective routing policies, which can respond to the uncertain environment in real-time. Previous studies mainly focus on the effectiveness of the routing policies but ignore the interpretability. In this paper, we focus on post-hoc interpretability, which explains a pre-trained complex routing policy. Unlike the existing explanation methods for classification/regression models, the behaviour of a routing policy is characterised as a ranking process rather than predicting a single output. To address this issue, this paper proposes a Local Ranking Explanation (LRE) method for GP-evolved routing policies for UCARP. Given a UCARP decision situation, LRE trains a linear model that gives the same ranks of the candidate tasks as those of the explained routing policy. The experimental results demonstrate that LRE can obtain more interpretable linear models that have highly correlated and consistent behaviours with the original routing policy in most decision situations. By analysing coefficients and attribute importance of the linear model, we managed to provide a local explanation of the original routing policy in a decision situation.