# Optimization Dubins Path of Multiple UAVs for Post-Earthquake Rapid-Assessment
## 3 HGSA Algorithm
### Mutation  
For chromosomes with the same expected income and different total flight times as shown in Figure 4, we designed a heading angle index mutation operator for the second line of the chromosome. The pseudocode of the mutation operator is shown in Algorithm 2. ```
1:Input: a chromosome \(C\);
2:Output: a new chromosome \(C_{m}\) with no worse fitness than \(C\);
3:begin
4: calculate the total flight duration fitness of \(C\) using Equation (14), denoted as \(Fit2_{C}\);
5: calculate the number of columns in \(C\), denoted as \(N_{C}\);
6:for i=1 to \([0.1\times N_{C}]\)
7: randomly select a gene in \(C\), denoted as \(C_{g}\);
8: obtain the index of the heading angle of \(C_{g}\), denoted as \(h_{C_{g}}\) (\(h_{C_{g}}=\) the second line of \(C_{g}\));
9: randomly generate an index of the heading angle, denoted as \(h_{r}\);
10:while\(h_{r}=h_{C_{g}}\)
11: randomly generate an index of the heading angle, denoted as \(h_{r}\);
12:endwhile
13: replace the index of the heading angle at the location of \(h_{C_{g}}\) in \(C\) with \(h_{r}\);
14:endfor
15: obtain a mutated chromosome, denoted as \(C_{m}\);
16: calculate the total flight duration fitness of \(C_{m}\) using Equation (14), denoted as \(Fit2_{Cm}\);
17:if\(Fit2_{Cm}>Fit2_{C}\)
18:\(C_{m}=C\)
19:endif
20:end

Figure 5: Chromosomes stitching example. (**a**) there is only one shared target index in Ak and Bk, then the genes behind it are exchanged to obtain the new segments Ck and Dk; (**b**) there is no shared index in Ak and Bk, then stitch Bk to the end of Ak to obtain a new segment Ck, and stitch Ak to the end of Bk to obtain a new segment Dk. Since the mutation operation is used only for the heading angle, the targets accessed by the UAV and the access sequence are not changed, so there is no influence on the value of \(Fit1\). Furthermore, only when \(Fit2\) is worth raising, that is, only the variation is small, is the variation is accepted so that the fitness of the new chromosome obtained by the mutation operation is not worse than that of the original chromosome. ### Population Update

The population update operation is accomplished by replacing some of the chromosomes in the newly generated offspring with the same number of elite chromosomes in the parent population. The formula for calculating the number of replacing chromosomes is \(N_{F}=N_{P}\times(1-Gap)\), where \(N_{p}\) is the population size and \(Gap\) is the generation gap, which are both preset. A new population for the next iteration of the GA is obtained by using the chromosomes of the pre-\(N_{F}\) position in the parent population to replace the chromosomes of the post-\(N_{F}\) position in the child population. In addition, perform a fitness evaluation of the optimal chromosome \(C\). _Nbest_ in the new population and the optimal chromosome \(C\). _best_ in the current population. \(C\). _best_ is replaced by \(C\). _Nbest_ only if \(C\). _Nbest_ has a higher fitness. ### Adaptive Switching from the GA to SA

For a two-phase hybrid GA and SA algorithm, the switching point between the GA and SA is crucial and is affected by the number of iterations. Setting the switch point too early will reduce the quality of the solution. However, if the switching point is too late, the efficiency of the algorithm will be affected [32]. In general, the GA must run a fixed number of generations which depends mainly on the users' experience or preference rather than adaptive self-computation. Because of the strong optimization ability of the GA in the early stage, the growth rate of the fitness value is faster, but in the later stage, the GA exhibits a decaying rate of increase. Therefore, in this paper, the switching point between the GA and SA is set when the growth rate of the \(Fit1\) value of \(C\). _best_ decreases for 10 generations continuously. When the adaptive switching condition from the GA to SA is satisfied, the GA is terminated, and \(C\). _best_ is used as the initial solution of SA.