Page 168 - 49A Field Guide to Genetic Programming

154 B TinyGP

0.1 0.0998334166468282
0.2 0.198669330795061
0.3 0.29552020666134
....
55 LINES OMITTED
....
5.9 -0.373876664830236
6.0 -0.279415498198926
6.1 -0.182162504272095
6.2 -0.0830894028174964

These fitness cases are sin(x) for x ∈ {0.0, 0.1, 0.2, . . . 6.2}

B.3 Source Code

The original TinyGP system was implemented, in the C programming lan-
2
guage, to maximise efficiency and minimise the size of the executable. The
version presented here is a Java re-implementation of TinyGP. The original
version did not allow the use of random numerical constants.
How does TinyGP work? The system is based on the standard flattened
(linear) representation for trees, which effectively corresponds to listing the
primitives in prefix notation but without any brackets. Each primitive occu-
pies one byte. A program is simply a vector of characters. The parameters
of the system are as specified in Section B.1. They are fixed at compile time
through a series of static class variable assignments. The operators used
are subtree crossover and point mutation. The selection of the crossover
points is performed at random with uniform probability. The primitive set
and fitness function are as indicated above. The code uses recursion for the
creation of the initial population (grow), for the identification of the subtree
rooted at a particular crossover point (traverse), for program execution
(run), and for printing programs (print indiv). A small number of global
variables have been used. For example, the variable program is a program
counter used during the recursive interpretation of programs, which is auto-
matically incremented every time a primitive is evaluated. Although using
global variables is normally considered bad programming practice, this was
done purposely, after extensive experimentation, to reduce the executable’s
size.

2 The C version of TinyGP is probably the world’s smallest tree-based symbolic-
regression GP system. The source code, in C, is 5,906 bytes. The original version included
a compilation script which, with a variety of tricks, created a self-extracting executable
occupying 2,871 bytes (while the actual size of the executable after self-extraction was
4,540 bytes). All optimisations in the code were aimed at bringing the executable size
(as opposed to the source code size) down, the main purpose being to show that, against
popular belief, it is possible to have really tiny and efficient GP systems.