Improved Biogeography-Based Optimization Based on Affinity Propagation

Abstract

To improve the search ability of biogeography-based optimization (BBO), this work proposed an improved biogeography-based optimization based on Affinity Propagation. We introduced the Memetic framework to the BBO algorithm, and used the simulated annealing algorithm as the local search strategy. MBBO enhanced the exploration with the Affinity Propagation strategy to improve the transfer operation of the BBO algorithm. In this work, the MBBO algorithm was applied to IEEE Congress on Evolutionary Computation (CEC) 2015 benchmarks optimization problems to conduct analytic comparison with the first three winners of the CEC 2015 competition. The results show that the MBBO algorithm enhances the exploration, exploitation, convergence speed and solution accuracy and can emerge as the best solution-providing algorithm among the competing algorithms.

1. Introduction

As an important branch in artificial intelligence, Evolutionary Algorithms (EAs) are derived from the simulation of complex biological systems in nature with the ability to cognize things of humans based on their interaction with nature. The biogeography-based optimization (BBO) algorithm is a new intelligent optimization algorithm that was proposed by Simon who was enlightened by biogeography theory [1] in 2008 based on the research of a mathematics model for biological species migration [2]. BBO has been widely studied, and good research achievements in theoretical analysis, improvement, and application have been achieved.

Some variations of BBO have recently been developed to improve the performance of basic BBO [3,4,5,6,7]. However, in these improved BBOs, the migration operation judges only the method of the immigration operation in terms of the immigration and emigration rates in different habitats without considering the interactional relationship among habitats. Therefore, there is still an insufficiency in these improved BBOs regarding the migration operator, which is good for exploitation but poor for exploration. Currently, we need changes that are more important than a simple hybrid.

This work proposes an improved BBO algorithm with Affinity Propagation (AP) [8] based on the Memetic framework [9,10,11,12] (MBBO). This algorithm improves the migration operation of the basic BBO algorithm by using the AP strategy to promote exploration. Further, the MBBO algorithm uses simulated annealing (SA) [13] as a local search strategy to promote exploitation and strengthen the ability to get out of the local optimum. This work also tests the MBBO algorithm and the three first winners of the CEC 2015 competition [14,15,16] in the CEC 2015 benchmarks and compares their operation results. After the modification of BBO, the Wilcoxon signed-rank test is used to demonstrate the differences between different implementations of the MBBO and the other three algorithms of the CEC 2015 competition, based on which it can be found that MBBO proposed in this work performs significantly better than do the three algorithms.

To summarize, our contributions are as follows:

• This work proposed an improved BBO algorithm using the AP strategy to modify the migration operation to promote exploration and
• proposed a MBBO algorithm using the Memetic framework and SA as the local search strategy to promote exploitation.

2. Improved BBO with Affinity Propagation based on Memetic Framework

2.1. BBO

In an ecosystem, the habitat suitability index (HSI) [17] can be used to describe the fitting degree of a habitat for species living in it [18]. HSI can be expressed with suitability index variables (SIV), which describe the characteristics of HSI, such as precipitation, humidity, and vegetation diversity in a habitat. A habitat with high HSI has more species living in it, whereas a habitat with low HSI has fewer species. In other words, HSI is directly proportional to the diversity of species. The largest possible number of species that a habitat can support is S_max; the immigration of species is λ, with a maximum of I; and the emigration rate is μ, with a maximum of E, with E = I, as shown in Figure 1.

When the number of species in this habitat is 0, the immigration rate at this time is obviously the maximum I. With the immigration of species, the number of species in the habitat increases; further, the immigration rate decreases when the emigration rate increases. When the number of species reaches the upper limit S_max, the habitat achieves the saturation state; thus, the immigration rate decreases to 0, and the emigration rate reaches the maximum E. In Figure 1, S₁ < S₂ and HSI at S₁ is smaller than that at S₂. Obviously, when the number of species in the habitat is S₁, the immigration rate λ(S₁) at S₁ is larger than λ(S₂) at S₂. Similarly, the emigration rate μ(S₁) at S₂ is smaller than μ(S₂) at S₂. For immigration among different habitats, the probability of immigration or emigration behavior occurring in one habitat is directly proportional to its immigration or emigration rate. Therefore, the immigration rate in one habitat can be used as the criterion for the immigration behavior, and the emigration rate can be further used to judge the emigration behavior from that habitat. In contrast, a habitat with high HSI can attract more species; however, this habitat may tend to be saturated with an increase in the number of species; thus, a larger amount of species may start to emigrate. For habitats with low HSI, more species may immigrate into it from other habitats upon the saturation of the number of species if few species live in habitats with low HSI. Such a behavior is called the migration behavior of species. In another situation, a habitat with low HSI has few species living in it, but no large species immigration occurs, which keeps the HSI low. Species in these habitats either go extinct or immigrate to other habitats. Such behavior is called mutation behavior. Using the descriptions of the immigration and emigration rates, consider the probability P_s that the habitat contains exactly S species. P_s changes from time t to time t + Δt according to Formula (1).

$$\begin{array}{c}{P}_s(t+\Delta t)=P_s\left(t\right)(1-{\lambda }_s\Delta t-{\mu }_s\Delta t)+P_{s-1}{\lambda }_{s-1}\Delta t+P_{s+1}{\mu }_{s+1}\Delta t\hfill \end{array}$$

(1)

where, λ_s and μ_s represent the immigration rate and emigration rate, respectively, when the number of species in the habitat is S. There are three conditions that satisfy this formula:

• At t time, there were S species in the habitat and no migration behavior in period Δt;
• At t time, there were S + 1 species in the habitat, with one species immigrating in period λ_s;
• At t time, there were S − 1 species in the habitat, with one species emigrating in period λ_s.

According to the linear relationship between immigration rate and emigration rate shown in Figure 1, the computational method of immigration rate and emigration rate when the number of species is k can be obtained as Formulas (2) and (3), respectively.

$$\begin{array}{c}{\lambda }_k=I(1-\frac{k}{n})\hfill \end{array}$$

(2)

$$\begin{array}{c}{\mu }_k=E\left(\frac{k}{n}\right)\hfill \end{array}$$

(3)

where n is S_max. Assume the special case E = I. In this case, λ_k + μ_k = E can be obtained. When Δt → 0, Formula (3) can be converted into Formula (4).

$$p_s=\left\{\begin{array}{ll}-({\lambda }_s+{\mu }_s)P_s+{\mu }_{s+1}{P}_{s+1},& S=0\\ -({\lambda }_s+{\mu }_s)P_s+{\lambda }_{s-1}{P}_{s-1}+{\mu }_{s+1}{P}_{s+1},& 1\le S\le S_{\text{max}}-1\\ -({\lambda }_s+{\mu }_s)P_s+{\lambda }_{s-1}{P}_{s-1},& S=S_{\text{max}}\end{array}\right.$$

(4)

If the probability of each species being counted in a habitat is low, mutation behavior may easily occur. In other words, the function of mutation probability is inversely proportional to the probability of species being counted in this habitat. Therefore, the corresponding mutation function can be obtained as Formula (5).

$$\begin{array}{c}{m}_s=m_{\text{max}}(1-\frac{P_s}{P_{\text{max}}})\hfill \end{array}$$

(5)

Assuming that a feasible solution of the optimization problem can be expressed with an integer vector, every integer component in the vector is defined as a SIV. If the objective function for the problem to be solved is known, the feasible solution with a higher adaptive value can be defined as the habitat with higher HSI. Assuming that the habitat is H ∈ SIV^m where H is the feasible solution of the optimization problem, m is the dimensionality of the solution vector and HSI is the adaptive value of the objective function, the basic procedure of the BBO algorithm can be obtained.

2.2. BBO with Affinity Propagation

Affinity propagation (AP) is a clustering strategy proposed by Frey and Dueck [8]. The basic idea of this strategy is to calculate the cluster center of all samples, which are treated as nodes in a network, via information transfer in all lines of the network. During the clustering, two types of information are transferred among nodes: attractiveness and availability. The clustering result is dependent on the similarity and information transfer among samples. This feature makes the strategy suitable as an auxiliary means for information transfer among habitats in the BBO algorithm. Among all habitats, a habitat with a high immigration rate can attract species from a habitat with a high emigration rate. Definitions related to AP applied to the BBO algorithm are as follows.

Definition 1. 

Migration matrix of habitat. Assuming that the habitat count is n, the similarity s(H_i, H_j) between any two habitats (the similarity can be either symmetric or asymmetric) can be calculated to represent the probability of habitat H_j attracting species emigrating from habitat H_i and immigrating into habitat H_j. The similarity matrix $s^{n\times n}$, which is composed of similarities between two habitats, is called the migration matrix of the habitat. s(H_i, H_j) is calculated as Formula (6).

$$\begin{array}{c}s\left(H_i,H_j\right)=-∥SI{V}_i^m-SI{V}_j^m∥\hfill \end{array}$$

(6)

Definition 2. 

Habitat immigration reference (HIR). Similarity s(H_k, H_k) shows whether habitat H_k is more likely to be immigrating which is denoted by HIR(k) (k = 1, 2,…, n). The value of HIR(k) can affect the ratio between the number of habitats to be immigrated into and that of habitats to be emigrated from. This ratio can determine whether the migration operation of the MBBO algorithm can effectively search the global optimum of the optimization problem.

The definition regarding HIR in [8] shows that the number of habitats to be immigrated into is directly proportional to HIR(k). According to Formula (1), HIR(k) is proportional to the immigration rate λ_k and inversely proportional to the emigration rate for any habitat H_k. In this work, let the value of s(H_k, H_k) be the ratio between the immigration rate λ_k and the emigration rate μ_k of habitat H_k, ${\lambda }_k$/${\mu }_k$. In Section 3.3, another method for obtaining the value is used for comparison to discuss how to select a more optimal value of HIR(k) (e.g., the mid-value of similarity S in [8], the average of similarity S, half of the mid-value of similarity S, and half of the average of similarity S).

Definition 3. 

Habitat attractiveness. Let habitat H_j belong to habitat set $H_i^n$. For candidate habitat H_j to be immigrated into, evidence r(H_i, H_j) is collected from habitat H_i (called the attractiveness of habitat H_j to habitat H_i) to describe the attractiveness of habitat H_j to attract species emigrating from habitat H_i and immigrating into habitat H_j. Such attractiveness can be called habitat attractiveness.

Definition 4. 

Habitat availability. For habitat H_j, evidence a(H_i, H_j) is collected for habitat H_i to be emigrated from (called the availability of habitat H_i to habitat H_j) to describe the suitability of species emigrating from habitat H_j and immigrating into habitat H_i. Such availability can be called habitat availability.

The stronger the evidence is (the larger the sum of r(H_i, H_j) and a(H_i, H_j)), the larger the probability is of species emigrating from habitat H_i and immigrating into habitat H_j. The methods for calculating and updating information matrix are shown as Formulas (7) and (8), respectively. The basic procedure of AP is shown in Figure 2.

$$\begin{array}{c}r(H_i,H_j)\leftarrow s(H_i,H_j)-\underset{j^{\prime }s.t.j^{\prime }\ne j}{max}\{a(H_i,H_{j^{\prime }})+s(H_i,H_{j^{\prime }})\}\hfill \end{array}$$

(7)

$$\begin{array}{c}\hfill \begin{array}{c}\hfill a(H_i,H_j)\leftarrow \left\{\begin{array}{cc}min\{0,r(H_j,H_j)+{\displaystyle \sum _{H_{i^{\prime }}s.t.H_{i^{\prime }}\notin \{H_i,H_j\}}}\text{max}\{0,r(H_{i^{\prime }},H_j)\}\},& i\ne j\\ {\displaystyle \sum _{H_{i^{\prime }}s.t.H_{i^{\prime }}\notin \{H_i,H_j\}}}\text{max}\{0,r(H_{i^{\prime }},H_j)\},& i=j\end{array}\right.\end{array}\end{array}$$

(8)

where r(H_j, H_j) and a(H_i, H_j) can be obtained using the migration immigration matrix of habitat s(H_i, H_j) and the habitat immigration reference HIR(k).

2.3. Local Search Strategies

To ensure population diversity under the precondition of fast convergence, this work uses SA as the local search (LS) strategy of the MBBO algorithm. SA uses the Metropolis criterion to accept non-prepreerence solutions and prevent them from falling into a local optimum. If the function is f(S), the current solution is f(S₁), the new solution is f(S₂), and the increment is df = f(S₂) − f(S₁), then the Metropolis criterion can be expressed as Formula (9).

$$\begin{array}{c}\hfill p=\left\{\begin{array}{cc}1,& df<0\\ exp(-\frac{df}{T}),& df\ge 0\end{array}\right.\end{array}$$

(9)

2.4. MBBO Algorithm

In this section, we provide some definitions as a first step towards formalizing the BBO algorithm and provide an outline of the algorithm.

Definition 5. 

Habitat migration strategy $\Omega (r,a):H^n\to H$ is a probabilistic operator used to control the migration operation. It can be judged that when the species emigrate from habitat H_i, they immigrate into habitat H_j with habitat attractiveness r and habitat availability a.

Definition 6. 

Habitat mutation strategy $M(\lambda ,\mu ):H\to H$ is a probabilistic operator used to control the mutation operation. Habitat mutation operation with randomly changing SIV_m is determined by the existing probability of species count P_s. Existing probability of species count P_s can be calculated using Formula (4). For the basic procedure of the habitat mutational strategy, refer to the mutational operation of the BBO algorithm.

Definition 7. 

Global search strategy of MBBO $G=\{m,n,\lambda ,\mu ,\Omega ,M\}$ is a 6-tuple that can iteratively optimize the initialized habitat.

Definition 8. 

Local search strategy of MBBO $L=\{t,l,P\}:H^n\to H$ is a 3-tuple set that can conduct local optimization of the evolution of the habitat in every generation. To provide this ability without the limit of a local optimum to the optimization of a habitat, the non-prepreerence solution can be accepted for a certain probability. t is a sufficiently large initial temperature, l is the Metropolis chain length that is, the performance time under temperature T, and P is the probability of acceptance, which can be calculated with using Formula (9).

Definition 9. 

MBBO algorithm $MBBO=\{\Phi ,G,L,T\}$ is a 4-tuple where Φ = ∅ → {Hⁿ,HSIⁿ} refers to initializing a set of habitats and calculating the function of the HSI value of a habitat. G is the global search strategy which can perform global optimization of the habitat. L is the local search strategy, which can perform local optimization of the habitat. $T=H^n\to \{true,false\}$ is a termination criterion.

The basic procedure of the MBBO algorithm is as Algorithm 1.

Algorithm 1: MBBO

Initialize the BBO parameters, including the habitat modification probability, mutation probability, maximum species count S, maximum migration rates E and I, maximum mutation rate mmax, the generation counter: g=0, the Metropolis chain length: L, the initial temperature T; Create a random initial population $H_i^{\left(g\right)}$, i = 1, 2, 3,…,N and g = 0, 1, 2,…,MAXGEN; Evaluate f($H_i^{\left(g\right)}$), i = 1, 2, 3,…,N; for g = 1 to MAXGEN do for i = 1 to N do Sort the population from best f($H_i^{\left(g\right)}$) to least f($H_i^{\left(g\right)}$); Map the HSI to the number of species; Calculate the immigration rate λi, the emigration rate μi, the Habitat attractiveness a and the Habitat availability r; for i = 1 to N do Modify the non-elite members of the population probabilistically with the migration operator; for i = 1 to N do Evaluate the new individuals in the population; Replace the habitats with their new versions; Replace the worst with the previous generation’s elites; while T ≠ 0 do for L = 1 to l do Create a random $H_i^{{\left(g\right)}^{\prime }}$; Calculate df = f($H_i^{{\left(g\right)}^{\prime }}$) − f($H_i^{\left(g\right)}$); if df < 0 then $H_i^{{\left(g\right)}^{\prime }}$ is accepted as the new current solution else $H_i^{{\left(g\right)}^{\prime }}$ is accepted as the new current solution as probability∝exp(−Δt/kT) T = T − 1; g = g + 1;

3. Experimental Settings and Results

3.1. CEC 2015 Benchmarks

In this work, to investigate the performance of the MBBO, we compared it with SPS-L-SHADE-EIG algorithm [14], DEsPA algorithm [15] and MVMO algorithm [16] using the CEC 2015 benchmarks. For convenient description, these functions [19] are denoted as F1-F15, as shown in

Table 1. Summary of the Congress on Evolutionary Computation (CEC)’15 Benchmark functions used in our experimental study.

Test Functions		${\mathit{F}}_{\mathit{i}}^{\mathbf{*}}={\mathit{F}}_{\mathit{i}}\mathbf{\left(}{\mathit{x}}^{\mathbf{*}}\mathbf{\right)}$
Unimodal Functions
F1	Rotated High Conditioned Elliptic Function	100
F2	Rotated Cigar Function	200
Simple Multimodal Functions
F3	Shifted and Rotated Ackley’s Function	300
F4	Shifted and Rotated Rastrigin’s Function	400
F5	Shifted and Rotated Schwefel’s Function	500
Hybrid Functions
F6	Hybrid Function 1 (N = 3)	600
F7	Hybrid Function 2 (N = 4)	700
F8	Hybrid Function 3(N = 5)	800
Composition Functions
F9	Composition Function 1 (N = 3)	900
F10	Composition Function 2 (N = 3)	1000
F11	Composition Function 3 (N = 5)	1100
F12	Composition Function 4 (N = 5)	1200
F13	Composition Function 5 (N = 5)	1300
F14	Composition Function 6 (N = 7)	1400
F15	Composition Function 7 (N = 10)	1500
Search Range: ${[-100,100]}^D$

. The SPS-L-SHADE-EIG algorithm combines the adaptive differential evolution [20,21] with linear population size reduction(L-SHADE) [22] with the eigenvector-based (EIG) [23] crossover and successful-parent-selecting (SPS) frameworks [24]. The DEsPA algorithm is a new Differential Evolution algorithm with a success-based parameter adaptation with resizing population space [25]. The MVMO algorithm is Mean-variance mapping optimization that uses a special mapping function for mutation operation. These three algorithms are state-of-the-art evolutionary mechanisms.

3.2. CEC 2015 Benchmarks Results and Analysis

3.2.1. Experiment Parameter Setting

The three aforementioned optimization techniques are used to optimize the 15 CEC2015 benchmark functions given in Table 1. For each test function, each algorithm is run 100 times. As suggested in [19], $10,000\times D$ function evaluations were used for the test functions with 10 and 50 dimensions. The search range was set to ${[-100,100]}^D$ for each dimension.

The parameters of MBBO should be set according to [2]. Let the maximum number of species in a habitat N = 50; habitat modification probability P_mod = 1; mutation probability m = 0; elitism parameter K = 2; and maximum immigration and emigration rate for each island I = E = 1.

3.2.2. Experiment Result and Analysis

The experiment results are shown in

Table 2. Comparison of MBBO, SPS-L-SHADE-EIG, DEsPA and MVMO. Statistical results of the 10-D and 50-D benchmark functions, averaged over 100 independent runs.

	MBBO					SPS-L-SHADE-EIG					DEsPA					MVMO
	Best	Median	Mean	Distance		Best	Median	Mean	Distance		Best	Median	Mean	Distance		Best	Median	Mean	Distance
10-D
F1	0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00
F2	0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00
F3	1.10E+01	1.50E+01	1.70E+01	1.10E+01		2.00E+01	2.20E+01	2.60E+01	2.00E+01		1.91E+01	2.19E+01	1.90E+01	1.91E+01		2.01E+01	2.33E+01	1.40E+01	2.01E+01
F4	1.34E-01	6.25E-01	1.23E+00	1.34E-01		7.83E-01	8.72E-01	1.95E+00	7.83E-01		8.93E-01	9.95E-01	1.17E+00	8.93E-01		9.83E-01	1.23E+00	9.76E-01	9.83E-01
F5	9.93E+00	1.34E+01	2.14E+01	9.93E+00		1.24E+01	1.64E+01	2.35E+01	1.24E+01		1.43E+01	1.86E+01	2.56E+01	1.43E+01		2.19E+01	2.35E+01	2.98E+01	2.19E+01
F6	0.00E+00	0.00E+00	1.01E-01	0.00E+00		0.00E+00	0.00E+00	1.23E-01	0.00E+00		0.00E+00	0.00E+00	8.79E-01	0.00E+00		0.00E+00	0.00E+00	7.98E-01	0.00E+00
F7	6.70E-03	1.02E-02	2.23E-02	6.70E-03		9.76E-03	1.94E-02	2.78E-02	9.76E-03		1.23E-02	2.31E-02	3.21E-02	1.23E-02		2.35E-02	3.12E-02	5.37E-02	2.35E-02
F8	7.63E-05	1.26E-04	7.32E-04	7.63E-05		1.01E-04	1.37E-04	8.81E-04	1.01E-04		2.13E-04	4.34E-04	9.86E-04	2.13E-04		3.98E-04	6.98E-04	9.98E-04	3.98E-04
F9	2.39E+01	8.69E+01	9.51E+01	2.39E+01		6.92E+01	1.00E+02	1.50E+02	6.92E+01		9.21E+01	1.02E+02	1.02E+02	9.21E+01		1.02E+02	1.97E+02	1.28E+02	1.02E+02
F10	2.03E+02	2.21E+02	2.04E+02	2.03E+02		1.98E+02	3.68E+02	3.53E+02	1.98E+02		2.58E+02	2.76E+02	2.37E+02	2.58E+02		2.98E+02	3.97E+02	3.15E+02	2.98E+02
F11	3.28E-02	7.52E-02	4.37E-01	3.28E-02		7.82E-02	9.79E-02	9.27E-01	7.82E-02		8.27E-02	9.86E-01	7.78E-01	8.27E-02		5.24E-02	1.00E-01	3.33E-01	5.24E-02
F12	2.39E+01	8.96E+01	1.00E+02	2.39E+01		9.82E+01	1.32E+02	1.06E+02	9.82E+01		1.92E+02	2.94E+02	2.36E+02	1.92E+02		2.01E+02	2.96E+02	2.75E+02	2.01E+02
F13	3.30E-03	1.23E-02	2.12E-02	3.30E-03		3.46E-02	8.26E-02	2.31E-02	3.46E-02		8.72E-02	9.26E-02	7.89E-02	8.72E-02		2.05E-02	2.83E-02	7.23E-02	2.05E-02
F14	1.03E+02	1.98E+02	3.94E+02	1.03E+02		1.95E+02	2.35E+02	5.21E+02	1.95E+02		4.32E+02	8.92E+02	7.26E+02	4.32E+02		3.95E+02	4.77E+02	5.67E+02	3.95E+02
F15	3.61E+01	8.70E+01	9.50E+01	3.61E+01		9.32E+01	1.02E+02	1.67E+02	9.32E+01		1.01E+02	1.36E+02	2.34E+02	1.01E+02		2.51E+02	3.55E+02	2.45E+02	2.51E+02
50-D
F1	0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00
F2	0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00		0.00E+00	0.00E+00	0.00E+00	0.00E+00
F3	1.09E+01	1.83E+01	1.93E+01	1.09E+01		2.91E+01	3.22E+01	2.32E+01	2.91E+01		2.81E+01	3.11E+01	2.82E+01	2.81E+01		4.15E+01	6.51E+01	2.82E+01	4.15E+01
F4	9.23E-01	1.23E+00	1.98E+00	9.23E-01		1.02E+00	3.52E+00	2.55E+00	1.02E+00		1.92E+00	2.46E+00	3.26E+00	1.92E+00		2.24E+00	3.86E+00	4.62E+00	2.24E+00
F5	1.70E+03	1.92E+03	1.87E+03	1.70E+03		1.53E+03	2.98E+03	1.75E+03	1.53E+03		2.42E+03	2.99E+03	2.68E+03	2.42E+03		2.73E+03	3.82E+03	3.00E+03	2.73E+03
F6	1.35E+02	1.98E+02	1.75E+02	1.35E+02		1.87E+02	2.11E+02	2.39E+02	1.87E+02		2.06E+02	2.67E+02	2.49E+02	2.06E+02		2.94E+02	3.22E+02	3.15E+02	2.94E+02
F7	2.31E+01	3.92E+01	2.56E+01	2.31E+01		3.52E+01	4.05E+01	2.74E+01	3.52E+01		3.94E+01	4.96E+01	3.16E+01	3.94E+01		4.52E+01	5.81E+01	4.87E+01	4.52E+01
F8	9.23E+00	2.16E+01	4.58E+01	9.23E+00		1.81E+01	2.79E+01	5.57E+01	1.81E+01		2.02E+01	2.62E+01	6.58E+01	2.02E+01		3.31E+01	6.32E+01	5.18E+01	3.31E+01
F9	7.20E+01	1.06E+02	1.02E+02	7.20E+01		1.36E+02	2.56E+02	2.37E+02	1.36E+02		1.84E+02	3.35E+02	3.02E+00	1.84E+02		4.89E+02	6.51E+02	5.56E+02	4.89E+02
F10	3.29E+02	7.95E+02	6.87E+02	3.29E+02		7.23E+02	8.09E+02	8.35E+02	7.23E+02		7.84E+02	9.86E+02	8.76E+02	7.84E+02		5.91E+02	6.98E+02	7.92E+02	5.91E+02
F11	1.36E+02	2.78E+02	2.69E+02	1.36E+02		2.47E+02	3.00E+02	3.00E+02	2.47E+02		2.84E+02	3.76E+02	3.56E+02	2.84E+02		3.34E+02	5.87E+02	4.98E+02	3.34E+02
F12	4.50E+01	1.00E+02	1.10E+02	4.50E+01		9.32E+01	1.04E+02	1.23E+02	9.32E+01		1.07E+02	1.98E+02	1.79E+02	1.07E+02		2.04E+02	3.01E+02	2.96E+02	2.04E+02
F13	1.32E-02	6.54E-02	5.77E-02	1.32E-02		3.73E-02	7.57E-02	7.62E-02	3.73E-02		6.25E-02	8.27E-02	7.26E-02	6.25E-02		6.13E-02	7.60E-02	6.67E-02	6.13E-02
F14	3.47E+04	5.98E+04	4.79E+04	3.47E+04		5.95E+04	6.83E+04	6.35E+04	5.95E+04		5.74E+04	7.89E+04	7.12E+04	5.74E+04		6.95E+04	8.63E+04	8.01E+04	6.95E+04
F15	3.72E+01	9.60E+01	1.01E+02	3.72E+01		1.03E+02	1.56E+02	1.35E+02	1.03E+02		1.62E+02	2.32E+02	2.17E+02	1.62E+02		3.74E+02	6.19E+02	5.97E+02	3.74E+02

. For unimodal functions F1 and F2, it can be found that the MBBO algorithm and the other three algorithms are able to obtain the optimal solution. Benchmarks F3-F5 are simple and multimodal; the MBBO algorithm uses the Affinity Propagation which can relatively accurately judge the global optimal solution according to the mutual affinity relationship between different solutions.

Benchmarks F6–F8 are hybrid functions, whereas the remaining benchmarks are composition functions. For these functions, the MBBO algorithm is better than the other three algorithms regarding the optimization result when the peak of function F9 shows undulation and jumpiness. Therefore, the Affinity Propagation of the MBBO algorithm can find the optimal solution of a function by propagating migration information among solutions. The MBBO algorithm uses SA as a local search strategy which can make the algorithm accept non-prepreerence under a certain probability and have a stronger ability to skip the local optimum. Therefore, MBBO can accurately obtain the optimal solution. MBBO uses the Memetic framework to optimize the complex function in global search and local search. With the strong global optimization ability of Affinity Propagation and the strong ability of SA to skip the local optimum, the MBBO algorithm can effectively solve complex functions such as F10-F15.

To performance the MBBO algorithm and the other three algorithms for limited budget, we added the experiment over 50 number of evaluations to compare the performance evolution among these algorithms. For 10-D function F3, F4, F7, F8, F14 and F15, the cumulative distribution function (CDF) plots can be found in Figure 3 that compared with the three other algorithms over 50 function evaluations. Figure 3a–f are the optimization processes of MBBO, SPS-L-SHADE-EIG, DEsPA and MVMO algorithms in F3, F4, F7, F8, F14 and F15 benchmark functions. For hybrid function F7 and F8, it can be found that MBBO algorithm is better than the other three algorithms in Figure 3c,d. For composition Function F14 and F15, it can be found in Figure 3e,f that compared with other three algorithms, MBBO algorithm has larger difference, while the result of this function solved with SPS-L-SGADE-EIG algorithm is more stable.

3.2.3. Statistical Analysis

A Wilcoxon signed-rank test has been conducted to determine whether the differences among the median results of the MBBO algorithm, SPS-L-SHADE-EIG algorithm, DEsPA algorithm and MVMO algorithm given in Table 2 are statistically significant.

Table 3. The statistical comparison of the MBBO algorithm with the other three algorithms, using the Wilcoxon signed-rank test with freedom at a 0.05 level of significance and 95 % confidence level.

	MBBO and SPS-L-SHADE-EIG			MBBO and DEsPA			MBBO and MVMO
	z	p-Value (2-Tailed)		z	p-Value (2-Tailed)		z	p-Value (2-Tailed)
F1	−0.367	0.713		−1.547	0.122		−1.249	0.212
F2	−0.920	0.357		−0.178	0.859		−1.823	0.068
F3	−2.077	0.038		−2.505	0.012		−2.716	0.007
F4	−1.134	0.254		−1.932	0.061		−1.899	0.058
F5	−2.139	0.032		−2.660	0.008		−2.634	0.008
F6	−3.696	0.000		−3.705	0.000		−3.702	0.000
F7	−2.996	0.003		−2.820	0.004		−2.492	0.013
F8	−2.323	0.025		−2.432	0.014		−2.814	0.005
F9	−2.928	0.003		−2.413	0.015		−3.203	0.001
F10	−3.222	0.001		−2.995	0.003		−3.220	0.001
F11	−2.746	0.006		−2.395	0.017		−2.466	0.014
F12	−2.640	0.008		−3.324	0.001		−5.244	0.000
F13	−5.376	0.000		−4.278	0.000		−4.437	0.000
F14	−2.934	0.003		−2.666	0.008		−2.936	0.003
F15	−1.090	0.091		−2.936	0.003		−6.232	0.000

shows the statistical comparison of the MBBO algorithm with the other three algorithms (SPS-L-SHADE-EIG, DEsPA and MVMO) for the 10-D benchmark functions using the Wilcoxon signed-rank test, with freedom at a 0.05 level of significance and 95 % confidence level.

The Wilcoxon signed-rank test results can be summarized as follows:

• MBBO algorithm and SPS-L-SHADE-EIG algorithm: A Wilcoxon signed-rank test showed that the MBBO algorithm did not elicit a statistically significant change in $F1(z=-0.367,p=0.713)$, F2 (z = −0.920, $p=0.357)$, $F4(z=-1.134,p=0.254)$ and $F15(z=-1.090,p=0.091)$. In these four functions, the median change from MBBO algorithm to SPS-L-SHADE-EIG algorithm is not significantly different from zero. This suggests that with $95\%$ confidence, the difference between the algorithms is statistically significant for the remaining 11 functions.
• MBBO algorithm and DEsPA algorithm: A Wilcoxon signed-rank test showed that the MBBO algorithm did not elicit a statistically significant change in $F1(z=-1.547,p=0.122)$, F2 (z = −0.178, $p=0.859)$ and $F4(z=-1.932,p=0.061)$ with a 95 % confidence level. Therefore, the test has not provided statistically significant evidence that the two algorithms are different for these benchmark functions. For the other 12 cases, the median change from MBBO algorithm to DEsPA algorithm is very different from zero.
• MBBO algorithm and MVMO algorithm: A Wilcoxon signed-rank test showed that the MBBO algorithm did not elicit a statistically significant change in $F1(z=-1.249,p=0.212)$, F2 (z = −1.823, $p=0.068)$ and $F4(z=-1.823,p=0.068)$. In these three functions, the median change from MBBO algorithm to SPS-L-SHADE-EIG algorithm is not significantly different from zero; for the other 12 cases, the two algorithms are different with a 95 % confidence level.

It can be concluded that, the compared algorithms are significantly different in most cases, with 95% confidence. Therefore, it is evident that MBBO can significantly outperform the other three algorithms and can emerge as the best solution-providing algorithm among the competing SPS-L-SHADE-EIG, DEsPA and MVMO algorithms.

3.3. Effect of the HIR on the Performance of MBBO

3.3.1. Experiment Setting

The HIR value in Affinity Propagation of the MBBO algorithm is the ratio between the habitat immigration rate and habitat emigration rate. To the compare efficiency with different values of HIR, a comparison experiment is set. Let the HIR value be the ratio between the habitat immigration and emigration rates, the mid-value in habitat similarity matrix S, half of the mid-value of habitat similarity matrix S, the average of habitat similarity matrix S, and half of the average of habitat similarity matrix S. Then, compare the efficiency of algorithms with the averages and standard deviations in the 25 independent tests using the CEC 2015 benchmarks. The parameters of the MBBO algorithm for five HIR sampling methods are set according to Subsection 3.2.1. Let the maximum species count in habitat N = 50; habitat modification probability P_mod = 1; mutation probability m = 0; elitism parameter K = 2; and maximum immigration and migration rates for each island I = E = 1.

3.3.2. Experimental Results and Analysis

The experimental results are shown in

Table 4. Comparison of efficiency with different values of habitat immigration reference (HIR). Let the HIR value be the ratio between habitat immigration rate and emigration rate, the mid-value in habitat similarity matrix S, half of the mid-value of habitat similarity matrix S, the average of habitat similarity matrix S, and half of the average of habitat similarity matrix S. Then, compare the efficiency of algorithms with the averages and standard deviations in 25 independent tests using the CEC 2015 Benchmarks

	MBBO ($\mathit{HIR}\mathbf{\left(}\mathit{k}\mathbf{\right)}\mathbf{=}{\mathit{\lambda }}_{\mathit{k}}\mathbf{/}{\mathit{\mu }}_{\mathit{k}}$)	MBBO $\mathbf{\left(}\mathit{HIR}\mathbf{\right(}\mathit{k}\mathbf{)}\mathbf{=}\mathit{M}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}\mathbf{)}$	MBBO $\mathbf{\left(}\mathit{HIR}\mathbf{\right(}\mathit{k}\mathbf{)}\mathbf{=}\mathit{M}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}\mathbf{/}\mathbf{2}\mathbf{)}$	MBBO $\mathbf{\left(}\mathit{HIR}\mathbf{\right(}\mathit{k}\mathbf{)}\mathbf{=}\mathit{A}\mathit{v}\mathit{e}\mathit{r}\mathit{a}\mathit{g}\mathit{e}\mathbf{)}$	MBBO $\mathbf{\left(}\mathit{HIR}\mathbf{\right(}\mathit{k}\mathbf{)}\mathbf{=}\mathit{A}\mathit{v}\mathit{e}\mathit{r}\mathit{a}\mathit{g}\mathit{e}\mathbf{/}\mathbf{2}\mathbf{)}$
	Mean	Std.	Mean	Std.	Mean	Std.	Mean	Std.	Mean	Std.
F1	1.78E+00	6.27E-01	2.30E+00	9.89E-01	2.13E+00	8.51E-01	2.84E+00	7.58E-01	2.59E+00	1.26E+00
F2	4.68E+03	1.62E+03	4.76E+03	1.39E+03	4.93E+03	1.33E+03	5.19E+03	1.34E+03	4.82E+03	1.92E+03
F3	4.11E+01	8.11E+00	4.84E+01	1.04E+01	4.45E+01	9.63E+00	4.13E+01	1.02E+01	4.41E+01	1.15E+01
F4	5.91E+00	1.56E+00	7.56E+00	2.31E+00	6.37E+00	1.14E+00	7.27E+00	1.60E+00	7.03E+00	1.69E+00
F5	9.97E+01	2.91E+01	1.14E+02	3.65E+01	1.13E+02	4.02E+01	1.14E+02	2.50E+01	1.18E+02	3.82E+01
F6	6.04E+02	2.63E+02	8.86E+02	3.03E+02	7.77E+02	2.65E+02	1.02E+03	4.75E+02	1.06E+03	4.16E+02
F7	4.65E-02	3.60E-02	1.07E-01	1.14E-01	7.23E-02	6.15E-02	1.13E-01	8.00E-02	9.99E-02	1.11E-01
F8	7.31E+02	2.09E+02	8.49E+02	2.21E+02	8.74E+02	2.33E+02	9.65E+02	2.34E+02	8.67E+02	2.79E+02
F9	3.02E+01	6.21E+00	3.45E+01	5.78E+00	3.16E+01	5.81E+00	3.46E+01	7.08E+00	3.45E+01	6.64E+00
F10	7.26E+00	1.09E+00	8.47E+00	9.48E-01	7.66E+00	9.36E-01	8.22E+00	1.34E+00	8.33E+00	1.01E+00
F11	7.22E+00	2.41E+00	9.63E+00	2.82E+00	7.70E+00	2.93E+00	1.04E+01	3.11E+00	9.70E+00	3.79E+00
F12	6.18E+04	2.72E+04	6.92E+04	2.41E+04	6.39E+04	1.97E+04	7.28E+04	3.49E+04	6.42E+04	1.91E+04
F13	2.13E+00	4.68E-01	3.52E+00	3.14E-01	3.40E+00	4.55E-01	6.23E+02	5.39E+02	3.23E+03	2.41E+03
F14	6.40E+01	1.47E+01	2.77E+02	1.03E+02	1.71E+02	2.01E+02	4.32E+02	2.43E+01	5.62E+02	3.31E+02
F15	1.02E+02	7.31E+00	1.07E+02	9.03E+00	1.23E+02	1.46E+01	5.11E+03	3.21E+03	6.42E+04	1.91E+04

According to these results, it can be found that the effect of MBBO algorithm (HIR(k) = ${\lambda }_k$/${\mu }_k$) is better than that of the other four situations for the solutions of the CEC 2015 benchmarks. The setting of the HIR value as the ratio between the habitat immigration and emigration rates can use the information regarding the number of species in a habitat. The propagation of information regarding attractiveness and availability among habitats can more accurately guide the species migration behavior among habitats.

3.4. Experimental Results Analysis

The MBBO algorithm uses Affinity Propagation which can relatively accurately judge the global optimal solution according to the mutual affinity relationship between different solutions. The MBBO algorithm uses SA as the local search strategy which can make the algorithm accept non-prepreerence under a certain probability and have a stronger ability to skip the local optimum. Therefore, MBBO can accurately obtain the optimal solution. MBBO uses the Memetic framework to optimize a complex function in global search and local search. With the strong global optimization ability of Affinity Propagation and the strong ability of SA to skip the local optimum, the MBBO algorithm can effectively solve complex functions.

4. Conclusions

This work proposed a MBBO algorithm that uses the AP strategy to modify the migration operation of the BBO algorithm and based on the Memetic frame, with SA as the local search strategy. According to an analysis of the test results of MBBO regarding the CEC 2015 benchmarks, this algorithm can better solve the limit value of function optimization. Compared with the SPS-L-SHADE-EIG, DEsPA and MVMO algorithms, it can be found that the MBBO algorithm has significantly better performance than do the other three algorithms. However, the study of the BBO algorithm is still in its infancy stage compared with other EAs (such as Genetic Algorithms [26,27] and Particle Swarm Optimizer [28,29]). In future work, other algorithm framework (such as the cultural algorithm framework [30]) models should be used to modify the performance of the BBO algorithm.