Optimization, block designs and No Free Lunch theorems

Reference:

Evan Griffiths and Pekka Orponen. Optimization, block designs and No Free Lunch theorems. Information Processing Letters, 94(2):55–61, April 2005.

Abstract:

We study the precise conditions under which all optimization strategies for a given family of finite functions yield the same expected maximisation performance, when averaged over a uniform distribution of the functions. In the case of bounded-length searches in a family of Boolean functions, we provide tight connections between such ``No Free Lunch'' conditions and the structure of -designs and -wise balanced designs for arbitrary values . As a corollary, we obtain a nontrivial family of -variate Boolean functions that satisfies the ``No Free Lunch`` condition with respect tosearches of length . Modifying the construction, we also obtain nontrivial ``No Free Lunch`` families of functions with large ranges.

Keywords:

theory of computation, combinatorial problems, optimization, No Free Lunch theorems, combinatorial designs

Suggested BibTeX entry:

@article{GrOr05,
    author = {Evan Griffiths and Pekka Orponen},
    journal = {Information Processing Letters},
    month = {April},
    number = {2},
    pages = {55--61},
    title = {Optimization, block designs and {N}o {F}ree {L}unch theorems},
    volume = {94},
    year = {2005},
}