## 3 \(k\)-Pareto Optimality-Based Sorting for Genetic Optimization
### Formal Definition of \(k\)-Pareto Optimality  
As we can see, the selection step of a genetic optimization procedure requires sorting the population of solutions according to a predefined dominance relation. In [14], we introduced sorting by \(k\)-Pareto optimality and demonstrated its utility in many-objective genetic optimization.  
Let us consider a set \(X\) with a binary relation \(R\). In the context of \(n\) objectives introduced in the previous section, \(R\) corresponds to the relation \(aRb\) iff \(\forall i\in\{1,\ldots,n\}:f_{i}(a)\geq f_{i}(b)\). Thus, Pareto dominance corresponds to the relation \(R^{*}\) defined by \(aR^{*}b\) iff \(aRb\wedge\
eg(bRa)\). We also consider a positive and \(\sigma\)-finite measure \(\mu\) defined on \(X\). The measure \(\mu\) can be defined in different ways. Important examples are the counting measure and probability measures. Depending on the definition of \(\mu\), it can indicate the following characteristics of the elements in \(X\): _how many?_, _how likely?_, _how important?_, etc. Thus, we have a measure space \((X,\Sigma,\mu)\), where \(\Sigma\) is a set of subsets of \(X\) and \(\mu\) intuitively indicates the size of these subsets.  
The \(k\)-Pareto optimality of an individual \(a\) is the measure of the set of points that Pareto dominate \(a\) and is written as \(\text{po}(a)\). Formally, \(\text{po}(a)=\mu(\{x:xR^{*}a\})\). If \(\mu\) is a probability measure, the \(k\)-Pareto optimality of an element \(a\), \(\text{po}(a)\), is the _likelihood_ an element drawn  
Figure 2: Flowchart of the genetic optimization procedure.  
at random from \(X\) is strictly preferable to \(a\). In the case of the counting measure, \(\text{po}(a)\) is the _number_ of elements from \(X\) that are strictly preferable to \(x\).  
Choice between \(a\) and \(b\) means that neither \(a\) Pareto dominates \(b\) nor \(b\) Pareto dominates \(a\). That is, \(a\) and \(b\) are equally preferable and belong to the same Pareto front. The notion of choice is closely related to the notion of _diversity_. This concept is more practically interesting and can be formally defined as the likelihood that two elements drawn at random from \(A\) offer choice. Thus, it is the choice offered by \(A\) divided by \(\mu(A)^{2}\).  
In [14], we formally proved that among all topological sorting methods, sorting by \(k\)-Pareto optimality maximizes the diversity of the subset of the best individuals of a predefined _measure_ (_size_ in the case of counting measure). This property holds for any type of element (points on a plane, graphs, functions, etc.), dominance or preference relations (smaller/larger than, parent/child, etc.), and measures defined on the set under investigation (counting measure, probability measure, etc.). The property of diversity maximization suggests that this sorting procedure can be useful in the selection step of genetic optimization. Indeed, the maximization of diversity of the generated solutions allows for investigating the search space more efficiently. Thereby, we suggest changing the non-dominated sorting to the sorting by \(k\)-Pareto optimality in the step 4.1 of the flowchart presented in Section 2. We also experiment with two types of measures \(\mu\): a probability measure and the counting measure.