Statistical analysis of local search landscapes

Abstract

This paper discusses the application of some statistical estimation tools in trying to understand the nature of the combinatorial landscapes induced by local search methods. One interesting property of a landscape is the number of optima that are present. In this paper we show that it is possible to compute a confidence interval on the number of independent local searches needed to find all optima. By extension, this also expresses the confidence that the global optimum has been found. In many cases, this confidence may be too low to be acceptable, but it is also possible to estimate the number of optima that exist. Theoretical analysis and empirical studies are discussed, which show that it may be possible to obtain a fairly accurate picture of this property of a combinatorial landscape. The approach is illustrated by analysis of an instance of the flowshop scheduling problem.

Keywords:

• heuristics
• landscapes
• local optima
• statistical estimation