Efficient AB-Cycle Fusion: Boosting GPX and Assessing Its Impact on EAX
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
Many highly effective solvers have been developed for the Traveling Salesperson Problem (TSP), among which the Edge Assembly Crossover (EAX) and the Lin-Kernighan-Helsgaun (LKH) heuristic are considered state of the art. In recent years, Generalized Partition Crossover (GPX) has emerged as a promising crossover operator that preserves all parental edges. It might thus be beneficial in situations in which EAX loses important information during the search. However, existing GPX variants lack a competitive implementation and are unable to reliably determine the feasibility of fused AB-cycles. In this work, we extend a recently proposed subtour-check procedure for AB-cycles to improve the evaluation of fused AB-cycles within GPX. Based on this extension, we develop a new GPX variant and integrate it directly into EAX. Unlike previous GPX variants, which rely on restrictive feasibility criteria such as equal connections or mirror-edge tests, our approach can correctly determine the feasibility of arbitrary fused AB-cycles. This overcomes a major limitation of previous GPX implementations. We evaluate the resulting algorithm on a well-established benchmark of evolved TSP instances and show that it outperforms vanilla EAX in several settings. To better understand the impact and limitations of our proposed check, we analyze the interaction between the two stages of EAX and the distribution of optimal edges in the population. Our experiments indicate that EAX sometimes removes optimal edges from the population during the first stage, thereby limiting the potential benefit of GPX in later stages. These findings provide new insight into the behavior of EAX and suggest promising directions for future research on crossover operators and population initialization.
Details
| Original language | English |
|---|---|
| Title of host publication | Parallel Problem Solving from Nature – PPSN XIX |
| Editors | Giovanni Iacca, Giorgia Nadizar, Anil Yaman, Doina Bucur, Antonio Della Cioppa, Ting Hu, Eric Medvet, Sarah L. Thomson |
| Pages | 298 - 314 |
| Number of pages | 17 |
| ISBN (electronic) | 978-3-032-36214-8 |
| Publication status | E-pub ahead of print - 25 Aug 2026 |
| Peer-reviewed | Yes |
Publication series
| Series | Lecture Notes in Computer Science |
|---|---|
| Volume | 16985 |
| ISSN | 0302-9743 |
External IDs
| ORCID | /0000-0003-2862-1418/work/226836108 |
|---|---|
| ORCID | /0000-0002-3571-667X/work/226837696 |
| Scopus | 105050251268 |
Keywords
ASJC Scopus subject areas
Keywords
- AB-cycles, EAX, Evolutionary Algorithm, GPX, TSP