# 3D Global Path Planning Optimization for Cellular-Connected UAVs under Link Reliability Constraint
## 3 Methodology
### Optimization Algorithms
#### 3.3.2 Genetic Algorithm  
GA is the most essential evolutionary algorithm, which has been inspired by the Darwinian evolution theorem concepts involving an initialization method, objective function to evaluate each chromosome, natural selection, crossover, and mutation operators. Conventionally, GA has been used as an effective method to solve the 2D path planning problem and helps to find an optimal global path for many robotic problems.  
The GA algorithm initially starts with generating a random set of populations, representing possible solutions for the optimization problem. Each solution needs to be evaluated by an objective function to qualify the generated solutions. In the next step, a selection operation is used to choose the parents that are subjected to reproduction according to their objective function value. Later, the crossover operation is applied to produce new progenies by recombining data from the two parents selected in the previous step. Another genetic operation that is applied is the mutation operation, which is used to enhance the diversity of the population by changing the genetic structure of parents based on a mutation rate. This procedure is repeated until the termination criteria are satisfied.  
The parent selection criteria for crossover and mutation are based on the merit of individuals, in which individuals with better cost values have a higher chance of being selected for crossover and mutation. As such, the Boltzmann method is used to calculate the selection probabilities associated with each individual:  
\[p_{i}=\frac{e^{-\eta\frac{c_{i}}{cmax}}}{\sum_{j=1}^{n_{pop}}e^{-\eta\frac{c_ {j}}{cmax}}}, \tag{23}\]  
where \(\sum_{i=1}^{n_{pop}}p_{i}=1\), \(c_{i}\) is the cost value corresponding to the \(i^{th}\) individual, and \(c_{max}\) is the worst cost value of the population, which is added for normalization purposes. \(\eta\) is the selection pressure. If \(\eta=0\), the selection probabilities of all individuals are the same, which is equivalent to a random selection, where \(p_{i}=\frac{1}{n_{pop}}\)\(\forall i\in n_{pop}\). If \(\eta\rightarrow\infty\), the selection probability of the best individual is one, and the selection probability of the rest of the population is zero. In this study, the roulette wheel selection (RWS) method [55] was used for population selection.  
Let us define \(p_{c}\) and \(p_{m}\) as crossover and mutation rate; then the number of offspring, \(n_{c}\), and mutants, \(n_{m}\), can be calculated as:  
\[n_{c}=2\times\left\lceil\frac{p_{c}\times n_{pop}}{2}\right\rceil \tag{24}\]  
\[n_{m}=\left\lceil p_{m}\times n_{pop}\right\rceil \tag{25}\]  
The termination criteria for GA are the same as PSO, and NFE is defined as  
\[NFE(t)=n_{pop}+(n_{c}+n_{m})\times n_{it}. \tag{26}\]  
Table 4 lists the simulation parameters for GA in different scenarios, and Algorithm 2 presents the pseudo-code of GA.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Parameter** & \(n_{pop}\) & \(n_{it}\) & \(p_{c}\) & \(p_{m}\) & \(\xi\) & \(\eta\) \\ \hline
**Value** & 50 & 150 & 0.8 & 0.3 & 0.02 & 8 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Parameters for GA simulations in different scenarios.