Johannes Lengler

Prof. Dr. Johannes Lengler

orcid

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
20 June 2018 in Combinatorics, Probability and Computing
Verified
Journal Article
Closed access
PDF file
JLJohannes Lengler
Johannes Lengler
ASA. Steger
A. Steger
One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a functionf: {0,1}n→ ℝ. The algorithm starts with a random search point ξ ∈ {0,1}n, and in each round it flips each bit of ξ with probabilityc/nindependently at random, wherec> 0 is a fixed constant. The thus created offspring ξ' replaces ξ if and only iff(ξ') ≥f(ξ). The analysis of the runtime of this simple algorithm for monotone and for linear functions turned out to be highly non-trivial. In this paper we review known results and provide new and self-contained proofs of partly stronger results.

15 May 2019 in IEEE Transactions on Evolutionary Computation
Verified
Journal Article
Closed access
JLJohannes Lengler
Johannes Lengler
It is known that the (1+1)-EA with mutation rate c/n optimises every monotone function efficiently if c<1, and needs exponential time on some monotone functions (HotTopic functions) if c≥2.2. We study the same question for a large variety of algorithms, particularly for the (1+λ)-EA, (μ+1)-EA, (μ+1)-GA, their “fast” counterparts, and for the (1+(λ,λ))-GA. We find that all considered mutation-based algorithms show a similar dichotomy for HotTopic functions, or even for all monotone functions. For the (1+(λ,λ))-GA, this dichotomy is in the parameter cγ, which is the expected number of bit flips in an individual after mutation and crossover, neglecting selection. For the fast algorithms, the dichotomy is in m2/m1, where m1 and m2 are the first and second falling moment of the number of bit flips. Surprisingly, the range of efficient parameters is not affected by either population size μ nor by the offspring population size λ. The picture changes completely if crossover is allowed. The genetic algorithms (μ+1)-GA and (μ+1)-fGA are efficient for arbitrary mutations strengths if μ is large enough.

4 December 2013 in PLOS ONE
Verified
Journal Article
Open access
PDF file
JLJohannes Lengler
Johannes Lengler
FJFlorian Jug
Florian Jug
ASAngelika Steger
Angelika Steger
For every engineer it goes without saying: in order to build a reliable system we need components that consistently behave precisely as they should. It is also well known that neurons, the building blocks of brains, do not satisfy this constraint. Even neurons of the same type come with huge variances in their properties and these properties also vary over time. Synapses, the connections between neurons, are highly unreliable in forwarding signals. In this paper we argue that both these fact add variance to neuronal processes, and that this variance is not a handicap of neural systems, but that instead predictable and reliable functional behavior of neural systems depends crucially on this variability. In particular, we show that higher variance allows a recurrently connected neural population to react more sensitively to incoming signals, and processes them faster and more energy efficient. This, for example, challenges the general assumption that the intrinsic variability of neurons in the brain is a defect that has to be overcome by synaptic plasticity in the process of learning.

4 November 2020 in Algorithmica
Verified
Journal Article
Open access
PDF file
JLJohannes Lengler
Johannes Lengler
DSDirk Sudholt
Dirk Sudholt
CWCarsten Witt
Carsten Witt
The compact Genetic Algorithm (cGA) evolves a probability distribution favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We study the intricate dynamics of the cGA on the test functionOneMax, and how its performance depends on the hypothetical population sizeK, which determines how quickly decisions about promising bit values are fixated in the probabilistic model. It is known that the cGA and the Univariate Marginal Distribution Algorithm (UMDA), a related algorithm whose population size is called $$\lambda$$λ , run in expected time $$O(n \log n)$$O(nlogn) when the population size is just large enough ( $$K = \varTheta (\sqrt{n}\log n)$$K=Θ(nlogn) and $$\lambda = \varTheta (\sqrt{n}\log n)$$λ=Θ(nlogn) , respectively) to avoid wrong decisions being fixated. The UMDA also shows the same performance in a very different regime ( $$\lambda =\varTheta (\log n)$$λ=Θ(logn) , equivalent to $$K = \varTheta (\log n)$$K=Θ(logn) in the cGA) with much smaller population size, but for very different reasons: many wrong decisions are fixated initially, but then reverted efficiently. If the population size is even smaller ( $$o(\log n)$$o(logn) ), the time is exponential. We show that population sizes in between the two optimal regimes are worse as they yield larger runtimes: we prove a lower bound of $$\varOmega (K^{1/3}n + n \log n)$$Ω(K1/3n+nlogn) for the cGA onOneMaxfor $$K = O(\sqrt{n}/\log ^2 n)$$K=O(n/log2n) . For $$K = \varOmega (\log ^3 n)$$K=Ω(log3n) the runtime increases with growing Kbefore dropping again to $$O(K\sqrt{n} + n \log n)$$O(Kn+nlogn) for $$K = \varOmega (\sqrt{n} \log n)$$K=Ω(nlogn) . This suggests that the expected runtime for the cGA is a bimodal function in Kwith two very different optimal regions and worse performance in between.

1 February 2019 in Theoretical Computer Science
Verified
Journal Article
Closed access
LGLeslie Ann Goldberg
Leslie Ann Goldberg
JLJohn Lapinskas
John Lapinskas
JLJohannes Lengler
Johannes Lengler
FMFlorian Meier
Florian Meier
KPKonstantinos Panagiotou
Konstantinos Panagiotou
PPPascal Pfister
Pascal Pfister