A suitable choice of the representation of candidate solutions is crucial for the efficiency of evolutionary algorithms and related metaheuristics. We focus on problems in permutation spaces, which are at the core of numerous practical applications of such algorithms, e.g., in scheduling and transportation. Inversion vectors (also called Lehmer codes) are an alternative representation of the permutation space S(n) compared to the classical encoding as a vector of n unique entries. In particular, they do not require any constraint handling. Using rigorous mathematical runtime analyses, we compare the efficiency of inversion vector encodings to the classical representation and give theory-guided advice on their choice. Moreover, we link the effect of local changes in the inversion code space to classical measures on permutations like the number of inversions. Finally, through experimental studies on linear ordering and quadratic assignment problems, we demonstrate the practical efficiency of inversion vector encodings.

Estimation of distribution algorithms (EDAs) are powerful optimization techniques that iteratively build probabilistic models based on the best performing solutions, thereby guiding the search process in complex solution landscapes. Classical EDAs handle only binary decision variables, but recent developments have introduced multi-valued EDAs to tackle problems with variables taking more than two values. Despite their growing importance, the theoretical understanding of multi-valued EDAs, especially regarding runtime behavior, remains limited. In this work, we provide theoretical analyses of the multi-valued compact genetic algorithm ( r ‑cGA) on the generalized (multi-valued) LeadingOnes and OneMax benchmark problems. We derive the first runtime bound for the r ‑cGA on the r -valued LeadingOnes function, together with an improved runtime for the r -valued OneMax function. These results also improve and refine previous theoretical analyses of the r ‑cGA, providing new insights into the performance of multi-valued EDAs. In addition, we for the first time include the case of frequency borders in the runtime analysis of the r ‑cGA.

The Compact Genetic Algorithm (cGA) is an estimation-of-distribution algorithm that has been receiving much attention especially in the runtime analysis community in recent years. It comes with a single parameter K determining its strength of updates. Contrary to other estimation-of-distribution algorithms like the UMDA, the standard cGA does not have a parameter controlling its selection pressure.

Populations play a key role in the area of evolutionary computation to tackle complex optimization problems. Nevertheless, it is hard to understand the underlying population dynamics from a theoretical perspective, and only a limited number of theoretical results for population-based algorithms are available even for simple benchmark functions. In this paper, we study the classic (μ+1) EA on the benchmark problem BinVal, which allows for exponentially many function values. Previous methods for the analysis, based on fitness levels and multiplicative drift analysis, lead to runtime bounds for this function of size n that include an additive term of Θ(n2). We provide new insights into how this standard algorithm optimizes BinVal, and we provide runtime bounds that are polynomial in the population size μ and do not include this additive term. In particular, we prove bounds on the expected runtime that are O(μ5n log (n/μ4)) for standard bit mutation, which is O(n log n) for constant μ. Our analysis considers the population dynamics of the (μ+1) EA more closely, proving that copies created by mutation lead to a low diversity in short blocks of bits across all individuals. We extend this method to mutation operators that cannot create duplicates, and prove bounds similar to standard bit mutation.

Recent research in the runtime analysis of estimation of distribution algorithms (EDAs) has focused on univariate EDAs for multi-valued decision variables. In particular, the runtime of the multi-valued cGA (r-cGA) and UMDA on multi-valued functions has been a significant area of study. Adak and Witt (PPSN 2024) and Hamano et al. (ECJ 2024) independently performed a first runtime analysis of the r-cGA on the r-valued OneMax function (r-OneMax). Adak and Witt also introduced a different r-valued OneMax function called G-OneMax. However, for that function, only empirical results were provided so far due to the increased complexity of its runtime analysis, since r-OneMax involves categorical values of two types only, while G-OneMax encompasses all possible values.

Abstract Estimation of distribution algorithms (EDAs) are general-purpose optimizers that maintain a probability distribution over a given search space. This probability distribution is updated through sampling from the distribution and a reinforcement learning process which rewards solution components that have shown to be part of good quality samples. The compact genetic algorithm (cGA) is a non-elitist EDA able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. We investigate the cGA on the Cliff function for which it was shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the Cliff function and investigate its dynamics both experimentally and theoretically. Our experimental results indicate that the cGA requires exponential time for all values of the update strength 1/K. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for K where the expected optimization time drops from $$n^{\Theta (n)}$$ n Θ ( n ) to $$2^{\Theta (n)}$$ 2 Θ ( n ) .

Chance-constrained optimization problems allow us to model problems where constraints involving stochastic components should be violated only with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high-quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance-constrained optimization. We study the scenario of stochastic components that are independent and normally distributed. Considering the simple single-objective (1+1) EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multiobjective formulation of the problem which trades off the expected cost and its variance. We show that multiobjective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance-constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multiobjective formulation, we propose and analyze improved convex multiobjective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multiobjective and the improved convex multiobjective approach in practice.

In the field of neuroevolution (NE), evolutionary algorithms are used to update the weights, biases and topologies of artificial neural networks (ANNs). A recent theoretical work presented the first runtime analysis of NE in a simple setting, considering a single neuron and intuitive benchmark function classes. However, this work was limited by the unrealistic settings with regard to activation functions and fitness measurements.

We propose a new, flexible approach for dynamically maintaining successful mutation rates in evolutionary algorithms using k-bit flip mutations. The algorithm adds successful mutation rates to an archive of promising rates that are favored in subsequent steps. Rates expire when their number of unsuccessful trials has exceeded a threshold, while rates currently not present in the archive can enter it in two ways: (i) via user-defined minimum selection probabilities for rates combined with a successful step or (ii) via a stagnation detection mechanism increasing the value for a promising rate after the current bit-flip neighborhood has been explored with high probability. For the minimum selection probabilities, we suggest different options, including heavy-tailed distributions.

Abstract We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (Automata, Languages and Programming, ICALP, Berlin, 2005). More precisely, denoting by $$n, m, w_{\max }$$ n , m , w max , and $$w_{\min }$$ w min the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature $$T_0 \ge w_{\max }$$ T 0 ≥ w max and multiplicative cooling schedule with factor $$1-1/\ell $$ 1 - 1 / ℓ , where $$\ell = \omega (mn\ln (m))$$ ℓ = ω ( m n ln ( m ) ) , with probability at least $$1-1/m$$ 1 - 1 / m computes in time $$O(\ell (\ln \ln (\ell ) + \ln (T_0/w_{\min }) ))$$ O ( ℓ ( ln ln ( ℓ ) + ln ( T 0 / w min ) ) ) a spanning tree with weight at most $$1+\kappa $$ 1 + κ times the optimum weight, where $$1+\kappa = \frac{(1+o(1))\ln (\ell m)}{\ln (\ell ) -\ln (mn\ln (m))}$$ 1 + κ = ( 1 + o ( 1 ) ) ln ( ℓ m ) ln ( ℓ ) - ln ( m n ln ( m ) ) . Consequently, for any $$\epsilon >0$$ ϵ > 0 , we can choose $$\ell $$ ℓ in such a way that a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation is found in time $$O((mn\ln (n))^{1+1/\epsilon +o(1)}(\ln \ln n + \ln (T_0/w_{\min })))$$ O ( ( m n ln ( n ) ) 1 + 1 / ϵ + o (

Abstract Stagnation detection has been proposed as a mechanism for randomized search heuristics to escape from local optima by automatically increasing the size of the neighborhood to find the so-called gap size, i. e., the distance to the next improvement. Its usefulness has mostly been considered in simple multimodal landscapes with few local optima that could be crossed one after another. In multimodal landscapes with a more complex location of optima of similar gap size, stagnation detection suffers from the fact that the neighborhood size is frequently reset to 1 without using gap sizes that were promising in the past. In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully by giving preference to values that were successful in the past. We implement this idea in an algorithm called SD-RLS $$^{\text {m}}$$ m and show compared to previous variants of stagnation detection that it yields speed-ups for linear functions under uniform constraints and the minimum spanning tree problem. Moreover, its running time does not significantly deteriorate on unimodal functions and a generalization of the Jump benchmark. Finally, we present experimental results carried out to study SD-RLS $$^{\text {m}}$$ m and compare it with other algorithms.

Pareto optimization using evolutionary multi-objective algorithms such as the classical GSEMO algorithm has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime of the classical GSEMO algorithm and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings.

We consider a simple setting in neuroevolution where an evolutionary algorithm optimizes the weights and activation functions of a simple artificial neural network. We then define simple example functions to be learned by the network and conduct rigorous runtime analyses for networks with a single neuron and for a more advanced structure with several neurons and two layers. Our results show that the proposed algorithm is generally efficient on two example problems designed for one neuron and efficient with at least constant probability on the example problem for a two-layer network. In particular, the so-called harmonic mutation operator choosing steps of size j with probability proportional to 1/j turns out as a good choice for the underlying search space. However, for the case of one neuron, we also identify situations with hard-to-overcome local optima. Experimental investigations of our neu-roevolutionary algorithm and a state-of-the-art CMA-ES support the theoretical findings.

Evolutionary multi-objective algorithms have successfully been used in the context of Pareto optimization where a given constraint is relaxed into an additional objective. In this paper, we explore the use of 3-objective formulations for problems with chance constraints. Our formulation trades off the expected cost and variance of the stochastic component as well as the given deterministic constraint. We point out benefits that this 3-objective formulation has compared to a bi-objective one recently investigated for chance constraints with Normally distributed stochastic components. Our analysis shows that the 3-objective formulation allows to compute all required trade-offs using 1-bit flips only, when dealing with a deterministic cardinality constraint. Furthermore, we carry out experimental investigations for the chance constrained dominating set problem and show the benefit for this classical NP-hard problem.

The Metropolis algorithm (MA) is a classic stochastic local search heuristic. It avoids getting stuck in local optima by occasionally accepting inferior solutions. To better and in a rigorous manner understand this ability, we conduct a mathematical runtime analysis of the MA on the CLIFF benchmark. Apart from one local optimum, cliff functions are monotonically increasing towards the global optimum. Consequently, to optimize a cliff function, the MA only once needs to accept an inferior solution. Despite seemingly being an ideal benchmark for the MA to profit from its main working principle, our mathematical runtime analysis shows that this hope does not come true. Even with the optimal temperature (the only parameter of the MA), the MA optimizes most cliff functions less efficiently than simple elitist evolutionary algorithms (EAs), which can only leave the local optimum by generating a superior solution possibly far away. This result suggests that our understanding of why the MA is often very successful in practice is not yet complete. Our work also suggests to equip the MA with global mutation operators, an idea supported by our preliminary experiments.

Recently a mechanism called stagnation detection was proposed that automatically adjusts the mutation rate of evolutionary algorithms when they encounter local optima. The so-called SD-(1+1) EA introduced by Rajabi and Witt (2022) adds stagnation detection to the classical (1+1) EA with standard bit mutation. This algorithm flips each bit independently with some mutation rate, and stagnation detection raises the rate when the algorithm is likely to have encountered a local optimum. In this article, we investigate stagnation detection in the context of the k-bit flip operator of randomized local search that flips k bits chosen uniformly at random and let stagnation detection adjust the parameter k. We obtain improved runtime results compared with the SD-(1+1) EA amounting to a speedup of at least (1-o(1))2πm, where m is the so-called gap size, that is, the distance to the next improvement. Moreover, we propose additional schemes that prevent infinite optimization times even if the algorithm misses a working choice of k due to unlucky events. Finally, we present an example where standard bit mutation still outperforms the k-bit flip operator with stagnation detection.

The benefits of using crossover in crossing fitness gaps have been studied extensively in evolutionary computation. Recent runtime results show that majority-vote crossover is particularly efficient at optimizing the well-known Jump benchmark function that includes a fitness gap next to the global optimum. Also estimation-of-distribution algorithms (EDAs), which use an implicit crossover, are much more efficient on Jump than typical mutation-based algorithms. However, the allowed gap size for polynomial runtimes with EDAs is at most logarithmic in the problem dimension n. In this paper, we investigate variants of the Jump function where the gap is shifted and appears in the middle of the typical search trajectory. Such gaps can still be overcome efficiently in time O(nlog⁡n) by majority-vote crossover and an estimation-of-distribution algorithm, even for gap sizes almost n. However, if the global optimum is located in the gap instead of the usual all-ones string, majority-vote crossover would nevertheless approach the all-ones string and be highly inefficient. In sharp contrast, an EDA can still find such a shifted optimum efficiently. Thanks to a general property called fair sampling, the EDA will with high probability sample from almost every fitness level of the function, including levels in the gap, and sample the global optimum even though the overall search trajectory points towards the all-ones string. Finally, we derive limits on the gap size allowing efficient runtimes for the EDA.

The compact genetic algorithm (cGA) is a non-elitist estimation of distribution algorithm which has shown to be able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. In this paper, we investigate the cGA on the Cliff function for which it has been shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the Cliff function and investigate its dynamics both experimentally and theoretically around the Cliff. Our experimental results indicate that the cGA requires exponential time for all values of the update strength K. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for K where the expected optimization time drops from nΘ(n) to 2Θ(n).

Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We study the scenario of stochastic components that are independent and Normally distributed. Considering the simple single-objective (1+1)~EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We show that multi-objective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multi-objective approach in practice.

Abstract Recent progress in the runtime analysis of evolutionary algorithms (EAs) has allowed the derivation of upper bounds on the expected runtime of standard steady-state genetic algorithms (GAs). These upper bounds have shown speed-ups of the GAs using crossover and mutation over the same algorithms that only use mutation operators (i.e., steady-state EAs) both for standard unimodal (i.e., OneMax) and multimodal (i.e., Jump) benchmark functions. The bounds suggest that populations are beneficial to the GA as well as higher mutation rates than the default 1/n rate. However, making rigorous claims was not possible because matching lower bounds were not available. Proving lower bounds on crossover-based EAs is a notoriously difficult task as it is hard to capture the progress that a diverse population can make. We use a potential function approach to prove a tight lower bound on the expected runtime of the (2+1) GA for OneMax for all mutation rates c/n with $$c < 1.422$$ c < 1.422 . This provides the last piece of the puzzle that completes the proof that larger population sizes improve the performance of the standard steady-state GA for OneMax for various mutation rates, and it proves that the optimal mutation rate for the (2+1) GA on OneMax is $$(\sqrt{97}-5)/(4n) \approx 1.2122/n$$ ( 97 - 5 ) / ( 4 n ) ≈ 1.2122 / n .

The benefits of using crossover in crossing fitness gaps have been studied extensively in evolutionary computation. Recent runtime results show that majority-vote crossover is particularly efficient at optimizing the well-known Jump benchmark function that includes a fitness gap next to the global optimum. Also estimation-of-distribution algorithms (EDAs), which use an implicit crossover, are much more efficient on Jump than typical mutation-based algorithms. However, the allowed gap size for polynomial runtimes with EDAs is at most logarithmic in the problem dimension n.

Stagnation detection has been proposed as a mechanism for randomized search heuristics to escape from local optima by automatically increasing the size of the neighborhood to find the so-called gap size, i. e., the distance to the next improvement. Its usefulness has mostly been considered in simple multimodal landscapes with few local optima that could be crossed one after another. In multimodal landscapes with a more complex location of optima of similar gap size, stagnation detection suffers from the fact that the neighborhood size is frequently reset to 1 without using gap sizes that were promising in the past.

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.

We analyse the impact of the selective pressure for the global optimisation capabilities of steady-state evolutionary algorithms (EAs). For the standard bimodal benchmark function TwoMax , we rigorously prove that using uniform parent selection leads to exponential runtimes with high probability to locate both optima for the standard ( +1) EA and ( +1) RLS with any polynomial population sizes. However, we prove that selecting the worst individual as parent leads to efficient global optimisation with overwhelming probability for reasonable population sizes. Since always selecting the worst individual may have detrimental effects for escaping from local optima, we consider the performance of stochastic parent selection operators with low selective pressure for a function class called TruncatedTwoMax, where one slope is shorter than the other. An experimental analysis shows that the EAs equipped with inverse tournament selection, where the loser is selected for reproduction and small tournament sizes, globally optimise TwoMax efficiently and effectively escape from local optima of TruncatedTwoMax with high probability. Thus, they identify both optima efficiently while uniform (or stronger) selection fails in theory and in practice. We then show the power of inverse selection on function classes from the literature where populations are essential by providing rigorous proofs or experimental evidence that it outperforms uniform selection equipped with or without a restart strategy. We conclude the article by confirming our theoretical insights with an empirical analysis of the different selective pressures on standard benchmarks of the classical MaxSat and multidimensional knapsack problems.

Recent progress in the runtime analysis of evolutionary algorithms (EAs) has allowed the derivation of upper bounds on the expected runtime of standard steady-state GAs. These upper bounds have shown speed-ups of the GAs using crossover and mutation over the same algorithms that only use mutation operators (i.e., steady-state EAs) both for standard unimodal (i.e., OneMax) and multimodal (i.e., Jump) benchmark functions. These upper bounds suggest that populations are beneficial to the GA as well as higher mutation rates than the default 1/n rate. However, making rigorous claims was not possible because matching lower bounds were not available. Proving lower bounds on crossover-based EAs is a notoriously difficult task as it is hard to capture the progress that a diverse population can make. We use a potential function approach to prove a tight lower bound on the expected runtime of the (2 + 1) GA for OneMax for all mutation rates c/n with c < 1.422. This provides the last piece of the puzzle that completes the proof that larger population sizes improve the performance of the standard steady-state GA for OneMax for various mutation rates, and it proves that the optimal mutation rate for the (2 + 1) GA on OneMax is [EQUATION].

Recent theoretical research has shown that self-adjusting and self-adaptive mechanisms can provably outperform static settings in evolutionary algorithms for binary search spaces. However, the vast majority of these studies focuses on unimodal functions which do not require the algorithm to flip several bits simultaneously to make progress. In fact, existing self-adjusting algorithms are not designed to detect local optima and do not have any obvious benefit to cross large Hamming gaps.

The expected running time of the classical (1+1) EA on the ONEMAX benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of O((log n)/n). The same approach proposed there also leads to a full asymptotic expansion with errors of the form O(n-K log n) for any K > 0. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on ONE MAX and obtains that the expected running time E (T), starting from [n/2] one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely

In the last decade remarkable progress has been made in development of suitable proof techniques for analysing randomised search heuristics. The theoretical investigation of these algorithms on classes of functions is essential to the understanding of the underlying stochastic process. Linear functions have been traditionally studied in this area resulting in tight bounds on the expected optimisation time of simple randomised search algorithms for this class of problems. Recently, the constrained version of this problem has gained attention and some theoretical results have also been obtained on this class of problems. In this paper we study the class of linear functions under uniform constraint and investigate the expected optimisation time of Randomised Local Search (RLS) and a simple evolutionary algorithm called (1+1) EA. We prove a tight bound of Θ(n2) for RLS and improve the previously best known bound of (1+1) EA from O(n2 log(Bwmax)) to O(n2 log B) in expectation and to O(n2 log n) with high probability, where wmax and B are the maximum weight of the linear objective function and the bound of the uniform constraint, respectively.

The runtime analysis of evolutionary algorithms using crossover as search operator has recently produced remarkable results indicating benefits and drawbacks of crossover and illustrating its working principles. Virtually all these results are restricted to upper bounds on the running time of the crossover-based algorithms. This work addresses this lack of lower bounds and rigorously bounds the optimization time of simple algorithms using uniform crossover on the search space {0, 1}n from below via two novel techniques called decoupling and family graphs. First, a simple steady-state crossover-based evolutionary algorithm without selection pressure is analyzed and shown that after O(µ log µ) generations, bit positions are sampled almost independently with marginal probabilities corresponding to the fraction of one-bits at the corresponding position in the initial population. Afterwards, a crossover-based algorithm using tournament selection is analyzed by a novel generalization of the family tree technique originally introduced for mutation-only EAs. Using these so-called family graphs, almost tight lower bounds on the optimization time on the OneMax benchmark function are shown.

Probabilistic model-building Genetic Algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size 1 / K in the so-called compact Genetic Algorithm (cGA) and the evaporation factor $$\rho $$ in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of $${\varOmega }(K\sqrt{n} + n \log n)$$ and $${\varOmega }(\sqrt{n}/\rho + n \log n)$$ , respectively, suggesting that the update strength should be limited to $$1/K, \rho = O(1/(\sqrt{n} \log n))$$ . In fact, choosing $$1/K, \rho \sim 1/(\sqrt{n}\log n)$$ both algorithms efficiently optimize OneMax in expected time $${\varTheta }(n \log n)$$ . Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization.

We propose and analyze a self-adaptive version of the (1, λ) evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of O(nλ/log λ + n log n). This time is asymptotically smaller than the optimization time of the classic (1, λ) EA and (1 + λ) EA for all static mutation rates and best possible among all λ-parallel mutation-based unbiased black-box algorithms.

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.

In the theory community of evolutionary computation, linear pseudo-boolean functions are often regarded as easy problems since all of them can be optimized in expected time O(n log n) by simple unbiased algorithms. However, results from genetic algorithms and estimation-of-distribution algorithms indicate that these algorithms treat different linear functions differently. More precisely, an effect called "domino convergence" is described in the literature, which means that bits of large weight in the linear function are optimized earlier than bits of low weight. Hence, different linear functions may lead to rather different expected optimization times.

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 $$\lambda $$ 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.

The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring.

A runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) is presented on the OneMax function for wide ranges of the parameters μ and λ. If μ ≥ c log n for some constant c > 0 and λ = (1 + Θ(1))μ, a general bound O(μn) on the expected runtime is obtained. This bound crucially assumes that all marginal probabilities of the algorithm are confined to the interval [1/n, 1 − 1/n]. If [EQUATION] log n for a constant c' > 0 and λ = (1 + Θ(1))μ, the behavior of the algorithm changes and the bound on the expected runtime becomes [EQUATION], which typically even holds if the borders on the marginal probabilities are omitted.

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.

We study the (1+λ) EA with mutation probability c/n, where c>0 is a constant, on the OneMax problem. Using an improved variable drift theorem, 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 introduce a simplified island model with behavior similar to the λ (1+1) islands optimizing the Maze fitness function, and investigate the effects of the migration topology on the ability of the simplified island model to track the optimum of a dynamic fitness function. More specifically, we prove that there exist choices of model parameters for which using a unidirectional ring as the migration topology allows the model to track the oscillating optimum through n Maze-like phases with high probability, while using a complete graph as the migration topology results in the island model losing track of the optimum with overwhelming probability. Additionally, we prove that if migration occurs only rarely, denser migration topologies may be advantageous. This serves to illustrate that while a less-dense migration topology may be useful when optimizing dynamic functions with oscillating behavior, and requires less problem-specific knowledge to determine when migration may be allowed to occur, care must be taken to ensure that a sufficient amount of migration occurs during the optimization process.

We provide a rigorous runtime analysis concerning the update strength, a vital parameter in probabilistic model-building GAs such as the step size 1/K in the compact Genetic Algorithm (cGA) and the evaporation factor ρ in ACO. While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to genetic drift and poor performance. We demonstrate this trade-off for the cGA and a simple MMAS ACO algorithm on the OneMax function. More precisely, we obtain lower bounds on the expected runtime of Ω(K√n + n log n) and Ω(√n/ρ + n log n), respectively, showing that the update strength should be limited to 1/K, ρ = O(1/(√n log n)). In fact, choosing 1/K, ρ sim 1/(√n log n) both algorithms efficiently optimize OneMax in expected time O(n log n). Our analyses provide new insights into the stochastic behavior of probabilistic model-building GAs and propose new guidelines for setting the update strength in global optimization.

Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension.

The (1+1) 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 λ. It turns out that 1/n is the only optimal mutation probability if λ=o(ln n ln ln n/ln ln ln n), which is the cut-off point for linear mnspeed-up. However, if λ 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.

A simple island model with λ islands and migration occurring after every τ iterations is studied on the dynamic fitness function Maze. This model is equivalent to a (1+λ) EA if τ=1, i.e., migration occurs during every iteration. It is proved that even for an increased offspring population size up to λ=O(n1-ε), the (1+λ) EA is still not able to track the optimum of Maze. If the migration interval is increased, the algorithm is able to track the optimum even for logarithmic λ. Finally, the relationship of τ, λ, and the ability of the island model to track the optimum is investigated more closely.

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 (PPSN 2012, 113--122), in polynomial time. This is then generalized to a hierarchy result stating that for every μ, a (μ+1) EA with genotype diversity is able to track a Maze function extended over a finite alphabet of μ symbols, whereas population size μ-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.

We revisit the classical analysis of the (1+1) EA for the minimum spanning tree problem in the case that nothing is known about the weights of the underlying graph. Here the original upper bound on the expected running time by Neumann and Wegener [Theor. Comput. Sci. 378(1), 32-40, 2007], which depends on the largest weight of the graph, is of no use. The best upper bound available before in this case is due to Reichel and Skutella [FOGA 2009, 21-28] and is of order O(m3 \log n), where m is the number of edges and n the number of vertices. Using an adaptive drift analysis, we show the improved bound O(m2 (sqrt{c(G)} + \log n)), where c(G) is the circumference (length of the longest cycle) of the graph. This is only by an asymptotic factor of at most sqrt{n}/\log n away from the classical lower bound. Furthermore, an alternative fitness function leading to the bound O(m2\log n) is proposed, and limitations of the adaptive drift analysis are pointed out.

Separable functions are composed of subfunctions that depend on mutually disjoint sets of bits. These subfunctions can be optimized independently, however in black-box optimization this direct approach is infeasible as the composition of subfunctions may be unknown. Common belief is that evolutionary algorithms make progress on all subfunctions in parallel, so that optimizing a separable function does not take not much longer than optimizing the hardest subfunction---subfunctions are optimized "in parallel."

At last year's GECCO a novel perspective for theoretical performance analysis of evolutionary algorithms and other randomised search heuristics was introduced that concentrates on the expected function value after a pre-defined number of steps, called budget. This is significantly different from the common perspective where the expected optimisation time is analysed. While there is a huge body of work and a large collection of tools for the analysis of the expected optimisation time the new fixed budget perspective introduces new analytical challenges. Here it is shown how results on the expected optimisation time that are strengthened by deviation bounds can be systematically turned into fixed budget results. We demonstrate our approach by considering the (1+1) EA on LeadingOnes and significantly improving previous results. We prove that deviating from the expected time by an additive term of ω(n3/2 happens only with probability o(1). This is turned into tight bounds on the function value using the inverse function. We use three, increasingly strong or general approaches to proving the deviation bounds, namely via Chebyshev's inequality, via Chernoff bounds for geometric random variables, and via variable drift analysis.

A simple ACO algorithm called λ-MMAS for dynamic variants of the single-destination shortest paths problem is studied by rigorous runtime analyses. Building upon previous results for the special case of 1-MMAS, it is studied to what extent an enlarged colony using $\lambda$ ants per vertex helps in tracking an oscillating optimum. It is shown that easy cases of oscillations can be tracked by a constant number of ants. However, the paper also identifies more involved oscillations that with overwhelming probability cannot be tracked with any polynomial-size colony. Finally, parameters of dynamic shortest-path problems which make the optimum difficult to track are discussed. Experiments illustrate theoretical findings and conjectures.

A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of our previous one. Firstly, the new result holds for population sizes up to mu = n1/4-epsilon which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.

For many years it has been a challenge to analyze the time complexity of Genetic Algorithms (GAs) using stochastic selection together with crossover and mutation. This paper presents a rigorous runtime analysis of the well-known Simple Genetic Algorithm (SGA) for OneMax. It is proved that the SGA has exponential runtime with overwhelming probability for population sizes up to μ≤ n1/8-ε for some arbitrarily small constant ε and problem size n. To the best of our knowledge, this is the first time non-trivial lower bounds are obtained on the runtime of a standard crossover-based GA for a standard benchmark function. The presented techniques might serve as a first basis towards systematic runtime analyses of GAs.

The analysis of randomized search heuristics on classes of functions is fundamental for the understanding of the underlying stochastic process and the development of suitable proof techniques. Recently, remarkable progress has been made in bounding the expected optimization time of the simple (1+1) EA on the class of linear functions. We improve the best known bound in this setting from (1.39+o(1))(en ln n) to (en ln n)+O(n) in expectation and with high probability, which is tight up to lower-order terms. Moreover, upper and lower bounds for arbitrary mutations probabilities p are derived, which imply expected polynomial optimization time as long as p=O((ln n)/n) and which are tight if p=c/n for a constant c. As a consequence, the standard mutation probability p=1/n is optimal for all linear functions, and the (1+1) EA is found to be an optimal mutation-based algorithm. Furthermore, the algorithm turns out to be surprisingly robust since large neighborhood explored by the mutation operator does not disrupt the search.

We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp upper and lower bounds. As an application, we improve the results by Doerr et al. (GECCO~2010) in several respects. First, the upper bound on the expected running time of the most successful quasirandom evolutionary algorithm for the OneMax function is improved from 1.28n ln n to 0.982n ln n, which breaks the barrier of n ln n posed by coupon-collector processes. Compared to the classical 1+1-EA, whose runtime will for the first time be analyzed with respect to terms of lower order, this represents a speedup by more than a factor of e=2.71...

Motivated by recent successful applications of the concept of quasirandomness, we investigate to what extent such ideas can be used in evolutionary computation. To this aim, we propose different variations of the classical (1+1) evolutionary algorithm, all imitating the property that the (1+1) EA over intervals of time touches all bits roughly the same number of times. We prove bounds on the optimization time of these algorithms for the simple OneMax function. Surprisingly, none of the algorithms achieves the seemingly obvious reduction of the runtime from Θ( n log n ) to O(n) . On the contrary, one may even need Ω( n 2 ) time. However, we also find that quasirandom ideas, if implemented correctly, can yield an over 50% speed-up.

The complexity theory for black-box algorithms, introduced by Droste et al. (2006), describes common limits on the efficiency of a broad class of randomised search heuristics. There is an obvious trade-off between the generality of the black-box model and the strength of the bounds that can be proven in such a model. In particular, the original black-box model allows polynomial complexity for certain NP-complete problems and provides for well-known benchmark problems relatively small lower bounds, which are typically not met by popular search heuristics.

Ant colony optimization (ACO) has found many applications in different problem domains. We carry out a first rigorous runtime analysis of ACO with iteration-best update, where the best solution in the each iteration is reinforced. This is similar to comma selection in evolutionary algorithms. We compare ACO to evolutionary algorithms for which it is well known that an offspring size of Ω(log n), n the problem dimension, is necessary to optimize even simple functions like ONEMAX. In sharp contrast, ACO is efficient on ONEMAX even for the smallest possible number of two ants. Remarkably, this only holds if the pheromone evaporation rate is small enough; the collective memory of many ants stored in the pheromones makes up for the small number of ants. We further prove an exponential lower bound for ACO with iteration-best update that depends on a trade-off between the number of ants and the evaporation rate.

We investigate theoretically how the fitness landscape influences the optimization process of population-based evolutionary algorithms using fitness-proportional selection. Considering the function OneMax, we show that it cannot be optimized in polynomial time with high probability regardless of the population size. This is proved by a generalization of drift analysis. For populations of at most logarithmic size, the negative result transfers to any function with unique optimum. Based on these insights, we investigate the effect of scaling the objective function in combination with a population that is not too small and show that then such algorithms compute optimal solutions for a wide range of problems in expected polynomial time. Finally, relationships with (1+λ)-EAs and (1,λ)-EAs are described.

Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in finite time. We present the first runtime analysis of an ACO algorithm, which transfers many rigorous results with respect to the runtime of a simple evolutionary algorithm to our algorithm. Moreover, we examine the choice of the evaporation factor, a crucial parameter in ACO algorithms, in detail. By deriving new lower bounds on the tails of sums of independent Poisson trials, we determine the effect of the evaporation factor almost completely and prove a phase transition from exponential to polynomial runtime.

Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast, the theoretical understanding of the interplay of different optimization methods is rare. In this paper, we make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.

Maintaining diversity is important for the performance of evolutionary algorithms. Diversity-preserving mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the global exploration capabilities of mutation-based algorithms. Using a simple bimodal test function and rigorous runtime analyses, we compare well-known diversity-preserving mechanisms like deterministic crowding, fitness sharing, and others with a plain algorithm without diversification. We show that diversification is necessary for global exploration, but not all mechanisms succeed in finding both optima efficiently. Our theoretical results are accompanied by additional experiments for different population sizes.

March 01 2009 Ingo Wegener In Special Collection: CogNet Thomas Jansen, Thomas Jansen Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Melanie Schmidt, Melanie Schmidt Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Dirk Sudholt, Dirk Sudholt Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Carsten Witt, Carsten Witt Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Christine Zarges Christine Zarges Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Author and Article Information Thomas Jansen Ingo Wegener's group, Technische Universität Dortmund Melanie Schmidt Ingo Wegener's group, Technische Universität Dortmund Dirk Sudholt Ingo Wegener's group, Technische Universität Dortmund Carsten Witt Ingo Wegener's group, Technische Universität Dortmund Christine Zarges Ingo Wegener's group, Technische Universität Dortmund Online Issn: 1530-9304 Print Issn: 1063-6560 © 2009 by the Massachusetts Institute of Technology2009 Evolutionary Computation (2009) 17 (1): 1–2. https://doi.org/10.1162/evco.2009.17.1.1 Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn MailTo Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Thomas Jansen, Melanie Schmidt, Dirk Sudholt, Carsten Witt, Christine Zarges; Ingo Wegener. Evol Comput 2009; 17 (1): 1–2. doi: https://doi.org/10.1162/evco.2009.17.1.1 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsEvolutionary Computation Search Advanced Search This content is only available as a PDF. © 2009 by the Massachusetts Institute of Technology2009 Article PDF first page preview Close Modal You do not currently have access to this content.

Maintaining diversity is important for the performance of evolutionary algorithms. Diversity mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the global exploration capabilities of mutation-based algorithms. Using a simple bimodal test function and rigorous runtime analyses, we compare well-known diversity mechanisms like deterministic crowding, fitness sharing, and others with a plain algorithm without diversification. We show that diversification is necessary for global exploration, but not all mechanisms succeed in finding both optima efficiently.

We investigate the runtime of the Binary Particle Swarm Optimization (PSO) algorithm introduced by Kennedy and Eberhart (1997). The Binary PSO maintains a global best solution and a swarm of particles. Each particle consists of a current position, an own best position and a velocity vector used in a probabilistic process to update the particle's position. We present lower bounds for swarms of polynomial size. To prove upper bounds, we transfer a fitness-level argument well-established for evolutionary algorithms (EAs) to PSO. This method is applied to estimate the expected runtime on the class of unimodal functions. A simple variant of the Binary PSO is considered in more detail. The 1-PSO only maintains one particle, hence own best and global best solutions coincide. Despite its simplicity, the 1-PSO is surprisingly efficient. A detailed analysis for the function OneMax shows that the 1-PSO is competitive to EAs.

Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast to this the theoretical understanding of the interplay of different optimization methods is rare. The aim of this paper is to make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. These results, however, apply particularly to classical search heuristics such as Evolutionary Algorithms (EAs) and Simulated Annealing. First runtime analyses of modern search heuristics have been conducted only recently w.r.t a simple Ant Colony Optimization (ACO) algorithm called 1-ANT. In particular, the influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w.r.t the runtime behavior have been determined for the example function OneMax.This paper puts forward the rigorous runtime analysis of the 1-ANT on example functions, namely on the functions LeadingOnes and BinVal. With respect to EAs, such analyses have been essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice can be very crucial to allow efficient runtimes. Moreover, the analyses provide insight into the working principles of ACO algorithms and, in terms of their robustness, describe essential differences to other randomized search heuristics.

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical explorations on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare single-objective and multi-objective models for such problems. For the VertexCover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case, no good approximation can be achieved within the expected polynomial time. Examining the more general SetCover problem, we show that optimal solutions can be approximated within a logarithmic factor of the size of the ground set, using the multi-objective approach, while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.

Various methods have been defined to measure the hardness of a fitness function for evolutionary algorithms and other black-box heuristics. Examples include fitness landscape analysis, epistasis, fitness-distance correlations etc., all of which are relatively easy to describe. However, they do not always correctly specify the hardness of the function. Some measures are easy to implement, others are more intuitive and hard to formalize. This paper rigorously defines difficulty measures in black-box optimization and proposes a classification. Different types of realizations of such measures are studied, namely exact and approximate ones. For both types of realizations, it is proven that predictive versions that run in polynomial time in general do not exist unless certain complexity-theoretical assumptions are wrong.

Although Evolutionary Algorithms (EAs) have been successfully applied to optimization in discrete search spaces, theoretical developments remain weak, in particular for population-based EAs. This paper presents a first rigorous analysis of the (μ + 1) EA on pseudo-Boolean functions. Using three well-known example functions fromthe analysis of the (1 + 1) EA, we derive bounds on the expected runtime and success probability. For two of these functions, upper and lower bounds on the expected runtime are tight, and on all three functions, the (μ + 1) EA is never more efficient than the (1 + 1) EA. Moreover, all lower bounds growwith μ. On a more complicated function, however, a small increase of μ provably decreases the expected runtime drastically. This paper develops a newproof technique that bounds the runtime of the (μ + 1) EA. It investigates the stochastic process for creating family trees of individuals; the depth of these trees is bounded. Thereby, the progress of the population towards the optimum is captured. This new technique is general enough to be applied to other population-based EAs.

Evolutionary algorithms (EAs) are general, randomized search heuristics applied successfully to optimization problems both in discrete and in continuous search spaces. In recent years, substantial progress has been made in theoretical runtime analysis of EAs, in particular for pseudo-Boolean fitness functions f:(0,1)n → R. Compared to this, little is known about the runtime of simple and, in particular, more complex EAs for continuous functions f: Rn → R.In this paper, a first rigorous runtime analysis of a population-based EA in continuous search spaces is presented. A simple (μ+1) evolution strategy ((μ+1)ES) that uses Gaussian mutations adapted by the 1/5-rule as its search operator is studied on the well-known Sphere functionand the influence of μ and n on its runtime is examined. By generalizing the proof technique of randomized family trees, developed before w.r.t. discrete search spaces, asymptotically upper and lower bounds on the time for the population to make a predefined progress are derived. Furthermore, the utility of the 1/5-rule in population-based evolution strategies is shown. Finally, the behavior of the (μ+1)ES on multimodal functions is discussed.

Evolutionary algorithms (EA) finds numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often concentrates on very simple algorithms like the (1+1) EA, where population size equals 1. In this paper, the question is addressed whether the use of a population by itself can be advantageous. A population-based EA does neither make use of crossover nor any diversity-maintaining operator is investigated on an example function. It is shown that an increase of the population size by polynomial factor decreases the expected runtime exponential to polynomial. Thereby, the so far best known gap is improved from superpolynomial to exponential. Moreover, it is proved that the stated runtime bounds occur with a probability exponentially close to one. Finally, a second example function is presented, where opposite results hold.