# Multi-Population Parallel Wolf Pack Algorithm for Task Assignment of UAV Swarm
###### Abstract  
The effectiveness of the Wolf Pack Algorithm (WPA) in high-dimensional discrete optimization problems has been verified in previous studies; however, it usually takes too long to obtain the best solution. This paper proposes the Multi-Population Parallel Wolf Pack Algorithm (MPPWPA), in which the size of the wolf population is reduced by dividing the population into multiple sub-populations that optimize independently at the same time. Using the approximate average division method, the population is divided into multiple equal mass sub-populations whose better individuals constitute an elite sub-population. Through the elite-mass population distribution, those better individuals are optimized twice by the elite sub-population and mass sub-populations, which can accelerate the convergence. In order to maintain the population diversity, population pretreatment is proposed. The sub-populations migrate according to a constant migration probability and the migration of sub-populations are equivalent to the re-division of the confluent population. Finally, the proposed algorithm is carried out in a synchronous parallel system. Through the simulation experiments on the task assignment of the UAV swarm in three scenarios whose dimensions of solution space are 8, 30 and 150, the MPPWPA is verified as being effective in improving the optimization performance. Wolf Pack Algorithm (WPA); multi-population optimization algorithms; Multi-Population Parallel Wolf Pack Algorithm (MPPWPA); approximate average division method; elite-mass population distribution; population pretreatment; synchronous parallel system; task assignment of UAV swarm +
Footnote †: journal: Applied Sciences  
12 November 2021  
13 December 2021  
16 December 2021  
**Publisher's Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. **  
**C. O. Copyright: 2021 by the authors. License MDP, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/by/4.0/](https://creativecommons.org/licenses/by/4.0/)]([https://creativecommons.org/licenses/by/4.0/](https://creativecommons.org/licenses/by/4.0/))). **  
**1. Introduction**  
During the Nagorno-Karabakh conflict in 2020, it was shocking to witness UAV swarms being employed to attack the ground targets precisely and roundly. It is an inevitable trend that Unmanned Aerial Vehicle (UAV) swarms will play an important role in future war [1]. Consequently, the task assignment of UAV swarms has become a research hotspot in recent decades. There are two core problems in task assignment. One is to establish a model for a specific operational process which has obtained abundant achievements after decades of extensive research, such as TSP (Travelling Salesman Problem), VRP (Vehicle Routing Problem), MILP (Mixed Integer Linear Programming), CMTAP (Cooperative Multiple Task Assignment Problem) and their extensions. The other is to design an appropriate optimization algorithm to solve the model. The quality of an optimization method determines the quality of a UAV's task sequence and then affects the overall combat effectiveness. Although the development of optimization algorithms is also thriving, there are few existing studies that solve the task assignment with high dimensionality (task assignment for 100 UAVs, for instance). In this paper, we proposed a novel heuristic method called the multi-population parallel Wolf Pack Algorithm (MPPWPA), which is improved from the basic Wolf PackAlgorithm (WPA) and is suitable for resolving the high-dimensional task assignment problems. The main contribution of this paper is to incorporate the multi-population optimization method and the parallel computing with WPA to reduce the convergence time. The remainder of this paper is organized as follows. Section 2 mainly describes the basic knowledge and corresponding literature review.