# Multi-UAV Mission Allocation under Constraint
## 4 Simulation Results
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Number** & **Task Route** & \begin{tabular}{c} **Reconnaissance** \\ **Time (h)** \\ \end{tabular} & **Total Time (h)** & \
\begin{tabular}{c} **Waiting Time** \\ **(h)** \\ \end{tabular} &
\begin{tabular}{c} **Reconnaissance** \\ **Reward** \\ \end{tabular} \\ \hline UAV1 & 0-19-2-23-20-3-0 & 6 & 14.5209 & 1.5342 & 2.4672 \\ UAV2 & 0-6-7-15-13-12-0 & 6 & 15.6689 & 0 & 2.8167 \\ UAV3 & 0-18-22-21-14-9-0 & 6 & 14.3061 & 0 & 2.1804 \\ UAV4 & 0-4-16-25-11-24-0 & 6 & 14.2566 & 0.665 & 2.5817 \\ UAV5 & 0-10-1-17-5-8-0 & 6 & 14.1233 & 0 & 2.3878 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Assignment status of each unmanned aerial vehicle (UAV). Figure 5: Optimal solution of the multi-UAV mission planning problem. (b) Individual evaluation: Calculate the fitness of each individual in the population P(gen). (c) Select the operation: Apply the selection operator to the group. The purpose of the selection is to directly infer the optimized individual to the next generation or to generate a new individual through pairing to regenerate to the next generation. The selection operation is based on the fitness assessment of the individual in the group. (d) Crossover operation: The crossover operator is applied to the population. The core function of genetic algorithms is the crossover operator. (e) Variation operation: The mutation operator is applied to the population. That is, changes in the gene values at certain loci of individual strings in a population. The population P(gen) is subjected to selection, crossover, and mutation operations to obtain the next generation population P(gen+1). (f) Termination condition judgment: If gen = G, the individual with the greatest fitness obtained during the evolution process is used as the optimal solution output, and the calculation is terminated. The corresponding program flow chart is shown in Figure 6.  
The basic idea of the NSGA-II algorithm is as follows: First, the initial population of size N is randomly generated. After the non-dominated sorting, the first generation of the population is obtained by the three basic operations of selection, crossover, and mutation of the genetic algorithm. Second, at the beginning of the generation, the parent population is merged with the offspring population, and the fast non-dominated sorting is performed. At the same time, the crowding degree is calculated for each individual in the non-dominated layer, and the appropriate individual is selected according to the non-dominated relationship and the individual crowding degree to form a new one. The parent population; finally, the new progeny population is generated by the basic operations of the genetic algorithm: and so on, until the condition of the end of the program is met. The NSGA-II algorithm will be improved in the following areas:  
1. Fast non-dominated sorting  
When NSGA performs non-dominated sorting, each individual in a population of size N is compared against M objective functions and N-1 individuals in the population, with a complexity of  
Figure 6: Genetic algorithm (GA) basic process. O(MN), so N in the population. The complexity of the individual end comparison is O(MN2), that is, the time complexity of each pareto grading is O(MN2). In the worst case, each pareto level contains only one individual, and the time complexity required to perform N gradings increases to O(MN3). In view of this, a fast non-dominated sorting method is proposed in the paper, and the time complexity of this method is O(MN2). The algorithm needs to save two quantities: (1)The number of dominations np. This amount is the number of individuals who can dominate the individual p in the feasible solution space. (2) The SP is controlled by the individual. This quantity is a collection of all individuals in the feasible solution space that are dominated by individuals p.  
2. Retention of individual diversity in the population  
In NSGA-II, a crowding algorithm and an elite strategy are used instead of the shared function algorithm. 3.