Some weeks ago I tested the data analysis system
Eureqa and was very delighted by its functions and performance, and especially the concept of Symbolic Regression. To quote from Eureqa's home page, Eureqa is
detecting equations and hidden mathematical relationships in your data. Its primary goal is to identify the simplest mathematical formulas which could describe the underlying mechanisms that produced the data.
I blogged about about this in my Swedish blog
Eureqa: equation discovery med genetisk programmering (Google translation to English
Eureqa: Equation discovery with genetic programming). Eureqa uses Symbolic Regression (using genetic programming) for calculating a mathematical formula given some data points. For more about Eureqa, see
my Eureqa page.
Symbolic Regression with JGAP
After that, I started to write my own system for symbolic regression using the genetic algorithm/genetic programming system
JGAP, written in Java. You will find Java code and example configuration files on
My JGAP page.
Here I give some examples of the usage of symbolic regression with my program. Last there is full lists of the defined function, options, and configuration files.
I wrote my own system instead of just using Eureqa for a couple of reasons:
 learning genetic programming, and symbolic regression, is probably better done with writing code
 it is easy to write new functions with JGAP, and I want to experiment with different things, new functions and options
 in some cases (like this) I like command line tools better than GUI:s, and the use configuration file where the options for the learning and data is collected
What is symbolic regression (SR)?
Symbolic regression is, simply put, a way of using genetic programming (GP) to generate a mathematical formula given some data points. In some cases of genetic programming it can be "real programs" but in this context there are mostly mathematical expressions. Note that symbolic regression is just one thing you can to with genetic programming.
For an example of symbolic regression, see
(from
www.geneticprogramming.com.) Also see Wikipedia's
Genetic Programming.
What fascinates me most with genetic programming is that the result of is a program which can be understood, it is a "white box" (clear box) technique. For some other machine learning techniques, say neural networks, it is very hard to understand the result; it's just a black box, where you may use the results but don't get any insights into the solution. Also, I tend to prefer other white box techniques such as decision trees and rule based.
My SymbolicRegression program have a lot of options, but I will not explain or exemplify them all here. All full list of the options with a short description is presented below.
Let us start with some simple examples to understand what symbolic regression can do and how to do it with the program SymbolicExpression.
Simple example: number puzzle
Let's say we got the following puzzle:
If we assume that:
2 + 3 = 10
7 + 2 = 63
6 + 5 = 66
8 + 4 = 96
How much is?
9 + 7 = ????
This can be somewhat tricky to solve this by hand (or head), or maybe we simply are too lazy to solve it by hand. Using symbolic regression is easier (although probably not that fun): Just create a configuration file like the one below. In this problem there is a specific unknown instance that we want to solved for, so we can write an instance with the
?
(question mark) in the place of the (unknown) output.
presentation: Puzzle
num_input_variables: 2
variable_names: x y z
functions: Multiply,Divide,Add,Subtract
terminal_range: 10 10
terminal_wholenumbers: true
population_size: 100
num_evolutions: 100
show_similiar: true
data
2 3 10
7 2 63
6 5 66
8 4 96
# the unknown instance
9 7 ?
We use the four arithmetic function (*,/, +,), coded as
Multiply,Divide,Add,Subtract
and have a small population size (100) and just 100 generations. The other options is explained more below.
Here is an (edited) sample run of the problem.
It was 4 data rows
It was 1 data rows in the user defined data set
Presentation: Puzzle
output_variable: z (index: 2)
input variable: x
input variable: y
function1: &1 * &2
function1: /
function1: &1 + &2
function1: &1  &2
function1: 10.0
Creating initial population
Evolving generation 0/100(time from start: 0,05s)
Best solution fitness: 35.0
Best solution: x + ((y  x) + (10.0 * x))
Depth of chrom: 3. Number of functions/terminals: 9 (4 functions, 5 terminals)
Correlation coefficient: 0.979073833348314
Evolving generation 3/100(time from start: 0,15s)
Best solution fitness: 31.0
Best solution: (10.0 * x) + ((x * y)  (8.0 + y))
Depth of chrom: 3. Number of functions/terminals: 11 (5 functions, 6 terminals)
Correlation coefficient: 0.9945949940306454
Evolving generation 11/100(time from start: 0,39s)
Best solution fitness: 26.0
Best solution: ((10.0 * x) + (x + (7.0 * y))) + (x * y)
Depth of chrom: 4. Number of functions/terminals: 13 (6 functions, 7 terminals)
Correlation coefficient: 0.969830602937701
Evolving generation 14/100(time from start: 0,50s)
Best solution fitness: 22.0
Best solution: (x * x) + (4.0 * x)
Depth of chrom: 2. Number of functions/terminals: 7 (3 functions, 4 terminals)
Correlation coefficient: 0.9726783536388712
Evolving generation 17/100(time from start: 0,58s)
Best solution fitness: 0.0
Best solution: (x * y) + (x * x)
Depth of chrom: 2. Number of functions/terminals: 7 (3 functions, 4 terminals)
Correlation coefficient: 1.0
All time best (from generation 17)
Evolving generation 101/100(time from start: 1,71s)
Best solution fitness: 0.0
Best solution: (x * y) + (x * x)
Depth of chrom: 2. Number of functions/terminals: 7 (3 functions, 4 terminals)
Correlation coefficient: 1.0
Total time 1,71s
All solutions with the best fitness (0.0):
(x * x) + (x * y) (26)
(x * x) + (y * x) (2)
(x + y) * x (2)
(x * y) + (x * x) (98)
((x * y) + (x * x)) * ((2.0  2.0) + (2.0 / 2.0)) (1)
((x / (y / x)) + x) * y (1)
It was 6 different solutions with fitness 0.0
Testing the fittest program with user defined test data:
9.0 7.0 Result: 144.0
Since it is a genetic programming system, the first generation  generation 0  is a completely random population of programs. Note that the configuration states very few limits in size, and number of population, and there is really no limits of the structure (see below).
The best fit program in this first generation,
x + ((y  x) + (10.0 * x))
has a quite bad
fitness measure: 35; rather a long way from the goal of fitness 0 (the perfect score). The fitness is calculated by the sum of the differences between the program's output for each data point and the real data point. (Note: One of my TODO:s is to have more alternatives of error measures.)
Generation 3 has a somewhat better solution, as has generations 11, and 14. A perfect solution is found in generation 17:
(x * y) + (x * x)
with a fitness (error) of 0.0, and a correlation coefficient of 1.0 (perfect fit between the input variable and output variable). After the 100 generations, the best solution is printed again with the total time (about 1.7 seconds).
Since the option
show_similar: true
was set, all solutions with the same fitness score as the best is also shown:
(x * x) + (x * y) (26)
(x * x) + (y * x) (2)
(x + y) * x (2)
(x * y) + (x * x) (98)
((x * y) + (x * x)) * ((2.0  2.0) + (2.0 / 2.0)) (1)
((x / (y / x)) + x) * y (1)
Some of these solutions are just permutation of the best solution, i.e. the places of the variable names or expressions are changed. Other are not very interesting either, or, like the 5th one, is not at all useful in this example. The numbers in parenthesis after the solution is the number of occurrences of the solution. Luckily the 5th solution was generated only once.
During the evolution we also see that the
correlation coefficient changes from
0.979073833348314 (which is rather good and unusual except in these easy problems) to a perfect fit
1.0.
Other notes:
 I consciously selected a rather bad run for this simple example to be able to show the development over the generations. In other runs the problem was solved in generation 2 or 3, and sometimes even in the generation 0. This indicates that it is a very easy problem and actually may have been replaced by just random search. For more serious (larger) problems this is not the case.
 The option in the configuration file are explained below. One of the most tricky thing about genetic programming is to select the
functions
to use. In this problem it would suffice with just the functions Add
, and Multiply
, but it is  of course  a special case.
Note: This problem was taken from
Roger Alsing's blog post the other day
Genetic Programming: Code smarter than you. Roger has also dona a great Mona Lisa application where a picture of Mona Lisa is evolved using genetic programming:
Genetic Programming: Evolution of Mona Lisa. Note: There is an example of a Mona Lisa application in the JGAP distribution.
Example: Fibonacci sequence, as lagged "time series"
Let's take another example, one that I wrote in my
Eureqa posting: Fibonacci numbers. The first one is 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946.
The relation between the numbers is, of course, that the next number F(n) is F(n1) + F(n2), e.g. 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 etc. It is a
recursive equation.
In order to analyze this kind of recursive sequences (in this program) we need to translate this sequence into a lagged "time series". Let us assume that we suspect that it is a recursive sequence but we don't know the exact relation or the number of previous elements that is needed. So we make a series where the output variable can be considered dependent of either 1, 2, or 3 variables. Like this:
1,1,2,3
1,2,3,5
2,3,5,8
...
After doing this transformation, we proceed in the same manner as the number problem above, i.e. create a configuration file (
fib1.conf) with the options and the data:
# Fibonacci with 3 variables
num_input_variables: 3
variable_names: F1 F2 F3 F4
functions: Multiply,Divide,Add,Subtract
terminal_range: 10 10
max_init_depth: 4
population_size: 20
max_crossover_depth: 8
num_evolutions: 100
max_nodes: 21
show_population: false
stop_criteria_fitness: 0
data
1,1,2,3
1,2,3,5
2,3,5,8
3,5,8,13
5,8,13,21
8,13,21,34
13,21,34,55
21,34,55,89
34,55,89,144
55,89,144,233
89,144,233,377
144,233,377,610
233,377,610,987
377,610,987,1597
610,987,1597,2584
987,1597,2584,4181
1597,2584,4181,6765
2584,4181,6765,10946
4181,6765,10946,17711
6765,10946,17711,28657
10946,17711,28657,46368
And here is a complete run (slightly edited) where the correct solution is found in generation 10:
F3+F2
. Also, here we added the option
stop_criteria_fitness: 0
which makes the program to exit after the criteria have been reached.
It was 21 data rows
Presentation: This is the Fibonacci series
output_variable: F4 (index: 3)
input variable: F1
input variable: F2
input variable: F3
function1: &1 * &2
function1: /
function1: &1 + &2
function1: &1  &2
function1: 4.0
Evolving generation 0/100(time from start: 0,01s)
Best solution fitness: 17619.64
Best solution: ((F3 + F1) + 7.0) + (F1 / F3)
Depth of chrom: 3. Number of functions+terminals: 9 (4 functions, 5 terminals)
Correlation coefficient: 0.9999999998872628
Evolving generation 2/100(time from start: 0,06s)
Best solution fitness: 7050.70
Best solution: ((F2 + F2) * (F1 + F1)) / (((F2 + 7.0) + F2) + (F1  F3))
Depth of chrom: 4. Number of functions+terminals: 17 (8 functions, 9 terminals)
Correlation coefficient: 0.9999999122259431
Evolving generation 9/100(time from start: 0,19s)
Best solution fitness: 6749.0
Best solution: (F2 / F2) + (4.0 * F1)
Depth of chrom: 2. Number of functions+terminals: 7 (3 functions, 4 terminals)
Correlation coefficient: 0.99999999956117
Evolving generation 10/100(time from start: 0,21s)
Best solution fitness: 0.0
Best solution: F3 + F2
Depth of chrom: 1. Number of functions+terminals: 3 (1 functions, 2 terminals)
Correlation coefficient: 1.0
Fitness stopping criteria (0.0) reached with fitness 0.0 at generation 10
All time best (from generation 10)
Evolving generation 10/100(time from start: 0,21s)
Best solution fitness: 0.0
Best solution: F3 + F2
Depth of chrom: 1. Number of functions+terminals: 3 (1 functions, 2 terminals)
Correlation coefficient: 1.0
Total time 0,21s
All solutions with the best fitness (0.0):
F3 + F2 (1)
It was 1 different solutions with fitness 0.0
A variant where we remove the stopping criteria, and instead use
show_similar: true
results in the following similar
solutions:
All solutions with the best fitness (0.0):
(F2 / 1.0) + F3 (1)
(3.0 / 3.0) * (F3 + F2) (1)
F3 + F2 (406)
F2 + F3 (7)
(2.0 / 2.0) * (F3 + F2) (1)
It was 5 different solutions with fitness 0.0
TODO: I have some plans to automatically generate this kind of lagged time serie for a sequence, and hope it will be finished soon. This is not rocket science but it can be tricky in the details.
Example: Classification with the Iris data set
The
Iris data set is a classic classification examples. It is used to classify three different species (classes) of the Iris flower: Iris setosa, Iris virginica, and Iris versicolor. Since my system cannot  yet  handle nominal data the three difference classes is translated to the numbers 1.0, 2.0, and 3.0 respectively.
In the configuration file
iris.conf we use the following functions:
functions: Multiply,Divide,Add,Subtract,IfLessThanOrEqualD
The function
IfLessThanOrEqualD
may be worth a comment: I am currently reading John Koza' first Genetic Programming book
Genetic Programming: v. 1 On the Programming of Computers by Means of Natural Selection (ISBN: 9780262111706). He mentions the
IFLTE
function (
if a <= b then c else d
), which I implemented  by cloning and mutation of my
IfElseD.java function (see, programmers also use these operators :). As Koza writes in page 365 about the function, it can be used instead of the following function:
However, it may convenient to instead use these functions explicitly since the generated code may be clearer for the user. Koza also lists equals (
==
) in this list, but I'm not so convinced that IFLTE can properly replace this.
Some notes:
 this is a selected  but real  run, all running are not this good (or bad)
 here we use the complete data set as fitness cases. Normally a certain percent of the data should be used as a validation set (with the option
validation_pct
). See below for a discussion of this.
We use a population of 100 and 100 generations for a rather fast (about 3 seconds) run. If the population iwhere incremented to  say  1000 and with 1000 generations we most surely getting better results, although it takes some more time.
population_size: 100
num_evolutions: 100
Other configuration options in the file:

input_variables: 4
Here we define that the number of input variables are 4, and there is always one output variable). (Note: This should probably be automatically detected.)

variable_names: sl sw pl pw class
Here is the names of the variables. They should be rather short to not clutter the output expression to much. The last variable (class
) is the output variable. Note that it it possible to change what variable to use as output variable, with the option output_variable
and state the (0based) position in the variable list. Here we could have the following option: output_variable: 4
.

terminal_range: 20 20
The range of the Terminal
(ephemeral terminal), i.e. the numbers used in the solution expression.

terminal_wholenumbers: false
This is a special option to be able to state that to use only whole numbers (or rather double representation of integers). In this example, we don't want to use only integers.

max_nodes: 31
This is about the only structural restriction there is in genetic programming: This states the maximum number of nodes in the expression trees. Nodes are either functions or terminals (numbers). So, here we allow up to 31 functions or terminals.

mutation_prob: 0.01
Probability of mutation. The probability of mutation and crossover are very important and may make the difference of an effective run vs. a slow progression. One have to experiment with these for larger problems.

crossover_prob: 0.9
Probability of crossover. See comment above.

show_progression: true
If this option is set, the generation number is printed on the last line of the command. Can be useful for larger problems.

show_results: true
If true, the results of the fittest programs is shown.

result_precision: 5
For show_results
: The precision of the results.

hits_criteria: 0.5
If the absolute difference between the result and the real value is equal or below this value, it is considered a hit. If set, the fitness measure is the number of nonhits. The value of 0.5 is chosen since the three classes are represented as value 1, 2, and 3, and if the different is <= than 0.5 we have a selected class. (Thoughtful and late note: Maybe it would suffice to add the function Round
or Floor
?)
Here is a very truncated run.
It was 150 data rows
Presentation: Iris
output_variable: class (index: 4)
input variable: sl
input variable: sw
input variable: pl
input variable: pw
function1: &1 * &2
function1: &1 + &2
function1: &1  &2
function1: /
function1: if(&1 <= &2) then (&3) else(&4)
function1: 16.624795863695333
Evolving generation 0/100(time from start: 0,16s)
Best solution fitness: 64.0
Best solution: ((sw * pl)  (pw * pw)) / ((sl  pl) * (sl  sw))
Depth of chrom: 3. Number of functions+terminals: 15 (7 functions, 8 terminals)
Correlation coefficient: 0.6621167550765015
Number of hits (<= 0.5): 86 (of 150 = 0,57)
Results for this program:
...
(22) 1.0: 0,98889 (diff: 0,01111)
(23) 1.0: 0,87582 (diff: 0,12418)
(24) 1.0: 1,58128 (diff: 0,58128) > 0.5!
(25) 1.0: 0,70000 (diff: 0,30000)
...
total diff: 111.08622273795162 (no abs diff: 42.32778738529426 #hits: 86 (of 150)
Evolving generation 1/100(time from start: 0,29s)
Best solution fitness: 48.0
Best solution: ((sw + pl) * sl) / (18.98720292178895 + pl)
Depth of chrom: 3. Number of functions+terminals: 9 (4 functions, 5 terminals)
Correlation coefficient: 0.8492617928834261
Number of hits (<= 0.5): 102 (of 150 = 0,68)
Results for this program:
...
total diff: 60.411404633990145 (no abs diff: 35.03754935483205 #hits: 102 (of 150)
Evolving generation 4/100(time from start: 0,61s)
Best solution fitness: 7.0
Best solution: (19.035483741865328 / 19.035483741865328) + pw
Depth of chrom: 2. Number of functions+terminals: 5 (2 functions, 3 terminals)
Correlation coefficient: 0.9564638238016164
Number of hits (<= 0.5): 143 (of 150 = 0,95)
...
total diff: 39.80000000000001 (no abs diff: 29.800000000000004 #hits: 143 (of 150)
Evolving generation 16/100(time from start: 0,94s)
Best solution fitness: 6.0
Best solution: (((19.035483741865328 / 19.035483741865328) + pw) / (sw / sw))  ((if(pw <= pl) then (sw) else(pl)) / (sw + 14.495973076477487))
Depth of chrom: 4. Number of functions+terminals: 19 (8 functions, 11 terminals)
Correlation coefficient: 0.9582679236481598
Number of hits (<= 0.5): 144 (of 150 = 0,96)
Results for this program:
...
total diff: 26.831398327892167 (no abs diff: 3.7720516041580767 #hits: 144 (of 150)
Evolving generation 39/100(time from start: 1,54s)
Best solution fitness: 5.0
Best solution: (((19.035483741865328 / 19.035483741865328) + pw) / (sw / sw))  ((if(pw <= pl) then (sw) else(pl)) / (((14.495973076477487  (sl + sl)) / sw) + 14.495973076477487))
Depth of chrom: 6. Number of functions+terminals: 25 (11 functions, 14 terminals)
Correlation coefficient: 0.958786524094953
Number of hits (<= 0.5): 145 (of 150 = 0,97)
Results for this program:
(0) 1.0: 0,97740 (diff: 0,02260)
(1) 1.0: 1,01322 (diff: 0,01322)
(2) 1.0: 1,00110 (diff: 0,00110)
(3) 1.0: 1,00869 (diff: 0,00869)
...
(69) 2.0: 1,94192 (diff: 0,05808)
(70) 2.0: 2,59137 (diff: 0,59137) > 0.5!
(71) 2.0: 2,11718 (diff: 0,11718)
...
(118) 3.0: 3,11623 (diff: 0,11623)
(119) 3.0: 2,35925 (diff: 0,64075) > 0.5!
(120) 3.0: 3,08251 (diff: 0,08251)
...
(128) 3.0: 2,91459 (diff: 0,08541)
(129) 3.0: 2,39350 (diff: 0,60650) > 0.5!
(130) 3.0: 2,70539 (diff: 0,29461)
(131) 3.0: 2,73150 (diff: 0,26850)
(132) 3.0: 3,01459 (diff: 0,01459)
(133) 3.0: 2,31546 (diff: 0,68454) > 0.5!
(134) 3.0: 2,23094 (diff: 0,76906) > 0.5!
(135) 3.0: 3,08865 (diff: 0,08865)
(136) 3.0: 3,17414 (diff: 0,17414)
...
(148) 3.0: 3,07502 (diff: 0,07502)
(149) 3.0: 2,60513 (diff: 0,39487)
total diff: 26.224671119186706 (no abs diff: 0.04627940721407109 #hits: 145 (of 150)
...
Total time 2,91s
The solutions of the best fit program (generation 39) is this.
Solution:(((19.035483741865328 / 19.035483741865328) + pw) / (sw / sw))  ((if(pw <= pl) then (sw) else(pl)) / (((14.495973076477487  (sl + sl)) / sw) + 14.495973076477487))
which is kind of funny looking. Here are some comments:

19.035483741865328 / 19.035483741865328
is 1. The program don't simplify such expressions, but this would be nice to have. (As I understand it, Eureqa has some kind of simplification process.)
 the
if then else
is used as an expression with the returning value is used directly in the solution. Something we don't see here but may happen with other settings is that the logical operators (or expressions using these operators) returns 1.0 (true) or 0.0 (false) and these values is used directly in the calculations as any other expression.
Best solution fitness: 5.0
...
Number of hits (<= 0.5): 145 (of 150 = 0,97)
We defined fitness as the number of differences <= 0.5, and we see that there are 5 wrongly classified instances (150144=6), with a hit rate of 97%. Not too bad, but not very good either.
If we study the instances more for the best fit program of generation 39 (and the overall best), we see that class 1 (instances 150) is classified very good, i.e. none are misclassified. For class 2 (instances 51100) there is one misclassified instance (#70), and the rest is of classified as class 3 (#119,#129,#133,and #134). However, due to the very random nature of genetic programming, another run could give another number of bad classifications, and other misclassification instances. However2, these instances  especially #70  is often misclassified as class 3.
Validation set
In this Iris run we used a quite low values of population size and the number of generations. With higher values, say population size=1000 and 1000 generations, it may well be possible to get a perfect hit, and that happened sometimes when I experimented. However this perfect fit could be bad since the fittest program has
over fitted the data: it learned the problem to well, so it may not be used for calculating new instances.
A standard procedure in machine learning or other data analysis to remedy over fitting is to move some of the test cases into a
validation set, i.e. instances not seen in the training session and then test the solution against the validation test. The option
validation_pct
does exactly that. The value of the option is the percentage of the data that will be placed in the validation set. Or more exactly: it is the
probability that a specific fitness case will be in the validation set.
Compiling the program
All files mentioned here (and at
my JGAP page) are collected in the file
symbolic_regression.zip. As of now, it is not packaged into a nice Jar file, so you have to compile it manually. There is no file structure either so the files should be unzipped in the same directory.
SymbolicRegression.java is the main program. It is based on JGAP's example
MathProblem.java
but extended with a lot of bells & whistles.
The program is compiled with (on a Linux box) like this. Note that you must have
JGAP installed.
javac Xlint:unchecked classpath "jgap/jgap.jar:jgap/lib/log4j.jar:jgap/lib/xstream1.2.2.jar:jgap/lib/commonslang2.1.jar:$CLASSPATH" SymbolicRegression.java
and run with:
java server Xmx1024m Xss2M classpath "jgap/jgap.jar:jgap/lib/log4j.jar:jgap/lib/xstream1.2.2.jar:jgap/lib/commonslang2.1.jar:$CLASSPATH" SymbolicRegression [config file]
Here is my
log4j.properties file.
Supported function from JGAP
The SymbolicRegression program has support for the many of the GP functions from JGAP. The "main" type is double so all functions is not applicable there (e.g.
IfElse
etc). However, for the ADF functions (defined by setting
adf_arity
to > 0, but see below) more functions is supported. Please note that some of these functions are experimental (or
very experimental) and the result may not make sense in this context.
For some functions, I have made a similar one so it returns double instead of  say  Boolean. These variants are mentioned in this list, has has the suffix
D
.

Multiply
(double)

Multiply3
(double)

Add
(double)

Add3
(double)

Add4
(double)

Divide
(double)

Subtract
(double)

Sine
(double)

ArcSine
(double)

Tangent
(double)

ArcTangent
(double)

Cosine
(double)

ArcCosine
(double)

Exp
(double)

Log
(double)

Abs
(double)

Pow
(double)

Round
(double), compare with my RoundD

Ceil
(double)

Floor
(double)

Modulo
(double), implements Java's %
operator for double. See ModuloD for a variant

Max
(double)

Min
(double)

LesserThan
(boolean)

GreaterThan
(boolean)

If
(boolean)

IfElse
(boolean), cf the IfElseD

IfDyn
(boolean)

Loop
(boolean), cf the experimental LoopD

Equals
(boolean), cf EqualsD

ForXLoop
(boolean)

ForLoop
(boolean)

Increment
(boolean)

Pop
(boolean)

Push
(boolean)

And
(boolean), cf the double variant AndD

Or
(boolean), cf the double variant OrD

Xor
(boolean), cf the double variant XorD

Not
(boolean), cf the double variant NotD

SubProgram
(boolean, experimental)

Tupel
(boolean, experimental)
My own functions
Here is a complete list of the functions I have wrote (the list will hopefully grow). Some of these may be considered experimental, but may be of some use in experimental settings (or just learning).
 Boolean operators for DoubleClass
Here are the Boolean operators for use with DoubleClass, i.e. they has double
as input and returns a double
(0.0d or 1.0d). Some of these functions are tested in odd_parity.conf.
 ModuloD.java: Modulo with
double
as input and output. First the input is converted to integers and then an integer modulo is done which is returned as a double. (The standard %
operator on double is not what I wanted.) This is tested in isbn_test.conf.
 ModuloReplaceD.java: Sometimes we want the Modulo function not to return 0 but some other value (e.g. the highest possible values in the data set). Then this function may be tried. Note: The replacement value is manually set in the configuration option
mod_replace
. This should be considered highly experimental.
 DivideIntD.java: A protected variant of
Divide
where the division is done by first converting to Integer
then doing an integer division. Also, if the divisor is 0 (zero), the result is 1 (i.e. protected).
 DivideProtected.java: A protected variant of
Divide
the result is 1 (i.e. protected) if the divisor is 0 (zero), else standard double division.
 Mathematical functions.
 Other functions
Making new functions
As you see there is about 30 new functions written for this package, and it quite simple to write new. My own method for writing a new function is this. Let's see how to write the
Sqrt
function (which is
here).
 decide what the new function will do: Sqrt of a function.
 copy a similiar function, if possible. Here I just copied the function
org.jgap.gp.function.Log
from the JGAP distribution.
 change the old name to the new function name : "Log" > "Sqrt"
 change way the function should be presented in
toString()
: "sqrt &1". If a function has more arguments, the different arguments are presented as "&1", "&2", "&3", etc. E.g. the ModuloD
function has the following presentation "&1 mod &2", but it can be "mod(&1,&2)" or even "(mod &1 &2)" depending on the style of output. (Hmm, maybe there should be an option in all functions how to represent the names, e.g. mathematical, Java version, Lisp version. I have to think about this more.)
 change the textual representation in
getName()
. We use Sqrt
.
 state the logic of the function in
exectute_double
. Since double is the only type that is supported right now, it suffices to change for exectute_double
. However, in some of the files, there are also support for other types, e.g. exectute_float
, exectute_int
, etc.
 change the number of arguments and call name in
execute_object
: here we use execute_sqrt
as the call name. This same name is to be used in Compatible
.
 Add the function name in the
makeCommands
method in SymbolicRegression.java. Recompile.
This is the basic procedure, if there are other arguments or types, some more tweaking may have to be done. .
Configuration files
One of the primary task of writing my of Symbolic Regression progra was to be able to use a configuration file to state the problem and the data. Below are some examples. Please note that some of these are experimental (and use experimental parameters/operators), and also they may not give any interesting or good results. More info about the data/problem is usually in the header of the file.
Some of these problems was first tested with Eureqa and was commented in
Eureqa: Equation discovery with genetic programming (a Google Translation of my original Swedish blog post
Eureqa: equation discovery med genetisk programmering).
 alldifferent3.conf: All variables should be different
 bolts.conf: Bolts. A machine learning example
 boyles_law.conf: Boyle's law.
 catalan.conf: Catalan numbers
 circle_1.conf : Circle
 exp_formula.conf: Test of Exp function
 exp_formula_no_exp.conf: Test of Exp function, but without
Exp
in the function list.
 fahrenheit_celsius.conf: Fahrenheit to Celsius conversion. You may experiment by changing
output_variable
to 0 for the reverse conversion (C > F).
 fib1.conf: Fibonacci series as a time serie.
 fib2.conf: Fibonacci series as a time serie.
 fib_50.conf: Fibonacci numbers, where I try to find the closed formula for the Fibonacci number.
 func1.conf: Unknown function (from a homework in a couse in Evolutionary Computing)
 gamma_test.conf: Test of Gammma function
 gelman.conf: Linear regression
 henon_100.conf: Henon, 100 data points
 heron_formula.conf: Heron formula
 intro_page_262.conf: A simple problem
 iris.conf: Iris data set
 isbn_test.conf: Trying to get the program to calculate the checksum for ISBN13
 longley.conf: Longley's data set of number employments
 majority_on_3.conf: Boolean 3majority on
 mod_test.conf: Test of modulus operator.
 moons.conf: Moons data
 multiplexer_3.conf: 3multiplexer (i.e. IfThenElse)
 multiplexer_6.conf: 6multiplexer
 multiplexer_11.conf: 11multiplexer
 mysterious.conf: Mysterious function
 number_puzzle1.conf: Number puzzle from Roger Alsing's blog post Genetic Programming: Code smarter than you!
 odd_parity.conf: Odd parity, using the double variants of the boolean functions, i.e. AndD, OrD, NotD (see above)
 odd_parity_double.conf: Odd parity, using the arithmetic functions +,,*,/
 odd_parity2.conf: Odd parity for two inputs
 p10.conf: Polynom P(10)
 p4.conf: Polynom P(4)
 p4_2.conf: Polynom P(4)
 p4_jgap.conf: Polynom P(4). This is the version in the JGAP example MathFormula.java
 p6_2.conf: Polynom P(6)
 planets.conf: Planets, i.e. Kepler's third law.
 quintic.conf: Quintic polynomial
 regression_koza.conf: Regression (0.5 * x^2, from John R. Koza's Lisp implementation)
 regression_psh.conf: Regression (y = 12x^2 + 5, from Psh)
 seq_ind1.conf: Sequence induction problem: 5*j^4+4*j^3+3*j^2+2^j+1 (for integers 0..10)
 sigmoid_test.conf: Test of Sigmoid function
 sin_formula.conf: Test of Sine
 sin_formula_rand20.conf: Test of Sine
 sine_tiny_gp.conf: Test of Sine from TinyGP
 sorted_3.conf: Sorting 3 variables.
 sqrt_formula2.conf: Yet another test of Sine
 sqrt_formula3.conf: Yet another test of Sine
 sqrt_formula.conf: Test of Sqrt function
 sunspots.conf: Sunspots data as time series
 test1.conf: A test of many functions.
 test2.conf: A test of new functions.
 tic_tac_toe.conf: Tictactoe
 triangular_numbers.conf: Triangular numbers
 weather.conf: Weather (classic classification example)
 x2.conf: A simply polynomial: x^2
 x4x3+x2x.conf: Polynomial: x^4x^3+x^2x
 zoo2.conf: Zoo (classic classification example)
The configuration parameters
The configuration file consists of the following parameters. Here is a short explanation; the full story is in the code:
SymbolicRegression.java. Most of the parameters has reasonable default values, taken from either MathProblem.java or GPConfiguration.

#
, %
: Line comments; lines that start with the characters "#" or "%" will be ignored.

presentation
: A text which is shown first in the run.

num_input_variables
: Number of input variables in the data set.

output_variable
: The index (0based) of the output variable. Default is the last variable.

variable_names
: The name of the variables, in order. Default is "V0", "V1", etc

data
: Starts the data
section, where each row is presented per line. The attributes may be separated by "," or some space. Decimal point is a .
(dot).
If a data row contains a ?
(question mark) in the position of the output variable, then it is considered a "user defined test" and the fittest program will be tested against this data last in the run.

terminal_range
: The range for the Terminal
as lower upper
. Note: Only one Terminal is used.

terminal_wholenumbers
: If the Terminal
should use wholenumbers or not (boolean)

constant
: Define a Constant
with this value

functions
: Define the functions, with the same name as in JGAP (or own defined functions).

adf_arity
: If > 0 then ADF is used. This is somewhat experimental as I am still try to understand how ADF:s works.

adf_function
: The functions used for ADF.

adf_type
: Either double or boolean. If set to boolean, we can use the boolean and logical operators.

max_init_depth
: JGAP parameter maxInitDepth

min_init_depth
: JGAP parameter minInitDepth

program_creation_max_tries
: JGAP parameter programCreationMaxTries

population_size
: JGAP parameter populationSize

max_crossover_depth
: JGAP parameter maxCrossoverDepth

function_prob
: JGAP parameter functionProb

reproduction_prob
: JGAP parameter reproductionProb

mutation_prob
: JGAP parameter mutationProb

crossover_prob
: JGAP parameter crossoverProb

dynamize_arity_prob
: JGAP parameter dynamizeArityProb

no_command_gene_cloning
: JGAP parameter no_command_gene_cloning

use_program_cache
: JGAP parameter use_program_cache

new_chroms_percent
: JGAP parameter newChromsPercent

num_evolutions
: JGAP parameter numEvolution

tournament_selector_size
: JGAP parameter tournamentSelectorSize

max_nodes
: JGAP parameter maxNodes

scale_error
: Sometimes the data values are very small which gives small fitness values (i.e. errors), making it hard to get any progress. Setting this parameter will multiply the errors by this value.

stop_criteria_fitness
: If set (>= 0) then the program will run "forever" (instead of num_evolution
) until fitness is less or equal to the value.

show_population
: This shows the whole population in each generation. Mainly for debugging purposes.

show_similar
: Shows all the solutions (programs) with the same fitness value as the best solution.

show_progression
: boolean. If true then the generation number is shown for all generations when nothing is happening (i.e. no gain in fitness).

sample_pct
: (float) Takes a (sample) percentage of the data set if > 0.0.

validation_pct
: Withheld a percentage of the test cases for a validation set. This fitness of this validation set is shown.

show_all_generations
: Show info of all generations, not just when fitness is changed.

hits_criteria
: Criteria of a hit: if the difference is <= this value, it is considered a hit. The number of nonhits is then used as a fitness measure instead of the sum of errors. Setting this function also shows the number of programs which is <= this value.

mod_replace
: Setting the replacement value of 0 (zero) for the ModuloIntD
function (see above).

showResults
: boolean. If set then all the fitness cases is shown with the output of the fitted program, with difference to the correct values.

resultPrecision
: the precision in the output used in showResult
, default 5

ignore_variables
: (TBW) It would be nice to be able to ignore some variables in the data set. But this is yet to be written.

return_type
: (TWB) This should be the type of the "main" return value. Note: it is now hard coded in the program as double/DoubleClass
.
ADF  Automatically Defined Function
JGAP has support for The SymbolicRegression program supports ADF (Automatically Defined Function), and this is a very interesting topic. See the section
6.1 Evolving Modular and Hierarchical Structures from
A Field Guide to Genetic Programming for more info.
SymbolicRegression program has some support for ADF:s, but it is not very well tested yet. I have tested ADF in some configurations but I am not very happy about the result. One example is
sunspots.conf which has the following ADF related options:
adf_arity: 0
adf_type: boolean
adf_functions: IfElse,GreaterThan,LesserThan
One of the problems I have with ADF is that many of the interesting ADF functions, e.g.
Loop
,
ForLoop
,
ForXLoop
, requires a different representation that SymbolicRegression supports. In spite of this, it can be interesting to experiment with the existing support for ADF.
Explanations of the ADF related options:

adf_arity
: When > 0 ADF is activated and all the ADF functions has this arity (number of arguments)

adf_type
: return type for the ADF functions. Can be either boolean
or double
. In order to work, the ADF function must support the stated type (and it is here I have some problems).

adf_function
: a list if functions to be used as ADF.
I hope to come back with a more working support of ADF.
Todo
Here are some TODO:s, or things nice to have. This list was simply copied from my
JGAP page when writing this blog post.
 option for ignoring specific variables
 option for stopping:
 running forever
 after a specific time,
 accept nominal values in the data section; then converted to numeric values.
 add more fitness metrics.
 better handling of punishing longer solutions (parsimony pressure).
 support for different "main" return classes, i.e. not just DoubleClass
 correlation coefficient, and other statistical measures, e.g.
Rsquared, mean squared error, mean absolute error, minimum error,
maximum error
 more/better error checks
 more building blocks, a la Eureqa http://ccsl.mae.cornell.edu/eureqa_ops
 support for derivatives (a la Eureqa)?
 incorporate in Weka?
 simplify the best solution with a CAS?
Also see
During this current travel with Genetic Programming I have read the following two books, in this order.
 Wolfgang Banzhaf, Peter Nordin, Robert E Keller, Frank D Francone: Genetic Programming  An Introduction (Elsevier Science & Technology, 1998, ISBN: 9781558605107). This is a great introduction of GP.
 Riccardo Poli, William B. Langdon, Nicholas F. McPhee, with contributions by John R. Koza:
A Field Guide to Genetic Programming HTML version of the book A Field Guide to Genetic Programming (Lulu.com, 2008, ISBN: 9781409200734). This is a great summary of the current state of genetic programming.
Currently I am reading John Koza' first Genetic Programming book
Genetic Programming: v. 1 On the Programming of Computers by Means of Natural Selection (ISBN: 9780262111706). This is the first and ground breaking book about GP. It is very inspiring and detailed. Many of the ideas here are not applicable to Symbolic Regression, so I hope to implement other GP programs as well.
See also: