Effective Fitness

The second Pi movie shows populations may continue to evolve even after a solution has been found. Indeed the population may be systematically taken over by a newer solution even if the newer guy is not better than the first solution found. Effective fitness is proposed as a name to explain this.

Essentially effective fitness takes into account not just the selection operator but also the effects of the other operators (crossover and mutation). Where these disrupt the programs, the combined effect is as if the fitness of the individual had been reduced. The effective fitness is this new fitness.

Effective fitness explains bloat, since bloated programs are liable to be less disrupted by genetic operations than their leaner ancestors.

The following assume the effects of mutation are more or less that same on all the programs we consider and so we look just at the effect of crossover. In our two dimensional demic population species form and so crossovers often occurs between direct descendents. Indeed since only the best guys survive selection to be crossover, in many cases the crossovers is between parents which are genetically identical.

The following sections consider four example solutions. The first solution "opt" and three "green" ones. Essentially two of the solutions survive and prosper because they produce approximately 10% more high fitness children than the other two. Since crossover is on average less disruptive, these programs have higher effective fitness, even though they produced identical answers.

Opt and the second example program both prosper initially but are eventually driven to extinction by the descents of other programs with identical fitness but higher effective fitness.

First Solution

In reverse polish the first solution (called "opt" in the pi2 film) is
k k c - / k + k k * k c * - - 0
Of the 79 pairs of crossover which yield legal children (ie within the size limit of 15) 47 are exact copies of the parent, and so have exactly its fitness. All the other 32 have far worse performance than their parent. I.e. there is almost a 60% chance of crossover not disrupting opt.

Subsequent Solutions

The second, after opt, most popular solution in generation 1100 is
k c - k k c - * k k c - / - - 0
Like opt it has 79 legal crossover pairs and 47 of these yield exact copies of their parent. However there are a further 8 crossover pairs which yeild slightly different programs which have identical fitness to it. Ie this solution has a 73% chance of not being disrupted by crossover. Significantly higher than opt and by generation 2000 the population contains 12712 copies of it.

The two children with identical fitness are

c c - k k c - * k k c - / - - 0
k k - k k c - * k k c - / - - 0

The second "Green" solution

Another equally good solution is
k k c - / k + k k * c k * - - 0
However, like opt, only 47 of the 79 legal crossover pairs produce children with a fitness equal to that of their parents. This second "green" solution shares the same fate as opt. It reaches a total of 5746 copies in generation 1000 but declines and is extinct by generation 2000.

Another high Effective Fitness program

Under self crossover
k c - k c - k * k k c - / - - 0
49 out of 79 legal crossover pairs again produce direct copies of their parent. However like the first green solution, a further 8 crossover pairs produced children with identical fitness. They are
c c - k c - k * k k c - / - - 0
k k - k c - k * k k c - / - - 0
This enables it to prosper and by generation 2000 there are almost ten thousand copies of it in the population.

W.Langdon xx.essex.ac.uk 28 May 2007