Fitness functions based on test cases are very common in Genetic Programming (GP). This process can be assimilated to a learning task, with the inference of models from a limited number of samples. This paper is an investigation on two methods to improve generalization in GP-based learning: 1) the selection of the best-of-run individuals using a three data sets methodology, and 2) the application of parsimony pressure in order to reduce the complexity of the solutions. Results using GP in a binary classification setup show that while the accuracy on the test sets is preserved, with less variances compared to baseline results, the mean tree size obtained with the tested methods is significantly reduced.
Genetic programming is distinguished from other evolutionary algorithms in that it uses tree representations of variable size instead of linear strings of fixed length. The flexible representation scheme is very important because it allows the underlying structure of the data to be discovered automatically. One primary difficulty, however, is that the solutions may grow too big without any improvement of their generalization ability. In this article we investigate the fundamental relationship between the performance and complexity of the evolved structures. The essence of the parsimony problem is demonstrated empirically by analyzing error landscapes of programs evolved for neural network synthesis. We consider genetic programming as a statistical inference problem and apply the Bayesian model-comparison framework to introduce a class of fitness functions with error and complexity terms. An adaptive learning method is then presented that automatically balances the model-complexity factor to evolve parsimonious programs without losing the diversity of the population needed for achieving the desired training accuracy. The effectiveness of this approach is empirically shown on the induction of sigma-pi neural networks for solving a real-world medical diagnosis problem as well as benchmark tasks. Genetic Programming (GP) uses variable size representations as programs. Size becomes an important and interesting emergent property of the structures evolved by GP. The size of programs can be both a controlling and a controlled factor in GP search. Size influences the efficiency of the search process and is related to the generality of solutions. This paper analyzes the size and generality issues in standard GP and GP using subroutines and addresses the question whether such an analysis can help control the search process. We relate the size, generalization and modularity issues for programs evolved to control an agent in a dynamic and non-deterministic environment, as exemplified by the Pac-Man game. The rapid growth of program code is an important problem in genetic programming systems. In the present paper we investigate a selection scheme based on multiobjective optimization. Since we want to obtain accurate and small solutions, we reformulate this problem as multiobjective optimization. We show that selection based on the Pareto nondomination criterion reduces code growth and processing time without significant loss of solution accuracy.    A common data mining heuristic is, "when choosing between models with the same training error, less complex models should be preferred as they perform better on unseen data". This heuristic may not always hold. In genetic programming a preference for less complex models is implemented as: (i) placing a limit on the size of the evolved program; (ii) penalizing more complex individuals, or both. The paper presents a GP-variant with no limit on the complexity of the evolved program that generates highly accurate models on a common dataset.  Many KDD systems incorporate an implicit or explicit preference for simpler models, but this use of “Occam‘s razor” has been strongly criticized by several authors (e.g., Schaffer, 1993s Webb, 1996). This controversy arises partly because Occam‘s razor has been interpreted in two quite different ways. The first interpretation (simplicity is a goal in itself) is essentially correct, but is at heart a preference for more comprehensible models. The second interpretation (simplicity leads to greater accuracy) is much more problematic. A critical review of the theoretical arguments for and against it shows that it is unfounded as a universal principle, and demonstrably false. A review of empirical evidence shows that it also fails as a practical heuristic. This article argues that its continued use in KDD risks causing significant opportunities to be missed, and should therefore be restricted to the comparatively few applications where it is appropriate. The article proposes and reviews the use of domain constraints as an alternative for avoiding overfitting, and examines possible methods for handling the accuracy–comprehensibility trade-off.