# Multi-Population Parallel Wolf Pack Algorithm for Task Assignment of UAV Swarm
## 2 Basic Knowledge and Literature Review
### Optimization Methods  
Optimization methods for the task assignment problem of UAV swarms are generally studied in three categories. The first category treats task assignment as a programming problem, such as the Hungarian algorithm [9], the branch and bound search algorithm [10], dynamic programming [11], the exhaustive method [12], Newton's method [13], the gradient method [14]and so on. These methods can obtain the optimal solution if there is a solution, but it is difficult to solve non-convex NP-hard problems. Generally, these methods need to abstract the problem to establish a mathematical model, so high mathematical ability is required, especially for large-scale problems. The methods that are easy to implement, such as the exhaustive method and the branch and bound search algorithm, have high time and space complexity. When the problem size increases, the difficulty of solving the problem increases sharply, and the time consumption increases exponentially [15]. The second category includes mainly the distributed optimization methods, such as the auction algorithm [16], the market-based decentralized algorithm [17], the contract network [18], etc. These methods utilize a market-based decision strategy as the mechanism for decentralized task selection and can naturally converge to a conflict-free solution. [PERSON] et al. [19] introduced consensus to the auction algorithm and proposed a consensus-based auction algorithm (CBAA) and a consensus-based bundle algorithm (CBBA) to improve the efficiency of conflict resolution. [PERSON] et al. [20] applied the CBAA to the task assignment of complex space crafts and found that the algorithm can guarantee successful assignment. These methods have excellent performance in small-scale distributed systems, but with the increase in the numbers of individuals in communication networks, the computation and time required for conflict resolution increase greatly. Hence, these methods are generally applicable to the coordination tasks in small-scale communication networks. In addition, these methods need build objective functions named bidding functions for individuals, and the bidding function directly determines the success and quality of the solution. The last category employs mainly bio-based heuristic algorithms, such as the Ant Colony Optimization Algorithm (ACO) [21], the Genetic Algorithm (GA) [22; 23], the Particle Swarm Optimization Algorithm (PSO) [24], etc. Such methods are inspired by the mechanism of natural evolution of biological populations and can approach optimal or sub-optimal solutions with finite calculation costs. Due to the characteristics of simplicity, robustness, parallelism, wide applicability and low structural requirements for the problem model, they are widely applied to various optimization problems [25]. In this paper, we focus on the application of heuristic algorithms in the task assignment of UAV swarms. The traditional classical heuristic algorithms still occupy the main position of optimization at present, and scholars have been committed to overcoming their defects of premature convergence and have put forward a large number of variants to adapt to various problems. In addition to the study of classical heuristic algorithms, many scholars are committed to designing new algorithms, such as the Fish Swarm Algorithm (FSA) [26], Bacterial Foraging Optimization (BFO) [27], the Shuffled Prog Leaping Algorithm (SFLA) [28], the Artificial Bee Colony (ABC) algorithm [29], the Wolf Pack Algorithm (WPA) [30] and so on. ABC has attracted much attention due to its simple optimization mechanism and the ability to move beyond a local optimal. In [29], compared with PSO and GA, it was found to perform well in solving five high dimensional numerical benchmark functions including the Griewank, Rastrigin, Rosenbrock, Ackley and Schwefel functions.