Search

For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); the resulting algorithm is denoted Concatenation Crossover GP. For this purpose three variants of the well-studied MAJORITY test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control., Comment: to appear in PPSN 2018

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, that is, the unnecessary growth of solution lengths, which may slow down the optimization process. So far, the mathematical runtime analysis could not deal well with bloat and required explicit assumptions limiting bloat. In this paper, we provide the first mathematical runtime analysis of a GP algorithm that does not require any assumptions on the bloat. Previous performance guarantees were only proven conditionally for runs in which no strong bloat occurs. Together with improved analyses for the case with bloat restrictions our results show that such assumptions on the bloat are not necessary and that the algorithm is efficient without explicit bloat control mechanism. More specifically, we analyzed the performance of the ( 1 + 1 ) GP on the two benchmark functions Order and Majority . When using lexicographic parsimony pressure as bloat control, we show a tight runtime estimate of O ( T init + n log ⁡ n ) iterations both for Order and Majority . For the case without bloat control, the bounds O ( T init log ⁡ T init + n ( log ⁡ n ) 3 ) and Ω ( T init + n log ⁡ n ) (and Ω ( T init log ⁡ T init ) for n = 1 ) hold for Majority . 1

We study randomized algorithms for constrained optimization, in abstract frameworks that include, in strictly increasing generality: convex programming; LP-type problems; violator spaces; and a setting we introduce, consistent spaces. Such algorithms typically involve a step of finding the optimal solution for a random sample of the constraints. They exploit the condition that, in finite dimension $$\delta $$ , this sample optimum violates a provably small expected fraction of the non-sampled constraints, with the fraction decreasing in the sample size r. We extend such algorithms by considering the technique of removal, where a fixed number k of constraints are removed from the sample according to a fixed rule, with the goal of improving the solution quality. This may have the effect of increasing the number of violated non-sampled constraints. We study this increase, and bound it in a variety of general settings. This work is motivated by, and extends, results on removal as proposed for chance-constrained optimization. For many relevant values of r, $$\delta $$ , and k, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k constraints. 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, and not in the generality we consider. Moreover, we show that our results extend from finite to infinite spaces, for chance-constrained optimization.

Real-world networks, like social networks or the internet infrastructure, have structural properties such as large clustering coefficients that can best be described in terms of an underlying geometry. This is why the focus of the literature on theoretical models for real-world networks shifted from classic models without geometry, such as Chung–Lu random graphs, to modern geometry-based models, such as hyperbolic random graphs. With this paper we contribute to the theoretical analysis of these modern, more realistic random graph models. Instead of studying directly hyperbolic random graphs, we use a generalization that we call geometric inhomogeneous random graphs (GIRGs). Since we ignore constant factors in the edge probabilities, GIRGs are technically simpler (specifically, we avoid hyperbolic cosines), while preserving the qualitative behavior of hyperbolic random graphs, and we suggest to replace hyperbolic random graphs by this new model in future theoretical studies. We prove the following fundamental structural and algorithmic results on GIRGs. (1) We provide a sampling algorithm that generates a random graph from our model in expected linear time, improving the best-known sampling algorithm for hyperbolic random graphs by a substantial factor O ( n ) . (2) We establish that GIRGs have clustering coefficients in Ω ( 1 ) , (3) we prove that GIRGs have small separators, i.e., it suffices to delete a sublinear number of edges to break the giant component into two large pieces, and (4) we show how to compress GIRGs using an expected linear number of bits.

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” have fitness r and other individuals, called “non-mutants” have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r > 1 . A family of digraphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on digraphs in this family. The most-amplifying known family of digraphs is the family of megastars of Galanis et al. We show that this family is optimal, up to logarithmic factors, since every strongly-connected n-vertex digraph has extinction probability Ω ( n − 1 / 2 ) . Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O ( n − 1 / 3 ) . We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O ( n / m ) , where m is the number of edges. Again, we show that this is optimal, up to constant factors.

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 function OneMax, and how its performance depends on the hypothetical population size K, 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 ( n log n ) when the population size is just large enough ($$K = \varTheta (\sqrt{n}\log n)$$ K = Θ ( n log n ) and $$\lambda = \varTheta (\sqrt{n}\log n)$$ λ = Θ ( n log n ) , respectively) to avoid wrong decisions being fixated. The UMDA also shows the same performance in a very different regime ($$\lambda =\varTheta (\log n)$$ λ = Θ ( log n ) , equivalent to $$K = \varTheta (\log n)$$ K = Θ ( log n ) 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 ( log n ) ), 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)$$ Ω ( K 1 / 3 n + n log n ) for the cGA on OneMax for $$K = O(\sqrt{n}/\log ^2 n)$$ K = O ( n / log 2 n ) . For $$K = \varOmega (\log ^3 n)$$ K = Ω ( log 3 n ) the runtime increases with growing K before dropping again to $$O(K\sqrt{n} + n \log n)$$ O ( K n + n log n ) for $$K = \varOmega (\sqrt{n} \log n)$$ K = Ω ( n log n ) . This suggests that the expected runtime for the cGA is a bimodal function in K with two very different optimal regions and worse performance in between.

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 fitness function. Specifically, we consider Dynamic BinVal, in which the fitness functions for each generation is given by the linear function BinVal, but in each generation the order of bits is randomly permuted. For the \((1 + 1)\)-EA it was known that there is an efficiency threshold \(c_0\) for the mutation parameter, at which the runtime switches from quasilinear to exponential. Previous empirical evidence suggested that for larger population size \(\mu \), the threshold may increase. We prove rigorously that this is at least the case in an \(\varepsilon \)-neighborhood around the optimum: the threshold of the \((\mu + 1)\)-EA becomes arbitrarily large if the \(\mu \) is chosen large enough.

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)\)-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 extremal 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)\)-EA is not close the optimum, but far away from it. In contrast, for the \((\mu +1)\)-GA, the region around the optimum is the hardest region in all studied cases (Extended Abstract. A full version is available on arxiv at [11]).

It is known that many neurons in the brain show spike trains with a coefficient of variation (CV) of the interspike times of approximately 1, thus resembling the properties of Poisson spike trains. Computational studies have been able to reproduce this phenomenon. However, the underlying models were too complex to be examined analytically. In this paper, we offer a simple model that shows the same effect but is accessible to an analytic treatment. The model is a random walk model with a reflecting barrier; we give explicit formulas for the CV in the regime of excess inhibition. We also analyze the effect of probabilistic synapses in our model and show that it resembles previous findings that were obtained by simulation.

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 to 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 $$\varOmega (n \log n)$$ lower bound for unary unbiased algorithms on functions with a unique global optimum (Lehre and Witt in Algorithmica 64:623–642, 2012), which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, such non-trivial lower bounds are very rare in the existing literature on black-box optimization and therefore remain 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 $$\varOmega (n^2)$$ , 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. in Lecture notes in computer science, vol 8066, pp 1–11. Springer, New York, 2013). The $$\varOmega (n^2)$$ lower bound does not rely on the fact that elitist black-box algorithms are not allowed to make use of absolute fitness values. In contrast, we show that even if absolute fitness values are revealed to the otherwise elitist algorithm, it cannot significantly profit from this additional information. Our result thus shows that for LeadingOnes the memory-restriction, together with the selection requirement, has a substantial impact on the best possible performance.

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 + e ) , 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 ) ) e n ln ⁡ n , which matches the performance of algorithms that know n in advance. Finally, we study the related model of initial segment uncertainty with static position-dependent mutation rates, and derive asymptotically optimal lower bounds. This answers a question by Doerr, Doerr, and Kotzing.

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. In this paper we show that the first statement does not apply to the ( μ + 1 ) -EA. More precisely, we prove that for every constant c > 0 there is a constant μ 0 ∈ N such that the ( μ + 1 ) -EA with mutation rate c / n and population size μ 0 ≤ μ ≤ n needs superpolynomial time to optimize some monotone functions. Thus, increasing the population size by just a constant has devastating effects on the performance. This is in stark contrast to many other benchmark functions on which increasing the population size either increases the performance significantly, or affects performance only mildly. The reason why larger populations are harmful lies in the fact that larger populations may temporarily decrease the selective pressure on parts of the population. This allows unfavorable mutations to accumulate in single individuals and their descendants. If the population moves sufficiently fast through the search space, then such unfavorable descendants can become ancestors of future generations, and the bad mutations are preserved. Remarkably, this effect only occurs if the population renews itself sufficiently fast, which can only happen far away from the optimum. This is counter-intuitive since usually optimization becomes harder as we approach the optimum. Previous work missed the effect because it focused on monotone functions that are only deceptive close to the optimum.

An important benchmark for evolutionary algorithms are (strictly) monotone functions. For the (1 + 1)-EA with mutation rate c/n, it was known that it can optimize any monotone function on n bits in time O(n log n) if c c c = 1 it was known that the runtime is always polynomial, but it was unclear whether it is quasilinear, and it was unclear whether c = 1 is the threshold at which the runtime jumps from polynomial to superpolynomial. We show there exists a c0 > 1 such that for all 0 c ≤ c0 the (1 + 1)-Evolutionary Algorithm with rate c/n finds the optimum in O(n log2 n) steps in expectation. The proof is based on an adaptation of Moser's entropy compression argument. That is, we show that a long runtime would allow us to encode the random steps of the algorithm with less bits than their entropy. This short note summarizes the results that have been published as "When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument" in the proceedings of the 16th Workshop on Analytic Algorithmics and Combinatorics (ANALCO), SIAM, 2019 [9].

We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability $p, An extended abstract of this paper has been presented at Genetic and Evolutionary Computation Conference (GECCO 2017)

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 LeadingOnes 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., Comment: Conference version appeared at GECCO 2019. This full version appeared in Algorithmica (2021)

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 (K = Θ(n log n)) 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. We show that step sizes in between these two optimal regimes are harmful as they yield larger runtimes: we prove a lower bound of Ω(K1/3n+n log n) for the cGA on OneMax for K = O(n/log2 n). For K = Ω(log3 n) the runtime increases with growing K before dropping again to O(Kn + n log n) for K = Ω(n log n). This suggests that the expected runtime for cGA is a bimodal function in K with two very different optimal regions and worse performance in between.

For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work.

Black-box complexity studies lower bounds for the efficiency of general-purpose black-box optimization algorithms such as evolutionary algorithms and other search heuristics. Different models exist, each one being designed to analyze a different aspect of typical heuristics such as the memory size or the variation operators in use. While most of the previous works focus on one particular such aspect, we consider in this work how the combination of several algorithmic restrictions influence the black-box complexity. Our testbed are so-called OneMax functions, a classical set of test functions that is intimately related to classic coin-weighing problems and to the board game Mastermind. We analyze in particular the combined memory-restricted ranking-based black-box complexity of OneMax for different memory sizes. While its isolated memory-restricted as well as its ranking-based black-box complexity for bit strings of length $n$ is only of order $n/\log n$, the combined model does not allow for algorithms being faster than linear in $n$, as can be seen by standard information-theoretic considerations. We show that this linear bound is indeed asymptotically tight. Similar results are obtained for other memory- and offspring-sizes. Our results also apply to the (Monte Carlo) complexity of OneMax in the recently introduced elitist model, in which only the best-so-far solution can be kept in the memory. Finally, we also provide improved lower bounds for the complexity of OneMax in the regarded models. Our result enlivens the quest for natural evolutionary algorithms optimizing OneMax in $o(n \log n)$ iterations., Comment: This is the full version of a paper accepted to GECCO 2015

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., 26 pages. This is the full version of the one presented at the Genetic and Evolutionary Computation Conference (GECCO 2011)

Black-box complexity theory provides lower bounds for the runtime 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. We provide several examples for which the elitist black-box complexity is exponentially larger than that 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 $\mathcal F$ can be smaller by an exponential factor than its typically regarded Las Vegas complexity (which measures the \emph{expected} time it takes to optimize $\mathcal F$)., Comment: A short version of this work has been presented at the GECCO conference 2015 in Madrid, Spain. Available at http://dl.acm.org/citation.cfm?doid=2739480.2754654

In an Achlioptas process, starting with a graph that has n vertices and no edge, in each round $d \geq 1$ edges are drawn uniformly at random, and using some rule exactly one of them is chosen and added to the evolving graph. For the class of Achlioptas processes we investigate how much impact the rule has on one of the most basic properties of a graph: connectivity. Our main results are twofold. First, we study the prominent class of bounded size rules, which select the edge to add according to the component sizes of its vertices, treating all sizes larger than some constant equally. For such rules we provide a fine analysis that exposes the limiting distribution of the number of rounds until the graph gets connected, and we give a detailed picture of the dynamics of the formation of the single component from smaller components. Second, our results allow us to study the connectivity transition of all Achlioptas processes, in the sense that we identify a process that accelerates it as much as possible.

One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a boolean function $f:\{0,1\}^n \to {\mathbb R}$. The algorithm starts with a random search point $\xi \in \{0,1\}^n$, and in each round it flips each bit of $\xi$ with probability $c/n$ independently at random, where $c>0$ is a fixed constant. The thus created offspring $\xi'$ replaces $\xi$ if and only if $f(\xi') \ge f(\xi)$. The analysis of the runtime of this simple algorithm on monotone and on 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., Comment: minor changes to improve readability

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 $\Omega(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 \textsc{LeadingOnes} and prove that its (1+1) elitist black-box complexity is $\Omega(n^2)$, a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of \textsc{LeadingOnes} is thus considerably larger than its unrestricted one, which is known to be of order $n\log\log n$ [Afshani et al., 2013]., Comment: An extended abstract of this paper will appear at GECCO 2016

The Cohen–Lenstra heuristic is a universal principle that assigns to each group a probability that tells how often this group should occur “in nature”. The most important, but not the only, applications are sequences of class groups, which conjecturally behave like random sequences of groups with respect to the so-called Cohen–Lenstra probability measure. So far, it was only possible to define this probability measure for finite abelian p-groups. We prove that it is also possible to define an analogous probability measure on the set of all finite abelian groups when restricting to the Σ-algebra on the set of all finite abelian groups that is generated by uniform properties.

In this paper, I will introduce a link between the volume of a finite abelian p -group in the Cohen–Lenstra measure and partitions of a certain type. These partitions will be classified by the output of an algorithm. As a corollary, I will give a formula (7.2) for the probability of a p -group to have a specific exponent.

We regard the problem of communication in the presence of faulty transmissions. In contrast to the classical works in this area, we assume some structure on the times when the faults occur. More realistic seems the model that all faults occur in some small time interval. Like previous work, our problem can best be modelled as a two-player perfect information game, in which one player (“Paul”) has to guess a number x from { 1 , … , n } using Yes/No-questions, which the second player (“Carole”) has to answer truthfully apart from few lies. In our setting, all lies have to be in a consecutive set of k rounds. We show that, for large n, Paul needs roughly log n + log log 2 n + k rounds to determine the number, which is only k more than the case of just one single lie. Our main theorem (1.1) gives precise upper and lower bounds which differ only by a (small) constant.

International audience; 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.We provide several examples for which the elitist black-box complexity is exponentially larger than that 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 F can be smaller by an exponential factor than its typically regarded Las Vegas complexity (which measures the expected time it takes to optimize F).

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.

In this work we study a diffusion process in a network that consists of two types of vertices: inhibitory vertices those obstructing the diffusion and excitatory vertices those facilitating the diffusion. We consider a continuous time model in which every edge of the network draws its transmission time randomly. For such an asynchronous diffusion process it has been recently proven that in Erdi¾?s-Renyi random graphs a normalization phenomenon arises: whenever the diffusion starts from a large enough but still tiny set of active vertices, it only percolates to a certain level that depends only on the activation threshold and the ratio of inhibitory to excitatory vertices. In this paper we extend this result to all networks in which the percolation process exhibits an explosive behaviour. This includes in particular inhomogeneous random networks, as given by Chung-Lu graphs with degree parameter $$\beta \in 2,3$$.

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.

We regard the problem of communication in the presence of faulty transmissions. In contrast to the classical works in this area, we assume some structure on the times when the faults occur. More realistic seems the “burst error model”, in which all faults occur in some small time interval. Like previous work, our problem can best be modelled as a two-player perfect information game, in which one player (“Paul”) has to guess a number x from {1, ..., n} using Yes/No-questions, which the second player (“Carole”) has to answer truthfully apart from few lies. In our setting, all lies have to be in a consecutive set of k rounds. We show that (for big n) Paul needs roughly logn+loglogn+k rounds to determine the number, which is only k more than the case of just one single lie.

In number theory, great efforts have been undertaken to study the Cohen–Lenstra probability measure on the set of all finite abelian p-groups. On the other hand, group theorists have studied a probability measure on the set of all partitions induced by the probability that a randomly chosen n×n-matrix over Fp is contained in a conjugacy class associated with this partitions, for n→∞.This paper shows that both probability measures are identical. As a consequence, a multitude of results can be transferred from each theory to the other one. The paper contains a survey about the known methods to study the probability measure and about the results that have been obtained so far, from both communities.