This test showed the ability of the generic genetic algorithm to evolve data trees. In this test the genetic algorithm was to evolve symbolic equations represented by binary trees to fit a set of data points.
The gene type for this test was a binary tree. Cross breeding was performed by selecting random points on the two parent trees and then swapping the subtrees denoted by those two points:
The raw fitness for any potential solution (i.e. an equation) was its average distance from all of the data points. The actual fitness was then calculated as : 100/(1+raw fitness). This not only placed the best fitness near 100 and the worst near 0, it also heavily weighted those equations that had higher fitnesses. Though this would cause a critical lack of diversity in fixed-string gene populations, lack of diversity is not nearly as much of a problem in populations of data trees. This is because if a tree is selected to cross-breed with a copy of itself it rarely produces two identical trees(the random node would have to be the same for both trees) whereas with most fixed length strings crossbreeding between copies produces two more copies.
The population size was 500. The cross-breeding percentage was set to 70%. Overselection was also used. In overselection 80% of the population is bred from the top N% of the previous population and the remaining 20% is bred from the rest of the previous population. In this example N was 30%. The maximum number of generations was set to 51 (the first random population and 50 evolved ones) and the run was terminated when the genetic algorithm found an individual with a perfect raw fitness of 0.
The first curve fit was to the equation f(x) = 5x2+2x+4. The genetic algorithm found the equation in eight generations with the tree: (-(-(+(+(X)(+(X)(*(1)(*(1)(5)))))(*(*(5)(X))(1)))(*(*(5)(X))(-(1)(X))))(1))
Which simplifies to: 5x2+2x+4, or the function to which the curve was being fit.
The graph shows that the best of generation converged rapidly to the solution while the average fitness of the population improved significantly. There is no improvement in the worst of generation indicating that random cross-breeding produced unfit members in each new generation.