Page 92 - 49A Field Guide to Genetic Programming

78 9 Multi-objective Genetic Programming

to focus the selection procedure towards specific regions of the Pareto front.
Hinchliffe, Willis, and Tham (1998) applied similar ideas to evolve parsimo-
nious and accurate models of chemical processes using MO GP. Langdon
and Nordin (2000) applied Pareto tournaments to obtain compact solutions
in programmatic image compression, two machine learning benchmark prob-
lems and a consumer profiling task. Nicolotti, Gillet, Fleming, and Green
(2002) used multi-objective GP to evolve quantitative structure–activity re-
lationship models in chemistry; objectives included model fitting, the total
number of terms and the occurrence of non-linear terms.
Ekart and Nemeth (2001) tried to control bloat using a variant of Pareto
tournament selection where an individual is selected if it is not dominated
by a set of randomly chosen individuals. If the test fails, another individual
is picked from the population, until one that is non-dominated is found.
In order to prevent very small individuals from taking over the population
in the early generations of runs, the Pareto criterion was modified so as
to consider as non-dominated solutions also those that were only slightly
bigger, provided their fitness was not worse.
Bleuler, Brack, Thiele, and Zitzler (2001) suggested using the well-known
multi-objective optimiser SPEA2 (Zitzler, Laumanns, and Thiele, 2001) to
reduce bloat. de Jong, Watson, and Pollack (2001) and de Jong and Pollack
(2003) proposed using a multi-objective approach to promote diversity and
reduce bloat, stressing that without diversity enhancement (given by modern
MOO methods) searches can easily converge to solutions that are too small
to solve a problem. Tests with even parity and other problems were very
encouraging. Badran and Rockett (2007) argued in favour of using mutation
to prevent the population from collapsing onto single-node individuals when
using a multi-objective GP.
As well as directly fighting bloat, MO GP can also be used to simplify
solution trees. After GP has found a suitable (but large) model, for example,
one can continue the evolutionary process, changing the fitness function to
include a second objective that the model be as small as possible (Langdon,
1998). GP can then trim the trees while ensuring that the simplified program
still fits the training data.

9.2.2 Other Objectives

Although much of the use of MOO techniques in GP has been aimed at
controlling bloat, there are also genuinely MOO applications.
For example, Langdon (1998) made extensive use of Pareto dominance
ranking to evolve different types of data structures. Up to six different
criteria were used to indicate to what degree an evolved data structure met
the requirements of the target data structure. The criteria were used in
Pareto-type tournament selection, where, unlike in other systems, a second