Author name cluster

Dirk Sudholt

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers

1 author row

IJCAI Conference 2025 Conference Paper

Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem

Duc-Cuong Dang
Aneta Neumann
Frank Neumann
Andre Opris
Dirk Sudholt

Quality diversity (QD) algorithms, an extension of evolutionary algorithms, excel at generating diverse sets of high-quality solutions for complex problems in robotics, games, and combinatorial optimisation. Despite their success, the underlying mechanisms remain poorly understood due to a lack of a theoretical foundation. We address this gap by analysing QD algorithms on the all-pairs-shortest-paths (APSP) problem, a classical planning task that naturally seeks multiple solutions. Using Map-Elites, a prominent QD approach, we leverage its ability to evolve solutions across distinct regions of a behavioural space, which for APSP corresponds to all pairs of nodes in the graph. Our analysis rigorously demonstrates that evolutionary algorithms using Map-Elites efficiently compute shortest paths for all node pairs in parallel by exploiting synergies in the behavioural space. By appending edges to an existing shortest path, mutation can create optimal solutions in other regions of the behavioural space. Crossover is particularly effective, as it can combine optimal paths from two regions to produce an optimal path for a third region simply by concatenating two shortest paths. Finally, refining the parent selection to facilitate successful crossovers exhibits significant speed-ups compared to standard QD approaches.

PDF Details DOI

AIJ Journal 2024 Journal Article

Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation

Duc-Cuong Dang
Andre Opris
Dirk Sudholt

Evolutionary algorithms are popular algorithms for multi-objective optimisation (also called Pareto optimisation) as they use a population to store trade-offs between different objectives. Despite their popularity, the theoretical foundation of multi-objective evolutionary optimisation (EMO) is still in its early development. Fundamental questions such as the benefits of the crossover operator are still not fully understood. We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover: we propose classes of “royal road” functions on which these algorithms cover the whole Pareto front in expected polynomial time if crossover is being used. But when disabling crossover, they require exponential time in expectation to cover the Pareto front. The latter even holds for a large class of black-box algorithms using any elitist selection and any unbiased mutation operator. Moreover, even the expected time to create a single Pareto-optimal search point is exponential. We provide two different function classes, one tailored for one-point crossover and another one tailored for uniform crossover, and we show that some immune-inspired hypermutations cannot avoid exponential optimisation times. Our work shows the first example of an exponential performance gap through the use of crossover for the widely used NSGA-II algorithm and contributes to a deeper understanding of its limitations and capabilities.

Details DOI

AIJ Journal 2024 Journal Article

Self-adjusting offspring population sizes outperform fixed parameters on the cliff function

Mario Alejandro Hevia Fajardo
Dirk Sudholt

In the discrete domain, self-adjusting parameters of evolutionary algorithms (EAs) have emerged as a fruitful research area with many runtime analyses showing that self-adjusting parameters can outperform the best fixed parameters. Most existing runtime analyses focus on elitist EAs on simple problems, for which moderate performance gains were shown. Here we consider a much more challenging scenario: the multimodal function Cliff, defined as an example where a ( 1, λ ) EA is effective, and for which the best known upper runtime bound for standard EAs is O ( n 25 ). We prove that a ( 1, λ ) EA self-adjusting the offspring population size λ using success-based rules optimises Cliff in O ( n ) expected generations and O ( n log ⁡ n ) expected evaluations. Along the way, we prove tight upper and lower bounds on the runtime for fixed λ (up to a logarithmic factor) and identify the runtime for the best fixed λ as n η for η ≈ 3. 97677 (up to sub-polynomial factors). Hence, the self-adjusting ( 1, λ ) EA outperforms the best fixed parameter by a factor of at least n 2. 9767.

Details DOI

AAAI Conference 2023 Conference Paper

A Proof That Using Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation

Duc-Cuong Dang
Andre Opris
Bahare Salehi
Dirk Sudholt

Evolutionary algorithms are popular algorithms for multiobjective optimisation (also called Pareto optimisation) as they use a population to store trade-offs between different objectives. Despite their popularity, the theoretical foundation of multiobjective evolutionary optimisation (EMO) is still in its early development. Fundamental questions such as the benefits of the crossover operator are still not fully understood. We provide a theoretical analysis of well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover. We propose a class of problems on which these EMO algorithms using crossover find the Pareto set in expected polynomial time. In sharp contrast, they and many other EMO algorithms without crossover require exponential time to even find a single Pareto-optimal point. This is the first example of an exponential performance gap through the use of crossover for the widely used NSGA-II algorithm.

PDF Details DOI

TCS Journal 2023 Journal Article

Do additional target points speed up evolutionary algorithms?

Jakob Bossek
Dirk Sudholt

Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT ∪ S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT. We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions with polynomial expected optimisation times we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1, λ) EA on OneMax. However, for the one-dimensional Ising model the time to reach Hamming balls of radius ( 1 / 2 − ε ) n around optima does not reduce the asymptotic expected optimisation time in the worst case. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time.

Details DOI

AIJ Journal 2022 Journal Article

On the impact of the performance metric on efficient algorithm configuration

George T. Hall
Pietro S. Oliveto
Dirk Sudholt

Algorithm configurators are automated methods to optimise the parameters of an algorithm for a class of problems. We analyse the impact of the cutoff time κ (the time spent evaluating a configuration for a problem instance) on the expected number of configuration comparisons required to find the optimal parameter value for the performance metrics (the measure used to judge the performance of a configuration) that compare configurations using either the best-found fitness values or optimisation times. We first prove that the configurators that use optimisation time as performance metric are not able to tune any unary unbiased algorithm for any function with up to an exponential number of optima using κ ≤ ( n ln ⁡ n ) / 2. Afterwards, we show that for simple algorithm configuration scenarios the required cutoff time for the optimisation time metric may be considerably larger while using the best fitness metric allows the tuners to configure the target algorithm in linear time in the number of parameters.

Details DOI

TCS Journal 2020 Journal Article

Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation

Edgar Covantes Osuna
Wanru Gao
Frank Neumann
Dirk Sudholt

Parent selection in evolutionary algorithms for multi-objective optimisation is usually performed by dominance mechanisms or indicator functions that prefer non-dominated points. We propose to refine the parent selection on evolutionary multi-objective optimisation with diversity-based metrics. The aim is to focus on individuals with a high diversity contribution located in poorly explored areas of the search space, so the chances of creating new non-dominated individuals are better than in highly populated areas. We show by means of rigorous runtime analysis that the use of diversity-based parent selection mechanisms in the Simple Evolutionary Multi-objective Optimiser (SEMO) and Global SEMO for the well known bi-objective functions OneMinMax and LOTZ can significantly improve their performance. Our theoretical results are accompanied by experimental studies that show a correspondence between theory and empirical results and motivate further theoretical investigations in terms of stagnation. We show that stagnation might occur when favouring individuals with a high diversity contribution in the parent selection step and provide a discussion on which scheme to use for more complex problems based on our theoretical and experimental results.

Details DOI

AIJ Journal 2020 Journal Article

Memetic algorithms outperform evolutionary algorithms in multimodal optimisation

Phan Trung Hai Nguyen
Dirk Sudholt

Memetic algorithms integrate local search into an evolutionary algorithm to combine the advantages of rapid exploitation and global optimisation. We provide a rigorous runtime analysis of memetic algorithms on the Hurdle problem, a landscape class of tunable difficulty with a “big valley structure”, a characteristic feature of many hard combinatorial optimisation problems. A parameter called hurdle width describes the length of fitness valleys that need to be overcome. We show that the expected runtime of plain evolutionary algorithms like the (1+1) EA increases steeply with the hurdle width, yielding superpolynomial times to find the optimum, whereas a simple memetic algorithm, (1+1) MA, only needs polynomial expected time. Surprisingly, while increasing the hurdle width makes the problem harder for evolutionary algorithms, it becomes easier for memetic algorithms. We further give the first rigorous proof that crossover can decrease the expected runtime in memetic algorithms. A (2+1) MA using mutation, crossover and local search outperforms any other combination of these operators. Our results demonstrate the power of memetic algorithms for problems with big valley structures and the benefits of hybridising multiple search operators.

Details DOI

TCS Journal 2019 Journal Article

On the benefits and risks of using fitness sharing for multimodal optimisation

Pietro S. Oliveto
Dirk Sudholt
Christine Zarges

Fitness sharing is a well-known diversity mechanism inspired by the idea that individuals in the population that are close to each other have to share their fitnesses in a similar way to how species in nature occupying the same ecological environment have to share resources. Thus, by derating the fitness of close individuals one hopes to encourage the population to spread out more. Previous runtime analyses of fitness sharing studied a variant where selection was based on populations instead of individuals. We study the conventional fitness sharing mechanism based on individuals and use runtime analysis to highlight its benefits and dangers on the well-known bimodal test problem TwoMax, where diversity is crucial for finding both optima. In contrast to population-based sharing, a (2+1) evolutionary algorithm (EA) with conventional fitness sharing does not guarantee to find both optima in polynomial time even when problem specific knowledge is used to estimate the distance between individuals; however, a ( μ + 1 ) EA with μ ≥ 3 always succeeds in expected polynomial time. We further show theoretically and empirically that large offspring populations in ( μ + λ ) EA s can be detrimental as creating too many offspring in one particular area of the search space can make all individuals in this area go extinct. We conclude the paper with an empirical study indicating that similar conclusions may be drawn when using the genotypic distance that has to be relied upon when no problem specific knowledge is available.

Details DOI

TCS Journal 2015 Journal Article

Design and analysis of different alternating variable searches for search-based software testing

Joseph Kempka
Phil McMinn
Dirk Sudholt

Manual software testing is a notoriously expensive part of the software development process, and its automation is of high concern. One aspect of the testing process is the automatic generation of test inputs. This paper studies the Alternating Variable Method (AVM) approach to search-based test input generation. The AVM has been shown to be an effective and efficient means of generating branch-covering inputs for procedural programs. However, there has been little work that has sought to analyse the technique and further improve its performance. This paper proposes two different local searches that may be used in conjunction with the AVM, Geometric and Lattice Search. A theoretical runtime analysis proves that under certain conditions, the use of these searches results in better performance compared to the original AVM. These theoretical results are confirmed by an empirical study with five programs, which shows that increases of speed of over 50% are possible in practice.

Details DOI

TCS Journal 2014 Journal Article

Analysis of speedups in parallel evolutionary algorithms and ( 1 + λ ) EAs for combinatorial optimization

Jörg Lässig
Dirk Sudholt

Evolutionary algorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected by a graph structure as communication topology. Each island periodically communicates copies of good solutions to neighboring islands in a process called migration. We consider the speedup gained by island models in terms of the parallel running time for problems from combinatorial optimization: sorting (as maximization of sortedness), shortest paths and Eulerian cycles. The results show in which settings and up to what degree evolutionary algorithms can be parallelized efficiently. Our results include offspring populations in ( 1 + λ ) EAs as a special case. Potential speedups depend on many design choices such as the search operators, representations and fitness functions used on the islands, and also the parameters of the island model. In particular, we show that a natural instance for Eulerian cycles leads to exponential vs. logarithmic speedups, depending on the frequency of migration.

Details DOI

TCS Journal 2014 Journal Article

The choice of the offspring population size in the ( 1, λ ) evolutionary algorithm

Jonathan E. Rowe
Dirk Sudholt

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the ( 1, λ ) EA. We establish a sharp threshold at λ = log e e − 1 n ≈ 5 log 10 n between exponential and polynomial running times on OneMax. For any smaller value, the ( 1, λ ) EA needs exponential time on every function that has only one global optimum. We also consider arbitrary unimodal functions and show that the threshold can shift towards larger offspring population sizes. In particular, for the function LeadingOnes there is a sharp threshold at λ = 2 log e e − 1 n ≈ 10 log 10 n. Finally, we investigate the relationship between the offspring population size and arbitrary mutation rates on OneMax. We get sharp thresholds for λ that decrease with the mutation rate. This illustrates the balance between selection and mutation.

Details DOI

TCS Journal 2011 Journal Article

Runtime analysis of the 1-ANT ant colony optimizer

Benjamin Doerr
Frank Neumann
Dirk Sudholt
Carsten Witt

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. First runtime analyses of ant colony optimization (ACO) have been conducted only recently. In these studies simple ACO algorithms such as the 1-ANT are investigated. The influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w. r. t. the runtime behavior have been determined for the example function OneMax. This work puts forward the rigorous runtime analysis of the 1-ANT on the example functions LeadingOnes and BinVal. With respect to Evolutionary Algorithms (EAs), such analyses were essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice has a crucial impact on the runtime. Moreover, the analyses provide insight into the working principles of ACO algorithms. Our theoretical results are accompanied by experimental results that give us a more detailed impression of the 1-ANT’s performance. Furthermore, the experiments also deal with the question whether using many ant solutions in one iteration can decrease the total runtime.

Details DOI

TCS Journal 2010 Journal Article

A self-stabilizing algorithm for cut problems in synchronous networks

Thomas Sauerwald
Dirk Sudholt

Consider a synchronized distributed system where each node can only observe the state of its neighbors. Such a system is called self-stabilizing if it reaches a stable global state in a finite number of rounds. Allowing two different states for each node induces a cut in the graph. In each round, every node decides whether it is (locally) satisfied with the current cut. Afterwards all unsatisfied nodes change sides independently with a fixed probability p. Using different notions of satisfaction enables the computation of maximal and minimal cuts, respectively. We analyze the expected time until such cuts are reached on several graph classes and study the impact of the parameter p and the initial cut.

Details DOI

TCS Journal 2010 Journal Article

Runtime analysis of a binary particle swarm optimizer

Dirk Sudholt
Carsten Witt

We investigate the runtime of a binary Particle Swarm Optimizer (PSO) for optimizing pseudo-Boolean functions f: { 0, 1 } n → R. The binary PSO maintains a swarm of particles searching for good solutions. Each particle consists of a current position from { 0, 1 } n, its own best position and a velocity vector used in a probabilistic process to update its current position. The velocities for a particle are then updated in the direction of its own best position and the position of the best particle in the swarm. We present a lower bound for the time needed to optimize any pseudo-Boolean function with a unique optimum. To prove upper bounds we transfer a fitness-level argument that is well-established for evolutionary algorithms (EAs) to PSO. This method is applied to estimate the expected runtime for the class of unimodal functions. A simple variant of the binary PSO is considered in more detail for the test function OneMax, showing that there the binary PSO is competitive to EAs. An additional experimental comparison reveals further insights.

Details DOI

TCS Journal 2009 Journal Article

The impact of parametrization in memetic evolutionary algorithms

Dirk Sudholt

Memetic (evolutionary) algorithms integrate local search into the search process of evolutionary algorithms. As computational resources have to be spread adequately among local and evolutionary search, one has to care about when to apply local search and how much computational effort to devote to local search. Often local search is called with a fixed frequency and run for a fixed number of iterations, the local search depth. There is empirical evidence that these parameters have a significant impact on performance, but a theoretical understanding as well as concrete design guidelines are missing. We initiate the rigorous theoretical analysis of memetic algorithms. To this end, we consider a simple memetic algorithm for pseudo-Boolean optimization that captures basic working principles of memetic algorithms—the interplay of genetic operators like mutation and selection with local search. We present function classes where even small changes of the parametrization have a strong impact on performance. For almost every reasonable parameter setting we construct a function that, with high probability, can be optimized in polynomial time. However, changing the local search depth by a small additive term in any direction yields a superpolynomial optimization time, with high probability. For another class of functions altering the local search frequency by a factor of 2 even yields exponential optimization times. Our results show exemplarily that parametrizing memetic evolutionary algorithms can be extremely hard. Moreover, this work yields insights into the dynamic behavior of memetic algorithms and contributes to a theoretical foundation of hybrid metaheuristics.

Details DOI