GENETIC PROGRAMMING
Introduction
Genetic Programming can be viewed as a specialization of
genetic algorithms
The main difference between the two is in the representation
scheme used
Where GAs use string representations, GP represents
individuals as executable programs (represented as trees)
The aim of the GP is to evolve computer programs
GENETIC PROGRAMMING
Introduction
The general Genetic Algorithm also applies to GP
Apart from the fact that the main difference between the two
approaches is in the representation scheme, there are
differences in the fitness evaluation, cross-over operators and
mutation operators also
GENETIC PROGRAMMING
Chromosome Representation
Each individual, or chromosome, represents one computer
program, represented using a tree structure
For this purpose we need to define two sets: a terminal set
and a function set
Example:
The terminal set specifies all the variables and constants
For the example the Terminal set is {a, x, z, 3.4}
GENETIC PROGRAMMING
Chromosome Representation
Example:
The function set contains all the functions that can be applied
to the elements of the terminal set. These functions may
include mathematical, arithmetic and/or Boolean functions.
Decision structures such as if-then-else can also be included
Minimal function set for the example is
{-, +, *, /, sin, exp, ln}
GENETIC PROGRAMMING
Chromosome Representation
Example:
Using tree terminology,
elements of the terminal set
form the leaf nodes of the
evolved tree,
and elements of the function
set form the non-leaf nodes
The optimum solution is
illustrated in the figure
GENETIC PROGRAMMING
Chromosome Representation
Each individual in a GP population represents a program,
which is an element of the program space formed by all
possible programs that can result from the given grammar
(as defined by the terminal and function sets)
The aim of the GP is then to search for a program within the
program space that gives the best approximation to the
objective (the true) program
GENETIC PROGRAMMING
Chromosome Representation
Trees within a population are of variable size, however
sometimes fixed size trees are also used
A restriction on maximum depth is usually placed
GENETIC PROGRAMMING
Initial Population
The initial population is generated randomly within the
restrictions of a maximum depth and semantics as expressed
by the given grammar
For each individual, a root is randomly selected from the set
of function elements
The branching factor (i.e. the number of children) of the root
(all all other non-terminal nodes) is determined by the arity
of the selected function
GENETIC PROGRAMMING
Initial Population
For each non-root node, the initialization algorithm
randomly selects an element either from the terminal set or
the function set
As soon as an element from the terminal set is selected, the
corresponding node becomes a leaf node and is no longer
considered for expansion
GENETIC PROGRAMMING
Fitness Function
Fitness function used for GP is problem dependent
As an example, assume we have no prior knowledge about
the structure of the program, other than the given terminal
and function sets
In addition, a data set is available, consisting of a number of
data patterns, where each data pattern consists of input
values for each of the variables and a target value
GENETIC PROGRAMMING
Fitness Function
The evaluation of each individual program (chromosome)
entails
1. Calculating the output of that individual given the values
of inputs
2. Calculating the error made
At the end, the mean-square-error (MSE) over the given data
set is a valid quantification of the fitness of that
individual
GENETIC PROGRAMMING
Selection Process
Any of the selection operators used in GAs can also be used
here
GENETIC PROGRAMMING
Crossover Operator
One or two offspring can be created by selecting a node
randomly in each of the two parents
The corresponding sub-trees are swapped to create the two
offspring
If one offspring is desired, then a sub-tree of one of the
parents is replaced by a sub-tree of another parent
GENETIC PROGRAMMING
Crossover Operator
GENETIC PROGRAMMING
Crossover Operator
GENETIC PROGRAMMING
Mutation Operators
Several mutation operators have been developed for the GP
Function node mutation: A function node is randomly selected and
replaced with a node of the same arity, randomly selected from the
function set
GENETIC PROGRAMMING
Mutation Operator
Terminal node mutation: A randomly selected terminal node is replaced
with a new terminal node randomly selected from the terminal set
GENETIC PROGRAMMING
Mutation Operator
Swap mutation: A function node is randomly selected and the arguments
of that node are swapped
GENETIC PROGRAMMING
Mutation Operator
Grow mutation: A node is randomly selected and replaced by a randomly
generated sub-tree. The new sub-tree is restricted by a
predetermined depth
GENETIC PROGRAMMING
Mutation Operator
Gaussian mutation: A terminal node which represents a constant is
randomly selected and mutated by adding a Gaussian random value
to that constant
GENETIC PROGRAMMING
Mutation Operator
Trunc mutation: A function node is randomly selected and replaced by a
random terminal node. This effectively performs a pruning of the
tree
GENETIC PROGRAMMING
Mutation Operator
Individuals to be mutated are selected according to a
mutation probability pm
Nodes within the selected tree are mutated according to a
probability pn
The larger the probability pn, the more the genetic build-up
of that individual is changed
The larger the mutation probability pm, the more individuals
will be mutated
GENETIC PROGRAMMING
References
Engelbrecht Chapter 10