Multi-objective Discrete Combinatorial Optimization Algorithm Combining Problem-Decomposition and Adaptive Large Neighborhood Search

Abstract

In order to efficiently obtain solutions for large-scale multi-objective optimization problems in reality, to achieve a balance among convergence, diversity, and uniformity has gradually become one of the important goals in multi-objective optimization. This paper proposes a multi-objective discrete combinatorial optimization algorithm combining problem-decomposition and adaptive large neighborhood search (MOALNS) for complex multi-objective discrete combinatorial optimization problems. The algorithm introduces large neighborhood search strategies and adaptive adjustment mechanisms for the optimization process of each sub-problem based on problem decomposition, forming a new set of convergence-guiding criteria to break through optimization barriers and achieve a balance between global and local search in the process of searching the multi-dimensional solution space for each sub-problem. In addition, this paper proposes that configuring independent operator integration libraries for each sub-problem can effectively adjust the optimization direction of each sub-problem, solving the problem of solution direction deviation caused by different objective weights, and thus achieving a more efficient and stable multi-objective optimization process. Numerical experiments demonstrate that the proposed new multi-objective discrete combinatorial optimization algorithm exhibits good performance in terms of convergence, diversity, uniformity, and extensibility in multiple sets of standard benchmark test cases and case studies, and holds advantages compared with other classical multi-objective optimization algorithms.

Keywords

• multi-objective discrete combinatorial optimization; problem decomposition; large neighborhood search; adaptive mechanism