Publication
Analysis of Evolutionary Diversity Optimization for Permutation Problems
Publisher:
Association for Computing Machinery (ACM)
Date:
30-09-2022
DOI:
10.1145/3561974
Abstract: Generating erse 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 ersity optimization for three of the most well-studied permutation problems: the Traveling Salesperson Problem (TSP), both symmetric and asymmetric variants, and the 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 ersity measure. Theoretical results show that many mutation operators for these problems guarantee convergence to maximally erse populations of sufficiently small size within cubic to quartic expected runtime. On the other hand, the results regarding QAP suggest that strong mutations give poor worst-case performance, as mutation strength contributes exponentially to the expected runtime. 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 findings regarding mutation strength. These results should serve as a baseline for future studies.