2025 [ nach oben ]

Krejca, Martin S.; Neumann, Frank; Witt, Carsten Population Dynamics and Improved Runtime Guarantees for the (µ+1) EA on BinValFoundations of Genetic Algorithms (FOGA) 2025: 142–153
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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+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 \(\Theta(n^2)\). We provide new insights into how this standard algorithm optimizes BinVal, and we provide runtime bounds that are polynomial in the population size \(\mu\) and do not include this additive term. In particular, we prove bounds on the expected runtime that are \(O(mu^5 n\log(n/\mu^4))\) for standard bit mutation, which is \(O(n \log n)\) for constant \(\mu\). Our analysis considers the population dynamics of the \((1+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.
@inproceedings{krejca2025population, abstract = {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+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 \(\Theta(n^2)\). We provide new insights into how this standard algorithm optimizes BinVal, and we provide runtime bounds that are polynomial in the population size \(\mu\) and do not include this additive term. In particular, we prove bounds on the expected runtime that are \(O(\mu^5 n\log(n/\mu^4))\) for standard bit mutation, which is \(O(n \log n)\) for constant \(\mu\). Our analysis considers the population dynamics of the \((1+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.}, author = {Krejca, Martin S. and Neumann, Frank and Witt, Carsten}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {carstenwitt foga frankneumann martinskrejca solelyextern year2025}, pages = {142-153}, title = {Population Dynamics and Improved Runtime Guarantees for the (µ+1) EA on BinVal}, year = 2025 }

2017 [ nach oben ]

Krejca, Martin S.; Witt, Carsten Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMaxFoundations of Genetic Algorithms (FOGA) 2017: 65–79
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 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.
@inproceedings{DBLP:conf/foga/KrejcaW17, abstract = {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 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.}, author = {Krejca, Martin S. and Witt, Carsten}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {foga martinskrejca year2017}, pages = {65-79}, publisher = {ACM Press}, title = {Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax}, year = 2017 }

Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew Michael Resampling vs Recombination: a Statistical Run Time EstimationFoundations of Genetic Algorithms (FOGA) 2017: 25–35
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling 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 pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-o 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 mutation-only 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 speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.
@inproceedings{DBLP:conf/foga/0001KQS17, abstract = {Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling 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 pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-o 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 mutation-only 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 speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew Michael}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {andrewmsutton foga francescoquinzan timokoetzing tobiasfriedrich year2017}, pages = {25-35}, title = {Resampling vs Recombination: a Statistical Run Time Estimation}, year = 2017 }

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 ConstraintsFoundations of Genetic Algorithms (FOGA) 2017: 45–54
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/foga/0001KLNS17, abstract = {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.}, author = {Friedrich, Tobias and Kötzing, Timo and Lagodzinski, J. A. Gregor and Neumann, Frank and Schirneck, Martin}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {foga frankneumann gregorlagodzinski martinschirneck timokoetzing tobiasfriedrich year2017}, pages = {45-54}, publisher = {ACM Press}, title = {Analysis of the {(1+1)} EA on Subclasses of Linear Functions under Uniform and Linear Constraints}, year = 2017 }

Pourhassan, Mojgan; Friedrich, Tobias; Neumann, Frank On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary AlgorithmsFoundations of Genetic Algorithms (FOGA) 2017: 37–44
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 2-approximation. Investigating multi-valued representations, we show that variants of randomized local search and the (1+1) EA achieve this goal in expected pseudo-polynomial 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 2-approximation in expected polynomial time while the (1+1) EA still encounters a pseudo-polynomial lower bound.
@inproceedings{DBLP:conf/foga/Pourhassan0N17, abstract = {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 2-approximation. Investigating multi-valued representations, we show that variants of randomized local search and the (1+1) EA achieve this goal in expected pseudo-polynomial 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 2-approximation in expected polynomial time while the (1+1) EA still encounters a pseudo-polynomial lower bound.}, author = {Pourhassan, Mojgan and Friedrich, Tobias and Neumann, Frank}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {FOGA adelaide frankneumann moganpourhassan tobiasfriedrich year2017}, pages = {37-44}, publisher = {ACM Press}, title = {On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms}, year = 2017 }

2011 [ nach oben ]

Sutton, Andrew M.; Whitley, Darrell; Howe, Adele E. Approximating the distribution of fitness over hamming regionsFoundations of Genetic Algorithms (FOGA) 2011: 93–104
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The distribution of fitness values across a set of states sharply influences the dynamics of evolutionary processes and heuristic search in combinatorial optimization. In this paper we present a method for approximating the distribution of fitness values over Hamming regions by solving a linear programming problem that incorporates low order moments of the target function. These moments can be retrieved in polynomial time for select problems such as MAX-\(k\)-SAT using Walsh analysis. The method is applicable to any real function on binary strings that is epistatically bounded and discrete with asymptotic bounds on the cardinality of its codomain. We perform several studies on the ONE-MAX and MAX-\(k\)-SAT domains to assess the accuracy of the approximation and its dependence on various factors. We show that the approximation can accurately predict the number of states within a Hamming region that have an improving fitness value.
@inproceedings{DBLP:conf/foga/SuttonWH11, abstract = {The distribution of fitness values across a set of states sharply influences the dynamics of evolutionary processes and heuristic search in combinatorial optimization. In this paper we present a method for approximating the distribution of fitness values over Hamming regions by solving a linear programming problem that incorporates low order moments of the target function. These moments can be retrieved in polynomial time for select problems such as MAX-\(k\)-SAT using Walsh analysis. The method is applicable to any real function on binary strings that is epistatically bounded and discrete with asymptotic bounds on the cardinality of its codomain. We perform several studies on the ONE-MAX and MAX-\(k\)-SAT domains to assess the accuracy of the approximation and its dependence on various factors. We show that the approximation can accurately predict the number of states within a Hamming region that have an improving fitness value.}, author = {Sutton, Andrew M. and Whitley, Darrell and Howe, Adele E.}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {andrewmsutton foga imported year2011}, pages = {93-104}, publisher = {{ACM}}, title = {Approximating the distribution of fitness over hamming regions}, year = 2011 }

Kötzing, Timo; Neumann, Frank; Sudholt, Dirk; Wagner, Markus Simple max-min ant systems and the optimization of linear pseudo-boolean functionsFoundations of Genetic Algorithms (FOGA) 2011: 209–218
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
With this paper, we contribute to the understanding of ant colony optimization (ACO) algorithms by formally analyzing their runtime behavior. We study simple MAX-MIN ant systems on the class of linear pseudo-Boolean functions defined on binary strings of length n. Our investigations point out how the progress according to function values is stored in the pheromones. We provide a general upper bound of \(O((n^3 \log n)\rho)\) on the running time for two ACO variants on all linear functions, where \(\rho\) determines the pheromone update strength. Furthermore, we show improved bounds for two well-known linear pseudo-Boolean functions called ONEMAX and BINVAL and give additional insights using an experimental study.
@inproceedings{DBLP:conf/foga/KotzingNSW11, abstract = {With this paper, we contribute to the understanding of ant colony optimization (ACO) algorithms by formally analyzing their runtime behavior. We study simple MAX-MIN ant systems on the class of linear pseudo-Boolean functions defined on binary strings of length n. Our investigations point out how the progress according to function values is stored in the pheromones. We provide a general upper bound of \(O((n^3 \log n)\rho)\) on the running time for two ACO variants on all linear functions, where \(\rho\) determines the pheromone update strength. Furthermore, we show improved bounds for two well-known linear pseudo-Boolean functions called ONEMAX and BINVAL and give additional insights using an experimental study.}, author = {Kötzing, Timo and Neumann, Frank and Sudholt, Dirk and Wagner, Markus}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {dirksudholt foga frankneumann imported markuswagner timokoetzing year2011}, pages = {209-218}, title = {Simple max-min ant systems and the optimization of linear pseudo-boolean functions}, year = 2011 }

2009 [ nach oben ]

Bringmann, Karl; Friedrich, Tobias Don’t be greedy when calculating hypervolume contributionsFoundations of Genetic Algorithms (FOGA) 2009: 103–112
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Most hypervolume indicator based optimization algorithms like SIBEA [Zitzler et al. 2007], SMS-EMOA [Beume et al. 2007], or MO-CMA-ES [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 d-dimensional 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\).
@inproceedings{DBLP:conf/foga/BringmannF09, abstract = {Most hypervolume indicator based optimization algorithms like SIBEA [Zitzler et al. 2007], SMS-EMOA [Beume et al. 2007], or MO-CMA-ES [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 d-dimensional 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\).}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {foga imported tobiasfriedrich year2009}, pages = {103-112}, title = {Don't be greedy when calculating hypervolume contributions}, year = 2009 }

Baswana, Surender; Biswas, Somenath; Doerr, Benjamin; Friedrich, Tobias; Kurur, Piyush P.; Neumann, Frank Computing Single Source Shortest Paths using Single-Objective Fitness FunctionsFoundations of Genetic Algorithms (FOGA) 2009: 59–66
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 well-known single source shortest path (SSSP) problem. Scharnow, Tinnefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multi-objective approach which solves the problem in expected polynomial time. They also suggest a related single-objective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multi-objective 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 multi-objective approach.
@inproceedings{DBLP:conf/foga/BaswanaBDFKN09, abstract = {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 well-known single source shortest path (SSSP) problem. Scharnow, Tinnefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multi-objective approach which solves the problem in expected polynomial time. They also suggest a related single-objective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multi-objective 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 multi-objective approach.}, author = {Baswana, Surender and Biswas, Somenath and Doerr, Benjamin and Friedrich, Tobias and Kurur, Piyush P. and Neumann, Frank}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {benjamindoerr foga frankneumann imported piyushpkurur somenathbiswas surenderbaswana tobiasfriedrich year2009}, pages = {59-66}, publisher = {{ACM}}, title = {Computing Single Source Shortest Paths using Single-Objective Fitness Functions}, year = 2009 }