## 3 \(k\)-Pareto Optimality-Based Sorting for Genetic Optimization
### Illustrative Example  
We illustrate the proposed approach and its difference from the traditional non-dominated sorting with the help of an example shown in Figure 3, see [14] for more details and derivations. In this example, the search space consists of 6 points defined on a 2D plane, and the goal is to maximize both objective functions defined by the relative coordinates of the points. Let us first consider the traditional non-dominated sorting by Pareto dominance. This sorting procedure distributes the available solutions between Pareto-fronts in the following way: First, all non-dominated points are identified. In the example shown in Figure 3, there are three non-dominated points: \(A\), \(B\) and \(C\). These three points make up the first front. Next, the points of the newly identified front are removed from consideration, and the process is repeated. Continuing this process, we obtain the second front made up of two points, \(D\) and \(E\), and the third front containing only one point, \(F\). The relative distribution of points between Pareto fronts is summarized in the second column of Table 1.  
Figure 3: Illustration of sorting for a maximization problem. Instead of sorting by Pareto dominance, we propose to sort the points by the measure of the dominating solutions, which we refer to as Pareto optimality (_PO_). Let us consider the counting measure. The sorting is thus conducted by the _number_ of dominating solutions. In the text, we refer to this procedure of calculating _PO_ values as counting _PO_, or _PO-count_, as it implies counting the number of dominating solutions. Similarly to the previous case, no other point dominates the points \(A\), \(B\), or \(C\) in Figure 3. Thereby, the value of the counting Pareto optimality for these points is 0. Point \(E\) is dominated by one point \(C\), resulting in the corresponding _PO_ value of 1. Finally, points \(D\) and \(F\) are dominated by two other points: \(A\), \(B\) and \(C\), \(E\) respectively, meaning that their Pareto optimality is 2. The front of the point is determined by its _PO-count_ value, see the third and the fourth columns of Table 1.  
Comparing sorting by _PD_ and _PO-count_, we can observe that the number of identified fronts is the same: three fronts in total. However, the point \(D\) moved from the second to the third front when transitioning from Pareto dominance to the counting Pareto optimality-based sorting. Also note that the first front is always the same for both procedures. Indeed, a non-dominated point will always have the value of _PO-count_ equal to 0 and vice versa. Instead of the counting measure, we can also consider a probability measure. We refer to the relevant procedure as probabilistic _PO_, or _PO-prob_. In this case, instead of calculating the number of points that dominate the current one, we can estimate the probability of this point to be dominated. In our calculations, we assume that there are no duplicates. This is also enforced in our experiments. If we have no a priori knowledge on how the objectives are correlated, we assume them to be independent. Thus, the probability of any point to be dominated can be estimated by multiplying the probabilities of being dominated with respect to the individual objectives. Let us calculate the values of _PO-prob_ for the example presented in Section 3 assuming the independence of objectives \(f_{1}\) and \(f_{2}\). Point \(A\) is never dominated with respect to \(f_{2}\); thereby, the probability of being dominated with respect to this objective is 0, \(P\_dom_{f_{2}}(A)=0\). Considering the first objective \(f_{1}\), 4 points out of total number of 6 points dominate the point \(A\), \(P\_dom_{f_{1}}(A)=4/6\approx 0.667\). By multiplying these two values, we can estimate the value of _PO-prob_ as \(P\_dom_{f_{1}}(A)P\_dom_{f_{2}}(A)=0.667\ast 0=0\). Let us now analyze in a similar way the point \(B\). It is dominated by three points with respect to \(f_{1}\) (points \(C\), \(E\) and \(F\)), resulting in \(P\_dom_{f_{1}}(B)=3/6=0.5\).