research
∙
05/22/2023
The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the m...
share
research
∙
05/17/2023
Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise
In single-objective optimization, it is well known that evolutionary alg...
research
∙
05/08/2023
Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise
Evolutionary algorithms are known to be robust to noise in the evaluatio...
research
∙
04/21/2023
How Well Does the Metropolis Algorithm Cope With Local Optima?
The Metropolis algorithm (MA) is a classic stochastic local search heuri...
research
∙
04/20/2023
How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligenc...
research
∙
03/20/2023
Randomized Rumor Spreading Revisited (Long Version)
We develop a simple and generic method to analyze randomized rumor sprea...
research
∙
03/13/2023
(1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error
Recently it has been proven that simple GP systems can efficiently evolv...
research
∙
02/28/2023
Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables
With apparently all research on estimation-of-distribution algorithms (E...
research
∙
02/24/2023
Lasting Diversity and Superior Runtime Guarantees for the (μ+1) Genetic Algorithm
Most evolutionary algorithms (EAs) used in practice employ crossover. In...
research
∙
02/16/2023
Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
We propose a new method based on discrete Fourier analysis to analyze th...
research
∙
11/23/2022
Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
The NSGA-II is one of the most prominent algorithms to solve multi-objec...
research
∙
11/15/2022
A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most pro...
research
∙
10/07/2022
The (1+(λ,λ)) Global SEMO Algorithm
The (1+(λ,λ)) genetic algorithm is a recently proposed single-objective ...
research
∙
09/28/2022
From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds
Due to the more complicated population dynamics of the NSGA-II, none of ...
research
∙
08/18/2022
The First Mathematical Proof That Crossover Gives Super-Constant Performance Gains For the NSGA-II
Very recently, the first mathematical runtime analyses for the NSGA-II, ...
research
∙
07/05/2022
Runtime Analysis for Permutation-based Evolutionary Algorithms
While the theoretical analysis of evolutionary algorithms (EAs) has made...
research
∙
06/22/2022
General Univariate Estimation-of-Distribution Algorithms
We propose a general formulation of a univariate estimation-of-distribut...
research
∙
06/18/2022
From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms
Estimation-of-distribution algorithms (EDAs) are optimization algorithms...
research
∙
05/07/2022
Automated Algorithm Selection for Radar Network Configuration
The configuration of radar networks is a complex problem that is often p...
research
∙
04/28/2022
A First Runtime Analysis of the NSGA-II on a Multimodal Problem
Very recently, the first mathematical runtime analyses of the multi-obje...
research
∙
04/15/2022
Towards a Stronger Theory for Permutation-based Evolutionary Algorithms
While the theoretical analysis of evolutionary algorithms (EAs) has made...
research
∙
04/05/2022
Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
We prove that Simulated Annealing with an appropriate cooling schedule c...
research
∙
03/05/2022
Better Approximation Guarantees for the NSGA-II by Using the Current Crowding Distance
A recent runtime analysis (Zheng, Liu, Doerr (2022)) has shown that a va...
research
∙
01/28/2022
Stagnation Detection meets Fast Mutation
Two mechanisms have recently been proposed that can significantly speed ...
research
∙
12/16/2021
A First Mathematical Runtime Analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
The non-dominated sorting genetic algorithm II (NSGA-II) is the most int...
research
∙
09/14/2021
Choosing the Right Algorithm With Hints From Complexity Theory
Choosing a suitable algorithm from the myriads of different search heuri...
research
∙
05/07/2021
An Extended Jump Function Benchmark for the Analysis of Randomized Search Heuristics
Jump functions are the most studied non-unimodal benchmark in the theory...
research
∙
04/21/2021
On Negative Dependence Properties of Latin Hypercube Samples and Scrambled Nets
We study the notion of γ-negative dependence of random variables. This n...
research
∙
04/14/2021
Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
Most evolutionary algorithms have multiple parameters and their values d...
research
∙
04/07/2021
Lower Bounds from Fitness Levels Made Easy
One of the first and easy to use techniques for proving run time bounds ...
research
∙
03/29/2021
A Sharp Discrepancy Bound for Jittered Sampling
For m, d ∈ℕ, a jittered sampling point set P having N = m^d points in [0...
research
∙
02/01/2021
Towards Explainable Exploratory Landscape Analysis: Extreme Feature Selection for Classifying BBOB Functions
Facilitated by the recent advances of Machine Learning (ML), the automat...
research
∙
12/14/2020
Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives
Previous theory work on multi-objective evolutionary algorithms consider...
research
∙
07/16/2020
The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univari...
research
∙
06/30/2020
A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
The theory of evolutionary computation for discrete search spaces has ma...
research
∙
06/22/2020
First Steps Towards a Runtime Analysis When Starting With a Good Solution
The mathematical runtime analysis of evolutionary algorithms traditional...
research
∙
06/19/2020
Exploratory Landscape Analysis is Strongly Sensitive to the Sampling Strategy
Exploratory landscape analysis (ELA) supports supervised learning approa...
research
∙
06/08/2020
Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments
We use an elementary argument building on group actions to prove that th...
research
∙
06/05/2020
Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions
It was recently observed that the (1+(λ,λ)) genetic algorithm can compar...
research
∙
05/02/2020
Lower Bounds for Non-Elitist Evolutionary Algorithms Via Negative Multiplicative Drift
A decent number of lower bounds for non-elitist population-based evoluti...
research
∙
04/20/2020
Fixed-Target Runtime Analysis
Runtime analysis aims at contributing to our understanding of evolutiona...
research
∙
04/15/2020
From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
One of the key difficulties in using estimation-of-distribution algorith...
research
∙
04/14/2020
The (1 + (λ, λ)) GA Is Even Faster on Multimodal Problems
The (1 + (λ,λ)) genetic algorithm is a recent invention of the theory co...
research
∙
04/14/2020
Fast Mutation in Crossover-based Algorithms
The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017)...
research
∙
04/13/2020
Exponential Upper Bounds for the Runtime of Randomized Search Heuristics
We argue that proven exponential upper bounds on runtimes, an establishe...
research
∙
04/10/2020
A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes
With elementary means, we prove a stronger run time guarantee for the un...
research
∙
04/02/2020
Does Comma Selection Help To Cope With Local Optima
One hope of using non-elitism in evolutionary computation is that it aid...
research
∙
11/26/2019
Optimization of Chance-Constrained Submodular Functions
Submodular optimization plays a key role in many real-world problems. In...
research
∙
10/31/2019
Sharp Bounds for Genetic Drift in EDAs
Estimation of Distribution Algorithms (EDAs) are one branch of Evolution...
research
∙
08/18/2019
