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

Duc-Cuong Dang, Aneta Neumann, Frank Neumann, Andre Opris, Dirk SudholtIJCAI 2025 · DOI

Abstract Quality Diversity (QD) algorithms, such as Map-Elites, have achieved notable success in robotics and design by maintaining a library of diverse, high-performing solutions. Despite their empirical utility, formal theoretical analysis of their efficiency has been limited. This paper bridges this gap by analyzing QD performance on the All-Pairs Shortest Path (APSP) problem. We provide the first runtime analysis for QD on a problem where diversity is the primary objective. Our results show that QD algorithms efficiently solve APSP by exploiting behavioral synergies, with crossover operators providing significant speedups. We also introduce a "Fast QD-APSP" variant that optimizes parent selection to achieve near-optimal runtime complexity.

Introduction

In many real-world optimization scenarios, finding a single global optimum is insufficient. Instead, practitioners often require a diverse set of high-quality solutions to provide robustness and flexibility—a goal addressed by the Quality Diversity (QD) paradigm. While algorithms like Map-Elites have seen massive empirical success, theoretical research has historically focused on single-objective optimization, often treating diversity merely as a stepping stone. This paper provides a rigorous foundation for QD by analyzing its performance on the All-Pairs Shortest Path (APSP) problem, where the objective is inherently to find an optimal solution for every possible pair of nodes in a graph.

The APSP Problem as a Quality Diversity Task

The APSP problem is a natural fit for QD analysis. In this context, the "behavioral space" is defined by the start and end nodes of a path. The QD archive (or map) is an $n \times n$ grid where each cell $(s, t)$ stores the best-known path from node $s$ to node $t$. The goal of the algorithm is to fill this entire map with optimal (shortest) paths.

Algorithmic Framework

The study evaluates three variants of a QD algorithm based on the Map-Elites framework:

  1. QD-EA: A mutation-only variant that adds or removes edges from existing paths.
  2. QD-GA: A genetic algorithm variant that incorporates crossover, allowing the concatenation of two paths.
  3. Fast QD-APSP: A novel variant introducing Improved Selection. Standard Map-Elites selects parents uniformly at random, which becomes inefficient as the map grows. Fast QD-APSP selects only "compatible" parents (e.g., where one path ends where the next begins), significantly reducing idle iterations.

Theoretical Analysis and Runtime Bounds

The researchers derived expected runtime bounds—the average number of fitness evaluations required to solve the problem—across different graph types. For general directed strongly connected graphs, the mutation-only QD-EA achieves a runtime of $O(n^2 \Delta \max\{\ell, \log n\})$, where $\Delta$ is the maximum degree and $\ell$ is the diameter.

Graph construction used to establish lower bounds on the runtime of crossover-based QD algorithms, illustrating the structural challenges analyzed.

To establish lower bounds and test the limits of crossover, the authors utilized specific graph constructions, such as weighted complete graphs ($K_n$) and complex gadgets (as seen in the figure above). These constructions demonstrate that while crossover is generally powerful, its efficiency depends heavily on the selection mechanism.

Key Insights

  • Behavioral Synergy: A critical finding is that mutation in QD is more efficient than expected due to synergies. Improving a path for one node pair often provides optimal sub-paths for many other pairs in the map simultaneously.
  • Crossover as a Catalyst: Crossover acts as a "killer app" for APSP. While mutation extends paths incrementally, crossover can combine two optimal sub-paths to instantly create longer optimal paths. This leads to an exponential "phase-based" speedup in map completion.
  • Selection Bottlenecks: The analysis reveals that as the map size ($n^2$) increases, the probability of randomly picking two combinable parents drops. The Fast QD-APSP variant mitigates this, reducing complexity from $O(n^4)$ to $O(n^3 \log n)$, matching the efficiency of some specialized classical algorithms.

Conclusion

This work provides the first formal proof that Quality Diversity algorithms are not just heuristic tools but can be theoretically efficient solvers for complex, multi-solution problems. By exploiting the compositional structure of problems like APSP through crossover and intelligent selection, QD algorithms can achieve performance competitive with classical methods while maintaining a diverse library of solutions. Future work will explore whether these insights extend to behavioral spaces where solutions lack the clean compositional structure of graph paths.

Summary updated

BibTeX
@inproceedings{dang2025theoretical,
  author = {Duc-Cuong Dang and Aneta Neumann and Frank Neumann and Andre Opris and Dirk Sudholt},
  title = {{Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/985},
}
Figure