Repository logo
 

Dramatically faster Partition Crossover for the traveling salesman problem

Abstract

The Partition Crossover is a deterministic crossover operator for the Traveling Salesman Problem (TSP). It decomposes the union graph of two TSP solutions, A and B, into connected components known as AB-cycles, from which the lower-cost edges are selected and recombined to produce offspring. The operator finds the best offspring within a search space of 2k solutions in linear time, where k is the number of recombining components. We introduce Generalized Partition Crossover 3 (GPX3), a new implementation of Partition Crossover. GPX3 features a new algorithm to quickly find AB-cycles in the union graph. It also identifies additional recombining AB-cycles, expanding the reachable search space. We show that GPX3 runs in O(n) time and is more efficient and effective than previous implementations of Partition Crossover for the TSP.

Description

Rights Access

Subject

traveling salesman problem
combinatorial optimization
genetics algorithms
crossover operators

Citation

Associated Publications

Collections