Partial neighborhoods of the Traveling Salesman Problem

Citation

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. http://dl.acm.org/citation.cfm?id=2001649; https://doi.org/10.1145/2001576.2001649

Abstract
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.