This file was created by the TYPO3 extension publications --- Timezone: CEST Creation date: 2024-03-28 Creation time: 17:03:11 --- Number of references 134 inbook JohannesLenglerandAndreOprisandDirkSudholt. Analysing Equilibrium States for Population Diversity 1 2023 1 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2023) ACM Johannes Lengler Andre Opris Dirk Sudholt inbook DucCuongDangandAndreOprisandBahareSalehiandDirkSudholt. Analysing the Robustness of NSGA-II under Noise 2023 1 Duc-Cuong Dang Andre Opris Bahare Salehi Dirk Sudholt inbook JoostJorritsmaandJohannesLenglerandDirkSudholt. Comma Selection Outperform Plus Selection on OneMax with Randomly Planted Optima 2023 1 Joost Jorritsma Johannes Lengler Dirk Sudholt article Bossek. Do additional target points speed up evolutionary algorithms? 2023 1 03043975 10.1016/j.tcs.2023.113757 Theoretical Computer Science 950 113757 Jakob Bossek Dirk Sudholt inbook JakobBossekandDirkSudholt. Runtime Analysis of Quality Diversity Algorithms 2023 1 Jakob Bossek Dirk Sudholt book Kneissl. The Cost of Randomness in Evolutionary Algorithms: Crossover can Save Random Bits 2023 1 10.1007/978-3-031-30035-6\textunderscore 12 13987 Carlo Kneissl Dirk Sudholt article VijayDhanjibhaiBhuva. Evolutionary Algorithms for Cardinality-Constrained Ising Models 2022 1 10.1007/978-3-031-14721-0$\backslash$\textunderscore 32 Vijay Dhanjibhai Bhuva Duc-Cuong Dang Liam Huber Dirk Sudholt article Fajardo. Hard problems are easier for success-based parameter control 2022 1 10.1145/3512290.3528781 796-804 Mario Alejandro Hevia Fajardo Dirk Sudholt article On the impact of the performance metric on efficient algorithm configuration 2022 11 08 1 1. https://www.sciencedirect.com/science/article/abs/pii/S0004370221001806 George T. Hall Dirk Sudholt Pietro S. Oliveto article CovantesOsuna2021 Runtime Analysis of Restricted Tournament Selection for Bimodal Optimisation 2022 1 Evolutionary Computation MIT Press Edgar Covantes Osuna Dirk Sudholt article Neumann. The compact genetic algorithm struggles on Cliff functions 2022 1 10.1145/3512290.3528776 1426-1433 Frank Neumann Dirk Sudholt Carsten Witt article HeviaFajardo. Theoretical and Empirical Analysis of Parameter Control Mechanisms in the (1 + (\textgreekl, \textgreekl)) Genetic Algorithm 2022 1 2688-299X 10.1145/3564755 ACM Transactions on Evolutionary Learning and Optimization 2 1-39 4 Mario Alejandro Hevia Fajardo Dirk Sudholt article Sudholt. Theory and practice of population diversity in evolutionary computation 2022 1 10.1145/3377929.3389892 975-992 Dirk Sudholt Giovanni Squillero article Tight Bounds on the Expected Runtime of a Standard Steady State Genetic Algorithm", Algorithmica 2022 1 Pietro S. Oliveto Dirk Sudholt Carsten Witt article Sudholt2020 Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial 2021 1 Algorithmica 83 976-1011 4 https://doi.org/10.1007/s00453-020-00671-0 Dirk Sudholt inproceedings Bossek.09062021 Do additional optima speed up evolutionary algorithms? 2021 1 9781450383523 10.1145/3450218.3477309 Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms ACM
New York, NY, USA
Finck, Steffen and Hellwig, Michael and Oliveto, Pietro S. 1--11 Jakob Bossek Dirk Sudholt
inproceedings Fajardo.09062021 Self-adjusting offspring population sizes outperform fixed parameters on the cliff function 2021 9781450383523 10.1145/3450218.3477306 Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms ACM
New York, NY, USA
Finck, Steffen and Hellwig, Michael and Oliveto, Pietro S. 1--15 Mario Alejandro Hevia Fajardo Dirk Sudholt
inproceedings Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms: Why Success Rates Matter 1 2021 1 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2021) ACM Mario Alejandro Hevia Fajardo Dirk Sudholt article The Complex Parameter Landscape of the Compact Genetic Algorithm 2021 1 Algorithmica 83 1096-1137 4 https://rdcu.be/b9KBR Johannes Lengler Dirk Sudholt Carsten Witt article Bossek.2021 Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem 2021 10.1007/s00453-021-00838-3 Algorithmica Jakob Bossek Frank Neumann Pan Peng Dirk Sudholt inproceedings Oliveto2020 A Tight Lower Bound on the Expected Runtime of Standard Steady State Genetic Algorithms 2020 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020) ACM 1323-1331 https://doi.org/10.1145/3377930.3390212 Pietro S. Oliveto Dirk Sudholt Carsten Witt inproceedings Hall2020 Analysis of the Performance of Algorithm Configurators for Search Heuristics with Global Mutation Operators 2020 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020) ACM 823-831 https://doi.org/10.1145/3377930.3390218 George T. Hall Pietro S. Oliveto Dirk Sudholt inproceedings Albunian2020 Causes and Effects of Fitness Landscapes in Unit Test Generation 2020 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020) ACM 1204-1212 https://doi.org/10.1145/3377930.3390194 Nasser Albunian Gordon Fraser Dirk Sudholt article Covantes2018b Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation 2020 Theoretical Computer Science 832 123-142 https://authors.elsevier.com/c/1b6NN15DaHylEh Edgar Covantes Osuna Wanru Gao Frank Neumann Dirk Sudholt inproceedings Foster2020 Do Sophisticated Evolutionary Algorithms Perform Better than Simple Ones? 2020 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020) ACM 184-192 https://doi.org/10.1145/3377930.3389830 Michael Foster Matthew Hughes George O'Brien Pietro S. Oliveto James Pyle Dirk Sudholt James Williams inproceedings Hall2020a Fast Perturbative Algorithm Configurators 2020 Parallel Problem Solving from Nature (PPSN 2020) 19--32 https://doi.org/10.1007/978-3-030-58112-1_2 George T. Hall Pietro S. Oliveto Dirk Sudholt inproceedings Albunian2020a Measuring and Maintaining Population Diversity in Search-based Unit Test Generation 2020 Proceedings of the 12th Symposium on Search-Based Software Engineering (SSBSE 2020) 153--168 https://doi.org/10.1007/978-3-030-59762-7_11 Nasser Albunian Gordon Fraser Dirk Sudholt article Nguyen2019 Memetic Algorithms Outperform Evolutionary Algorithms in Multimodal Optimisation 2020 1 Artificial Intelligence 287 103345 https://doi.org/10.1016/j.artint.2020.103345 Phan Trung Hai Nguyen Dirk Sudholt inproceedings Bossek2020 More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization 2020 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020) ACM 1277-1285 https://doi.org/10.1145/3377930.3390174 Jakob Bossek Frank Neumann Pan Peng Dirk Sudholt inproceedings Hevia2020 On the Choice of the Parameter Control Mechanism in the(1+(λ,λ)) Genetic Algorithm 2020 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020) ACM 832-840 https://doi.org/10.1145/3377930.3390200 Mario Alejandro Hevia Fajardo Dirk Sudholt article Lehre2019 Parallel Black-Box Complexity with Tail Bounds 2020 1 IEEE Transactions on Evolutionary Computation 24 1010-1024 6 https://doi.org/10.1109/TEVC.2019.2954234 Per Kristian Lehre Dirk Sudholt article Covantes2019 Runtime Analysis of Crowding Mechanisms for Multimodal Optimisation 2020 IEEE Transactions on Evolutionary Computation 24 581--592 3 https://doi.org/10.1109/TEVC.2019.2914606 Edgar Covantes Osuna Dirk Sudholt incollection Sudholt2018 The Benefits of Population Diversity in Evolutionary Algorithms: A Survey of Rigorous Runtime Analyses 2020 Theory of Evolutionary Computation: Recent Developments in Discrete Optimization Springer Benjamin Doerr and Frank Neumann https://link.springer.com/chapter/10.1007/978-3-030-29414-4_8 Dirk Sudholt article Sudholt.b Theory and practice of population diversity in evolutionary computation 2020 1 10.1145/3520304.3533642 1469-1486 Dirk Sudholt Giovanni Squillero article Nallaperuma2018 On the Analysis of Trajectory-Based Search Algorithms: When is it Beneficial to Reject Improvements? 2019 Algorithmica 81 858--885 2 https://doi.org/10.1007/s00453-018-0462-1 Samadhi Nallaperuma Pietro S. Oliveto Jorge Pérez Heredia Dirk Sudholt article Oliveto2018 On the Benefits and Risks of Using Fitness Sharing for Multimodal Optimisation 2019 Theoretical Computer Science 773 53--70 https://doi.org/10.1016/j.tcs.2018.07.007 Pietro S. Oliveto Dirk Sudholt Christine Zarges article Sudholt2018b On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization 2019 Algorithmica 81 1450--1489 4 https://doi.org/10.1007/s00453-018-0480-z Dirk Sudholt Carsten Witt inproceedings Hall2019 On the Impact of the Cutoff Time on the Performance of Algorithm Configurators 2019 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2019) ACM 907--915 https://doi.org/10.1145/3321707.3321879 George T. Hall Pietro S. Oliveto Dirk Sudholt article Covantes2018a On the Runtime Analysis of the Clearing Diversity-Preserving Mechanism 2019 Evolutionary Computation 27 MIT Press 403-433 https://doi.org/10.1162/evco_a_00225 Edgar Covantes Osuna Dirk Sudholt article Kotzing. Preface to the Special Issue on Theory of Genetic and Evolutionary Computation 2019 1 0178-4617 10.1007/s00453-017-0379-0 Algorithmica 80 1575-1578 5 Timo Kötzing Dirk Sudholt inproceedings Bossek2019 Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring 2019 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2019) ACM 1443--1451 https://doi.org/10.1145/3321707.3321792 Jakob Bossek Frank Neumann Pan Peng Dirk Sudholt inproceedings Bossek2019a Time Complexity Analysis of RLS and (1+1)~EA for the Edge Coloring Problem 2019 Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2019) ACM 102--115 https://doi.org/10.1145/3299904.3340311 Jakob Bossek Dirk Sudholt inproceedings CovantesOsuna2018a Empirical Analysis of Diversity-preserving Mechanisms on Example Landscapes for Multimodal Optimisation 2018 Parallel Problem Solving from Nature (PPSN~'18) Springer 207--219 https://rdcu.be/bsfpE Edgar Covantes Osuna Dirk Sudholt article Dang2017 Escaping Local Optima Using Crossover with Emergent Diversity 2018 IEEE Transactions on Evolutionary Computation 22 IEEE 484--497 https://doi.org/10.1109/TEVC.2017.2724201 Duc-Cuong Dang Per Kristian Lehre Tobias Friedrich Timo Kötzing Martin S. Krejca Pietro S. Oliveto Dirk Sudholt Andrew M. Sutton article Oliveto2017 How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism 2018 Algorithmica 80 1604--1633 http://dx.doi.org/10.1007/s00453-017-0369-2 Pietro S. Oliveto Tiago Paixão Jorge Pérez Heredia Dirk Sudholt Barbora Trubenova inproceedings Lengler2018 Medium Step Sizes are Harmful for the Compact Genetic Algorithm 2018 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) ACM 1499--1506 https://doi.org/10.1145/3205455.3205576 Johannes Lengler Dirk Sudholt Carsten Witt inproceedings Nguyen2018 Memetic Algorithms Beat Evolutionary Algorithms on the Class of Hurdle Problems 2018 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) ACM 1071--1078 https://doi.org/10.1145/3205455.3205456 Phan Trung Hai Nguyen Dirk Sudholt inproceedings Sudholt2018a On the Robustness of Evolutionary Algorithms to Noise: Refined Results and an Example Where Noise Helps 2018 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) ACM 1523--1530 https://doi.org/10.1145/3205455.3205595 Dirk Sudholt article Doerr. Preface to the Special Issue on Theory of Genetic and Evolutionary Computation 2018 1 0178-4617 10.1007/s00453-018-00543-8 Algorithmica 81 589-592 2 Carola Doerr Dirk Sudholt inproceedings CovantesOsuna2018 Runtime Analysis of Probabilistic Crowding and Restricted Tournament Selection for Bimodal Optimisation 2018 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018) ACM 929--936 https://doi.org/10.1145/3205455.3205591 Nominiert für einen best paper award in der Kategorie \glqq{}Genetic Algorithms\grqq{}. Edgar Covantes Osuna Dirk Sudholt inproceedings CovantesOsuna2017 Analysis of the Clearing Diversity-Preserving Mechanism 2017 Proceedings of Foundations of Genetic Algorithms (FOGA 2017) ACM Press 55--63 https://doi.org/10.1145/3040718.3040731 Edgar Covantes Osuna Dirk Sudholt article Nallaperuma2017 Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem 2017 Evolutionary Computation 25 673--705 http://dx.doi.org/10.1162/EVCO_a_00199 Samadhi Nallaperuma Frank Neumann Dirk Sudholt article Sudholt2016 How Crossover Speeds Up Building-Block Assembly in Genetic Algorithms 2017 Evolutionary Computation 25 237-274 2 http://www.mitpressjournals.org/doi/abs/10.1162/EVCO_a_00171 Dirk Sudholt article Corus2017 On Easiest Functions for Mutation Operators in Bio-Inspired Optimisation 2017 Algorithmica 78 714--740 2 http://link.springer.com/article/10.1007/s00453-016-0201-4 Dogan Corus Jun He Thomas Jansen Pietro S. Oliveto Dirk Sudholt Christine Zarges article Moraglio2017 Principled Design and Runtime Analysis of Abstract Convex Evolutionary Search 2017 Evolutionary Computation 25 205--236 2 http://www.mitpressjournals.org/doi/abs/10.1162/EVCO_a_00169 Alberto Moraglio Dirk Sudholt article PerezHeredia2016 Selection Limits to Adaptive Walks on Correlated Landscapes Adaptation depends critically on the effects of new mutations and their dependency on the genetic background they occur in. These two factors can be summarized by the fitness landscape. However, it would require testing all mutations in all backgrounds, making the definition and analysis of fitness landscapes mostly inaccessible. Instead of postulating a particular fitness landscape, we address this problem by considering general classes of landscapes and calculating an upper limit for the time it takes for a population to reach a fitness peak, circumventing the need to have full knowledge about the fitness landscape. We analyse populations in the weak-mutation regime and characterize the conditions that enable them to quickly reach the fitness peak as a function of the number of sites under selection. We show that for additive landscapes there is a critical selection strength enabling populations to reach high fitness genotypes, regardless of the distribution of effects. This threshold scales with the number of sites under selection, effectively setting a limit to adaptation, and results from the inevitable increase in deleterious mutational pressure as the population adapts in a space of discrete genotypes. Furthermore, we show that for the class of all unimodal landscapes this condition is sufficient but not necessary for rapid adaptation, as in some highly epistatic landscapes the critical strength does not depend on the number of sites under selection, effectively removing this barrier to adaptation. 2017 10.1534/genetics.116.189340 Genetics 205 Genetics 803--825 2 http://www.genetics.org/content/early/2016/11/22/genetics.116.189340 Jorge Pérez Heredia Barbora Trubenova Dirk Sudholt Tiago Paixão inproceedings CovantesOsuna2017a Speeding Up Evolutionary Multi-objective Optimisation Through Diversity-based Parent Selection 2017 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2017) ACM 553--560 https://doi.org/10.1145/3071178.3080294 Edgar Covantes Osuna Wanru Gao Frank Neumann Dirk Sudholt inproceedings Lissovoi2017 Theoretical Results on Bet-and-run As an Initialisation Strategy 2017 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2017) ACM 857--864 https://doi.org/10.1145/3071178.3071329 Andrei Lissovoi Dirk Sudholt Markus Wagner Christine Zarges article Paixao2016 Towards a Runtime Comparison of Natural and Artificial Evolution Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1)?EA. We show that SSWM can have a moderate advantage over the (1+1)?EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1)?EA by taking advantage of information on the fitness gradient. 2017 Algorithmica 78 681--713 2 http://dx.doi.org/10.1007/s00453-016-0212-1 Tiago Paixão Jorge Pérez Heredia Dirk Sudholt Barbora Trubenova inproceedings Nallaperuma2017a When is It Beneficial to Reject Improvements? 2017 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2017) ACM 1391--1398 https://doi.org/10.1145/3071178.3071273 Samadhi Nallaperuma Pietro S. Oliveto Jorge Pérez Heredia Dirk Sudholt inproceedings Dang2016a Emergence of Diversity and Its Benefits for Crossover in Genetic Algorithms Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for a standard $\backslash$(($\backslash$mu+1)$\backslash$) GA and the $\backslash$(Jump\_k$\backslash$) test function. By studying the stochastic process underlying the size of the largest collection of identical genotypes we show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order $\backslash$(?mega(n/ $\backslash$log n)$\backslash$) compared to mutation-only algorithms like the $\backslash$((1+1)$\backslash$) EA. 2016 10.1007/978-3-319-45823-6_83 Proceedings of the 14th {{International Conference Parallel Problem Solving From Nature}} ({{PPSN}}) Springer sage-output http://dx.doi.org/10.1007/978-3-319-45823-6_83 Nominiert für den best paper award. Duc-Cuong Dang Per Kristian Lehre Tobias Friedrich Timo Kötzing Martin S. Krejca Pietro S. Oliveto Dirk Sudholt Andrew M. Sutton inproceedings Dang2016 Escaping Local Optima with Diversity-Mechanisms and Crossover 2016 Proceedings of the Genetic and Evolutionary Computation Conference ({GECCO} 2016) {ACM Press} 645--652 http://dx.doi.org/10.1145/2908812.2908956 Duc-Cuong Dang Tobias Friedrich Martin S. Krejca Timo Kötzing Per Kristian Lehre Pietro S. Oliveto Dirk Sudholt Andrew Michael Sutton inproceedings Goldman2016 Runtime Analysis for the Parameter-less Population Pyramid 2016 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016) ACM 669--676 http://dx.doi.org/10.1145/2908812.2908846 Brian W. Goldman Dirk Sudholt inproceedings Sudholt2016a Update Strength in EDAs and ACO: How to Avoid Genetic Drift 2016 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016) ACM 61--68 http://dx.doi.org/10.1145/2908812.2908867 Nominiert für einen best paper award in der Kategorie \glqq{}Ant Colony Optimization and Swarm Intelligence\grqq{}. Dirk Sudholt Carsten Witt inproceedings Oliveto2016 When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys 2016 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016) ACM 1163-1170 http://dx.doi.org/10.1145/2908812.2908909 Pietro S. Oliveto Tiago Paixão Jorge Pérez Heredia Dirk Sudholt Barbora Trubenova article paixao_unified_2015 A Unified Model of Evolutionary Processes 2015 Journal of Theoretical Biology 383 28--43 sage-output-soon http://dx.doi.org/10.1016/j.jtbi.2015.07.011 Unter den 5 meist heruntergeladenen Open-Access-Artikeln der Zeitschrift (23. 11. 2015). Tiago Paixão Golnaz Badkobeh Nick Barton Dogan Corus Duc-Cuong Dang Tobias Friedrich Per Kristian Lehre Dirk Sudholt Andrew M. Sutton Barbora Trubenova inproceedings Badkobeh2015 Black-box Complexity of Parallel Search with Distributed Populations 2015 Proceedings of Foundations of Genetic Algorithms (FOGA 2015) ACM Press 3--15 http://dx.doi.org/10.1145/2725494.2725504 Golnaz Badkobeh Per Kristian Lehre Dirk Sudholt article Kempka2015 Design and analysis of different alternating variable searches for search-based software testing 2015 Theoretical Computer Science 605 1--20 http://dx.doi.org/10.1016/j.tcs.2014.12.009 Joseph Kempka Phil McMinn Dirk Sudholt article mambrini_design_2015 Design and Analysis of Schemes for Adapting Migration Intervals in Parallel Evolutionary Algorithms 2015 Evolutionary Computation 23 559--582 sage-output-soon http://dx.doi.org/10.1162/EVCO_a_00153 Andrea Mambrini Dirk Sudholt inproceedings Paixao2015 First Steps Towards a Runtime Comparison of Natural and Artificial Evolution 2015 10.1145/2739480.2754758 Proceedings of the Genetic and {{Evolutionary Computation Conference}} ({{GECCO}} 2015) {ACM} 1455--1462 sage-output http://dx.doi.org/10.1145/2739480.2754758 Tiago Paixão Jorge Pérez Heredia Dirk Sudholt Barbora Trubenova inproceedings Corus2015 On Easiest Functions for Somatic Contiguous Hypermutations And Standard Bit Mutations 2015 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO~2015) ACM Press 1399--1406 http://dx.doi.org/10.1145/2739480.2754799 Dogan Corus Jun He Thomas Jansen Pietro S. Oliveto Dirk Sudholt Christine Zarges incollection Sudholt2012a Parallel Evolutionary Algorithms 2015 Handbook of Computational Intelligence Springer Janusz Kacprzyk and Witold Pedrycz 929--959 http://www.springer.com/engineering/computational+intelligence+and+complexity/book/978-3-662-43504-5 Eingeladener Beitrag. 6180+ Downloads am 7. 9. 2019 Dirk Sudholt inproceedings Nallaperuma2014 A Fixed Budget Analysis of Randomized Search Heuristics for the Traveling Salesperson Problem 2014 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2014) ACM Press 807--814 http://dx.doi.org/10.1145/2576768.2598302 Nominiert f?r einen best paper award in der Kategorie \glqq{}Genetic Algorithms\grqq{}. Samadhi Nallaperuma Frank Neumann Dirk Sudholt article Lassig2014 Analysis of speedups in parallel evolutionaryalgorithms and (1+λ)~EAs for combinatorialoptimization 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. 2014 10.1016/j.tcs.2014.06.037 Theoretical Computer Science 551 66--83 Combinatorial optimization, Island model, Offspring populations, Parallel evolutionary algorithms, runtime analysis, Spatial structures http://www.sciencedirect.com/science/article/pii/S0304397514004976 Jörg Lässig Dirk Sudholt inproceedings Mambrini2014 Design and Analysis of Adaptive Migration Intervals in Parallel Evolutionary Algorithms 2014 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2014) ACM Press 1047--1054 http://dx.doi.org/10.1145/2576768.2598347 Best paper award in der Kategorie \glqq{}Parallel Evolutionary Systems\grqq{}. Andrea Mambrini Dirk Sudholt article Lassig2013a General Upper Bounds on the Running Time of Parallel Evolutionary Algorithms 2014 Evolutionary Computation 22 MIT Press 405--437 3 http://dx.doi.org/10.1162/EVCO_a_00114 Jörg Lässig Dirk Sudholt article Minku2013 Improved Evolutionary Algorithm Design for the Project Scheduling Problem Based on Runtime Analysis 2014 IEEE Transactions on Software Engineering 40 83--102 1 http://dx.doi.org/10.1109/TSE.2013.52 Zweitmeist heruntergeladener Artikel der Zeitschrift im März 2014. Leandro L. Minku Dirk Sudholt Xin Yao inproceedings Oliveto2014a On the Runtime Analysis of Fitness Sharing Mechanisms 2014 13th International Conference on Parallel Problem Solving from Nature (PPSN 2014) 8672 Springer LNCS 932-941 http://dx.doi.org/10.1007/978-3-319-10762-2_92 Pietro S. Oliveto Dirk Sudholt Christine Zarges inproceedings Oliveto2014 On the Runtime Analysis of Stochastic Ageing Mechanisms 2014 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2014) ACM Press 113--120 http://dx.doi.org/10.1145/2576768.2598328 Best paper award in der Kategorie \glqq{}Artificial Immune Systems\grqq{}. Pietro S. Oliveto Dirk Sudholt article Rowe2013 The choice of the offspring population size in the(1,λ) evolutionary algorithm 2014 http://dx.doi.org/10.1016/j.tcs.2013.09.036 Theoretical Computer Science 545 20--38 http://www.sciencedirect.com/science/article/pii/S030439751300755X Jonathan E. Rowe Dirk Sudholt inproceedings Badkobeh2014 Unbiased Black-Box Complexity of Parallel Search 2014 13th International Conference on Parallel Problem Solving from Nature (PPSN 2014) 8672 Springer LNCS 892-901 http://dx.doi.org/10.1007/978-3-319-10762-2_88 Golnaz Badkobeh Per Kristian Lehre Dirk Sudholt article Sudholt2012c A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms 2013 IEEE Transactions on Evolutionary Computation 17 418-435 3 http://dx.doi.org/10.1109/TEVC.2012.2202241 Dirk Sudholt inproceedings Kempka2013 A Theoretical Runtime and Empirical Analysis of Different Alternating Variable Searches for Search-Based Testing 2013 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2013) ACM 1445--1452 http://dx.doi.org/10.1145/2463372.2463549 Joseph Kempka Phil McMinn Dirk Sudholt article Lassig2013 Design and Analysis of Migration in Parallel Evolutionary Algorithms 2013 Soft Computing 17 Springer 1121--1144 http://dx.doi.org/10.1007/s00500-013-0991-0 Sonderheft zum Thema \glqq{}Bio-inspired Algorithms with Structured Populations\grqq{} (Annahmequote 14%). Jörg Lässig Dirk Sudholt article monotone-journal Mutation Rate Matters Even When Optimizing Monotonic Functions 2013 Evolutionary Computation 21 1--21 1 http://www.mitpressjournals.org/doi/abs/10.1162/EVCO_a_00055 Benjamin Doerr Thomas Jansen Dirk Sudholt Carola Winzen Christine Zarges inproceedings Doerr2013 When Do Evolutionary Algorithms Optimize Separable Functions in Parallel? 2013 Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms (FOGA 2013) ACM 51--64 linear functions, pseudo-boolean optimization, runtime analysis, separable functions, theory http://dx.doi.org/10.1145/2460239.2460245 Benjamin Doerr Dirk Sudholt Carsten Witt article ant-stochastic-journal A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems 2012 Algorithmica 64 Springer 643--672 4 http://dx.doi.org/10.1007/s00453-011-9606-2 Dirk Sudholt Christian Thyssen inproceedings Sudholt2012 Crossover Speeds Up Building-Block Assembly 2012 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012) 689--696 http://dx.doi.org/10.1145/2330163.2330260 Nominiert für einen best paper award in der Kategorie \glqq{}Genetic Algorithms\grqq{}. Dirk Sudholt inproceedings Minku2012 Evolutionary Algorithms for the Project Scheduling Problem: Runtime Analysis and Improved Design 2012 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012) 1221--1228 http://dx.doi.org/10.1145/2330163.2330332 Leandro L. Minku Dirk Sudholt Xin Yao inproceedings Mambrini2012 Homogeneous and Heterogeneous Island Models for the Set Cover Problem 2012 Parallel Problem Solving from Nature (PPSN 2012) 7491 Springer LNCS 11--20 http://dx.doi.org/10.1007/978-3-642-32937-1_2 Andrea Mambrini Dirk Sudholt Xin Yao incollection SudholtHandbook Parametrization and Balancing Global and Local Search 2012 Handbook of Memetic Algorithms 379 Springer Studies in Computational Intelligence Carlos Cotta and Ferrante Neri and Pablo Moscato http://www.springer.com/engineering/computational+intelligence+and+complexity/book/978-3-642-23246-6 Eingeladener Beitrag. 1360+ Downloads am 7. 9. 2019 Dirk Sudholt article ant-sp-journal Running time analysis of Ant Colony Optimization for shortest path problems 2012 DOI: 10.1016/j.jda.2011.06.002 Journal of Discrete Algorithms 10 165--180 http://dx.doi.org/10.1016/j.jda.2011.06.002 Platz 6 in der Rangliste \glqq{}2011's top downloaded articles from Journal of Discrete Algorithms\grqq{} Dirk Sudholt Christian Thyssen inproceedings Moraglio2012 Runtime Analysis of Convex Evolutionary Search 2012 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012) http://dx.doi.org/10.1145/2330163.2330255 Best paper award in der Kategorie \glqq{}Genetic Algorithms\grqq{}. Alberto Moraglio Dirk Sudholt inproceedings Rowe2012 The Choice of the Offspring Population Size in the (1,λ)~EA 2012 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012) http://dx.doi.org/10.1145/2330163.2330350 Nominiert für einen best paper award in der Kategorie \glqq{}Theory/ESEP\grqq{}. Jon Rowe Dirk Sudholt inproceedings Lassig2010c Adaptive Population Models for Offspring Populations and Parallel Evolutionary Algorithms 2011 Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA~2011) ACM Press 181--192 http://dx.doi.org/10.1145/1967654.1967671 Jörg Lässig Dirk Sudholt inproceedings Lassig2011a Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization 2011 22nd International Symposium on Algorithms and Computation (ISAAC~2011) 7074 Springer LNCS 405-414 http://dx.doi.org/10.1007/978-3-642-25591-5_42 Jörg Lässig Dirk Sudholt inproceedings Koetzing2011 How Crossover Helps in Pseudo-Boolean Optimization 2011 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO~2011) ACM Press 989--996 http://dx.doi.org/10.1145/2001576.2001711 Best paper award in der Kategorie \glqq{}Genetic Algorithms\grqq{}. Timo Kötzing Dirk Sudholt Madeleine Theile article Sudholt2010 Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima 2011 Algorithmica 59 343--368 3 http://dx.doi.org/10.1007/s00453-009-9384-2 Dirk Sudholt incollection SudholtTRSH Memetic Evolutionary Algorithms 2011 Theory of Randomized Search Heuristics -- Foundations and Recent Developments World Scientific Series on Theoretical Computer Science Anne Auger and Benjamin Doerr 1 http://worldscibooks.com/compsci/7438.html Dirk Sudholt inproceedings Neumann2011 On the Effectiveness of Crossover for Migration in Parallel Evolutionary Algorithms 2011 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO~2011) ACM Press 1587--1594 http://dx.doi.org/10.1145/2001576.2001790 Frank Neumann Pietro S. Oliveto Günter Rudolph Dirk Sudholt article Doerr2010a Runtime Analysis of the 1-ANT Ant Colony Optimizer 2011 Theoretical Computer Science 412 1629--1644 17 http://dx.doi.org/10.1016/j.tcs.2010.12.030 Benjamin Doerr Frank Neumann Dirk Sudholt Carsten Witt inproceedings Koetzing2010 Simple Max-Min Ant Systems and the Optimization of Linear Pseudo-Boolean Functions 2011 Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA~2011) ACM Press 209--218 http://dx.doi.org/10.1145/1967654.1967673 Timo Kötzing Frank Neumann Dirk Sudholt Markus Wagner inproceedings Sudholt2010c Using Markov-Chain Mixing Time Estimates for the Analysis of Ant Colony Optimization 2011 Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA~2011) ACM Press 139--150 http://dx.doi.org/10.1145/1967654.1967667 Dirk Sudholt inproceedings Neumann2010a A Few Ants are Enough: ACO with Iteration-Best Update 2010 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010) 63--70 http://dx.doi.org/10.1145/1830483.1830493 Nominiert für einen best paper award in der Kategorie \glqq{}Ant Colony Optimization/Swarm Intelligence\grqq{}. Frank Neumann Dirk Sudholt Carsten Witt article SauerwaldTCS A Self-stabilizing Algorithm for Cut Problems in Synchronous Networks 2010 Theoretical Computer Science 411 1599--1612 14--15 http://dx.doi.org/10.1016/j.tcs.2010.01.008 Thomas Sauerwald Dirk Sudholt article Jansentoappear Analysis of an Asymmetric Mutation Operator 2010 Evolutionary Computation 18 1--26 1 http://dx.doi.org/10.1162/evco.2010.18.1.18101 Thomas Jansen Dirk Sudholt inproceedings Sudholt2010b Analysis of an Iterated Local Search Algorithm for Vertex Coloring 2010 21st International Symposium on Algorithms and Computation (ISAAC 2010) 6506 Springer LNCS 340--352 http://dx.doi.org/10.1007/978-3-642-17517-6_31 Dirk Sudholt Christine Zarges inproceedings Horoba2010 Ant Colony Optimization for Stochastic Shortest Path Problems 2010 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010) 1465--1472 http://dx.doi.org/10.1145/1830483.1830750 Nominiert für einen best paper award in der Kategorie \glqq{}Theory\grqq{}. Eingeladen zu einem Sonderheft in \emph{Algorithmica}. Christian Horoba Dirk Sudholt inproceedings Lassig2010b Experimental Supplements to the Theoretical Analysis of Migration in the Island Model 2010 11th International Conference on Parallel Problem Solving from Nature (PPSN~2010) 6238 Springer LNCS 224--233 http://dx.doi.org/10.1007/978-3-642-15844-5_23 Jörg Lässig Dirk Sudholt inproceedings Sudholt2010a General Lower Bounds for the Running Time of Evolutionary Algorithms 2010 11th International Conference on Parallel Problem Solving from Nature (PPSN~2010) 6238 Springer LNCS 124--133 http://dx.doi.org/10.1007/978-3-642-15844-5_13 Dirk Sudholt inproceedings Lassig2010a General Scheme for Analyzing Running Times of Parallel Evolutionary Algorithms 2010 11th International Conference on Parallel Problem Solving from Nature (PPSN~2010) 6238 Springer LNCS 234--243 http://dx.doi.org/10.1007/978-3-642-15844-5_24 Best paper award. Jörg Lässig Dirk Sudholt inproceedings Doerr2010 Optimizing Monotone Functions Can Be Difficult 2010 11th International Conference on Parallel Problem Solving from Nature (PPSN~2010) 6238 Springer LNCS 42--51 http://dx.doi.org/10.1007/978-3-642-15844-5_5 Benjamin Doerr Thomas Jansen Dirk Sudholt Carola Winzen Christine Zarges article Sudholtsubmitteda Runtime Analysis of a Binary Particle Swarm Optimizer 2010 Theoretical Computer Science 411 2084--2100 21 http://dx.doi.org/10.1016/j.tcs.2010.03.002 Dirk Sudholt Carsten Witt inproceedings Lassig2010 The Benefit of Migration in Parallel Evolutionary Algorithms 2010 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010) 1105--1112 http://dx.doi.org/10.1145/1830483.1830687 Best paper award in der Kategorie \glqq{}Parallel Evolutionary Systems\grqq{}. Jörg Lässig Dirk Sudholt article Neumann2009 Analysis of Different MMAS ACO Algorithms on Unimodal Functions and Plateaus 2009 Swarm Intelligence 3 35--68 1 http://dx.doi.org/10.1007/s11721-008-0023-3 Sonderheft zum Thema \glqq{}Ant colony optimization\grqq{} (Annahmequote 16%). Frank Neumann Dirk Sudholt Carsten Witt article Friedrichsubmitted Analysis of Diversity-Preserving Mechanisms for Global Exploration 2009 Evolutionary Computation 17 455--476 4 http://dx.doi.org/10.1162/evco.2009.17.4.17401 Tobias Friedrich Pietro S. Oliveto Dirk Sudholt Carsten Witt incollection Neumann2009a Computational Complexity of Ant Colony Optimization and its Hybridization with Local Search 2009 Innovations in Swarm Intelligence Springer SGI Chee Peng Lim and Lakhmi C. Jain and Satchidananda Dehuri 248 http://www.springer.com/engineering/book/978-3-642-04224-9 Frank Neumann Dirk Sudholt Carsten Witt inproceedings Horoba2009a Running Time Analysis of ACO Systems for Shortest Path Problems 2009 Proceedings of Engineering Stochastic Local Search Algorithms (SLS~'09) 5752 Springer LNCS 76--91 http://dx.doi.org/10.1007/978-3-642-03751-1_6 Christian Horoba Dirk Sudholt article Sudholtsubmitted The Impact of Parametrization in Memetic Evolutionary Algorithms 2009 Theoretical Computer Science 410 2511--2528 26 http://dx.doi.org/10.1016/j.tcs.2009.03.003 Dirk Sudholt thesis Sudholt2008thesis Computational Complexity of Evolutionary Algorithms, Hybridizations, and Swarm Intelligence Dissertation 2008 1 Technische Universität Dortmund http://hdl.handle.net/2003/25954 Dirk Sudholt inproceedings Sudholt2008 Memetic Algorithms with Variable-Depth Search to Overcome Local Optima 2008 Proceedings of the Genetic and Evolutionary Computation Conference {(GECCO 2008)} ACM Press 787-794 http://doi.acm.org/10.1145/1389095.1389251 Nominiert für einen best paper award in der Kategorie \glqq{}Formal Theory\grqq{}. Eingeladen zu einem Sonderheft in \emph{Algorithmica}. Dirk Sudholt inproceedings Neumann2008a Rigorous Analyses for the Combination of Ant Colony Optimization and Local Search 2008 Proceedings of the Sixth International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS~'08) 5217 Springer LNCS 132--143 http://dx.doi.org/10.1007/978-3-540-87527-7_12 Frank Neumann Dirk Sudholt Carsten Witt inproceedings Sudholt2008c Runtime Analysis of Binary PSO 2008 Proceedings of the Genetic and Evolutionary Computation Conference {(GECCO 2008)} ACM Press 135--142 http://doi.acm.org/10.1145/1389095.1389114 Dirk Sudholt Carsten Witt inproceedings Sauerwald2008a Self-stabilizing Cuts in Synchronous Networks 2008 International Colloquium on Structural Information and Communication Complexity (SIROCCO~'08) 5058 Springer LNCS 234--246 http://dx.doi.org/10.1007/978-3-540-69355-0_20 Eingeladen zu einem Sonderheft in \emph{Theoretical Computer Science}. Thomas Sauerwald Dirk Sudholt inproceedings Friedrich2008a Theoretical Analysis of Diversity Mechanisms for Global Exploration 2008 Proceedings of the Genetic and Evolutionary Computation Conference {(GECCO 2008)} ACM Press 945--952 http://doi.acm.org/10.1145/1389095.1389276 Best paper award in der Kategorie \glqq{}Genetic Algorithms\grqq{}. Tobias Friedrich Pietro S. Oliveto Dirk Sudholt Carsten Witt inproceedings Neumann2007 Comparing Variants of MMAS ACO Algorithms on Pseudo-Boolean Functions 2007 Proceedings of Engineering Stochastic Local Search Algorithms (SLS~'07) 4638 Springer LNCS 61--75 http://dx.doi.org/10.1007/978-3-540-74446-7_5 Frank Neumann Dirk Sudholt Carsten Witt inproceedings Doerr2007b On the Runtime Analysis of the 1-ANT ACO Algorithm 2007 Proceedings of the Genetic and Evolutionary Computation Conference {(GECCO 2007)} ACM Press 33--40 http://doi.acm.org/10.1145/1276958.1276964 Best paper award in der Kategorie \glqq{}Ant Colony Optimization, Swarm Intelligence, and Artificial Immune Systems\grqq{}. Benjamin Doerr Frank Neumann Dirk Sudholt Carsten Witt inproceedings Sudholt2006 Local Search in Evolutionary Algorithms: the Impact of the Local Search Frequency 2006 Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC~'06) 4288 Springer LNCS 359-368 http://dx.doi.org/10.1007/11940128_37 Dirk Sudholt inproceedings Sudholt2006a On the Analysis of the (1+1)~Memetic Algorithm 2006 Proceedings of the Genetic and Evolutionary Computation Conference {(GECCO 2006)} ACM Press 493-500 http://doi.acm.org/10.1145/1143997.1144087 Dirk Sudholt inproceedings Sudholt2005 Crossover is Provably Essential for the Ising Model on Trees 2005 Proceedings of the Genetic and Evolutionary Computation Conference {(GECCO 2005)} ACM Press 1161-1167 http://doi.acm.org/10.1145/1068009.1068202 Dirk Sudholt inproceedings Jansen2005 Design and analysis of an asymmetric mutation operator 2005 Proceedings of the IEEE Congress on Evolutionary Computation (CEC~'05) IEEE Press 497--504 http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1554684 Thomas Jansen Dirk Sudholt thesis Sudholt2004 Evolutionäre Algorithmen als Adaptationsschemata Diplomarbeit 2004 1 Universität Dortmund t3://file?uid=383605 _blank PDF PDF-Dokument Note test Dirk Sudholt inproceedings Briest2004e Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization 2004 Parallel Problem Solving From Nature (PPSN VIII) 3242 Springer LNCS 21--30 http://dx.doi.org/10.1007/978-3-540-30217-9_3 Patrick Briest Dimo Brockhoff Sebastian Degener Matthias Englert Christian Gunia Oliver Heering Thomas Jansen Michael Leifhelm Kai Plociennik Heiko Röglin Andrea Schweer Dirk Sudholt Stefan Tannenbaum Ingo Wegener inproceedings Briest2004d The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes 2004 Parallel Problem Solving From Nature (PPSN VIII) 3242 Springer LNCS 31--40 http://dx.doi.org/10.1007/978-3-540-30217-9_4 Patrick Briest Dimo Brockhoff Sebastian Degener Matthias Englert Christian Gunia Oliver Heering Thomas Jansen Michael Leifhelm Kai Plociennik Heiko Röglin Andrea Schweer Dirk Sudholt Stefan Tannenbaum Ingo Wegener