发现并修复EAX算法中关键的AB循环，提升旅行商问题求解效率与质量。
To Repair or Not to Repair? Investigating the Importance of AB-Cycles for the State-of-the-Art TSP Heuristic EAX
- 提出快速验证AB循环是否需修复的新方法，优化算法初期阶段。
- 在10000个实例上测试，新变体在难解实例中效率与精度双提升。
- 适合研究组合优化或想改进经典启发式算法的读者参考。
边组装交叉（EAX）算法是求解旅行商问题（TSP）的当前最优启发式方法，通常优于林-克尼格-赫尔施高算法（LKH）。EAX采用两阶段机制：先局部优化，再全局优化。尽管第二阶段已深入研究和调优，但第一阶段仍鲜有探讨。本文聚焦于EAX的第一阶段，提出一种新方法，可快速判断内部优化过程中生成的AB循环是否构成有效路径——若否，则需修复。该知识对后续应用广义分区交叉（GPX）等强大交叉算子也至关重要。基于此，我们提出并评估多个改进版EAX。在10000个不同TSP实例上的基准测试表明，其中最优变体在先前较难的实例上表现出更高的计算效率与更优解质量，超越当前最先进版本。
原文摘要 · Abstract (English)
The Edge Assembly Crossover (EAX) algorithm is the state-of-the-art heuristic for solving the Traveling Salesperson Problem (TSP). It regularly outperforms other methods, such as the Lin-Kernighan-Helsgaun heuristic (LKH), across diverse sets of TSP instances. Essentially, EAX employs a two-stage mechanism that focuses on improving the current solutions, first, at the local and, subsequently, at the global level. Although the second phase of the algorithm has been thoroughly studied, configured, and refined in the past, in particular, its first stage has hardly been examined. In this paper, we thus focus on the first stage of EAX and introduce a novel method that quickly verifies whether the AB-cycles, generated during its internal optimization procedure, yield valid tours -- or whether they need to be repaired. Knowledge of the latter is also particularly relevant before applying other powerful crossover operators such as the Generalized Partition Crossover (GPX). Based on our insights, we propose and evaluate several improved versions of EAX. According to our benchmark study across 10 000 different TSP instances, the most promising of our proposed EAX variants demonstrates improved computational efficiency and solution quality on previously rather difficult instances compared to the current state-of-the-art EAX algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。