# Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2021.

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

- [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)

## Abstract (arXiv)

Computing diverse sets of high-quality solutions has gained increasing attention among the evolutionary computation community in recent years. It allows practitioners to choose from a set of high-quality alternatives. In this paper, we employ a population diversity measure, called the high-order entropy measure, in an evolutionary algorithm to compute a diverse set of high-quality solutions for the Traveling Salesperson Problem. In contrast to previous studies, our approach allows diversifying segments of tours containing several edges based on the entropy measure. We examine the resulting evolutionary diversity optimisation approach precisely in terms of the final set of solutions and theoretical properties. Experimental results show significant improvements compared to a recently proposed edge-based diversity optimisation approach when working with a large population of solutions or long segments.