Classes of problems in the black box scenario
Yossi Borenstein, Riccardo Poli · 2006
The no-free-lunch theorems (NFLTs) do not consider explicitly the structure of problems. In [1] we gave a formal definition of structure. We showed that many metaheuristics have identical performance on problems which belong to the same structural class. In this paper, we define a notion of a distance between fitness functions. We argue that an algorithm cannot be efficient on a class of problems if the distance between the fitness function associated with instances of that class is too big. In [2] we corroborate our ideas using several problems.