Multi-objective Pseudo Boolean Functions in Runtime Analysis: A Review
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 objectives and linear Pareto fronts), which may not be able to well represent realistic scenarios. In this paper, we survey commonly used multi-objective functions in the theory domain and systematically review their features, limitations and implications to practical use. Moreover, we present several new functions with more realistic features, such as 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Merging variables: one technique of search in pseudo-Boolean optimization
In the present paper we describe new heuristic technique, which can be applied to the optimization of pseudo-Boolean functions including Black-Box functions. This technique is based on a simple procedure which consists i…
Runtime Analysis of Evolutionary Algorithms for Multiparty Multiobjective Optimization
In scenarios where multiple decision-makers operate within a common decision space, each focusing on their own multi-objective optimization problem (e.g., bargaining games), the problem can be modeled as a multi-party mu…
Evolutionary AlgorithmsMultiobjective OptimizationEfficient Hill-Climber for Multi-Objective Pseudo-Boolean Optimization
Local search algorithms and iterated local search algorithms are a basic technique. Local search can be a stand along search methods, but it can also be hybridized with evolutionary algorithms. Recently, it has been show…
Evolutionary AlgorithmsRuntime Analysis for Permutation-based Evolutionary Algorithms
While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permut…
Evolutionary AlgorithmsGeneralized Totalizer Encoding for Pseudo-Boolean Constraints
Pseudo-Boolean constraints, also known as 0-1 Integer Linear Constraints, are used to model many real-world problems. A common approach to solve these constraints is to encode them into a SAT formula. The runtime of the …
ARC