Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax
The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark problem OneMinMax, for which all solutions are Pareto-optimal. We provide a rigorous runtime analysis of the last step of the optimization, when the algorithm starts with a population with a second-best diversity, and prove that it finds a population with optimal diversity in expected time $O(n^2)$, when the problem size $n$ is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversitySimilar Papers 제목 키워드 기반
Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem
The diversity optimization is the class of optimization problems, in which we aim at finding a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms…
DiversityEvolutionary AlgorithmsAnalysing the Robustness of NSGA-II under Noise
Runtime analysis has produced many results on the efficiency of simple evolutionary algorithms like the (1+1) EA, and its analogue called GSEMO in evolutionary multiobjective optimisation (EMO). Recently, the first runti…
Evolutionary AlgorithmsSliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions
Variants of the GSEMO algorithm using multi-objective formulations have been successfully analyzed and applied to optimize chance-constrained submodular functions. However, due to the effect of the increasing population …
Evolutionary AlgorithmsIllustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis
Runtime analysis has recently been applied to popular evolutionary multi-objective (EMO) algorithms like NSGA-II in order to establish a rigorous theoretical foundation. However, most analyses showed that these algorithm…
DiversityTowards Self-adaptive Mutation in Evolutionary Multi-Objective Algorithms
Parameter control has succeeded in accelerating the convergence process of evolutionary algorithms. While empirical and theoretical studies have shed light on the behavior of algorithms for single-objective optimization,…
BenchmarkingEvolutionary Algorithms