Evolutionary Computation

Evolutionary Computation - Ex 3

Eran Ziserman	034301143
Yonatan Shichel	034472837

The code

Was written to operate on Petite chez scheme, and might not work on other interpreters, such as DrScheme.

Links to the code:
gp.scm
gp-adf.scm
definitions.scm
cases.scm

Algorithm Description

We have tried both "Standard GP" and "ADF GP" versions, using the following configuration:

Crossover Rate: 0.9.
The crossover operator chooses two random subtrees in both parents and switches them. To prevent tree bloating, we have used Langdon's method: first subtree is chosen randomly, while the other subtree is chosen such that the resulting tree will not exceed max depth. The ADF version chooses either to take the subtrees from the program tree, or from the ADF tree.
Mutation Rate: 0.05.
The mutation operator chooses a random node, removes it from the tree and grows a random tree instead. Max tree depth is kept. The ADF version chooses apply the mutation on either the program tree, or the ADF tree.
Reproduction Rate: 0.05.
In this case, the parents will remain the same - no crossover or mutation applied.
Max Tree Depth: 12.
We have found out that bigger trees does not always produce better results - we have chosen to limit the tree depth, and trade it for more generations.
Number of Generations: 61
Population size: 10000
Generation zero was build according to Koza's Ramped half and half scheme, in depths of 4 and 6.

Results

We were surprised to find out that the ADF version gave poorer results than the Standard one: After 61 generations, we have managed to fully solve the problem (192 hits) using the Standard GP algorithm, but got only 181 hits on the ADF version.
We will explain this later.

All the plots below are the results of the Standard GP, except for the last one! The best fitnessed program of G0:
G0 (fitness=123): (+ (% (sin 0.9278467457441475) (sin (- (- y y) x))) -0.8681734581126563)

There was a major improvement in the best fitness between G12 to G13:

G12 (fitness=149): (- (iflte (sin (cos (* (% (% y y) y) -0.7092057377693095))) (cos (cos 0.8889946797240751)) (sin x) (- (cos (+ (+ x 0.009710391679497832) (sin -0.2334314655307459))) (+ (iflte (sin (+ 0.2704674830632072 0.10636354096515577)) (% -0.5981160011486515 x) (iflte y y -0.6184087184328844 -0.4151589491884047) (% y (sin y))) (% (iflte -0.8524252641990926 -0.6956366002867487 y 0.8533493113232118) (cos y))))) (% (cos (cos (+ (cos (* y x)) (sin -0.26910037875541937)))) (sin x)))

G13 (fitness=164): (sin (+ (- (* (* x x) (sin (% (cos 0.12948622208309146) y))) (+ (% y -0.23181791341289548) y)) (* (- (+ x y) (* (iflte y x y (sin y)) 0.7262901819730825)) (* 0.08054884139488738 (sin (- y y))))))

After G13, the programs evolved gradually, resulting in better and better fitness values, but the plots of all best fitnessed programs of G13 to G61 are almost the same - the concept was set in G13, and only minor improvements for it emerge in each new generation.

G61 (fitness=192): (sin (+ (+ (- (* (* x x) (sin (% (cos 0.12948622208309146) y))) (+ (% y -0.23181791341289548) y)) (* (- (+ x y) (iflte x x (iflte (sin y) (* (iflte x x (% 0.4580823256937734 y) y) x) (cos 0.6920156590577111) (sin y)) y)) (* (cos (sin (* (iflte (% 0.6175264089037422 0.6463145518175524) (iflte (% 0.4580823256937734 y) x x (* 0.8136537242325512 x)) x x) (% (iflte x x x y) (% 0.4580823256937734 y))))) (- (% 0.11792904811676452 (+ -0.42850286526845016 (% (iflte x x (iflte -0.049560311990299866 -0.42850286526845016 x y) y) (% 0.4580823256937734 y)))) -0.26910037875541937)))) (* (iflte y (iflte y (% (% (+ (% y -0.23181791341289548) y) (+ (% 0.4580823256937734 y) (% y (% 0.4580823256937734 y)))) y) (+ (iflte (sin x) (* (iflte x x (% 0.4580823256937734 y) y) x) (cos 0.6920156590577111) (sin y)) (% (iflte x x (* y 0.11565702438677494) (iflte y y x y)) (% 0.4580823256937734 y))) (% (% (iflte (sin (- y (* 0.8136537242325512 x))) (cos (iflte x x x y)) (sin y) (sin x)) y) y)) (% (cos y) y) (sin (* (% 0.11792904811676452 y) (% (- y 0.594713588548542) (+ 0.3773379896712745 y))))) (* (* (- (+ (+ 0.6475079287991443 (sin (% x y))) y) (* (iflte x -0.23181791341289548 y (sin y)) (cos y))) (% 0.4580823256937734 y)) (- (% 0.11792904811676452 y) (+ -0.42850286526845016 0.3773379896712745))))))

G61, ADF version (fitness=181):

adf0:

(- arg1 (% (iflte (% arg0 (+ (iflte (- arg0 (sin (cos arg0))) arg1 (cos (% arg0 (% (sin (sin arg1)) (sin (sin arg1))))) arg0) arg1)) (iflte arg1 (sin arg1) (* (sin arg1) (iflte arg1 (+ arg0 arg1) (% (+ (cos (+ arg0 arg1)) (% arg0 (* arg1 arg0))) arg1) arg0)) (* arg0 (% (sin (cos arg0)) (+ arg0 arg0)))) (cos (cos arg1)) (% (iflte arg0 arg0 (sin (- arg0 arg0)) arg0) (+ arg0 arg0))) (- (% (cos arg0) (+ arg0 arg0)) (* (- arg0 (+ arg0 (% arg1 arg1))) (- arg0 (iflte arg1 arg1 (% (+ (cos (+ arg0 arg1)) (% (sin (sin arg0)) (* (- arg0 arg0) arg0))) arg1) arg0))))))

prog:

(% (- (% (- (% (% (* (sin x) (* y y)) (+ (% x x) (cos x))) (+ (% x x) (cos x))) (iflte (+ (% x x) (* (cos (+ y (adf0 y x))) (* x x))) x (+ (- (+ (+ x 0.5693584675139158) (cos (iflte x y (% 0.4925951050055333 0.5494227443080999) y))) (adf0 y -0.5979918928753256)) (+ (- (- x y) (- -0.8066617899548918 x)) (sin (% (iflte x y -0.9629606678055693 y) 0.9767518968325706)))) (+ (adf0 y x) (adf0 x (cos (+ (- (- x y) (- -0.8066617899548918 x)) (* y y))))))) (+ (% x x) (cos x))) (iflte (+ (% (adf0 (cos (- (- (cos (adf0 x 0.9033036050374776)) 0.13834902839976237) y)) 0.4832754129958161) (+ x 0.5693584675139158)) (* (cos y) (adf0 y -0.5979918928753256))) (adf0 (- (+ (+ x 0.5693584675139158) (cos -0.6027666250917219)) (% y (- x (% (sin (sin (% y 0.9767518968325706))) (sin (* y -0.8223300167348206)))))) (iflte x y (% 0.4925951050055333 0.5494227443080999) y)) (+ (- y x) (+ y (adf0 y (sin x)))) (+ (adf0 y x) (adf0 x (cos y))))) (+ (% (sin (sin (% y 0.9767518968325706))) (sin (* y -0.8223300167348206))) 0.4925951050055333))

Explanations to the difference between the Standard and ADF versions:

At the beginning, the ADF version gave better results, but at generation 13 the Standard version had a giant leap in fitness (from 149 to 164 - see plots above).
This "fitness leap" was, in fact, a change in the "program's concept of the problem". At G12 the problem was a set of rectangles, while at G13 the program found a "semi-polar" representation which greatly improved the fitness. From G13 and so, the GP did "fine tuning" to this concept, which allowed getting more and more hits.
The ADF did not have this fitness leap, so it didn't get the "polar concept", thus wasn't able to solve the problem within the generation limit. We can clearly see that at G61 it still treats the problem as a set of rectangles, similar to the Standard version's G12.
Note that the ADF GP did not stop improving, so it might solve the problem if more generations are allowed.
It is interesing to check how does the algorithms evolve, if instead of cartesian x and y coordinates we would supply polar (r, theta) coordinates. This is a simple task to do, but we will leave it to the future at this point (time limits!)

A different approach

Since the GP solution to the intertwined spirals function is a periodic function, we assumed that its range is bounded, so we have tried to plot the GP function itself (not the normalized -1/1 value!) as a 3D plot.

We won't get into much details here - this is brought only as an aesthetic point of view...