# Multi-Population Parallel Wolf Pack Algorithm for Task Assignment of UAV Swarm
## 2 Basic Knowledge and Literature Review
### Multi-Population Optimization Method
#### 2.4.1 The Basics of the Multi-Population Optimization Method  
A population is divided into multiple small sub-populations who evolve with their own evolution operations; every once in a while, sub-populations interact with each other via merging and communication processes to maintain population diversity and avoid premature convergence [46; 47]. The general flow of the multi-population optimization method is shown in Figure 4. Generally, the algorithm starts with initialization, including the setting of parameters, the generation of an initial population of solutions and the evaluation of the population. Then, the population is divided into multiple sub-populations and each sub-population is optimized independently with its own algorithm within a certain number of iterations. After that, sub-populations communicate to update themselves according to some rules and this process is called population migration. This step is the key to maintain diversity and accelerate the overall optimization progress. Finally, the process stops once the termination condition is met. The steps are described in detail as follows. Step 1: Configuration of the parameters. The parameters of multi-population optimization method include the maximum iterations, the size of the population, the number of sub-populations, the parameters of the algorithm corresponding to each sub-population and the parameters related to population migration. Step 2: Generation of the initial population. An initial population of solutions is created randomly or via some methods. Step 3: Evaluation of the population. The fitness of each individual in the population is calculated according to the objective function. Step 4: Division of the population into sub-populations. Sub-populations may have the same or different sizes. Individuals of the population are divided into sub-populations randomly or in the light of some criterion. Step 5: Sub-populations perform the optimization process simultaneously and independently, which is the main step of the method. Within certain iterations, each sub-population searches the solution space according to its own algorithm and parameters. According to sub-population selections of the optimization algorithms, multi-population optimization methods can be divided into isomorphic multi-population optimization and heterogeneous multi-population optimization. In the former method, all sub-populations have the same optimization algorithm and parameters, while in the latter method, the optimization algorithms or optimization parameters of each sub-population are different. Step 6: Judging whether the termination condition is met. Once the termination condition is met, the evolution process is stopped and the current best solution is output. Otherwise, Step 7 is begun. Step 7: Population migration, which is the key for multi-populations to maintain diversity and accelerate optimization. Through specific communication mechanisms and migration rules, each sub-population sends information on some individuals to other sub-populations and receives external individuals to replace its own ones. This is a process of fusion and renewal for sub-populations. Then, Step 5 is returned to. In the last decade, multi-population optimization methods have been studied in many fields, including cognitive radio networks [48], energy power [49], Cloud manufacturing [50], mobile ad-hoc networks [51], job-shop scheduling [52], path planning [53] and so on. Since each sub-population can run its own optimization algorithm independently, multi-population optimization methods have strong flexibility in selecting algorithms. [PERSON] et al. [54] applied the same algorithm with multiple sets of parameters in different sub-populations to generate high-quality and effective paths of robots. Through a high number of sub-populations interacting in parallel, the effect of each sub-population's parameters is compensated by individuals selected from other populations [55]. [PERSON] et al. [56] used  
Figure 4: General flow of the multi-population optimization algorithm.