23 citations · 87 across the 20 of their papers we have counts for
36 papers
On Connectivity in Random Graph Models with Limited Dependencies
Johannes Lengler, Anders Martinsson, Kalina Petrova +4
For any positive edge density , a random graph in the Erdős-Renyi model is connected with non-zero probability, since all edges are mutually independent. We consider r…
Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima
Joost Jorritsma, Johannes Lengler, Dirk Sudholt
It is an ongoing debate whether and how comma selection in evolutionary algorithms helps to escape local optima. We propose a new benchmark function to investigate the benefits of…
Analysing Equilibrium States for Population Diversity
Johannes Lengler, Andre Opris, Dirk Sudholt
Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantage…
Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions
Carola Doerr, Duri Andrea Janett, Johannes Lengler
In a seminal paper in 2013, Witt showed that the (1+1) Evolutionary Algorithm with standard bit mutation needs time to find the optimum of any linear function…
Population Diversity Leads to Short Running Times of Lexicase Selection
Thomas Helmuth, Johannes Lengler, William La Cava
In this paper we investigate why the running time of lexicase parent selection is empirically much lower than its worst-case bound of O(N*C). We define a measure of population dive…
OneMax is not the Easiest Function for Fitness Improvements
Marc Kaufmann, Maxime Larcher, Johannes Lengler +1
We study the success rule for controlling the population size of the -EA. It was shown by Hevia Fajardo and Sudholt that this parameter control mechanism can run i…
Self-adjusting Population Sizes for the -EA on Monotone Functions
Marc Kaufmann, Maxime Larcher, Johannes Lengler +1
We study the -EA with mutation rate for , where the population size is adaptively controlled with the -success rule. Recently, Hevia Fajardo and Sudho…
Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard
Duri Janett, Johannes Lengler
In this paper we show how to use drift analysis in the case of two random variables , when the drift is approximatively given by for a matrix . Th…
Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function
Johannes Lengler, Simone Riedi
We study evolutionary algorithms in a dynamic setting, where for each generation a different fitness function is chosen, and selection is performed with respect to the current fitn…
Large Population Sizes and Crossover Help in Dynamic Environments
Johannes Lengler, Jonas Meier
Dynamic linear functions on the hypercube are functions which assign to each bit a positive weight, but the weights change over time. Throughout optimization, these functions maint…
Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs
Júlia Komjáthy, John Lapinskas, Johannes Lengler
We study the spread of information in finite and infinite inhomogeneous spatial random graphs. We assume that each edge has a transmission cost that is a product of an i.i.d. rando…
Exponential Slowdown for Larger Populations: The -EA on Monotone Functions
Johannes Lengler, Xun Zou
Pseudo-Boolean monotone functions are unimodal functions which are trivial to optimize for some hillclimbers, but are challenging for a surprising number of evolutionary algorithms…
Self-Adjusting Mutation Rates with Provably Optimal Success Rules
Benjamin Doerr, Carola Doerr, Johannes Lengler
The one-fifth success rule is one of the best-known and most widely accepted techniques to control the parameters of evolutionary algorithms. While it is often applied in the liter…
The linear hidden subset problem for the (1+1) EA with scheduled and adaptive mutation rates
Hafsteinn Einarsson, Marcelo Matheus Gauy, Johannes Lengler +4
We study unbiased evolutionary algorithms on linear functions with an unknown number of bits with non-zero weight. Static algorithms achieve an optimal runtime of $O(n…
When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
Johannes Lengler, Anders Martinsson, Angelika Steger
Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions are (s…
Bounding Bloat in Genetic Programming
Benjamin Doerr, Timo Kötzing, J. A. Gregor Lagodzinski +1
While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on vari…
Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming
Timo Kötzing, J. A. Gregor Lagodzinski, Johannes Lengler +1
For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yieldi…
A General Dichotomy of Evolutionary Algorithms on Monotone Functions
Johannes Lengler
It is known that the evolutionary algorithm -EA with mutation rate optimises every monotone function efficiently if , and needs exponential time on some monotone…
Sorting by Swaps with Noisy Comparisons
Tomáš Gavenčiak, Barbara Geissmann, Johannes Lengler
We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability . We use this process as prototype for the behaviour o…
Drift Analysis
Johannes Lengler
Drift analysis is one of the major tools for analysing evolutionary algorithms and nature-inspired search heuristics. In this chapter we give an introduction to drift analysis and…
Existence of Small Separators Depends on Geometry for Geometric Inhomogeneous Random Graphs
Johannes Lengler, Lazar Todorovic
We show that Geometric Inhomogeneous Random Graphs (GIRGs) with power law weights may either have or not have separators of linear size, depending on the underlying geometry. While…
Tight Analysis for the 3-Majority Consensus Dynamics
Mohsen Ghaffari, Johannes Lengler
We present a tight analysis for the well-studied randomized 3-majority dynamics of stabilizing consensus, hence answering the main open question of Becchetti et al. [SODA'16]. Cons…
Asymptotically Optimal Amplifiers for the Moran Process
Leslie Ann Goldberg, John Lapinskas, Johannes Lengler +3
We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called "mutants" ha…
Drift Analysis and Evolutionary Algorithms Revisited
Johannes Lengler, Angelika Steger
One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a boolean function . The…