Niching-based Evolutionary Diversity Optimization for the Traveling Salesperson Problem

Abstract

In this work, we consider the problem of finding a set of tours to a traveling salesperson problem (TSP) instance maximizing diversity, while satisfying a given cost constraint. This study aims to investigate the effectiveness of applying niching to maximize diversity rather than simply maintaining it. To this end, we introduce a 2-stage approach where a simple niching memetic algorithm (NMA), derived from a state-of-the-art for multi-solution TSP, is combined with a baseline diversifying algorithm. The most notable feature of the proposed NMA is the use of randomized improvement-first local search instead of 2-opt. Our experiment on TSPLIB instances shows that while the populations evolved by our NMA tend to contain clusters at tight quality constraints, they frequently occupy distant basins of attraction rather than close-by regions, improving on the baseline diversification in terms of sum-sum diversity. Compared to the original NMA, ours, despite its simplicity, finds more distant solutions of higher quality within less running time, by a large margin.

arXiv comment14 pages

References in corpus (8)

• Procedural Content Generation through Quality Diversity
• Empowering Quality Diversity in Dungeon Design with Interactive Constrained MAP-Elites
• Evolving Diverse Sets of Tours for the Travelling Salesperson Problem
• Evolutionary Multimodal Optimization: A Short Survey
• Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
• Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem
• Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms
• Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation