Statistical Analysis of Search Spaces

In contrast to the classical theoretical computational complexity point of view summarized in Chapter 1 according to which a given problem belongs to a certain complexity class, the common practice in the metaheuristics community is to consider the specific search space of a given problem instance or class of problem instances (see Chapter 2). This is natural to the extent that metaheuristics can be seen as clever techniques that exploit the search space structure of a problem instance in order to find a quality solution in reasonable time. And it is not in contradiction with the fact that a problem may be classified as being hard in general as, in practice, not all instances will be equally difficult to solve, as we have learned in the chapter on phase transitions in computational hardness, where we have seen that intractable problems may possess easy-to-solve instances under some conditions. It therefore becomes important in the field of metaheuristics to be able to build tools that allow us to obtain quantitative measures of the main features of a search space