Enhanced Evolution of Parallel Algorithm Portfolio for Vehicle Routing Problem via Transfer Optimization

Parallel Algorithm Portfolio (PAP), comprising several component solvers with complementary capabilities, emerges as a cutting-edge computational technique for addressing computationally hard problems. Automatic construction of PAPs can develop high-performance PAPs without human intervention. It is natural to believe that the component solvers share common useful building blocks, thus knowledge transfer among them could be beneficial during the evolution. However, this has been neglected by existing studies. To fill this gap, we propose a transfer optimization framework for automatically co-evolving high-performance PAPs. Specifically, we develop a novel performance-oriented dynamic instance grouping strategy to divide problem instances into groups, each of which is associated with a subpopulation of individuals tasked with evolving a component solver. Additionally, the framework incorporates an adaptive knowledge transfer strategy that automatically identifies when and how to transfer knowledge among instance groups. We conducted extensive experiments on the well-known Vehicle Routing Problem (VRP), a famously challenging NP-hard combinatorial optimization problem. The comprehensive experimental results from three public benchmarks demonstrate that our proposed framework significantly outperforms existing state-of-the-art VRP solvers and automatic PAP construction methods.