Page 95 - 49A Field Guide to Genetic Programming

9.4 Multi-objective Optimisation via Operator Bias 81

which initially guide GP towards solutions that maximise the main objec-
tive. When enough of the population has reached reasonable levels in that
objective, the fitness function is modified so as to guide the population to-
wards the optimisation of a second objective. In principle this process can
be iterated for multiple objectives. Of course, care needs to be taken to
ensure that the functionality reached with a set of previous fitness measures
is not wiped by the search for the optima of a later fitness function. This
can be avoided by making sure each new fitness function somehow includes
all the previous ones. For example, the fitness based on the new objectives
can be added to the pre-existing objectives with some appropriate scaling
factors.
A similar effect can be achieved via static, but staged, fitness functions.
These are staged in the sense that certain levels of fitness are only be made
available to an individual once it has reached a minimum acceptable perfor-
mance on all objectives at the previous level. If each level represents one of
the objectives, individuals are then encouraged to evolve in directions that
ensure that good performance is achieved and retained on all objectives.
Koza et al. (1999) used this strategy when using GP for the evolution of
electronic circuits where many criteria, such as input-output performance,
power consumption, size, etc., must all be taken into account to produce
good circuits. Kalganova and Miller (1999) used Cartesian GP (see Sec-
tion 7.2.3) to design combinational logic circuits. A circuit’s fitness was
given by a value between 0 and 100 representing the percentage of output
bits that were correct. If the circuit was 100% functional, then a further
component was added which represented the number of gates in the graph
that were not involved in the circuit. Since all individuals had the same
number of gates available in the Cartesian GP grid, this could be used to
minimise the number of gates actually used to solve the problem at hand.

9.4 MO GP via Operator Bias

While it is very common to use only modifications of the selection phase to
perform multi-objective search, it is also possible to combine MOO selection
with genetic operators exhibiting an inbuilt search bias which can steer the
algorithm towards optimising certain objectives.
In some sense the classical repair operators, which are used in constrained
optimisation to deal with hard constraints, are an extreme form of the idea
of using operators to help MOO search. 1 More generally, it is possible to
imagine search operators with softer biases which favour the achievement
of one or more objectives. These can be the same or different from the
objectives that bias the selection of parents.
1
In combinatorial optimisation, repair operators are applied to invalid offspring to
modify them in such a way as to ensure a problem’s hard constraints are respected.