## 3 \(k\)-Pareto Optimality-Based Sorting for Genetic Optimization
### Genetic Optimization Overview  
Let us consider \(n\) objectives \(f_{i}\), \(i\in\{1,\ldots,n\}\), and a maximization task which consists of the simultaneous maximization of all \(n\) objectives over a set \(X\) of solutions, that is,  
\[\begin{split}\text{maximize }\{\vec{f}(a)\equiv&(f_{1}(a),f_{2 }(a),\ldots,f_{n}(a))\}.\\ &\text{ over }a\ \in X\end{split} \tag{1}\]  
The binary concept of Pareto-dominance is defined as follows.  
**Definition 1**.: _An individual \(a\) Pareto-dominates an individual \(b\) if: \(\forall i\in\{1,\ldots,n\}:f_{i}(a)\geq f_{i}(b)\quad\land\quad\exists i\in\{1, \ldots,n\}:f_{i}(a)>f_{i}(b)\)._  
An individual is said to be _Pareto-optimal_ if it is not Pareto-dominated by any other element. The goal of multi-objective optimization is to find a set of Pareto-optimal solutions spread over the whole Pareto-frontier. Genetic optimization algorithms aim to solve this problem based on a biologically inspired heuristic: the evolution of a set of randomly initialized solutions.  
In Figure 2, we present the general flowchart of the genetic optimization procedure. The main steps of the procedure are explained below.  
1. First, we create an initial population of solutions (or individuals) of a predefined size, _pop_size_, and evaluate the fitness of every individual with respect to a predefined fitness function, step 1. In the case of multi- or many-objective optimization, this is a function with multi-dimensional output.
2. Second, we select a subset of individuals for \"procreation\" based on a chosen parent selection criterion, step 2. Two popular criteria are random and tournament selection. In random selection, the parents are chosen randomly; in tournament selection, the choice is made based on fitness among a set of randomly selected individuals of a predefined size.
3. Next, on the step 3, the chosen parents are \"mated\" to create a required number of children or offspring. This operation is also known as crossover. Often, the number of children is equal to the size of the original population. The generated offspring can also be mutated. The latter process is controlled by the value of the mutation probability, _mut_prob_. After evaluating the fitness values for the newly created offspring, the two sets of solutions are joined.
4. Finally, on the selection step, step 4, the combined population is sorted according to a specific criterion, and the best _pop_size_ individuals are advanced to the next generation. The evolution continues until a certain criterion is fulfilled. Often, the process is controlled by the maximum number of generations, _n_gen_.  
When the number of objectives is larger than 1, various methods can be used to sort the combined population of solutions in step 4 of the flowchart. The popular _NSGA-II_ algorithm performs the following: First, all solutions are assigned to fronts using the Pareto dominance (_PD_) relation. Next, the crowding distance is calculated for all individuals within the same front. As reflected in the name, the crowding distance measures the distance to the nearest individual within a front. Finally, the population is sorted with respect to fronts and the crowding distance as the primary and the secondary criteria. This procedure ensures that the most fitted solutions advance to the next generation. The usage of crowding distance allows one to choose the solutions that are spread all along the non-dominated front and helps avoid concentration. See [6] for a more detailed presentation of _NSGA-II_.