Dr Dirk Sudholt
PhD
Department of Computer Science
Visiting Professor
 Profile

Until September 2020 I was a Senior Lecturer at the University of Sheffield in the Department of Computer Science, heading the newly established Algorithms research group. Before coming to Sheffield, I obtained my Diploma and my Ph.D. from the Technische Universität Dortmund under the supervision of Prof. Ingo Wegener.
I have held postdoc positions at the International Computer Science Institute (ICSI) in Berkeley, California, in the group of Prof. Richard M. Karp as well as the University of Birmingham, working with Prof. Xin Yao in the SEBASE project.
 Research interests

I am interested in randomised algorithms, algorithmic analysis, and combinatorial optimisation. My main expertise is the analysis of bioinspired search heuristics such as evolutionary algorithms, ant colony optimisation, particle swarm optimisation as well as hybrid and parallel variants thereof.
I am interested in rigorous analyses of their optimisation time: the expected time until a search heuristic finds a satisfactory solution for an interesting problem.Such studies give insight into the working principles of bioinspired search heuristics.
They tell us how effective these metaheuristics are in comparison to problemspecific algorithms and how design choices such as the choice of operators and parameters affect performance. This helps practitioners to make informed design choices and contributes to a rigorous theoretical foundation of metaheuristics.
 Publications

Journal articles
 Memetic algorithms outperform evolutionary algorithms in multimodal optimisation. Artificial Intelligence, 287. View this article in WRRO
 Analysing the robustness of evolutionary algorithms to noise : refined runtime bounds and an example where noise is beneficial. Algorithmica. View this article in WRRO
 Analysis of the performance of algorithm configurators for search heuristics with global mutation operators. Proceedings of the 2020 Genetic and Evolutionary Computation Conference.
 Parallel blackbox complexity with tail bounds. IEEE Transactions on Evolutionary Computation. View this article in WRRO
 On the benefits and risks of using fitness sharing for multimodal optimisation. Theoretical Computer Science, 773, 5370. View this article in WRRO
 Runtime Analysis of Crowding Mechanisms for Multimodal Optimisation. IEEE Transactions on Evolutionary Computation. View this article in WRRO
 On the Choice of the Update Strength in EstimationofDistribution Algorithms and Ant Colony Optimization. Algorithmica, 81(4), 14501489. View this article in WRRO
 On the Analysis of TrajectoryBased Search Algorithms: When is it Beneficial to Reject Improvements?. Algorithmica, 81(2), 858885. View this article in WRRO
 Preface to the Special Issue on Theory of Genetic and Evolutionary Computation. Algorithmica, 81(2), 589592.
 Design and Analysis of DiversityBased Parent Selection Schemes for Speeding Up Evolutionary Multiobjective Optimisation. Theoretical Computer Science. View this article in WRRO
 On the Runtime Analysis of the Clearing DiversityPreserving Mechanism. Evolutionary Computation. View this article in WRRO
 Preface to the Special Issue on Theory of Genetic and Evolutionary Computation. Algorithmica, 14.
 How to Escape Local Optima in Black Box Optimisation: When Nonelitism Outperforms Elitism. Algorithmica. View this article in WRRO
 Escaping Local Optima Using Crossover with Emergent Diversity. IEEE Transactions on Evolutionary Computation, 22(3), 484497. View this article in WRRO
 Towards a Runtime Comparison of Natural and Artificial Evolution. Algorithmica, 78(2), 681713. View this article in WRRO
 On Easiest Functions for Mutation Operators in BioInspired Optimisation. Algorithmica, 78(2), 714740. View this article in WRRO
 How Crossover Speeds up Building Block Assembly in Genetic Algorithms. Evolutionary Computation, 25(2), 237274. View this article in WRRO
 Selection limits to adaptive walks on correlated landscapes. Genetics, 205(2), 803825. View this article in WRRO
 Principled Design and Runtime Analysis of Abstract Convex Evolutionary Search. Evolutionary Computation, 25(2), 205236. View this article in WRRO
 Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem. Evolutionary Computation, 25(4), 673705. View this article in WRRO
 Design and Analysis of Schemes for Adapting Migration Intervals in Parallel Evolutionary Algorithms. Evolutionary Computation, 23(4), 559582. View this article in WRRO
 Design and analysis of different alternating variable searches for searchbased software testing. Theoretical Computer Science, 605, 120. View this article in WRRO
 Toward a unifying framework for evolutionary processes. Journal of Theoretical Biology, 383, 2843. View this article in WRRO
 Analysis of Speedups in Parallel Evolutionary Algorithms and (1+lambda) EAs for Combinatorial Optimization. Theoretical Computer Science, 551, 6683.
 General Upper Bounds on the Runtime of Parallel Evolutionary Algorithms. Evolutionary Computation, 22(3), 405437. View this article in WRRO
 Improved evolutionary algorithm design for the project scheduling problem based on runtime analysis. IEEE Transactions on Software Engineering, 40(1), 83102.
 Mutation rate matters even when optimizing monotonic functions. Evolutionary Computation, 21(1), 127.
 The choice of the offspring population size in the (1, λ) evolutionary algorithm. Theoretical Computer Science.
 When do evolutionary algorithms optimize separable functions in parallel?. FOGA 2013  Proceedings of the 12th ACM Workshop on Foundations of Genetic Algorithms, 5163.
 Design and analysis of migration in parallel evolutionary algorithms. Soft Computing, 17(7), 11211144.
 Running time analysis of ant colony optimization for shortest path problems. Journal of Discrete Algorithms, 10(1), 165180.
 A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems. Algorithmica (New York), 130.
 A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms. CoRR, abs/1109.1504.
 Runtime analysis of the 1ANT ant colony optimizer. Theoretical Computer Science, 412(17), 16291644.
 Hybridizing evolutionary algorithms with variabledepth search to overcome local optima. Algorithmica (New York), 59(3), 343368.
 Running time analysis of Ant Colony Optimization for shortest path problems. Journal of Discrete Algorithms.
 Runtime analysis of a binary particle swarm optimizer. THEORETICAL COMPUTER SCIENCE, 411(21), 20842100.
 Analysis of an Asymmetric Mutation Operator. EVOLUTIONARY COMPUTATION, 18(1), 126.
 A selfstabilizing algorithm for cut problems in synchronous networks. Theoretical Computer Science, 411(1415), 15991612.
 Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intelligence, 3(1), 3568.
 The impact of parametrization in memetic evolutionary algorithms. Theoretical Computer Science, 410(26), 25112528.
 Analysis of diversitypreserving mechanisms for global exploration.. Evol Comput, 17(4), 455476.
Chapters
 The Benefits of Population Diversity in Evolutionary Algorithms: A Survey of Rigorous Runtime Analyses, Natural Computing Series (pp. 359404). Springer International Publishing
 Parallel Evolutionary Algorithms, Springer Handbook of Computational Intelligence (pp. 929959). Springer Berlin Heidelberg
 Parallel Evolutionary Algorithms In Kacprzyk J & Pedrycz W (Ed.), Handbook of Computational Intelligence (pp. 929959). Springer
 Parametrization and balancing local and global search (pp. 5572).
 Memetic Evolutionary Algorithms In Auger A & Doerr B (Ed.), Theory of Randomized Search Heuristics (pp. 141169). World Scientific Publishing Company
 Computational complexity of ant colony optimization and its hybridization with local search (pp. 91120).
Conference proceedings papers
 A tight lower bound on the expected runtime of standard steady state genetic algorithms. Proceedings of the 2020 Genetic and Evolutionary Computation Conference View this article in WRRO
 Do sophisticated evolutionary algorithms perform better than simple ones?. Proceedings of the 2020 Genetic and Evolutionary Computation Conference View this article in WRRO
 Causes and effects of fitness landscapes in unit test generation. Proceedings of the 2020 Genetic and Evolutionary Computation Conference View this article in WRRO
 On the choice of the parameter control mechanism in the (1+( λ, λ )) genetic algorithm. Proceedings of the 2020 Genetic and Evolutionary Computation Conference View this article in WRRO
 More effective randomized search heuristics for graph coloring through dynamic optimization. Proceedings of the 2020 Genetic and Evolutionary Computation Conference View this article in WRRO
 Runtime analysis of randomized search heuristics for dynamic graph coloring. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 19). Prague, Czech Republic, 13 July 2019  17 July 2019. View this article in WRRO
 On the impact of the cutoff time on the performance of algorithm configurators. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2019). Prague, Czech Republic, 13 July 2019  17 July 2019. View this article in WRRO
 Time complexity analysis of RLS and (1 + 1) EA for the edge coloring problem. Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms  FOGA '19, 27 August 2019  29 August 2019. View this article in WRRO
 Empirical analysis of diversitypreserving mechanisms on example landscapes for multimodal optimisation. Parallel Problem Solving from Nature – PPSN XV, Vol. 11102 LNCS (pp 207219), 8 September 2018  12 September 2018. View this article in WRRO
 Memetic Algorithms Beat Evolutionary Algorithms on the Class of Hurdle Problems. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) View this article in WRRO
 Medium Step Sizes are Harmful for the Compact Genetic Algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) (pp 14991506), 15 July 2018  19 July 2018. View this article in WRRO
 On the Robustness of Evolutionary Algorithms to Noise: Refined Results and an Example Where Noise Helps. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) View this article in WRRO
 Runtime Analysis of Probabilistic Crowding and Restricted Tournament Selection for Bimodal Optimisation. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) View this article in WRRO
 Theory of swarm intelligence. Proceedings of the Genetic and Evolutionary Computation Conference Companion
 Speeding Up Evolutionary Multiobjective Optimisation Through DiversityBased Parent Selection. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 17) (pp 553560), 15 July 2017  19 July 2017. View this article in WRRO
 Theoretical results on betandrun as an initialisation strategy. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 17) (pp 857864), 15 July 2017  19 July 2017. View this article in WRRO
 When is it Beneficial to Reject Improvements?. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 17) (pp 13911398), 15 July 2017  19 July 2017. View this article in WRRO
 FOGA 2017 chairs' welcome. FOGA 2017  Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (pp iii)
 Analysis of the Clearing DiversityPreserving Mechanism. 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '17), 12 January 2017  15 January 2017. View this article in WRRO
 Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms. Parallel Problem Solving from Nature – PPSN XIV View this article in WRRO
 Theory of Swarm Intelligence. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion  GECCO '16 Companion, 20 July 2016  24 July 2016.
 When NonElitism Outperforms Elitism for Crossing Fitness Valleys. GECCO '16 Proceedings of the Genetic and Evolutionary Computation Conference 2016 (pp 11631170), 20 July 2016  24 July 2016. View this article in WRRO
 Escaping Local Optima with Diversity Mechanisms and Crossover. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference  GECCO '16, 20 July 2016  24 July 2016.
 Update Strength in EDAs and ACO. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference  GECCO '16, 20 July 2016  24 July 2016.
 Runtime Analysis for the Parameterless Population Pyramid. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference  GECCO '16, 20 July 2016  24 July 2016.
 Tutorials at PPSN 2016 (pp 10121022)
 First Steps Towards a Runtime Comparison of Natural and Artificial Evolution. Proceedings of the 2015 on Genetic and Evolutionary Computation Conference  GECCO '15, 11 July 2015  15 July 2015.
 Blackbox Complexity of Parallel Search with Distributed Populations. Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII  FOGA '15, 17 January 2015  22 January 2015.
 On Easiest Functions for Somatic Contiguous Hypermutations And Standard Bit Mutations. Proceedings of the 2015 on Genetic and Evolutionary Computation Conference  GECCO '15, 11 July 2015  15 July 2015.
 A fixed budget analysis of randomized search heuristics for the traveling salesperson problem. Proceedings of the 2014 conference on Genetic and evolutionary computation  GECCO '14, 12 July 2014  16 July 2014.
 On the runtime analysis of stochastic ageing mechanisms. Proceedings of the 2014 conference on Genetic and evolutionary computation  GECCO '14, 12 July 2014  16 July 2014.
 Design and analysis of adaptive migration intervals in parallel evolutionary algorithms. Proceedings of the 2014 conference on Genetic and evolutionary computation  GECCO '14, 12 July 2014  16 July 2014.
 Theory of swarm intelligence. Proceedings of the 2014 conference companion on Genetic and evolutionary computation companion  GECCO Comp '14, 12 July 2014  16 July 2014.
 Unbiased BlackBox Complexity of Parallel Search (pp 892901)
 On the Runtime Analysis of Fitness Sharing Mechanisms (pp 932941)
 A theoretical runtime and empirical analysis of different alternating variable searches for searchbased testing. Genetic and Evolutionary Computation Conference (GECCO 2013) (pp 14451452). Amsterdam, 6 July 2013  10 July 2013.
 Homogeneous and heterogeneous island models for the set cover problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 7491 LNCS(PART 1) (pp 1120)
 Crossover speeds up buildingblock assembly. GECCO'12  Proceedings of the 14th International Conference on Genetic and Evolutionary Computation (pp 689696)
 Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design. GECCO'12  Proceedings of the 14th International Conference on Genetic and Evolutionary Computation (pp 12211228)
 The choice of the offspring population size in the (1,λ) EA. GECCO'12  Proceedings of the 14th International Conference on Genetic and Evolutionary Computation (pp 13491356)
 Runtime analysis of convex evolutionary search. GECCO'12  Proceedings of the 14th International Conference on Genetic and Evolutionary Computation (pp 649656)
 General Upper Bounds on the Running Time of Parallel Evolutionary Algorithms. CoRR, Vol. abs/1206.3522
 Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization  (Extended Abstract).. ISAAC, Vol. 7074 (pp 405414)
 How crossover helps in PseudoBoolean optimization. Genetic and Evolutionary Computation Conference, GECCO'11 (pp 989996)
 On the effectiveness of crossover for migration in parallel evolutionary algorithms. Genetic and Evolutionary Computation Conference, GECCO'11 (pp 15871594)
 Analysis of speedups in parallel evolutionary algorithms for combinatorial optimization (Extended abstract). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 7074 LNCS (pp 405414)
 Using Markovchain mixing time estimates for the analysis of ant colony optimization. FOGA'11  Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI (pp 139150)
 Adaptive population models for offspring populations and parallel evolutionary algorithms. FOGA'11  Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI (pp 181192)
 Simple maxmin ant systems and the optimization of linear pseudoBoolean functions. FOGA'11  Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI (pp 209218)
 Simple MaxMin Ant Systems and the Optimization of Linear PseudoBoolean Functions. CoRR, Vol. abs/1007.4707
 General Lower Bounds for the Running Time of Evolutionary Algorithms. PARALLEL PROBLEMS SOLVING FROM NATURE  PPSN XI, PT I, Vol. 6238 (pp 124133)
 Optimizing Monotone Functions Can Be Difficult.. PPSN (1), Vol. 6238 (pp 4251)
 General Lower Bounds for the Running Time of Evolutionary Algorithms.. PPSN (1), Vol. 6238 (pp 124133)
 The benefit of migration in parallel evolutionary algorithms.. GECCO (pp 11051112)
 A few ants are enough: ACO with iterationbest update.. GECCO (pp 6370)
 Experimental Supplements to the Theoretical Analysis of Migration in the Island Model. PARALLEL PROBLEMS SOLVING FROM NATURE  PPSN XI, PT I, Vol. 6238 (pp 224233)
 General Scheme for Analyzing Running Times of Parallel Evolutionary Algorithms. PARALLEL PROBLEMS SOLVING FROM NATURE  PPSN XI, PT I, Vol. 6238 (pp 234243)
 Analysis of an iterated local search algorithm for vertex coloring. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 6506 LNCS(PART 1) (pp 340352)
 Optimizing monotone functions can be difficult. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 6238 LNCS(PART 1) (pp 4251)
 Ant Colony Optimization for stochastic shortest path problems. Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10 (pp 14651472)
 Running time analysis of ACO systems for shortest path problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 5752 LNCS (pp 7691)
 Rigorous analyses for the combination of ant colony optimization and local search. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 5217 LNCS (pp 132143)
 Selfstabilizing cuts in synchronous networks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 5058 LNCS (pp 234246)
 Memetic algorithms with variabledepth search to overcome local optima. GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008 (pp 787794)
 Runtime analysis of binary PSO. GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008 (pp 135142)
 Theoretical analysis of diversity mechanisms for global exploration. GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008 (pp 945952)
 On the runtime analysis of the 1ANT ACO algorithm. Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference (pp 3340)
 Comparing variants of MMAS ACO algorithms on pseudoboolean functions. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4638 LNCS (pp 6175)
 On the analysis of the (1+1) memetic algorithm. GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2 (pp 493500)
 Local search in evolutionary algorithms: The impact of the local search frequency. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4288 LNCS (pp 359368)
 Design and analysis of an asymmetric mutation operator. 2005 IEEE Congress on Evolutionary Computation, IEEE CEC 2005. Proceedings, Vol. 1 (pp 190197)
 Crossover is probably essential for the ising model on trees. GECCO 2005  Genetic and Evolutionary Computation Conference (pp 11611167)
 Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 3242 (pp 2130)
 The ising model: Simple evolutionary algorithms as adaptation schemes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 3242 (pp 3140)
 View this article in WRRO Fast Perturbative Algorithm Configurators. Parallel Problem Solving from Nature
 View this article in WRRO Analysis of the Performance of Algorithm Configurators for Search Heuristics with Global Mutation Operators. Proceedings of the Genetic and Evolutionary Computation Conference
Reports
 Adaptive Population Models for Offspring Populations and Parallel Evolutionary Algorithms
 Memetic Algorithms: Parametrization and Balancing Local and Global Search
Theses / Dissertations
Other
 Theory of swarm intelligence.. GECCO (Companion), 12151238.
 Theory of swarm intelligence. Genetic and Evolutionary Computation Conference, GECCO'11  Companion Publication, 13811410.
 Grants

SAGE: Speed of Adaptation in Population Genetics and Evolutionary, EUROPEAN COMMISSION  FP6/FP7, 01/2014 to 12/2016, £262,874, as PI