2003/03/31 by Christian Igel, Igel, Christian, Marc Toussaint +1
Computer Science · Mathematics · Physics and Astronomy · #Adaptation and Self-Organizing Systems (nlin.AO) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #G.1.6 #Neural and Evolutionary Computing (cs.NE) #Optimization and Control (math.OC) #cs.NE #math.OC #nlin.AO
paper · pdf · doi:10.48550/arxiv.cs/0303032
10 pages, LaTeX, see http://www.neuroinformatik.rub.de/PROJECTS/SONN/
arxiv created 2003/03/31 · arxiv updated 2009/11/30
The sharpened No-Free-Lunch-theorem (NFL-theorem) states that the performance of all optimization algorithms averaged over any finite set F of functions is equal if and only if F is closed under permutation (c.u.p.) and each target function in F is equally likely. In this paper, we first summarize some consequences of this theorem, which have been proven recently: The average number of evaluations needed to find a desirable (e.g., optimal) solution can be calculated; the number of subsets c.u.p. can be neglected compared to the overall number of possible subsets; and problem classes relevant in practice are not likely to be c.u.p. Second, as the main result, the NFL-theorem is extended. Necessary and sufficient conditions for NFL-results to hold are given for arbitrary, non-uniform distributions of target functions. This yields the most general NFL-theorem for optimization presented so far.