MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENSE

MILITARY TECHNICAL ACADEMY

NGUYEN THI HIEN
A STUDY OF GENERALIZATION
IN GENETIC PROGRAMMING THE THESIS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY
IN MATHEMATICS



Specialized in: Applied Mathematics and Computer Science
Code: 60 46 01 10
THE THESIS IS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS
FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN MATHEMATICS

ACADEMIC SUPERVISORS
:
1.
Assoc/Prof. Dr. Nguyen Xuan Hoai
2. Prof. Dr. R.I. (Bob) McKay
Hanoi - 2014
i
Abstract
Genetic Programming (GP) is a meta-heuristic technique that simulates biological evolu-
tion. GP differs to other Evolutionary Algorithms (EAs) in that it generates solutions to
problems in the form of computer programs. The quality criterion for each individual is
often referred to as fitness in EAs and it is with which we determine which individuals

line research chats. Working with him, I have learnt how to do research systematically. In
particular, the leaders of the Department of Software Engineering and Faculty of Informa-
tion Technology, Military Technical Academy have frequently supported my research with
regards to facilities and materials for running the experiments. Dr. Nguyen Quang Uy has
discussed a number of issues related to this research with me. I would like to thank him
for his thorough comments and suggestions on my research.
I also would like to acknowledge the supports from my family, especially my parents,
Nguyen Van Hoan and Nguyen Thi Quy, who have worked hard and always believed
strongly in their children and to my husband, Nguyen Hai Trieu for sharing happiness and
difficulty in the life with me. To my beloved daughter Nguyen Thi Hai Phuong, who was
born before this thesis was completed, I would like to express my thanks for being such a
good girl always cheering me up.
i
Contents
Abstract ii
List of Figures v
List of Tables vii
Abbreviations ix
0.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.2 Research Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.3 Contributions of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1 Backgrounds 6
1.1 Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Representation, Initialization and Operators in GP . . . . . . . . . 7
1.1.2 Some Variants of GP . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 An Example of Problem Domain . . . . . . . . . . . . . . . . . . . . . . . 19
1.3 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 GP and Machine Learning Issues . . . . . . . . . . . . . . . . . . . . . . . 21
1.4.1 Search Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.1.2 The Initial Sample Set Size . . . . . . . . . . . . . . . . . . . . . . 84
4.1.3 The Number of Learning Layers . . . . . . . . . . . . . . . . . . . . 86
4.1.4 The Stopping Criterion for Each Layer . . . . . . . . . . . . . . . . 86
4.2 Experimental Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2.1 Data Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2.2 GP Systems Configurations . . . . . . . . . . . . . . . . . . . . . . 87
4.3 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.1 Learning Effectiveness Comparison . . . . . . . . . . . . . . . . . . 89
4.3.2 Learning Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.3.3 Solution Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3.4 Distribution of Best Solutions by Layers . . . . . . . . . . . . . . . 93
4.3.5 Synergies between System Components . . . . . . . . . . . . . . . . 94
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5 Conclusions and Future Work 99
5.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Bibliography 104
iv
List of Figures
1.1 GP’s main loop [57] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 GP expression tree representing max(x*x,x+3y). [57] . . . . . . . . . . . . . 8
1.3 Creation of a full tree having maximum depth 2 (and therefore a total of
seven nodes) using the Full initialisation method (t=time). [57] . . . . . . . 10
1.4 Creation of a five node tree using the Grow initialisation method with a
maximum depth of 2 (t=time). A terminal is chosen at t = 2, causing
the left branch of the root to be terminated at that point even though the
maximum depth has not been reached. [57] . . . . . . . . . . . . . . . . . . 12
1.5 Example of subtree crossover. . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Example of subtree mutation. [57] . . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Idealized training and validation error curves. Vertical axis: errors; hori-

Tar vs GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.6 p-value of complexity of VF, OF, True Adap stopping criterion and Tar vs
GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.7 Relative Generalization Errors and Run Time of OF, VF and True Adap
stopping criterion (vs GP) . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.8 Generalization error and run time of GL, PQ and UP stopping criterion . . 66
3.9 Size of the best individual of GL, PQ and UP stopping criterion . . . . . . 67
3.10 p-value of GL, PQ and UP stopping criterion vs GP . . . . . . . . . . . . . 68
vii
3.11 p-value of size of best individual of comparison GL, PQ and UP stopping
criterion with GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.12 Relative Generalization Errors and Run Time of GL, PQ and UP stopping
criterion (vs GP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.13 p-value of GE, run time and size of best solution of True Adap, PQ vs Tarpeian 77
4.1 Data Sets for the Test Functions. . . . . . . . . . . . . . . . . . . . . . . . 88
4.2 Evolutionary Parameter Settings for the Genetic Programming Systems . . 89
4.3 Mean and SD of Generalization Error, GPLL and GP (14 Problems) . . . . 90
4.4 Relative Average Generalization Errors and p-values (GPLL vs GP) (14
Problems) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.5 Mean Run Time, GPLL and GP (14 Problems) . . . . . . . . . . . . . . . 91
4.6 Relative Run Times and p-values (GPLLs vs GP) (14 Problems) . . . . . . 92
4.7 Mean Solution Size and p-values, GPLL vs GP (14 Problems) . . . . . . . 93
4.8 Number of End-of-run Best Solutions First Found by GPLL in Each Layer 94
4.9 Average Generalization Error on 14 Problems . . . . . . . . . . . . . . . . 95
4.10 Average Run Time of All Systems . . . . . . . . . . . . . . . . . . . . . . . 96
4.11 Average Size of Solutions Found by all Systems . . . . . . . . . . . . . . . 97
viii
Abbreviations
Abbreviation Meaning
ARMA AutoregressiveMoving-Average

learning machine, has not been taken the attention that it deserves. This thesis focuses on
the generalization aspect of GP and proposes mechanisms to improve GP generalization
ability.
1
0.1. MOTIVATIONS
0.1 Motivations
GP is one of the evolutionary algorithms (EAs). The common underlying idea behind all
EA techniques is the same: given a population of individuals the environmental pressure
causes natural selection (survival of the fittest) and this causes a rise in the fitness of the
population. Given a quality function to be maximised we can randomly create a set of
candidate solutions, i.e., elements of the function’s domain, and apply the quality function
as an abstract fitness measure - the higher the better. Based on this fitness, some of the
better candidates are chosen to seed the next generation by applying recombination and/or
mutation to them. Recombination is an operator applied to two or more selected candidates
(the so-called parents) and results one or more new candidates (the children). Mutation
is applied to one candidate and results in one new candidate. Executing recombination
and mutation leads to a set of new candidates (the offspring) that compete - based on
their fitness (and possibly age) - with the old ones for a place in the next generation. This
process can be iterated until a candidate with sufficient quality (a solution) is found or a
previously set computational limit is reached. GP has been proposed as a machine learning
(ML) method [53], and solutions to various learning problems are sought by means of an
evolutionary process of program discovery. Since GP often tackles ML issues, generalization
that is synonymous with robustness has been the desirable property at the end of the GP
evolutionary process. The main goal when using GP or other ML techniques is not only to
create a program that exactly cover the training examples (as in many GP applications so
far), but also to have a good generalization ability: for unseen and future samples of data,
the program should output values that closely resemble the underlying function. Although,
recently, the issue of generalization in GP has received more attention than it deserves,
the use of more traditional machine learning techniques has been rather limited. It is
strange that generalization has been an old time studied topic in machine learning with

and operators as well as some benchmark problem domains (some are used for the ex-
periments in this thesis). Two important research issues and a metaphor of GP search
are then discussed. Next, the major issues of GP are discussed especially when the GP
is considered as a machine learning system. It first overviews the approaches proposed
in the literature that help to improve the generalization ability of GP. Then, the solution
complexity (code bloat), in the particular context of GP, and its relations to GP learning
performance (generalization, training time, solution comprehensibility) are discussed.
Chapter 2 provides a backgrounds on a number of concepts and techniques subsequently
used in the thesis for improving GP learning performance. They include progressive sam-
pling, layer learning, and early stopping in machine learning.
Chapter 3 presents one of the main contributions of the thesis. It proposes some crite-
ria used to determine when to stop the training of GP with an aim to avoid over-fitting.
Experiments are conducted to assess the effectiveness of the proposed early stopping crite-
ria. The results emphasise that GP with early stopping could find solutions with at least
similar generalization errors with standard GP but in much shorter training time and lower
complexity of solutions.
Chapter 4 develops a learning framework for GP that is based layer learning and pro-
gressive sampling. The results show that the solutions of GP with progressive sampling
significantly reduce in size and the training time is much faster when compared to standard
4
0.4. ORGANIZATION OF THE THESIS
GP while the generalization error of the obtained solutions is often smaller.
Chapter 5 concludes the thesis summarizing the main results and proposing suggestions
for future works that extend the research in this thesis.
5
Chapter 1
Backgrounds
GP [53] is an evolutionary algorithm (EA) that uses either a procedural or a functional
representation. This chapter describes the representation and the specific algorithm com-
ponents used in the canonical version of GP. The basics of GP are initially presented,

(subsection 1.1.1.3) as well as recombination and mutation(subsection 1.1.1.4) are used to
create the new individuals in the standard GP (as proposed in [53]).
7
1.1. GENETIC PROGRAMMING
1.1.1.1 Representation
Traditionally, GP programs are expressed as expression trees. Figure 1.2 shows, for ex-
ample, the tree representation of the program max(x*x,x+3*y). The variables and
constants in the program (x, y, and 3), are called terminals in GP, which are the leaves
of the tree. The arithmetic operations (+, *, and max) are internal nodes (called func-
tions in the GP literature). The sets of allowed functions and terminals together form the
primitive symbol set of a GP system.
Fig. 1.2: GP expression tree representing max(x*x,x+3y). [57]
The terminal set The terminal set consists of all inputs to GP programs (individuals),
constants supplied to GP programs, and the zero-argument functions with side-effects
executed by GP programs.
Inputs, constants and other zero-argument nodes are called terminals or leaves as they
appear at the frontier of expression tree-based programs. By this view, GP is no different
from any other ML system, where users have to make decision on the set of features -
inputs, and each of these inputs becomes part of the GP training and test sets as a GP
terminal.
The function set The function set is comprised of statements, operators, and functions
available to GP systems.
8
1.1. GENETIC PROGRAMMING
The function set is usually application-specific, it is selected to fit the problem domain.
Some examples of function sets that have been used in GP are as follows:
• Boolean Functions
For example: AND, OR, NOT, XOR.
• Arithmetic Functions
For example: +, -, *, /

terminals are selected. This metho d allows trees with branches of different depths to
be generated but ensures that the trees will never become larger than a certain depth.
Pseudo code for a recursive implementation of both the Full and Grow methods is given
in Algorithm 2.
Fig. 1.3: Creation of a full tree having maximum depth 2 (and therefore a total of seven
nodes) using the Full initialisation method (t=time). [57]
10
1.1. GENETIC PROGRAMMING
Algorithm 2: Pseudo code for recursive generation of trees with the ”Full” and
”Grow” methods [57].
P rocedure : gen rnd expr(f unc set, term set, max d, method)
if max d = 0 or (method = grow and rand() <
|term set|
|term set|+|f unc set|
then
expr = choose random element(term set)
else if then
func = choose random element(f unc set) ;
for i ← 1 to arity(func) do
arg
i
= gen rnd expr (func set, term set, max d − 1, method);
expr = (f unc, arg
1
, arg
2
, ) ;
return expr;
Notes: func set is a function set, term set is a terminal set, max d is the maximum
allowed depth for expression trees, the method is either ”Full” or ”Grow” and expr