# Parallel Compact Differential Evolution for Optimization Applied to Image Segmentation
## 2 Background
### Compact Differential Evolution Algorithm  
The cDE algorithm inherits the probability vector \((PV)\) and elites mechanism from rcGA [9; 29]. In cDE, \(PV\) is an \(n*2\) matrix and is not a vector [30]:  
\[PV=[\mu,\sigma] \tag{6}\]  
where \(n\) is the dimension of the problem. \(\mu\) and \(\sigma\) are \(n*1\) vectors. \(\mu_{i}\) and \(\sigma_{i}\) respectively represent the mean value and standard deviation of the normal distribution. The normal probability distribution function (PDF) is truncated on the interval [-1,1]. To make the area of the probability distribution function equal to 1, we normalize the height of the probability distribution function. \[PDF_{\mu_{i},\sigma_{i}}(x)=\frac{e^{-\frac{-(x-y_{i})^{2}}{2\sigma_{1}^{2}}}\sqrt{ \frac{2}{\pi}}}{\sigma_{i}(erf(\frac{\mu_{i}+1}{\sqrt{2}\sigma_{i}})-erf(\frac{ \mu_{i}-1}{\sqrt{2}\sigma_{i}}))} \tag{7}\]  
where \(erf()\) is the error function [31]. According to the description in [32], cumulative distribution function (CDF) can be constructed from Chebyshev polynomials. The specific steps of sampling can be expressed as follows:  
1. Construct a PDF with \(PV\) as a parameter. 2. Construct a cumulative distribution function through Chebyshev polynomials. 3. Generate a random number \(r\) over the (0, 1) interval, which is uniformly distributed. 4. Get the corresponding \(x\) through inverse cumulative distribution function (ICDF) according to \(r\). ```
1//Initialization generate \(Np\) individuals pseudo-randomly
2 whilebudget conditiondo
3 fork=1:Npdo
4 calculate the \(fit(x_{k})\)
5 fork=1:Npdo
6 //Mutation randomly select three individuals \(x_{r},x_{s}\), and \(x_{t}\)
7 compute \(x_{off}^{{}^{\prime}}=x_{t}+F*(x_{r}-x_{s})\);
8 //Crossover
9\(x_{off}=x_{off}^{{}^{\prime}}\)
10 fori=1:ntdo
11 ifrand(0, 1)>Crthen
12\(x_{off}[i]=x_{k}[i]\)
13 //Selection
14 iffit(\(x_{off}\)) \(\geq\)fit(\(x_{k}\))then
15 save index for replacement \(x_{k}=x_{off}\)
16
17
18 perform replacements
```  
**Algorithm 1**DE algorithm pseudocode (rand/1/bin)  
The sketch map of the sampling mechanism is shown in Figure 1.  
At the beginning of the cDE algorithm, \(\mu\) is initialized to 0, \(\sigma\) is initialized to 10. A solution is sampled from the solution space as elite. During each iteration, a new temporary offspring will be generated through the new \(PV\). The temporary offspring will be compared with the elite. The one with higher fitness will be recorded as the winner, while the one with lower fitness as a loser. \(PV\) update rules are as follows:  
\[\mu_{i}(gth+1)=\mu_{i}(gth)+\frac{(winner_{i}-loser_{i})}{Np} \tag{8}\]  
\[\sigma_{i}(gth+1)=\sqrt{(\sigma_{i}(gth))^{2}+(\mu_{i}(gth))^{2}-(\mu_{i}(gth+ 1))^{2}+\frac{(winner_{i}^{2}-loser_{i}^{2})}{Np}} \tag{9}\]There are two different versions of cDE, which are called persistent elitism compact differential evolution (pe-cDE) and non-persistent elitism compact differential evolution (ne-cDE) (see [9]). For pe-cDE algorithm, the elite is replaced by the temporary offspring when the elite is loser, while for the ne-cDE algorithm, if there is no replacement after the \(\eta\) (a predefined constant representing the threshold) comparison, whatever the state of elite's fitness is, the elite will be replaced by temporary offspring. The pseudocode of pe-cDE and ne-cDE are shown in Algorithms 2 and 3.