A Multi-objective Evolutionary Algorithm for Formation Structure Optimization of Unmanned Aerial Vehicles Performing Search Task

In order to solve the target search problem of the multiple Unmanned Aerial Vehicles (UAVs) under the condition of implicit communication, this paper firstly establishes a multi-objective optimization model of formation structure. The objective of this model is to maximize the invulnerability of information transmission topology and formation search efficiency. The constraints such as topology connectivity and safety distance are considered. Then, this paper proposes a multi-objective evolutionary algorithm CLUinD&O-MOEA based on NSGA-II, which combines the clustering method and improved crowding distance, in order to improve the efficiency of exploring the irregular frontier of this problem. In the early stage of the iteration process, the Self-Organizing Maps (SOM) method is used to cluster the population in the decision space, and each mating male parent is selected from the same cluster to improve the global search ability of the algorithm. At the end of the iteration process, the population is clustered in the target space, so that the algorithm can converge to the real PF faster. At the same time, this paper improves the calculation method of crowding distance, which combines the crowding distance of the solution in the target space and the decision space to improve the diversity of the population. In addition, a disturbance mechanism was designed for CLUinD&O-MOEA to solve the redundancy problem caused by the symmetry of formation geometry. Finally, the experimental results show that CLUinD&O-MOEA is better than the comparison algorithms CA-MOEA and NSGA-II-DE in solving the formation structure optimization problem, and can effectively improve the solving efficiency.