Landscapes, operators and heuristic search

Heuristic search methods have been increasingly applied to combinatorial optimization problems. 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, a simple example will be used to illustrate the fact that the landscape structure changes with the operator; indeed, it often depends even on the way the operators are applied. Recent attention has focused on trying to better understand the nature of these "landscapes". Recent work 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 distance metric. In this paper, their work is developed by investigating the question of how landscapes change 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 a numerical assessment of the landscape. Other conclusions relate to the existence of ultra-metricity, and to the usefulness or otherwise of hybrid neighbourhood operators.