On the Problem Characteristics of Multi-objective Pseudo-Boolean Functions in Runtime Analysis - review and new test functions

Aug 23, 2026

Upload by Aurora

Runtime analysis provides theoretical tools for understanding multi-objective evolutionary algorithms (MOEAs), but commonly used benchmark functions in this area are dominated by highly artificial pseudo-Boolean constructions. The text reviews standard multi-objective functions, clarifies how their features and limitations influence theoretical results and practical algorithm design, and explains why linear Pareto fronts and fully conflicting objectives can misrepresent realism. New functions are introduced by mixing classical single-objective components, creating heterogenous objectives, local optimality, and nonlinear Pareto fronts to enrich test suites and strengthen theory–practice connections.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages20

Reading Time50 min

AccessFree to download

Introduction

Runtime analysis for MOEAs

Limitations of artificial benchmark functions

Problem characteristics in multi-objective pseudo-Boolean functions

Artificial vs. realistic objective trade-offs

Pareto front linearity and algorithm bias

Review and new benchmark functions

Mixing single-objective components into multi-objective tests

Implications for theory and practical algorithm development

On the Problem Characteristics of Multi-objective Pseudo-Boolean Functions in Runtime Analysis Zimin Liang and Miqing Li∗ arXiv :2503 . 19 166v2 [ cs .NE] 8 Jul 2025 Abstract—Recently, there has been growing interest within the theoretical community in analytically studying multi-objective evolutionary algorithms. This runtime analysis-focused research can help formally understand algorithm behaviour, explain empirical observations, and provide theoretical insights to support algorithm development and exploration. However, the test problems commonly used in the theoretical analysis are predominantly limited to problems with heavy “artificial” characteristics (e.g., symmetric, homogeneous objectives and linear Pareto fronts), which may not be able to well represent realistic scenarios. In this paper, we first discuss commonly used multi-objective functions in the theory domain and systematically review their features, limitations and implications to practical use. Then, we present several new functions with more realistic features, such as heterogenous objectives, local optimality and nonlinearity of the Pareto front, through simply mixing and matching classical single-objective functions in the area (e.g., LeadingOnes, Jump and RoyalRoad). We hope these functions can enrich the existing test problem suites, and strengthen the connection between theoretic and practical research. Index Terms—Multi-objective optimisation, evolutionary computation, runtime analysis, pseudo Boolean functions. I. INTRODUCTION Many real-world challenges contain multiple conflicting objectives to be optimised simultaneously, known as multiobjective optimisation problems (MOPs) . Instead of a single optimal solution, MOPs yield a set of solutions called Pareto optimal solutions, each representing a distinct trade-off between the objectives. Multi-objective evolutionary algorithms (MOEAs) have demonstrated their ability to deal with MOPsin a variety of practical scenarios. Yet, the theoretical understanding of MOEAs, particularly their behaviours and performance guarantees, lags behind their practical success [1], [2] . In this regard, runtime analysis [2] emerges as a very useful tool. First, it can be used to theoretically analyse the expected runtime of MOEAs, including mainstream algorithms like NSGA-II [3], [4], [5], SPEA2 [6], SMS-EMOA [7], [8],[9], MOEA/D [10], [11], [12] and NSGA-III [13], as well as simple heuristics like SEMO [14], [15], [16] and G-SEMO [17], [18], [19] . Second, runtime analysis can help confirm observations reported from empirical studies, for example, why NSGA-II is less effective for problems with three or more objectives [20] . Third, runtime analysis can provide insight and guidance in algorithm design (e.g., the use of crossover [19], adaptive mutation [21] and the archive [22]), as well as in algorithmic parameter setup (e.g., mutation rate setting [23]) . Zimin Liang and Miqing Li (corresponding author) are with the School of Computer Science, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK (emails: [zxl525@student.bham.ac.uk](zxl525@student.bham.ac.uk); [m.li.8@bham.ac.uk](m.li.8@bham.ac.uk)) . Lastly, it can even be used to challenge conventional practice in the empirical community and guides the development of different mechanisms, for example introducing randomness in population update of MOEAs [24], [25] . Yet, multi-objective benchmark functions used in runtime analysis are predominantly limited to pseudo-Boolean ones with heavy “artificial” characteristics. They may not be able to well represent realistic scenarios. For example, in OneMinMax [15], a commonly used benchmark, any point in the decision space is a Pareto optimal solution. That means the two objectives are completely conflicting, with no configuration improving both objectives or yielding dominated solutions. This is apparently not very realistic. Another prominent feature in multi-objective pseudoBoolean functions is

FAQs

Why is runtime analysis important for multi-objective evolutionary algorithms?

It enables theoretical analysis of expected runtimes, helps validate empirical observations, and offers guidance for algorithm design choices such as crossover, adaptive mutation, archives, and parameter settings like mutation rate.

What limitations do commonly used multi-objective pseudo-Boolean benchmark functions have?

They often rely on heavy artificial characteristics, including symmetric or homogeneous objectives and linear Pareto fronts, which may not represent realistic scenarios or fair comparisons across MOEAs.

How do the paper’s newly proposed test functions aim to improve benchmarks?

They are built by mixing and matching classical single-objective functions to produce more realistic features such as heterogeneous objectives, local optimality, and nonlinear Pareto front shapes, thereby enriching existing test suites.

Aug 23, 2026

Upload by Aurora