Conference Paper (published)
Details
Citation
Woodward J & Neil JR (2003) No free lunch, program induction and combinatorial problems. In: Ryan C, Soule T, Keijzer M, Tsang E, Poli R & Costa E (eds.) Genetic Programming: 6th European Conference, EuroGP 2003 Essex, UK, April 14–16, 2003 Proceedings. Lecture Notes in Computer Science, 2610. 6th European Conference, EuroGP 2003, Essex, UK, 14.04.2003-16.04.2003. Berlin Heidelberg: Springer, pp. 475-484. http://link.springer.com/chapter/10.1007/3-540-36599-0_45#; https://doi.org/10.1007/3-540-36599-0_45
Abstract
This paper has three aims. Firstly, to clarify the poorly understood No Free Lunch Theorem (NFL) which states all search algorithms perform equally. Secondly, search algorithms are often applied to program induction and it is suggested that NFL does not hold due to the universal nature of the mapping between program space and functionality space. Finally, NFL and combinatorial problems are examined. When evaluating a candidate solution, it can be discarded without being fully examined. A stronger version of NFL is established for this class of problems where the goal is to minimize a quantity.
| Status | Published |
|---|---|
| Title of series | Lecture Notes in Computer Science |
| Number in series | 2610 |
| Publication date | 31/12/2003 |
| Publication date online | 30/04/2003 |
| Publisher | Springer |
| Publisher URL | http://link.springer.com/chapter/10.1007/3-540-36599-0_45# |
| Place of publication | Berlin Heidelberg |
| ISSN of series | 0302-9743 |
| ISBN | 978-3-540-00971-9 |
| Conference | 6th European Conference, EuroGP 2003 |
| Conference location | Essex, UK |
| Dates | – |