# OADC: An Obstacle-Avoidance Data Collection Scheme Using Multiple Unmanned Aerial Vehicles
## 4 Algorithms
### A Genetic-Algorithm-Based Path Planning with VRAOA (GA w/VRAOA)
#### 4.2.3 Selection, Crossover, and Mutation Operators  
In GA, to produce new offspring in the next generation, a selection operator is used that selects the best individuals from the population based on the fitness value. Generally, there is an intuition that parents with good fitness values produce fitter children, and there is an opportunity to find an optimal or near-optimal solution for better-fitted children. On the other hand, chromosomes with lower fitness can also produce offspring with high fitness. Therefore, we used the roulette-wheel operator [33] to select chromosomes with a probability of \(P_{s}\). The best individuals are selected based on a ratio, which is the probability \(P_{s}\). According to this operator, the ratio of the fitness of each chromosome over the sum of the fitness of all chromosomes in the population \(P^{m}\) is calculated for each generation, which can be presented as  
\[P_{s}(C_{l}^{m})=\frac{F_{l}(C_{l}^{m})}{\sum\limits_{l\in P^{m}}F_{l}(C_{l}^{m})} \tag{14}\]  
Here, \(F_{l}(C_{l}^{m})\) is the fitness value of chromosome \(C_{l}^{m}\), and the sum of the fitness value of all chromosome is \(\sum\limits_{l\in P^{m}}F_{l}(C_{l}^{m})\). The crossover operation involves mating the chosen parents to produce a new generation of offspring, each of whom carries genes from both parents. The order-based crossover operator (OX2) [34] has been selected in the GA w/VRAOA algorithm. In OX2, random portions (a random number of genes) from the first parent are selected, and the selected portions are set to empty. Then, the empty spaces are filled with the ordered list of the second parent without duplication of the genes. In a similar manner, we swap the first parent's and the second parent's roles by using similar placements. For example, consider two candidate solutions (chromosomes) \(C_{a}=[0,1,2,3,4,5]\) and \(C_{b}=[0,4,5,3,2,1]\) with five sensors and a sink (0). In the OX2 operation, random several positions in \(C_{a}\) are selected. Suppose positions three, four, and five are selected. Then, the selected positions are set to empty, i.e., \([0,1,*,*,5]\). Finally, fills up the empty positions with the sensors in the same order as in \(C_{b}\), i.e., \([0,1,4,3,2,5]\). The mutation operator in the GA brings diversity to the population and is essential for the convergence of the GA. We used a swap mutation operator [35], which is performed between random genes in the crossed-overed chromosomes for balancing the exploration and exploitation in the search space. The crossover and mutation operations occur once every generation with a certain probability. These operations repeat until the new offspring meets all the constraint requirements and reaches a predetermined number of iterations [36]. The crossover and mutation probabilities have been selected after various trials to provide the optimal solutions for the problem and avoid the premature convergence of the algorithm. Algorithm 2 presents the pseudo-code of the GA w/VRAOA. The sensors in the environment are clustered into a number of groups, \(c\), using the K-means algorithm (line number 1), where each cluster is assigned to a UAV. Then, in line numbers 2-15, for each UAV or cluster, the initial population is created, genetic operations (selection, crossover, and mutation) are performed, and the path for each UAV is obtained. Figure 4: Graph representation for the Dijkstra algorithm. ```
Input: Set of sensor nodes for \(m\) clusters. Output: Set of tours for \(m\) UAVs with minimum traveling distances. ```
1: apply K-means clustering algorithm to the senor node and made \(c\) clusters for \(c\) UAVs
2: Set total number of chromosomes \(n_{pop}\), crossover probability \(P_{cr}\), mutation probability \(P_{mn}\), selection probability \(P_{s}\), generation \(\mathfrak{g}\gets 0\), \(\mathfrak{g}_{max}\). 3:for each cluster \(m\)do\(\triangleright\)\(m\) is the number of clusters
4: Randomly generate initial population. 5: Evaluate fitness for each chromosomes.