Empirical Comparison between MOEAs and Local Search on Multi-Objective Combinatorial Optimisation Problems

Abstract

Local search has gained its popularity in addressing multi-objective combinatorial optimisation problems (MOCOPs) within the communities of evolutionary computation and operational research. The ease of defining the neighbourhood in discrete spaces of MOCOPs makes local search well-suited to conducting step-wise moves. On the other side, evolutionary algorithms are amongst very first choices in solving various multi-objective optimisation problems. Although most multi-objective evolutionary algorithms (MOEAs) are developed, tested and studied on the basis of continuous problems, when encountering a practical MOCOP, practitioners tend to resort to popular MOEAs. Therefore, a relevant question is that between MOEAs and local search heuristics, which one may be more suitable for MOCOPs. In this paper, we attempt to answer this question. We choose seven well-known "baseline" MOEAs and local search heuristics in the area and systematically study their behaviours on four MOCOPs. We find that, unsurprisingly, different search paradigms have their own sweet spots; it depends on problem types, problem settings and search budgets. However, surprisingly, there exists one search heuristic, SEMO, which can be seen as a "transition" between the two search paradigms (i.e., a simple MOEA or randomised local search), that performs consistently better than the other heuristics across all the settings.