A No-Free-Lunch theorem for non-uniform distributions of target functions

Authors: Christian Igel¹; Marc Toussaint²

Source: Journal of Mathematical Modelling and Algorithms, Volume 3, Number 4, January 2005 , pp. 313-322(10)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

The sharpened No-Free-Lunch-theorem (NFL-theorem) states that, regardless of the performance measure, the performance of all optimization algorithms averaged uniformly over any finite set F of functions is equal if and only if F is closed under permutation (c.u.p.). In this paper, we first summarize some consequences of this theorem, which have been proven recently: The number of subsets c.u.p. can be neglected compared to the total number of possible subsets. In particular, problem classes relevant in practice are not likely to be c.u.p. The average number of evaluations needed to find a desirable (e.g., optimal) solution can be calculated independent of the optimization algorithm in certain scenarios. Second, as the main result, the NFL-theorem is extended. Necessary and sufficient conditions for NFL-results to hold are given for arbitrary distributions of target functions. This yields the most general NFL-theorem for optimization presented so far.

Keywords: evolutionary computation; No-Free-Lunch theorem; 90C27; 68T20

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10852-005-2586-y

Affiliations: 1: Chair of Theoretical Biology, Institut für Neuroinformatik, Ruhr-Universität Bochum, 44780, Bochum, Germany, Email: christian.igel,marc.toussaint@neuroinformatik.rub.de 2: Chair of Theoretical Biology, Institut für Neuroinformatik, Ruhr-Universität Bochum, 44780, Bochum, Germany,

Publication date: 2005-01-01