Hands-On Introduction to Genetic
Programming by Dmitry Batenkov
HELLO WORLD
The idea to mimic the principles of Dar winian evolution in computing has been around at least since the 1950s, so long, in fact, that it has
grown into the field called evolutionary
computing (EC). In this tutorial, we’ll learn
the basic principles of EC and its offspring,
genetic programming (GP), on a “toy
problem” of symbolicregression. We’ll also
learn how to use OpenBeagle, a generic
C++ object-oriented EC framework.
The Fittest Program Survives
EC can be regarded as a very general kind
of optimization, where the solution to a
given problem is selected from an evolving
population of candidate solutions, or
individuals, represented by their genomes.
The selection is based on certain fitness
criteria, which can just be a function
operating on genomes.
The computation starts by choosing a
random bunch of individuals—generation
zero. Generation n+ 1 is the result of
applying evolution operators to the
individuals of generation n. The most
used operators are mutation (random
modification of a single individual’s
genome) and crossover (random mixing
of genomes of two individuals). The
individuals that produce “offspring” are
chosen based on their fitness. The process
ends when a certain stopping criteria
are met (for example, some predefined
number of generations).
GP takes these ideas one step further
by performing the search in the space
of programs (algorithms). A program’s
genome is usually represented as a tree of
primitives, such as variables, arithmetical
and logical operators, loops, conditionals,
function calls, and so forth.
The very nature of EC and GP enables
one to tackle problems without having
the slightest idea how the solution should
look. Indeed, this paradigm has been
successfully applied in a broad range of
applications, producing results that have
even been patented as new inventions.
On the other hand, success is never
guaranteed.
Listing 1: (a) First, we define the primitive set in OpenBeagle. (b) Next, we define a
component to hold the initial data.
GP:: System:: Handle create_system() {
GP::PrimitiveSet:: Handle lSet = new GP:: PrimitiveSet;
lSet->insert(new GP::Add);
lSet->insert(new GP::Subtract);
lSet->insert(new GP::Multiply);
lSet->insert(new GP::Divide);
lSet->insert(new GP::Token T<Double>(“x”));
return new GP:: System(lSet);
}
a1
2
3
4
5
6
7
8
9
class InitialData : public Component {
public:
std:: vector<Double> X, Y;
InitialData (unsigned int npoints) : Component(“InitialData”)
{
srand((unsigned)time(0));
for(unsigned int i=0; i<npoints; i++)
{
X.push_back(- 1.0+ 2.0*(double)rand()/RAND_MAX);
Y.push_back(- 1.0-sin( 2.0*X[i].getWrappedValue()));
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
b
Example
