Search

Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of evolutionary algorithms which use non-trivial populations remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the (μ + λ) evolutionary algorithm on the simple OneMax benchmark function, only the special cases μ = 1 and λ = 1 have been solved. In this work, we analyze this long-standing problem and show the asymptotically tight result that the runtime T, the number of iterations until the optimum is found, satisfies E [ T ] = Θ ( n log n λ + n λ / μ + n log + log + (λ / μ) log + (λ / μ) ) , where log + x : = max { 1 , log x } for all x > 0 . The same methods allow to improve the previous-best O (n log n λ + n log λ) runtime guarantee for the (λ + λ) EA with fair parent selection to a tight Θ (n log n λ + n) runtime result. [ABSTRACT FROM AUTHOR]

Island models denote a distributed system of evolutionary algorithms which operate independently, but occasionally share their solutions with each other along the so-called migration topology. We investigate the impact of the migration topology by introducing a simplified island model with behavior similar to λ islands optimizing the so-called MAZE fitness function (Kötzing and Molter in Proceedings of parallel problem solving from nature (PPSN XII), Springer, Berlin, pp 113-122, 2012). Previous work has shown that when a complete migration topology is used, migration must not occur too frequently, nor too soon before the optimum changes, to track the optimum of the MAZE function. We show that using a sparse migration topology alleviates these restrictions. More specifically, we prove that there exist choices of model parameters for which using a unidirectional ring of logarithmic diameter as the migration topology allows the model to track the oscillating optimum through n MAZE-like phases with high probability, while using any graph of diameter less than c ln n for some sufficiently small constant c > 0 results in the island model losing track of the optimum with overwhelming probability. Experimentally, we show that very frequent migration on a ring topology is not an effective diversity mechanism, while a lower migration rate allows the ring topology to track the optimum for a wider range of oscillation patterns. When migration occurs only rarely, we prove that dense migration topologies of small diameter may be advantageous. Combined, our results show that the sparse migration topology is able to track the optimum through a wider range of oscillation patterns, and cope with a wider range of migration frequencies. [ABSTRACT FROM AUTHOR]

We study the (1+λ) EA, a classical population-based evolutionary algorithm, with mutation probability c/n, where c > 0 and λ are constant, on the benchmark function OneMax, which counts the number of 1-bits in a bitstring. We improve a well-established result that allows to determine the first hitting time from the expected progress (drift) of a stochastic process, known as the variable drift theorem. Using our improved result, we show that upper and lower bounds on the expected runtime of the (1+λ) EA obtained from variable drift theorems are at most apart by a small lower order term if the exact drift is known. This reduces the analysis of expected optimization time to finding an exact expression for the drift. We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+λ) EA for various parameter settings of c and λ and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize c for fixed n and λ for the optimization of ONEMAX unnecessary. Interestingly, even for moderate n and not too small λ it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1/n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1/n with the optimal mutation rate. [ABSTRACT FROM AUTHOR]

The ( $$1+\lambda $$ ) EA with mutation probability c / n, where $$c>0$$ is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and $$\lambda $$ . It turns out that 1 / n is the only optimal mutation probability if $$\lambda =o(\ln n\ln \ln n/\ln \ln \ln n)$$ , which is the cut-off point for linear speed-up. However, if $$\lambda $$ is above this cut-off point then the standard mutation probability 1 / n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The theoretical results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds. Experimental supplements shed light on the optimal mutation probability for small problem sizes. [ABSTRACT FROM AUTHOR]

A simple island model with $$\lambda $$ islands and migration occurring after every $$\tau $$ iterations is studied on the dynamic fitness function Maze. This model is equivalent to a $$(1+\lambda )$$ EA if $$\tau =1$$ , i. e., migration occurs during every iteration. It is proved that even for an increased offspring population size up to $$\lambda =O(n^{1-\epsilon })$$ , the $$(1+\lambda )$$ EA is still not able to track the optimum of Maze. If the migration interval is chosen carefully, the algorithm is able to track the optimum even for logarithmic $$\lambda $$ . The relationship of $$\tau , \lambda $$ , and the ability of the island model to track the optimum is then investigated more closely. Finally, experiments are performed to supplement the asymptotic results, and investigate the impact of the migration topology. [ABSTRACT FROM AUTHOR]

We study the behavior of a population-based EA and the Max-Min Ant System (MMAS) on a family of deterministically-changing fitness functions, where, in order to find the global optimum, the algorithms have to find specific local optima within each of a series of phases. In particular, we prove that a (2+1) EA with genotype diversity is able to find the global optimum of the Maze function, previously considered by Kötzing and Molter [9], in polynomial time. This is then generalized to a hierarchy result stating that for every $$\mu $$ , a ( $$\mu $$ +1) EA with genotype diversity is able to track a Maze function extended over a finite alphabet of $$\mu $$ symbols, whereas population size $$\mu -1$$ is not sufficient. Furthermore, we show that MMAS does not require additional modifications to track the optimum of the finite-alphabet Maze functions, and, using a novel drift statement to simplify the analysis, reduce the required phase length of the Maze function. [ABSTRACT FROM AUTHOR]

We consider stochastic versions of OneMax and LeadingOnes and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the ( $$1+1$$ ) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size $$\varTheta (\log n)$$ ) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the ( $$1+1$$ ) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings. [ABSTRACT FROM AUTHOR]