8 M. Kommenda et al.
Fig. 3 Exemplary Pareto fronts generate either by an NSGA-II using the standard or the
discretized objective function. The Pareto front generated by the discrete objective contains fewer
and simpler models that describe the data equally well
4 Experiments
The effectiveness of the new complexity measure is demonstrated by solving five
benchmark problems (Sect.4.1) and compared to single-objective optimization
using standard genetic programming as well as using the NSGA-II with other
complexity measures. All algorithm variants have been identically configured with
the exception that three different maximum tree length values for standard genetic
programming and four different objective functions for the NSGA-II (including
all previously discussed adaptations) have been tested. Parameters such as the
population size, the termination criterion and the allowed terminal or function
symbols are listed in Table 1.
The initial population has been created with the probabilistic tree creator
(PTC2, Luke 2000 ), which produces uniformly distributed tree lengths between
the specified minimum and maximum length. The individuals for reproduction are
selected using a tournament with a group size of four on the prediction accuracy
in the case of standard genetic programming, while NSGA-II uses tournament
selection with a group size of two on the rank and crowding distance of individuals.
A standard subtree swapping crossover, which respects the maximum tree length,
has been used as crossover operator and single point, remove branch and replace
branch mutation have been applied after crossover with a probability of 25 %. After
the reproduction operations the whole previous population gets replaced by the new
individuals with the exception of one elite individual when performing standard
genetic programming. NSGA-II merges the new and already existing individuals,
performs fast non-dominated sorting and keeps the best 1000 individuals which
form the new population. The sketched procedure of selection, reproduction and