Landscapes, operators and heuristic search

Heuristic search methods have been increasingly applied to combinatorial optimizationproblems. While a specific problem defines a unique search space, different “landscapes”are created by the different heuristic search operators used to search it. In this paper, asimple example will be used to illustrate the fact that the landscape structure changes withthe operator; indeed, it often depends even on the way the operators are applied. Recentattention has focused on trying to better understand the nature of these “landscapes”. Recentwork by Boese et al. [2] has shown that instances of the TSP are often characterised by a“big valley” structure in the case of a 2‐opt exchange operator, and a particular distancemetric. In this paper, their work is developed by investigating the question of how landscapeschange under different search operators in the case of the n/m/P/C max flowshop problem.Six operators and four distance metrics are defined, and the resulting landscapes examined.The work is further extended by proposing a statistical randomisation test to provide anumerical assessment of the landscape. Other conclusions relate to the existence of ultra‐metricity,and to the usefulness or otherwise of hybrid neighbourhood operators. Copyright Kluwer Academic Publishers 1999