ORCID Profile
0000-0002-2721-3618
Current Organisation
University of Adelaide
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: ACM
Date: 07-07-2010
Publisher: ACM
Date: 06-07-2013
Publisher: Elsevier BV
Date: 10-2011
Publisher: IEEE
Date: 07-2018
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: Springer Science and Business Media LLC
Date: 17-11-2010
Publisher: IEEE
Date: 06-2012
Publisher: IEEE
Date: 09-2007
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: IEEE
Date: 09-2007
Publisher: Springer International Publishing
Date: 2018
Publisher: Elsevier BV
Date: 09-2008
Publisher: ACM
Date: 02-07-2018
Publisher: ACM
Date: 11-07-2015
Publisher: Elsevier BV
Date: 04-2011
Publisher: Springer Science and Business Media LLC
Date: 31-10-2021
Publisher: ACM
Date: 11-07-2015
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: Springer International Publishing
Date: 2016
Publisher: Springer Science and Business Media LLC
Date: 09-08-2019
Publisher: Springer Science and Business Media LLC
Date: 29-08-2017
Publisher: ACM
Date: 12-07-2023
Publisher: ACM
Date: 07-07-2010
Publisher: Springer International Publishing
Date: 2018
Publisher: IEEE
Date: 07-2018
Publisher: ACM
Date: 06-07-2013
Publisher: ACM
Date: 06-07-2013
Publisher: IOS Press
Date: 28-09-2023
DOI: 10.3233/FAIA230463
Publisher: ACM
Date: 12-07-2014
Publisher: ACM
Date: 06-07-2018
Publisher: Springer Science and Business Media LLC
Date: 17-11-2009
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: ACM
Date: 06-07-2013
Publisher: Elsevier BV
Date: 02-2010
Publisher: Elsevier BV
Date: 06-2007
Publisher: MIT Press - Journals
Date: 09-2018
DOI: 10.1162/EVCO_A_00233
Abstract: The generalized travelling salesperson problem is an important NP-hard combinatorial optimization problem for which metaheuristics, such as local search and evolutionary algorithms, have been used very successfully. Two hierarchical approaches with different neighbourhood structures, namely a cluster-based approach and a node-based approach, have been proposed by Hu and Raidl ( 2008 ) for solving this problem. In this article, local search algorithms and simple evolutionary algorithms based on these approaches are investigated from a theoretical perspective. For local search algorithms, we point out the complementary abilities of the two approaches by presenting instances where they mutually outperform each other. Afterwards, we introduce an instance which is hard for both approaches when initialized on a particular point of the search space, but where a variable neighbourhood search combining them finds the optimal solution in polynomial time. Then we turn our attention to analysing the behaviour of simple evolutionary algorithms that use these approaches. We show that the node-based approach solves the hard instance of the cluster-based approach presented in Corus et al. ( 2016 ) in polynomial time. Furthermore, we prove an exponential lower bound on the optimization time of the node-based approach for a class of Euclidean instances.
Publisher: IEEE
Date: 05-2009
Publisher: Springer International Publishing
Date: 2021
Publisher: ACM
Date: 05-01-2011
Publisher: ACM
Date: 08-07-2009
Publisher: ACM
Date: 02-07-2018
Publisher: ACM
Date: 12-07-2023
Publisher: MIT Press - Journals
Date: 12-2014
DOI: 10.1162/EVCO_A_00119
Abstract: Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, 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 investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound their runtime. We analyze the runtime in dependence of the number of inner points k. In the first part of the paper, we study a [Formula: see text] EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time [Formula: see text] where A is a function of the minimum angle [Formula: see text] between any three points. Based on insights provided by the analysis, we improve this upper bound by introducing a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps. This strategy improves the upper bound to [Formula: see text]. In the second part of the paper, we use the information gained in the analysis to incorporate domain knowledge to design two fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a [Formula: see text] EA based on an analysis by M. Theile, 2009, ”Exact solutions to the traveling salesperson problem by a population-based evolutionary algorithm,” Lecture notes in computer science, Vol. 5482 (pp. 145–155), that solves the TSP with k inner points in [Formula: see text] generations with probability [Formula: see text]. We then design a [Formula: see text] EA that incorporates a dynamic programming step into the fitness evaluation. We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after [Formula: see text] steps in expectation with a cost of [Formula: see text] for each fitness evaluation.
Publisher: Springer Science and Business Media LLC
Date: 27-04-2006
Publisher: ACM
Date: 07-07-2010
Publisher: Springer International Publishing
Date: 2018
Publisher: ACM
Date: 13-07-2019
Publisher: ACM
Date: 05-01-2011
Publisher: Springer International Publishing
Date: 2016
Publisher: Springer International Publishing
Date: 2017
Publisher: MIT Press - Journals
Date: 09-2010
DOI: 10.1162/EVCO_E_00019
Publisher: Springer International Publishing
Date: 2016
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 10-2014
Publisher: ACM
Date: 12-07-2023
Publisher: Springer International Publishing
Date: 2015
Publisher: Springer International Publishing
Date: 2015
Publisher: Springer Science and Business Media LLC
Date: 30-03-2013
Publisher: Elsevier BV
Date: 2015
Publisher: ACM
Date: 15-07-2023
Publisher: Elsevier BV
Date: 06-2015
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: ACM
Date: 07-07-2012
Publisher: Elsevier BV
Date: 03-2013
Publisher: ACM
Date: 25-06-2005
Publisher: ACM
Date: 07-07-2012
Publisher: ACM
Date: 07-07-2007
Publisher: Frontiers Media SA
Date: 20-07-2015
Publisher: Springer Science and Business Media LLC
Date: 26-05-2013
Publisher: ACM
Date: 07-07-2007
Publisher: ACM
Date: 13-07-2019
Publisher: ACM
Date: 12-07-2023
Publisher: ACM
Date: 13-07-2019
Publisher: Association for Computing Machinery (ACM)
Date: 30-09-2022
DOI: 10.1145/3561974
Abstract: Generating erse populations of high-quality solutions has gained interest as a promising extension to the traditional optimization tasks. This work contributes to this line of research with an investigation on evolutionary ersity optimization for three of the most well-studied permutation problems: the Traveling Salesperson Problem (TSP), both symmetric and asymmetric variants, and the Quadratic Assignment Problem (QAP). It includes an analysis of the worst-case performance of a simple mutation-only evolutionary algorithm with different mutation operators, using an established ersity measure. Theoretical results show that many mutation operators for these problems guarantee convergence to maximally erse populations of sufficiently small size within cubic to quartic expected runtime. On the other hand, the results regarding QAP suggest that strong mutations give poor worst-case performance, as mutation strength contributes exponentially to the expected runtime. Additionally, experiments are carried out on QAPLIB and synthetic instances in unconstrained and constrained settings, and reveal much more optimistic practical performances while corroborating the theoretical findings regarding mutation strength. These results should serve as a baseline for future studies.
Publisher: Springer Science and Business Media LLC
Date: 10-05-2018
Publisher: MIT Press - Journals
Date: 12-2010
DOI: 10.1162/EVCO_A_00003
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 explorations 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 VertexCover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case, no good approximation can be achieved within the expected polynomial time. Examining the more general SetCover problem, we show that optimal solutions can be approximated within a logarithmic factor of the size of the ground set, using the multi-objective approach, while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.
Publisher: Springer Berlin Heidelberg
Date: 2011
Publisher: MIT Press
Date: 03-2018
DOI: 10.1162/EVCO_A_00242
Abstract: It has long been observed that for practically any computational problem that has been intensely studied, different instances are best solved using different algorithms. This is particularly pronounced for computationally hard problems, where in most cases, no single algorithm defines the state of the art instead, there is a set of algorithms with complementary strengths. This performance complementarity can be exploited in various ways, one of which is based on the idea of selecting, from a set of given algorithms, for each problem instance to be solved the one expected to perform best. The task of automatically selecting an algorithm from a given set is known as the per-instance algorithm selection problem and has been intensely studied over the past 15 years, leading to major improvements in the state of the art in solving a growing number of discrete combinatorial problems, including propositional satisfiability and AI planning. Per-instance algorithm selection also shows much promise for boosting performance in solving continuous and mixed discrete/continuous optimisation problems. This survey provides an overview of research in automated algorithm selection, ranging from early and seminal works to recent and promising application areas. Different from earlier work, it covers applications to discrete and continuous problems, and discusses algorithm selection in context with conceptually related approaches, such as algorithm configuration, scheduling, or portfolio selection. Since informative and cheaply computable problem instance features provide the basis for effective per-instance algorithm selection systems, we also provide an overview of such features for discrete and continuous problems. Finally, we provide perspectives on future work in the area and discuss a number of open research challenges.
Publisher: MIT Press - Journals
Date: 03-2015
DOI: 10.1162/EVCO_A_00126
Abstract: Many optimization problems arising in applications have to consider several objective functions at the same time. Evolutionary algorithms seem to be a very natural choice for dealing with multi-objective problems as the population of such an algorithm can be used to represent the trade-offs with respect to the given objective functions. In this paper, we contribute to the theoretical understanding of evolutionary algorithms for multi-objective problems. We consider indicator-based algorithms whose goal is to maximize the hypervolume for a given problem by distributing [Formula: see text] points on the Pareto front. To gain new theoretical insights into the behavior of hypervolume-based algorithms, we compare their optimization goal to the goal of achieving an optimal multiplicative approximation ratio. Our studies are carried out for different Pareto front shapes of bi-objective problems. For the class of linear fronts and a class of convex fronts, we prove that maximizing the hypervolume gives the best possible approximation ratio when assuming that the extreme points have to be included in both distributions of the points on the Pareto front. Furthermore, we investigate the choice of the reference point on the approximation behavior of hypervolume-based approaches and examine Pareto fronts of different shapes by numerical calculations.
Publisher: Elsevier BV
Date: 03-2012
Publisher: Springer International Publishing
Date: 2018
Publisher: IEEE
Date: 11-2018
Publisher: Springer Science and Business Media LLC
Date: 28-03-2013
Publisher: ACM
Date: 02-07-2018
Publisher: ACM
Date: 12-07-2011
Publisher: Springer International Publishing
Date: 2015
Publisher: IEEE
Date: 06-2016
Publisher: Springer Science and Business Media LLC
Date: 17-11-2011
Publisher: Springer International Publishing
Date: 2018
Publisher: Springer Science and Business Media LLC
Date: 05-12-2009
Publisher: IEEE
Date: 07-2014
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 09-2017
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: MIT Press - Journals
Date: 12-2015
DOI: 10.1162/EVCO_A_00159
Abstract: Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called ([Formula: see text]) EA and a multiobjective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints, we show that the GSEMO achieves a [Formula: see text]-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of [Formula: see text] matroids, we show that the ([Formula: see text]) EA achieves a ([Formula: see text])-approximation in expected polynomial time for any constant [Formula: see text]. Turning to nonmonotone symmetric submodular functions with [Formula: see text] matroid intersection constraints, we show that the GSEMO achieves a [Formula: see text]-approximation in expected time [Formula: see text].
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 06-2009
Publisher: ACM
Date: 07-07-2007
Publisher: Springer International Publishing
Date: 2022
Publisher: ACM
Date: 12-07-2011
Publisher: Elsevier BV
Date: 02-2013
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: ACM
Date: 07-07-2010
Publisher: ACM
Date: 12-07-2011
Publisher: Elsevier BV
Date: 02-2013
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11730095_13
Publisher: Springer Berlin Heidelberg
Date: 2015
Publisher: MIT Press - Journals
Date: 12-2015
DOI: 10.1162/EVCO_A_00149
Abstract: In genetic programming, the size of a solution is typically not specified in advance, and solutions of larger size may have a larger benefit. The flexibility often comes at the cost of the so-called bloat problem: in iduals grow without providing additional benefit to the quality of solutions, and the additional elements can block the optimization process. Consequently, problems that are relatively easy to optimize cannot be handled by variable-length evolutionary algorithms. In this article, we analyze different single- and multiobjective algorithms on the sorting problem, a problem that typically lacks independent and additive fitness structures. We complement the theoretical results with comprehensive experiments to indicate the tightness of existing bounds, and to indicate bounds where theoretical results are missing.
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: MIT Press - Journals
Date: 03-2016
DOI: 10.1162/EVCO_A_00147
Abstract: Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem and the generalised travelling salesperson problem in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl ( 2012 ) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) evolutionary algorithm working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the problem can be solved in fixed-parameter time with the global structure representation. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other’s hard instances very efficiently. For the generalised travelling salesperson problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) evolutionary algorithm working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.
Publisher: Elsevier BV
Date: 09-2007
Publisher: Elsevier BV
Date: 04-2016
Publisher: ACM
Date: 20-07-2016
Publisher: ACM
Date: 13-07-2019
Publisher: ACM
Date: 12-07-2023
Publisher: ACM
Date: 13-07-2019
Publisher: IEEE
Date: 06-2013
Publisher: Elsevier BV
Date: 09-2020
Publisher: IEEE
Date: 07-2014
Publisher: IEEE
Date: 07-2016
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: ACM
Date: 06-07-2013
Publisher: IEEE
Date: 09-2009
Publisher: ACM
Date: 07-2017
Publisher: ACM
Date: 12-01-2017
Publisher: Springer International Publishing
Date: 2017
Publisher: ACM
Date: 12-01-2017
Publisher: ACM
Date: 02-07-2018
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11734673_13
Publisher: ACM
Date: 11-07-2015
Publisher: ACM
Date: 20-07-2016
Publisher: Elsevier BV
Date: 04-2011
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11940128_62
Publisher: ACM
Date: 07-2017
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: ACM
Date: 11-07-2015
Publisher: ACM
Date: 16-01-2013
Publisher: MIT Press - Journals
Date: 12-2017
DOI: 10.1162/EVCO_A_00199
Abstract: Randomized search heuristics are frequently applied to NP-hard combinatorial optimization problems. The runtime analysis of randomized search heuristics has contributed tremendously to our theoretical understanding. Recently, randomized search heuristics have been examined regarding their achievable progress within a fixed-time budget. We follow this approach and present a fixed-budget analysis for an NP-hard combinatorial optimization problem. We consider the well-known Traveling Salesperson Problem (TSP) and analyze the fitness increase that randomized search heuristics are able to achieve within a given fixed-time budget. In particular, we analyze Manhattan and Euclidean TSP instances and Randomized Local Search (RLS), (1+1) EA and (1+[Formula: see text]) EA algorithms for the TSP in a smoothed complexity setting, and derive the lower bounds of the expected fitness gain for a specified number of generations.
Publisher: Springer International Publishing
Date: 2019
Publisher: ACM
Date: 12-07-2011
Publisher: Springer Science and Business Media LLC
Date: 15-10-2012
Publisher: ACM
Date: 07-07-2007
Publisher: ACM
Date: 12-07-2023
Publisher: Springer International Publishing
Date: 2022
Publisher: IEEE
Date: 06-2013
Publisher: IEEE
Date: 06-2012
Publisher: ACM
Date: 12-07-2014
Publisher: MIT Press - Journals
Date: 12-2007
DOI: 10.1162/EVCO.2007.15.4.401
Abstract: Successful applications of evolutionary algorithms show that certain variation operators can lead to good solutions much faster than other ones. We examine this behavior observed in practice from a theoretical point of view and investigate the effect of an asymmetric mutation operator in evolutionary algorithms with respect to the runtime behavior. Considering the Eulerian cycle problem we present runtime bounds for evolutionary algorithms using an asymmetric operator which are much smaller than the best upper bounds for a more general one. In our analysis it turns out that a plateau which both algorithms have to cope with changes its structure in a way that allows the algorithm to obtain an improvement much faster. In addition, we present a lower bound for the general case which shows that the asymmetric operator speeds up computation by at least a linear factor.
Publisher: Springer International Publishing
Date: 2021
Publisher: ACM
Date: 06-07-2013
Publisher: IEEE
Date: 06-2008
Publisher: ACM
Date: 20-07-2016
Publisher: ACM
Date: 09-01-2009
Publisher: ACM
Date: 09-01-2009
Publisher: Elsevier BV
Date: 03-2016
Publisher: ACM
Date: 07-07-2012
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: Springer International Publishing
Date: 2017
Publisher: ACM
Date: 07-07-2007
Publisher: Elsevier BV
Date: 05-2010
Publisher: Elsevier BV
Date: 08-2014
Publisher: IEEE
Date: 06-2008
Publisher: ACM
Date: 12-07-2014
Publisher: Springer Berlin Heidelberg
Date: 2005
DOI: 10.1007/11555964_4
Publisher: IEEE
Date: 11-2018
Publisher: ACM
Date: 07-2017
Publisher: Springer International Publishing
Date: 2019
Publisher: ACM
Date: 12-07-2014
Publisher: ACM
Date: 07-07-2010
Publisher: MIT Press - Journals
Date: 03-2009
Abstract: Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast, the theoretical understanding of the interplay of different optimization methods is rare. In this paper, we 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.
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: ACM
Date: 08-07-2009
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: ACM
Date: 20-07-2016
Publisher: Elsevier BV
Date: 04-2017
Publisher: ACM
Date: 13-07-2019
Publisher: ACM
Date: 11-07-2015
Publisher: ACM
Date: 30-08-2023
Publisher: ACM
Date: 08-07-2009
Publisher: Elsevier BV
Date: 10-2012
Publisher: ACM
Date: 30-08-2023
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: ACM
Date: 08-07-2009
Publisher: Elsevier BV
Date: 09-2020
Publisher: Elsevier BV
Date: 06-2009
Publisher: Springer International Publishing
Date: 2016
Publisher: Elsevier BV
Date: 09-2019
Publisher: Springer Science and Business Media LLC
Date: 28-11-2009
Publisher: IEEE
Date: 09-2007
Publisher: ACM
Date: 13-07-2019
Publisher: Springer Science and Business Media LLC
Date: 26-10-2010
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11682462_68
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: ACM
Date: 07-07-2012
No related grants have been discovered for Frank Neumann.