A review of metrics on permutations for search landscape analysis

Search landscape analysis has become a central tool for analysing the dependency of the performance of stochastic local search algorithms on structural aspects of the spaces being searched. Central to search landscape analysis is the notion of distance between candidate solutions. This distance depends on some underlying basic operator and it is defined as the minimum number of operations that need to be applied to one candidate solution for transforming it into another one. For operations on candidate solutions that are represented by permutations, in almost all researches on search landscape analysis surrogate distance measures are applied, although efficient algorithms exist in many cases for computing the exact distances. This discrepancy is probably due to the fact that these efficient algorithms are not very widely known. In this article, we review algorithms for computing distances on permutations for the most widely applied operators and present simulation results that compare the exact distances to commonly used approximations. © 2005 Elsevier Ltd. All rights reserved.