Does Fairness Help in Multi-Objective Local Search

Local search, a long-established optimisation technique, has recently attracted renewed attention in multi-objective optimisation. It has been successfully applied to a wide range of practical problems and has recently been shown to outperform well-established evolutionary algorithms. Despite these promising results, the search behaviour of different local search methods, particularly when and why one method is better than another, remains poorly understood. In this paper, we provide both empirical and theoretical insights into this question. We show that local search methods that select solutions more fairly (i.e., according to the number of times they have been visited) generally achieve faster search progress, particularly during the early stages of optimisation. We validate these findings using three local search methods with different levels of fairness on a diverse suite of well-studied problems, including the multi-objective knapsack, travelling salesman, resource allocation, NK-landscape, and quadratic assignment problems.