Conference Proceeding

Partial neighborhoods of the Traveling Salesman Problem



Whitley D & Ochoa G (2011) Partial neighborhoods of the Traveling Salesman Problem. In: GECCO'11 - Genetic and Evolutionary Computation Conference Proceedings. GECCO '11 - 13th annual conference on Genetic and evolutionary computation, Dublin, Ireland, 12.07.2011-16.07.2011. New York, NY, USA: ACM, pp. 529-536.;

The Traveling Salesman Problem (TSP) is known to display an elementary landscape under all k-opt move operators. Previous work has also shown that partial neighborhoods may exist that retain some properties characteristic of elementary landscapes. For a tour of n cities, we show that the 2-opt neighborhood can be decomposed into n/2-1 partial neighborhoods. While this paper focuses on the TSP, it also introduces a more formal treatment of partial neighborhoods which applies to all elementary landscapes. Tracking partial neighborhood averages in elementary landscapes requires partitioning the cost matrix. After every move in the search space, the relevant partitions must be updated. However, just as the evaluation function allows a partial update for the TSP, there also exists a partial update for the cost matrix partitions. By only looking at a subset of the partial neighborhoods we can further reduce the cost of updating the cost matrix partitions.

Publication date31/12/2011
Publication date online31/07/2011
Related URLs
Publisher URL
Place of publicationNew York, NY, USA
ConferenceGECCO '11 - 13th annual conference on Genetic and evolutionary computation
Conference locationDublin, Ireland

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Research centres/groups