The inefficiency of genetic programming for symbolic regression

Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

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

Abstract

We analyse the search behaviour of genetic programming (GP) for symbolic regression (SR) in search spaces that are small enough to allow exhaustive enumeration, and use an improved exhaustive symbolic regression algorithm to generate the set of semantically unique expression structures, which is orders of magnitude smaller than the original SR search space. The efficiency of GP and a hypothetical random search in this set of unique expressions is compared, whereby the efficiency is quantified via the number of function evaluations performed until a given error threshold is reached, and the percentage of unique expressions evaluated during the search after simplification to a canonical form. The results for two real-world datasets with a single input variable show that GP in such limited search space explores only a small fraction of the search space, and evaluates semantically equivalent expressions repeatedly. GP has a smaller success probability than the idealised random search for such small search spaces.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVIII
Subtitle of host publication18th International Conference, PPSN 2024, Hagenberg, Austria, September 14–18, 2024, Proceedings, Part I
EditorsMichael Affenzeller, Stephan M. Winkler, Anna V. Kononova, Heike Trautmann, Tea Tušar, Penousal Machado, Thomas Bäck
PublisherSpringer
Pages273-289
Number of pages17
ISBN (Electronic)9783031700552
ISBN (Print)9783031700545
DOIs
Publication statusPublished - 7 Sept 2024
EventParallel Problem Solving from Nature – PPSN XVIII: 18th International Conference, PPSN 2024 - Hagenberg, Austria
Duration: 14 Sept 202418 Sept 2024
https://ppsn2024.fh-ooe.at/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume15148
ISSN (Print)0302-9743
NamePPSN: International Conference on Parallel Problem Solving from Nature
PublisherSpringer

Conference

ConferenceParallel Problem Solving from Nature – PPSN XVIII: 18th International Conference, PPSN 2024
Country/TerritoryAustria
CityHagenberg
Period14/09/2418/09/24
Internet address

Keywords

  • Symbolic regression
  • Genetic programming
  • Search space

Fingerprint

Dive into the research topics of 'The inefficiency of genetic programming for symbolic regression'. Together they form a unique fingerprint.

Cite this