2018 [ to top ]

• 
  Gao, Wanru; Friedrich, Tobias; Neumann, Frank; Hercher, Christian Randomized Greedy Algorithms for Covering Problems. Genetic and Evolutionary Computation Conference (GECCO) 2018: 309-315
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter \(\gamma\) which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems.
  @inproceedings{gao2018randomized, abstract = {Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter \(\gamma\) which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems.}, author = {Gao, Wanru and Friedrich, Tobias and Neumann, Frank and Hercher, Christian}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO christianhercher frankneumann tobiasfriedrich wanrugao year2018}, pages = {309-315}, title = {Randomized Greedy Algorithms for Covering Problems}, year = 2018 }
• 
  Friedrich, Tobias; Quinzan, Francesco; Wagner, Markus Escaping Large Deceptive Basins of Attraction with Heavy Mutation Operators. Genetic and Evolutionary Computation Conference (GECCO) 2018: 293-300
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In many Evolutionary Algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results into a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.
  @inproceedings{friedrich2018escaping, abstract = {In many Evolutionary Algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results into a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.}, author = {Friedrich, Tobias and Quinzan, Francesco and Wagner, Markus}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO francescoquinzan markuswagner tobiasfriedrich year2018}, pages = {293-300}, title = {Escaping Large Deceptive Basins of Attraction with Heavy Mutation Operators}, year = 2018 }
• 
  Doerr, Benjamin; Krejca, Martin S. Significance-based Estimation-of-Distribution Algorithms. Genetic 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 = {GECCO benjamindoerr martinskrejca year2018}, pages = {1483-1490}, title = {Significance-based Estimation-of-Distribution Algorithms}, year = 2018 }
• 
  Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew M. Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences. Genetic and Evolutionary Computation Conference (GECCO) 2018: 301-308
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In the context of black box optimization, the most common way to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple \((1+1)\) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the \((1+1)~EA_{\mathcal{U}}\), a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the \((1+1)~EA\) exhibits exponential run time. We prove that the \((1+1)~EA_{\mathcal{U}}\) has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the \((1+1)~EA\) yields exponential run time on those instances, and the \((1+1)~EA_{\mathcal{U}}\) finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the \((1+1)~EA\) does not find a \((4/3-\epsilon)\)-approximation in polynomial time, and we show that the \((1+1)~EA_{\mathcal{U}}\) reaches a \((4/3-\epsilon)\)-approximation in polynomial time. We then prove that the \((1+1)~EA_{\mathcal{U}}\) serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a \((1+\epsilon)\)-approximation with \(\epsilon > 4/n\).
  @inproceedings{friedrich2018improving, abstract = {In the context of black box optimization, the most common way to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple \((1+1)\) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the \((1+1)~EA_{\mathcal{U}}\), a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the \((1+1)~EA\) exhibits exponential run time. We prove that the \((1+1)~EA_{\mathcal{U}}\) has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the \((1+1)~EA\) yields exponential run time on those instances, and the \((1+1)~EA_{\mathcal{U}}\) finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the \((1+1)~EA\) does not find a \((4/3-\epsilon)\)-approximation in polynomial time, and we show that the \((1+1)~EA_{\mathcal{U}}\) reaches a \((4/3-\epsilon)\)-approximation in polynomial time. We then prove that the \((1+1)~EA_{\mathcal{U}}\) serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a \((1+\epsilon)\)-approximation with \(\epsilon > 4/n\).}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO andrewmsutton francescoquinzan timokoetzing tobiasfriedrich year2018}, pages = {301-308}, title = {Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences}, year = 2018 }

2017 [ to top ]

• 
  Friedrich, Tobias; Kötzing, Timo; Melnichenko, Anna Analyzing Search Heuristics with Differential Equations. Genetic and Evolutionary Computation Conference (GECCO) 2017: 313-314
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).
  @inproceedings{friedrich2017analyzing, abstract = {Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).}, author = {Friedrich, Tobias and Kötzing, Timo and Melnichenko, Anna}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {annamelnichenko gecco timokoetzing tobiasfriedrich year2017}, pages = {313-314}, title = {Analyzing Search Heuristics with Differential Equations}, year = 2017 }
• 
  Chauhan, Ankit; Friedrich, Tobias; Quinzan, Francesco Approximating Optimization Problems using EAs on Scale-Free Networks. Genetic and Evolutionary Computation Conference (GECCO) 2017: 235-242
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  It has been experimentally observed that real-world networks follow certain topologicalproperties, such as small-world, power-law etc. To study these networks, many random graph models, such as Preferential Attachment, have been proposed. In this paper, we consider the deterministic properties which capture power-law degree distribution and degeneracy. Networks with these properties are known as scale-free networks in the literature. Many interesting problems remain NP-hard on scale-free networks. We study the relationship between scale-free properties and the approximation-ratio of some commonly used evolutionary algorithms. For the Vertex Cover, we observe experimentally that the \((1+1)\) EA always gives the better result than a greedy local search, even when it runs for only \(O(n, \log(n))\) steps. We give the construction of a scale-free network in which a multi-objective algorithm and a greedy algorithm obtain optimal solutions, while the \((1+1)\) EA obtains the worst possible solution with constant probability. We prove that for the Dominating Set, Vertex Cover, Connected Dominating Set and Independent Set, the \((1+1)\) EA obtains constant-factor approximation in expected run time \(O(n, \log(n))\) and \(O(n^4)\) respectively. Whereas, GSEMO gives even better approximation than \((1+1)\) EA in expected run time \(O(n^3)\) for Dominating Set, Vertex Cover and Connected Dominating Set on such networks.
  @inproceedings{chauhan2017approximating, abstract = {It has been experimentally observed that real-world networks follow certain topologicalproperties, such as small-world, power-law etc. To study these networks, many random graph models, such as Preferential Attachment, have been proposed. In this paper, we consider the deterministic properties which capture power-law degree distribution and degeneracy. Networks with these properties are known as scale-free networks in the literature. Many interesting problems remain NP-hard on scale-free networks. We study the relationship between scale-free properties and the approximation-ratio of some commonly used evolutionary algorithms. For the Vertex Cover, we observe experimentally that the \((1+1)\) EA always gives the better result than a greedy local search, even when it runs for only \(O(n\, \log(n))\) steps. We give the construction of a scale-free network in which a multi-objective algorithm and a greedy algorithm obtain optimal solutions, while the \((1+1)\) EA obtains the worst possible solution with constant probability. We prove that for the Dominating Set, Vertex Cover, Connected Dominating Set and Independent Set, the \((1+1)\) EA obtains constant-factor approximation in expected run time \(O(n\, \log(n))\) and \(O(n^4)\) respectively. Whereas, GSEMO gives even better approximation than \((1+1)\) EA in expected run time \(O(n^3)\) for Dominating Set, Vertex Cover and Connected Dominating Set on such networks.}, author = {Chauhan, Ankit and Friedrich, Tobias and Quinzan, Francesco}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {ankitchauhan francescoquinzan gecco tobiasfriedrich year2017}, pages = {235-242}, title = {Approximating Optimization Problems using EAs on Scale-Free Networks}, year = 2017 }
• 
  Doerr, Benjamin; Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes Bounding Bloat in Genetic Programming. Genetic and Evolutionary Computation Conference (GECCO) 2017: 921-928
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat. In this paper we analyze bloat in mutation-based genetic programming for the two test functions ORDER and MAJORITY. We overcome previous assumptions on the magnitude of bloat and give matching or close-to-matching upper and lower bounds for the expected optimization time. In particular, we show that the \((1+1)\) GP takes (i) \(\Theta(T_\text{init + n\, \log n)\) iterations with bloat control on ORDER as well as MAJORITY; and (ii) \(O(T_{\text{init ,log \,T_{\text{init + n(\log n)^3)\) and \(\Omega(T_\text{init + n \,\log n)\) (and \(\Omega(T_\text{init \,\log \,T_{\text{init}})\) for \(n = 1\)) iterations without bloat control on MAJORITY.
  @inproceedings{doerr2017bounding, abstract = {While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat. In this paper we analyze bloat in mutation-based genetic programming for the two test functions ORDER and MAJORITY. We overcome previous assumptions on the magnitude of bloat and give matching or close-to-matching upper and lower bounds for the expected optimization time. In particular, we show that the \((1+1)\) GP takes (i) \(\Theta(T_{\text{init}} + n\, \log n)\) iterations with bloat control on ORDER as well as MAJORITY; and (ii) \(O(T_{\text{init}} \,\log \,T_{\text{init}} + n(\log n)^3)\) and \(\Omega(T_{\text{init}} + n \,\log n)\) (and \(\Omega(T_{\text{init}} \,\log \,T_{\text{init}})\) for \(n = 1\)) iterations without bloat control on MAJORITY.}, author = {Doerr, Benjamin and Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr gecco gregorlagodzinski johanneslengler timokoetzing year2017}, pages = {921-928}, title = {Bounding Bloat in Genetic Programming}, year = 2017 }
• 
  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2017: 1407-1414
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Thee investigations of linear pseudo-Boolean functions play a central role in the area of runtime analysis of evolutionary computing techniques. Having an additional linear constraint on a linear function is equivalent to the NP-hard knapsack problem and special problem classes thereof have been investigated in recent works. In this paper, we extend these studies to problems with dynamic constraints and investigate the runtime of different evolutionary algorithms to recompute an optimal solution when the constraint bound changes by a certain amount. We study the classical \((1+1)\) EA and population-based algorithms and show that they recompute an optimal solution very efficiently. Furthermore, we show that a variant of the \((1+(\lambda, \lambda))\) GA can recompute the optimal solution more efficiently in some cases.
  @inproceedings{shi2017reoptimization, abstract = {Thee investigations of linear pseudo-Boolean functions play a central role in the area of runtime analysis of evolutionary computing techniques. Having an additional linear constraint on a linear function is equivalent to the NP-hard knapsack problem and special problem classes thereof have been investigated in recent works. In this paper, we extend these studies to problems with dynamic constraints and investigate the runtime of different evolutionary algorithms to recompute an optimal solution when the constraint bound changes by a certain amount. We study the classical \((1+1)\) EA and population-based algorithms and show that they recompute an optimal solution very efficiently. Furthermore, we show that a variant of the \((1+(\lambda, \lambda))\) GA can recompute the optimal solution more efficiently in some cases.}, author = {Shi, Feng and Schirneck, Martin and Friedrich, Tobias and Kötzing, Timo and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {fengshi frankneumann gecco martinschirneck timokoetzing tobiasfriedrich year2017}, pages = {1407-1414}, title = {Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints}, year = 2017 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unknown Solution Length Problems With No Asymptotically Optimal Run Time. Genetic and Evolutionary Computation Conference (GECCO) 2017: 1367-1374
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length \(N\), but only \(n << N\) of them have an influence on the fitness. Neither the position of these relevant bits nor their number is known. In previous work, variants of the \((1 + 1)\) evolutionary algorithm (EA) have been developed that solve, for arbitrary \(s \in N\), such OneMax and LeadingOnes instances, simultaneously for all \(n \in N\), in expected time \(O(n(\log(n))^2 log \log(n) dots \log^{s-1 (n)(\log^{(s) (n))^1+\epsilon} )\)and \(O(n^2 \log(n) log \log(n) dots \log^{s-1 (n)(\log^{(s) (n))^1+\epsilon} )\), respectively; that is, in almost the same time as if n and the relevant bit positions were known. In this work, we prove the first, almost matching, lower bounds for this setting. For LeadingOnes, we show that, for every \(s \in N\), the \((1 + 1)\) EA with any mutation operator treating zeros and ones equally has an expected run time of \(\omega(n^2 \log(n) log \log(n) dots \log^{(s) (n))\) when facing problem size \(n\). Aiming at closing the small remaining gap, we realize that, quite surprisingly, there is no asymptotically best performance. For any algorithm solving, for all \(n\), all instances of size \(n\) in expected time at most \(T (n)\), there is an algorithm doing the same in time \(T'(n)\) with \(T' = o(T )\). For OneMax we show results of similar flavor.
  @inproceedings{doerr2017unknown, abstract = {We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length \(N\), but only \(n << N\) of them have an influence on the fitness. Neither the position of these relevant bits nor their number is known. In previous work, variants of the \((1 + 1)\) evolutionary algorithm (EA) have been developed that solve, for arbitrary \(s \in N\), such OneMax and LeadingOnes instances, simultaneously for all \(n \in N\), in expected time \(O(n(\log(n))^2 \log \log(n) \dots \log^{s-1} (n)(\log^{(s)} (n))^{1+\epsilon} )\)and \(O(n^2 \log(n) \log \log(n) \dots \log^{s-1} (n)(\log^{(s)} (n))^{1+\epsilon} )\), respectively; that is, in almost the same time as if n and the relevant bit positions were known. In this work, we prove the first, almost matching, lower bounds for this setting. For LeadingOnes, we show that, for every \(s \in N\), the \((1 + 1)\) EA with any mutation operator treating zeros and ones equally has an expected run time of \(\omega(n^2 \log(n) \log \log(n) \dots \log^{(s)} (n))\) when facing problem size \(n\). Aiming at closing the small remaining gap, we realize that, quite surprisingly, there is no asymptotically best performance. For any algorithm solving, for all \(n\), all instances of size \(n\) in expected time at most \(T (n)\), there is an algorithm doing the same in time \(T'(n)\) with \(T' = o(T )\). For OneMax we show results of similar flavor.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr caroladoerr gecco timokoetzing year2017}, pages = {1367-1374}, title = {Unknown Solution Length Problems With No Asymptotically Optimal Run Time}, year = 2017 }
• 
  Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, Martin Island Models Meet Rumor Spreading. Genetic and Evolutionary Computation Conference (GECCO) 2017: 1359-1366
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort. We improve the existing upper bounds for the communication effort (i) by improving the run time bounds via a careful analysis, (ii) by setting the balance between individual computation and communication in a more appropriate manner, and (iii) by replacing the usual communicate-with-all-neighbors approach with randomized rumor spreading, where each island contacts a randomly chosen neighbor. This epidemic communication paradigm is known to lead to very fast and robust information dissemination in many applications. Our results concern islands running simple (1+1) evolutionary algorithms, we regard d-dimensional tori and complete graphs as communication topologies, and optimize the classic test functions OneMax and LeadingOnes.
  @inproceedings{doerr2017island, abstract = {Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort. We improve the existing upper bounds for the communication effort (i) by improving the run time bounds via a careful analysis, (ii) by setting the balance between individual computation and communication in a more appropriate manner, and (iii) by replacing the usual communicate-with-all-neighbors approach with randomized rumor spreading, where each island contacts a randomly chosen neighbor. This epidemic communication paradigm is known to lead to very fast and robust information dissemination in many applications. Our results concern islands running simple (1+1) evolutionary algorithms, we regard d-dimensional tori and complete graphs as communication topologies, and optimize the classic test functions OneMax and LeadingOnes.}, author = {Doerr, Benjamin and Fischbeck, Philipp and Frahnow, Clemens and Friedrich, Tobias and Kötzing, Timo and Schirneck, Martin}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr clemensfrahnow gecco martinschirneck philippfischbeck timokoetzing tobiasfriedrich year2017}, pages = {1359-1366}, title = {Island Models Meet Rumor Spreading}, year = 2017 }

2016 [ to top ]

• 
  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 Crossover. Genetic 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 = {andrewmsutton gecco martinskrejca timokoetzing tobiasfriedrich year2016}, pages = {645-652}, publisher = {ACM Press}, title = {Escaping Local Optima with Diversity Mechanisms and Crossover}, year = 2016 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo The Right Mutation Strength for Multi-Valued Decision Variables. Genetic and Evolutionary Computation Conference (GECCO) 2016: 1115-1122
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The most common representation in evolutionary computation are bit strings. This is ideal to model binary decision variables, but less useful for variables taking more values. With very little theoretical work existing on how to use evolutionary algorithms for such optimization problems, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over \(\Omega=\{0,1,\dots,r-1\}n\). More precisely, we regard a variety of problem classes requesting the component-wise minimization of the distance to an unknown target vector \(z \in \Omega\). For such problems we see a crucial difference in how we extend the standard-bit mutation operator to these multi-valued domains. While it is natural to select each position of the solution vector to be changed independently with probability \(1/n\), there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of \(\Theta(nr\log n)\). If we change each selected position by either +1 or -1 (random choice), the optimization time reduces to \(\Theta(nr+n\log n)\). If we use a random mutation strength \(i \in \{0,1,\dots,r-1\}n\) with probability inversely proportional to \(i\) and change the selected position by either +\(i\) or -\(i\) (random choice), then the optimization time becomes \(\Theta(n\log(r)(\log(n)+\log(r)))\), bringing down the dependence on \(r\) from linear to polylogarithmic. One of our results depends on a new variant of the lower bounding multiplicative drift theorem.
  @inproceedings{DBLP:conf/gecco/DoerrDK16, abstract = {The most common representation in evolutionary computation are bit strings. This is ideal to model binary decision variables, but less useful for variables taking more values. With very little theoretical work existing on how to use evolutionary algorithms for such optimization problems, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over \(\Omega=\{0,1,\dots,r-1\}n\). More precisely, we regard a variety of problem classes requesting the component-wise minimization of the distance to an unknown target vector \(z \in \Omega\). For such problems we see a crucial difference in how we extend the standard-bit mutation operator to these multi-valued domains. While it is natural to select each position of the solution vector to be changed independently with probability \(1/n\), there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of \(\Theta(nr\log n)\). If we change each selected position by either +1 or -1 (random choice), the optimization time reduces to \(\Theta(nr+n\log n)\). If we use a random mutation strength \(i \in \{0,1,\dots,r-1\}n\) with probability inversely proportional to \(i\) and change the selected position by either +\(i\) or -\(i\) (random choice), then the optimization time becomes \(\Theta(n\log(r)(\log(n)+\log(r)))\), bringing down the dependence on \(r\) from linear to polylogarithmic. One of our results depends on a new variant of the lower bounding multiplicative drift theorem.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO benjamindoerr caroladoerr timokoetzing year2016}, pages = {1115-1122}, title = {The Right Mutation Strength for Multi-Valued Decision Variables}, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. EDAs cannot be Balanced and Stable. Genetic 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 = {GECCO martinskrejca timokoetzing tobiasfriedrich year2016}, pages = {1139-1146}, publisher = {ACM Press}, title = {EDAs cannot be Balanced and Stable}, type = {Publication}, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, Martin Fast Building Block Assembly by Majority Vote Crossover. Genetic 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 = {GECCO frankneumann martinschirneck martinskrejca samadhinallaperuma timokoetzing tobiasfriedrich year2016}, pages = {661-668}, publisher = {ACM Press}, title = {Fast Building Block Assembly by Majority Vote Crossover}, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew M. Ant Colony Optimization Beats Resampling on Noisy Functions. Genetic and Evolutionary Computation Conference (GECCO) 2016: 3-4
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Despite the pervasiveness of noise in real-world optimization, there is little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques such as statistical resampling. Ant Colony Optimization (ACO) algorithms are claimed to be particularly well-suited to dynamic and noisy problems, even without explicit noise-handling techniques. In this work, we empirically investigate the trade-offs between resampling an the noise-handling abilities of ACO algorithms. Our main focus is to locate the point where resampling costs more than it is worth.
  @inproceedings{DBLP:conf/gecco/FriedrichKQS16, abstract = {Despite the pervasiveness of noise in real-world optimization, there is little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques such as statistical resampling. Ant Colony Optimization (ACO) algorithms are claimed to be particularly well-suited to dynamic and noisy problems, even without explicit noise-handling techniques. In this work, we empirically investigate the trade-offs between resampling an the noise-handling abilities of ACO algorithms. Our main focus is to locate the point where resampling costs more than it is worth.}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO andrewmsutton francescoquinzan timokoetzing tobiasfriedrich year2016}, pages = {3-4}, title = {Ant Colony Optimization Beats Resampling on Noisy Functions}, year = 2016 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary Search. Genetic 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 = {andrewmsutton gecco martinskrejca timokoetzing tobiasfriedrich year2016}, pages = {161-162}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2016 }

2015 [ to top ]

• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Solving Problems with Unknown Solution Length at (Almost) No Extra Cost. Genetic and Evolutionary Computation Conference (GECCO) 2015: 831-838
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if no a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the OneMax and LeadingOnes test functions, thus solving an open problem from Cathabard et al.
  @inproceedings{DBLP:conf/gecco/DoerrDK15, abstract = {Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if no a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the OneMax and LeadingOnes test functions, thus solving an open problem from Cathabard et al.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr caroladoerr gecco imported timokoetzing year2015}, pages = {831-838}, publisher = {{ACM}}, title = {Solving Problems with Unknown Solution Length at (Almost) No Extra Cost}, year = 2015 }
• 
  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to Noise. Genetic 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 = {andrewmsutton bestpaper first gecco imported martinskrejca timokoetzing tobiasfriedrich year2015}, note = {Best Paper Award (ACO/SI Track)}, pages = {17-24}, publisher = {{ACM}}, title = {Robustness of Ant Colony Optimization to Noise}, year = 2015 }
• 
  Doerr, Benjamin; Neumann, Frank; Sutton, Andrew M. Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation. Genetic and Evolutionary Computation Conference (GECCO) 2015: 1415-1422
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time \(O(n \log n)\) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
  @inproceedings{DBLP:conf/gecco/DoerrNS15, abstract = {With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time \(O(n \log n)\) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.}, author = {Doerr, Benjamin and Neumann, Frank and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton benjamindoerr bestpaper frankneumann gecco imported second year2015}, pages = {1415-1422}, publisher = {{ACM}}, title = {Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation}, year = 2015 }

2014 [ to top ]

• 
  Gießen, Christian; Kötzing, Timo Robustness of populations in stochastic environments. Genetic and Evolutionary Computation Conference (GECCO) 2014: 1383-1390
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We consider stochastic versions of OneMax and LeadingOnes and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the (1+1) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size \(\Theta(\log n)\)) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the (1+1) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings.
  @inproceedings{DBLP:conf/gecco/GiessenK14, abstract = {We consider stochastic versions of OneMax and LeadingOnes and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the (1+1) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size \(\Theta(\log n)\)) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the (1+1) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings.}, author = {Gießen, Christian and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported timokoetzing year2014}, pages = {1383-1390}, publisher = {{ACM}}, title = {Robustness of populations in stochastic environments}, year = 2014 }
• 
  Kötzing, Timo Concentration of first hitting times under additive drift. Genetic and Evolutionary Computation Conference (GECCO) 2014: 1391-1398
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Recent advances in drift analysis have given us better and better tools for understanding random processes, including the run time of randomized search heuristics. In the setting of multiplicative drift we do not only have excellent bounds on the expected run time, but also more general results showing the concentration of the run time. In this paper we investigate the setting of additive drift under the assumption of strong concentration of the "step size" of the process. Under sufficiently strong drift towards the goal we show a strong concentration of the hitting time. In contrast to this, we show that in the presence of small drift a Gambler's-Ruin-like behavior of the process overrides the influence of the drift. Finally, in the presence of sufficiently strong negative drift the hitting time is superpolynomial with high probability; this corresponds to the so-called negative drift theorem, for which we give new variants.
  @inproceedings{DBLP:conf/gecco/Kotzing14, abstract = {Recent advances in drift analysis have given us better and better tools for understanding random processes, including the run time of randomized search heuristics. In the setting of multiplicative drift we do not only have excellent bounds on the expected run time, but also more general results showing the concentration of the run time. In this paper we investigate the setting of additive drift under the assumption of strong concentration of the "step size" of the process. Under sufficiently strong drift towards the goal we show a strong concentration of the hitting time. In contrast to this, we show that in the presence of small drift a Gambler's-Ruin-like behavior of the process overrides the influence of the drift. Finally, in the presence of sufficiently strong negative drift the hitting time is superpolynomial with high probability; this corresponds to the so-called negative drift theorem, for which we give new variants.}, author = {Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported timokoetzing year2014}, pages = {1391-1398}, publisher = {{ACM}}, title = {Concentration of first hitting times under additive drift}, year = 2014 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unbiased black-box complexities of jump functions: how to cross large plateaus. Genetic and Evolutionary Computation Conference (GECCO) 2014: 769-776
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We analyze the unbiased black-box complexity of jump functions with large jump sizes. Among other results, we show that when the jump size is \((1/2 - \epsilon)n\), that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values \(n/2\) and \(n\) are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a \(\Theta(n^{-1/2})\) fraction) is a plateau of constant fitness.To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.
  @inproceedings{DBLP:conf/gecco/DoerrDK14, abstract = {We analyze the unbiased black-box complexity of jump functions with large jump sizes. Among other results, we show that when the jump size is \((1/2 - \epsilon)n\), that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values \(n/2\) and \(n\) are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a \(\Theta(n^{-1/2})\) fraction) is a plateau of constant fitness.To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr caroladoerr gecco imported timokoetzing year2014}, pages = {769-776}, publisher = {{ACM}}, title = {Unbiased black-box complexities of jump functions: how to cross large plateaus}, year = 2014 }
• 
  Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Two-dimensional subset selection for hypervolume and epsilon-indicator. Genetic and Evolutionary Computation Conference (GECCO) 2014: 589-596
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The goal of bi-objective optimization is to find a small set of good compromise solutions. A common problem for bi-objective evolutionary algorithms is the following subset selection problem (SSP): Given \(n\) solutions \(P \subset \mathbb{R}^2\) in the objective space, select \(k\) solutions \(P^*\) from \(P\) that optimize an indicator function. In the hypervolume SSP we want to select \(k\) points \(P^*\) that maximize the hypervolume indicator \(I_{HYP}(P^*, r)\) for some reference point \(r \in R^2\). Similarly, the \(\epsilon\)-indicator SSP aims at selecting \(\tilde k\) points \(P^*\) that minimize the \(\epsilon\)-indicator \(I_{\epsilon}(P^*,\mathbb{R})\) for some reference set \(R \subset R^2\) of size \(m\) (which can be \(\mathbb{R}=P\)). We first present a new algorithm for the hypervolume SSP with runtime \(O(n (k + \log n))\). Our second main result is a new algorithm for the \(\epsilon\)-indicator SSP with runtime \(O(n \log n + m \log m)\). Both results improve the current state of the art runtimes by a factor of (nearly) \(n\) and make the problems tractable for new applications. Preliminary experiments confirm that the theoretical results translate into substantial empirical runtime improvements.
  @inproceedings{DBLP:conf/gecco/BringmannFK14, abstract = {The goal of bi-objective optimization is to find a small set of good compromise solutions. A common problem for bi-objective evolutionary algorithms is the following subset selection problem (SSP): Given \(n\) solutions \(P \subset \mathbb{R}^2\) in the objective space, select \(k\) solutions \(P^*\) from \(P\) that optimize an indicator function. In the hypervolume SSP we want to select \(k\) points \(P^*\) that maximize the hypervolume indicator \(I_{HYP}(P^*, r)\) for some reference point \(r \in R^2\). Similarly, the \(\epsilon\)-indicator SSP aims at selecting \(\tilde k\) points \(P^*\) that minimize the \(\epsilon\)-indicator \(I_{\epsilon}(P^*,\mathbb{R})\) for some reference set \(R \subset R^2\) of size \(m\) (which can be \(\mathbb{R}=P\)). We first present a new algorithm for the hypervolume SSP with runtime \(O(n (k + \log n))\). Our second main result is a new algorithm for the \(\epsilon\)-indicator SSP with runtime \(O(n \log n + m \log m)\). Both results improve the current state of the art runtimes by a factor of (nearly) \(n\) and make the problems tractable for new applications. Preliminary experiments confirm that the theoretical results translate into substantial empirical runtime improvements.}, author = {Bringmann, Karl and Friedrich, Tobias and Klitzke, Patrick}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2014}, pages = {589-596}, publisher = {{ACM}}, title = {Two-dimensional subset selection for hypervolume and epsilon-indicator}, year = 2014 }
• 
  Chicano, Francisco; Whitley, Darrell; Sutton, Andrew M. Efficient identification of improving moves in a ball for pseudo-boolean problems. Genetic and Evolutionary Computation Conference (GECCO) 2014: 437-444
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length \(n\), we define the \(r\)-ball neighborhood as the set of solutions at Hamming distance \(r\) or less from the current solution. For \(r \ll n\) this neighborhood contains \(\Theta(n^r)\) solutions. In this paper efficient methods areintroduced to locate improving moves in the \(r\)-ball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NK-landscapes and MAX-\(k\)-SAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in \(n\). We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKq-landscapes instances.
  @inproceedings{DBLP:conf/gecco/ChicanoWS14, abstract = {Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length \(n\), we define the \(r\)-ball neighborhood as the set of solutions at Hamming distance \(r\) or less from the current solution. For \(r \ll n\) this neighborhood contains \(\Theta(n^r)\) solutions. In this paper efficient methods areintroduced to locate improving moves in the \(r\)-ball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NK-landscapes and MAX-\(k\)-SAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in \(n\). We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKq-landscapes instances.}, author = {Chicano, Francisco and Whitley, Darrell and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2014}, pages = {437-444}, publisher = {{ACM}}, title = {Efficient identification of improving moves in a ball for pseudo-boolean problems}, year = 2014 }

2013 [ to top ]

• 
  Benz, Florian; Kötzing, Timo An effective heuristic for the smallest grammar problem. Genetic and Evolutionary Computation Conference (GECCO) 2013: 487-494
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The smallest grammar problem is the problem of finding the smallest context-free grammar that generates exactly one given sequence. Approximating the problem with a ratio of less than 8569/8568 is known to be NP-hard. Most work on this problem has focused on finding decent solutions fast (mostly in linear time), rather than on good heuristic algorithms. Inspired by a new perspective on the problem presented by Carrascosa et al. (2010), we investigate the performance of different heuristics on the problem. The aim is to find a good solution on large instances by allowing more than linear time. We propose a hybrid of a max-min ant system and a genetic algorithm that in combination with a novel local search outperforms the state of the art on all files of the Canterbury corpus, a standard benchmark suite. Furthermore, this hybrid performs well on a standard DNA corpus.
  @inproceedings{DBLP:conf/gecco/BenzK13, abstract = {The smallest grammar problem is the problem of finding the smallest context-free grammar that generates exactly one given sequence. Approximating the problem with a ratio of less than 8569/8568 is known to be NP-hard. Most work on this problem has focused on finding decent solutions fast (mostly in linear time), rather than on good heuristic algorithms. Inspired by a new perspective on the problem presented by Carrascosa et al.\ (2010), we investigate the performance of different heuristics on the problem. The aim is to find a good solution on large instances by allowing more than linear time. We propose a hybrid of a max-min ant system and a genetic algorithm that in combination with a novel local search outperforms the state of the art on all files of the Canterbury corpus, a standard benchmark suite. Furthermore, this hybrid performs well on a standard DNA corpus.}, author = {Benz, Florian and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported timokoetzing year2013}, pages = {487-494}, publisher = {{ACM}}, title = {An effective heuristic for the smallest grammar problem}, year = 2013 }
• 
  Bringmann, Karl; Friedrich, Tobias Parameterized average-case complexity of the hypervolume indicator. Genetic and Evolutionary Computation Conference (GECCO) 2013: 575-582

  Nominated for Best Paper Award (EMO Track)
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The hypervolume indicator (HYP) is a popular measure for the quality of a set of \(n\) solutions in \(\mathbb{R}^d\). We discuss its asymptotic worst-case runtimes and several lower bounds depending on different complexity-theoretic assumptions. Assuming that P \(\neq\) NP, there is no algorithm with runtime \(poly(n,d)\). Assuming the exponential time hypothesis, there is no algorithm with runtime \(n^{o(d)}\). In contrast to these worst-case lower bounds, we study the average-case complexity of HYP for points distributed i.i.d. at random on a \(d\)-dimensional simplex. We present a general framework which translates any algorithm for HYP with worst-case runtime \(n^{f(d)}\) to an algorithm with worst-case runtime \(n^{f(d) +1}\) and fixed-parameter-tractable (FPT) average-case runtime. This can be used to show that HYP can be solved in expected time \(O(d^{d^2/2 n + d n^2)\), which implies that HYP is FPT on average while it is W1-hard in the worst-case. For constant dimension \(d\) this gives an algorithm for HYP with runtime \(O(n^2)\) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worst-case runtime predicts.
  @inproceedings{DBLP:conf/gecco/BringmannF13, abstract = {The hypervolume indicator (HYP) is a popular measure for the quality of a set of \(n\) solutions in \(\mathbb{R}^d\). We discuss its asymptotic worst-case runtimes and several lower bounds depending on different complexity-theoretic assumptions. Assuming that P \(\neq\) NP, there is no algorithm with runtime \(poly(n,d)\). Assuming the exponential time hypothesis, there is no algorithm with runtime \(n^{o(d)}\). In contrast to these worst-case lower bounds, we study the average-case complexity of HYP for points distributed i.i.d. at random on a \(d\)-dimensional simplex. We present a general framework which translates any algorithm for HYP with worst-case runtime \(n^{f(d)}\) to an algorithm with worst-case runtime \(n^{f(d) +1}\) and fixed-parameter-tractable (FPT) average-case runtime. This can be used to show that HYP can be solved in expected time \(O(d^{d^2/2} n + d n^2)\), which implies that HYP is FPT on average while it is W1-hard in the worst-case. For constant dimension \(d\) this gives an algorithm for HYP with runtime \(O(n^2)\) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worst-case runtime predicts.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2013}, note = {Nominated for Best Paper Award (EMO Track)}, pages = {575-582}, publisher = {{ACM}}, title = {Parameterized average-case complexity of the hypervolume indicator}, year = 2013 }

2012 [ to top ]

• 
  Sutton, Andrew M.; Day, Jareth; Neumann, Frank A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT. Genetic and Evolutionary Computation Conference (GECCO) 2012: 433-440
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We investigate the MAX-2-SAT problem and study evolutionary algorithms by parameterized runtime analysis. The parameterized runtime analysis of evolutionary algorithms has been initiated recently and reveals new insights into which type of instances of NP-hard combinatorial optimization problems are hard to solve by evolutionary computing methods. We show that a variant of the (1+1) EA is a fixed-parameter evolutionary algorithm with respect to the standard parameterization for MAX-2-SAT. Furthermore, we study how the dependencies between the variables affect problem difficulty and present fixed-parameter evolutionary algorithms for the MAX-(2,3)-SAT problem where the studied parameter is the diameter of the variable graph.
  @inproceedings{DBLP:conf/gecco/SuttonDN12, abstract = {We investigate the MAX-2-SAT problem and study evolutionary algorithms by parameterized runtime analysis. The parameterized runtime analysis of evolutionary algorithms has been initiated recently and reveals new insights into which type of instances of NP-hard combinatorial optimization problems are hard to solve by evolutionary computing methods. We show that a variant of the (1+1) EA is a fixed-parameter evolutionary algorithm with respect to the standard parameterization for MAX-2-SAT. Furthermore, we study how the dependencies between the variables affect problem difficulty and present fixed-parameter evolutionary algorithms for the MAX-(2,3)-SAT problem where the studied parameter is the diameter of the variable graph.}, author = {Sutton, Andrew M. and Day, Jareth and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton frankneumann gecco imported jarethday year2012}, pages = {433-440}, publisher = {{ACM}}, title = {A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT}, year = 2012 }
• 
  Kötzing, Timo; Sutton, Andrew M.; Neumann, Frank; O'Reilly, Una-May The max problem revisited: the importance of mutation in genetic programming. Genetic and Evolutionary Computation Conference (GECCO) 2012: 1333-1340
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the well-studied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutation-based genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutation-based genetic programming algorithms.
  @inproceedings{DBLP:conf/gecco/KotzingSNO12, abstract = {This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the well-studied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutation-based genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutation-based genetic programming algorithms.}, author = {Kötzing, Timo and Sutton, Andrew M. and Neumann, Frank and O'Reilly, Una-May}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton frankneumann gecco imported timokoetzing unamayoreilly year2012}, pages = {1333-1340}, publisher = {{ACM}}, title = {The max problem revisited: the importance of mutation in genetic programming}, year = 2012 }
• 
  Doerr, Benjamin; Hota, Ashish; Kötzing, Timo Ants easily solve stochastic shortest path problems. Genetic and Evolutionary Computation Conference (GECCO) 2012: 17-24
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The first rigorous theoretical analysis (Horoba, Sudholt (GECCO 2010)) of an ant colony optimizer for the stochastic shortest path problem suggests that ant system experience significant difficulties when the input data is prone to noise. In this work, we propose a slightly different ant optimizer to deal with noise. We prove that under mild conditions, it finds the paths with shortest expected length efficiently, despite the fact that we do not have convergence in the classic sense. To prove our results, we introduce a stronger drift theorem that can also deal with the situation that the progress is faster when one is closer to the goal.
  @inproceedings{DBLP:conf/gecco/DoerrHK12, abstract = {The first rigorous theoretical analysis (Horoba, Sudholt (GECCO 2010)) of an ant colony optimizer for the stochastic shortest path problem suggests that ant system experience significant difficulties when the input data is prone to noise. In this work, we propose a slightly different ant optimizer to deal with noise. We prove that under mild conditions, it finds the paths with shortest expected length efficiently, despite the fact that we do not have convergence in the classic sense. To prove our results, we introduce a stronger drift theorem that can also deal with the situation that the progress is faster when one is closer to the goal.}, author = {Doerr, Benjamin and Hota, Ashish and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported timokoetzing year2012}, pages = {17-24}, publisher = {{ACM}}, title = {Ants easily solve stochastic shortest path problems}, year = 2012 }
• 
  Bringmann, Karl; Friedrich, Tobias Convergence of hypervolume-based archiving algorithms ii: competitiveness. Genetic and Evolutionary Computation Conference (GECCO) 2012: 457-464
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We study the convergence behavior of \((\mu+\lambda)\)-archiving algorithms. A \((\mu+\lambda)\)-archiving algorithm defines how to choose in each generation \(\mu\) children from \(\mu\) parents and \(\lambda\) offspring together. Archiving algorithms have to choose individuals online without knowing future offspring. Previous studies assumed the offspring generation to be best-case. We assume the initial population and the offspring generation to be worst-case and use the competitive ratio to measure how much smaller hypervolumes an archiving algorithm finds due to not knowing the future in advance. We prove that all archiving algorithms which increase the hypervolume in each step (if they can) are only \(\mu\)-competitive. We also present a new archiving algorithm which is \((4+2/\mu)\)-competitive. This algorithm not only achieves a constant competitive ratio, but is also efficiently computable. Both properties provably do not hold for the commonly used greedy archiving algorithms, for example those used in SIBEA, SMS-EMOA, or the generational MO-CMA-ES.
  @inproceedings{DBLP:conf/gecco/BringmannF12, abstract = {We study the convergence behavior of \((\mu+\lambda)\)-archiving algorithms. A \((\mu+\lambda)\)-archiving algorithm defines how to choose in each generation \(\mu\) children from \(\mu\) parents and \(\lambda\) offspring together. Archiving algorithms have to choose individuals online without knowing future offspring. Previous studies assumed the offspring generation to be best-case. We assume the initial population and the offspring generation to be worst-case and use the competitive ratio to measure how much smaller hypervolumes an archiving algorithm finds due to not knowing the future in advance. We prove that all archiving algorithms which increase the hypervolume in each step (if they can) are only \(\mu\)-competitive. We also present a new archiving algorithm which is \((4+2/\mu)\)-competitive. This algorithm not only achieves a constant competitive ratio, but is also efficiently computable. Both properties provably do not hold for the commonly used greedy archiving algorithms, for example those used in SIBEA, SMS-EMOA, or the generational MO-CMA-ES.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2012}, pages = {457-464}, publisher = {{ACM}}, title = {Convergence of hypervolume-based archiving algorithms ii: competitiveness}, year = 2012 }
• 
  Baumbach, Jan; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch Efficient Algorithms for Extracting Biological Key Pathways with Global Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2012: 169-176
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs where all nodes but K are expressed in all cases but at most L, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected sub-networks where all but at most K nodes are expressed in all cases but in total (!) at most L, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONE-components is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpi-inf.mpg.de.
  @inproceedings{DBLP:conf/gecco/BaumbachFKKMP12, abstract = {The integrated analysis of data of different types and with various interdependencies is one of the major challenges in computational biology. Recently, we developed KeyPathwayMiner, a method that combines biological networks modeled as graphs with disease-specific genetic expression data gained from a set of cases (patients, cell lines, tissues, etc.). We aimed for finding all maximal connected sub-graphs where all nodes but K are expressed in all cases but at most L, i.e. key pathways. Thereby, we combined biological networks with OMICS data, instead of analyzing these data sets in isolation. Here we present an alternative approach that avoids a certain bias towards hub nodes: We now aim for extracting all maximal connected sub-networks where all but at most K nodes are expressed in all cases but in total (!) at most L, i.e. accumulated over all cases and all nodes in a solution. We call this strategy GLONE (global node exceptions); the previous problem we call INES (individual node exceptions). Since finding GLONE-components is computationally hard, we developed an Ant Colony Optimization algorithm and implemented it with the KeyPathwayMiner Cytoscape framework as an alternative to the INES algorithms. KeyPathwayMiner 3.0 now offers both the INES and the GLONE algorithms. It is available as plugin from Cytoscape and online at http://keypathwayminer.mpi-inf.mpg.de.}, author = {Baumbach, Jan and Friedrich, Tobias and Kötzing, Timo and Krohmer, Anton and Müller, Joachim and Pauling, Josch}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {ACO antonkrohmer gecco timokoetzing tobiasfriedrich year2012}, pages = {169-176}, title = {Efficient Algorithms for Extracting Biological Key Pathways with Global Constraints}, year = 2012 }

2011 [ to top ]

• 
  Sutton, Andrew M.; Whitley, Darrell; Howe, Adele E. Mutation rates of the (1+1)-EA on pseudo-boolean functions of bounded epistasis. Genetic and Evolutionary Computation Conference (GECCO) 2011: 973-980
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)-EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of \(1/n\) is provably optimal. On functions where epistasis is bounded by a constant \(k\), we show that for sufficiently high fitness, the commonly used mutation rate of \(1/n\) is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degree-\(k\) polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum \(k\)-satisfiability problems and NK-landscapes show that this expectation-maximized mutation rate can cause significant gains early in search.
  @inproceedings{DBLP:conf/gecco/SuttonWH11, abstract = {When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)-EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of \(1/n\) is provably optimal. On functions where epistasis is bounded by a constant \(k\), we show that for sufficiently high fitness, the commonly used mutation rate of \(1/n\) is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degree-\(k\) polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum \(k\)-satisfiability problems and NK-landscapes show that this expectation-maximized mutation rate can cause significant gains early in search.}, author = {Sutton, Andrew M. and Whitley, Darrell and Howe, Adele E.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2011}, pages = {973-980}, publisher = {{ACM}}, title = {Mutation rates of the (1+1)-EA on pseudo-boolean functions of bounded epistasis}, year = 2011 }
• 
  Kötzing, Timo; Neumann, Frank; Spöhel, Reto PAC learning and genetic programming. Genetic and Evolutionary Computation Conference (GECCO) 2011: 2091-2096
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Genetic programming (GP) is a very successful type of learning algorithm that is hard to understand from a theoretical point of view. With this paper we contribute to the computational complexity analysis of genetic programming that has been started recently. We analyze GP in the well-known PAC learning framework and point out how it can observe quality changes in the the evolution of functions by random sampling. This leads to computational complexity bounds for a linear GP algorithm for perfectly learning any member of a simple class of linear pseudo-Boolean functions. Furthermore, we show that the same algorithm on the functions from the same class finds good approximations of the target function in less time.
  @inproceedings{DBLP:conf/gecco/KotzingNS11, abstract = {Genetic programming (GP) is a very successful type of learning algorithm that is hard to understand from a theoretical point of view. With this paper we contribute to the computational complexity analysis of genetic programming that has been started recently. We analyze GP in the well-known PAC learning framework and point out how it can observe quality changes in the the evolution of functions by random sampling. This leads to computational complexity bounds for a linear GP algorithm for perfectly learning any member of a simple class of linear pseudo-Boolean functions. Furthermore, we show that the same algorithm on the functions from the same class finds good approximations of the target function in less time.}, author = {Kötzing, Timo and Neumann, Frank and Spöhel, Reto}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {frankneumann gecco imported retospoehel timokoetzing year2011}, pages = {2091-2096}, publisher = {{ACM}}, title = {PAC learning and genetic programming}, year = 2011 }
• 
  Doerr, Benjamin; Lengler, Johannes; Kötzing, Timo; Winzen, Carola Black-box complexities of combinatorial problems. Genetic and Evolutionary Computation Conference (GECCO) 2011: 981-988
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on black-box complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and single-source shortest paths. Besides giving interesting bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem is non-trivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.
  @inproceedings{DBLP:conf/gecco/DoerrLKW11, abstract = {Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on black-box complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and single-source shortest paths. Besides giving interesting bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem is non-trivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.}, author = {Doerr, Benjamin and Lengler, Johannes and Kötzing, Timo and Winzen, Carola}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr caroladoerr gecco imported johanneslengler timokoetzing year2011}, pages = {981-988}, publisher = {{ACM}}, title = {Black-box complexities of combinatorial problems}, year = 2011 }
• 
  Doerr, Benjamin; Kötzing, Timo; Winzen, Carola Too fast unbiased black-box algorithms. Genetic and Evolutionary Computation Conference (GECCO) 2011: 2043-2050
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Unbiased black-box complexity was recently introduced as a refined complexity model for randomized search heuristics (Lehre and Witt, GECCO 2010). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste, Jansen, and Wegener (Theor. Comput. Sci. 2006). In this work, we show that for two natural problems the unbiased black-box complexity remains artificially small. For the classical JumpK test function class and for a subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity \(O(n \log n)\). Since the first problem usually needs \(\Theta(n^k)\) function evaluations to be optimized by standard heuristics and the second is even NP-complete, these black-box complexities seem not to indicate the true difficulty of the two problems for randomized search heuristics.
  @inproceedings{DBLP:conf/gecco/DoerrKW11, abstract = {Unbiased black-box complexity was recently introduced as a refined complexity model for randomized search heuristics (Lehre and Witt, GECCO 2010). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste, Jansen, and Wegener (Theor. Comput. Sci. 2006). In this work, we show that for two natural problems the unbiased black-box complexity remains artificially small. For the classical JumpK test function class and for a subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity \(O(n \log n)\). Since the first problem usually needs \(\Theta(n^k)\) function evaluations to be optimized by standard heuristics and the second is even NP-complete, these black-box complexities seem not to indicate the true difficulty of the two problems for randomized search heuristics.}, author = {Doerr, Benjamin and Kötzing, Timo and Winzen, Carola}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr caroladoerr gecco imported timokoetzing year2011}, pages = {2043-2050}, publisher = {{ACM}}, title = {Too fast unbiased black-box algorithms}, year = 2011 }
• 
  Kötzing, Timo; Sudholt, Dirk; Theile, Madeleine How crossover helps in pseudo-boolean optimization. Genetic and Evolutionary Computation Conference (GECCO) 2011: 989-996
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions OneMax and Jump. First, we assess the potential speedup by crossover when combined with a fitness-invariant bit shuffling operator that simulates a lineage of independent evolution on a function of unitation. Theoretical and empirical results show drastic speedups for both functions. Second, we consider a simple GA without shuffling and investigate the interplay of mutation and crossover on Jump. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. We complement our theoretical findings by Monte Carlo simulations on the population diversity.
  @inproceedings{DBLP:conf/gecco/KotzingST11, abstract = {Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions OneMax and Jump. First, we assess the potential speedup by crossover when combined with a fitness-invariant bit shuffling operator that simulates a lineage of independent evolution on a function of unitation. Theoretical and empirical results show drastic speedups for both functions. Second, we consider a simple GA without shuffling and investigate the interplay of mutation and crossover on Jump. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. We complement our theoretical findings by Monte Carlo simulations on the population diversity.}, author = {Kötzing, Timo and Sudholt, Dirk and Theile, Madeleine}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {dirksudholt gecco imported madeleinetheile timokoetzing year2011}, pages = {989-996}, publisher = {{ACM}}, title = {How crossover helps in pseudo-boolean optimization}, year = 2011 }
• 
  Bringmann, Karl; Friedrich, Tobias Convergence of hypervolume-based archiving algorithms I: effectiveness. Genetic and Evolutionary Computation Conference (GECCO) 2011: 745-752

  Nominated for Best Paper Award (EMO Track)
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The core of hypervolume-based multi-objective evolutionary algorithms is an archiving algorithm which performs the environmental selection. A \((\mu+\lambda)\)-archiving algorithm defines how to choose \(\mu\) children from \(\mu\) parents and \(\lambda\) offspring together. We study theoretically \((\mu+\lambda)\)-archiving algorithms which never decrease the hypervolume from one generation to the next. Zitzler, Thiele, and Bader (IEEE Trans. Evolutionary Computation, 14:58--79, 2010) proved that all \((\mu+1)\)-archiving algorithms are ineffective, which means there is an initial population such that independent of the used reproduction rule, a set with maximum hypervolume cannot be reached. We extend this and prove that for \(\lambda < \mu\) all archiving algorithms are ineffective. On the other hand, locally optimal algorithms, which maximize the hypervolume in each step, are effective for \(\lambda = \mu\) and can always find a population with hypervolume at least half the optimum for \(\lambda < \mu\). We also prove that there is no hypervolume-based archiving algorithm which can always find a population with hypervolume greater than \(1 / (1 + 0.1338, ( 1/\lambda - 1/\mu) )\) times the optimum.
  @inproceedings{DBLP:conf/gecco/BringmannF11, abstract = {The core of hypervolume-based multi-objective evolutionary algorithms is an archiving algorithm which performs the environmental selection. A \((\mu+\lambda)\)-archiving algorithm defines how to choose \(\mu\) children from \(\mu\) parents and \(\lambda\) offspring together. We study theoretically \((\mu+\lambda)\)-archiving algorithms which never decrease the hypervolume from one generation to the next. Zitzler, Thiele, and Bader (IEEE Trans. Evolutionary Computation, 14:58--79, 2010) proved that all \((\mu+1)\)-archiving algorithms are ineffective, which means there is an initial population such that independent of the used reproduction rule, a set with maximum hypervolume cannot be reached. We extend this and prove that for \(\lambda < \mu\) all archiving algorithms are ineffective. On the other hand, locally optimal algorithms, which maximize the hypervolume in each step, are effective for \(\lambda = \mu\) and can always find a population with hypervolume at least half the optimum for \(\lambda < \mu\). We also prove that there is no hypervolume-based archiving algorithm which can always find a population with hypervolume greater than \(1 / (1 + 0.1338, ( 1/\lambda - 1/\mu) )\) times the optimum.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2011}, note = {Nominated for Best Paper Award (EMO Track)}, pages = {745-752}, publisher = {{ACM}}, title = {Convergence of hypervolume-based archiving algorithms I: effectiveness}, year = 2011 }

2010 [ to top ]

• 
  Bringmann, Karl; Friedrich, Tobias The maximum hypervolume set yields near-optimal approximation. Genetic and Evolutionary Computation Conference (GECCO) 2010: 511-518

  Best Paper Award (EMO Track)
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multiobjective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation factor with the approximation factor achieved by sets maximizing the hypervolume indicator. We bound the optimal approximation factor of \(n\) points by \(1+\Theta(1/n)\) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of \(n\) points that maximize the hypervolume indicator. This shows that the speed of convergence of the approximation ratio achieved by maximizing the hypervolume indicator is asymptotically optimal. This implies that for large values of \(n\), sets maximizing the hypervolume indicator quickly approach the optimal approximation ratio. Moreover, our bounds show that also for relatively small values of \(n\), sets maximizing the hypervolume indicator achieve a near-optimal approximation ratio.
  @inproceedings{DBLP:conf/gecco/BringmannF10, abstract = {In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multiobjective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation factor with the approximation factor achieved by sets maximizing the hypervolume indicator. We bound the optimal approximation factor of \(n\) points by \(1+\Theta(1/n)\) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of \(n\) points that maximize the hypervolume indicator. This shows that the speed of convergence of the approximation ratio achieved by maximizing the hypervolume indicator is asymptotically optimal. This implies that for large values of \(n\), sets maximizing the hypervolume indicator quickly approach the optimal approximation ratio. Moreover, our bounds show that also for relatively small values of \(n\), sets maximizing the hypervolume indicator achieve a near-optimal approximation ratio.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2010}, note = {Best Paper Award (EMO Track)}, pages = {511-518}, publisher = {{ACM}}, title = {The maximum hypervolume set yields near-optimal approximation}, year = 2010 }
• 
  Berghammer, Rudolf; Friedrich, Tobias; Neumann, Frank Set-based multi-objective optimization, indicators, and deteriorative cycles. Genetic and Evolutionary Computation Conference (GECCO) 2010: 495-502
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Evolutionary multi-objective optimization deals with the task of computing a minimal set of search points according to a given set of objective functions. The task has been made explicit in a recent paper by Zitzler et al. [13]. We take an order-theoretic view on this task and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. Thereby, we point out that evolutionary algorithms for multi-objective optimization working on the dominance relation of search points have to deal with a cyclic behavior that may lead to worsenings with respect to the Pareto-dominance relation defined on sets. Later on, we point out in which situations well-known binary and unary indicators can help to avoid this cyclic behavior.
  @inproceedings{DBLP:conf/gecco/BerghammerFN10, abstract = {Evolutionary multi-objective optimization deals with the task of computing a minimal set of search points according to a given set of objective functions. The task has been made explicit in a recent paper by Zitzler et al. [13]. We take an order-theoretic view on this task and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. Thereby, we point out that evolutionary algorithms for multi-objective optimization working on the dominance relation of search points have to deal with a cyclic behavior that may lead to worsenings with respect to the Pareto-dominance relation defined on sets. Later on, we point out in which situations well-known binary and unary indicators can help to avoid this cyclic behavior.}, author = {Berghammer, Rudolf and Friedrich, Tobias and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {frankneumann gecco imported rudolfberghammer tobiasfriedrich year2010}, pages = {495-502}, publisher = {{ACM}}, title = {Set-based multi-objective optimization, indicators, and deteriorative cycles}, year = 2010 }
• 
  Kötzing, Timo; Lehre, Per Kristian; Neumann, Frank; Oliveto, Pietro Simone Ant colony optimization and the minimum cut problem. Genetic and Evolutionary Computation Conference (GECCO) 2010: 1393-1400
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts.
  @inproceedings{DBLP:conf/gecco/KotzingLNO10, abstract = {Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts.}, author = {Kötzing, Timo and Lehre, Per Kristian and Neumann, Frank and Oliveto, Pietro Simone}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {frankneumann gecco imported perkristianlehre pietrosimoneoliveto timokoetzing year2010}, pages = {1393-1400}, publisher = {{ACM}}, title = {Ant colony optimization and the minimum cut problem}, year = 2010 }
• 
  Voß, Thomas; Friedrich, Tobias; Bringmann, Karl; Igel, Christian Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study. Genetic and Evolutionary Computation Conference (GECCO) 2010: 1975-1978
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  It is known that the performance of multi-objective evolutionary algorithms (MOEAs) in general deteriorates with increasing number of objectives. For few objectives, MOEAs relying on the contributing hypervolume as (second-level) sorting criterion are the methods of choice. However, the computational complexity of calculating the contributing hypervolume prevents the broad application of these powerful MOEAs to objective functions with many objectives. In this study, we employ the approximation within the steady-state MO-CMA-ES and the SMS-EMOA to empirically investigate whether the Monte-Carlo approximation is indeed useful in practice.
  @inproceedings{DBLP:conf/gecco/VossFBI10, abstract = {It is known that the performance of multi-objective evolutionary algorithms (MOEAs) in general deteriorates with increasing number of objectives. For few objectives, MOEAs relying on the contributing hypervolume as (second-level) sorting criterion are the methods of choice. However, the computational complexity of calculating the contributing hypervolume prevents the broad application of these powerful MOEAs to objective functions with many objectives. In this study, we employ the approximation within the steady-state MO-CMA-ES and the SMS-EMOA to empirically investigate whether the Monte-Carlo approximation is indeed useful in practice.}, author = {Voß, Thomas and Friedrich, Tobias and Bringmann, Karl and Igel, Christian}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco noabstract tobiasfriedrich year2010}, pages = {1975-1978}, title = {Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study}, year = 2010 }

2009 [ to top ]

• 
  Whitley, L. Darrell; Sutton, Andrew M. Partial neighborhoods of elementary landscapes. Genetic and Evolutionary Computation Conference (GECCO) 2009: 381-388
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  This paper introduces a new component based model that makes it relatively simple to prove that certain types of landscapes are elementary. We use the model to reconstruct proofs for the Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning. The same model is then used to efficiently compute the average values over particular partial neighborhoods for these same problems. For Graph Coloring and Min-Cut Graph Partitioning, this computation can be used to focus search on those moves that are most likely to yield an improving move, ignoring moves that cannot yield an improving move. Let \(x\) be a candidate solution with objective function value \(f(x)\). The mean value of the objective function over the entire landscape is denoted \(f\). Normally in an elementary landscape one can only be sure that a neighborhood includes an improving move (assuming minimization) if \(f(x) > f\). However, by computing the expected value of an appropriate partial neighborhood it is sometimes possible to know that an improving move exists in the partial neighborhood even when \(f(x) < f\).
  @inproceedings{DBLP:conf/gecco/WhitleyS09, abstract = {This paper introduces a new component based model that makes it relatively simple to prove that certain types of landscapes are elementary. We use the model to reconstruct proofs for the Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning. The same model is then used to efficiently compute the average values over particular partial neighborhoods for these same problems. For Graph Coloring and Min-Cut Graph Partitioning, this computation can be used to focus search on those moves that are most likely to yield an improving move, ignoring moves that cannot yield an improving move. Let \(x\) be a candidate solution with objective function value \(f(x)\). The mean value of the objective function over the entire landscape is denoted \(f\). Normally in an elementary landscape one can only be sure that a neighborhood includes an improving move (assuming minimization) if \(f(x) > f\). However, by computing the expected value of an appropriate partial neighborhood it is sometimes possible to know that an improving move exists in the partial neighborhood even when \(f(x) < f\).}, author = {Whitley, L. Darrell and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2009}, pages = {381-388}, publisher = {{ACM}}, title = {Partial neighborhoods of elementary landscapes}, year = 2009 }
• 
  Friedrich, Tobias; Horoba, Christian; Neumann, Frank Multiplicative approximations and the hypervolume indicator. Genetic and Evolutionary Computation Conference (GECCO) 2009: 571-578

  Best Paper Award (EMO Track)
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Indicator-based algorithms have become a very popular approach to solve multi-objective optimization problems. In this paper, we contribute to the theoretical understanding of algorithms maximizing the hypervolume for a given problem by distributing \(\mu\) points on the Pareto front. We examine this common approach with respect to the achieved multiplicative approximation ratio for a given multi-objective problem and relate it to a set of \(\mu\) points on the Pareto front that achieves the best possible approximation ratio. For the class of linear fronts and a class of concave fronts, we prove that the hypervolume gives the best possible approximation ratio. In addition, we examine Pareto fronts of different shapes by numerical calculations and show that the approximation computed by the hypervolume may differ from the optimal approximation ratio.
  @inproceedings{DBLP:conf/gecco/FriedrichHN09, abstract = {Indicator-based algorithms have become a very popular approach to solve multi-objective optimization problems. In this paper, we contribute to the theoretical understanding of algorithms maximizing the hypervolume for a given problem by distributing \(\mu\) points on the Pareto front. We examine this common approach with respect to the achieved multiplicative approximation ratio for a given multi-objective problem and relate it to a set of \(\mu\) points on the Pareto front that achieves the best possible approximation ratio. For the class of linear fronts and a class of concave fronts, we prove that the hypervolume gives the best possible approximation ratio. In addition, we examine Pareto fronts of different shapes by numerical calculations and show that the approximation computed by the hypervolume may differ from the optimal approximation ratio.}, author = {Friedrich, Tobias and Horoba, Christian and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {christianhoroba frankneumann gecco imported tobiasfriedrich year2009}, note = {Best Paper Award (EMO Track)}, pages = {571-578}, publisher = {{ACM}}, title = {Multiplicative approximations and the hypervolume indicator}, year = 2009 }
• 
  Sutton, Andrew M.; Whitley, L. Darrell; Howe, Adele E. A polynomial time computation of the exact correlation structure of k-satisfiability landscapes. Genetic and Evolutionary Computation Conference (GECCO) 2009: 365-372
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The autocorrelation function and related correlation length are statistical quantities that capture the ruggedness of the fitness landscape: a measure that is directly related to the hardness of a problem for certain heuristic search algorithms. Typically, these quantities are estimated empirically by sampling along a random walk. In this paper, we show that a polynomial-time Walsh decomposition of the \(k\)-satisfiability evaluation function allows us to compute the exact autocorrelation function and correlation length for any given \(k\)-satisfiability instance. We also use the decomposition to compute a theoretical expectation for the autocorrelation function and correlation length over the ensemble of instances generated uniformly at random. We find that this expectation is invariant to the constrainedness of the problem as measured by the ratio of clauses to variables. However, we show that filtered problems, which are typically used in local search studies, have a bias that causes a significant deviation from the expected correlation structure of unfiltered, uniformly generated problems.
  @inproceedings{DBLP:conf/gecco/SuttonWH09, abstract = {The autocorrelation function and related correlation length are statistical quantities that capture the ruggedness of the fitness landscape: a measure that is directly related to the hardness of a problem for certain heuristic search algorithms. Typically, these quantities are estimated empirically by sampling along a random walk. In this paper, we show that a polynomial-time Walsh decomposition of the \(k\)-satisfiability evaluation function allows us to compute the exact autocorrelation function and correlation length for any given \(k\)-satisfiability instance. We also use the decomposition to compute a theoretical expectation for the autocorrelation function and correlation length over the ensemble of instances generated uniformly at random. We find that this expectation is invariant to the constrainedness of the problem as measured by the ratio of clauses to variables. However, we show that filtered problems, which are typically used in local search studies, have a bias that causes a significant deviation from the expected correlation structure of unfiltered, uniformly generated problems.}, author = {Sutton, Andrew M. and Whitley, L. Darrell and Howe, Adele E.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2009}, pages = {365-372}, publisher = {{ACM}}, title = {A polynomial time computation of the exact correlation structure of k-satisfiability landscapes}, year = 2009 }

2008 [ to top ]

• 
  Friedrich, Tobias; Oliveto, Pietro Simone; Sudholt, Dirk; Witt, Carsten Theoretical analysis of diversity mechanisms for global exploration. Genetic and Evolutionary Computation Conference (GECCO) 2008: 945-952

  Best Paper Award (Genetic Algorithms Track)
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Maintaining diversity is important for the performance of evolutionary algorithms. Diversity-preserving mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the global exploration capabilities of mutation-based algorithms. Using a simple bimodal test function and rigorous runtime analyses, we compare well-known diversity-preserving mechanisms like deterministic crowding, fitness sharing, and others with a plain algorithm without diversification. We show that diversification is necessary for global exploration, but not all mechanisms succeed in finding both optima efficiently. Our theoretical results are accompanied by additional experiments for different population sizes.
  @inproceedings{DBLP:conf/gecco/FriedrichOSW08, abstract = {Maintaining diversity is important for the performance of evolutionary algorithms. Diversity-preserving mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the global exploration capabilities of mutation-based algorithms. Using a simple bimodal test function and rigorous runtime analyses, we compare well-known diversity-preserving mechanisms like deterministic crowding, fitness sharing, and others with a plain algorithm without diversification. We show that diversification is necessary for global exploration, but not all mechanisms succeed in finding both optima efficiently. Our theoretical results are accompanied by additional experiments for different population sizes.}, author = {Friedrich, Tobias and Oliveto, Pietro Simone and Sudholt, Dirk and Witt, Carsten}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2008}, note = {Best Paper Award (Genetic Algorithms Track)}, pages = {945-952}, publisher = {{ACM}}, title = {Theoretical analysis of diversity mechanisms for global exploration}, year = 2008 }
• 
  Whitley, Darrell; Sutton, Andrew M.; Howe, Adele E. Understanding elementary landscapes. Genetic and Evolutionary Computation Conference (GECCO) 2008: 585-592
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The landscape formalism unites a finite candidate solution set to a neighborhood topology and an objective function. This construct can be used to model the behavior of local search on combinatorial optimization problems. A landscape is elementary when it possesses a unique property that results in a relative smoothness and decomposability to its structure. In this paper we explain elementary landscapes in terms of the expected value of solution components which are transformed in the process of moving from an incumbent solution to a neighboring solution. We introduce new results about the properties of elementary landscapes and discuss the practical implications for search algorithms.
  @inproceedings{DBLP:conf/gecco/WhitleySH08, abstract = {The landscape formalism unites a finite candidate solution set to a neighborhood topology and an objective function. This construct can be used to model the behavior of local search on combinatorial optimization problems. A landscape is elementary when it possesses a unique property that results in a relative smoothness and decomposability to its structure. In this paper we explain elementary landscapes in terms of the expected value of solution components which are transformed in the process of moving from an incumbent solution to a neighboring solution. We introduce new results about the properties of elementary landscapes and discuss the practical implications for search algorithms.}, author = {Whitley, Darrell and Sutton, Andrew M. and Howe, Adele E.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2008}, pages = {585-592}, publisher = {{ACM}}, title = {Understanding elementary landscapes}, year = 2008 }

2007 [ to top ]

• 
  Sutton, Andrew M.; Lunacek, Monte; Whitley, L. Darrell Differential evolution and non-separability: using selective pressure to focus search. Genetic and Evolutionary Computation Conference (GECCO) 2007: 1428-1435
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Recent results show that the Differential Evolution algorithm has significant difficulty on functions that are not linearly separable. On such functions, the algorithm must rely primarily on its differential mutation procedure which, unlike its recombination strategy, is rotationally invariant. We conjecture that this mutation strategy lacks sufficient selective pressure when appointing parent and donor vectors to have satisfactory exploitative power on non-separable functions. We find that imposing pressure in the form of rank-based differential mutation results in a significant improvement of exploitation on rotated benchmarks.
  @inproceedings{DBLP:conf/gecco/SuttonLW07, abstract = {Recent results show that the Differential Evolution algorithm has significant difficulty on functions that are not linearly separable. On such functions, the algorithm must rely primarily on its differential mutation procedure which, unlike its recombination strategy, is rotationally invariant. We conjecture that this mutation strategy lacks sufficient selective pressure when appointing parent and donor vectors to have satisfactory exploitative power on non-separable functions. We find that imposing pressure in the form of rank-based differential mutation results in a significant improvement of exploitation on rotated benchmarks.}, author = {Sutton, Andrew M. and Lunacek, Monte and Whitley, L. Darrell}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2007}, pages = {1428-1435}, publisher = {{ACM}}, title = {Differential evolution and non-separability: using selective pressure to focus search}, year = 2007 }
• 
  Friedrich, Tobias; Hebbinghaus, Nils; Neumann, Frank Rigorous analyses of simple diversity mechanisms. Genetic and Evolutionary Computation Conference (GECCO) 2007: 1219-1225
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  It is widely assumed and observed in experiments that the use of diversity mechanisms in evolutionary algorithms may have a great impact on its running time. Up to now there is no rigorous analysis pointing out the use of different mechanisms with respect to the runtime behavior. We consider evolutionary algorithms that differ from each other in the way they ensure diversity and point out situations where the right mechanism is crucial for the success of the algorithm. The algorithms considered either diversify the population with respect to the search points or with respect to function values. Investigating simple plateau functions, we show that using the "right" diversity strategy makes the difference between an exponential and a polynomial runtime.
  @inproceedings{DBLP:conf/gecco/FriedrichHN07, abstract = {It is widely assumed and observed in experiments that the use of diversity mechanisms in evolutionary algorithms may have a great impact on its running time. Up to now there is no rigorous analysis pointing out the use of different mechanisms with respect to the runtime behavior. We consider evolutionary algorithms that differ from each other in the way they ensure diversity and point out situations where the right mechanism is crucial for the success of the algorithm. The algorithms considered either diversify the population with respect to the search points or with respect to function values. Investigating simple plateau functions, we show that using the "right" diversity strategy makes the difference between an exponential and a polynomial runtime.}, author = {Friedrich, Tobias and Hebbinghaus, Nils and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {frankneumann gecco imported nilshebbinghaus tobiasfriedrich year2007}, pages = {1219-1225}, publisher = {ACM}, title = {Rigorous analyses of simple diversity mechanisms}, year = 2007 }
• 
  Friedrich, Tobias; Hebbinghaus, Nils; Neumann, Frank; He, Jun; Witt, Carsten Approximating covering problems by randomized search heuristics using multi-objective models. Genetic and Evolutionary Computation Conference (GECCO) 2007: 797-804
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical ones on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare single-objective and multi-objective models for such problems. For the Vertex-Cover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case even no good approximation can be achieved within expected polynomial time. Examining the more general Set-Cover problem we show that optimal solutions can be approximated within a factor of \(\log n\), where \(n\) is the problem dimension, using the multi-objective approach while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.
  @inproceedings{DBLP:conf/gecco/FriedrichHNHW07, abstract = {The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical ones on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare single-objective and multi-objective models for such problems. For the Vertex-Cover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case even no good approximation can be achieved within expected polynomial time. Examining the more general Set-Cover problem we show that optimal solutions can be approximated within a factor of \(\log n\), where \(n\) is the problem dimension, using the multi-objective approach while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.}, author = {Friedrich, Tobias and Hebbinghaus, Nils and Neumann, Frank and He, Jun and Witt, Carsten}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {carstenwitt frankneumann gecco junhe nilshebbinghaus noabstract tobiasfriedrich year2007}, pages = {797-804}, title = {Approximating covering problems by randomized search heuristics using multi-objective models}, year = 2007 }
• 
  Brockhoff, Dimo; Friedrich, Tobias; Hebbinghaus, Nils; Klein, Christian; Neumann, Frank; Zitzler, Eckart Do additional objectives make a problem harder?. Genetic and Evolutionary Computation Conference (GECCO) 2007: 765-772
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In this paper, we examine how adding objectives to a given optimization problem affects the computation effort required to generate the set of Pareto-optimal solutions. Experimental studies show that additional objectives may change the runtime behavior of an algorithm drastically. Often it is assumed that more objectives make a problem harder as the number of different trade-offs may increase with the problem dimension. We show that additional objectives, however, may be both beneficial and obstructive depending on the chosen objective. Our results are obtained by rigorous runtime analyses that show the different effects of adding objectives to a well-known plateau-function.
  @inproceedings{DBLP:conf/gecco/BrockhoffFHKNZ07, abstract = {In this paper, we examine how adding objectives to a given optimization problem affects the computation effort required to generate the set of Pareto-optimal solutions. Experimental studies show that additional objectives may change the runtime behavior of an algorithm drastically. Often it is assumed that more objectives make a problem harder as the number of different trade-offs may increase with the problem dimension. We show that additional objectives, however, may be both beneficial and obstructive depending on the chosen objective. Our results are obtained by rigorous runtime analyses that show the different effects of adding objectives to a well-known plateau-function.}, author = {Brockhoff, Dimo and Friedrich, Tobias and Hebbinghaus, Nils and Klein, Christian and Neumann, Frank and Zitzler, Eckart}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {christianklein dimobrockhoff eckartzitzler frankneumann gecco imported nilshebbinghaus tobiasfriedrich year2007}, pages = {765-772}, publisher = {{ACM}}, title = {Do additional objectives make a problem harder?}, year = 2007 }

2006 [ to top ]

• 
  Sutton, Andrew M.; Whitley, Darrell; Lunacek, Monte; Howe, Adele E. PSO and multi-funnel landscapes: how cooperation might limit exploration. Genetic and Evolutionary Computation Conference (GECCO) 2006: 75-82
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Particle Swarm Optimization (PSO) is a population-based optimization method in which search points employ a cooperative strategy to move toward one another. In this paper we show that PSO appears to work well on "singlefunnel" optimization functions. On more complex optimization problems, PSO tends to converge too quickly and then fail to make further progress. We contend that most benchmarks for PSO have classically been demonstrated on singlefunnel functions. However, in practice, optimization tasks are more complex and possess higher problem dimensionality. We present empirical results that support our conjecture that PSO performs well on single-funnel functions but tends to stagnate on more complicated landscapes.
  @inproceedings{DBLP:conf/gecco/SuttonWLH06, abstract = {Particle Swarm Optimization (PSO) is a population-based optimization method in which search points employ a cooperative strategy to move toward one another. In this paper we show that PSO appears to work well on "singlefunnel" optimization functions. On more complex optimization problems, PSO tends to converge too quickly and then fail to make further progress. We contend that most benchmarks for PSO have classically been demonstrated on singlefunnel functions. However, in practice, optimization tasks are more complex and possess higher problem dimensionality. We present empirical results that support our conjecture that PSO performs well on single-funnel functions but tends to stagnate on more complicated landscapes.}, author = {Sutton, Andrew M. and Whitley, Darrell and Lunacek, Monte and Howe, Adele E.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton gecco imported year2006}, pages = {75-82}, publisher = {{ACM}}, title = {PSO and multi-funnel landscapes: how cooperation might limit exploration}, year = 2006 }