
Krejca, Martin S.; Witt, Carsten Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax. Foundations of Genetic Algorithms (FOGA) 2017: 6579
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 \(Omega (\mu \sqrt n + n \log n)\), where \(\mu\) 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 blackbox 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.

Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew Michael Resampling vs Recombination: a Statistical Run Time Estimation. Foundations of Genetic Algorithms (FOGA) 2017: 2535
Noise is pervasive in realworld optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noisehandling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudoBoolean functions under additive posterior Gaussian noise and explore the tradeo between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutationonly evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speedup, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDAlike algorithms require no resampling, and can handle noise implicitly.

Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Foundations of Genetic Algorithms (FOGA) 2017: 4554
Linear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective function and the constraint is given by the OneMax function and present upper bounds as well as lower bounds for the general case. Furthermore, we also consider the LeadingOnes fitness function.

Pourhassan, Mojgan; Friedrich, Tobias; Neumann, Frank On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms. Foundations of Genetic Algorithms (FOGA) 2017: 3744
We consider the weighted minimum vertex cover problem and investigate how its dual formulation can be exploited to design evolutionary algorithms that provably obtain a 2approximation. Investigating multivalued representations, we show that variants of randomized local search and the (1+1) EA achieve this goal in expected pseudopolynomial time. In order to speed up the process, we consider the use of step size adaptation in both algorithms and show that RLS obtains a 2approximation in expected polynomial time while the (1+1) EA still encounters a pseudopolynomial lower bound.

Bringmann, Karl; Friedrich, Tobias Don't be greedy when calculating hypervolume contributions. Foundations of Genetic Algorithms (FOGA) 2009: 103112
Most hypervolume indicator based optimization algorithms like SIBEA [Zitzler et al. 2007], SMSEMOA [Beume et al. 2007], or MOCMAES [Igel et al. 2007] remove the solution with the smallest loss with respect to the dominated hypervolume from the population. This is usually iterated \(\lambda\) times until the size of the population no longer exceeds a fixed size \(\mu\). We show that there are populations such that the contributing hypervolume of the \(\lambda\) solutions chosen by this greedy selection scheme can be much smaller than the contributing hypervolume of an optimal set of \(\lambda\) solutions. Selecting the optimal \(\lambda\)set implies calculating \(\frac{\mu + \lambda}{\mu}\) conventional hypervolume contributions, which is considered computationally too expensive. We present the first hypervolume algorithm which calculates directly the contribution of every set of \(\lambda\) solutions. This gives an additive term of \(\frac{\mu + \lambda}{\mu}\) in the runtime of the calculation instead of a multiplicative factor of binomial \(\frac{\mu + \lambda}{\mu}\) . Given a population of size\(n = \mu + \lambda \) our algorithm can calculate a set of \(\lambda \geq 1 \) solutions with minimal ddimensional hypervolume contribution in time \(O(n^{d/2 \log n + n^\lambda)\) for \(d > 2\). This improves all previously published algorithms by a factor of order \(n^{\min(\lambda, d/2)}\) for \(d > 3\). Therefore even if we remove the solutions one by one greedily as usual, we gain a speedup factor of \(n\) for all \(d > 3\).

Baswana, Surender; Biswas, Somenath; Doerr, Benjamin; Friedrich, Tobias; Kurur, Piyush P.; Neumann, Frank Computing Single Source Shortest Paths using SingleObjective Fitness Functions. Foundations of Genetic Algorithms (FOGA) 2009: 5966
Runtime analysis of evolutionary algorithms has become an important part in the theoretical analysis of randomized search heuristics. The first combinatorial problem where rigorous runtime results have been achieved is the wellknown single source shortest path (SSSP) problem. Scharnow, Tinnefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multiobjective approach which solves the problem in expected polynomial time. They also suggest a related singleobjective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multiobjective fitness functions for problems like the SSSP yield more efficient evolutionary algorithms. In this paper, we show that the single objective approach yields an efficient (1+1) EA with runtime bounds very close to those of the multiobjective approach.