2 Parity

O'Reilly and Oppacher (1994,1995) and Juels (1995) studied the Multiplexer problem with genetic programming and similar hill-climbing type methods . The Parity and Multiplexer problems have similar functions, terminals and objectives, though they are not identical. Hill-climbing techniques appeared superior in this type of problem. Could genetic programming improve performance by becoming more of a hill-climber? De Jong et al. (2001) used a multi-objective method that kept only non-dominated individuals according to an individual's fitness, size and diversity to produce superior performance over genetic programming on the Even-5-Parity problem. Diversity was based on an edit distance between trees. Small populations were used that kept all non-dominated individuals. The authors noted that diversity is required to prevent convergence resulting in run failure with their ``uncommon degree of greediness or elitism''. Hill-climbing appears to perform well on this problem as does a multi-objective method which simulates hill-climbing.

Figure 5.7: Average size of an individual in the generation where the best fitness was found in the Parity experiments.

Lineage selection on this problem decreases selection pressure and prevents the loss of diversity and convergence. Lineage selection appears to remove the attributes of genetic programming which allow it to behave like a ``hill-climber''. Additionally, the size of individuals is significantly reduced under lineage selection, as seen in Figure 5.4 and Figure 5.7. The latter graph shows the best fitness of each run plotted against the average size of an individual in that generation. Only in the Parity problem was there such a distinctive increase in size associated with an improvement in fitness. It is hypothesised that an additional factor is responsible for poorer fitness under lineage selection. By using code-growth reducing methods, Luke and Panait (2002a) showed that reducing the size of solutions in Parity and Multiplexer problems (in both size restricted and unrestricted spaces) had the effect of also worsening fitness when compared with standard runs . In both problems, the solving of all the fitness cases requires the use of all the terminal values. For example, in the Parity domain, the absence of one of the boolean variables from a program would result in only half of the test cases being potentially solved. There is a benefit to programs which contain several copies of each terminal to increase the chance that they are used properly.

Adding additional elitism or more computation time with lineage selection should improve the fitness results. Also, for problems where it is known that solutions will need particular terminals or functions, it would make sense to encourage their inclusion.