# Energy-Efficient UAVs Deployment for QoS-Guaranteed VoWiFi Service
## 5 Solving a Pseudo-Static Scenario
### Search Algorithm: GA  
A genetic algorithm is a heuristic search method inspired by the process of natural selection. A population of individuals (i.e., candidate solutions to the problem at hand) is evolved through evolutionary operators (e.g., crossover, mutation) toward better solutions. For every new generation, the population is evaluated and scored according to a fitness function and the best individuals are passed to the next generation. This process typically starts with a first generation of random individuals. In our problem, each individual represents the location of \(D\) drones \(\mathcal{X}=\{\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{D}|\mathbf{x}_{i}\in\mathcal{P},i \in\mathcal{D},\mathbf{x}_{i}\
eq\mathbf{x}_{j}|_{\forall j\
eq i}\}\), where \(\mathbf{x}_{i}\in\mathcal{P}\) stands for the location of drone \(i\). For example, consider a scenario with \(D=3\) drones; then, individuals would be represented by the following sequence of genes:  
\[\mathcal{X}|_{D=3}=\{\underbrace{x_{1},\,y_{1},\,z_{1}}_{\mathbf{x}_{1}},\, \underbrace{x_{2},\,y_{2},\,z_{2}}_{\mathbf{x}_{2}},\,\underbrace{x_{3},\,y_{3},\,z _{3}}_{\mathbf{x}_{3}}\} \tag{10}\]  
Algorithm 1 shows the pseudocode of our GA-based search method. The input of the algorithm is the set of ground users (\(\mathcal{U}\)) and their location (\(\mathbf{w}_{k}\)), the set of edges (\(\mathcal{P}\)), the minimum coverage constraint (\(C_{\text{min}}\)), the minimum speech quality constraint (\(R_{\text{min}}\)), and the maximum number of available drones (\(D_{\text{max}}\)). The algorithm starts by seeking solutions with one drone (\(D=1\) ) and then increases the number of UAVs until a sub-optimal solution is found (or until \(D_{\text{max}}\)). On each iteration, the genetic algorithm (lines from 3 to 18 in Algorithm 1) aims to find the best solution that meets the problem constraints. Every time that the genetic algorithm is initiated, an initial population of candidate solutions (i.e., individuals) is created as \(\mathcal{I}\) by the _GA_InitialPopulation_ function. Then, every individual in \(\mathcal{I}\) is evaluated using the _Check_ function. This function returns the objective function value (see Equation (9)) including the ratio of coverage and QoS-level. If one individual meets the problem constraints and improves the last best value of the objective function (\(f_{\text{obj}}^{*}\)), the individual is recorded as a candidate solution. After the assessment of one generation, the next one is created. In the next generation, some individuals are a copy of the best individuals from parents (function _GA_Elite_), some others are created applying operations of Crossover-and-Mutation (function _GA_CM_) and Self-Reproduction and Mutation (function _GA_SRM_) to the parents [50; 51]. This process is repeated until a maximum number of generations is reached without any improvement (exit criteria). ```
Input:\(\mathcal{P}\), \(\mathcal{U}\), \(\{\mathbf{w}_{k}\}\), \(D_{\text{max}}\), \(C_{\text{min}}\), \(R_{\text{min}}\) Output:\(\mathcal{L}^{*}\) (location), \(f^{*}_{\text{obj}}\) (obj. value) Initialization:\(D=1\), \(\textit{finish}=\text{False}\), \(\mathcal{L}^{*}=\varnothing\), \(f^{*}_{\text{obj}}=\text{Inf}\) while\((\textit{finish}\)and\(D\leq D_{\text{max}})\)dofinish = True; /* Build initial population */ \(\mathcal{I}=\text{GA\_InitialPopulation}\) (\(\mathcal{U}\), \(\{\mathbf{w}_{k}\}\)); while!