Page 94 - 49A Field Guide to Genetic Programming

80 9 Multi-objective Genetic Programming

relay. The following objectives were used: the number of nodes that know
the designated node after a given amount of time, the size of the protocol
code, its memory requirements, and a transmission count.
Agapitos, Togelius, and Lucas (2007) used MO GP to encourage the
effective use of state variables in the evolution of controllers for toy car
racing. Three different objectives were used: the ratio of the number of
variables used within a program to the number of variables offered for use by
the primitive language, the ratio of the number of variables being set within
the program to the number of variables being accessed, and the average
positional distance between memory setting instructions and corresponding
memory reading instructions.
When two or three objectives need to be simultaneously optimised, the
Pareto front produced by an algorithm is often easy to visualise. When
more than three objectives are optimised, however, it becomes difficult to
directly visualise the set of non-dominated solutions. Valdes and Barton
(2006) proposed using GP to identify similarity mappings between high-
dimensional Pareto fronts and 3-D space, and then use virtual reality to
visualise the result.

9.2.3 Non-Pareto Criteria

Pareto dominance is not the only way to deal with multiple objectives with-
out aggregating them into a scalar fitness function.
Schmiedle, Drechsler, Grosse, and Drechsler (2001) compared GP with
four different MOO selection methods on the identification of binary deci-
sion diagrams. Linear weighting of the objectives was compared against: a)
Pareto dominance; b) a weaker form of Pareto dominance where a solution
is preferred to another if the number of objectives where the first is superior
to the second is bigger than the number of objectives where the opposite is
true; c) lexicographic ordering (where objectives are ordered based on the
user’s preference); and d) a new method based on priorities. The lexico-
graphic parsimony pressure method proposed in (Luke and Panait, 2002;
Ryan, 1994) is in fact a form of MOO with lexicographic ordering (in which
shorter programs are preferred to longer ones whenever their fitness is the
same or sufficiently similar). An approach which combines Pareto domi-
nance and lexicographic ordering was proposed in (Panait and Luke, 2004).

9.3 Multiple Objectives via Dynamic and
Staged Fitness Functions

Often it is possible to rank multiple objectives based on some notion of
importance. In these cases, it is possible to use dynamic fitness functions