A Multi-Objective Genetic Programming Algorithm With α Dominance and Archive for Uncertain Capacitated Arc Routing Problem
针对不确定容量弧路径问题，提出一种多目标遗传规划算法，利用α支配策略和存档机制，同时优化路由策略的有效性和简洁性，实验表明优于现有算法。
The uncertain capacitated arc routing problem (UCARP) is an important combinatorial optimization problem with many applications in the real world. Genetic programming hyper-heuristic has been successfully used to automatically evolve routing policies, which can make real-time routing decisions for UCARPs. It is desired to evolve routing policies that are both effective and small/simple to be easily understood. The effectiveness and size are two potentially conflicting objectives. A further challenge is the objective selection bias issue, i.e., it is much more likely to obtain small but ineffective routing policies than the effective ones that are typically large. In this article, we propose a new multiobjective genetic programming algorithm to evolve effective and small routing policies. The new algorithm employs the α dominance strategy with a newly proposed α adaptation scheme to address the objective selection bias issue. In addition, it contains a new archive strategy to prevent the loss of promising individuals due to the rotation of training instances. The experimental results showed that the newly proposed algorithm can evolve significantly better routing policies than the current state-of-the-art algorithms for UCARP in terms of both effectiveness and size. We have also analyzed the evolved routing policies to show better interpretability.