Solving Multiobjective Combinatorial Optimization via Learning to Improve Method
- 27 February 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Emerging Topics in Computational Intelligence
- Vol. 9 (3) , 2122-2136
Abstract
Recently, neural combinatorial optimization (NCO) methods have been prevailing for solving multiobjective combinatorial optimization problems (MOCOPs). Most NCO methods are based on the “Learning to Construct” (L2C) paradigm, where the trained model(s) can directly generate a set of approximate Pareto optimal solutions. However, these methods still suffer from insufficient proximity and poor diversity towards the true Pareto front. In this paper, following the “Learning to Improve” (L2I) paradigm, we propose weight-related policy network (WRPN), a learning-based improvement method for solving MOCOPs. WRPN is incorporated into multiobjective evolutionary algorithm (MOEA) frameworks to effectively guide the search direction. A shared baseline for proximal policy optimization is presented to reduce variance in model training. A quality enhancement mechanism is designed to further refine the Pareto set during model inference. Computational experiments conducted on two classic MOCOPs, i.e., multiobjective traveling salesman problem and multiobjective vehicle routing problem, indicate that our method achieves remarkable results. Notably, our WRPN module can be easily integrated into various MOEA frameworks such as NSGA-II, MOEA/D and MOGLS, providing versatility and applicability across different problem domains.Keywords
This publication has 30 references indexed in Scilit:
- Deep Policy Dynamic Programming for Vehicle Routing Problems2022
- Learning the travelling salesperson problem requires rethinking generalizationConstraints, 2022
- Reinforcement learning for combinatorial optimization: A surveyComputers & Operations Research, 2021
- Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic2018
- Generation of the exact Pareto set in Multi-Objective Traveling Salesman and Set Covering ProblemsApplied Mathematics and Computation, 2014
- The Multiobjective Traveling Salesman Problem: A Survey and a New Approach2010
- The Hypervolume Indicator Revisited: On the Design of Pareto-compliant Indicators Via Weighted Integration2007
- A Dynasearch Neighborhood for the Bicriteria Traveling Salesman Problem2004
- A survey and annotated bibliography of multiobjective combinatorial optimizationOR Spectrum, 2000
- An efficient implementation of local search algorithms for constrained routing problemsEuropean Journal of Operational Research, 1990