# Analysis of Evolutionary Diversity Optimisation for Permutation Problems

arXiv: https://arxiv.org/abs/2102.11469 · HTML: https://mlsanity.com/paper/2102.11469/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2021.

## Built on by (most cited first, 7 of 7)

- [Diversity from Human Feedback](https://mlsanity.com/paper/2310.06648/) (2023)
- [Optimizing Cyber Defense in Dynamic Active Directories through Reinforcement Learning](https://mlsanity.com/paper/2406.19596/) (2024)
- [Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax](https://mlsanity.com/paper/2307.07248/) (2023)
- [Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem](https://mlsanity.com/paper/2404.11496/) (2024)
- [Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential](https://mlsanity.com/paper/2407.08963/) (2024)
- [Benchmarking Randomized Optimization Algorithms on Binary, Permutation, and Combinatorial Problem Landscapes](https://mlsanity.com/paper/2501.17170/) (2025)
- [Linear Ordering Problem: Time for a Change](https://mlsanity.com/paper/2605.31051/) (2026)

## Abstract (arXiv)

Generating diverse populations of high quality solutions has gained interest as a promising extension to the traditional optimization tasks. This work contributes to this line of research with an investigation on evolutionary diversity optimization for three of the most well-studied permutation problems, namely the Traveling Salesperson Problem (TSP), both symmetric and asymmetric variants, and Quadratic Assignment Problem (QAP). It includes an analysis of the worst-case performance of a simple mutation-only evolutionary algorithm with different mutation operators, using an established diversity measure. Theoretical results show many mutation operators for these problems guarantee convergence to maximally diverse populations of sufficiently small size within cubic to quartic expected run-time. On the other hand, the result on QAP suggests that strong mutations give poor worst-case performance, as mutation strength contributes exponentially to the expected run-time. Additionally, experiments are carried out on QAPLIB and synthetic instances in unconstrained and constrained settings, and reveal much more optimistic practical performances, while corroborating the theoretical finding regarding mutation strength. These results should serve as a baseline for future studies.