-
Chapter and Conference Paper
Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms
We revisit the analysis of the ( \(1\) 1 ...
-
Article
Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs
The runtime analysis of evolutionary algorithms using crossover as search operator has recently produced remarkable results indicating benefits and drawbacks of crossover and illustrating its working principle...
-
Article
Fixed-Parameter Tractability of Crossover: Steady-State GAs on the Closest String Problem
We investigate the effect of crossover in the context of parameterized complexity on a well-known fixed-parameter tractable combinatorial optimization problem known as the closest string problem. We prove that a ...
-
Chapter and Conference Paper
Solving Non-uniform Planted and Filtered Random SAT Formulas Greedily
Recently, there has been an interest in studying non-uniform random k-satisfiability (k-SAT) models in order to address the non-uniformity of formulas arising from real-world applications. While uniform random k-...
-
Chapter and Conference Paper
Symmetry Breaking for Voting Mechanisms
Recently, Rowe and Aishwaryaprajna [FOGA 2019] introduced a simple majority vote technique that efficiently solves Jump with large gaps, OneMax with large noise, and any monotone function with a polynomial-size i...
-
Chapter and Conference Paper
Approximation Speed-Up by Quadratization on LeadingOnes
We investigate the quadratization of LeadingOnes in the context of the landscape for local search. We prove that a standard quadratization (i.e., its expression as a degree-2 multilinear polynomial) of LeadingOne...
-
Chapter
Parameterized Complexity Analysis of Randomized Search Heuristics
This chapter compiles a number of results that apply the theory of parameterized algorithmics to the running-time analysis of randomized search heuristics such as evolutionary algorithms. The parameterized app...
-
Chapter and Conference Paper
On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition
The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic l...
-
Chapter and Conference Paper
Runtime Analysis of Evolutionary Algorithms for the Knapsack Problem with Favorably Correlated Weights
We rigorously analyze the runtime of evolutionary algorithms for the classical knapsack problem where the weights are favorably correlated with the profits. Our result for the (
-
Article
Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas
We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and ...
-
Article
Superpolynomial Lower Bounds for the \((1+1)\) EA on Some Easy Combinatorial Problems
The ( \(1+1\) 1 + ...
-
Chapter and Conference Paper
Graceful Scaling on Uniform Versus Steep-Tailed Noise
Recently, different evolutionary algorithms (EAs) have been analyzed in noisy environments. The most frequently used noise model for this was additive posterior noise (noise added after the fitness evaluation)...
-
Chapter and Conference Paper
Emergence of Diversity and Its Benefits for Crossover in Genetic Algorithms
Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well un...
-
Chapter and Conference Paper
On the Robustness of Evolving Populations
Most theoretical work that studies the benefit of recombination focuses on the ability of crossover to speed up optimization time on specific search problems. In this paper, we take a slightly different perspe...
-
Chapter and Conference Paper
The Benefit of Recombination in Noisy Evolutionary Search
Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimiza...
-
Chapter and Conference Paper
Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF Formulas
We show that simple mutation-only evolutionary algorithms find a satisfying assignment on two similar models of random planted 3-CNF Boolean formulas in polynomial time with high probability in the high constr...
-
Article
Thomas Jansen: Analyzing Evolutionary Algorithms: The Computer Science Perspective
-
Chapter and Conference Paper
A Parameterized Runtime Analysis of Simple Evolutionary Algorithms for Makespan Scheduling
We consider simple multi-start evolutionary algorithms applied to the classical NP-hard combinatorial optimization problem of Makespan Scheduling on two machines. We study the dependence of the runtime of this ty...
-
Reference Work Entry In depth
Genetic Algorithms — A Survey of Models and Methods
This chapter first reviews the simple genetic algorithm. Mathematical models of the genetic algorithm are also reviewed, including the schema theorem, exact infinite population models, and exact Markov models ...
-
Chapter and Conference Paper
Improved Robustness through Population Variance in Ant Colony Optimization
Ant Colony Optimization algorithms are population-based Stochastic Local Search algorithms that mimic the behavior of ants, simulating pheromone trails to search for solutions to combinatorial optimization pro...
