We study push-pull rumour spreading in ultra-small-world models for social networks where the degrees follow a power-law distribution. In a non-geometric setting, Fountoulakis, Panagiotou and Sauerwald have shown that rumours always spread ultra-fast (SODA 2012). On the other hand, Janssen and Mehrabian have found that rumours spread slowly in a spatial preferential attachment model (SIDMA 2017). We study the question systematically for the model of Geometric Inhomogeneous Random Graphs (GIRGs), which has been found to be a good theoretical and empirical fit for social networks. Our results are two-fold: first, with classical Euclidean geometry slow, fast and ultra-fast (i.e., polynomial, polylogarithmic and doubly logarithmic number of rounds) rumour spreading may occur, depending on the exponent of the power law and the strength of the geometry in the network, and we fully characterise the phase boundaries between these regimes. The regimes do not coincide with the graph distance regimes, i.e., polylogarithmic or even polynomial rumour spreading may occur even if graph distances are doubly logarithmic. We expect these results to hold with little effort for related models, e.g. Scale-Free Percolation. Second, we show that rumour spreading is always (at least) fast in a nonmetric geometry. The considered non-metric geometry allows to model social connections where resemblance of vertices in a single attribute, such as familial kinship, already strongly indicates the presence of an edge. Classical Euclidean geometry fails to capture such ties.

Abstract We compare the $$(1, \lambda )$$ -EA and the $$(1 + \lambda )$$ -EA on the recently introduced benchmark $$\textsc {DisOM}$$ , which is the OneMax function with randomly planted local optima. Previous work showed that if all local optima have the same relative height, then the plus strategy never loses more than a factor $$O(n\log n)$$ compared to the comma strategy. Here we show that even small random fluctuations in the heights of the local optima have a devastating effect for the plus strategy and lead to superpolynomial time to achieve a prescribed fitness target. On the other hand, due to their ability to escape local optima, comma strategies are unaffected by the height of the local optima and remain efficient. Our results hold for a broad class of possible distortions and show that the plus strategy, but not the comma strategy, is generally deceived by sparse unstructured fluctuations of a smooth landscape.

Crossover is a powerful mechanism for generating new solutions from a given population of solutions. Crossover comes with a discrepancy in itself: on the one hand, crossover usually works best if there is enough diversity in the population; on the other hand, exploiting the benefits of crossover reduces diversity. This antagonism often makes crossover reduce its own effectiveness.

Evolutionary multitasking has gained significant attention in the evolutionary computation literature in recent years. Here an evolutionary algorithm is used to compute good or optimal solutions for not just a single but several (possibly related) tasks. We provide a first runtime analysis of evolutionary multitask algorithms and investigate generalized versions of OneMax, LeadingOnes, and Jump which are classical benchmark functions frequently studied in the area of runtime analysis. Our theoretical investigations point out significant speed ups when using evolutionary multitasking instead of several runs of the classical (1+1) EA. In particular, our analysis reveals how progress is shared between the different tasks using uniform crossover in an evolutionary multitasking algorithm. We complement our asymptotic theoretical analysis by experimental investigations which provide further insights into the actual speed ups dependent on the similarity of the given tasks for realistic problem sizes.

Abstract Evolutionary algorithms (EAs) are general-purpose optimisation algorithms that maintain a population (multiset) of candidate solutions and apply variation operators to create new solutions called offspring. A new population is typically formed using one of two strategies: a $$(\mu +\lambda )$$ EA (plus selection) keeps the best $$\mu $$ search points out of the union of $$\mu $$ parents in the old population and $$\lambda $$ offspring, whereas a $$(\mu ,\lambda )$$ EA (comma selection) discards all parents and only keeps the best $$\mu $$ out of $$\lambda $$ offspring. Comma selection may help to escape from local optima, however when and how it is beneficial is subject to an ongoing debate. We propose a new benchmark function to investigate the benefits of comma selection: the well known benchmark function OneMax with randomly planted local optima, generated by frozen noise. We show that comma selection (the $${(1,\lambda )}$$ EA) is faster than plus selection (the $${(1+\lambda )}$$ EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes $$\lambda $$ for which both algorithms behave differently. For certain parameters, the $${(1,\lambda )}$$ EAfinds the target in $$\Theta (n \ln n)$$ evaluations, with high probability (w.h.p.), while the $${(1+\lambda )}$$ EAw.h.p. requires $$\omega (n^2)$$ evaluations. We further show that the advantage of comma selection is not arbitrarily large: w.h.p. comma selection outperforms plus selection at most by a factor of $$O(n \ln n)$$ for most reasonable parameter choices. We develop novel methods for analysing frozen noise and give powerful and general fixed-target results with tail bounds that are of independent interest.

Abstract The $$\textsc {Jump} _k$$ benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (Algorithmica 2002) proved an upper bound of $$O(\textrm{poly}(n) + 4^k/p_c)$$ for the ( $$\mu $$ +1) Genetic Algorithm (( $$\mu $$ +1) GA), but only for unrealistically small crossover probabilities $$p_c$$ . To this date, it remains an open problem to prove similar upper bounds for realistic $$p_c$$ ; the best known runtime bound, in terms of function evaluations, for $$p_c = \Omega (1)$$ is $$O((n/\chi )^{k-1})$$ , $$\chi $$ a positive constant. We provide a novel approach and analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the ( $$\mu $$ +1) GA on $$\textsc {Jump} _k$$ . The ( $$\mu $$ +1)- $${\lambda _c}$$ -GA creates one offspring in each generation either by applying mutation to one parent or by applying crossover $${\lambda _c}$$ times to the same two parents (followed by mutation), to amplify the probability of creating an accepted offspring in generations with crossover. We show that population diversity in the ( $$\mu $$ +1)- $${\lambda _c}$$ -GA converges to an equilibrium of near-perfect diversity. This yields an improved time bound of $$O(\mu n \log (\mu ) + 4^k)$$ function evaluations for a range of k under the mild assumptions $$p_c = O(1/k)$$ and $$\mu \in \Omega (kn)$$ . For all constant k , the restriction is satisfied for some $$p_c = \Omega (1)$$ and it implies that the expected runtime for all constant k and an appropriate $$\mu = \Theta (kn)$$ is bounded by $$O(n^2 \log n)$$ , irrespective of k . For larger k , the expected time of the ( $$\mu $$ +1)- $${\lambda _c}$$ -GA is $$\Theta (4^k)$$ , which is tight for a large class of unbiased black-box algorithms and faster than the original ( $$\mu $$ +1) GA by a factor of $$\Omega (1/p_c)$$ . We also show that our analysis can be extended to other unitation functions such as $$\textsc {Jump} _{k, \delta }$$ and H urdle .

We study the (1:s+1) success rule for controlling the population size of the (1,λ)-EA. It was shown by Hevia Fajardo and Sudholt that this parameter control mechanism can run into problems for large s if the fitness landscape is too easy. They conjectured that this problem is worst for the OneMax benchmark, since in some well-established sense OneMax is known to be the easiest fitness landscape. In this paper, we disprove this conjecture. We show that there exist s and ɛ such that the self-adjusting (1,λ)-EA with the (1:s+1)-rule optimizes OneMax efficiently when started with ɛn zero-bits, but does not find the optimum in polynomial time on Dynamic BinVal. Hence, we show that there are landscapes where the problem of the (1:s+1)-rule for controlling the population size of the (1,λ)-EA is more severe than for OneMax. The key insight is that, while OneMax is the easiest function for decreasing the distance to the optimum, it is not the easiest fitness landscape with respect to finding fitness-improving steps.

In this paper, we study graph distances in the geometric random graph models scale-free percolation SFP, geometric inhomogeneous random graphs GIRG, and hyperbolic random graphs HRG. Despite the wide success of the models, the parameter regime in which graph distances are polylogarithmic is poorly understood. We provide new and improved lower bounds. In a certain portion of the parameter regime, those match the known upper bounds. Compared to the best previous lower bounds by Hao and Heydenreich, our result has several advantages: it gives matching bounds for a larger range of parameters, thus settling the question for a larger portion of the parameter space. It strictly improves the lower bounds by Hao and Heydenreich for all parameters settings in which those bounds were not tight. It gives tail bounds on the probability of having short paths, which imply shape theorems for the $k$-neighbourhood of a vertex whenever our lower bounds are tight, and tight bounds for the size of this $k$-neighbourhood. And last but not least, our proof is much simpler and not much longer than two pages, and we demonstrate that it generalizes well by showing that the same technique also works for first passage percolation.

We compare the (1, λ)-EA and the (1 + λ)-EA on the recently introduced benchmark DisOM, which is the OneMax function with randomly planted local optima. Previous work showed that if all local optima have the same relative height, then the plus strategy never loses more than a factor O(n log n) compared to the comma strategy. Here we show that even small random fluctuations in the heights of the local optima have a devastating effect for the plus strategy and lead to super-polynomial runtimes. On the other hand, due to their ability to escape local optima, comma strategies are unaffected by the height of the local optima and remain efficient. Our results hold for a broad class of possible distortions and show that the plus strategy, but not the comma strategy, is generally deceived by sparse unstructured fluctuations of a smooth landscape. We further develop new techniques for analyzing "frozen noise" which may be of independent interest.

The Jumpk benchmark was the first problem for which crossover was proven to give a speedup over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of O(poly(n) + 4k/pc) for the (μ+1) Genetic Algorithm ((μ+1) GA), but only for unrealistically small crossover probabilities pc. To this date, it remains an open problem to prove similar upper bounds for realistic pc; the best known runtime bound for pc = Ω(1) is O((n/x)k-1), χ a positive constant.

Abstract Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantages of population diversity, we have no clear picture of how diversity evolves over time. We study how the population diversity of $$(\mu +1)$$ ( μ + 1 ) algorithms, measured by the sum of pairwise Hamming distances, evolves in a fitness-neutral environment. We give an exact formula for the drift of population diversity and show that it is driven towards an equilibrium state. Moreover, we bound the expected time for getting close to the equilibrium state. We find that these dynamics, including the location of the equilibrium, are unaffected by surprisingly many algorithmic choices. All unbiased mutation operators with the same expected number of bit flips have the same effect on the expected diversity. Many crossover operators have no effect at all, including all binary unbiased, respectful operators. We review crossover operators from the literature and identify crossovers that are neutral towards the evolution of diversity and crossovers that are not.

Abstract Dynamic linear functions on the boolean hypercube are functions which assign to each bit a positive weight, but the weights change over time. Throughout optimization, these functions maintain the same global optimum, and never have defecting local optima. Nevertheless, it was recently shown [Lengler, Schaller, FOCI 2019] that the $$(1+1)$$ ( 1 + 1 ) -Evolutionary Algorithm needs exponential time to find or approximate the optimum for some algorithm configurations. In this experimental paper, we study the effect of larger population sizes for dynamic binval, the extreme form of dynamic linear functions. We find that moderately increased population sizes extend the range of efficient algorithm configurations, and that crossover boosts this positive effect substantially. Remarkably, similar to the static setting of monotone functions in [Lengler, Zou, FOGA 2019], the hardest region of optimization for $$(\mu +1)$$ ( μ + 1 ) -EA is not close the optimum, but far away from it. In contrast, for the $$(\mu +1)$$ ( μ + 1 ) -GA, the region around the optimum is the hardest region in all studied cases.Kindly check and confirm the inserted city name is correctly identified.Correct.

In a seminal paper in 2013, Witt showed that the (1+1) Evolutionary Algorithm with standard bit mutation needs time (1 + o (1))n ln n/p1 to find the optimum of any linear function, as long as the probability p1 to flip exactly one bit is Θ(1). In this paper we investigate how this result generalizes if standard bit mutation is replaced by an arbitrary unbiased mutation operator. This situation is notably different, since the stochastic domination argument used for the lower bound by Witt no longer holds. In particular, starting closer to the optimum is not necessarily an advantage, and OneMax is no longer the easiest function for arbitrary starting positions.

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 comma selection: OneMax with randomly planted local optima, generated by frozen noise. We show that comma selection (the (1, Λ) EA) is faster than plus selection (the (1 + Λ) EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes Λ for which both algorithms behave differently. For certain parameters, the (1, Λ) EA finds the target in Θ(n ln n) evaluations, with high probability (w.h.p.), while the (1 + Λ) EA w.h.p. requires almost Θ((n ln n)2) evaluations.

Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantages of population diversity, we have no clear picture of how diversity evolves over time.

In this paper we show how to use drift analysis in the case of two random variables X1,X2, when the drift is approximatively given by A⋅(X1,X2)T for a matrix A. The non-trivial case is that X1 and X2 impede each other's progress, and we give a full characterization of this case. As an application, we develop and analyze a minimal example TwoLin of a dynamic environment that can be hard. The environment consists of two linear functions f1 and f2 with positive weights, and in each generation selection is based on one of them at random. They only differ in the set of positions that have weight 1 and n. We show that the (1+1)-EA with mutation rate χ/n is efficient for small χ on TwoLin, but does not find the shared optimum in polynomial time for large χ.

We study the (1,λ)-EA with mutation rate c/n for c≤1, where the population size is adaptively controlled with the (1:s+1)-success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c=1 is efficient on OneMax for s<1, but inefficient if s≥18. Surprisingly, the hardest part is not close to the optimum, but rather at linear distance. We show that this behavior is not specific to OneMax. If s is small, then the algorithm is efficient on all monotone functions, and if s is large, then it needs super-polynomial time on all monotone functions. In the former case, for c<1 we show a O(n) upper bound for the number of generations and O(nlog⁡n) for the number of function evaluations, and for c=1 we show O(nlog⁡n) generations and O(n2log⁡log⁡n) evaluations. We also show formally that optimization is always fast, regardless of s, if the algorithm starts in proximity of the optimum. All results also hold in a dynamic environment where the fitness function changes in each generation. An extended abstract, containing only the results without proofs, has been published at the PPSN conference [1].

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 literal sense, a common interpretation sees the one-fifth success rule as a family of success-based updated rules that are determined by an update strength F and a success rate. We analyze in this work how the performance of the (1+1) Evolutionary Algorithm on Leading Ones depends on these two hyper-parameters. Our main result shows that the best performance is obtained for small update strengths $$F=1+o(1)$$ and success rate 1/e. We also prove that the running time obtained by this parameter setting is, apart from lower order terms, the same that is achieved with the best fitness-dependent mutation rate. We show similar results for the resampling variant of the (1+1) Evolutionary Algorithm, which enforces to flip at least one bit per iteration.

Abstract 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.

Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].

In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli et al., 2013] it was also conjectured that the same result still holds for sparse graphs if the degrees are at least C log n. We disprove this conjecture by showing that even for degrees n^epsilon, for some epsilon>0, the algorithm converges without reaching consensus. In fact, we show that the algorithm does not even reach almost consensus, but converges prematurely resulting in orders of magnitude more communities.

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. A general trend is that evolutionary algorithms are efficient if parameters like the mutation rate are set conservatively, but may need exponential time otherwise. In particular, it was known that the (1 + 1)-EA and the (1 + λ)-EA can optimize every monotone function in pseudolinear time if the mutation rate is c/n for some c < 1, but that they need exponential time for some monotone functions for c > 2.2. The second part of the statement was also known for the (µ + 1)-EA.

We study unbiased (1 + 1) evolutionary algorithms on linear functions with an unknown number n of bits with non-zero weight. Static algorithms achieve an optimal runtime of O(n(ln n)2+ε), however, it remained unclear whether more dynamic parameter policies could yield better runtime guarantees. We consider two setups: one where the mutation rate follows a fixed schedule, and one where it may be adapted depending on the history of the run. For the first setup, we give a schedule that achieves a runtime of (1±o(1))βn ln n, where β ≈ 3.552, which is an asymptotic improvement over the runtime of the static setup. Moreover, we show that no schedule admits a better runtime guarantee and that the optimal schedule is essentially unique. For the second setup, we show that the runtime can be further improved to (1 ± o(1))en ln n, which matches the performance of algorithms that know n in advance.

We study the intricate dynamics of the Compact Genetic Algorithm (cGA) on OneMax, and how its performance depends on the step size 1/K, that determines how quickly decisions about promising bit values are fixed in the probabilistic model. It is known that cGA and UMDA, a related algorithm, run in expected time O(n log n) when the step size is just small enough [EQUATION] to avoid wrong decisions being fixed. UMDA also shows the same performance in a very different regime (equivalent to K = Θ(log n) in the cGA) with much larger steps sizes, but for very different reasons: many wrong decisions are fixed initially, but then reverted efficiently.

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> c_0 = 2.13692..$$ . We study the same question for a large variety of algorithms, particularly for $$(1 + \lambda )$$ -EA, $$(\mu + 1)$$ -EA, $$(\mu + 1)$$ -GA, their fast counterparts like fast $$(1 + 1)$$ -EA, and for $$(1 + (\lambda ,\lambda ))$$ -GA. We prove that all considered mutation-based algorithms show a similar dichotomy for HotTopic functions, or even for all monotone functions. For the $$(1 + (\lambda ,\lambda ))$$ -GA, this dichotomy is in the parameter $$c\gamma $$ , 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 $$m_2/m_1$$ , where $$m_1$$ and $$m_2$$ 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 $$\mu $$ nor by the offspring population size $$\lambda $$ . The picture changes completely if crossover is allowed. The genetic algorithms $$(\mu + 1)$$ -GA and $$(\mu + 1)$$ -fGA are efficient for arbitrary mutations strengths if $$\mu $$ is large enough.

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 variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat.

We study sorting of permutations by random swaps if the comparison operator is noisy. The noise is not associated with the underlying fitness but is inherent to the comparison operator. This type of fitness-independent noise has not been studied before in the community but is prototypical for comparison-based evolutionary algorithms, which often do not need to compute or approximate explicit fitness values. As quality measure, we compute the average fitness of the stationary distribution. To measure runtime, we compute the minimal number of steps after which the expected fitness approximates the average fitness of the stationary distribution.

The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study decentralized greedy routing in a more flexible random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks. In this model, the greedy routing protocol is purely distributed as each vertex only needs to know information about its direct neighbors. We prove that it succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length Θ(log log n), where our bound is tight including the leading constant. Moreover, we study natural local patching methods which augment greedy routing by backtracking and which do not require any global knowledge. We show that such methods can ensure success probability 1 in an asymptotically tight number of steps.

Black-box complexity theory provides lower bounds for the runtime of black-box optimizers like evolutionary algorithms and other search heuristics and serves as an inspiration for the design of new genetic algorithms. Several black-box models covering different classes of algorithms exist, each highlighting a different aspect of the algorithms under considerations. In this work we add to the existing black-box notions a new elitist black-box model, in which algorithms are required to base all decisions solely on (the relative performance of) a fixed number of the best search points sampled so far. Our elitist model thus combines features of the ranking-based and the memory-restricted black-box models with an enforced usage of truncation selection. We provide several examples for which the elitist black-box complexity is exponentially larger than that of the respective complexities in all previous black-box models, thus showing that the elitist black-box complexity can be much closer to the runtime of typical evolutionary algorithms. We also introduce the concept of p-Monte Carlo black-box complexity, which measures the time it takes to optimize a problem with failure probability at most p. Even for small p, the p-Monte Carlo black-box complexity of a function class [Formula: see text] can be smaller by an exponential factor than its typically regarded Las Vegas complexity (which measures the expected time it takes to optimize [Formula: see text]).

Sequences of precisely timed neuronal activity are observed in many brain areas in various species. Synfire chains are a well-established model that can explain such sequences. However, it is unknown under which conditions synfire chains can develop in initially unstructured networks by self-organization. This work shows that with spike-timing dependent plasticity (STDP), modulated by global population activity, long synfire chains emerge in sparse random networks. The learning rule fosters neurons to participate multiple times in the chain or in multiple chains. Such reuse of neurons has been experimentally observed and is necessary for high capacity. Sparse networks prevent the chains from being short and cyclic and show that the formation of specific synapses is not essential for chain formation. Analysis of the learning rule in a simple network of binary threshold neurons reveals the asymptotically optimal length of the emerging chains. The theoretical results generalize to simulated networks of conductance-based leaky integrate-and-fire (LIF) neurons. As an application of the emerged chain, we propose a one-shot memory for sequences of precisely timed neuronal activity.

Random sampling is a classical tool in constrained optimization. Under favorable conditions, the optimal solution subject to a small subset of randomly chosen constraints violates only a small subset of the remaining constraints. Here we study the following variant that we call random sampling with removal: suppose that after sampling the subset, we remove a fixed number of constraints from the sample, according to an arbitrary rule. Is it still true that the optimal solution of the reduced sample violates only a small subset of the constraints? The question naturally comes up in situations where the solution subject to the sampled constraints is used as an approximate solution to the original problem. In this case, it makes sense to improve cost and volatility of the sample solution by removing some of the constraints that appear most restricting. At the same time, the approximation quality (measured in terms of violated constraints) should remain high. We study random sampling with removal in a generalized, completely abstract setting where we assign to each subset R of the constraints an arbitrary set V(R) of constraints disjoint from R; in applications, V(R) corresponds to the constraints violated by the optimal solution subject to only the constraints in R. Furthermore, our results are parametrized by the dimension d, i.e., we assume that every set R has a subset B of size at most d with the same set of violated constraints. This is the first time this generalized setting is studied. In this setting, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k elements. For a large range of values of k, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases. We show that this bound on special LP-type problems, can be derived in the much more general setting of violator spaces, and with very elementary proofs.

One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the Ω(n log n) lower bound for unary unbiased algorithms on functions with a unique global optimum [Lehre/Witt, GECCO 2010], which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, almost no non-trivial bounds are known for other restricted models. Proving such bounds therefore remains to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of LeadingOnes and prove that its (1+1) elitist black-box complexity is Ω(n2), a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of LeadingOnes is thus considerably larger than its unrestricted one, which is known to be of order n log log n [Afshani et al., 2013].

Geometric inhomogeneous random graphs (GIRGs) are a model for scale-free networks with underlying geometry. We study bootstrap percolation on these graphs, which is a process modelling the spread of an infection of vertices starting within a (small) local region. We show that the process exhibits a phase transition in terms of the initial infection rate in this region. We determine the speed of the process in the supercritical case, up to lower order terms, and show that its evolution is fundamentally influenced by the underlying geometry. For vertices with given position and expected degree, we determine the infection time up to lower order terms. Finally, we show how this knowledge can be used to contain the infection locally by removing relatively few edges from the graph. This is the first time that the role of geometry on bootstrap percolation is analysed mathematically for geometric scale-free networks.

We present a fixed budget analysis of the (1+1) evolutionary algorithm for general linear functions, considering both the quality of the solution after a predetermined 'budget' of fitness function evaluations (a priori) and the improvement in quality when the algorithm is given additional budget, given the quality of the current solution (a posteriori). Two methods are presented: one based on drift analysis, the other on the differential equation method and Chebyshev's inequality. While the first method is superior for general linear functions, the second can be more precise for specific functions and provides concentration guarantees. As an example, we provide tight a posteriori fixed budget results for the function OneMax.

Black-box complexity theory provides lower bounds for the runtime %classes of black-box optimizers like evolutionary algorithms and serves as an inspiration for the design of new genetic algorithms. Several black-box models covering different classes of algorithms exist, each highlighting a different aspect of the algorithms under considerations. In this work we add to the existing black-box notions a new \emph{elitist black-box model}, in which algorithms are required to base all decisions solely on (a fixed number of) the best search points sampled so far. Our model combines features of the ranking-based and the memory-restricted black-box models with elitist selection.

As in classical runtime analysis the OneMax problem is the most prominent test problem also in black-box complexity theory. It is known that the unrestricted, the memory-restricted, and the ranking-based black-box complexities of this problem are all of order n/log n, where n denotes the length of the bit strings. The combined memory-restricted ranking-based black-box complexity of OneMax, however, was not known. We show in this work that it is Θ(n) for the smallest possible size bound, that is, for (1+1) black-box algorithms. We extend this result by showing that even if elitist selection is enforced, there exists a linear time algorithm optimizing OneMax with failure probability o(1). This is quite surprising given that all previously regarded algorithms with o(n log n) runtime on OneMax, in particular the quite natural (1+(λ,λ))~GA, heavily exploit information encoded in search points of fitness much smaller than the current best-so-far solution.

Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on black-box complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and single-source shortest paths. Besides giving interesting bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem is non-trivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.

In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search [13] to accelerate the search for improved offsprings.To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems OneMax, LeadingOnes, and Discrepancy. We show that although there is a speedup in the case of OneMax and LeadingOnes in the quantum setting, the speedup is less than quadratic. For Discrepancy, we show that the speedup is at best constant.The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps.