TY - GEN
T1 - Free lunches for function and program induction
AU - Poli, Riccardo
AU - Graff, Mario
AU - McPhee, Nicholas Freitag
PY - 2009
Y1 - 2009
N2 - In this paper we prove that for a variety of practical problems and representations, there is a free lunch for search algorithms that specialise in the task of finding functions or programs that solve problems, such as genetic programming. In other words, not all such algorithms are equally good under all possible performance measures. We focus in particular on the case where the objective is to discover functions that fit sets of data-points - a task that we will call symbolic regression. We show under what conditions there is a free lunch for symbolic regression, highlighting that these are extremely restrictive.
AB - In this paper we prove that for a variety of practical problems and representations, there is a free lunch for search algorithms that specialise in the task of finding functions or programs that solve problems, such as genetic programming. In other words, not all such algorithms are equally good under all possible performance measures. We focus in particular on the case where the objective is to discover functions that fit sets of data-points - a task that we will call symbolic regression. We show under what conditions there is a free lunch for symbolic regression, highlighting that these are extremely restrictive.
KW - Genetic programming
KW - No-free Lunch
KW - Theory
UR - http://www.scopus.com/inward/record.url?scp=70349110962&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349110962&partnerID=8YFLogxK
U2 - 10.1145/1527125.1527148
DO - 10.1145/1527125.1527148
M3 - Conference contribution
AN - SCOPUS:70349110962
SN - 9781605584140
T3 - Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
SP - 183
EP - 194
BT - Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
T2 - 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
Y2 - 9 January 2009 through 11 January 2009
ER -