zbMATH — the first resource for mathematics

A no-free-lunch theorem for non-uniform distributions of target functions. (English) Zbl 1079.90111
Summary: 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.

MSC:
 90C27 Combinatorial optimization 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text:
References:
 [2] English, T.M.: Evaluation of evolutionary and genetic optimizers: No free lunch, in L. J. Fogel, P. J. Angeline and T. Bäck (eds), Proceedings of the Fifth Annual Conference on Evolutionary Programming (EP V), 1996, pp. 163-169. [3] English, T. M.: Optimization is easy and learning is hard in the typical function, in A. Zalzala, C. Fonseca, J.-H. Kim and A. Smith (eds), Proceedings of the 2000 Congress on Evolutionary Computation (CEC 2000), 2000, pp. 924-931. [4] Igel, C. and Stagge, P.: Graph isomorphisms effect structure optimization of neural networks, in International Joint Conference on Neural Networks (IJCNN 2002), 2002, pp. 142-147. [7] Igel, C. and Toussaint, M.: Recent results on no-free-lunch theorems for optimization, arXiv preprint cs.NE/0303032, http://arxiv.org/abs/cs.NE/0303032, 2003. · Zbl 1162.68816 [10] Schumacher, C.: Fundamental limitations of search, Ph.D. thesis, University of Tennessee, 2000. [11] Schumacher, C., Vose, M. D. and Whitley, L. D.: The no free lunch and description length, in L. Spector, E. Goodman, A. Wu, W. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon and E. Burke (eds), Genetic and Evolutionary Computation Conference (GECCO 2001), 2001, pp. 565-570. [12] Streeter, M. J.: Two broad classes of functions for which a no free lunch result does not hold, in E. Cantú-Paz, J. A. Foster, K. Deb, D. Davis, R. Roy, U.-M. O?Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. Dowsland, N. Jonoska and J. Miller (eds), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), 2003, pp. 1418-1430.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.