Duc-Cuong Dang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Duc-Cuong Dang has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Dirk Sudholt
Chair of Algorithms for Intelligent Systems, University of Passau, Passau, Germany
11 shared publications - Andre Opris
University of Passau
10 shared publications - Aziz Moukrim
Université de Technologie de Compiègne
3 shared publications Andre Opris
University of Passau
2 shared publications- Frank Neumann
Adelaide University
2 shared publications - Per Kristian Lehre
University of Birmingham, Birmingham, United Kingdom
2 shared publications
Latest Publications
- 25 August 2026
- Published by Springer Nature
- p. 163-179
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
- 25 August 2026
- Published by Springer Nature
- p. 163-179
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
- 23 August 2026
- Published by Springer Nature
- p. 382-399
SPEA2$^+$: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees- 23 August 2026
- Published by Springer Nature
- p. 382-399
SPEA2$^+$: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees- Open Access
- 20 August 2026
- Published by Springer Nature in Algorithmica
- Vol. 88 (5) , 60
Why Dominance is Not Enough: Lessons from Practical Evolutionary Multi-objective Algorithms
Practical evolutionary multi-objective (EMO) algorithms like NSGA-II, NSGA-III, and SMS-EMOA combine the dominance relation with diversity criteria to identify promising solutions. Despite many success stories, their theoretical foundation remains underdeveloped, with key questions still unanswered–such as which information obtained during evolution is critical for their success. In this work, we explore the limitations of the information provided by the dominance relation between search points encountered so far. We present a large class of bi-objective problems whose Pareto-optimal set is small, while almost all pairs of search points are incomparable. On such problems, we prove that any black-box EMO algorithm that only relies on the dominance relation for making decisions fails spectacularly, requiring exponential time with high probability. In stark contrast, NSGA-II, NSGA-III, and SMS-EMOA efficiently cover the Pareto front in at most expected quadratic time by incorporating additional information from the objective values, such as crowding distances or hypervolume contributions of search points. Experiments conducted on randomly generated problems complement our theoretical findings. Our results highlight the superiority of practical EMO algorithms and the necessity of using information beyond dominance for effective multi-objective optimisation.
- 20 August 2026
- Published by Springer Nature in Algorithmica
- Vol. 88 (5) , 60
Open AccessWhy Dominance is Not Enough: Lessons from Practical Evolutionary Multi-objective Algorithms
Practical evolutionary multi-objective (EMO) algorithms like NSGA-II, NSGA-III, and SMS-EMOA combine the dominance relation with diversity criteria to identify promising solutions. Despite many success stories, their theoretical foundation remains underdeveloped, with key questions still unanswered–such as which information obtained during evolution is critical for their success. In this work, we explore the limitations of the information provided by the dominance relation between search points encountered so far. We present a large class of bi-objective problems whose Pareto-optimal set is small, while almost all pairs of search points are incomparable. On such problems, we prove that any black-box EMO algorithm that only relies on the dominance relation for making decisions fails spectacularly, requiring exponential time with high probability. In stark contrast, NSGA-II, NSGA-III, and SMS-EMOA efficiently cover the Pareto front in at most expected quadratic time by incorporating additional information from the objective values, such as crowding distances or hypervolume contributions of search points. Experiments conducted on randomly generated problems complement our theoretical findings. Our results highlight the superiority of practical EMO algorithms and the necessity of using information beyond dominance for effective multi-objective optimisation.
- Open Access
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 45-46
Hot of the Press: Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 45-46
Open AccessHot of the Press: Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem
- Open Access
- 30 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Evolutionary Learning and Optimization
- Vol. 6 (2) , 1-33
Runtime Analysis of Functions where Widely Used Evolutionary Multi-Objective Algorithms Beat Simple Ones
In evolutionary multi-objective optimisation, runtime analysis examines the (expected) time for Evolutionary Multi-Objective Algorithms (EMOAs) to cover the Pareto front. It has recently been applied to NSGA-II, NSGA-III and SMS-EMOA. However, most analyses showed that these widely used algorithms have the same runtime guarantee as the simplest EMOA, (G)SEMO. To our knowledge, no runtime analyses demonstrate an advantage of a popular EMOA over (G)SEMO for deterministic problems. We propose such problems to illustrate the superiority of popular EMOAs over (G)SEMO. We introduce a classification of multi-objective problems and identify the so-called ( \( a \) , \( b \) )-Pareto-sparse problems that are difficult for (G)SEMO as Pareto-optimal points are separated by large genotypic distances. A general lower bound on the expected number of fitness evaluations for (G)SEMO to solve any ( \( a \) , \( b \) )-Pareto-sparse problem is proven. On many example problems, this bound is \(n^{\Omega(n)}\) : OneTrapZeroTrap , a generalisation of Trap function to two objectives, the OneJumpZeroJump class with a large gap parameter and a class of bi-objective MaxSat instances called OneZeroCountSat . Therefore, (G)SEMO performs poorly on all these problems. Conversely, we prove that the three popular EMO algorithms—NSGA-II, NSGA-III and SMS-EMOA—enhanced with a mild diversity mechanism of avoiding genotype duplication, are highly efficient as they optimise OneTrapZeroTrap in only \(O(n\log{n})\) fitness evaluations in expectation. Experimental results on OneTrapZeroTrap and OneZeroCountSat match our theoretical prediction that (G)SEMO always fails, while the other algorithms always succeed. Our analysis reveals the importance of the key components in these sophisticated algorithms and contributes to a better understanding of their capabilities.- 30 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Evolutionary Learning and Optimization
- Vol. 6 (2) , 1-33
Open AccessRuntime Analysis of Functions where Widely Used Evolutionary Multi-Objective Algorithms Beat Simple Ones
In evolutionary multi-objective optimisation, runtime analysis examines the (expected) time for Evolutionary Multi-Objective Algorithms (EMOAs) to cover the Pareto front. It has recently been applied to NSGA-II, NSGA-III and SMS-EMOA. However, most analyses showed that these widely used algorithms have the same runtime guarantee as the simplest EMOA, (G)SEMO. To our knowledge, no runtime analyses demonstrate an advantage of a popular EMOA over (G)SEMO for deterministic problems. We propose such problems to illustrate the superiority of popular EMOAs over (G)SEMO. We introduce a classification of multi-objective problems and identify the so-called ( \( a \) , \( b \) )-Pareto-sparse problems that are difficult for (G)SEMO as Pareto-optimal points are separated by large genotypic distances. A general lower bound on the expected number of fitness evaluations for (G)SEMO to solve any ( \( a \) , \( b \) )-Pareto-sparse problem is proven. On many example problems, this bound is \(n^{\Omega(n)}\) : OneTrapZeroTrap , a generalisation of Trap function to two objectives, the OneJumpZeroJump class with a large gap parameter and a class of bi-objective MaxSat instances called OneZeroCountSat . Therefore, (G)SEMO performs poorly on all these problems. Conversely, we prove that the three popular EMO algorithms—NSGA-II, NSGA-III and SMS-EMOA—enhanced with a mild diversity mechanism of avoiding genotype duplication, are highly efficient as they optimise OneTrapZeroTrap in only \(O(n\log{n})\) fitness evaluations in expectation. Experimental results on OneTrapZeroTrap and OneZeroCountSat match our theoretical prediction that (G)SEMO always fails, while the other algorithms always succeed. Our analysis reveals the importance of the key components in these sophisticated algorithms and contributes to a better understanding of their capabilities. - Open Access
- 13 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 1604-1612
Why Dominance Is Not Enough: Lessons from Practical Evolutionary Multi-Objective Algorithms
- 13 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 1604-1612
Open AccessWhy Dominance Is Not Enough: Lessons from Practical Evolutionary Multi-Objective Algorithms
- 7 September 2024
- Published by Springer Nature
- p. 230-245
On the Equivalence Between Stochastic Tournament and Power-Law Ranking Selection and How to Implement Them Efficiently
- 7 September 2024
- Published by Springer Nature
- p. 230-245
On the Equivalence Between Stochastic Tournament and Power-Law Ranking Selection and How to Implement Them Efficiently
- Open Access
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 51-52
Hot of the Press: Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation
Despite the popularity of evolutionary multi-objective (EMO) algorithms in practices, their theoretical foundations are still in the early development. Fundamental questions such as the benefits of crossover are not fully understood. This work provides a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover. We propose two classes of "royal road" functions, one tailored for one-point crossover and another one for uniform crossover, on which the EMO algorithms cover the Pareto front in expected polynomial time if crossover is being used. But when disabling crossover, they require exponential time 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, or even with the use of some immune-inspired hypermutation operator. This is the first example of a proven exponential performance gap through enabling crossover for the NSGA-II. This Hot-off-the-Press paper summarises the work Duc-Cuong Dang, Andre Opris, and Dirk Sudholt. Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation, Artificial Intelligence, 330 (2024), 104098.
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 51-52
Open AccessHot of the Press: Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation
Despite the popularity of evolutionary multi-objective (EMO) algorithms in practices, their theoretical foundations are still in the early development. Fundamental questions such as the benefits of crossover are not fully understood. This work provides a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover. We propose two classes of "royal road" functions, one tailored for one-point crossover and another one for uniform crossover, on which the EMO algorithms cover the Pareto front in expected polynomial time if crossover is being used. But when disabling crossover, they require exponential time 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, or even with the use of some immune-inspired hypermutation operator. This is the first example of a proven exponential performance gap through enabling crossover for the NSGA-II. This Hot-off-the-Press paper summarises the work Duc-Cuong Dang, Andre Opris, and Dirk Sudholt. Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation, Artificial Intelligence, 330 (2024), 104098.
- Open Access
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1551-1559
The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary Algorithms
While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy. We generalise the previous work to a complete hierarchy for all pseudo-Boolean functions. The hierarchy is consistent with existing results for the runtime of EAs. The hardest part of the hierarchy consists of problems satisfying the No Free Lunch theorem. The easiest part contains well-known theoretical benchmark problems, easy for EAs. The intermediary parts contain instances of NP-hard problems. Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We study how random perturbations of a function can change its classification. E.g, randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs.
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1551-1559
Open AccessThe SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary Algorithms
While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy. We generalise the previous work to a complete hierarchy for all pseudo-Boolean functions. The hierarchy is consistent with existing results for the runtime of EAs. The hardest part of the hierarchy consists of problems satisfying the No Free Lunch theorem. The easiest part contains well-known theoretical benchmark problems, easy for EAs. The intermediary parts contain instances of NP-hard problems. Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We study how random perturbations of a function can change its classification. E.g, randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs.
- Top Cited PapersOpen Access
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1596-1604
Runtime Analyses of NSGA-III on Many-Objective Problems
NSGA-II and NSGA-III are two of the most popular evolutionary multi-objective algorithms used in practice. While NSGA-II is used for few objectives such as 2 and 3, NSGA-III is designed to deal with a larger number of objectives. In a recent breakthrough, Wietheger and Doerr (IJCAI 2023) gave the first runtime analysis for NSGA-III on the 3-objective OneMinMax problem, showing that this state-of-the-art algorithm can be analyzed rigorously. We advance this new line of research by presenting the first runtime analyses of NSGA-III on the popular many-objective benchmark problems m-LOTZ, m-OMM, and m-COCZ, for an arbitrary constant number m of objectives. Our analysis provides ways to set the important parameters of the algorithm: the number of reference points and the population size, so that a good performance can be guaranteed. We show how these parameters should be scaled with the problem dimension, the number of objectives and the fitness range. To our knowledge, these are the first runtime analyses for NSGA-III for more than 3 objectives.
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1596-1604
Top Cited PapersOpen AccessRuntime Analyses of NSGA-III on Many-Objective Problems
NSGA-II and NSGA-III are two of the most popular evolutionary multi-objective algorithms used in practice. While NSGA-II is used for few objectives such as 2 and 3, NSGA-III is designed to deal with a larger number of objectives. In a recent breakthrough, Wietheger and Doerr (IJCAI 2023) gave the first runtime analysis for NSGA-III on the 3-objective OneMinMax problem, showing that this state-of-the-art algorithm can be analyzed rigorously. We advance this new line of research by presenting the first runtime analyses of NSGA-III on the popular many-objective benchmark problems m-LOTZ, m-OMM, and m-COCZ, for an arbitrary constant number m of objectives. Our analysis provides ways to set the important parameters of the algorithm: the number of reference points and the population size, so that a good performance can be guaranteed. We show how these parameters should be scaled with the problem dimension, the number of objectives and the fitness range. To our knowledge, these are the first runtime analyses for NSGA-III for more than 3 objectives.