A Simple Combination of Local Search and MOEAD for Combinatorial Multi-objective Optimization

In this work, we address multi-objective combinatorial optimization problems, which require managing the discrete nature of the search space while simultaneously optimizing the conflicting objective functions. Local search is widely recognized as a cornerstone in the development of advanced algorithms for discrete search spaces, while evolutionary paradigms such as decomposition, dominance-based methods, and indicator-based approaches are often employed to tackle the multi-objective nature of these problems. We consider a simple combination of iterated local search with the well-established MOEA/D approach — where single-objective subproblems are generated via objective aggregation. This approach is compared to a simple evolutionary algorithm and its superiority demonstrated on a broad range of challenging binary MNK-landscapes used as benchmarks.