Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation

Adel Nikfarjam, Jakob Bossek, Aneta Neumann, Frank Neumann

Abstract

Evolutionary algorithms based on edge assembly crossover (EAX) constitute some of the best performing incomplete solvers for the well-known traveling salesperson problem (TSP). Often, it is desirable to compute not just a single solution for a given problem, but a diverse set of high quality solutions from which a decision maker can choose one for implementation. Currently, there are only a few approaches for computing a diverse solution set for the TSP. Furthermore, almost all of them assume that the optimal solution is known. In this paper, we introduce evolutionary diversity optimisation (EDO) approaches for the TSP that find a diverse set of tours when the optimal tour is known or unknown. We show how to adopt EAX to not only find a high-quality solution but also to maximise the diversity of the population. The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse high-quality tours when the optimal solution for the TSP is known or unknown. A comparison to existing approaches shows that they are clearly outperformed by EAX-EDO.

Introduction

In classical optimization, the primary objective is typically the identification of a single global optimum. However, in practical applications such as logistics or air traffic control, the mathematically optimal route may be susceptible to real-world disruptions like road closures or changing priorities. Evolutionary Diversity Optimisation (EDO) addresses this by seeking a set of solutions that are both high-quality (within a specified cost threshold) and structurally diverse.

While previous research into TSP diversity often assumed prior knowledge of the optimal solution or relied on simple local search operators like $k$-OPT, this paper introduces EAX-EDO. This approach leverages the powerful Edge Assembly Crossover (EAX) to generate diverse, near-optimal tours from scratch, even when the global optimum is unknown.

Methodology: The EAX-EDO Crossover

The core of the proposed method is the modification of the state-of-the-art EAX operator. Standard EAX combines edges from two parent tours to form "AB-cycles," which are then used to generate an intermediate solution consisting of several sub-tours. These sub-tours are typically merged greedily to minimize total cost.

The EAX-EDO process: from parent selection to the generation of offspring optimized for diversity.

EAX-EDO introduces two significant changes:

  1. Entropy-Based Diversity ($H$): Instead of simple edge counting, the algorithm employs an information-theoretic entropy measure. A population achieves high entropy when edges are distributed broadly across the set, preventing the convergence of the population toward a few "popular" edges.
  2. Diversity-Preserving Connection: During the sub-tour merging phase, EAX-EDO evaluates potential edge additions based on their contribution to the population's total entropy, provided the resulting tour length does not exceed a quality threshold $c_{max}$.

The authors also compared single-stage and two-stage frameworks. The single-stage approach, which simultaneously optimizes for quality and diversity by generating two distinct offspring per iteration, proved more robust and efficient than alternating between the two objectives.

Experimental Evaluation

The approach was tested on standard benchmarks from TSPlib, ranging from small instances (eil51, eil76, eil101) to larger, more complex maps (up to fnl4461). The performance was evaluated using multiple diversity metrics, including entropy (ENT), edge distance (ED), and pairwise distance (PD).

Comparative results of different diversity measures across various TSP instances and parameter settings.

Key Results and Insights

The experimental results highlight several advantages of the EAX-EDO approach:

  • Superior Diversity Generation: EAX-EDO consistently outperforms $k$-OPT and standard EAX. For the eil101 instance, EAX-EDO identified 758 unique edges, nearly triple the 238 found by standard EAX.
  • Structural Robustness: The use of entropy as a fitness function leads to more structurally diverse populations than distance-based measures. This diversity acts as a "safety net"; in scenarios where optimal edges were removed, EAX-EDO populations provided viable high-quality alternatives in 82% to 90% of cases.
  • Efficiency of Single-Stage Optimization: Maintaining a "hall of fame" ($P^*$) of the best solutions allows the single-stage approach to explore diverse regions of the search space without sacrificing solution quality.

Conclusion

EAX-EDO represents a significant advancement in generating diverse solution sets for the TSP. By integrating entropy-based diversity into the EAX operator, the method provides robust, high-quality alternatives that are essential for real-world decision-making. Future work will focus on reducing the computational overhead of the EAX operator and applying these techniques to dynamic logistics problems where constraints evolve over time.

Summary updated

Abstract

Evolutionary algorithms based on edge assembly crossover (EAX) constitute some of the best performing incomplete solvers for the well-known traveling salesperson problem (TSP). Often, it is desirable to compute not just a single solution for a given problem, but a diverse set of high quality solutions from which a decision maker can choose one for implementation. Currently, there are only a few approaches for computing a diverse solution set for the TSP. Furthermore, almost all of them assume that the optimal solution is known. In this paper, we introduce evolutionary diversity optimisation (EDO) approaches for the TSP that find a diverse set of tours when the optimal tour is known or unknown. We show how to adopt EAX to not only find a high-quality solution but also to maximise the diversity of the population. The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse high-quality tours when the optimal solution for the TSP is known or unknown. A comparison to existing approaches shows that they are clearly outperformed by EAX-EDO.
BibTeX
@inproceedings{nikfarjam2021computing,
  author = {Adel Nikfarjam and Jakob Bossek and Aneta Neumann and Frank Neumann},
  title = {{Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation}},
  booktitle = {FOGA},
  year = {2021},
  url = {https://openreview.net/forum?id=8v2V1laZNZd},
}
Figure