23 citations · 87 across the 20 of their papers we have counts for
6 papers · 1 filter
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…