## 5 UAV Placement Based on NSGA-II  
In this section, we present the terminologies used by NSGA-II [26] and the main genetic algorithm elements (individual or chromosome, fitness, selection, population, and genetic operators). The term solutions and individuals are interchangeably used along the remaining part of this paper.  
NSGA-II is an elitist MOEA, which comprises two main procedures. One is the Pareto ranking procedure, which aims at sorting the population into different non-domination levels (\(i_{rank}\)) in ascending order. The lowest ranking level contains the best solution. In order to identify solutions of the first non-dominated front in a population of size \(N\), each solution is compared with every other solution in the population to find if it is dominated. After all members of the first non-dominated front are found, they are discounted temporally so that the next non-dominated front could be found by repeating this first procedure. The other procedure is the diversity preservation, which is used to maintain a good spread of solutions in the obtained set of solutions. Members in each non-dominated front are assigned a value called _crowding distance_ (\(i_{distance}\)). This value gives an estimate of the density of solutions surrounding a particular solution in the population. A solution with a smaller value of this distance measure is, in some sense, more crowded by other solutions. The crowded-comparison operator, denoted as \(\prec_{n}\), is used to distinguish the best solution during the selection process. It assumes that every individual \(i\) in the population has two attributes, \(i_{rank}\) and \(i_{distance}\). The partial order \(\prec_{n}\) is defined as:  
\[\begin{split} i\prec_{n}j\text{ if }(i_{rank}<j_{rank})\\ \text{or }((i_{rank}=j_{rank})\text{ and }(i_{distance}>j_{ distance}))\end{split} \tag{10}\]  
That is, between two solutions with differing non-domination ranks, we prefer the solution with the lower (better) rank. Otherwise, if both solutions belong to the same front, then we prefer the solution that is located in a less crowded region.  
Algorithm 2 shows the main loop of NSGA-II proposed by the authors in [26], where the call of the routines fast-non-dominated-sort (\(R_{t}\)) and crowding-distance-assignment (\(\mathcal{F}_{i}\)) corresponds to the first and second procedure described above, respectively. \(R_{t}\) is of size \(2N\) formed by combining parent \(S_{t}\) and offspring \(Z_{t}\) populations. \(\mathcal{F}_{i}\) refers to the \(i^{\text{th}}\) front or level. The detailed explanation of the aforementioned procedures is also available in [26]. We describe the main loop of NSGA-II as follows:  
```
1:\(R_{t}=S_{t}\cup Z_{t}\)
2:\(\mathcal{F}\) = fast-non-dominated-sort (\(R_{t}\))
3:\(S_{t+1}=\emptyset\) and \(i=1\)
4:Until\(|S_{t+1}|+\mathcal{F}_{i}\leq N\)
``` ```
**Algorithm 2** NSGA-II main loop.
```
1:\(R_{t}=S_{t}\cup Z_{t}\)
2:\(\mathcal{F}\) = fast-non-dominated-sort (\(R_{t}\))
3:\(S_{t+1}=\emptyset\) and \(i=1\)
4:Until\(|S_{t+1}|+\mathcal{F}_{i}\leq N\) ```
```
```

**Algorithm 3** NSGA-II main loop.

```
1:\(R_{t}=S_{t}\cup Z_  
* Sort in descending order using \(\prec_{n}\);
* Choose the first \((N-|S_{t+1}|)\) elements of \(\mathcal{F}_{i}\);
* Use selection, crossover, and mutation to create a new population \(Z_{t+1}\);
* Increment the generation counter.