On the futility of blind search: an algorithmic view of "no free lunch". Export

@article{citeulike:202214, abstract = {The paper is in three parts. First, we use simple adversary arguments to redevelop and explore some of the no-free-lunch (NFL) theorems and perhaps extend them a little. Second, we clarify the relationship of NFL theorems to algorithm theory and complexity classes such as NP. We claim that NFL is weaker in the sense that the constraints implied by the conjectures of traditional algorithm theory on what an evolutionary algorithm may be expected to accomplish are far more severe than those implied by NFL. Third, we take a brief look at how natural evolution relates to computation and optimization. We suggest that the evolution of complex systems exhibiting high degrees of orderliness is not equivalent in difficulty to optimizing hard (in the complexity sense) problems, and that the optimism in genetic algorithms (GAs) as universal optimizers is not justified by natural evolution. This is an informal tutorial paper--most of the information presented is not formally proven, and is either "common knowledge" or formally proven elsewhere. Some of the claims are intuitions based on experience with algorithms, and in a more formal setting should be classified as conjectures.}, address = {Department of Computing Science, University of Alberta, Edmonton, Canada. joe@cs.ualberta.ca}, author = {Culberson, J. C.}, citeulike-article-id = {202214}, citeulike-linkout-0 = {http://view.ncbi.nlm.nih.gov/pubmed/10021743}, citeulike-linkout-1 = {http://www.hubmed.org/display.cgi?uids=10021743}, issn = {1063-6560}, journal = {Evol Comput}, keywords = {evolutionarycomputation, nofreelunch}, number = {2}, pages = {109--127}, posted-at = {2005-05-18 00:27:51}, priority = {2}, title = {On the futility of blind search: an algorithmic view of "no free lunch".}, url = {http://view.ncbi.nlm.nih.gov/pubmed/10021743}, volume = {6}, year = {1998} }

TY - JOUR ID - citeulike:202214 L3 - citeulike-article-id:202214 N2 - The paper is in three parts. First, we use simple adversary arguments to redevelop and explore some of the no-free-lunch (NFL) theorems and perhaps extend them a little. Second, we clarify the relationship of NFL theorems to algorithm theory and complexity classes such as NP. We claim that NFL is weaker in the sense that the constraints implied by the conjectures of traditional algorithm theory on what an evolutionary algorithm may be expected to accomplish are far more severe than those implied by NFL. Third, we take a brief look at how natural evolution relates to computation and optimization. We suggest that the evolution of complex systems exhibiting high degrees of orderliness is not equivalent in difficulty to optimizing hard (in the complexity sense) problems, and that the optimism in genetic algorithms (GAs) as universal optimizers is not justified by natural evolution. This is an informal tutorial paper--most of the information presented is not formally proven, and is either "common knowledge" or formally proven elsewhere. Some of the claims are intuitions based on experience with algorithms, and in a more formal setting should be classified as conjectures. IS - 2 JF - Evol Comput SN - 1063-6560 AD - Department of Computing Science, University of Alberta, Edmonton, Canada. joe@cs.ualberta.ca EP - 127 TI - On the futility of blind search: an algorithmic view of "no free lunch". VL - 6 SP - 109 KW - evolutionarycomputation KW - nofreelunch AU - Culberson, JC PY - 1998/// UR - http://view.ncbi.nlm.nih.gov/pubmed/10021743 ER -