A Comprehensive Analysis of Down-sampling for Genetic Programming-based Program Synthesis
Ryan Boldi, Ashley Bao, Martin Briesch, Thomas Helmuth, Dominik Sobania, Lee C. Spector, Alexander Lalejini · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2024
Genetic programming systems typically require large computational resource investments for training-set evaluations. Down-sampling these sets has proven to decrease costs and improve problem-solving success, particularly with the lexicase parent selection algorithm. We investigated its effectiveness when applied to three other common selection methods and across various program synthesis problems. Our findings show that down-sampling notably enhances all three methods, indicating its potential broad applicability. Additionally, we found informed down-sampling to be more successful than its random counterpart, particularly in selection schemes maintaining diversity like lexicase selection. We conclude that down-sampling is a promising strategy for test-based genetic programming problems, irrespective of selection scheme.