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.