2017

Wagner, Markus; Friedrich, Tobias; Lindauer, Marius Improving local search in a minimum vertex cover solver for classes of networksCongress on Evolutionary Computation (CEC) 2017: 1704–1711
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks - which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.
@inproceedings{wagner2017improving, abstract = {For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks - which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.}, author = {Wagner, Markus and Friedrich, Tobias and Lindauer, Marius}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {cec markuswagner tobiasfriedrich year2017}, pages = {1704-1711}, title = {Improving local search in a minimum vertex cover solver for classes of networks}, year = 2017 }

2015

Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Efficient computation of two-dimensional solution sets maximizing the epsilon-indicatorCongress on Evolutionary Computation (CEC) 2015: 970–977
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The majority of empirical comparisons of multi-objective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the a-priori knowledge of the optimal Pareto front. This allows measuring the proximity to the optimal front for the solution sets returned by the different MOEAs. Such a comparison is only meaningful if the cardinality of all solution sets is bounded by some fixed \(k\). In order to compare MOEAs to the theoretical optimum achievable with \(k\) solutions, we determine best possible \(\epsilon\)-indicator values achievable with solution sets of size \(k\), up to an error of \(\delta\). We present a new algorithm with runtime \(O(k cdot \log^2(\delta-1))\), which is an exponential improvement regarding the dependence on the error \(\delta\) compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality \(k \in \2, 3, 4, 5, 10, 20, 50, 100, 1000\}\) for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error \(\delta = 10^{-25}\).
@inproceedings{DBLP:conf/cec/BringmannFK15, abstract = {The majority of empirical comparisons of multi-objective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the a-priori knowledge of the optimal Pareto front. This allows measuring the proximity to the optimal front for the solution sets returned by the different MOEAs. Such a comparison is only meaningful if the cardinality of all solution sets is bounded by some fixed \(k\). In order to compare MOEAs to the theoretical optimum achievable with \(k\) solutions, we determine best possible \(\epsilon\)-indicator values achievable with solution sets of size \(k\), up to an error of \(\delta\). We present a new algorithm with runtime \(O(k \cdot \log^2(\delta-1))\), which is an exponential improvement regarding the dependence on the error \(\delta\) compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality \(k \in \{2, 3, 4, 5, 10, 20, 50, 100, 1000\}\) for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error \(\delta = 10^{-25}\).}, author = {Bringmann, Karl and Friedrich, Tobias and Klitzke, Patrick}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {cec imported tobiasfriedrich year2015}, pages = {970-977}, title = {Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator}, year = 2015 }

2013

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problemCongress on Evolutionary Computation (CEC) 2013: 2045–2052
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the well-known MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.
@inproceedings{DBLP:conf/cec/NallaperumaSN13a, abstract = {We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the well-known MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.}, author = {Nallaperuma, Samadhi and Sutton, Andrew M. and Neumann, Frank}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {andrewmsutton cec frankneumann imported samadhinallaperuma year2013}, pages = {2045-2052}, title = {Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem}, year = 2013 }

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Fixed-parameter evolutionary algorithms for the Euclidean Traveling Salesperson problemCongress on Evolutionary Computation (CEC) 2013: 2037–2044
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points \(k\) and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time \(O(n^{4k(2k - 1)!)\). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2-opt tour can be found by randomized local search in expected time \(O(n^{2k}!)\).
@inproceedings{DBLP:conf/cec/NallaperumaSN13, abstract = {We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points \(k\) and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time \(O(n^{4k}(2k - 1)!)\). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2-opt tour can be found by randomized local search in expected time \(O(n^{2k}!)\).}, author = {Nallaperuma, Samadhi and Sutton, Andrew M. and Neumann, Frank}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {andrewmsutton cec frankneumann imported samadhinallaperuma year2013}, pages = {2037-2044}, title = {Fixed-parameter evolutionary algorithms for the Euclidean Traveling Salesperson problem}, year = 2013 }

2008

Friedrich, Tobias; Neumann, Frank When to use bit-wise neutralityCongress on Evolutionary Computation (CEC) 2008: 997–1003
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Representation techniques are important issues when designing successful evolutionary algorithms. Within this field the use of neutrality plays an important role. We examine the use of bit-wise neutrality introduced by Poli and Lopez (2007) from a theoretical point of view and show that this mechanism only enhances mutation-based evolutionary algorithms if not the same number of genotypic bits for each phenotypic bit is used. Using different numbers of genotypic bits for the bits in the phenome we point out by rigorous runtime analyses that it may reduce the optimization time significantly.
@inproceedings{DBLP:conf/cec/FriedrichN08, abstract = {Representation techniques are important issues when designing successful evolutionary algorithms. Within this field the use of neutrality plays an important role. We examine the use of bit-wise neutrality introduced by Poli and Lopez (2007) from a theoretical point of view and show that this mechanism only enhances mutation-based evolutionary algorithms if not the same number of genotypic bits for each phenotypic bit is used. Using different numbers of genotypic bits for the bits in the phenome we point out by rigorous runtime analyses that it may reduce the optimization time significantly.}, author = {Friedrich, Tobias and Neumann, Frank}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {cec frankneumann imported tobiasfriedrich year2008}, pages = {997-1003}, title = {When to use bit-wise neutrality}, year = 2008 }

2007

Friedrich, Tobias; He, Jun; Hebbinghaus, Nils; Neumann, Frank; Witt, Carsten On improving approximate solutions by evolutionary algorithmsCongress on Evolutionary Computation (CEC) 2007: 2614–2621
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast to this the theoretical understanding of the interplay of different optimization methods is rare. The aim of this paper is to make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.
@inproceedings{DBLP:conf/cec/FriedrichHHNW07, abstract = {Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast to this the theoretical understanding of the interplay of different optimization methods is rare. The aim of this paper is to make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.}, author = {Friedrich, Tobias and He, Jun and Hebbinghaus, Nils and Neumann, Frank and Witt, Carsten}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {carstenwitt cec frankneumann imported junhe nilshebbinghaus tobiasfriedrich year2007}, pages = {2614-2621}, title = {On improving approximate solutions by evolutionary algorithms}, year = 2007 }

Friedrich, Tobias; Hebbinghaus, Nils; Neumann, Frank Plateaus can be harder in multi-objective optimizationCongress on Evolutionary Computation (CEC) 2007: 2622–2629
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.
@inproceedings{DBLP:conf/cec/FriedrichHN07, abstract = {In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.}, author = {Friedrich, Tobias and Hebbinghaus, Nils and Neumann, Frank}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {cec frankneumann nilshebbinghaus noabstract tobiasfriedrich year2007}, pages = {2622-2629}, title = {Plateaus can be harder in multi-objective optimization}, year = 2007 }