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.
EAX-EDO introduces two significant changes:
- 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.
- 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).
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
eil101instance, 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