#11 - Domination in Multi Objective Optimization

Domination

Domination in multi-objective optimization is a topic of quality indication when comparing members of a population to a search space problem.  To reiterate, a search space problem is one given a set of decision parameters, a model evaluates the decisions to score its objectives.  In mathematical terms, this is input (x), and function output (y = f (x)).

A quality indicator is used when comparing two members of a population.  That is, it is used to compare two sets of output vectors (the objective scores).  As an example, consider two members of the population for which the objective scores are as follows:

P1: [0.5, 0.8]
P2: [0.4, 1.0]

We want to know if P1 is better than P2 or vice-versa.  That is, we want to know if P1 dominates P2.  For each objective however, we will need to know whether higher numbers are better than lower, or vice-versa. In our example, let us assume low numbers are better.  We as humans, will first examine the first column, and ask ourselves in which member is the objective score lower.  Since 0.4 < 0.5, P2 receives the win on this column.  And similarly, P1 wins the second column because 0.8 < 1.0.  Since this is a tie however, each member won a column each, how do we decide which member is the more dominant?  Intuition would suggest that since P1 won its column by 0.2, but only lost its other column by 0.1, that P1 would be slightly more dominant over P2.  However, a classical definition of domination requires no losses and at least one win.

In terms of classical domination, there is no clear winner here in our example.  So we may have need at times, for something a little weaker or a definition which guarantees that someone dominates.

Quality Indicators

Quality indicators are often used to combine a vector of many output scores into a single scalar value, so that it can be compared quite easily to another population member.  They allow us to answer the questions of "how much" and "in what way" is a population member better than some other member.  Not all quality indicators are binary (comparing two members), as some are unary (yield a measure of quality on just a single member).  Each indicator yields a value between 0 and 1 (0-100%), to reflect how close to "perfect = as good as it gets" it is.  For a general overview, refer to [Ref #1].

Examples

This may become a bit more technical from this point onward.  We will demonstrate the use of a quality indicator described in [Ref #2].  F(P1) = sum (-e ^ (I {P2,P1} / k ), where I {P2,P1} is a binary indicator of choice, and k the number of attributes in P.  Here, we will use a binary epsilon indicator, which simply tells us the difference between the two attributes in the same column of two members from the population.

EX1: We want to maximize both columns.

P1: [0.5, 0.8]
P2: [0.4, 1.0]

F(P1) = -e ^ (0.4 - 0.5)/2 + -e ^ (1.0 - 0.8)/2 = -1.06
F(P2) = -e ^ (0.5 - 0.4)/2 + -e ^ (0.8 - 1.0)/2 = -0.96

Since F(P2) > F(P1) it is better.  The small difference here assumes they are rather similar.

EX2: This time, we want to maximize both columns again, but it is more obvious who wins.
P1: [0.2, 0.3]
P2: [0.8, 0.9]

F(P1) = -e ^ ((0.8 - 0.2)/2) + -e ^ ((0.9 - 0.3)/2) = -2.69
F(P2) = -e ^ ((0.2 - 0.8)/2) + -e ^ ((0.3 - 0.9)/2) = -1.48

F(P2) > F(P1) by far, as was obvious just from eyeballing the objective scores yourself.

EX3: This time, we want to minimize both columns.  We stick in negatives to apply this "weight".
P1: [0.2, 0.3]
P2: [0.8, 0.9]

F(P1) = -e ^ ((-0.8 - -0.2)/2) + -e ^ ((-0.9 - -0.3)/2) = -1.48
F(P2) = -e ^ ((-0.2 - -0.8)/2) + -e ^ ((-0.3 - -0.9)/2) = -2.69

F(P1) wins this time, as we would have thought.

EX4: Now we just want to maximize the first column, and minimize the second column.
P1: [0.2, 0.3]
P2: [0.8, 0.9]

F(P1) = -e ^ ((-0.8 - -0.2)/2) + -e ^ ((0.9 - 0.3)/2) = -2.09
F(P2) = -e ^ ((-0.2 - -0.8)/2) + -e ^ ((0.3 - 0.9)/2) = -2.09

F(P1) = F(P2)!  Just as we expected, since both columns only differ by 0.6.

References

[Ref #1] http://www.tik.ee.ethz.ch/pisa/publications/emo-tutorial-2up.pdf
[Ref #2] ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf