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. 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/Cmax 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 ultrametricity, and to the usefulness or otherwise of hybrid neighbourhood operators.