Pareto Optimality and Dominance Relations

Preamble¶

Introduction¶

In an earlier section, we briefly covered selection in single-objective problems. There is a fundamental difference between selection in single-objective problems when compared to multi-objective problems. In single-objective problems, we often look for a single solution which has the best objective value, whereas this is not possible in multi-objective problems because they often involve conflicts between multiple objectives. Because multi-objective problems consider more than one objective value, it is often the case that a solution with the best value for one objective will often have degradation in one or more other objective values. This is where a trade-off emerges in the objective space, and it is unlikely that there exists a single solution that can be considered optimal.

Therefore, the solution to a multi-objective optimisation problem is not a single solution vector, but instead an approximation set. This is a set of many candidate solutions that present trade-offs between the multiple objectives, where any improvement in one objective value will result in the degradation in one or more of the other objective values. This notion of "optimum" solutions is called Pareto-optimality.

Pareto-optimality and other approaches to determining dominance relationships between multiple solutions in a population are important during the selection stage of an optimisation algorithm, highlighted below.

Notation¶

Let's define a multi-objective function f(x)f(x)f(x) consisting of two objectives.

f(x)=(f1(x),f2(x))(1) f(x) = (f_{1}(x),f_{2}(x))\tag{1} f(x)=(f1​(x),f2​(x))(1)

We have a population X\mathrm{X}X of N\mathrm{N}N candidate solutions.

X=⟨X1,X2,…,XN⟩ \mathbf{X} = \langle \mathrm{X}_1,\mathrm{X}_2,\ldots,\mathrm{X}_{\mathrm{N}}\rangle X=⟨X1​,X2​,…,XN​⟩

where N\mathrm{N}N refers to the number of solutions in the population, Xn\mathrm{X}_{n}Xn​ refers to the nnn-th solution in the population, and xdnx_{dn}xdn​ refers to the ddd-th decision variable of the nnn-th solution in the population.

Xn=⟨x1n,x2n,…,xDn⟩ \mathrm{X}_{n} = \langle x_{1n},x_{2n},\ldots,x_{\mathrm{D}n} \rangle Xn​=⟨x1n​,x2n​,…,xDn​⟩

We will also define the corresponding objective values Y\mathrm{Y}Y which are calculated when evaluating the function in Equation 1.

Y=⟨Y1,Y2,…,YN⟩ \mathbf{Y} = \langle \mathrm{Y}_1,\mathrm{Y}_2,\ldots,\mathrm{Y}_{\mathrm{N}}\rangle Y=⟨Y1​,Y2​,…,YN​⟩

where N\mathrm{N}N refers to the number of objective value sets, Yn\mathrm{Y}_{n}Yn​ refers to the nnn-th set of objective values in the population, and ymny_{mn}ymn​ refers to the mmm-th objective value of the nnn-th set of objective values in the population.

Yn=⟨y1n,y2n⟩ \mathrm{Y}_{n} = \langle y_{1n},y_{2n} \rangle Yn​=⟨y1n​,y2n​⟩

Dominance¶

When using or designing algorithms to solve multi-objective optimisation problems, we will often encounter the concept of domination. This concept is useful for comparing two solutions to determine whether one is better than the other.

We can now use our notation to define dominance relationships. Let's take two solutions to a two-objective problem: X1\mathrm{X}_1X1​ and X2\mathrm{X}_2X2​, with their corresponding objective values Y1=⟨y1,1,y2,1⟩\mathrm{Y}_{1} = \langle y_{1,1},y_{2,1} \rangleY1​=⟨y1,1​,y2,1​⟩ and Y2=⟨y1,2,y2,2⟩\mathrm{Y}_{2} = \langle y_{1,2},y_{2,2} \rangleY2​=⟨y1,2​,y2,2​⟩.

Definition 1: A solution X1\mathrm{X}_1X1​ is said to dominate another solution X2\mathrm{X}_2X2​, if both of the following conditions are satisfied:

1. The objective values of X1\mathrm{X}_1X1​ are no worse than those of X2\mathrm{X}_2X2​ in all objectives, i.e. for this two-objective problem fm(X1)≤fm(X2)f_{m}(\mathrm{X}_1) \leq f_{m}(\mathrm{X}_2)fm​(X1​)≤fm​(X2​) for all m=(1,2)m = (1, 2)m=(1,2).

2. The objective values of solution X1\mathrm{X}_1X1​ are strictly better than at least one of those of solution X2\mathrm{X}_2X2​, i.e. for this two-objective problem fm(X1)<fm(X2)f_{m}(\mathrm{X}_1) \lt f_{m}(\mathrm{X}_2)fm​(X1​)<fm​(X2​) for at least one m=(1,2)m = (1, 2)m=(1,2).

If any of the two conditions are violated, the solution X1\mathrm{X}_1X1​ does not dominate the solution X2\mathrm{X}_2X2​ . Otherwise, we can claim X1\mathrm{X}_1X1​ dominates X2\mathrm{X}_2X2​.

Definition 2: Two solutions X1\mathrm{X}_1X1​ and X2\mathrm{X}_2X2​ are said to be non-dominating with respect to each other if the following conditions are satisfied:

1. The objective values of solution X1\mathrm{X}_1X1​ are strictly better than at least one of those of solution X2\mathrm{X}_2X2​, i.e. for this two-objective problem fm(X1)<fm(X2)f_{m}(\mathrm{X}_1) \lt f_{m}(\mathrm{X}_2)fm​(X1​)<fm​(X2​) for at least one m=(1,2)m = (1, 2)m=(1,2).

2. The objective values of solution X1\mathrm{X}_1X1​ are strictly worse than at least one of those of solution X2\mathrm{X}_2X2​, i.e. for this two-objective problem fm(X1)>fm(X2)f_{m}(\mathrm{X}_1) \gt f_{m}(\mathrm{X}_2)fm​(X1​)>fm​(X2​) for at least one m=(1,2)m = (1, 2)m=(1,2).

Selecting Solutions¶

Generally, one of our goals throughout the optimisation process is to select the best solutions. This means that solutions that can be categorised as either "dominating" or "non-dominating" are solutions that we are interested in. To be clear, we are not interested in solutions that are dominated, because they do not offer any desirable performance with respect to any of the considered objectives.

Let's use Python to demonstrate these dominance relations that are often used for selection. Here, we will assume a minimisation problem, where smaller values are better. We will initialise four sets of solutions by synthetically assigning objective values that will demonstrate our dominance relations.

Our first set Y1\mathrm{Y}_1Y1​ and Y2\mathrm{Y}_2Y2​ will demonstrate the scenario where Y1\mathrm{Y}_1Y1​ dominates Y2\mathrm{Y}_2Y2​.

Our second set Y3\mathrm{Y}_3Y3​ and Y4\mathrm{Y}_4Y4​ will demonstrate the scenario where Y3\mathrm{Y}_3Y3​ is identical to Y4\mathrm{Y}_4Y4​.

Our third set Y5\mathrm{Y}_5Y5​ and Y6\mathrm{Y}_6Y6​ will demonstrate the scenario where Y5\mathrm{Y}_5Y5​ and Y6\mathrm{Y}_6Y6​ are non-dominated with respect to each other.

Our fourth set Y7\mathrm{Y}_7Y7​ and Y8\mathrm{Y}_8Y8​ will demonstrate the scenario where Y7\mathrm{Y}_7Y7​ is dominated by Y8\mathrm{Y}_8Y8​.

First, we will define a function to determine whether a solution dominates another or not.

Now, let's test it with our four sets of objective values.

As expected, the only solution pairing that satisfies the criteria for dominance is our first set Y1\mathrm{Y}_1Y1​ and Y2\mathrm{Y}_2Y2​.

Next, let's define a function to determine whether two solutions are non-dominated.

Again, we will test it with our four sets of objective values.

As expected, the only solution pairing that satisfies the criteria for dominance is our first set Y5\mathrm{Y}_5Y5​ and Y6\mathrm{Y}_6Y6​.

We can string these two functions together within a decision structure to determine the dominance relation between any two solutions.

Finally, we will test it with our four sets of objective values.

Conclusion¶

In this section we introduced the concept of Pareto-optimality and looked at dominance relations in more detail, complete with examples in Python. The next challenge we will encounter is when we need to select a subset of solutions from a population that consists of entirely non-dominated solutions. For example, which 100 solutions do we select from a population of 200 non-dominated solutions? We will offer some solutions to this challenge in the later sections.