Journal of Frontiers of Computer Science and Technology ›› 2024, Vol. 18 ›› Issue (7): 1762-1775.DOI: 10.3778/j.issn.1673-9418.2306032

• Theory·Algorithm • Previous Articles     Next Articles

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

WEI Qian, JI Bin   

  1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China
  • Online:2024-07-01 Published:2024-06-28

融合分解和自适应邻域的多目标离散组合优化算法

韦倩,季彬   

  1. 中南大学 交通运输工程学院,长沙 410075

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.

Key words: multi-objective discrete combinatorial optimization, problem decomposition, large neighborhood search, adaptive mechanism

摘要: 为了高效获取现实中大规模多目标优化问题解决方案,实现收敛性、多样性和均匀性的平衡逐渐发展为多目标优化的重要目标之一。针对复杂多目标离散组合优化问题,提出了融合分解和自适应邻域的多目标离散组合优化算法(MOALNS)。该算法在问题分解的基础上为各子问题的寻优进程引入大邻域搜索策略与自适应调整机制,形成一套新型的收敛指导准则突破寻优阻力,进而使各子问题在搜索多维解空间的过程中达到全局搜索与局部搜索的平衡。同时,提出为各子问题配置独立算子积分库可有效地调整各子问题的寻优方向,解决由于目标权重不同而造成的求解方向偏差问题,以此实现更为高效、稳定的多目标优化进程。数值实验表明,提出的新型多目标离散组合优化算法在多组标准测试算例与真实案例中均展现出了在收敛性、多样性、均匀性和延展性等方面的良好性能,相较于其他经典多目标优化算法而言更具优势。

关键词: 多目标离散组合优化, 问题分解, 大邻域搜索, 自适应机制