  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.
