Article,
Multi-Objective Methods for Tree Size Control
Genetic Programming and Evolvable Machines, 4 (3): 211--233 (September 2003)
DOI: doi:10.1023/A:1025122906870
Abstract
Variable length methods for evolutionary computation
can lead to a progressive and mainly unnecessary growth
of individuals, known as bloat. First, we propose to
measure performance in genetic programming as a
function of the number of nodes, rather than trees,
that have been evaluated. Evolutionary Multi-Objective
Optimisation (EMOO) constitutes a principled way to
optimise both size and fitness and may provide
parameterless size control. Reportedly, its use can
also lead to minimisation of size at the expense of
fitness. We replicate this problem, and an empirical
analysis suggests that multi-objective size control
particularly requires diversity maintenance.
Experiments support this explanation.
The multi-objective approach is compared to genetic
programming without size control on the 11-multiplexer,
6-parity, and a symbolic regression problem. On all
three test problems, the method greatly reduces bloat
and significantly improves fitness as a function of
computational expense. Using the FOCUS algorithm,
multi-objective size control is combined with active
pursuit of diversity, and hypothesised minimum-size
solutions to 3-, 4- and 5-parity are found. The
solutions thus found are furthermore easily
interpretable. When combined with diversity
maintenance, EMOO can provide an adequate and
parameterless approach to size control in variable
length evolution.
Tags
- algorithms,
- bloat,
- code
- genetic
- growth,
- interpretability
- multi-objective
- optimality,
- optimization,
- pareto
- programming,
- representations,
- size
- variable
