Visible to the public A Two-Stage Genetic Programming Hyper-Heuristic for Uncertain Capacitated Arc Routing Problem

TitleA Two-Stage Genetic Programming Hyper-Heuristic for Uncertain Capacitated Arc Routing Problem
Publication TypeConference Paper
Year of Publication2019
AuthorsWang, S., Mei, Y., Park, J., Zhang, M.
Conference Name2019 IEEE Symposium Series on Computational Intelligence (SSCI)
Date PublishedDec. 2019
ISBN Number978-1-7281-2485-8
Keywordscomplex uncertain capacitated arc routing problem, Complexity theory, effective routing policies, genetic algorithms, GP-evolved routing policies, GPHH, graph theory, Human Behavior, human trust, interpretable routing policies, MOGP, multi-objective., MultiObjective GP, Optimization, poor routing policies, pubcrawl, Robustness, Routing, routing policy, search problems, single-objective GPHH, Sociology, Statistics, Task Analysis, TS-GPHH, two-stage genetic programming hyper-heuristic, Two-Stage GPHH, UCARP, vehicle routing

Genetic Programming Hyper-heuristic (GPHH) has been successfully applied to automatically evolve effective routing policies to solve the complex Uncertain Capacitated Arc Routing Problem (UCARP). However, GPHH typically ignores the interpretability of the evolved routing policies. As a result, GP-evolved routing policies are often very complex and hard to be understood and trusted by human users. In this paper, we aim to improve the interpretability of the GP-evolved routing policies. To this end, we propose a new Multi-Objective GP (MOGP) to optimise the performance and size simultaneously. A major issue here is that the size is much easier to be optimised than the performance, and the search tends to be biased to the small but poor routing policies. To address this issue, we propose a simple yet effective Two-Stage GPHH (TS-GPHH). In the first stage, only the performance is to be optimised. Then, in the second stage, both objectives are considered (using our new MOGP). The experimental results showed that TS-GPHH could obtain much smaller and more interpretable routing policies than the state-of-the-art single-objective GPHH, without deteriorating the performance. Compared with traditional MOGP, TS-GPHH can obtain a much better and more widespread Pareto front.

Citation Keywang_two-stage_2019