Theoretical Analysis of Multi-Objective Evolutionary Algorithms on Integer Spaces with Local Optima

Abstract

Multi-objective evolutionary algorithms (MOEAs) are popular tools for multi-objective optimization (MOO), and have been successfully applied to many real-world MOO problems. However, the theoretical study has lagged behind their practical success and remains largely confined to synthetic pseudo-Boolean functions. To close this gap, this paper--drawing inspiration from a class of popular continuous problems with real-world relevance--introduces a multi-objective benchmark defined on an integer space, featuring an analyzable landscape and the presence of local optima. We conduct a running time analysis on the proposed benchmark and derive several theoretical results. Specifically, we prove that a widely-studied MOEA, GSEMO, using unit-step mutation can be trapped in local optimal regions and fail to identify the Pareto front. Fortunately, we find that this difficulty can be overcome either by incorporating an ageing mechanism or using heavy-tailed mutations that allow multi-valued changes along each dimension of an individual. In addition, we demonstrate the extendability of the proposed benchmark to more complex landscapes with numerous local optima, resembling well-established problems in the field (e.g., those from the ZDT and DTLZ suites). We hope this work is a step forward for the theoretical study of MOEAs on problems that are closely related to those commonly investigated in empirical research.