×

zbMATH — the first resource for mathematics

Optimization with randomized search heuristics – the (A)NFL theorem, realistic scenarios, and difficult functions. (English) Zbl 1061.68145
Summary: The No Free Lunch (NFL) theorem due to D. H. Wolpert and W. G. Macready [IEEE Trans. Evol. Comput. 1, No. 1, 67–82 (1997)] has led to controversial discussions on the usefulness of randomized search heuristics, in particular, evolutionary algorithms. Here a short and simple proof of the NFL theorem is given to show its elementary character. Moreover, the proof method leads to a generalization of the NFL theorem. Afterwards, realistic complexity theoretical-based scenarios for black box optimization are presented and it is argued why NFL theorems are not possible in such situations. However, an Almost No Free Lunch (ANFL) theorem shows that for each function which can be optimized efficiently by a search heuristic there can be constructed many related functions where the same heuristic is bad. As a consequence, search heuristics use some idea how to look for good points and can be successful only for functions “giving the right hints”. The consequences of these theoretical considerations for some well-known classes of functions are discussed.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W20 Randomized algorithms
90C59 Approximation methods and heuristics in mathematical programming
Software:
Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Culberson, J.C., On the futility of blind search: an algorithmic view of no free lunch, Evol. comput., 6, 2, 109-127, (1998)
[2] Droste, S.; Jansen, T.; Wegener, I., Perhaps not a free lunch but at least a free appetizer, (), 833-839
[3] Fogel, D., Evolutionary computation: toward a new philosophy of machine intelligence, (1995), IEEE Press Piscataway, NJ
[4] F. Glover, M. Laguna, Tabu search, in: C. Reeves (Ed.), Modern Heuristic Techniques for Combinatorial Problems, Scientific Publications, Oxford, 1993.
[5] Goldberg, D., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056
[6] Hagerup, T.; Rüb, C.R., A guided tour of Chernoff bounds, Inform. process. lett., 33, 305-308, (1989) · Zbl 0702.60021
[7] Hochbaum, D.S., Approximation algorithms for NP-hard problems, (1996), PWS Publishing Company Boston, MA · Zbl 1368.68010
[8] Li, M.; Vitányi, P., An introduction to Kolmogorov complexity and its applications, (1993), Springer Berlin · Zbl 0805.68063
[9] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge University Press Cambridge · Zbl 0849.68039
[10] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
[11] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1998), Dover Englewood Cliffs, NJ · Zbl 0944.90066
[12] Rabani, Y.; Rabinovich, Y.; Sinclair, A., A computational view of population genetics, Random struct. alg., 12, 4, 314-334, (1995)
[13] N. Radcliffe, P. Surry, Fundamental limitations on search algorithms: evolutionary computing in perspective, in: J. van Leeuwen (Ed.), Lecture Notes in Computer Science, Vol. 1000, Springer, Berlin, 1995.
[14] U. Schöning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, in: Proc. 40th Ann. IEEE Symp. on Foundations of Computer Science (FOCS ’99), IEEE Press, Piscataway, NJ, 410-414.
[15] Schwefel, H.-P., Evolution and optimum seeking, (1995), Wiley New York
[16] van Laarhoven, P.; Aarts, E., Simulated annealing: theory and practice, (1987), Kluwer Academic Publishers Dordrecht · Zbl 0643.65028
[17] D.L. Whitley, Permutations, in: T. Bäck, D.B. Fogel, Z. Michalewicz (Eds.), Handbook of Evolutionary Computation, C1.4, Institute of Physics Publishing and Oxford University Press, Bristol, New York, 1997, 1-8.
[18] Wolpert, D.; Macready, W., No free lunch theorems for optimization, IEEE trans. evol. comput., 1, 1, 67-82, (1997)
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.