Class  Description 

ProgramChromosome<A> 
Holds the nodes of the operation tree.

ProgramGene<A> 
This gene represents a program, build upon an AST of
Op functions. 
x  y 

0.00  0.0000 
0.10  0.0740 
0.20  0.1120 
0.30  0.1380 
...  ... 
NOTE: The function which created the sample points is not needed in the error function we have to define for the GP. It just let us verify the final, evolved result.
As first step, we have to define the set of allowed nonterminal and the terminal operations the GP is working with. Selecting the right set of operation has a big influence on the performance of the GP. If the operation set is bigger than necessary, we will expand the potential search space, and the execution time for finding a solution. For our polynomial example we will chose the following operations and terminals.
static final ISeq<Op<Double>> OPERATIONS = ISeq.of(
MathOp.ADD,
MathOp.SUB,
MathOp.MUL
);
static final ISeq<Op<Double>> TERMINALS = ISeq.of(
Var.of("x", 0),
EphemeralConst.of(() > (double)RandomRegistry.getRandom().nextInt(10))
);
In the next step define the fitness function for the GP, which will be an error function we will minimize.
// The lookup table where the data points are stored.
static final double[][] SAMPLES = new double[][] {
{1.0, 8.0000},
{0.9, 6.2460},
...
};
static double error(final ProgramGene<Double> program) {
return Arrays.stream(SAMPLES).mapToDouble(sample > {
final double x = sample[0];
final double y = sample[1];
final double result = program.eval(x);
return abs(y  result) + program.size()*0.00005;
})
.sum();
}
ProgramGene
). Since we prefer compact programs over complex one, we
will add a penalty for the program size (the number of nodes of the program
tree).
CAUTION: The penalty for the tree size must be small enough to not dominate the error function. We still want to find an approximating function and not the smallest possible one
After we have defined the error function, we need to define the properCodec
.
static final Codec<ProgramGene<Double>, ProgramGene<Double>> CODEC =
Codec.of(
Genotype.of(ProgramChromosome.of(
// Program tree depth.
5,
// Chromosome validator.
ch > ch.getRoot().size() <= 50,
OPERATIONS,
TERMINALS
)),
Genotype::getGene
);
ProgramChromosome
:
public static void main(final String[] args) {
final Engine<ProgramGene<Double>, Double> engine = Engine
.builder(Polynomial::error, CODEC)
.minimizing()
.alterers(
new SingleNodeCrossover<>(),
new Mutator<>())
.build();
final ProgramGene<Double> program = engine.stream()
.limit(500)
.collect(EvolutionResult.toBestGenotype())
.getGene();
System.out.println(Tree.toString(program));
}
add ├── mul │ ├── x │ └── sub │ ├── 0.0 │ └── mul │ ├── x │ └── sub │ ├── sub │ │ ├── sub │ │ │ ├── sub │ │ │ │ ├── 3.0 │ │ │ │ └── x │ │ │ └── x │ │ └── x │ └── x └── xThis program can be reduced to 4*x^3  3*x^2 + x, which is exactly the polynomial, which created the sample data.
© 20072017 Franz Wilhelmstötter (20170822 19:30)