Evolving Diverse Sets of Tours for the Travelling Salesperson Problem

Abstract

Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm.

11 pages, 3 tables, 3 figures, published in GECCO '20; proof of Theorem 1 corrected

Cited by in corpus (12)

• Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem
• Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
• Analysis of Evolutionary Diversity Optimisation for Permutation Problems
• Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms
• Defending Active Directory by Combining Neural Network based Dynamic Program and Evolutionary Diversity Optimisation
• Runtime Analysis for Permutation-based Evolutionary Algorithms
• Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation
• Towards a Stronger Theory for Permutation-based Evolutionary Algorithms
• Niching-based Evolutionary Diversity Optimization for the Traveling Salesperson Problem
• Exploring the Feature Space of TSP Instances Using Quality Diversity
• Computing Diverse Sets of Solutions for Monotone Submodular Optimisation Problems
• Exact Counting and Sampling of Optima for the Knapsack Problem