2026

Krejca, Martin; Witt, Carsten A Flexible Evolutionary Algorithm with Dynamic Mutation Rate ArchiveAlgorithmica 2026: 1–32
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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. We conduct rigorous runtime analysis of the flexible evolutionary algorithm on the OneMax and Jump functions, on general unimodal functions, on minimum spanning trees, and on a class of hurdle-like functions with varying hurdle width that benefit particularly from the archive of promising mutation rates. In all cases, the runtime bounds are close to or even outperform the best known results for both stagnation detection and heavy-tailed mutations.
@article{krejca2026flexible, abstract = {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. We conduct rigorous runtime analysis of the flexible evolutionary algorithm on the OneMax and Jump functions, on general unimodal functions, on minimum spanning trees, and on a class of hurdle-like functions with varying hurdle width that benefit particularly from the archive of promising mutation rates. In all cases, the runtime bounds are close to or even outperform the best known results for both stagnation detection and heavy-tailed mutations.}, author = {Krejca, Martin and Witt, Carsten}, journal = {Algorithmica}, keywords = {algorithmica martinskrejca carstenwitt year2026 solelyextern}, number = 5, pages = {1-32}, title = {A Flexible Evolutionary Algorithm with Dynamic Mutation Rate Archive}, volume = 88, year = 2026 }

Doerr, Benjamin; Krejca, Martin S.; Stanković, Milan Improved Runtime Guarantees for the SPEA2 Multi-Objective OptimizerAnnual AAAI Conference on Artificial Intelligence (AAAI) 2026: 36855–36863
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size \(\mu \ge n - 2k + 3\) and offspring population size \(\lambda\) computes the Pareto front of the OneJumpZeroJump benchmark with gap size~\($k$\) in an expected number of \(O( (\lambda+\mu)n + n^{k+1})\) function evaluations. This shows that the best runtime guarantee of \(O(n^{k+1})\) is not only achieved for \(mu = \Theta(n)\) and \(lambda = O(n)\) but for arbitrary \(mu, lambda = O(n^k)\). Thus, choosing suitable parameters – a key challenge in using heuristic algorithms – is much easier for the SPEA2 than the NSGA-II.
@inproceedings{doerr2026improved, abstract = {Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size \(\mu \ge n - 2k + 3\) and offspring population size \(\lambda\) computes the Pareto front of the OneJumpZeroJump benchmark with gap size $k$ in an expected number of \(O( (\lambda+\mu)n + n^{k+1})\) function evaluations. This shows that the best runtime guarantee of \(O(n^{k+1})\) is not only achieved for \(\mu = \Theta(n)\) and \(\lambda = O(n)\) but for arbitrary \(\mu, \lambda = O(n^k)\). Thus, choosing suitable parameters – a key challenge in using heuristic algorithms – is much easier for the SPEA2 than the NSGA-II.}, author = {Doerr, Benjamin and Krejca, Martin S. and Stanković, Milan}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {milanstankovic martinskrejca year2026 aaai benjamindoerr solelyextern}, pages = {36855-36863}, title = {Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer}, year = 2026 }

Doerr, Benjamin; Krejca, Martin S.; Wietheger, Simon Speeding Up the NSGA-II via Dynamic Population SizesInternational Joint Conferences on Artifical Intelligence (IJCAI) 2026
[ Abstract ] [ BibTeX ] [ Download ]
 
Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) simultaneously, MOEAs are typically run with a large population of solution candidates. This slows down the algorithm and renders the choice of the population size a crucial design decision. In this work, we aim to overcome these difficulties by proposing the dynamic NSGA-II, a variant of the well-known NSGA-II that starts with a small initial population and doubles it after a user-specified number \(\tau\) of function evaluations, up to a maximum size of \(N_{\max}\). We prove that the dynamic NSGA-II with optimal parameters computes the Pareto front of the OneMinMax benchmark of size \(n\) with high probability in \(O(n \log^2 n)\) function evaluations, which is considerably faster than the \(\Theta(n^2 \log n)\) runtime of the static NSGA-II with optimal parameters. For the OneJumpZeroJump benchmark with gap size \(k\), we show a runtime of \(O(n^k \log^2 n)\), improving upon the known runtime of \(\Theta(n^{k+1})\). We also propose a variant that uses the initial population size for a longer period and achieves slightly better performance. Finally, we show that a simple concurrent-run strategy turns our dynamic NSGA-II variants into parameter-less algorithms that exceed the above runtimes only by a logarithmic factor and hence still outperform the static NSGA-II by a factor of \(\tilde\Omega(n)\).
@inproceedings{doerr2026speeding, abstract = {Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) simultaneously, MOEAs are typically run with a large population of solution candidates. This slows down the algorithm and renders the choice of the population size a crucial design decision. In this work, we aim to overcome these difficulties by proposing the dynamic NSGA-II, a variant of the well-known NSGA-II that starts with a small initial population and doubles it after a user-specified number \(\tau\) of function evaluations, up to a maximum size of \(N_{\max}\). We prove that the dynamic NSGA-II with optimal parameters computes the Pareto front of the OneMinMax benchmark of size \(n\) with high probability in \(O(n \log^2 n)\) function evaluations, which is considerably faster than the \(\Theta(n^2 \log n)\) runtime of the static NSGA-II with optimal parameters. For the OneJumpZeroJump benchmark with gap size \(k\), we show a runtime of \(O(n^k \log^2 n)\), improving upon the known runtime of \(\Theta(n^{k+1})\). We also propose a variant that uses the initial population size for a longer period and achieves slightly better performance. Finally, we show that a simple concurrent-run strategy turns our dynamic NSGA-II variants into parameter-less algorithms that exceed the above runtimes only by a logarithmic factor and hence still outperform the static NSGA-II by a factor of \(\tilde\Omega(n)\).}, author = {Doerr, Benjamin and Krejca, Martin S. and Wietheger, Simon}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai martinskrejca simonwietheger year2026 benjamindoerr solelyextern}, title = {Speeding Up the NSGA-II via Dynamic Population Sizes}, year = 2026 }

Krejca, Martin S.; Witt, Carsten Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax FunctionParallel Problem Solving from Nature (PPSN) 2026
[ Abstract ] [ BibTeX ] [ Download ]
 
Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G--OneMax\(\colon \0,\dots,r-1\^n \to \N\) defined by G-OneMax\((x_1,\dots,x_n)=\sum_{i=1^n \bm{x}_i\) and truly depending on all \(r\) categories. We improve their runtime result from \(O\bigl(n r^3 \log^2(n)log (r)\bigr)\) to \(O\bigl(n r \log^3(n)\log^3(r)\bigr)\), both for an optimal choice of the update strength \(K\). Our result matches, up to polylogarithmic factors, the existing bound for the simpler \(r\)-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the \(r\)-valued frequency matrix.
@inproceedings{krejca2026runtime, abstract = {Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G–OneMax\(\colon \{0,\dots,r-1\}^n \to \N\) defined by G-OneMax\((x_1,\dots,x_n)=\sum_{i=1}^n \bm{x}_i\) and truly depending on all \(r\) categories. We improve their runtime result from \(O\bigl(n r^3 \log^2(n)\log (r)\bigr)\) to \(O\bigl(n r \log^3(n)\log^3(r)\bigr)\), both for an optimal choice of the update strength \(K\). Our result matches, up to polylogarithmic factors, the existing bound for the simpler \(r\)-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the \(r\)-valued frequency matrix.}, author = {Krejca, Martin S. and Witt, Carsten}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {martinskrejca carstenwitt year2026 solelyextern ppsn}, title = {Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function}, year = 2026 }

2025

Fourquet, Océane; Krejca, Martin S.; Doerr, Carola; Schwikowski, Benno Towards the genome-scale discovery of bivariate monotonic classifiersBMC Bioinformatics 2025: 228:1–228:32
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Background Bivariate monotonic classifiers (BMCs) are based on pairs of input features. Like many other models used for machine learning, they can capture nonlinear patterns in high-dimensional data. At the same time, they are simple and easy to interpret. Until now, the use of BMCs on a genome scale was hampered by the high computational complexity of the search for pairs of features with a high leave-one-out performance estimate. Results We introduce the fastBMC algorithm, which drastically speeds up the identification of BMCs. The algorithm is based on a mathematical bound for the BMC performance estimate while maintaining optimality. We show empirically that fastBMC speeds up the computation by a factor of at least 15 already for a small number of features, compared to the traditional approach. For two of the three smaller biomedical datasets that we consider here, the resulting possibility of considering much larger sets of features translates into significantly improved classification performance. As an example of the high degree of interpretability of BMCs, we discuss a straightforward interpretation of a BMC glioblastoma survival predictor, an immediate novel biomedical hypothesis, options for biomedical validation, and treatment implications. In addition, we study the performance of fastBMC on a larger and well-known breast cancer dataset, validating the benefits of the BMCs for biomarker identification and biomedical hypothesis generation. Conclusion fastBMC enables the rapid construction of robust and interpretable ensemble models using BMC, facilitating the discovery of gene pairs predictive of relevant phenotypes and their interaction in that context. Availability We provide the first open-source implementation for learning BMCs, a Python implementation of fastBMC in particular, and Python code to reproduce the fastBMC results on real and simulated data in this paper, at https://github.com/oceanefrqt/fastBMC.
@article{fourquet2025towards, abstract = {Background Bivariate monotonic classifiers (BMCs) are based on pairs of input features. Like many other models used for machine learning, they can capture nonlinear patterns in high-dimensional data. At the same time, they are simple and easy to interpret. Until now, the use of BMCs on a genome scale was hampered by the high computational complexity of the search for pairs of features with a high leave-one-out performance estimate. Results We introduce the fastBMC algorithm, which drastically speeds up the identification of BMCs. The algorithm is based on a mathematical bound for the BMC performance estimate while maintaining optimality. We show empirically that fastBMC speeds up the computation by a factor of at least 15 already for a small number of features, compared to the traditional approach. For two of the three smaller biomedical datasets that we consider here, the resulting possibility of considering much larger sets of features translates into significantly improved classification performance. As an example of the high degree of interpretability of BMCs, we discuss a straightforward interpretation of a BMC glioblastoma survival predictor, an immediate novel biomedical hypothesis, options for biomedical validation, and treatment implications. In addition, we study the performance of fastBMC on a larger and well-known breast cancer dataset, validating the benefits of the BMCs for biomarker identification and biomedical hypothesis generation. Conclusion fastBMC enables the rapid construction of robust and interpretable ensemble models using BMC, facilitating the discovery of gene pairs predictive of relevant phenotypes and their interaction in that context. Availability We provide the first open-source implementation for learning BMCs, a Python implementation of fastBMC in particular, and Python code to reproduce the fastBMC results on real and simulated data in this paper, at https://github.com/oceanefrqt/fastBMC.}, author = {Fourquet, Océane and Krejca, Martin S. and Doerr, Carola and Schwikowski, Benno}, journal = {BMC Bioinformatics}, keywords = {bmcbioinformatics caroladoerr martinskrejca bennoschwikowski year2025 solelyextern oceanefourquet}, number = 228, pages = {228:1-228:32}, title = {Towards the genome-scale discovery of bivariate monotonic classifiers}, volume = 26, year = 2025 }

Chwiałkowski, Marcel; Doerr, Benjamin; Krejca, Martin S. Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes BenchmarkIEEE Transactions on Evolutionary Computation 2025: 311–320
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA)---another simple EDA---, the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LeadingOnes benchmark---one of the most studied theory benchmarks in the domain of evolutionary computation. We fill this gap in the literature by conducting a formal runtime analysis of the cGA on LeadingOnes. For the cGA's single parameter---called the hypothetical population size---at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LeadingOnes with high probability within a number of function evaluations quasi-linear in the problem size and linear in the hypothetical population size. For the best hypothetical population size, our result matches, up to polylogarithmic factors, the typical quadratic runtime that many randomized search heuristics exhibit on LeadingOnes. Our analysis exhibits some noteworthy differences in the working principles of the two algorithms which were not visible in previous works.
@article{chwiakowski2025runtime, abstract = {The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA)—another simple EDA—, the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LeadingOnes benchmark—one of the most studied theory benchmarks in the domain of evolutionary computation. We fill this gap in the literature by conducting a formal runtime analysis of the cGA on LeadingOnes. For the cGA's single parameter—called the hypothetical population size—at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LeadingOnes with high probability within a number of function evaluations quasi-linear in the problem size and linear in the hypothetical population size. For the best hypothetical population size, our result matches, up to polylogarithmic factors, the typical quadratic runtime that many randomized search heuristics exhibit on LeadingOnes. Our analysis exhibits some noteworthy differences in the working principles of the two algorithms which were not visible in previous works.}, author = {Chwiałkowski, Marcel and Doerr, Benjamin and Krejca, Martin S.}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {marcelchwialkowski martinskrejca ieeetevc benjamindoerr year2025 solelyextern}, number = 1, pages = {311-320}, title = {Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark}, volume = 30, year = 2025 }

Doerr, Benjamin; Korkotashvili, Dimitri; Krejca, Martin S. Difficulties of the NSGA-II with the Many-Objective LeadingOnes ProblemIEEE Transactions on Evolutionary Computation 2025: 773–782
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The NSGA-II is the most prominent multi-objective evolutionary algorithm (cited more than 50,000 times). Very recently, a mathematical runtime analysis has proven that this algorithm can have enormous difficulties when the number of objectives is larger than two (Zheng, Doerr. IEEE Transactions on Evolutionary Computation (2024)). However, this result was shown only for the OneMinMax benchmark problem, which has the particularity that all solutions are on the Pareto front, a fact heavily exploited in the proof of this result. In this work, we show a comparable result for the LeadingOnesTrailingZeroes benchmark. This popular benchmark problem appears more natural in that most of its solutions are not on the Pareto front. With a careful analysis of the population dynamics of the NGSA-II optimizing this benchmark, we manage to show that when the population grows on the Pareto front, then it does so much faster by creating known Pareto optima than by spreading out on the Pareto front. Consequently, already when still a constant fraction of the Pareto front is unexplored, the crowding distance becomes the crucial selection mechanism, and thus the same problems arise as in the optimization of OneMinMax. With these and some further arguments, we show that the NSGA-II, with a population size by at most a constant factor larger than the Pareto front, cannot compute the Pareto front in less than exponential time.
@article{doerr2025difficulties, abstract = {The NSGA-II is the most prominent multi-objective evolutionary algorithm (cited more than 50,000 times). Very recently, a mathematical runtime analysis has proven that this algorithm can have enormous difficulties when the number of objectives is larger than two (Zheng, Doerr. IEEE Transactions on Evolutionary Computation (2024)). However, this result was shown only for the OneMinMax benchmark problem, which has the particularity that all solutions are on the Pareto front, a fact heavily exploited in the proof of this result. In this work, we show a comparable result for the LeadingOnesTrailingZeroes benchmark. This popular benchmark problem appears more natural in that most of its solutions are not on the Pareto front. With a careful analysis of the population dynamics of the NGSA-II optimizing this benchmark, we manage to show that when the population grows on the Pareto front, then it does so much faster by creating known Pareto optima than by spreading out on the Pareto front. Consequently, already when still a constant fraction of the Pareto front is unexplored, the crowding distance becomes the crucial selection mechanism, and thus the same problems arise as in the optimization of OneMinMax. With these and some further arguments, we show that the NSGA-II, with a population size by at most a constant factor larger than the Pareto front, cannot compute the Pareto front in less than exponential time.}, author = {Doerr, Benjamin and Korkotashvili, Dimitri and Krejca, Martin S.}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {dimitrikorkotashvili martinskrejca benjamindoerr year2025 solelyextern}, number = 2, pages = {773-782}, title = {Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem}, volume = 30, year = 2025 }

Doerr, Benjamin; Krejca, Martin S.; Rudolph, Günter Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer SpacesAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26955–26963
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.
@inproceedings{doerr2025runtime, abstract = {Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables – the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results – however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.}, author = {Doerr, Benjamin and Krejca, Martin S. and Rudolph, Günter}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {guenterrudolph martinskrejca aaai benjamindoerr year2025 solelyextern}, pages = {26955-26963}, title = {Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces}, year = 2025 }

Doerr, Benjamin; Ivan, Tudor; Krejca, Martin S. Speeding Up the NSGA-II With a Simple Tie-Breaking RuleAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26964–26972
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The non-dominated sorting genetic algorithm II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length \($n$\) and gap parameter \($k$\), we show a runtime guarantee of \($O(\max\{n^{k+1},Nn\})$\) function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice \($N = \Theta(n)$\), this result improves considerably over the \($\Theta(Nn^k)$\) runtime of the classic NSGA-II.
@inproceedings{doerr2025speeding, abstract = {The non-dominated sorting genetic algorithm II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II.}, author = {Doerr, Benjamin and Ivan, Tudor and Krejca, Martin S.}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {tudorivan martinskrejca aaai benjamindoerr year2025 solelyextern}, pages = {26964-26972}, title = {Speeding Up the NSGA-II With a Simple Tie-Breaking Rule}, year = 2025 }

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 = {foga martinskrejca carstenwitt year2025 frankneumann solelyextern}, pages = {142-153}, title = {Population Dynamics and Improved Runtime Guarantees for the (µ+1) EA on BinVal}, year = 2025 }

Alghouass, Yasser; Doerr, Benjamin; Krejca, Martin S.; Lagmah, Mohammed Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-IIInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025: 8833–8841
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of \(\sigma\)-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.
@inproceedings{alghouass2025proven, abstract = {Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of \(\sigma\)-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.}, author = {Alghouass, Yasser and Doerr, Benjamin and Krejca, Martin S. and Lagmah, Mohammed}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai martinskrejca yasseralghouass mohammedlagmah benjamindoerr year2025 solelyextern}, pages = {8833-8841}, title = {Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II}, year = 2025 }

Doerr, Benjamin; Krejca, Martin S.; Opris, Andre Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary AlgorithmInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025: 8876–8884
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order \(\Omega(n^2 \log n)\), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time \(O(n^2)\), improving over the previous estimate of \(O(n^2 \log n)\) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first \(\Omega(n^{k+1})\) lower bound for the OJZJ benchmark in the case that the gap parameter is \(k \in \{2,3\}\). We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.
@inproceedings{doerr2025tight, abstract = {The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order \(\Omega(n^2 \log n)\), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time \(O(n^2)\), improving over the previous estimate of \(O(n^2 \log n)\) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first \(\Omega(n^{k+1})\) lower bound for the OJZJ benchmark in the case that the gap parameter is \(k \in \{2,3\}\). We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.}, author = {Doerr, Benjamin and Krejca, Martin S. and Opris, Andre}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai andreopris martinskrejca benjamindoerr year2025 solelyextern}, pages = {8876-8884}, title = {Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm}, year = 2025 }

2024

Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S. Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science 2024: 114622:1–114622:16
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a naive reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued, categorical variables. Roughly speaking, when the variables take \(r\) different values, the time for genetic drift to become significant is \(r\) times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen \(r\) times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the \(r\)-valued LeadingOnes problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in \(O(r\ln(r)^2 n^2 \ln(n))\) function evaluations. This bound is nearly tight as our lower bound \(\Omega(r\ln(r) n^2 \ln(n))\) shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.
@article{benjedidia2024estimationofdistribution, abstract = {The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a naive reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued, categorical variables. Roughly speaking, when the variables take \(r\) different values, the time for genetic drift to become significant is \(r\) times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen \(r\) times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the \(r\)-valued LeadingOnes problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in \(O(r\ln(r)^2 n^2 \ln(n))\) function evaluations. This bound is nearly tight as our lower bound \(\Omega(r\ln(r) n^2 \ln(n))\) shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.}, author = {Ben Jedidia, Firas and Doerr, Benjamin and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {tcs martinskrejca firasbenjedidia benjamindoerr year2024 solelyextern}, pages = {114622:1-114622:16}, title = {Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables}, volume = 1003, year = 2024 }

Doerr, Benjamin; Echarghaoui, Aymen; Jamal, Mohammed; Krejca, Martin S. Runtime Analysis of the (µ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse PopulationsAnnual AAAI Conference on Artificial Intelligence (AAAI) 2024: 20683–20691
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most evolutionary algorithms used in practice heavily employ crossover. In contrast, the rigorous understanding of how crossover is beneficial is largely lagging behind. In this work, we make a considerable step forward by analyzing the population dynamics of the \((\mu+1)\) genetic algorithm when optimizing the Jump benchmark. We observe (and prove via mathematical means) that once the population contains two different individuals on the local optimum, the diversity in the population increases in expectation. From this drift towards more diverse states, we show that a diversity suitable for crossover to be effective is reached quickly and, more importantly, then persists for a time that is at least exponential in the population size \(\mu\). This drastically improves over the previously best known guarantee, which is only quadratic in \(\mu\). Our new understanding of the population dynamics easily gives stronger performance guarantees. In particular, we derive that population sizes logarithmic in the problem size \(n\) already suffice to gain an \(\Omega(n)\)-factor runtime improvement from crossover (previous works achieved comparable bounds only with \(\mu=\Theta(n)\) or via a non-standard mutation rate).
@inproceedings{doerr2024runtime, abstract = {Most evolutionary algorithms used in practice heavily employ crossover. In contrast, the rigorous understanding of how crossover is beneficial is largely lagging behind. In this work, we make a considerable step forward by analyzing the population dynamics of the \((\mu+1)\) genetic algorithm when optimizing the Jump benchmark. We observe (and prove via mathematical means) that once the population contains two different individuals on the local optimum, the diversity in the population increases in expectation. From this drift towards more diverse states, we show that a diversity suitable for crossover to be effective is reached quickly and, more importantly, then persists for a time that is at least exponential in the population size \(\mu\). This drastically improves over the previously best known guarantee, which is only quadratic in \(\mu\). Our new understanding of the population dynamics easily gives stronger performance guarantees. In particular, we derive that population sizes logarithmic in the problem size \(n\) already suffice to gain an \(\Omega(n)\)-factor runtime improvement from crossover (previous works achieved comparable bounds only with \(\mu=\Theta(n)\) or via a non-standard mutation rate).}, author = {Doerr, Benjamin and Echarghaoui, Aymen and Jamal, Mohammed and Krejca, Martin S.}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {jamalmohammed martinskrejca aaai benjamindoerr year2024 solelyextern aymenecharghaoui}, pages = {20683-20691}, title = {Runtime Analysis of the (µ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations}, year = 2024 }

Doerr, Benjamin; Krejca, Martin S.; Vu, Nguyen Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy HeuristicsGenetic and Evolutionary Computation Conference (GECCO) 2024: 169–177
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The target set selection problem (TSS) asks for a set of vertices such that an influence spreading process started in these vertices reaches the whole graph. The current state of the art for this NP-hard problem are three recently proposed randomized search heuristics, namely a biased random-key genetic algorithm (BRKGA) obtained from extensive parameter tuning, a max-min ant system (MMAS), and a MMAS using Q-learning with a graph convolutional network. We show that the BRKGA with two simple modifications and without the costly parameter tuning obtains significantly better results. Our first modification is to simply choose all parameters of the BRKGA in each iteration randomly from a power-law distribution. The resulting parameterless BRKGA is already competitive with the tuned BRKGA, as our experiments on the previously used benchmarks show. We then add a natural greedy heuristic, namely to repeatedly discard small-degree vertices that are not necessary for reaching the whole graph. The resulting algorithm consistently outperforms all of the state-of-the-art algorithms. Besides providing a superior algorithm for the TSS problem, this work shows that randomized parameter choices and elementary greedy heuristics can give better results than complex algorithms and costly parameter tuning.
@inproceedings{doerr2024superior, abstract = {The target set selection problem (TSS) asks for a set of vertices such that an influence spreading process started in these vertices reaches the whole graph. The current state of the art for this NP-hard problem are three recently proposed randomized search heuristics, namely a biased random-key genetic algorithm (BRKGA) obtained from extensive parameter tuning, a max-min ant system (MMAS), and a MMAS using Q-learning with a graph convolutional network. We show that the BRKGA with two simple modifications and without the costly parameter tuning obtains significantly better results. Our first modification is to simply choose all parameters of the BRKGA in each iteration randomly from a power-law distribution. The resulting parameterless BRKGA is already competitive with the tuned BRKGA, as our experiments on the previously used benchmarks show. We then add a natural greedy heuristic, namely to repeatedly discard small-degree vertices that are not necessary for reaching the whole graph. The resulting algorithm consistently outperforms all of the state-of-the-art algorithms. Besides providing a superior algorithm for the TSS problem, this work shows that randomized parameter choices and elementary greedy heuristics can give better results than complex algorithms and costly parameter tuning.}, author = {Doerr, Benjamin and Krejca, Martin S. and Vu, Nguyen}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca nguyenvu benjamindoerr gecco year2024 solelyextern}, pages = {169–177}, title = {Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics}, year = 2024 }

Krejca, Martin S.; Witt, Carsten A Flexible Evolutionary Algorithm With Dynamic Mutation Rate ArchiveGenetic and Evolutionary Computation Conference (GECCO) 2024: 1578–1586
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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. We conduct rigorous runtime analysis of the flexible evolutionary algorithm on the OneMax and Jump functions, on general unimodal functions, on minimum spanning and on a class of hurdle-like functions with varying hurdle width that benefit particularly from the archive of promising mutation rates. In all cases, the runtime bounds are close to or even outperform the best known results for both stagnation detection and heavy-tailed mutations.
@inproceedings{krejca2024flexible, abstract = {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. We conduct rigorous runtime analysis of the flexible evolutionary algorithm on the OneMax and Jump functions, on general unimodal functions, on minimum spanning and on a class of hurdle-like functions with varying hurdle width that benefit particularly from the archive of promising mutation rates. In all cases, the runtime bounds are close to or even outperform the best known results for both stagnation detection and heavy-tailed mutations.}, author = {Krejca, Martin S. and Witt, Carsten}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca carstenwitt gecco year2024 solelyextern}, pages = {1578-1586}, title = {A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive}, year = 2024 }

Doerr, Benjamin; Krejca, Martin S.; Weeks, Noé Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem SolutionsParallel Problem Solving from Nature (PPSN) 2024: 197–212
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function \(f\), but instead optimizes \(N + 1\) single-objective subproblems of \(f\) in a co-evolutionary manner. It maintains an archive of all non-dominated solutions found and outputs it as approximation to the Pareto front. Once the MOEA/D found all optima of the subproblems (the \(g\)-optima), it may still miss Pareto optima of \(f\). The algorithm is then tasked to find the remaining Pareto optima directly by mutating the \(g\)-optima. In this work, we analyze for the first time how the MOEA/D with only standard mutation operators computes the whole Pareto front of the OneMinMax benchmark when the \(g\)-optima are a strict subset of the Pareto front. For standard bit mutation, we prove an expected runtime of \(O(n N log n + n^n/(2N) N \log n)\) function evaluations. Especially for the second, more interesting phase when the algorithm start with all \(g\)-optima, we prove an \(\Omega(n^(1/2)(n/N + 1) \sqrt{N} 2^{-n/N})\) expected runtime. This runtime is super-polynomial if \(N = o(n)\), since this leaves large gaps between the \(g\)-optima, which require costly mutations to cover. For power-law mutation with exponent \(beta in (1, 2)\), we prove an expected runtime of \(O\left(n N \log n + n^\beta} \log n\right)\) function evaluations. The \(O\left(n^{\beta} \log n\right)\) term stems from the second phase of starting with all \(g\)-optima, and it is independent of the number of subproblems \(N\). This leads to a huge speedup compared to the lower bound for standard bit mutation. In general, our overall bound for power-law suggests that the MOEA/D performs best for \(N = O(n^\beta - 1})\), resulting in an \(O(n^\beta \log n)\) bound. In contrast to standard bit mutation, smaller values of \(N\) are better for power-law mutation, as it is capable of easily creating missing solutions.
@inproceedings{doerr2024proven, abstract = {The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function \(f\), but instead optimizes \(N + 1\) single-objective subproblems of \(f\) in a co-evolutionary manner. It maintains an archive of all non-dominated solutions found and outputs it as approximation to the Pareto front. Once the MOEA/D found all optima of the subproblems (the \(g\)-optima), it may still miss Pareto optima of \(f\). The algorithm is then tasked to find the remaining Pareto optima directly by mutating the \(g\)-optima. In this work, we analyze for the first time how the MOEA/D with only standard mutation operators computes the whole Pareto front of the OneMinMax benchmark when the \(g\)-optima are a strict subset of the Pareto front. For standard bit mutation, we prove an expected runtime of \(O(n N \log n + n^{n/(2N)} N \log n)\) function evaluations. Especially for the second, more interesting phase when the algorithm start with all \(g\)-optima, we prove an \(\Omega(n^{(1/2)(n/N + 1)} \sqrt{N} 2^{-n/N})\) expected runtime. This runtime is super-polynomial if \(N = o(n)\), since this leaves large gaps between the \(g\)-optima, which require costly mutations to cover. For power-law mutation with exponent \(\beta \in (1, 2)\), we prove an expected runtime of \(O\left(n N \log n + n^{\beta} \log n\right)\) function evaluations. The \(O\left(n^{\beta} \log n\right)\) term stems from the second phase of starting with all \(g\)-optima, and it is independent of the number of subproblems \(N\). This leads to a huge speedup compared to the lower bound for standard bit mutation. In general, our overall bound for power-law suggests that the MOEA/D performs best for \(N = O(n^{\beta - 1})\), resulting in an \(O(n^\beta \log n)\) bound. In contrast to standard bit mutation, smaller values of \(N\) are better for power-law mutation, as it is capable of easily creating missing solutions.}, author = {Doerr, Benjamin and Krejca, Martin S. and Weeks, Noé}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {noeweeks ppsn24 martinskrejca benjamindoerr year2024 solelyextern}, pages = {197–212}, title = {Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions}, year = 2024 }

2023

Doerr, Carola; Krejca, Martin S. Run Time Analysis for Random Local Search on Generalized Majority FunctionsIEEE Transactions on Evolutionary Computation 2023: 1385–1397
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Run time analysis of evolutionary algorithms recently makes significant progress in linking algorithm performance to algorithm parameters. However, settings that study the impact of problem parameters are rare. The recently proposed W-model provides a good framework for such analyses, generating pseudo-Boolean optimization problems with tunable properties. We initiate theoretical research of the W-model by studying how one of its properties—neutrality—influences the run time of random local search. Neutrality creates plateaus in the search space by first performing a majority vote for subsets of the solution candidate and then evaluating the smaller-dimensional string via a low-level fitness function. We prove upper bounds for the expected run time of random local search on this MAJORITY problem for its entire parameter spectrum. To this end, we provide a theorem, applicable to many optimization algorithms, that links the run time of MAJORITY with its symmetric version HASMAJORITY, where a sufficient majority is needed to optimize the subset. We also introduce a generalized version of classic drift theorems as well as a generalized version of Wald's equation, both of which we believe to be of independent interest.
@article{doerr2023analysis, abstract = {Run time analysis of evolutionary algorithms recently makes significant progress in linking algorithm performance to algorithm parameters. However, settings that study the impact of problem parameters are rare. The recently proposed W-model provides a good framework for such analyses, generating pseudo-Boolean optimization problems with tunable properties. We initiate theoretical research of the W-model by studying how one of its properties—neutrality—influences the run time of random local search. Neutrality creates plateaus in the search space by first performing a majority vote for subsets of the solution candidate and then evaluating the smaller-dimensional string via a low-level fitness function. We prove upper bounds for the expected run time of random local search on this MAJORITY problem for its entire parameter spectrum. To this end, we provide a theorem, applicable to many optimization algorithms, that links the run time of MAJORITY with its symmetric version HASMAJORITY, where a sufficient majority is needed to optimize the subset. We also introduce a generalized version of classic drift theorems as well as a generalized version of Wald's equation, both of which we believe to be of independent interest.}, author = {Doerr, Carola and Krejca, Martin S.}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {caroladoerr martinskrejca year2023 solelyextern}, number = 5, pages = {1385-1397}, title = {Run Time Analysis for Random Local Search on Generalized Majority Functions}, volume = 27, year = 2023 }

Doerr, Benjamin; Krejca, Martin S. Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of OptimaTheoretical Computer Science 2023: 114074.1–114074.16
[ BibTeX ] [ DOI ] [ Download ]
 
@article{doerr2023bivariate, author = {Doerr, Benjamin and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {tcs martinskrejca benjamindoerr year2023 solelyextern}, pages = {114074.1-114074.16}, title = {Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima}, volume = 971, year = 2023 }

Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S. Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesGenetic and Evolutionary Computation Conference (GECCO) 2023: 230–238
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
With apparently all research on estimation-of-distribution algorithms (EDAs) concentrated on pseudo-Boolean optimization and permutation problems, we undertake the first steps towards using EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems. To this aim, we propose a natural way to extend the known univariate EDAs to such variables. Different from a naive reduction to the binary case, it avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued variables. Roughly speaking, when the variables take \(r\) different values, the time for genetic drift to become critical is \(r\) times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen \(r\) times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the \(r\)-valued LeadingOnes problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in \(O(r\log(r)^2 n^2 \log(n))\) function evaluations. Overall, our work shows that EDAs can be adjusted to multi-valued problems and gives advice on how to set their parameters.
@inproceedings{benjedidia2023estimationofdistribution, abstract = {With apparently all research on estimation-of-distribution algorithms (EDAs) concentrated on pseudo-Boolean optimization and permutation problems, we undertake the first steps towards using EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems. To this aim, we propose a natural way to extend the known univariate EDAs to such variables. Different from a naive reduction to the binary case, it avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued variables. Roughly speaking, when the variables take \(r\) different values, the time for genetic drift to become critical is \(r\) times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen \(r\) times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the \(r\)-valued LeadingOnes problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in \(O(r\log(r)^2 n^2 \log(n))\) function evaluations. Overall, our work shows that EDAs can be adjusted to multi-valued problems and gives advice on how to set their parameters.}, author = {Ben Jedidia, Firas and Doerr, Benjamin and Krejca, Martin S.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca firasbenjedidia benjamindoerr gecco year2023 solelyextern}, pages = {230-238}, title = {Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables}, year = 2023 }

2022

Biedenkapp, André; Dang, Nguyên; Krejca, Martin S.; Hutter, Frank; Doerr, Carola Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm ConfigurationGenetic and Evolutionary Computation Conference (GECCO) 2022: 766–775
Best-Paper Award (GECH Track)
[ BibTeX ] [ DOI ] [ Download ]
 
@inproceedings{biedenkapp2022theoryinspired, author = {Biedenkapp, André and Dang, Nguyên and Krejca, Martin S. and Hutter, Frank and Doerr, Carola}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca bestpaper gecco solelyextern year2022}, note = {Best-Paper Award (GECH Track)}, pages = {766-775}, title = {Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration}, year = 2022 }

2021

Doerr, Benjamin; Krejca, Martin S. The Univariate Marginal Distribution Algorithm Copes Well with Deception and EpistasisEvolutionary Computation 2021: 543–563
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most \(\lambda(\frac{n}{2 + 2 e \ln n)\) fitness evaluations. Since an offspring population size \(\lambda\) of order \(n \log n\) can prevent genetic drift, the UMDA can solve the DLB problem with \(O(n^2 \log n)\) fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than \(O(n^3)\) is known (which we prove to be tight for the \(1 + 1\) EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than many classic evolutionary algorithms; such a result was previously known only for the compact genetic algorithm. Together with the lower bound of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
@article{doerr2020univariate, abstract = {In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most \(\lambda(\frac{n}{2} + 2 e \ln n)\) fitness evaluations. Since an offspring population size \(\lambda\) of order \(n \log n\) can prevent genetic drift, the UMDA can solve the DLB problem with \(O(n^2 \log n)\) fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than \(O(n^3)\) is known (which we prove to be tight for the \(1 + 1\) EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than many classic evolutionary algorithms; such a result was previously known only for the compact genetic algorithm. Together with the lower bound of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.}, author = {Doerr, Benjamin and Krejca, Martin S.}, journal = {Evolutionary Computation}, keywords = {martinskrejca benjamindoerr ecj solelyextern year2021}, number = 4, pages = {543-563}, publisher = {MIT Press}, title = {The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis}, volume = 29, year = 2021 }

2025 [ nach oben ]

Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free DiffusionInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025
[ Abstract ] [ BibTeX ] [ Download ]
 
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.
@inproceedings{gbel2025resistance, abstract = {Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.}, author = {Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai nicolasklodt marcuspappik martinskrejca andreasgoebel year2025}, title = {Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion}, year = 2025 }

2024 [ nach oben ]

Friedrich, Tobias; Göbel, Andres; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Analysis of the survival time of the SIRS process via expansionElectronic Journal of Probability 2024: 1–29
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the SIRS process---a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate~\(\lambda\), and each recovered vertex becomes susceptible at a rate~\(\varrho\), which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of~\(\lambda\). This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs \(G\) with \(n\) vertices, degree close to \(d\), and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in \(n\) when \(\lambda \geq c/d\) for a constant \(c > 1\). Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if \(G\) is a subgraph. Notably, our result implies an almost-tight threshold for Erdos-Renyi-graphs and a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.
@article{friedrich2024analysis, abstract = {We study the SIRS process—a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate \(\lambda\), and each recovered vertex becomes susceptible at a rate \(\varrho\), which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of \(\lambda\). This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs \(G\) with \(n\) vertices, degree close to \(d\), and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in \(n\) when \(\lambda \geq c/d\) for a constant \(c > 1\). Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if \(G\) is a subgraph. Notably, our result implies an almost-tight threshold for Erdos-Renyi-graphs and a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.}, author = {Friedrich, Tobias and Göbel, Andres and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, journal = {Electronic Journal of Probability}, keywords = {nicolasklodt marcuspappik martinskrejca andreasgoebel tobiasfriedrich ejp year2024}, pages = {1-29}, title = {Analysis of the survival time of the SIRS process via expansion}, volume = 29, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network ModelsAnnual AAAI Conference on Artificial Intelligence 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.
@inproceedings{friedrich2024irrelevance, abstract = {Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {Annual AAAI Conference on Artificial Intelligence}, keywords = {nicolasklodt marcuspappik martinskrejca andreasgoebel tobiasfriedrich aaai year2024}, title = {The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models}, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion ModelsThe 23rd International Conference on Autonomous Agents and Multi-Agent Systems 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.
@inproceedings{friedrich2024market, abstract = {Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {The 23rd International Conference on Autonomous Agents and Multi-Agent Systems}, keywords = {nicolasklodt marcuspappik martinskrejca andreasgoebel tobiasfriedrich aamas year2024}, title = {From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models}, year = 2024 }

Bläsius, Thomas; Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic ApproximationCoRR 2024
ArXiv preprint
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations.
@article{blasius2024robust, abstract = {Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations.}, author = {Bläsius, Thomas and Cohen, Sarel and Fischbeck, Philipp and Friedrich, Tobias and Krejca, Martin S.}, journal = {CoRR}, keywords = {sarelcohen philippfischbeck thomasblaesius martinskrejca tobiasfriedrich year2024 arxiv}, note = {ArXiv preprint}, title = {Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation}, volume = {arXiv:2402.05534}, year = 2024 }

2023 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise The Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessComputational Geometry (CGTA) 2023: 101902
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Schelling's classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We introduce an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to change their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge u,v is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and, moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge u,v makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c>0 such that the expected fraction of monochrome edges after the FSP is at least 1/2+c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2+o(1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.
@article{blasius2023impact, abstract = {Schelling's classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We introduce an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to change their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge {u,v} is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and, moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u,v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c>0 such that the expected fraction of monochrome edges after the FSP is at least 1/2+c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2+o(1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise}, journal = {Computational Geometry (CGTA)}, keywords = {sys:relevantfor:ae thomasblaesius louisemolitor martinskrejca tobiasfriedrich year2023 cgta}, pages = 101902, title = {The Impact of Geometry on Monochrome Regions in the Flip Schelling Process}, volume = 108, year = 2023 }

Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias Evolutionary Minimization of Traffic CongestionIEEE Transactions on Evolutionary Computation 2023: 1809–1821
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and destination and aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of Berlin, Germany. We find that a combination of all operators yields the best result, reducing the overall travel time by a factor between \(1.8\) and \(3\), in the median, compared to all drivers taking the fastest route. For the base case \(n = 2\), we compare our MREA to the highly tailored optimal solver by Bläsius et al. (ATMOS 2020), and show that, in the median, our approach finds solutions of quality at least \(99.69 \%\) of an optimal solution while only requiring \(40 \%\) of the time.
@article{2023evolutionary, abstract = {Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and destination and aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of Berlin, Germany. We find that a combination of all operators yields the best result, reducing the overall travel time by a factor between \(1.8\) and \(3\), in the median, compared to all drivers taking the fastest route. For the base case \(n = 2\), we compare our MREA to the highly tailored optimal solver by Bläsius et al. (ATMOS 2020), and show that, in the median, our approach finds solutions of quality at least \(99.69 \%\) of an optimal solution while only requiring \(40 \%\) of the time.}, author = {Böther, Maximilian and Schiller, Leon and Fischbeck, Philipp and Molitor, Louise and Krejca, Martin S. and Friedrich, Tobias}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {maximilianboether philippfischbeck louisemolitor martinskrejca tobiasfriedrich tevoc leonschiller year2023}, number = 6, pages = {1809-1821}, title = {Evolutionary Minimization of Traffic Congestion}, volume = 27, year = 2023 }

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus Polymer Dynamics via Cliques: New Conditions for ApproximationsTheoretical Computer Science 2023: 230–252
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least \(2^{1/\alpha}\) for the hard-core model on bipartite \(\alpha\)-expanders.
@article{friedrich2023polymer, abstract = {Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least \(2^{1/\alpha}\) for the hard-core model on bipartite \(\alpha\)-expanders.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, journal = {Theoretical Computer Science}, keywords = {tcs marcuspappik martinskrejca andreasgoebel tobiasfriedrich year2023}, pages = {230-252}, title = {Polymer Dynamics via Cliques: New Conditions for Approximations}, volume = 942, year = 2023 }

Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. The Common-Neighbors Metric is Noise-Robust and Reveals Substructures of Real-World NetworksPacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2023: 67–79
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Real-world networks typically display a complex structure that is hard to explain by a single model. A common approach is to partition the edges of the network into disjoint simpler structures. An important property in this context is locality—incident vertices usually have many common neighbors. This allows to classify edges into two groups, based on the number of the common neighbors of their incident vertices. Formally, this is captured by the common-neighbors (CN) metric, which forms the basis of many metrics for detecting outlier edges. Such outliers can be interpreted as noise or as a substructure. We aim to understand how useful the metric is, and empirically analyze several scenarios. We randomly insert outlier edges into real-world and generated graphs with high locality, and measure the metric accuracy for partitioning the combined edges. In addition, we use the metric to decompose real-world networks, and measure properties of the partitions. Our results show that the CN metric is a very good classifier that can reliably detect noise up to extreme levels (\(83\%\) noisy edges). We also provide mathematically rigorous analyses on special random-graph models. Last, we find the CN metric consistently decomposes real-world networks into two graphs with very different structures.
@inproceedings{cohen2023commonneighbors, abstract = {Real-world networks typically display a complex structure that is hard to explain by a single model. A common approach is to partition the edges of the network into disjoint simpler structures. An important property in this context is locality—incident vertices usually have many common neighbors. This allows to classify edges into two groups, based on the number of the common neighbors of their incident vertices. Formally, this is captured by the common-neighbors (CN) metric, which forms the basis of many metrics for detecting outlier edges. Such outliers can be interpreted as noise or as a substructure. We aim to understand how useful the metric is, and empirically analyze several scenarios. We randomly insert outlier edges into real-world and generated graphs with high locality, and measure the metric accuracy for partitioning the combined edges. In addition, we use the metric to decompose real-world networks, and measure properties of the partitions. Our results show that the CN metric is a very good classifier that can reliably detect noise up to extreme levels (\(83\%\) noisy edges). We also provide mathematically rigorous analyses on special random-graph models. Last, we find the CN metric consistently decomposes real-world networks into two graphs with very different structures.}, author = {Cohen, Sarel and Fischbeck, Philipp and Friedrich, Tobias and Krejca, Martin S.}, booktitle = {Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)}, keywords = {sarelcohen philippfischbeck martinskrejca tobiasfriedrich year2023 pakdd}, pages = {67–79}, title = {The Common-Neighbors Metric is Noise-Robust and Reveals Substructures of Real-World Networks}, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A Spectral Independence View on Hard Spheres via Block DynamicsSIAM Journal on Discrete Mathematics 2022: 2282–2322
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \(\lambda < \mathrm{e / 2d\), the runtime of our algorithm is polynomial in the volume of the system. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance, we use block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.
@article{friedrich2022spectral, abstract = {The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \(\lambda < \mathrm{e} / 2d\), the runtime of our algorithm is polynomial in the volume of the system. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance, we use block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich year2022}, number = 3, pages = {2282-2322}, title = {A Spectral Independence View on Hard Spheres via Block Dynamics}, volume = 36, year = 2022 }

Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Krejca, Martin S.; Pappik, Marcus Algorithms for hard-constraint point processes via discretizationInternational Computing and Combinatorics Conference (COCOON) 2022: 242–254
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom--Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom--Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom--Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.
@inproceedings{friedrich2022algorithms, abstract = {We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom&ndash;Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom&ndash;Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom&ndash;Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.}, author = {Friedrich, Tobias and Göbel, Andreas and Katzmann, Maximilian and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Computing and Combinatorics Conference (COCOON)}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich cocoon maximiliankatzmann year2022}, pages = {242–254}, title = {Algorithms for hard-constraint point processes via discretization}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Rajabi, Amirhossein Escaping Local Optima With Local Search: A Theory-Driven DiscussionParallel Problem Solving from Nature (PPSN) 2022: 442–455
Best Paper Award and Best Poster Award
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Local search is the most basic strategy in optimization settings when no specific problem knowledge is employed. While this strategy finds good solutions for certain optimization problems, it generally suffers from getting stuck in local optima. This stagnation can be avoided if local search is modified. Depending on the optimization landscape, different modifications vary in their success. We discuss several features of optimization landscapes and give analyses as examples for how they affect the performance of modifications of local search. We consider modifying random local search by restarting it and by considering larger search radii. The landscape features we analyze include the number of local optima, the distance between different optima, as well as the local landscape around a local optimum. For each feature, we show which modifications of local search handle them well and which do not.
@inproceedings{friedrich2022escaping, abstract = {Local search is the most basic strategy in optimization settings when no specific problem knowledge is employed. While this strategy finds good solutions for certain optimization problems, it generally suffers from getting stuck in local optima. This stagnation can be avoided if local search is modified. Depending on the optimization landscape, different modifications vary in their success. We discuss several features of optimization landscapes and give analyses as examples for how they affect the performance of modifications of local search. We consider modifying random local search by restarting it and by considering larger search radii. The landscape features we analyze include the number of local optima, the distance between different optima, as well as the local landscape around a local optimum. For each feature, we show which modifications of local search handle them well and which do not.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Rajabi, Amirhossein}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {martinskrejca timokoetzing tobiasfriedrich amirhosseinrajabi year2022 ppsn}, note = {Best Paper Award and Best Poster Award}, pages = {442-455}, title = {Escaping Local Optima With Local Search: A Theory-Driven Discussion}, year = 2022 }

Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Sauerwald, Thomas Accelerated Information Dissemination on Networks with Local and Global EdgesStructural Information and Communication Complexity (SIROCCO) 2022: 79–97
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least \(r\) neighbors were active in the previous round. We propose the \emph{perturbed percolation process: a superposition of two percolation processes on the same node set. One process acts on a local graph with activation threshold~\(1\), the other acts on a global graph with threshold \(r\)~-- representing local and global edges, respectively. We consider grid-like local graphs and expanders as global graphs on~\(n\) nodes. For the extreme case \(r = 1\), all nodes are active after \(O(\log n)\) rounds, while the process spreads only polynomially fast for the other extreme case \(r \geq n\). For a range of suitable values of~\(r\), we prove that the process exhibits both phases of the above extremes: It starts with a polynomial growth and eventually transitions from at most \(cn\) to~\(n\) active nodes, for some constant \(c in (0, 1)\), in \(O(\log n)\) rounds. We observe this behavior also empirically, considering additional global-graph models.
@inproceedings{cohen2022accelerated, abstract = {Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least \(r\) neighbors were active in the previous round. We propose the \emph{perturbed} percolation process: a superposition of two percolation processes on the same node set. One process acts on a local graph with activation threshold&nbsp;\(1\), the other acts on a global graph with threshold \(r\)&nbsp;&ndash; representing local and global edges, respectively. We consider grid-like local graphs and expanders as global graphs on&nbsp;\(n\) nodes. For the extreme case \(r = 1\), all nodes are active after \(O(\log n)\) rounds, while the process spreads only polynomially fast for the other extreme case \(r \geq n\). For a range of suitable values of&nbsp;\(r\), we prove that the process exhibits both phases of the above extremes: It starts with a polynomial growth and eventually transitions from at most \(cn\) to&nbsp;\(n\) active nodes, for some constant \(c \in (0, 1)\), in \(O(\log n)\) rounds. We observe this behavior also empirically, considering additional global-graph models.}, author = {Cohen, Sarel and Fischbeck, Philipp and Friedrich, Tobias and Krejca, Martin S. and Sauerwald, Thomas}, booktitle = {Structural Information and Communication Complexity (SIROCCO)}, keywords = {sarelcohen philippfischbeck martinskrejca sirocco tobiasfriedrich year2022 thomassauerwald}, pages = {79&ndash;97}, title = {Accelerated Information Dissemination on Networks with Local and Global Edges}, year = 2022 }

2021 [ nach oben ]

Doerr, Benjamin; Krejca, Martin S. A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnesTheoretical Computer Science 2021: 121–128
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(lambda \frac{n - \log(n\lambda)}log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.
@article{doerr2021simplified, abstract = {With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e} \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{\log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(\lambda \frac{n - \log(n\lambda)}{\log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.}, author = {Doerr, Benjamin and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {tcs martinskrejca benjamindoerr year2021}, pages = {121-128}, title = {A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes}, volume = 851, year = 2021 }

Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias Evolutionary Minimization of Traffic CongestionGenetic and Evolutionary Computation Conference (GECCO) 2021: 937–945
Best-Paper Award (RWA Track)
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and a destination and then aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of the city of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case \(n=2\), we compare our MREA to the highly tailored optimal solver by Bläsius etal. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least \(99.69\%\) of an optimal solution while only requiring \(40\%\) of the time.
@inproceedings{boether2021evolutionary, abstract = {Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and a destination and then aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of the city of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case \(n=2\), we compare our MREA to the highly tailored optimal solver by Bläsius etal. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least \(99.69\%\) of an optimal solution while only requiring \(40\%\) of the time.}, author = {Böther, Maximilian and Schiller, Leon and Fischbeck, Philipp and Molitor, Louise and Krejca, Martin S. and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {maximilianboether philippfischbeck louisemolitor martinskrejca tobiasfriedrich gecco leonschiller year2021}, note = {Best-Paper Award (RWA Track)}, pages = {937&ndash;945}, title = {Evolutionary Minimization of Traffic Congestion}, year = 2021 }

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A spectral independence view on hard spheres via block dynamicsInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \( \lambda < \text{e}/2^d\), the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.
@inproceedings{fgkp-asivohsvbd-2021, abstract = {The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \( \lambda < \text{e}/2^d\), the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich icalp year2021}, pages = {66:1-66:15}, title = {A spectral independence view on hard spheres via block dynamics}, volume = 198, year = 2021 }

Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise The Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessInternational Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Schelling’s classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We consider an agent-based saturated open-city variant, the Flip-Schelling-Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to changes their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge u,vis monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge u,v makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the FSP is at least 1/2 + c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2 + o (1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.
@inproceedings{blasius2021impact, abstract = {Schelling’s classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We consider an agent-based saturated open-city variant, the Flip-Schelling-Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to changes their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge {u,v}is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u,v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the FSP is at least 1/2 + c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2 + o (1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise}, booktitle = {International Symposium on Algorithms and Computation, (ISAAC) 2021}, keywords = {sys:relevantfor:ae thomasblaesius isaac louisemolitor martinskrejca tobiasfriedrich year2021}, pages = {29:1&ndash;29:17}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {The Impact of Geometry on Monochrome Regions in the Flip Schelling Process}, volume = 212, year = 2021 }

2020 [ nach oben ]

Doerr, Benjamin; Krejca, Martin S. Significance-based Estimation-of-Distribution AlgorithmsIEEE Transactions on Evolutionary Computation 2020: 1025–1034
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the commonly regarded benchmark functions OneMax, LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in its hypothetical population size. Similarly, we show that the convex search algorithm cannot optimize OneMax in polynomial time.
@article{doerrsignificancebased, abstract = {Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the commonly regarded benchmark functions OneMax, LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in its hypothetical population size. Similarly, we show that the convex search algorithm cannot optimize OneMax in polynomial time.}, author = {Doerr, Benjamin and Krejca, Martin S.}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {martinskrejca benjamindoerr tevoc year2020}, number = 6, pages = {1025-1034}, publisher = {IEEE}, title = {Significance-based Estimation-of-Distribution Algorithms}, volume = 24, year = 2020 }

Krejca, Martin S.; Witt, Carsten Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMaxTheoretical Computer Science 2020: 143–165
[ 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 on bit strings of length \(n\), a lower bound of \(\Omega(\lambda + \mu \sqrt{n} + n\log n)\), where \(\mu\) and \(\lambda\) are algorithm-specific parameters, on its expected run time is proved. This is the first direct lower bound on the run time of 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.
@article{krejca2020lower, abstract = {The Univariate Marginal Distribution Algorithm (UMDA) &ndash; a popular estimation-of-distribution algorithm &ndash; is studied from a run time perspective. On the classical OneMax benchmark function on bit strings of length \(n\), a lower bound of \(\Omega(\lambda + \mu \sqrt{n} + n\log n)\), where \(\mu\) and \(\lambda\) are algorithm-specific parameters, on its expected run time is proved. This is the first direct lower bound on the run time of 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}, journal = {Theoretical Computer Science}, keywords = {tcs martinskrejca carstenwitt year2020}, pages = {143-165}, title = {Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax}, volume = 832, year = 2020 }

Krejca, Martin S.; Witt, Carsten Theory of Estimation-of-Distribution AlgorithmsTheory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405–442
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Estimation-of-distribution algorithms (EDAs) are general metaheuristics used in optimization that represent a more recent alternative to classical approaches such as evolutionary algorithms. In a nutshell, EDAs typically do not directly evolve populations of search points but build probabilistic models of promising solutions by repeatedly sampling and selecting points from the underlying search space. Recently, significant progress has been made in the theoretical understanding of EDAs. This chapter provides an up-to-date overview of the most commonly analyzed EDAs and the most recent theoretical results in this area. In particular, emphasis is put on the runtime analysis of simple univariate EDAs, including a description of typical benchmark functions and tools for the analysis. Along the way, open problems and directions for future research are described.
@incollection{krejca2020theory, abstract = {Estimation-of-distribution algorithms (EDAs) are general metaheuristics used in optimization that represent a more recent alternative to classical approaches such as evolutionary algorithms. In a nutshell, EDAs typically do not directly evolve populations of search points but build probabilistic models of promising solutions by repeatedly sampling and selecting points from the underlying search space. Recently, significant progress has been made in the theoretical understanding of EDAs. This chapter provides an up-to-date overview of the most commonly analyzed EDAs and the most recent theoretical results in this area. In particular, emphasis is put on the runtime analysis of simple univariate EDAs, including a description of typical benchmark functions and tools for the analysis. Along the way, open problems and directions for future research are described.}, author = {Krejca, Martin S. and Witt, Carsten}, booktitle = {Theory of Evolutionary Computation: Recent Developments in Discrete Optimization}, chapter = 9, editor = {Doerr, Benjamin and Neumann, Frank}, keywords = {sys:relevantfor:ae martinskrejca carstenwitt year2020}, pages = {405-442}, publisher = {Springer}, series = {Natural Computing Series}, title = {Theory of Estimation-of-Distribution Algorithms}, year = 2020 }

Doerr, Benjamin; Krejca, Martin S. The Univariate Marginal Distribution Algorithm Copes Well with Deception and EpistasisEvolutionary Computation in Combinatorial Optimization (EvoCOP) 2020: 51–66
Best-Paper Award
[ BibTeX ] [ DOI ] [ Download ]
 
@inproceedings{doerrunivariate, author = {Doerr, Benjamin and Krejca, Martin S.}, booktitle = {Evolutionary Computation in Combinatorial Optimization (EvoCOP)}, keywords = {martinskrejca evocop benjamindoerr year2020}, note = {Best-Paper Award}, pages = {51-66}, publisher = {Springer}, title = {The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis}, year = 2020 }

Doerr, Benjamin; Krejca, Martin S. Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of OptimaGenetic and Evolutionary Computation Conference (GECCO) 2020: 796–804
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Finding a large set of optima in a multimodal optimization landscape is a challenging task. Classical population-based evolutionary algorithms (EAs) typically converge only to a single solution. While this can be counteracted by applying niching strategies, the number of optima is nonetheless trivially bounded by the population size. Estimation-of-distribution algorithms (EDAs) provide an alternative approach by maintaining a probabilistic model of the solution space instead of an explicit population. Such a model has the benefit of being able to implicitly represent a solution set that is far larger than any realistic population size. To support the study of how optimization algorithms handle large sets of optima, we propose the test function EqualBlocksOneMax (EBOM). It has an easy to optimize fitness landscape, however, with an exponential number of optima. We show that the bivariate EDA mutual-information-maximizing input clustering (MIMIC), without any problem-specific modification, quickly generates a model that behaves very similarly to a theoretically ideal model for that function, which samples each of the exponentially many optima with the same maximal probability.
@inproceedings{doerr2020bivariate, abstract = {Finding a large set of optima in a multimodal optimization landscape is a challenging task. Classical population-based evolutionary algorithms (EAs) typically converge only to a single solution. While this can be counteracted by applying niching strategies, the number of optima is nonetheless trivially bounded by the population size. Estimation-of-distribution algorithms (EDAs) provide an alternative approach by maintaining a probabilistic model of the solution space instead of an explicit population. Such a model has the benefit of being able to implicitly represent a solution set that is far larger than any realistic population size. To support the study of how optimization algorithms handle large sets of optima, we propose the test function EqualBlocksOneMax (EBOM). It has an easy to optimize fitness landscape, however, with an exponential number of optima. We show that the bivariate EDA mutual-information-maximizing input clustering (MIMIC), without any problem-specific modification, quickly generates a model that behaves very similarly to a theoretically ideal model for that function, which samples each of the exponentially many optima with the same maximal probability.}, author = {Doerr, Benjamin and Krejca, Martin S.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca benjamindoerr gecco year2020}, pages = {796–804}, title = {Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima}, year = 2020 }

Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, Arthur Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear ApproximationInternational Conference on Neural Information Processing (ICONIP) 2020: 592–604
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Time series are sequences of data indexed by time. Such data are collected in various domains, often in massive amounts, such that storing them proves challenging. Thus, time series are commonly stored in a compressed format. An important compression approach is piecewise linear approximation (PLA), which only keeps a small set of time points and interpolates the remainder linearly. Picking a subset of time points such that the PLA minimizes the mean squared error to the original time series is a challenging task, naturally lending itself to heuristics. We propose the piecewise linear approximation genetic algorithm (PLA-GA) for compressing time series by PLA. The PLA-GA is a memetic \((\mu + \lambda)\) GA that makes use of two distinct operators tailored to time series compression. First, we add special individuals to the initial population that are derived using established PLA heuristics. Second, we propose a novel local search operator that greedily improves a compressed time series. We compare the PLA-GA empirically with existing evolutionary approaches and with a deterministic PLA algorithm, known as Bellman's algorithm, that is optimal for the restricted setting of sampling. In both cases, the PLA-GA approximates the original time series better and quicker. Further, it drastically outperforms Bellman's algorithm with increasing instance size with respect to run time until finding a solution of equal or better quality -- we observe speed-up factors between 7 and 100 for instances of 90,000 to 100,000 data points.
@inproceedings{friedrich2020memetic, abstract = {Time series are sequences of data indexed by time. Such data are collected in various domains, often in massive amounts, such that storing them proves challenging. Thus, time series are commonly stored in a compressed format. An important compression approach is piecewise linear approximation (PLA), which only keeps a small set of time points and interpolates the remainder linearly. Picking a subset of time points such that the PLA minimizes the mean squared error to the original time series is a challenging task, naturally lending itself to heuristics. We propose the piecewise linear approximation genetic algorithm (PLA-GA) for compressing time series by PLA. The PLA-GA is a memetic \((\mu + \lambda)\) GA that makes use of two distinct operators tailored to time series compression. First, we add special individuals to the initial population that are derived using established PLA heuristics. Second, we propose a novel local search operator that greedily improves a compressed time series. We compare the PLA-GA empirically with existing evolutionary approaches and with a deterministic PLA algorithm, known as Bellman's algorithm, that is optimal for the restricted setting of sampling. In both cases, the PLA-GA approximates the original time series better and quicker. Further, it drastically outperforms Bellman's algorithm with increasing instance size with respect to run time until finding a solution of equal or better quality &ndash; we observe speed-up factors between 7 and 100 for instances of 90,000 to 100,000 data points.}, author = {Friedrich, Tobias and Krejca, Martin S. and Lagodzinski, J. A. Gregor and Rizzo, Manuel and Zahn, Arthur}, booktitle = {International Conference on Neural Information Processing (ICONIP)}, keywords = {gregorlagodzinski martinskrejca manuelrizzo tobiasfriedrich arthurzahn iconip year2020}, pages = {592-604}, title = {Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation}, volume = 12534, year = 2020 }

2019 [ nach oben ]

Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin Routing for On-Street Parking Search using Probabilistic DataAI Communications 2019: 113–124
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.
@article{friedrich2019routing, abstract = {A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.}, author = {Friedrich, Tobias and Krejca, Martin S. and Rothenberger, Ralf and Arndt, Tobias and Hafner, Danijar and Kellermeier, Thomas and Krogmann, Simon and Razmjou, Armin}, journal = {AI Communications}, keywords = {tobiasarndt year2019 martinskrejca thomaskellermeier tobiasfriedrich arminrazmjou ralfrothenberger simonkrogmann danijarhafner}, number = 2, pages = {113-124}, title = {Routing for On-Street Parking Search using Probabilistic Data}, volume = 32, year = 2019 }

Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian Surfing on the seascape: Adaptation in a changing environmentEvolution: International Journal of Organic Evolution 2019: 1356–1374
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The environment changes constantly at various time scales and, in order to survive, species need to keep adapting. Whether these species succeed in avoiding extinction is a major evolutionary question. Using a multilocus evolutionary model of a mutation‐limited population adapting under strong selection, we investigate the effects of the frequency of environmental fluctuations on adaptation. Our results rely on an "adaptive‐walk" approximation and use mathematical methods from evolutionary computation theory to investigate the interplay between fluctuation frequency, the similarity of environments, and the number of loci contributing to adaptation. First, we assume a linear additive fitness function, but later generalize our results to include several types of epistasis. We show that frequent environmental changes prevent populations from reaching a fitness peak, but they may also prevent the large fitness loss that occurs after a single environmental change. Thus, the population can survive, although not thrive, in a wide range of conditions. Furthermore, we show that in a frequently changing environment, the similarity of threats that a population faces affects the level of adaptation that it is able to achieve. We check and supplement our analytical results with simulations.
@article{trubenova2019surfing, abstract = {The environment changes constantly at various time scales and, in order to survive, species need to keep adapting. Whether these species succeed in avoiding extinction is a major evolutionary question. Using a multilocus evolutionary model of a mutation‐limited population adapting under strong selection, we investigate the effects of the frequency of environmental fluctuations on adaptation. Our results rely on an "adaptive‐walk" approximation and use mathematical methods from evolutionary computation theory to investigate the interplay between fluctuation frequency, the similarity of environments, and the number of loci contributing to adaptation. First, we assume a linear additive fitness function, but later generalize our results to include several types of epistasis. We show that frequent environmental changes prevent populations from reaching a fitness peak, but they may also prevent the large fitness loss that occurs after a single environmental change. Thus, the population can survive, although not thrive, in a wide range of conditions. Furthermore, we show that in a frequently changing environment, the similarity of threats that a population faces affects the level of adaptation that it is able to achieve. We check and supplement our analytical results with simulations.}, author = {Trubenova, Barbora and Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian}, journal = {Evolution: International Journal of Organic Evolution}, keywords = {ev barboratrubenova perkristianlehre sys:relevantfor:ae year2019 martinskrejca timokoetzing}, number = 7, pages = {1356-1374}, title = {Surfing on the seascape: Adaptation in a changing environment}, volume = 73, year = 2019 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. Unbiasedness of Estimation-of-Distribution AlgorithmsTheoretical Computer Science 2019: 46–59
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics – especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced \(n\)-Bernoulli-\(\lambda\)-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, \(\lambda\)-MMAS\(_\textrm{IB}\), and cGA. We show that an \(n\)-Bernoulli-\(\lambda\)-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of \([0, 1]^n\). By restricting how an \(n\)-Bernoulli-\(\lambda\)-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased.
@article{friedrich2019unbiasedness, abstract = {In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics – especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced \(n\)-Bernoulli-\(\lambda\)-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, \(\lambda\)-MMAS\(_\textrm{IB}\), and cGA. We show that an \(n\)-Bernoulli-\(\lambda\)-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of \([0, 1]^n\). By restricting how an \(n\)-Bernoulli-\(\lambda\)-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {tcs year2019 martinskrejca timokoetzing tobiasfriedrich}, pages = {46-59}, title = {Unbiasedness of Estimation-of-Distribution Algorithms}, volume = 785, year = 2019 }

Kötzing, Timo; Krejca, Martin S. First-hitting times under driftTheoretical Computer Science 2019: 51–69
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be lower-bounded, that is, we remove unnecessary restrictions like a finite, discrete, or bounded state space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift. By bounding the step size of the process, we derive new lower-bounding multiplicative and variable drift theorems. Last, we also state theorems that are applicable when the process has a drift of 0, by using a drift on the variance of the process.
@article{ktzing2019firsthitting, abstract = {For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be lower-bounded, that is, we remove unnecessary restrictions like a finite, discrete, or bounded state space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift. By bounding the step size of the process, we derive new lower-bounding multiplicative and variable drift theorems. Last, we also state theorems that are applicable when the process has a drift of 0, by using a drift on the variance of the process.}, author = {Kötzing, Timo and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {tcs year2019 martinskrejca timokoetzing}, pages = {51-69}, title = {First-hitting times under drift}, volume = 796, year = 2019 }

Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, Tobias Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment ProblemInternational Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a state-of-the-art solver to get solutions that closely approximate the optimum. In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA. For our real-world instance of the assignment problem, given the same total time budget of \(100\) hours, a parallel EA approach finds a solution that is only \(1.7\)% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of \(10.5\) %.
@inproceedings{peters2019mixed, abstract = {Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a state-of-the-art solver to get solutions that closely approximate the optimum. In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA. For our real-world instance of the assignment problem, given the same total time budget of \(100\) hours, a parallel EA approach finds a solution that is only \(1.7\)\% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of \(10.5\) \%.}, author = {Peters, Jannik and Stephan, Daniel and Amon, Isabel and Gawendowicz, Hans and Lischeid, Julius and Salabarria, Julius and Umland, Jonas and Werner, Felix and Krejca, Martin S. and Rothenberger, Ralf and Kötzing, Timo and Friedrich, Tobias}, booktitle = {International Conference on Automated Planning and Scheduling (ICAPS)}, keywords = {year2019 martinskrejca felixwerner tobiasfriedrich danielstephan hansgawendowicz jonasumland timokoetzing isabelamon lennartsalabarria jannikpeters juliuslischeid ralfrothenberger icaps}, pages = {541-554}, title = {Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem}, year = 2019 }

2018 [ nach oben ]

Dang, Duc-Cuong; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M. Escaping Local Optima Using Crossover with Emergent DiversityIEEE Transactions on Evolutionary Computation 2018: 484–497
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^{k-1})\) for duplicate elimination/minimisation, \(O(n^2 \log n)\) for maximising the convex hull, \(O(n \log n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n \log n)\) for maximising the Hamming distance, \(O(n \log n)\) for fitness sharing, \(O(n \log n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.
@article{dang2017escaping, abstract = {Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^{k-1})\) for duplicate elimination/minimisation, \(O(n^2 \log n)\) for maximising the convex hull, \(O(n \log n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n \log n)\) for maximising the Hamming distance, \(O(n \log n)\) for fitness sharing, \(O(n \log n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.}, author = {Dang, Duc-Cuong and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.}, editor = {Tan, Kay Chen}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {martinskrejca timokoetzing year2018 tobiasfriedrich tevoc andrewmsutton}, month = {jun}, number = 3, pages = {484-497}, publisher = {IEEE}, title = {Escaping Local Optima Using Crossover with Emergent Diversity}, volume = 22, year = 2018 }

Doerr, Benjamin; Krejca, Martin S. Significance-based Estimation-of-Distribution AlgorithmsGenetic and Evolutionary Computation Conference (GECCO) 2018: 1483–1490
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this short-term perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. This can lead to significant performance losses. In order to overcome this problem, we propose a new EDA that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the common benchmark functions OneMax and LeadingOnes both in \(O(n\log n)\) time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in the hypothetical population size \(1/\rho\).
@inproceedings{doerr2018significancebased, abstract = {Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this short-term perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. This can lead to significant performance losses. In order to overcome this problem, we propose a new EDA that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the common benchmark functions OneMax and LeadingOnes both in \(O(n\log n)\) time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in the hypothetical population size \(1/\rho\).}, author = {Doerr, Benjamin and Krejca, Martin S.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca year2018 GECCO benjamindoerr}, pages = {1483-1490}, title = {Significance-based Estimation-of-Distribution Algorithms}, year = 2018 }

Kötzing, Timo; Krejca, Martin S. First-Hitting Times for Finite State SpacesParallel Problem Solving From Nature (PPSN) 2018: 79–91
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
One of the most important aspects of a randomized algorithm is bounding its expected run time on various problems. Formally speaking, this means bounding the expected first-hitting time of a random process. The two arguably most popular tools to do so are the fitness level method and drift theory. The fitness level method considers arbitrary transition probabilities but only allows the process to move toward the goal. On the other hand, drift theory allows the process to move into any direction as long as it moves closer to the goal in expectation; however, this tendency has to be monotone and, thus, the transition probabilities cannot be arbitrary. We provide a result that combines the benefit of these two approaches: our result gives a lower and an upper bound for the expected first-hitting time of a random process over \(\{0, \ldots ,n\}\) that is allowed to move forward and backward by 1 and can use arbitrary transition probabilities. In case that the transition probabilities are known, our bounds coincide and yield the exact value of the expected first-hitting time. Further, we also state the stationary distribution as well as the mixing time of a special case of our scenario.
@inproceedings{kotzing2018firsthitting, abstract = {One of the most important aspects of a randomized algorithm is bounding its expected run time on various problems. Formally speaking, this means bounding the expected first-hitting time of a random process. The two arguably most popular tools to do so are the fitness level method and drift theory. The fitness level method considers arbitrary transition probabilities but only allows the process to move toward the goal. On the other hand, drift theory allows the process to move into any direction as long as it moves closer to the goal in expectation; however, this tendency has to be monotone and, thus, the transition probabilities cannot be arbitrary. We provide a result that combines the benefit of these two approaches: our result gives a lower and an upper bound for the expected first-hitting time of a random process over \(\{0, \ldots ,n\}\) that is allowed to move forward and backward by 1 and can use arbitrary transition probabilities. In case that the transition probabilities are known, our bounds coincide and yield the exact value of the expected first-hitting time. Further, we also state the stationary distribution as well as the mixing time of a special case of our scenario.}, author = {Kötzing, Timo and Krejca, Martin S.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {martinskrejca timokoetzing year2018 ppsn}, pages = {79-91}, title = {First-Hitting Times for Finite State Spaces}, year = 2018 }

Kötzing, Timo; Krejca, Martin S. First-Hitting Times Under Additive DriftParallel Problem Solving From Nature (PPSN) 2018: 92–104
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift
@inproceedings{kotzingyear2018firsthitting, abstract = {For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift}, author = {Kötzing, Timo and Krejca, Martin S.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {martinskrejca timokoetzing year2018 ppsn}, pages = {92-104}, title = {First-Hitting Times Under Additive Drift}, year = 2018 }

Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, Justin Memory-restricted Routing With Tiled Map DataSystems, Man, and Cybernetics (SMC) 2018: 3347–3354
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
@inproceedings{blasius2018memory, abstract = {Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.}, author = {Bläsius, Thomas and Eube, Jan and Feldtkeller, Thomas and Friedrich, Tobias and Krejca, Martin S. and Lagodzinski, J. A. Gregor and Rothenberger, Ralf and Severin, Julius and Sommer, Fabian and Trautmann, Justin}, booktitle = {Systems, Man, and Cybernetics (SMC)}, keywords = {gregorlagodzinski janeube juliusseverin thomasblaesius martinskrejca year2018 thomasfeldtkeller smc tobiasfriedrich justintrautmann fabiansommer ralfrothenberger}, month = 10, pages = {3347-3354}, title = {Memory-restricted Routing With Tiled Map Data}, year = 2018 }

2017 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Compact Genetic Algorithm is Efficient under Extreme Gaussian NoiseIEEE Transactions on Evolutionary Computation 2017: 477–490
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.
@article{friedrich2017compact, abstract = {Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, journal = {IEEE Transactions on Evolutionary Computation}, keywords = {martinskrejca timokoetzing year2017 tobiasfriedrich tevoc andrewmsutton}, number = 3, pages = {477-490}, publisher = {IEEE}, title = {The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise}, volume = 21, year = 2017 }

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 }

2016 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to NoiseEvolutionary Computation 2016: 237–254
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical \((\mu+1)\)-EA outperforms any ACO algorithm, with smaller \(\mu\) being better; however, with large noise, the \((\mu+1)\)-EA fails, even for high values of \(\mu\) (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor \(p\) is small enough dependent on the parameter \(\delta^2\) of the noise and the dimension \(n\) of the search space \((p = o(1/(n(n + \delta \log n)^2 \log n)))\), optimization will be successful.
@article{DBLP:journals/ec/FriedrichKKS16, abstract = {Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical \((\mu+1)\)-EA outperforms any ACO algorithm, with smaller \(\mu\) being better; however, with large noise, the \((\mu+1)\)-EA fails, even for high values of \(\mu\) (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor \(p\) is small enough dependent on the parameter \(\delta^2\) of the noise and the dimension \(n\) of the search space \((p = o(1/(n(n + \delta \log n)^2 \log n)))\), optimization will be successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, journal = {Evolutionary Computation}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich andrewmsutton EC}, number = 2, pages = {237-254}, title = {Robustness of Ant Colony Optimization to Noise}, volume = 24, year = 2016 }

Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, Tobias Probabilistic Routing for On-Street Parking SearchEuropean Symposium on Algorithms (ESA) 2016: 6:1–6:13
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
An estimated \(30\%\) of urban traffic is caused by search for parking spots. Traffic could be reduced by suggesting effective routes leading along potential parking spots. In this paper, we formalize parking search as a probabilistic problem on a road graph and show that it is NP-complete. We explore heuristics that optimize for the driving duration and the walking distance to the destination. Routes are constrained to reach a certain probability threshold of finding a spot. Empirically estimated probabilities of successful parking attempts are provided by TomTom on a per-street basis. We release these probabilities as a dataset of about 80,000 roads covering the Berlin area. This allows to evaluate parking search algorithms on a real road network with realistic probabilities for the first time. However, for many other areas, parking probabilities are not openly available. Because they are effortful to collect, we propose an algorithm that relies on conventional road attributes only. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. This leads to the conclusion that conventional road attributes may be sufficient to compute reasonably good parking search routes.
@inproceedings{DBLP:conf/esa/ArndtHKKRKRF16, abstract = {An estimated \(30\%\) of urban traffic is caused by search for parking spots. Traffic could be reduced by suggesting effective routes leading along potential parking spots. In this paper, we formalize parking search as a probabilistic problem on a road graph and show that it is NP-complete. We explore heuristics that optimize for the driving duration and the walking distance to the destination. Routes are constrained to reach a certain probability threshold of finding a spot. Empirically estimated probabilities of successful parking attempts are provided by TomTom on a per-street basis. We release these probabilities as a dataset of about 80,000 roads covering the Berlin area. This allows to evaluate parking search algorithms on a real road network with realistic probabilities for the first time. However, for many other areas, parking probabilities are not openly available. Because they are effortful to collect, we propose an algorithm that relies on conventional road attributes only. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. This leads to the conclusion that conventional road attributes may be sufficient to compute reasonably good parking search routes.}, author = {Arndt, Tobias and Hafner, Danijar and Kellermeier, Thomas and Krogmann, Simon and Razmjou, Armin and Krejca, Martin S. and Rothenberger, Ralf and Friedrich, Tobias}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {ESA tobiasarndt martinskrejca year2016 thomaskellermeier tobiasfriedrich arminrazmjou ralfrothenberger simonkrogmann danijarhafner}, pages = {6:1-6:13}, title = {Probabilistic Routing for On-Street Parking Search}, year = 2016 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary SearchGenetic and Evolutionary Computation Conference (GECCO) 2016: 161–162
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the Compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.
@inproceedings{DBLP:conf/gecco/FriedrichKKS16, abstract = {Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the Compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich gecco andrewmsutton}, pages = {161-162}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2016 }

Dang, Duc-Cuong; Friedrich, Tobias; Krejca, Martin S.; Kötzing, Timo; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew Michael Escaping Local Optima with Diversity Mechanisms and CrossoverGenetic and Evolutionary Computation Conference (GECCO) 2016: 645–652
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^{k-1})\) for duplicate elimination/minimisation, \(O(n^2 \log n)\) for maximising the convex hull, \(O(n \log n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n \log n)\) for maximising the Hamming distance, \(O(n \log n)\) for fitness sharing, \(O(n \log n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.
@inproceedings{DBLP:conf/gecco/DangFKKLOSS16, abstract = {Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^{k-1})\) for duplicate elimination/minimisation, \(O(n^2 \log n)\) for maximising the convex hull, \(O(n \log n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n \log n)\) for maximising the Hamming distance, \(O(n \log n)\) for fitness sharing, \(O(n \log n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.}, author = {Dang, Duc-Cuong and Friedrich, Tobias and Krejca, Martin S. and Kötzing, Timo and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew Michael}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich gecco andrewmsutton}, pages = {645-652}, publisher = {ACM Press}, title = {Escaping Local Optima with Diversity Mechanisms and Crossover}, year = 2016 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, Martin Fast Building Block Assembly by Majority Vote CrossoverGenetic and Evolutionary Computation Conference (GECCO) 2016: 661–668
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Different works have shown how crossover can help with building block assembly. Typically, crossover might get lucky to select good building blocks from each parent, but these lucky choices are usually rare. In this work we consider a crossover operator which works on three parent individuals. In each component, the offspring inherits the value present in the majority of the parents; thus, we call this crossover operator majority vote. We show that, if good components are sufficiently prevalent in the individuals, majority vote creates an optimal individual with high probability. Furthermore, we show that this process can be amplified: as long as components are good independently and with probability at least \(1/2+\delta\), we require only \(O(\log 1/\delta + \log \log n)\) successive stages of majority vote to create an optimal individual with high probability! We show how this applies in two scenarios. The first scenario is the Jump test function. With sufficient diversity, we get an optimization time of \(O(n \log n)\) even for jump sizes as large as \(O(n^{(1/2-\epsilon)})\). Our second scenario is a family of vertex cover instances. Majority vote optimizes this family efficiently, while local searches fail and only highly specialized two-parent crossovers are successful.
@inproceedings{DBLP:conf/gecco/FriedrichKKNNS16, abstract = {Different works have shown how crossover can help with building block assembly. Typically, crossover might get lucky to select good building blocks from each parent, but these lucky choices are usually rare. In this work we consider a crossover operator which works on three parent individuals. In each component, the offspring inherits the value present in the majority of the parents; thus, we call this crossover operator majority vote. We show that, if good components are sufficiently prevalent in the individuals, majority vote creates an optimal individual with high probability. Furthermore, we show that this process can be amplified: as long as components are good independently and with probability at least \(1/2+\delta\), we require only \(O(\log 1/\delta + \log \log n)\) successive stages of majority vote to create an optimal individual with high probability! We show how this applies in two scenarios. The first scenario is the Jump test function. With sufficient diversity, we get an optimization time of \(O(n \log n)\) even for jump sizes as large as \(O(n^{(1/2-\epsilon)})\). Our second scenario is a family of vertex cover instances. Majority vote optimizes this family efficiently, while local searches fail and only highly specialized two-parent crossovers are successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Nallaperuma, Samadhi and Neumann, Frank and Schirneck, Martin}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {samadhinallaperuma martinskrejca timokoetzing year2016 GECCO tobiasfriedrich frankneumann martinschirneck}, pages = {661-668}, publisher = {ACM Press}, title = {Fast Building Block Assembly by Majority Vote Crossover}, year = 2016 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. EDAs cannot be Balanced and StableGenetic and Evolutionary Computation Conference (GECCO) 2016: 1139–1146
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Estimation of Distribution Algorithms (EDAs) work by iteratively updating a distribution over the search space with the help of samples from each iteration. Up to now, theoretical analyses of EDAs are scarce and present run time results for specific EDAs. We propose a new framework for EDAs that captures the idea of several known optimizers, including PBIL, UMDA, \(\lambda\)-MMASIB, cGA, and \((1,\lambda)\)-EA. Our focus is on analyzing two core features of EDAs: a balanced EDA is sensitive to signals in the fitness; a stable EDA remains uncommitted under a biasless fitness function. We prove that no EDA can be both balanced and stable. The LeadingOnes function is a prime example where, at the beginning of the optimization, the fitness function shows no bias for many bits. Since many well-known EDAs are balanced and thus not stable, they are not well-suited to optimize LeadingOnes. We give a stable EDA which optimizes LeadingOnes within a time of \(O(n\,\log n)\).
@inproceedings{DBLP:conf/gecco/FriedrichKK16, abstract = {Estimation of Distribution Algorithms (EDAs) work by iteratively updating a distribution over the search space with the help of samples from each iteration. Up to now, theoretical analyses of EDAs are scarce and present run time results for specific EDAs. We propose a new framework for EDAs that captures the idea of several known optimizers, including PBIL, UMDA, \(\lambda\)-MMASIB, cGA, and \((1,\lambda)\)-EA. Our focus is on analyzing two core features of EDAs: a balanced EDA is sensitive to signals in the fitness; a stable EDA remains uncommitted under a biasless fitness function. We prove that no EDA can be both balanced and stable. The LeadingOnes function is a prime example where, at the beginning of the optimization, the fitness function shows no bias for many bits. Since many well-known EDAs are balanced and thus not stable, they are not well-suited to optimize LeadingOnes. We give a stable EDA which optimizes LeadingOnes within a time of \(O(n\,\log n)\).}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {martinskrejca timokoetzing year2016 GECCO tobiasfriedrich}, pages = {1139-1146}, title = {{EDA}s cannot be Balanced and Stable}, year = 2016 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Graceful Scaling on Uniform versus Steep-Tailed NoiseParallel Problem Solving From Nature (PPSN) 2016: 761–770
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Recently, different evolutionary algorithms (EAs) have been analyzed in noisy environments. The most frequently used noise model for this was additive posterior noise (noise added after the fitness evaluation) taken from a Gaussian distribution. In particular, for this setting it was shown that the \((\mu + 1)\)-EA on OneMax does not scale gracefully (higher noise cannot efficiently be compensated by higher \(\mu\)). In this paper we want to understand whether there is anything special about the Gaussian distribution which makes the \((\mu + 1)\)-EA not scale gracefully. We keep the setting of posterior noise, but we look at other distributions. We see that for exponential tails the \((\mu + 1)\)-EA on OneMax does also not scale gracefully, for similar reasons as in the case of Gaussian noise. On the other hand, for uniform distributions (as well as other, similar distributions) we see that the \((\mu + 1)\)-EA on OneMax does scale gracefully, indicating the importance of the noise model.
@inproceedings{DBLP:conf/ppsn/FriedrichKKS16, abstract = {Recently, different evolutionary algorithms (EAs) have been analyzed in noisy environments. The most frequently used noise model for this was additive posterior noise (noise added after the fitness evaluation) taken from a Gaussian distribution. In particular, for this setting it was shown that the \((\mu + 1)\)-EA on OneMax does not scale gracefully (higher noise cannot efficiently be compensated by higher \(\mu\)). In this paper we want to understand whether there is anything special about the Gaussian distribution which makes the \((\mu + 1)\)-EA not scale gracefully. We keep the setting of posterior noise, but we look at other distributions. We see that for exponential tails the \((\mu + 1)\)-EA on OneMax does also not scale gracefully, for similar reasons as in the case of Gaussian noise. On the other hand, for uniform distributions (as well as other, similar distributions) we see that the \((\mu + 1)\)-EA on OneMax does scale gracefully, indicating the importance of the noise model.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {martinskrejca timokoetzing year2016 tobiasfriedrich andrewmsutton PPSN}, pages = {761-770}, title = {Graceful Scaling on Uniform versus Steep-Tailed Noise}, year = 2016 }

Dang, Duc-Cuong; Lehre, Per Kristian; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M. Emergence of Diversity and its Benefits for Crossover in Genetic AlgorithmsParallel Problem Solving From Nature (PPSN) 2016: 890–900
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for a standard \((\mu+1)\) GA and the \(Jump_k\) test function. By studying the stochastic process underlying the size of the largest collection of identical genotypes we show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order \(\Omega(n/ \log n)\) compared to mutation-only algorithms like the \((1+1)\) EA.
@inproceedings{DBLP:conf/ppsn/DangFKKLOSS16, abstract = {Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for a standard \((\mu+1)\) GA and the \(Jump_k\) test function. By studying the stochastic process underlying the size of the largest collection of identical genotypes we show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order \(\Omega(n/ \log n)\) compared to mutation-only algorithms like the \((1+1)\) EA.}, author = {Dang, Duc-Cuong and Lehre, Per Kristian and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {martinskrejca timokoetzing tobiasfriedrich andrewmsutton PPSN}, pages = {890-900}, title = {Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms}, year = 2016 }

2015 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to NoiseGenetic and Evolutionary Computation Conference (GECCO) 2015: 17–24
Best-Paper Award (ACO/SI Track)
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical \((\mu+1)\)-EA outperforms any ACO algorithm, with smaller \(\mu\) being better; however, with large noise, the \((\mu+1)\)-EA fails, even for high values of \(\mu\) (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor \(\mu\) is small enough dependent on the parameter \(\delta^2\) of the noise and the dimension \(n\) of the search space \((p = o(1/(n(n + \delta \log n)^2 \log n)))\), optimization will be successful.
@inproceedings{DBLP:conf/gecco/FriedrichKKS15, abstract = {Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical \((\mu+1)\)-EA outperforms any ACO algorithm, with smaller \(\mu\) being better; however, with large noise, the \((\mu+1)\)-EA fails, even for high values of \(\mu\) (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor \(\mu\) is small enough dependent on the parameter \(\delta^2\) of the noise and the dimension \(n\) of the search space \((p = o(1/(n(n + \delta \log n)^2 \log n)))\), optimization will be successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {imported first martinskrejca timokoetzing bestpaper year2015 tobiasfriedrich gecco andrewmsutton}, note = {Best-Paper Award (ACO/SI Track)}, pages = {17-24}, title = {Robustness of Ant Colony Optimization to Noise}, year = 2015 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary SearchInternational Symposium of Algorithms and Computation (ISAAC) 2015: 140–150
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the \((\mu+1)\)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.
@inproceedings{DBLP:conf/isaac/FriedrichKKS15, abstract = {Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the \((\mu+1)\)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.}, address = {Berlin, Heidelberg}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {International Symposium of Algorithms and Computation (ISAAC)}, editor = {Elbassioni, Khaled and Makino, Kazuhisa}, keywords = {isaac martinskrejca timokoetzing year2015 tobiasfriedrich andrewmsutton}, pages = {140-150}, publisher = {Springer Berlin Heidelberg}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2015 }

2019 [ nach oben ]

Theoretical Analyses of Univariate Estimation-of-Distribution Algorithms. Technical Report (PhD dissertation), Krejca, Martin S. (2019).
ACM SIGEVO Dissertation Award, Honorable Mention
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Optimization is a core part of technological advancement and is usually heavily aided by computers. However, since many optimization problems are hard, it is unrealistic to expect an optimal solution within reasonable time. Hence, heuristics are employed, that is, computer programs that try to produce solutions of high quality quickly. One special class are estimation-of-distribution algorithms (EDAs), which are characterized by maintaining a probabilistic model over the problem domain, which they evolve over time. In an iterative fashion, an EDA uses its model in order to generate a set of solutions, which it then uses to refine the model such that the probability of producing good solutions is increased. In this thesis, we theoretically analyze the class of univariate EDAs over the Boolean domain, that is, over the space of all length-\(n\) bit strings. In this setting, the probabilistic model of a univariate EDA consists of an \(n\)-dimensional probability vector where each component denotes the probability to sample a \(1\) for that position in order to generate a bit string. My contribution follows two main directions: first, we analyze general inherent properties of univariate EDAs. Second, we determine the expected run times of specific EDAs on benchmark functions from theory. In the first part, we characterize when EDAs are unbiased with respect to the problem encoding. We then consider a setting where all solutions look equally good to an EDA, and we show that the probabilistic model of an EDA quickly evolves into an incorrect model if it is always updated such that it does not change in expectation. In the second part, we first show that the algorithms cGA and MMAS-fp are able to efficiently optimize a noisy version of the classical benchmark function OneMax. We perturb the function by adding Gaussian noise with a variance of \(\sigma^2\), and we prove that the algorithms are able to generate the true optimum in a time polynomial in \(\sigma^2\) and the problem size \(n\). For the MMAS-fp, we generalize this result to linear functions. Further, we prove a run time of \(\Omega\big(n \log(n)\big)\) for the algorithm UMDA on (unnoisy) OneMax. Last, we introduce a new algorithm that is able to optimize the benchmark functions OneMax and LeadingOnes both in \(O\big(n \log(n)\big)\), which is a novelty for heuristics in the domain we consider.
@phdthesis{krejca2019theoretical, abstract = {Optimization is a core part of technological advancement and is usually heavily aided by computers. However, since many optimization problems are hard, it is unrealistic to expect an optimal solution within reasonable time. Hence, heuristics are employed, that is, computer programs that try to produce solutions of high quality quickly. One special class are estimation-of-distribution algorithms (EDAs), which are characterized by maintaining a probabilistic model over the problem domain, which they evolve over time. In an iterative fashion, an EDA uses its model in order to generate a set of solutions, which it then uses to refine the model such that the probability of producing good solutions is increased. In this thesis, we theoretically analyze the class of univariate EDAs over the Boolean domain, that is, over the space of all length-\(n\) bit strings. In this setting, the probabilistic model of a univariate EDA consists of an \(n\)-dimensional probability vector where each component denotes the probability to sample a \(1\) for that position in order to generate a bit string. My contribution follows two main directions: first, we analyze general inherent properties of univariate EDAs. Second, we determine the expected run times of specific EDAs on benchmark functions from theory. In the first part, we characterize when EDAs are unbiased with respect to the problem encoding. We then consider a setting where all solutions look equally good to an EDA, and we show that the probabilistic model of an EDA quickly evolves into an incorrect model if it is always updated such that it does not change in expectation. In the second part, we first show that the algorithms cGA and MMAS-fp are able to efficiently optimize a noisy version of the classical benchmark function OneMax. We perturb the function by adding Gaussian noise with a variance of \(\sigma^2\), and we prove that the algorithms are able to generate the true optimum in a time polynomial in \(\sigma^2\) and the problem size \(n\). For the MMAS-fp, we generalize this result to linear functions. Further, we prove a run time of \(\Omega\big(n \log(n)\big)\) for the algorithm UMDA on (unnoisy) OneMax. Last, we introduce a new algorithm that is able to optimize the benchmark functions OneMax and LeadingOnes both in \(O\big(n \log(n)\big)\), which is a novelty for heuristics in the domain we consider.}, annote = {PhD thesis, Hasso Plattner Institute, University of Potsdam}, author = {Krejca, Martin S.}, keywords = {sys:relevantfor:ae martinskrejca phdthesis theses year2019}, note = {ACM SIGEVO Dissertation Award, Honorable Mention}, school = {Hasso Plattner Institute, University of Potsdam}, title = {Theoretical Analyses of Univariate Estimation-of-Distribution Algorithms}, year = 2019 }