A comparison of fitness-case sampling methods for genetic programming

Abstract

Genetic programming (GP) is an evolutionary computation paradigm for automatic program induction. GP has produced impressive results but it still needs to overcome some practical limitations, particularly its high computational cost, overfitting and excessive code growth. Recently, many researchers have proposed fitness-case sampling methods to overcome some of these problems, with mixed results in several limited tests. This paper presents an extensive comparative study of four fitness-case sampling methods, namely: Interleaved Sampling, Random Interleaved Sampling, Lexicase Selection and Keep-Worst Interleaved Sampling. The algorithms are compared on 11 symbolic regression problems and 11 supervised classification problems, using 10 synthetic benchmarks and 12 real-world data-sets. They are evaluated based on test performance, overfitting and average program size, comparing them with a standard GP search. Comparisons are carried out using non-parametric multigroup tests and post hoc pairwise statistical tests. The experimental results suggest that fitness-case sampling methods are particularly useful for difficult real-world symbolic regression problems, improving performance, reducing overfitting and limiting code growth. On the other hand, it seems that fitness-case sampling cannot improve upon GP performance when considering supervised binary classification.

Keywords:

• Genetic programming
• fitness-case sampling
• performance evaluation

Notes

No potential conflict of interest was reported by the authors.

1 Fitness-case sampling refers to the selection of a subset of fitness-cases, which is mostly the case for the methods presented in this study. Though, there is the possibility to consider the entire training set.

Additional information

Funding

First, second and fifth authors were supported by CONACYT (México) scholarships, respectively, [grant number 226981], [grant number 232288], [grant number 573397]. Funding for this work was provided by CONACYT Basic Science Research Project number [178323], DGEST (México) Research Project [5414.14-P], FP7-PEOPLE-2013-IRSES project ACOBSEC financed by the European Commission with contract number [612689] and CONACYT Project [FC-2015-2/944] “Aprendizaje evolutivo a gran escala".