Practical Evolutionary Algorithms
A practical book on Evolutionary Algorithms that teaches you the concepts and how they’re implemented in practice.
Get the bookPareto Optimality and Dominance Relations
Preamble¶
# used to create block diagrams
%reload_ext xdiag_magic
%xdiag_output_format svg
import numpy as np # for multidimensional containers
Introduction¶
In an earlier section, we briefly covered selection in singleobjective problems. There is a fundamental difference between selection in singleobjective problems when compared to multiobjective problems. In singleobjective problems, we often look for a single solution which has the best objective value, whereas this is not possible in multiobjective problems because they often involve conflicts between multiple objectives. Because multiobjective 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 tradeoff 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 multiobjective optimisation problem is not a single solution vector, but instead an approximation set. This is a set of many candidate solutions that present tradeoffs 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 Paretooptimality.
Paretooptimality 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.
%%blockdiag
{
orientation = portrait
Initialisation > Evaluation > "Terminate?" > Selection > Variation > Evaluation
Selection [color = '#ffffcc']
}
Notation¶
Let's define a multiobjective function $f(x)$ consisting of two objectives.
$$ f(x) = (f_{1}(x),f_{2}(x))\tag{1} $$We have a population $\mathrm{X}$ of $\mathrm{N}$ candidate solutions.
$$ \mathbf{X} = \langle \mathrm{X}_1,\mathrm{X}_2,\ldots,\mathrm{X}_{\mathrm{N}}\rangle $$where $\mathrm{N}$ refers to the number of solutions in the population, $\mathrm{X}_{n}$ refers to the $n$th solution in the population, and $x_{dn}$ refers to the $d$th decision variable of the $n$th solution in the population.
$$ \mathrm{X}_{n} = \langle x_{1n},x_{2n},\ldots,x_{\mathrm{D}n} \rangle $$We will also define the corresponding objective values $\mathrm{Y}$ which are calculated when evaluating the function in Equation 1.
$$ \mathbf{Y} = \langle \mathrm{Y}_1,\mathrm{Y}_2,\ldots,\mathrm{Y}_{\mathrm{N}}\rangle $$where $\mathrm{N}$ refers to the number of objective value sets, $\mathrm{Y}_{n}$ refers to the $n$th set of objective values in the population, and $y_{mn}$ refers to the $m$th objective value of the $n$th set of objective values in the population.
$$ \mathrm{Y}_{n} = \langle y_{1n},y_{2n} \rangle $$Dominance¶
When using or designing algorithms to solve multiobjective 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 twoobjective problem: $\mathrm{X}_1$ and $\mathrm{X}_2$, with their corresponding objective values $\mathrm{Y}_{1} = \langle y_{1,1},y_{2,1} \rangle$ and $\mathrm{Y}_{2} = \langle y_{1,2},y_{2,2} \rangle$.
Definition 1: A solution $\mathrm{X}_1$ is said to dominate another solution $\mathrm{X}_2$, if both of the following conditions are satisfied:

The objective values of $\mathrm{X}_1$ are no worse than those of $\mathrm{X}_2$ in all objectives, i.e. for this twoobjective problem $f_{m}(\mathrm{X}_1) \leq f_{m}(\mathrm{X}_2)$ for all $m = (1, 2)$.

The objective values of solution $\mathrm{X}_1$ are strictly better than at least one of those of solution $\mathrm{X}_2$, i.e. for this twoobjective problem $f_{m}(\mathrm{X}_1) \lt f_{m}(\mathrm{X}_2)$ for at least one $m = (1, 2)$.
If any of the two conditions are violated, the solution $\mathrm{X}_1$ does not dominate the solution $\mathrm{X}_2$ . Otherwise, we can claim $\mathrm{X}_1$ dominates $\mathrm{X}_2$.
Definition 2: Two solutions $\mathrm{X}_1$ and $\mathrm{X}_2$ are said to be nondominating with respect to each other if the following conditions are satisfied:

The objective values of solution $\mathrm{X}_1$ are strictly better than at least one of those of solution $\mathrm{X}_2$, i.e. for this twoobjective problem $f_{m}(\mathrm{X}_1) \lt f_{m}(\mathrm{X}_2)$ for at least one $m = (1, 2)$.

The objective values of solution $\mathrm{X}_1$ are strictly worse than at least one of those of solution $\mathrm{X}_2$, i.e. for this twoobjective problem $f_{m}(\mathrm{X}_1) \gt f_{m}(\mathrm{X}_2)$ for at least one $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 "nondominating" 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 $\mathrm{Y}_1$ and $\mathrm{Y}_2$ will demonstrate the scenario where $\mathrm{Y}_1$ dominates $\mathrm{Y}_2$.
Y1 = np.array([0, 0.5])
Y2 = np.array([0.5, 0.5])
Our second set $\mathrm{Y}_3$ and $\mathrm{Y}_4$ will demonstrate the scenario where $\mathrm{Y}_3$ is identical to $\mathrm{Y}_4$.
Y3 = np.array([0.5, 0.5])
Y4 = np.array([0.5, 0.5])
Our third set $\mathrm{Y}_5$ and $\mathrm{Y}_6$ will demonstrate the scenario where $\mathrm{Y}_5$ and $\mathrm{Y}_6$ are nondominated with respect to each other.
Y5 = np.array([0, 0.5])
Y6 = np.array([0.5, 0])
Our fourth set $\mathrm{Y}_7$ and $\mathrm{Y}_8$ will demonstrate the scenario where $\mathrm{Y}_7$ is dominated by $\mathrm{Y}_8$.
Y7 = np.array([0.5, 0.5])
Y8 = np.array([0, 0.25])
First, we will define a function to determine whether a solution dominates another or not.
def dominates(X1, X2):
if(np.any(X1 < X2) and np.all(X1 <= X2)):
return True
else:
return False
Now, let's test it with our four sets of objective values.
dominates(Y1, Y2)
dominates(Y3, Y4)
dominates(Y5, Y6)
dominates(Y7, Y8)
As expected, the only solution pairing that satisfies the criteria for dominance is our first set $\mathrm{Y}_1$ and $\mathrm{Y}_2$.
Next, let's define a function to determine whether two solutions are nondominated.
def nondominated(X1, X2):
if(np.any(X1 < X2) and np.any(X1 > X2)):
return True
else:
return False
Again, we will test it with our four sets of objective values.
nondominated(Y1, Y2)
nondominated(Y3, Y4)
nondominated(Y5, Y6)
nondominated(Y7, Y8)
As expected, the only solution pairing that satisfies the criteria for dominance is our first set $\mathrm{Y}_5$ and $\mathrm{Y}_6$.
We can string these two functions together within a decision structure to determine the dominance relation between any two solutions.
def dominance_relation(X1, X2):
if(np.all(X1 == X2)):
print("The solutions are identical.")
elif(dominates(X1, X2)):
print("The first solution dominates the second.")
elif(nondominated(X1, X2)):
print("The two solations are nondominating")
else:
print("The first solution is dominated by the second.")
Finally, we will test it with our four sets of objective values.
dominance_relation(Y1, Y2)
dominance_relation(Y3, Y4)
dominance_relation(Y5, Y6)
dominance_relation(Y7, Y8)
Conclusion¶
In this section we introduced the concept of Paretooptimality 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 nondominated solutions. For example, which 100 solutions do we select from a population of 200 nondominated solutions? We will offer some solutions to this challenge in the later sections.
Support this work
You can access this notebook and more by getting the ebook on Practical Evolutionary Algorithms.