A No-Free-Lunch theorem for non-uniform distributions of target functions
Authors: Christian Igel1; Marc Toussaint2
Source: Journal of Mathematical Modelling and Algorithms, Volume 3, Number 4, January 2005 , pp. 313-322(10)
Publisher: Springer
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
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: 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,
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
Click here for Page Help