# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.3 Evolutionary Algorithm
[43] proposed a multi-objective evolutionary algorithm (MOEA) for trajectory planning that introduces a Genetic Vector Router (GVR) while combining trajectory tracking capabilities with existing swarm behavior to measure the impact of these capabilities on the impact of swarm characteristics. By using \"immigrant\" population members to increase the search space and generate trajectories that meet mission requirements, they solved the problem of UAV formations exploring the terrain of larger areas and threatening regional trajectory planning. [PERSON] and [PERSON] [44] developed an efficient strategy for the assignment and trajectory planning of homogeneous UAVs, combining Voronoi diagrams and Genetic Algorithms (GAs) to generate efficient flyable trajectories in network shapes, solving the problem of task assignment, and trajectory planning in the presence of time constraints is addressed. [PERSON] and [PERSON] [45] proposed a new multi-frequency Vibration Genetic Algorithm (mVGA), which constructed a Voronoi diagram using height filtering and fuzzy c-means clustering methods. They generated some initial individuals based on Voronoi vertices to improve the initial population, thereby generating efficient and fast flyable trajectories and solving the local optimization problem in a relatively short optimization period. [PERSON] [46] proposed a flight-able trajectory planning method for multi-UAV systems, which combines the Genetic Algorithm (GA) and Bezier curves to generate an efficient and feasible trajectory of the UAV formation, solving the problem in which the curve is not smooth when using the traditional Genetic Algorithm (GA) for trajectory planning. [PERSON] and [PERSON] [47] proposed an improved constrained Differential Evolution (DE) algorithm, which combines the global search capability of the Differential Evolution (DE) algorithm and the constraint processing technology of level comparison, and they designed a level update strategy that solves the trajectory planning problem of formations under multiple constraints in real scenes. [PERSON] et al. [48] used a parallel Genetic Algorithm on the CUDA architecture to plan feasible trajectories for multiple UAVs; the algorithm first used a clustering method to find a subset of control points and then parallelized it on the programming computing platform. The Genetic Algorithm is used to solve each cluster and generate the feasible trajectory of the UAV formation, which solves the problem of long calculation time of the serial algorithm. [PERSON] et al. [49] proposed a co-evolutionary multi-UAV cooperative trajectory planning method, which applied the co-evolutionary Genetic Algorithm to trajectory planning, and they considered the sensors carried by each UAV in the formation quantity and location effects, real-time or near-real-time trajectory planning for each UAV, solving the problem of trajectory planning for UAV formations in dynamic environments. [PERSON] et al. [50] proposed a parallel optimization method, which uses real coding methods and effective selection operations, crossover operations, and mutation operations to improve the Genetic Algorithm (GA), and at the same time, the Particle Swarm Optimization algorithm (the combination of PSO) and Ant Colony Optimization algorithm (ACO) makes the ants in the PSO-ACO system have particle characteristics. Then, it uses the two algorithms to generate formation trajectories simultaneously, which solves the weak global search ability of the Genetic Algorithm (GA) and the Ant Colony Optimization algorithm (ACO) premature maturation problem. [PERSON] et al. [51] proposed an improved evolution method of Genetic Algorithm (GA) and Harmony Search (HS); the improved search method utilizes various evolution operators with the same properties at the starting position to determine the overall shortest trajectories, which solves the problem of trajectory planning for drone formations when collecting data from multiple roadside units (RSUs). [PERSON] et al.