1 Introduction

In artificial intelligence, optimization is an important issue which exists in a wide range of practical applications. Even in our daily life, optimization exists everywhere, such as optimizing paths in transportation, maximizing profit in investments and minimizing the payments in journey. In many real applications, resources, including money, time and people, are not much enough. Therefore, it is crucial to do optimization in order to satisfy users’ requirements. To date, a widely used formulation to summarize an optimization problem can be given as (1).

$$\begin{aligned} \mathrm{Minimize} \,\,f_i(x),\quad (i=1,2,\ldots, M) \end{aligned}$$
(1)

subject to:

$$\begin{aligned} h_j(x)&= {} 0, \quad (j=1,2,\ldots, J) \end{aligned}$$
(2)
$$\begin{aligned} g_k(x)\le & {} 0, \quad (k=1,2,\ldots ,K) \end{aligned}$$
(3)

where \(f_i,h_j\) and \(g_k\) are usually nonlinear functions, or integrals, or differential equations. In (1), the vector \(x=(x_1,x_2,\ldots ,x_n)\) can include continuous, discrete or mixed variables in searching domain. \(f_i\) is the ith objective function. If the number of objective functions is two or three, the optimization problem is multi-objective optimization, while it is called many-objective optimization if the number of \(f_i\) is more than three.

To solve optimization problems, meta-heuristic algorithms inspired by nature phenomena play an important role and are well implemented in science, engineering, medicine, finance and so forth. Other than several classic algorithms such as genetic algorithm (GA) [1, 2], particle swarm optimization (PSO) [3, 4], ant colony optimization (ACO) [5], novel approaches are explored and exploited in recent years. Inspired from the science of biogeography, Simon proposed biogeography-based optimization (BBO) in 2008 [6], which mimics the species dynamic distribution caused by migration and mutation. As a novel meta-heuristic approach, this algorithm has drawn worldwide attentions due to its outstanding performance in optimization problems and has been well implemented in various kinds of applications.

The science of biogeography is a branch of geography that investigates the species distribution and its dynamic properties from past to present spatially and temporally. Since the research of biogeography is related to the physical environment and also includes biomes, taxonomy and the interactive influence between environment and species distribution, biogeography is also deemed to be a subfield of physical geography. The related research of biogeography begins by Wallance [7] and Darwin [8] in the middle and later periods of nineteenth century. In 1967, MacArthur and Wilson [9], who focus on the species distribution among islands, publish the book named “The Theory of Island Biogeography”, where is to build mathematical models of biogeography to inaugurate a new view for biogeography scientists to understand and describe spatial patterns of species distribution. After that, island biography gains popularity as the researches of MacArthur and Wilson are easy to explain species distribution on islands. Furthermore, the researches of habitat fragmentation give rise to the development of landscape ecology and conservation biology.

With the development of computational intelligence, scientists and engineers would like to solve problems by learning from nature. Considering that the science of biogeography is becoming a mature discipline, it is possible to propose new computational methods according to the mechanism in biogeography. The work has been done in 2008 that biogeography-based optimization (BBO) is proposed. Due to BBO’s outstanding performance in handling optimization problems, this algorithm has already been implemented in both numerical simulations and practical applications. In BBO, the algorithm abstracts the mechanism of species migration and mutation, and employs related mathematical models to depict the species dynamic distribution. In BBO, “island” is considered as a habitat which is isolated from other habitats, rather than an area surround by water [10]. In nature, for a good island, there are many kinds of species living on it. For the best islands, the capability for species living is almost saturated. Hence, the good island has a low immigration rate and a high emigration rate. However, for a poor island, considering that the number of the species living on it is small, the island has a high immigration rate and a low emigration rate. In BBO, a candidate solution is considered as an island. The features in the solution are considered as species. Species migration is analogous to candidate solutions’ interaction. Hence, for a good solution, it has a high probability to affect other solutions and has a low probability to be affected. Meanwhile, for a poor solution, it has a low probability to affect other solutions and has a high probability to be affected. It is noted that the probability to affect other solutions is analogous to immigration rate, while the probability to be affected by other solutions is analogous to emigration rate. In BBO, migration operator and mutation operator are very important to affect algorithm’s performance. For each generation, every candidate solution has chances to communicate with all other candidates. Therefore, the candidate solutions in BBO have more flexible ways to communicate with each other by comparing some other classic meta-heuristic method, say genetic algorithm (GA). Considering BBO is very active in current researches and gains a big success in optimization [6, 11–15], we investigate this algorithm and provide this survey to help readers understand this algorithm and help this algorithm develop further.

The rest of this paper is organized as follows. In Sect. 2, we introduce the standard BBO by employing a linear migration model. In this section, two basic operators, say migration operator and mutation operator, respectively, are illustrated. Section 3 presents theoretical analysis on BBO including Markov model analysis, dynamic model and the effects of migration and mutation to BBO’s performance. In Sect. 3, we also summarize variants of BBO and hybrid algorithms. The implementations and practical applications of BBO are summarized in Sect. 4. We conclude this paper and present some open unsolved issues of BBO in Sect. 5.

2 The method of biogeography-based optimization

2.1 BBO’s mechanism and its fundamental operators

By abstracting the mechanism of species migration among different islands, Biogeography-based optimization mimics the species distribution in natural biogeography. It is noted that the island in BBO is not a piece of subcontinental land that is surrounded by water, but describes an area which is geographically isolated from other areas. In the science of biogeography, to judge the quality of geographical areas, we need to consider many elements including climate, temperature and humidity. All the elements are called suitability index variables (SIVs), and the quality of the island is called habitat suitability index (HSI). For the areas which are suitable for species living, it has a large value of HSI, while for the areas which are not suitable for species living, it only has a low HSI. Hence, the capability of good areas are almost saturated so that it is difficult to immigrate to the areas, but easy to emigrate. Oppositely, for poor areas, it is easy to immigrate, but difficult to emigrate. In BBO, a poor solution is analogous to an area that has a low HSI, while a good solution presents an area that has a high HSI. According to the mechanism of BBO, good solutions have high probabilities to share their SIVs with other solutions and have a low probability to accept SIVs from other solutions. Meanwhile, poor solutions have low probabilities to share their SIVs with other solutions and have high probabilities to accept SIVs from other solutions. This is very similar to species migrating among good and poor areas. To explain the relationship between species distribution and migration rates, we give Fig. 1, where I is the maximum possible immigration rate and E presents the maximum possible emigration rate, \(K_\mathrm{{max}}\) is the maximum number that an island can afford and \(K_0\) is the number of species that makes immigration rate equal to emigration rate. According to Fig. 1, it is obvious that immigration rate increases as the quality of solution decreases, while the emigration rate decreases when the quantity of species decreases. In nature, the curves of natural models may be more complicated. However, this linear model presents a descriptive way for us to know the process of species migration. Novel migration models can be designed if needed, and we will introduce some in next sections.

Fig. 1
figure 1

Linear migration model in biogeography-based optimization in a single Island

Full size image

In standard BBO, there is a default assignment for the species number in each island. For convenience, the algorithm assumes that for the ith island, it has i species living there. According to the design of BBO, a good island has a large number of species, while a poor island has a small number of species. In this way, the ranking of islands can be decided by the number of species. According to Fig. 1, a linear migration model is presented in (4).

$$\begin{aligned} \mu _i&= {} \frac{Ei}{N} \nonumber \\ \lambda _i&= {} I \left( 1-\frac{i}{N} \right) \end{aligned}$$
(4)

where \(\lambda _i\) and \(\mu _i\) are the immigration rate and emigration rate for ith island, respectively, I and E are the maximum migration rate and maximum emigration rate, respectively, and N is the population size.

The pseudo-codes of migration operator are shown in Algorithm 1, where \(H_i\) and \(H_j\) denote the ith island and the jth island, respectively, N is the maximum account of species and D is the dimension of a solution.

figure a

Like most other meta-heuristics, BBO has mutation operator which helps algorithms break away local optimum and explore the searching space. In standard version of most other meta-heuristic algorithms, the mutation rate is a fixed value. However, in standard BBO, the mutation rate dynamically changes during the optimization process. The design of BBO’s mutation rate takes account of the probability that migration occurs. To understand the dynamical mutation rate, we introduce a notation \(P_S\) which is the probability that an island contains exactly S species.

In Island S, the immigration rate is \(\lambda _S\) and emigration rate is \(\mu _S\). By assuming \(\varDelta t\) is small enough so that during \(\varDelta t\) there is no more than one migration (immigration or emigration) occurs. Hence, \(P_S\) changes from time t to \(t+\varDelta t\) as follows,

$$\begin{aligned} P_S(t+\varDelta t)&= {} P_S(t)(1-\lambda _S \varDelta t - \mu _S \varDelta t) + P_{S-1}(t)\lambda _{S-1}\varDelta t + P_{S+1}(t)\mu _{S+1}\varDelta t \end{aligned}$$
(5)

In (5), it contains three cases [6]: (1) for the island contains S species at time t, no immigration or emigration occurs during \(\varDelta t\); (2) for the island that contains \(K-1\) species at time t, one species immigrates during \(\varDelta t\); and (3) For the island that contains \(K+1\) species at time t, one species emigrates during \(\varDelta t\). For simplicity, we define the largest possible species account that an island can support is N (as mentioned above, the index of island which can support N species is also N), and obtain

$$\begin{aligned} \dot{P}=AP \end{aligned}$$
(6)

where

$$\begin{aligned} P=[P_0,\ldots ,P_N]^T \end{aligned}$$
(7)

and

$$\begin{aligned} A=\left( \begin{array}{ccccc} -(\lambda _0 + \mu _0) &{}\mu _1 &{}0 &{}\cdots &{}0\\ \lambda _0 &{}-(\lambda _1 + \mu _1) &{}\mu _2 &{}\ddots &{}\vdots \\ \vdots &{}\ddots &{}\ddots &{}\ddots &{}\vdots \\ \vdots &{}\ddots &{}\lambda _{N-2} &{}-(\lambda _{N-1}+\mu _{N-1}) &{}\mu _N\\ 0 &{}\cdots &{}0 &{}\lambda _{N-1} &{}-(\lambda _{N}+\mu _{N}) \end{array} \right) \end{aligned}$$
(8)

In BBO [6], the mutation rate of Island S is calculated by (9).

$$\begin{aligned} m_S = m_\mathrm{{max}} \left( \frac{P_\mathrm{{max}}-P_{S}}{P_\mathrm{{max}}} \right) \end{aligned}$$
(9)

where \(m_\mathrm{{max}}\) is defined by users in advance and \(P_\mathrm{{max}}\) and \(P_{S}\) can be obtained by (5). Since (5) involves migration rates, the mutation rate in (9) is not independent and affected by migration rates, which is a significant difference between BBO and other standard meta-heuristics. The pseudo-codes of mutation operator are shown in Algorithm 2, where N is the maximum value of island index and D is the dimension of a solution.

figure b

2.2 Comparative study on BBO and other meta-heuristics

According to current researches, BBO has drawn a lot of attentions due to its outstanding performances. In this subsection, we present a comparison study to investigate the differences of BBO and other meta-heuristics. First, we compare BBO with several other algorithms in the view of design and mechanism. Second, we employ widely used benchmarks to compare algorithms’ performances.

By comparing BBO with several other classical meta-heuristics, BBO has its own characteristics in design. As a population-based optimization algorithm, BBO improves its current population in each iteration, rather than reproduce a new population which is termed “children.” Hence, it is different from genetic algorithm (GA) and evolutionary strategy (ES). In ACO (ant colony optimization), the algorithm generates a new set of solutions according to pheromone density in paths, while BBO maintains solutions, but only changes some features, from one iteration to the next. The principle to maintain solutions is based on migration models. For the comparison between BBO and PSO (particle swarm optimization), the two algorithms share information among solutions in a direct and indirect way, respectively. The candidate solutions in BBO communicate with each other in a direct way; namely, it can directly share their attributes (SIVs) with other solutions. However, PSO’s solutions communicate with each other by an additional variable, namely velocity, which is not a direct interaction. For DE (differential evolution), although the solutions interact with each other in a direct way, the motivation to change solutions is based on the differences among solutions. However, in BBO, the motivation is dependent on the design of migration models. In [12], the authors analyze the Markov models for BBO and GA, respectively, and also employ a simple specific problem as an example to compare BBO and GA. Considering the length of this survey, we do not present the problem (which can be found in [16]), but show the conclusion. The author presents BBO’s performance as a function of population size N as follows:

$$\begin{aligned} \frac{{\text {BBO}}\,{\text {performance}}}{{\text {GA}}\, {\text {performance}}} = \left( \frac{5N+7}{3N+9}\right) ^D \end{aligned}$$
(10)

where D is the dimension of a solution. To summarize the conclusion, BBO outperforms GA for all problems sizes and all population sizes. In addition, the authors also use several classical combinatorial problems, including traveling salesman problem, graph coloring problem and bin packing problem, as benchmarks to compare BBO’s and GA’s performances. All the simulation results exhibit that the performance of BBO is superior to that of GA. Besides, the standard BBO also has a big difference comparing with other meta-heuristics. In BBO, the mutation rate is not a predefined constant value, but related to migration models, which means that mutation operator is affected by recombination operator. Besides, for different candidate solutions, their mutation rates are different and dynamically changes during the whole optimization process. The details will be presented in following section.

To present a performance comparison between BBO and several other classical meta-heuristics, we present the numerical simulation results of BBO and other algorithms. In [6], Simon firstly employs several widely used benchmarks to test BBO’s performances. The results can be found in Table 1, where the details of benchmarks can be found in [17]. From Table 1, it is obvious that BBO is very competitive to deal with optimization problems. For Ackley, Fletcher, Rastrigin, Schwefel 1.2, Schwefel 2.21, Schwefel 2.22, Sphere benchmarks, BBO outperforms other algorithms. For other benchmarks, BBO also achieves a very good performance. In [14], the author employs 23 common benchmarks to investigate a more comprehensive comparison. The results also demonstrate that BBO is competent in optimization. The author also investigates the effects of population size, problem dimensions, maximum migration rate, etc. to BBO’s performances, which is helpful for users to adjust parameters in order to pursue a better performance for a specific problem. The author also proposes several new migration models and compare the performances. According to the experimental numerical simulation results, we know that nonlinear migration models are generally superior to linear migration models. However, the simulations are done only for single-objective optimization problems. According to the sequential studies on multi-objective BBO [15], the evaluations to migration models should be reconsidered, which will be illustrated in the following sections.

Table 1 Mean normalized optimization results and CPU times on benchmark functions over 100 monte carlo simulations, and the smallest (best) number in each row is 100
Full size table

3 The development of biogeography-based optimization

3.1 Evaluation and improvement for migration model

Meta-heuristic algorithms have various kinds of ways to handle individuals in population to make them more suitable to the fitness function so that the population evolutes toward optimum. The ways to deal with individuals are usually inspired by nature phenomena. In genetic algorithm, the crossover operator mimics the biological process by generating chromosomes to next generations [1, 18]. Simulated annealing (SA) is inspired by the annealing in metallurgy [19]. The idea of particle swarm optimization (PSO) is inspired from the nature phenomena of birds’ flocking [3]. Ant colony optimization (ACO) mimics the mechanism of ants foraging behavior [5], and artificial bee colony (ABC) models honeybees behavior in collecting nectar [20].

First, we summarize the analysis on migration operators. As a particular operator in BBO, migration helps BBO recombine and improve population. The quality of migration operator is directly influential to algorithm’s performance. In [6], linear migration operator is introduced as shown in Sect. 2. In subsequent researches, novel migration models are proposed and analyzed. Besides the linear migration model, in [14] the author propose five new migration models. By employing a set of 23 benchmarks in the numerical simulation, it is clear that different migration models have different performances. A suitable design of migration model outperforms others for most benchmarks, which also validates the performances of migration models are not random. The conclusion in [14] is given that the performance raises as probability of medium number of species increases, which presents a guidance for users to choose a suitable migration model. However, the conclusion does not hold for all cases. To complete the research of migration models, in [13], Guo et al. investigate migration models in a mathematical way. By employing probability analysis, [13] present the roles of emigration rate and immigration rate, which explore a new view to do the researches on migration model and the conclusions are more helpful to design new migration models. The simulation results are in agreement with the analysis and novel migration models designed based on the analysis is feasible and effective. Besides, Simon [16] investigates BBO by Markov analysis. The probability of population transitioning during one iteration is also proposed.

Second, the details are given as follows. In [6], the original BBO employs a linear migration model which is explained in Sect. 2. After that, in addition to the linear migration model, Ma [14] proposes another five novel migration models which are listed as follows.

Model 1 (Const immigration and linear emigration model)

$$\begin{aligned} \lambda _S&= {} \frac{I}{2} \end{aligned}$$
(11)
$$\begin{aligned} \mu _S&= {} E\frac{S}{N} \end{aligned}$$
(12)

Model 2 (Linear immigration and const emigration model)

$$\begin{aligned} \lambda _S&= {} I\left( 1-\frac{S}{N}\right) \end{aligned}$$
(13)
$$\begin{aligned} \mu _S&= {} \frac{E}{2} \end{aligned}$$
(14)

Model 3 (Linear migration model, which is proposed in [6].)

$$\begin{aligned} \lambda _S&= {} I \left( 1 - \frac{S}{N}\right) \end{aligned}$$
(15)
$$\begin{aligned} \mu _S&= {} E \left( \frac{S}{N}\right) \end{aligned}$$
(16)

Model 4 (Trapezoidal migration model)

$$\begin{aligned} \lambda _S&= {} {\left\{ \begin{array}{ll} I, &{}\text{ if }\quad S\le i'\\ 2I\left( 1-\frac{S}{N}\right) , &{}\text{ if }\quad i'< F(K) \le N\end{array}\right. } \end{aligned}$$
(17)
$$\begin{aligned} \mu _S&= {} {\left\{ \begin{array}{ll} 2E\frac{S}{N}, &{}\text{ if }\quad S\le i'\\ E, &{}\text{ if }\quad i' < S \le N \end{array}\right. } \end{aligned}$$
(18)

where \(i' = ceil(\frac{N+1}{2})\) and ceil() is an operator that makes a variable round toward positive infinity.

Model 5 (Quadratic migration model)

$$\begin{aligned} \lambda _S&= {} I \left( 1 - \frac{S}{N}\right) ^2 \end{aligned}$$
(19)
$$\begin{aligned} \mu _S&= {} E \left( \frac{S}{N}\right) ^2 \end{aligned}$$
(20)

Model 6 (Sinusoidal migration model)

$$\begin{aligned} \lambda _S&= {} \frac{I}{2} \left( \cos \left( \frac{S}{N}\pi \right) + 1\right) \end{aligned}$$
(21)
$$\begin{aligned} \mu _S&= {} \frac{E}{2}\left( -\cos \left( \frac{S}{N}\pi \right) + 1\right) \end{aligned}$$
(22)

According to the numerical simulation in [14], nonlinear migration models perform better than linear migration models. After that, Guo et al. investigate the models’ performances in a mathematical way [13]. The authors analyze the probability to obtain a good feature and the probability to retain the good feature by one-iteration evolution analysis. According to the analysis, for a solution i, the probability to obtain a good feature is given in (23).

$$\begin{aligned} P_\mathrm{obtain} (i) \approx \lambda _i \frac{\sum _{j\in J_i} \mu _j}{\sum _{j=1}^N\mu _j} \end{aligned}$$
(23)

where \(J_i = \{j\in [1,N] : f_j\,\, is\,\,better\,\,than\,\,f_i\}\) and N is the population size. The probability for solution i to retain the feature is given in (24).

$$\begin{aligned} P_\mathrm{retain}(i) = 1 - \lambda _i\left( 1 - \frac{\mu _i}{\sum _j\mu _j} \right) \end{aligned}$$
(24)

From (23) and (24), we know that, for solution i, a large value of \(\mu \) is helpful to obtain and retain good features. However, it is not easy to decide the design for immigration rate, say \(\lambda \). A large value of \(\lambda \) can enhance BBO’s ability to obtain good features, but reduce the probability to retain the features. Hence, the design of immigration model should balance the probabilities to obtain and retain good features.

The analysis of migration operator had also been done by Markov models. In [21], Simon et al. focus on migration operator to investigate BBO’s population transitioning during one iteration. The authors conduct Markov analysis for BBO and use multinomial theory to present the probability Pr(u|v), shown in (25), that BBO obtains a population vector u after one iteration, given that BBO starts with a population v.

$$\begin{aligned} Pr(u|v) = \sum _{J\in Y} \prod _{k=1}^T \prod _{i=1}^N[P_{ki}(v)]^{J_{ki}} \end{aligned}$$
(25)

where

$$\begin{aligned} P_{ki}(v)&= {} \prod _{s=1}^q \left[ \left( 1-\lambda _m\right) 1_0\left( x_m(s)-x_i(s)\right) + \lambda _m \frac{\sum _{g\in G_i(s)}v_g\mu _g}{\sum _{j=1}^nv_j\mu _j}\right] \end{aligned}$$
(26)
$$Y= \left\{ J \in R^{T\times N} : J_{ki} \in \{0,1\}, \sum _{i=1}^NJ_{ki}=1\,{\text {for\,all}}\,k,\sum _{k=1}^TJ_{ki}=u_i\,{\text {for\,all}}\,i \right\}$$
(27)

and \(1_0(\cdot )\) is an indicator function on set \(\{0\}\), \(G_i(s)=\{g:x_g(s)=x_i(s)\}\), T is the number of trials and N is the population size. The introduction of mutation operator based on Markov analysis is given in next subsection. However, the computational cost to calculate Markov model is very expensive because of the \((N+T-1)\)-choose-T size of the Markov transition matrix. In simulation, the authors employ the 3-b one-max problem to validate the analysis conclusion.

3.2 Analysis of BBO’s mutation operator

Like most other meta-heuristic algorithms, BBO also has mutation operator that plays an important role in exploring the search space, maintaining the diversity of population and getting rid of local optimums. In [21], the authors conduct Markov analysis for mutation operator. By defining \(U_{ij}\) as the probability that \(x_j\) mutates to \(x_i\), we obtain a \(n\times n\) mutation matrix U. The probability that the kth immigration trial followed by mutation results in \(x_i\) is denoted as \(P_{ki}^{(2)}(v)\) which can be depicted in (28).

$$\begin{aligned} P^{(2)}_{ki}(v) = \sum _{j=1}^nU_{ij}P_{kj}(v) \end{aligned}$$
(28)

from which we can obtain the following format.

$$\begin{aligned} P^{(2)}(v) = P(v)U^T \end{aligned}$$
(29)

where P(v) is composed by the elements shown in (26). In this case, considering both migration and mutation, the probability of transitioning from population vector v to u after one generation as

$$\begin{aligned} Pr(u|v)=\sum _Y \prod _{k=1}^T \prod _{i=1}^N [P_{ki}^{(2)}(v)]^{J_{ki}} \end{aligned}$$
(30)

where Y is same as in (27).

In Sect. 2.2, we present comparisons between BBO and other meta-heuristics. As mentioned, the design of mutation operator in BBO is very different from the standard version of other meta-heuristics. In most other standard meta-heuristics, the value of mutation rate is predefined by users’ experiences and the value is fixed during the whole optimization process. Besides, the mutation operator is independent of recombination operator. However, there is a big difference between BBO and other meta-heuristics in design of mutation operator. According to (9), for island S, the mutation rate is composed by two parts. The first part is \(m_\mathrm{{max}}\) which is defined by users in advance. This value limits the maximum value of migration rate. The second part is related to probabilities \(P_S\) and \(P_\mathrm{{max}}\). Considering that \(P_S\) and \(P_\mathrm{{max}}\) are calculated based on migration models, mutation rates are related to migration models, which means that if migration model changes, mutation rates change. Besides, for a solution S, its ranking in the whole population may change so that its migration rates will change, and therefore, the value of \(P_S\) changes, then \(m_S\) changes according to (9). Hence, the mutation rate of solution S is not fixed during the whole optimization process, but dynamically changes. To present a visual explanation, an example is given in Fig. 2. In this example, we employ a linear migration model, quadratic model and sinusoidal model, respectively. The population size is set as 50 and predefined mutation rate \(m_\mathrm{{max}}\) is 0.05.

Fig. 2
figure 2

Mutation rates with linear migration model, quadric migration model and sinusoidal migration model (predefined maximum mutation rate \(m_\mathrm{{max}} = 0.05\), population size = 50)

Full size image

As shown in Fig. 2, we can drawn two conclusions: (1) In BBO, for different solutions, their mutation rates are different. (2) The selection of migration models will affect the migration rates. These make the design of mutation operator more complex. In order to reveal the relationship between the mutation operator and migration operator, Guo et al. employ drift analysis to investigate the expected value of first hitting time (EFHT) of BBO with different mutation operators [22]. In that paper, the authors take account into three kinds of objective functions including linear functions, pseudo-modular functions and almost positive functions. For convenience, the authors use detail functions, shown in (31), (32) and (33), to conduct the analysis for mutation operators.

Linear function

$$\begin{aligned} {\text {Maximize}}\,\,F(X)=\sum _{i=1}^nx_i \end{aligned}$$
(31)

Pseudo-modular function

$$\begin{aligned} {\text {Maximize}}\,\,F(X)=\sum _{i=1}^n \prod _{j=1}^{i}x_j \end{aligned}$$
(32)

Almost positive function

$$\begin{aligned} {\text {Maximize}}\,\,F(X)=n - \sum _{i=1}^n x_i + (n+1)\prod _{i=1}^nx_i \end{aligned}$$
(33)

According to the analysis in [22], for the metric first hitting time, quadratic migration model can generate better mutation rates than sinusoidal migration model, and sinusoidal migration model can generate better mutation rates than linear migration model. Since the drift analysis is only implemented to three specific problems, there lacks general conclusions to evaluate the effects of mutation models to BBO’s performance. From the conclusions, it is intuitive to conclude that a large mutation rate can provide more chances for population to obtain good features. Although the conclusions in [22] are limited to specific problems, but useful for readers to do an analysis for given problems. Besides, they are also can be considered as references to design migration models. This conclusions also match the study in [14]. Sinusoidal migration model which can provide a large mutation rate outperforms linear migration model which can only provide a relatively small mutation rate. Besides, the numerical simulation results in [14] also demonstrate that a too large value of mutation rate will also reduce algorithm’s ability. Hence, a proper value of \(m_\mathrm{{max}}\) is crucial to BBO’s performance.

3.3 Development of BBO and hybrid algorithms

After Simon first proposes BBO in 2008 [6], many works to develop BBO have been done from different views. There are mainly four aspects. The first one is improvement of migration operators. As a recombination operator, the design of migration operator directly affects BBO’s performance, and therefore, the related work is most attractive. Many improved versions of BBO’s migration operators have been proposed. Second, mutation operator is also a crucial operator that affects BBO’s performance. Classical and novel mutation operators are implemented to BBO in order to enhance BBO’s ability. Third, in the research of bio-inspired algorithms, hybrid algorithm is also a hot topic, since in general, a hybrid algorithm can combine advantages from two or more algorithms so that the proposed algorithm can exhibit a more powerful ability in optimization. BBO is also been used to hybridize algorithms and achieve very good performances. Fourth, nowadays, many complex problems are raised, including multi-objective optimization, large-scale optimization and expensive optimization. For the specific problems, BBO should be modified to fit the requirements in solving problems. The first three points focus on the improvement of algorithms’ design, while the fourth one is about BBO’s application. In this section, we investigate BBO’s design (the first three points), while the applications (the fourth point) will be summarized in Sect. 4.

3.3.1 Variants of BBO

After the standard version of BBO, Simon proposes a simplified version of BBO, which is called SBBO in [23]. For a migration, the steps are given as follows. For each iteration, SBBO does not evaluate all solutions, but only tracks the best candidate solution.

  1. 1.

    In an iteration, find the best solution \(x_\mathrm{best}\) in the whole population.

  2. 2.

    Randomly generate a integer \(s \in [1,N]\), where N is the population size.

  3. 3.

    Select an island \(x_j\) according to immigration rates which satisfy a uniform probability distribution.

  4. 4.

    \(x_j = x_\mathrm{best}\)

As illustrations in above steps, the immigration and emigration rates meet a uniform provability distribution, which can be explained as in Fig. 3. Based on SBBO, it is easy to be implemented by Markov analysis. In the analysis of [23], the authors focus on the probability per generation that a population optimum improves, the state matrix of the algorithm, and the expected amount of improvement in the population optimum, which provides an easy way for researchers to explore and exploit BBO.

Fig. 3
figure 3

SBBO’ migration curves in island. All solutions have the same probability of migration rates except the best solution with \(\lambda _\mathrm{best} = 0\) and \(\mu _\mathrm{best} = 1\)

Full size image

A dynamic system model for BBO is proposed and discussed in [16]. In [16], Simon summarizes a previously proposed Markov model of BBO and derives a dynamic system model for BBO. In dynamic system model, the authors make a slight modification in standard BBO. In BBO, all N candidate solutions will take part in immigration, while in [16], the algorithm chooses a random candidate solution for N times. The pseudo-codes are given in Algorithm 3. By comparing the dynamic model of BBO with the corresponding models with GA on a set of 19 classical benchmarks, it is obvious that BBO far outperforms GAs in simulation with low mutation rates (0.1xxx). Besides, for problems with large dimension, BBO are also has a better performance than GAs.

figure c

In current years, BBO has been much explored and improved and many variants of BBO are proposed. After Simon proposes BBO, related analysis on standard BBO begins in subsequent works. In 2009, Ergezer et al. propose oppositional Biogeography-Based Optimization (OBBO) in [24] by employing opposition-based learning (OBL) [25]. For OBL, its principle is that a number’s opposite is probably closer than a random number to the right solution. As an efficient machine learning method for reinforcement learning [25, 26], oppositional learning has been well implemented in soft computing including neural network [27, 28], fuzzy systems [29] and differential evolution [30, 31]. For the combination of BBO and oppositional learning, [24] illustrated two ways. The first one is open-path opposition, which is efficient for problems with non-connected nodes such as the graph coloring problem. The second is circular opposition, which is suited for problems where the endpoints are linked, say TSP problem. The simulation results demonstrate that the performance of OBBO enhances as the dimension of problem increases. Compared with the standard BBO, OBBO has a high probability to produce qualified solutions with lower computation cost. A similar way to produce more promising solutions is to employ local searching ability [32, 33], other than the oppositional way, the local searching technology do a local searching around current solutions, which is to enhance the probability to pursue better solutions. In OBBO, OBL algorithm is called with a probability \(J_r \in [0,1]\) after migration and mutation operator. The pseudo-codes are given in Algorithm 4.

figure d

Besides opposition-based learning, an improved version, termed quasi-opposition-based learning technology, is implemented in [34]. For quasi-oppositional operation, Line 10 should be changed as shown in Algorithm 5, where \(Median = \frac{Min+Max}{2}\), \(\kappa \in [0,1]\) is a reflection weight which is introduced to determine the amount of reflection based on the solution fitness.

figure e

3.3.2 Improvement of migration and mutation operators

As a crucial operator in BBO, migration and mutation operators have drawn many attentions in current researches. In 2009, a perturb Biogeography-Based Optimization (PBBO) is proposed in [35]. In standard BBO, if a solution is not selected to be immigrate, migration operator does not run. However, in [35], for the solutions that not be selected to be immigrated, perturb method is used which is to select a neighborhood solution to update the current one. The pseudo-codes are given in Algorithm (6), where \(\varphi \in [-2,0]\) is a random value.

figure f

Besides, the author also employs Gaussian mutation operator in PBBO, which can be depicted in (34).

$$\begin{aligned} H_i(SIV)=H_i(SIV) + N(0,1) \end{aligned}$$
(34)

where N(0, 1), shown in (35), satisfies the Guassian distribution [36].

$$\begin{aligned} N(0,1)=\frac{1}{\sqrt{2\pi }}e^{-\frac{x^2}{2}} \end{aligned}$$
(35)

Two years later, an improvement in migration operator for the case \(H_i\) is selected is proposed in [37]. Considering that in standard BBO, if \(H_i(SIV)\) is selected to be immigrated by \(H_j(SIV)\), the operator \(H_i(SIV)=H_j(SIV)\). This may shrinks searching space so that to results in a local optimum. Hence, Ma proposes a novel operator which combines the features of both immigrators and emigrants, shown in Algorithm 7. This strategy helps BBO maintain population diversity and so that avoid local optimum.

figure g

In Algorithm 7, \(\alpha \in [0,1]\) is used to adjust the weights of current candidate solution and immigrate solution. In [37], the authors investigate the setting of \(\alpha \) in an experimental way. The test results conclude that a proper value of \(\alpha \), say \(\alpha =0.5\), performs better than a large or a small value of \(\alpha \), say \(\alpha =0\) and 0.8, respectively. In [6, 35] and [37], design of migration operator only involves another one solution, which means the current candidate will learn from another solution. To learn from more than one solution in one migration, Xiong [38] proposes, in 2004, a polyphyletic migration operator, which employs another two solutions in migration operator. The pseudo-codes are given in Algorithm 8, where \(\varphi \in [0,1]\), \(i, j, l, s \in [1,N]\), N and D are population size and problem dimension, respectively. After migration, [38] employs orthogonal learning strategy (OLS) so that BBO can search potential solutions around current solutions. The strategy, given in Algorithm 9, is also proposed in [39]. In Algorithm 9, \(A_i = H_{i\_best}^p\), where \(i=1,2,\ldots ,N\). \(H_{i\_best}^p\) is randomly chosen as one of the top \(p\times 100\,\%\) (\(p\in (0,1]\)) ranking solutions in the current population and should be different from \(H_i\). This strategy divides a large dimension into several factors and employs orthogonal rules to produce new generations. Based on the analysis and simulation results, this method helps BBO improve population diversity and enhance the convergence speed. Considering that orthogonal learning strategy is not the main focus in this survey, we do not present the details, but recommend [40] and [41] as references. By combing Algorithm 8 and Algorithm 9, [38] proposes polyphyletic orthogonal learning BBO, which is abbreviated as POLBBO.

figure h
figure i

In [42], the authors propose four variants of migration operators, which are total immigration-based BBO, partial immigration-based BBO, total emigration-based BBO and partial emigration-based BBO, respectively. The corresponding Markov analysis is also done for the four algorithms. For partial immigration model, it is the same as standard BBO, which employs \(\lambda \) to decide whether a solution should be immigrated or not. In total immigration-based BBO, \(\lambda \) is used to decide whether a whole solution should immigrate. If a solution is selected to be immigrated, all the composing features will involve in immigration. The pseudo-codes are shown in Algorithm 10.

figure j

In both partial immigration-based BBO and total immigration-based BBO, the sequence in migration is that emigration occurs after immigration. To change the sequence, Ma [42] proposes partial emigration-based BBO and total emigration-based BBO, which are shown in Algorithm 11 and Algorithm 12. In these two algorithms, immigration occurs after emigration, which means that only emigration rate is used to decide whether migration occurs. If emigration rate occurs by \(\mu \) selection, immigration occurs to select immigrators according to \(\lambda \).

figure k
figure l

Quantum BBO (QBBO) is proposed in [43], which employs multi-quantum probability models. In the decision space, by establishing a quantum model in an area that represents a habitat, migration models work more efficient to generate promising solutions. A combinatorial problem named 0-1 knapsack problem is considered as benchmark in simulations, and the results demonstrate that QBBO have efficient ability to solve hard optimization problem.

In nature, predators must hunt prey to live, while the prey needs to run away from the predators. Inspired by this phenomenon, a predator–prey strategy is imported into the design of BBO to enhance BBO’s searching ability of obtaining good features. In [44, 45] and [46], the authors adopt the concept of predator–prey strategy, which the inferior individuals (preys) will be hunted, namely replaced, by good individuals (predators). The replacement probability increases with increasing iteration. This design is effective to increase population diversity and overcome the traps of local optimum.

Besides the investigation on regular mutation operator, some classical mutation operator are implemented to BBO. Since the regular mutation operator is more likely to mutate in a random way, it lacks the exploration ability. To enhance the effectiveness of mutation operator, Gong [47] employs Gaussian mutation, Cauchy mutation and Lévy mutation, respectively, in real-code BBO to reveal the effects of mutation operator to algorithms’ performances. The three kinds of mutation operators are widely used in evolutionary algorithms. Comparing with standard BBO, the modified mutation operator has a superior ability to explore searching space. Although, in [47], the authors do not draw a conclusion to compare the qualities of the three mutation operator, the modified mutation operators enhance BBO’s performance to explore searching space, especially for the high-dimensional problems. In [48], a modified BBO is proposed which is inspired from the natural phenomenon that same individuals will be prevented. Hence, the authors control the mutation rate to keep individuals from mutating to the near feasible solutions so that the population in BBO can maintain a suitable diversity. In this way, the mutation operator is more effective to help algorithm converge fast. In [49], the authors design a mutation operator by involving chaos mapping, which is given in (36).

$$\begin{aligned} H_{newi}(SIV) = H_{i}(SIV)+(1-2x) \end{aligned}$$
(36)

where \(x_{n+1} = \mu x_n(1-x_n)\), \(\mu \) is the control parameter which is often equal to 4 for full range of mapping and \(x_i\) is a variable between 0 and 1 and the initial value of x, namely, \(x_1 \ne 0, 0.25, 0.5, 0.75, 1\). After mutation, the proposed algorithm operates selection between \(H_{newi}\) and \(H_i\). If the new candidate solution \(H_{newi}\) is better than \(H_i\), then \(H_i = H_{newi}\). Otherwise, \(H_i\) does not change. In standard BBO, the mutation is operated in random way. However, in the chaos way, BBO can mutate around the current solutions so that the algorithm is able to find more precious solutions.

3.3.3 Hybrid algorithms based on BBO

Hybrid algorithms combing advantages of each individual algorithm are widely used to enhance algorithms’ performance. In the research of BBO, hybrid approach is also popular and successful.

In [50], the authors propose DE/BBO algorithm which is a hybridization of BBO and another popular meta-heuristic algorithms termed differential evolution (DE) which is a robust and fast global optimization algorithm [51]. DE/BBO that has the exploration ability of DE and the exploitation ability of BBO is effective to generate competitive solutions in handling global numerical optimization problems. The pseudo-codes of the migration in DE/BBO algorithm are given in Algorithm 13. A set including 23 benchmarks are used to verify the algorithm’s performance. Some other issues including the effects of population size, dimensions, parameter setting are also discussed in that paper. In [52], a BBO-DE algorithms is also proposed and applied to a wireless sensor network (WSN) problem, which the objective is to minimize the total power spent. The algorithm’s performances are compared with BBO and DE, respectively, and show that the proposed algorithm performs better than individual ones.

figure m

In [53], the authors hybridize BBO with other two kinds of evolutionary algorithms, ant colony optimization (ACO) and artificial immune algorithm (AIA) in two different ways. However, the hybrid strategies are only implemented by sequential operating different algorithms, but not combine different meta-heuristical algorithms into a novel algorithm. The flowcharts are given in Fig. 4. Several numerical simulations and practical problems are considered as benchmarks to validate the proposed hybridization method is feasible and effective in solving optimization problems. However, from Fig. 4, we know that the hybrid strategy is proposed just by sequentially operating different algorithms, but do not combine the design ini one algorithm.

Fig. 4
figure 4

a Flowchart for \(BBO\_AIA\_1\), b Flowchart for \(BBO\_AIA\_2\), c Flowchart chart for \(BBO\_ACO\_1\). Cited from [53]

Full size image

In [54], the authors propose a hybrid algorithm of BBO and artificial bee colony (ABC) for global numerical optimization problem. In this paper, the migration operator in BBO is imported by the mechanism of ABC, which trains the migration rates by ABC in order to obtain a more suitable rate setting. This hybridization is helpful for candidate solutions to obtain good features. A set of 13 classical benchmarks are tested to demonstrate the feasibility and effectiveness of this method. By comparing this algorithm with other standard evolutionary algorithms, it shows that the algorithm has superior ability in dealing with optimization problems. In [55], the authors hybridize BBO and PSO to propose biogeography-based particle swarm optimization (BPSO). A hierarchical structure is designed, which the population are split into several groups. The flowchart of BPSO is given in Fig. 5. For each generation, in the inner of group, PSO is utilized to select elite individuals and all the elite individuals composes the initial population for BBO. The individuals selected by BBO will take part in the next generations of PSO. Based on the simulation results, the BPSO outperforms both of BBO and PSO. Several mechanical design problems are also considered as benchmarks to validate the superiority of hybrid design.

Fig. 5
figure 5

Flowchart of BPSO. Cited from [55]

Full size image

4 The applications of biogeography-based optimization

Considering that BBO’s performances are very outstanding in different kinds of optimization problems, this algorithm has drawn many worldwide attentions and been implemented to various kinds of practical applications including power systems, image processing, wireless network, path planning and job shop schedule. A list of BBO’s applications are presented in Table 2.

Table 2 Applications and Implementations of BBO
Full size table

As a very important practical area in industry, power system is a very hot and attractive practical case. In power system problems, economic load dispatch (ELD) problem and optimal power flow are common and important. In [82, 85] and [83] which is a global optimization problem with multi-objectives and has nonlinearity and constraints, is a common and important problem in power system. In [83], the authors propose four kinds of economic load dispatch problems, which are ELD with quadratic cost function and transmission loss, ELD with prohibited operating zones and ramp rate limits, ELD with valve-point loading effects, and ELD with combined valve-point loading effects and multi-fuel options, respectively. By employing BBO in [83] and [82], Bhattacharya considers two cases that are convex optimization and non-convex optimization, respectively, in ELD and the simulation results show a good performance of BBO. For BBO, it is easy to deal with non-convex optimization with constraints which includes transmission losses, electric load, limitation of slide speed, multi-fuel and no operation area. In [84], Bhattacharya uses DE and BBO to deal with ELD problem in convex and non-convex thermal power generator and gains well performance in handling this problem.

In [56], Ergezer et al. further explore OBBO, which introduce two different strategies of opposition, open-path opposition and circular opposition, respectively, to solve two types of combinatorial optimization problems, 16 vertex coloring problem and 16 traveling salesman problem, respectively. The results validate the superiority of OBBO. In [87], a Cauchy mutation strategy is introduced into an improved biogeography-based optimization (IBBO) algorithm in order to design an optimal sub-synchronous damping controller. The distribution function of Cauchy distribution is given in (37).

$$\begin{aligned} {\mathcal {C}}(i) = \frac{1}{2} + \frac{1}{\pi \arctan (i)} \end{aligned}$$
(37)

The formula of the mutative scale of chaos and Cauchy distribution is given as follows:

$$\begin{aligned} H_{new\_i}(SIV) = (1-\varpi _{SIV})H_{cb}(SIV) + \varpi _{SIV} {\mathcal {C}}(i) \end{aligned}$$
(38)

where \(H_{new\_i}\) is the newly generated optimized individual and \(H_{cb}\) is the best individual in current population. After running (38), if the fitness of \(H_{new\_i}\) is better than that of the \(H_{cb}\), it remains. Otherwise, we still use \(H_{cb}\) as the current best solution and give up \(H_{new\_i}\). \({\mathcal {C}}(i)\) is the chaos or Cauchy iteration variable mapped to the parameters of the search space. \(\varpi _{SIV}\) is a variable scale factor, which can be obtained with the following formula:

$$\begin{aligned} \varpi _k = 1 - \left| \frac{(k-1)}{k}\right| ^\gamma \end{aligned}$$
(39)

where \(\gamma \) is a parameter which is to adjust convergence speed. The paper summarizes the design of SVC controller as a constrained optimization problem as follows:

$$\begin{aligned} max\,\,f=\frac{1}{n}\times ||R||_1 \end{aligned}$$
(40)

where \(R=(\eta _1,\eta _2,\ldots ,\eta _n)^T\), \(||R||_1=\sum _{i=1}^n\eta _i\), \(\eta _i>0\). The simulation results show that the improved BBO is competent to solve SVC controller. The Cauchy mutation strategy is also used in [67]. By importing cauchy mutation in BBO, paper [67] applies BBO to image matching based on lateral inhibition technology and the results also demonstrate that the Cauchy mutation is competitive in dealing with the optimization in image matching.

In [55], a hybrid strategy on BBO and PSO is proposed. In the hybridization, two strategies are employed. The first one is hierarchical strategy. The whole population is divided into several groups. In each group, namely low layer, PSO is implemented to select good individuals. All group good individuals are collected together as a new population in upper layer to be implemented by BBO. Second, in the selection from groups to upper layer, a large proportion of individuals are adopted. This strategy helps algorithm employs more good solutions in generating next population. By employing several classical mechanical engineering problems, the algorithm is tested and the results demonstrate the proposed algorithm is superior to previous work.

BBO is well implemented in complex system with multi-subsystems, multi-objectives and multi-constraints [92]. Considering that complex system is very common in practical applications which involve more than thousands of variables, it is very necessary to design BBO for complex systems. In [92], the authors propose the idea of distances between island to rank solutions, which is given as follows:

$$\begin{aligned} \mathrm{Distance} = \sqrt{\sum _{k=1}^c(S_{hak} - S_{hbk})^2} \end{aligned}$$
(41)

The distances are influential to migration rates and therefore affect algorithms’ performances. This calculation is valid if and only if both islands share the same structure, which means that they have the same SIV type at the same location. However, in a complex system, subsystems usually have different island structures. Three complex system optimization algorithms are used to compare the design of BBO/Complex. The results show that BBO demonstrates a very competitive performance.

In [45], the authors apply BBO with predator–prey strategy to optimize power flow. In predator–prey strategy, the best solution is considered as a predator, while the worst solution is considered as a prey. Predator is motivated to affect other solutions, while the prey is pushed to be improved. Hence, the algorithm can exhibit a huge potential to pursue optimums. Predator–prey strategy is also used in [46] and extended to multi-objective optimization problems in [44].

In [80], the authors consider a three-objective power flow problem, and 9-bus, 26-bus and IEEE 118-bus systems are taken into account as the benchmarks to compare BBO and other well used optimization algorithms including genetic algorithm and particle swarm optimization. The simulation results demonstrate that BBO outperforms others in handling this optimization problem. BBO also performs well in parameter estimation and tuning. The algorithm is employed in PID controllers for vibration control of active suspension system in [74]. Paper [62] employs BBO and Kalman filter in wireless network learning control system for PID parameter tuning. Besides parameter estimation in PID controller, BBO is also used to other systems for parameter estimation. In [76, 78] and [77], the authors employ BBO to investigate the parameter estimation in chaotic system. According to the results, BBO is competitive in dealing with parameter estimation problems. Considering that meta-heuristics is very popular in design of antenna, in [59], BBO is adopted in the design of isotropic linear antenna arrays by optimizing null control and side lobe level. In [63], the authors use BBO to help cognitive radio system to meet the quality of service including five objectives : maximum spectral, minimum interference, maximum throughput, minimum bit error rate and minimum transmit power. There also exist successful cases of BBO in transportation systems. Emergency railway wagon scheduling plays an important role in railway transportation. By employing BBO, Zheng et al. [93] investigate the scheduling for emergency railway wagon in a mathematical way, which takes into account multiple targets stations, source stations and transfer stations. Path planning is a hot topic in various kinds of applications, such as [46] and [94] for path planning in uninhabited combat air vehicle (UCAV) and Voronoi diagram (VD).

All the achievements illustrate that BBO does not only exhibit a dramatic performance in analysis and numerical simulation, it also plays an active role in applications. In above applications, the comparisons of BBO and other evolutionary algorithms are conducted and the results show that BBO is competent to solve optimization problems.

5 Discussions and conclusions

In current years, BBO deserves worldwide attentions due to its novelty and remarkable performance. However compared with some other classical meta-heuristics such as genetic algorithm, particle swarm optimization and ant colony optimization, the basic research of BBO is not completed. Hence, there still exists some topics related to BBO are supposed to be further investigated. The examples are given that the parameter setting, complexity analysis, design of fitness functions as well as the exploitation of applications should be studied in future work.

To be specific, two aspects are illustrated as follows. First, in the field of theoretical research, though BBO has been analyzed by establishing Markov model and theoretical/experimental comparisons also validate the superiority of this algorithm, there is still a long way to further explore this algorithm. Although the improvements of algorithm including the proposal of PBBO, OBBO, DE/BBO and PBSO have demonstrated their powerful abilities in simulations and experiments of computation and optimization, the investigations of mechanisms of these algorithms including convergence and complexity analysis are few in a mathematical view. Besides, the hybridization of algorithms can be conducted from the view of other disciplines including fuzzy logistics, neural networks and big data structures. Second, the applications of BBO can be exploited in future work. By referring the applications of other meta-heuristics, BBO can play more important roles in various areas including data mining, information security and bioinformatics, since its current applications exhibit that BBO has a competitive ability in dealing with practical implementations.