On classes of functions for which No Free Lunch results hold

摘要: The No Free Lunch (NFL) theorems for combinatorial optimization state, roughly speaking, that all search algorithms have the same average performance over possible objective functions f : X → Y, where space as well cost-value Y are finite sets [6]. However, it has been argued in practice one does not need an algorithm performs on functions, but only a subset arises from constraints of real-world problems. For example, shown pseudo-Boolean restrictions complexity can lead to subsets which some perform better than others (in [5] is defined terms number local minima and [1, 2] based size smallest ordered binary decision diagram, OBDD, representing function). Recently, sharpened version NFL theorem proven states results hold any F set if closed under permutation (c.u.p.) [4]. Based this important result, we derive classes simply by showing these c.u.p. This leads main result paper: It fraction negligibly small. Arguments given why think resulting problems likely be In following section, give basic definitions concisely restate Then Finally, discuss observations regarding structured spaces closure permutation.