  Genetic programming (GP) is one of the best approaches today to discover
symbolic regression models. To find models that trade off accuracy and
complexity, the non-dominated sorting genetic algorithm II (NSGA-II) is widely
used. Unfortunately, it has been shown that NSGA-II can be inefficient: in
early generations, low-complexity models over-replicate and take over most of
the population. Consequently, studies have proposed different approaches to
promote diversity. Here, we study the root of this problem, in order to design
a superior approach. We find that the over-replication of low complexity-models
is due to a lack of evolvability, i.e., the inability to produce offspring with
improved accuracy. We therefore extend NSGA-II to track, over time, the
evolvability of models of different levels of complexity. With this
information, we limit how many models of each complexity level are allowed to
survive the generation. We compare this new version of NSGA-II, evoNSGA-II,
with the use of seven existing multi-objective GP approaches on ten widely-used
data sets, and find that evoNSGA-II is equal or superior to using these
approaches in almost all comparisons. Furthermore, our results confirm that
evoNSGA-II behaves as intended: models that are more evolvable form the
majority of the population.
