Authors: Droste, Stefan
Jansen, Thomas
Wegener, Ingo
Title: Optimization with Randomized Search Heuristics : The (A)NFL Theorem,Realistic Scenarios, and Difficult Functions
Language (ISO): en
Abstract: The No Free Lunch (NFL)theorem due to Wolpert and Macready (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.
URI: http://hdl.handle.net/2003/5394
http://dx.doi.org/10.17877/DE290R-5645
Issue Date: 2001-10-17
Provenance: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
ci91.pdfDNB201.28 kBAdobe PDFView/Open
ci91.ps411.91 kBPostscriptView/Open


This item is protected by original copyright



This item is protected by original copyright rightsstatements.org