# Multi-Population Differential Evolution Algorithm with Uniform Local Search
## 4 The Proposed Algorithm
### MUDE (Multi-Population Differential Evolution)  
In this subsection, we put forward a novel multi-island based DE algorithm, MUDE, which implements a differential mutation strategy to the island by evolutionary ratio. The information between islands is exchanged according to SIM, and the local exploration is carried out by ULS. The MUDE procedure is shown in Figure 3.  
Figure 3: MUDE procedure.  
Figure 2: Example of ULS.  
In Figure 3, the soft island model is used to migrate individuals between subpopulations, and the optimal individual between subpopulations is to perform a local search by uniform local search. Meanwhile, the MUDE pseudocode is provided in Algorithm 1.  
There are four input parameters in MUDE, i.e., population size (\(NP\)), individual dimension (\(D\)), migration probability (\(P\)), and benchmark function (\(f\)). The global optimal is the output value of the algorithm. On lines 1 and 2, the population p are randomly initialized and fed into the benchmark function to obtain fitness values. On line 3, we choose three strategies to build a strategy pool, Equations (2), (4), and (5).  
On lines 4 and 5, the stopping condition of MUDE is controlled by the function evaluation times FES, and the MUDE will stop evolving when FES is larger than MaxFes. The population is randomly split into k subpopulations on line 6. On line 7, parameters \(F_{i}\) and \(CR_{i}\) are calculated from the Cauchy distribution and normal distribution respectively, i.e., \(N(uF_{i},0.1)\) and randn(\(uCR_{i},0.1\)). \(uFi\) and \(uCR_{i}\) are updated as follows.  
\[uF_{i}=(1-c)\cdot uF_{i}+c\cdot mean_{L}(S_{F,i}) \tag{9}\]  
\[uCR_{i}=(1-c)\cdot uCR_{i}+c\cdot mean_{A}(S_{CR,i}) \tag{10}\]  
where, \(mean_{L}\) and \(mean_{A}\) are the Lehmer mean.  
On lines 8 and 9, first, the fitness value of each island between generations is computed. Then the subpopulation chooses the appropriate strategy according to the ratio. On line 10, the individual of the subpopulation is migrated according to SIM. Finally, the global best \(fit_{best}\) is returned.  
In MUDE, the multi-strategy mechanism is beneficial to enhance the exploitation ability of the population, the SIM improves population diversity, and ULS improves the exploration of the population.  
```
Input:\(NP\), \(D\), \(P\), \(f\) Output: The population's best solution: \(fit_{best}\)
1. Generate the population \(p\) by the Equation (1);
2. Calculate the individual function values \(fit\);
3. Strategy pool \(Sp=\{Sp_{1},Sp_{2},\ldots,Sp_{n}\}\), set \(uCR_{i}=0.5\), \(uF_{i}=0.5\), \(f_{i}=0\), \(Fes_{i}=0\) for each strategy;
4. \(FES=NP\);
5. while\(FES\leq MaxFes\)
6. The population \(p\) is the randomly divided \(k\) subpopulation, \(p=\{p_{1},p_{2},\ldots,p_{k}\}\);
7. Calculate \(F_{i}\) and \(Cr_{i}\) for each subpopulation;
8. Pick a \(Sp_{i}\) for each subpopulation according to evolutionary ratio;
9. Perform strategy \(Sp_{i}\) for \(p_{i}\);
10. Migrate individual between subpopulation by probability \(P\) of SIM;
11. Perform the local exploration from each \(p\) by ULS;
12. end while
13. Return \(fit_{best}\).
```  
**Algorithm 1** MUDE algorithm