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.

翻译：在这项工作中,我们考虑了寻找一套旅行销售人员问题旅游(TSP)的问题,以尽量扩大多样性,同时满足一定的成本限制。本研究旨在调查运用挤压来尽量扩大多样性而不是简单地维持多样性的有效性。为此,我们引入了一种两阶段的方法,即从多种溶解TSP的最先进的简单消化算法(NMA)与基线多样化算法相结合,拟议的NMA的最显著特征是使用随机化的改进-第一次本地搜索,而不是2-opt。我们对TSPLIB案例的实验表明,虽然我们NMA所发展的人口往往在质量紧紧的制约下包含集群,但他们往往占据着遥远的吸引区而不是近邻区,在总和多样性方面改进了基线多样化。与原始NMA相比,我们虽然简单,但在运行时间较短的情况下找到更远的更高质量解决方案,但幅度很大。