Knowledge Transfer Genetic Programming With Auxiliary Population for Solving Uncertain Capacitated Arc Routing Problem
针对不确定容量弧路径问题，提出一种带辅助种群的知识迁移遗传规划方法，通过迁移知识初始化并协同进化辅助种群，显著提升最终性能和收敛速度。
The uncertain capacitated arc routing problem (UCARP) is an NP-hard combinatorial optimization problem with a wide range of applications in logistics domains. Genetic programming (GP) hyper-heuristic has been successfully applied to evolve routing policies to effectively handle the uncertain environment in this problem. The real world usually encounters different but related instances due to events, such as season change and vehicle breakdowns, and it is desirable to transfer knowledge gained from solving one instance to help solve another related one. However, the solutions found by the GP process can lack diversity, and the existing methods use the transferred knowledge mainly during initialization. Thus, they cannot sufficiently handle the change from the source to the target instance. To address this issue, we develop a novel knowledge transfer GP with an auxiliary population. In addition to the main population for the target instance, we initialize an auxiliary population using the transferred knowledge and evolve it alongside the main population. We develop a novel scheme to carefully exchange the knowledge between the two populations, and a surrogate model to evaluate the auxiliary population efficiently. The experimental results confirm that the proposed method performed significantly better than the state-of-the-art GP approaches for a wide range of uncertain arc routing instances, in terms of both final performance and convergence speed.