Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
New EAX Crossover for Large TSP Instances
verfasst von : Yuichi Nagata
Erschienen in: Parallel Problem Solving from Nature - PPSN IX
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose an evolutionary algorithm (EA) that applies to the traveling salesman problem (TSP). The EA uses edge assembly crossover (EAX), which is known to be efficient and effective for solving TSPs. Recently, a fast implementation of EAX and an effective technique for preserving population diversity were proposed. This makes it possible to compare the EA with EAX comparable to state-of-the-art TSP heuristics based on Lin-Karnighan heuristics. We further improved the performance of EAs with EAX, especially for large instances of more than 10,000 cities. Our method can find optimal solutions for instances of up to 24978 cities within a day using a single Itanium 2 1.3-GHz processor. Moreover, our EA found three new best tours for unsolved national TSP instances in a reasonable computation time.