Information Technology Reference
In-Depth Information
F
(
x
1
)
>F
(
x
2
)
⇔
∀
i.f
i
(
x
1
)
≥
f
i
(
x
2
)
∧∃
i.f
i
(
x
1
)
>f
i
(
x
2
)
Under Pareto optimality, one solution is better than another if it is better ac-
cording to at least one of the individual fitness functions and no worse according
to all of the others. Under the Pareto interpretation of combined fitness, no
overall fitness improvement occurs no matter how much almost all of the fitness
functions improve, should they do so at the slightest expense of any one of their
number. The use of Pareto optimality is an alternative to simply aggregating
fitness using a weighted sum of the
n
fitness functions.
When searching for solutions to a problem using Pareto optimality, the search
yields a set of solutions that are non-dominated. That is, each member of the
non-dominated set is no worse than any of the others in the set, but also cannot
be said to be better. Any set of non-dominated solutions forms a Pareto front.
Consider Figure 12, which depicts the computation of Pareto optimality for
two imaginary fitness functions (Objective 1 and Objective 2). The longer the
search algorithm is run the better the approximation becomes to the real Pareto
front. In the figure, points
S
1,
S
2and
S
3 lie on the Pareto front, while
S
4and
S
5 are dominated.
Pareto optimality has many advantages. Should a single solution be required,
then coecients can be re-introduced in order to distinguish among the non-
dominated set at the current Pareto front. However, by refusing to conflate
the individual fitness functions into a single aggregate, the search may consider
solutions that may be overlooked by search guided by aggregate fitness. The
approximation of the Pareto front is also a useful analysis tool in itself. For
example, it may contain 'knee points', where a small change in one fitness is
accompanied by a large change in another. These knee points denote interesting
parts of the solution space that warrant closer investigation.
Fig. 12.
Pareto Optimality and Pareto Fronts (taken from the survey by Harman
et al. [48])
Search WWH ::
Custom Search