Genetic Programming and Evolutionary
Generalization Ibrahim Kushchu · 2002
In genetic programming (GP), learning problems can be classified broadly into two types: those using data sets, as in supervised learning, and those using an environment as a source of feedback. Recently, an increasing amount of research has con- centrated on the robustness or generalization ability of the pro- grams evolved using GP. While some of the researchers report on the brittleness of the solutions evolved, others proposed methods of promoting robustness/generalization. It is important that these methods are not ad hoc and are applicable to other experimental setups. In this paper, learning concepts from traditional machine learning and a brief review of research on generalization in GP are presented. The paper also identifies problems with brittleness of solutions produced by GP and suggests a method for promoting ro- bustness/generalization of the solutions in simulating learning be- haviors using GP. The concept of generalization as used in the connectionist or symbolic learning research is similar to robustness, but is much broader and requires a formal methodology for the design and evaluation of the experiments. The established formalism of learning and generalization research of AI can provide a useful methodology for improving research on evolving robust pro- grams using GP. Specifically, such formalisms can be helpful in designing an evolutionary setup and objectively measuring the learning performance in terms of robustness or generaliza- tion. For example, an experiment on generalization may be best measured if it is conducted in two distinct stages: training and testing. Finding a solution using an evolutionary process can be seen as training and the generalization can subsequently be mea- sured by the performance of the learner (i.e., solution) during the testing process. A generalization-oriented experiment may also follow certain rules in selecting instances for training and testing (i.e., representativeness of the training cases and degree of overlapping between the two). The issue of generalization in GP has not received the at- tention it deserves. A common agreement is that researchers face overfitting (i.e., overtraining) and brittle solutions for the problems (see the review in Section V). This paper investigates generalization efforts in GP research and presents an empirical method for improving generalization performances of GP so- lutions. It starts by introducing the concept of learning and a computational learning framework. Next, it presents a critical review of generalization research in GP in terms of both su- pervised learning using data sets and simulations of learning in an environment. The review suggests that there is a growing need for improving approaches to promote generalization of so- lutions produced by GP. Then it investigates the questions raised in the literature (17), (15) with respect to the generalization of solutions to the artificial ant problem. Experimental results pre- sented in this paper show that evolving a solution for the ar- tificial ant problem based on a single environment may result in brittle solutions. The paper then presents a new approach to the simulation of the artificial ant problem. The results show that an environmental sampling can improve learning and re- sult in generalization within a particular class of environments. This approach is implemented in GP using a traditional machine learning framework.