Free lunches for function and program induction

Riccardo Poli, Mario Graff, Nicholas Freitag McPhee

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    17 Scopus citations

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
    Pages183-194
    Number of pages12
    DOIs
    StatePublished - Sep 21 2009
    Event10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09 - Orlando, FL, United States
    Duration: Jan 9 2009Jan 11 2009

    Publication series

    NameProceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09

    Conference

    Conference10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
    CountryUnited States
    CityOrlando, FL
    Period1/9/091/11/09

    Keywords

    • Genetic programming
    • No-free Lunch
    • Theory

    Fingerprint Dive into the research topics of 'Free lunches for function and program induction'. Together they form a unique fingerprint.

    Cite this