LON/D — Sub-problem Landscape Analysis in Decomposition-Based Multi-objective Optimization

Citation

Liefooghe A, Ochoa G & Verel S (2025) LON/D — Sub-problem Landscape Analysis in Decomposition-Based Multi-objective Optimization. In: Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science. Cham: Springer Nature Switzerland, pp. 133-149. https://doi.org/10.1007/978-3-031-86849-8_9

Abstract
We explore the underlying difficulties of sub-problems arising from decomposition in multi-objective optimization. Decomposition algorithms, such as MOEA/D, split the original multi-objective problem into a set of single-objective sub-problems using a scalarizing function. A weighting coefficient vector defines each sub-problem. We examine the relative difficulty of these sub-problems based on their weight vector and the chosen scalar function—either weighted sum or weighted Tchebycheff. Our approach involves creating a landscape for each sub-problem and analyzing its local optima network (LON). We contribute by jointly visualizing the LONs of sub-problems, defining LON features for decomposition, and examining their interaction with problem properties and their impact on algorithm performance. An extensive experimental analysis of bi-objective NK-landscapes reveals that landscape properties depend not only on the weight vector and scalar function but also on the objectives’ intrinsic difficulty and their degree of conflict. These factors directly affect the relative performance of MOEA/D for each sub-problem. Among the landscape features explored, the size of each sub-problem’s global optimum basin of attraction showed the strongest impact on the performance of decomposition-based multi-objective optimization.

Keywords
Multi-objective combinatorial optimization; Decomposition; MOEA/D; Landscape analysis; Local optima network; pmnk-landscapes

Notes
Best-paper-Award nomination