A Multilevel Splitting Algorithm for Quick Sampling

As the initial state of the candidates, the samples of the elite set are crucial in the framework of the multilevel splitting algorithm. As mentioned above, the selection of the elite set is usually performed as follows: for the $k$ -th level, rank the components of ${𝒳}_k=\{X_1^k,X_2^k,\mathrm{\dots },X_N^k\}$ sequence and reserve a predetermined number of samples that have the best objective function values. Experimental research has determined that if the objective function is more complex, ${ℰ}_k$ might overlap ${ℰ}_{k-1}$ as $k$ is close to $m$ , which shows the convergence speed. Therefore, we expand the elite set selection range far beyond that of the current collection ${𝒳}_k$ , but also involve set ${ℰ}_k$ . That is, we choose $N_E=N\rho$ top samples from the set ${𝒳}_k^{\prime }={𝒳}_k\cup {ℰ}_{k0}$ to construct ${ℰ}_k$ . If $k=0$ , let ${ℰ}_0=[]$ . This procedure is presented below:

• If $k<1$ , randomly generate ${𝒳}_0=\{X_1^{(0)},\mathrm{\dots },$ $X_N^{(0)}\}.$ Let ${𝒳}_0^{\prime }={𝒳}_0\cup {ℰ}_0=\{X_1^{(0)},\mathrm{\dots },X_N^{(0)}\}$ , rank the objective function value ${ℱ}^{(0)}=(f_1^{(0)},\mathrm{\dots },f_N^{(0)})$ of each sample of ${𝒳}_0^{\prime }$ as $f_{J_1}^{(0)}<\mathrm{\dots }<f_{J_N}^{(0)}$ , and choose ${ℰ}_1=\{X_{J_1}^{(0)},\mathrm{\dots },$ $X_{J_{N_E}}^{(0)}\}$ ;

• If $k⩾1$ , let ${𝒳}_k^{\prime }={𝒳}_k\cup {ℰ}_k=\{X_1^{(k)},\mathrm{\dots },$ $X_N^{(k)},X_{J_1}^{(k-1)},\mathrm{\dots },X_{J_{N_E}}^{(k-1)}\}$ . The sorted function is $f_{J_1}^{(k)}<\mathrm{\cdots }<f_{J_{N+N_E}}^{(k)}$ , and use the best $N_E$ samples to construct the elite ${ℰ}_k$ , where $J_i,i=1,\mathrm{\dots },N_E$ , comprises the subscript index of the sorted order.

In previous work, we integrated the DE algorithm into the splitting framework to produce the next generation and obtained a good global optimization result. On this basis, here, we propose a novel splitting mechanism that combines an adaptive differential evolution algorithm with a local searching algorithm. We update the intermediate point using a dimension-by-dimension approach to improve the diversity.

(1) Adaptive differential evolution algorithm

Define the elite population as

(2) $$(X_1^{(k)},\mathrm{\dots },X_{N_E}^{(k)})=\left(\begin{array}{ccc}\hfill X_1^{(k)}(1)\hfill & \hfill \mathrm{\cdots }\hfill & \hfill X_1^{(k)}(D)\hfill \\ \hfill \mathrm{⋮}\hfill & \hfill \mathrm{\ddots }\hfill & \hfill \mathrm{⋮}\hfill \\ \hfill X_{N_E}^{(k)}(1)\hfill & \hfill \mathrm{\cdots }\hfill & \hfill X_{N_E}^{(k)}(D)\hfill \end{array}\right)$$

The main steps of the adaptive DE algorithm in each iteration are as follows:

• Mutation. For the $i$ -th target point $X_i^{(k)}=$ $(X_i^{(k)}(1),\mathrm{\dots },X_i^{(k)}(D)),$ $i=1,\mathrm{\dots },N_E,$ $N_E$ is the size of the elite set and $k$ denotes the splitting level. The mutation point ${\stackrel{\dot{}}{X}}_i^{(k)}=({\stackrel{\dot{}}{X}}_i^{(k)}(1),\mathrm{\dots },{\stackrel{\dot{}}{X}}_i^{(k)}(D))$ of the DE/rand/1/bin strategy is:

(3) $${\stackrel{\dot{}}{X}}_i^{(k)}=X_{r_1}^{(k)}+F\cdot (X_{r_2}^{(k)}-X_{r_3}^{(k)})$$

where $r_1$ , $r_2$ , and $r_3$ are three unequal random and uniform individuals of set $\{1,2,\mathrm{\dots },N_E\}/i$ . $F$ is a magnification factor belonging to $[0,2]$ .

To enhance the validity of the offspring population, we propose the use of a novel adaptive DE algorithm for adaptively choosing the control parameter $F$ . We assign $F={[0.5,\mathrm{\dots },0.5]}_{N\times D}$ to start. Then, Eq. ( 3 ) can be rewritten as follows:

(4) $${\stackrel{\dot{}}{X}}_i^{(k)}(d)=X_{r_1}^{(k)}(d)+F(d)\cdot (X_{r_2}^{(k)}(d)-X_{r_3}^{(k)}(d))$$

where $d=1,2,\mathrm{\dots },D$ . If ${\stackrel{\dot{}}{X}}_i^{(k)}(d)$ exceeds the range of the decision variance, reset the mutation point as follows:

(5) $${\stackrel{\dot{}}{X}}_i^k(d)=\{\begin{array}{cc}L(d),\hfill & \text{if }{\stackrel{\dot{}}{X}}_i^{(k)}(d)<L(d);\hfill \\ U(d),\hfill & \text{if }{\stackrel{\dot{}}{X}}_i^{(k)}(d)>U(d)\hfill \end{array}$$

where $U(d)$ and $L(d)$ are the upper and lower bounds of the $d$ -th dimension, respectively.

In this process, if the mutation point ${\stackrel{\dot{}}{X}}_i^{(k)}(d)$ is worse than the target point $X_i^{(k)}(d)$ , choose $F(d)$ in the same dimension of the next generation as shown in Eq. ( 6 ). Reset $F(d)=\text{0.5}$ when it is less than 0 or greater than 1. Otherwise, reserve $F(d)$ for the next generation, that is,

(6) $$F(d)=\{\begin{array}{cc}F(d)+0.1\times N(0,1),\hfill & \text{if }f(X_i^{(k)})<f({\stackrel{\dot{}}{X}}_i^{(k)});\hfill \\ F(d),\hfill & \text{otherwise}\hfill \end{array}$$

• Cross-over. Diversity can be improved with a cross-over factor. For simplicity, this is set to be a constant in the range of [0, 1] (e.g., $\text{CR}=$ 0.8) to determine whether the trail point inherits the value of the mutation point or remains unchanged, that is,

(7) $${\tilde{X}}_i^{(k)}=\{\begin{array}{cc}{\stackrel{\dot{}}{X}}_i^{(k)},\hfill & \text{if }\text{rand}(0,1)⩽\text{CR};\hfill \\ X_i^{(k)},\hfill & \text{otherwise}\hfill \end{array}$$

In SADE-L, $\text{CR}={[0.8,\mathrm{\dots },0.8]}_{N\times D}$ at the start, and Eq. ( 7 ) can be rewritten as follows:

(8) $${\tilde{X}}_i^{(k)}(d)=\{\begin{array}{cc}{\stackrel{\dot{}}{X}}_i^{(k)}(d),\hfill & \text{if }\text{rand}(0,1)⩽\text{CR}(d);\hfill \\ X_i^{(k)}(d),\hfill & \text{otherwise}\hfill \end{array}$$

Generate $\text{CR}(d)$ as shown in Eq. ( 9 ) if the candidate fails and reset it to equal 0.8 when it goes beyond the boundaries. Otherwise, reserve $\text{CR}(d)$ for the next generation.

(9) $$\text{CR}(d)=\{\begin{array}{cc}\text{CR}(d)+\text{0.1}\times N(0,1),\hfill & \text{if }f(X_i^{(k)})<f({\stackrel{\dot{}}{X}}_i^{(k)});\hfill \\ \text{CR}(d),\hfill & \text{otherwise}\hfill \end{array}$$

• Selection. Compute the objective function values of $X_i^{(k)}(d)$ and ${\tilde{X}}_i^{(k)}(d)$ , then make a comparison to choose a solution that can survive to the next level.

(10) $$X_i^{(k+1)}(d)=\{\begin{array}{cc}{\tilde{X}}_i^{(k)}(d),\hfill & \text{if}f({\tilde{X}}_i^{(k)})<f(X_i^{(k)});\hfill \\ X_i^{(k)}(d),\hfill & \text{otherwise}\hfill \end{array}$$

(2) Local searching algorithm

For global searching, we use an adaptive difference evolution algorithm. In addition, a local searching algorithm is utilized to obtain good solutions in a neighborhood. In this step, the intermediate is generated based on a local displacement of the start point in each dimension, and the vector with a superior objective function value is retained for the next level.

• Searching. For the $i$ -th target point $X_i^{(k)}=(X_i^{(k)}(1),\mathrm{\dots },X_i^{(k)}(D))$ , $i=1,\mathrm{\dots },N_E$ , the candidate point ${\stackrel{\dot{}}{X}}_i^{(k)}=({\stackrel{\dot{}}{X}}_i^{(k)}(1),\mathrm{\dots },{\stackrel{\dot{}}{X}}_i^{(k)}(D))$ can be calculated as follows:

(11) $${\stackrel{\dot{}}{X}}_i^{(k)}(d)=X_i^{(k)}(d)+\beta \cdot (X_B^{(k)}(d)-X_W^{(k)}(d))$$

where $\beta \sim U(0,1)$ is a reduction factor. $X_B^{(k)}(d)$ and $X_W^{(k)}(d)$ denote the decision vectors of the best and worst objective functions that correspond to the $d$ -th dimension in the $k$ -th level, respectively.

• Selection. Compare the relationship between vectors $f(X_i^{(k)})$ and $f({\stackrel{\dot{}}{X}}_i^{(k)})$ and select the element of ${𝒳}_{k+1}$ shown in Eq. ( 12 ):

(12) $$X_i^{(k+1)}(d)=\{\begin{array}{cc}{\stackrel{\dot{}}{X}}_i^{(k)}(d),\hfill & \text{if}f({\stackrel{\dot{}}{X}}_i^{(k)})⩽f(X_i^{(k)});\hfill \\ X_i^{(k)}(d),\hfill & \text{otherwise}\hfill \end{array}$$