2005-09-23: Implemented function-tree optimization. In the literature, this is called "editing." It's used, among other reasons, in the hope that compacting useful sections of the tree will make them more robust against disruption by crossover.

In this particular domain, I'm hoping that function optimization will be a significant win in evaluation speed. Each tree only needs to be optimized once, but needs to be evaluated for (tens of) thousands of pixels.

The optimizations currently implemented:

f(const)=const abs(abs(x)) = abs(x) x-x=0 x/x=1 x mod x=0 mix(x,x,y) = x iflt(const,const,a,b) eliminates one branch iflt(x,x,a,b) = b iflt(a,b,x,x) = x

Some of these were quite trivial. A lot more can be done with
optimization, especially of deeper constructs such as `(ADD 1 (ADD 2
X)) = (ADD 3 X)`

As part of the optimization work, I had to implement tree comparisons
to determine if two sub-trees were equal. It currently works for exact
trees. I intend to extend it to also check for equivalency, i.e. the
current comparator doesn't exploit the commutative property:
`(ADD X Y) = (ADD Y X)`

I also wrote a fast statistics gatherer which will later be made optional at compile-time. This is currently being used to track how effective different optimizations are.

Here is a sample run of optimizing a randomly generated tree:

setting seed to 15 (MIX (MIX (MIX (SIN (Y)) (MIX (Y) (Y) (Y)) (SQRT (Y))) (SUB (IFLT (CONST -0.287493) (Y) (Y) (Y)) (MOD (CONST -0.356111) (CONST -0.276621))) (SIN (SUB (CONST 0.986738) (X)))) (IFLT (SUB (SIN (Y)) (ADD (Y) (X))) (IFLT (DIV (Y) (X)) (MOD (X) (Y)) (SUB (X) (CONST -0.699458)) (IFLT (CONST -0.907861) (CONST -0.671048) (Y) (Y))) (ADD (SQRT (CONST -0.641829)) (SIN (Y))) (SUB (SIN (Y)) (MOD (X) (Y)))) (ADD (MIX (SQRT (X)) (IFLT (X) (Y) (CONST -0.170858) (CONST -0.306319)) (COS (Y))) (SUB (SUB (X) (Y)) (DIV (X) (X))))) optimized: (MIX (MIX (MIX (SIN (Y)) (Y) (SQRT (Y))) (SUB (Y) (CONST -0.079489)) (SIN (SUB (CONST 0.986738) (X)))) (IFLT (SUB (SIN (Y)) (ADD (Y) (X))) (IFLT (DIV (Y) (X)) (MOD (X) (Y)) (SUB (X) (CONST -0.699458)) (Y)) (ADD (CONST -0.801142) (SIN (Y))) (SUB (SIN (Y)) (MOD (X) (Y)))) (ADD (MIX (SQRT (X)) (IFLT (X) (Y) (CONST -0.170858) (CONST -0.306319)) (COS (Y))) (SUB (SUB (X) (Y)) (CONST 1.000000)))) 9 node evaluations 1 optimize: iflt(const,const,a,b) eliminates one branch 1 protected square roots 31 optimize failures due to zero args 1 protected square roots of a negative 28 optimize failures due to non-const args 1 optimize: x/x=1 1 optimize: iflt(a,b,x,x) = x 65 optimize attempts 1 optimize: mix(x,x,y) = x 2 optimize: f(const)=const hashtable: 141 updates, 11 items, 16 slots, 3 rehashes

Before and after optimization:

GraphViz is cool.