Keywords

1 Introduction

The knowledge of biogeography can be traced back to the work of the nineteenth century by naturalists such as Darwin and Wallace [1, 2]. In the early 1960s, MacArthur and Wilson begin working together on mathematical models of biogeography, the work culminating with the classic 1967 work “The Theory of Island Biogeography” [3]. Their concentration was primarily observant on the distribution of biological species surrounded by neighboring islands along with the geo-temporal revolution. They were attracted to mathematical models of biogeography to describe speciation (the evolution of new species), the migration of species (animals, fish, birds, or insects) between islands, and the extinction of species.

BBO algorithm introduced by Simon in 2008 [4] was motivated by the theory of island biogeography. The novel idea of original BBO algorithm is based on the principle of migration strategy of biological genesis for solving complex optimization problem by maintaining a population of candidate solutions. In BBO, the components’ involvement in arrangements is equal to the species’ movement in biogeography. Migration model imitate species migration among islands, which provides a recombination way for candidate solutions to interact with each other so that the properties of the population can be improved by keeping the best solutions from previous generation. In BBO, a global optimum solution is one with low Habitat Suitability Index (HSI) that can share their features with poor habitat. This can be achieved only by migrating Suitability Index Variables (SIVs) from emigrating habitats to immigrating habitats. The original BBO is based on linear migration model [4], and the way to perk up algorithms’ performance, several other popular novel migration models are introduced. Motivated by the migration mechanisms of ecosystems and its mathematical model, various extensions to BBO are proposed for achieving information sharing by species migration.

In this paper, we propose a novel technique for migration for enhancing the performance of BBO. The migration operator combines the features from a locally best nearest neighborhood of the individual to be migrated with globally best individual of the pool. Thereby, the LGBBO mimic the species distribution under local best and global best optimum solution, and thus achieves a much better balance between exploration (global search) and exploitation (local search). In Sect. 2, the overviews of BBO and its improvements have been summarized. In Sect. 3 the LGBBO technique has been discussed. The numerical benchmarks are working to test the proposed migration operators and the results are compared with previous work in Sect. 4. In Sect. 5, the conclusions and future research directions are discussed.

2 Review of Biogeography-based Optimization

In BBO, algorithm initializes with population of candidate solutions that are called habitats. Habitats with a high HSI can support many species, whereas low HSI habitats support only a few species. Low HSI habitats can improve their HSI by accepting new features from more attractive habitats in the adaptation process. BBO migration is a probabilistic operator that adjusts each habitat Hi by taking SIVs from a higher HSI habitat. In [4], Simon proposed a migration model which is expressed in Eq. (1). Each habitat has its own probabilistic operators based on HSI as emigration rate \((\mu )\) and immigration rate \((\lambda )\) to define the migration rate for next generation. The migration rates are directly related to the number of species in a habitat. Thus the migration process increases the diversity of the habitat and contributes the likelihood of which information to be shared between the species. The emigration and immigration rates can be calculated in Eq. (2) as follows when there are k species in the habitat:

$$H_{i} ({\text{SIV}}) \leftarrow H_{j} ({\text{SIV}})$$
(1)
$$\mu_{k} = \frac{Ek}{{S_{ \hbox{max} } }}\;{\text{and}}\;\uplambda_{k} = I(1 - \mu_{k} ),$$
(2)

where E is the maximum emigration rate, I is the maximum immigration rate, and \(S_{ \hbox{max} }\) is the largest achievable number of species that the habitat can support. We have shown the emigration and immigration rates in Fig. 1 as straight-line model of species large quantity in a single habitat gives us a general description of the process of emigration and immigration [5]. If there are no species on the island, then the emigration rate is zero. The equilibrium number of species is \(S_{0}\), at which point the emigration and immigration rates are equal.

Fig. 1
figure 1

Illustration of two candidate solutions: \(S_{1}\) is a relatively poor solution, while \(S_{2}\) is a relatively good solution

Full size image

\(S_{1}\) in Fig. 1 represents a low HSI solution, while \(S_{2}\) represents a high HSI solution. Thus, the immigration rate \(\uplambda_{1}\) for \(S_{1}\) will be higher than the immigration rate \(\lambda_{2}\) for \(S_{2}\). Similarly, the emigration rate \(\mu_{1}\) for \(S_{1}\) will be lower than the emigration rate \(\mu_{2}\) for \(S_{2}\). After migration procedure, the mutation operator is used to enhance the diversity of the population to get better solutions. In BBO, mutation is also a probabilistic operator which is used for modifying one or more randomly selected SIV of a solution based on its priori probability of existence \(P_{i}\). It changes a habitat’s SIV randomly based on mutation rate \(m_{i}\) in Eq. (3) that is calculated using solution probability:

$$m_{i} = M_{ \hbox{max} } \left( {1 - \frac{{P_{i} }}{{P_{ \hbox{max} } }}} \right),$$
(3)

where \(m_{i}\) and M max are the user-defined parameters of mutation rate and the maximum mutation rate, and P max is the maximum probability of species count.

2.1 Canonical BBO

Simon [4] uses linear migration model in BBO, which means that \(\lambda\) and \(\mu\) are the linear functions of solution fitness and are normalized to the range [0, 1]. The pseudocode of canonical BBO is given below.

2.2 Variants of BBO

It is evident from the literature study on BBO that the improvements are based on a modification of migration process only. Guo et al. [6] investigated the migration model by stochastic approaches and exposed the relationship between migration rates and algorithm’s performance. Ma et al. [7] and Ma and Simon in [8] proposed a variation of migration model of BBO by using Markov theory. After central BBO, Ergezer et al. [9] proposed oppositional BBO (OBBO) by employing opposition-based learning (OBL). The migration operation of OBBO can be expressed in Eq. (4) as

$$OH_{i} ({\text{SIV}}) \leftarrow {\text{Min}} + {\text{Max}} - H_{i} ({\text{SIV}}).$$
(4)

In [4], the original BBO employs a linear migration model, after that, in addition to the linear migration model, Ma et al. [7] explored the performance of six migration models which are inspired by the science of biogeography generalizing the equilibrium species count of biogeography theory and showed that the sinusoidal migration model outperforms other models. In [10], Ma et al. proposed a blended migration operator (BMO) shown in Eq. (5), which is inspired from [7]:

$$H_{i} ({\text{SIV}}) \leftarrow \alpha H_{i} ({\text{SIV}}) + (1 - \alpha )H_{i} ({\text{SIV}}),$$
(5)

where \(\alpha \in [0,1]\) is a random or deterministic value. In [10], Ma and Simon extend the work of [8] to propose a uniform blended migration operator (UBMO) and nonuniform blended migration operator (NUBMO). They investigate the setting of \(\alpha\) in an experimental work to test the results and 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.0\) and 0.8, respectively. Feng et al. in [11] proposed the Heuristic Migration Operator (HMO) as shown in Eq. (6), where the parameter \(\beta \in [0,1]\) and \(F(.)\) is a fitness function:

$$H_{i} ({\text{SIV}}) \leftarrow H_{i} ({\text{SIV}}) + \beta (H_{j} ({\text{SIV}}) - H_{i} ({\text{SIV}})),F(H_{j} ) \ge F(H_{i} ).$$
(6)

Gong et al. [12] have proposed popular hybrid alpha-heuristic approach called DE/BBO algorithm in order to balance the exploration of DE and the exploitation of BBO effectively. Siarry and Ahmed-Nacer in [13] proposed a hybridize BBO with different kinds of evolutionary algorithms such as Ant Colony Optimization (ACO) and Artificial Immune Algorithm (AIA) in two different ways. Simon proposed that the canonical approach of BBO has some weakness on its exploration [4]. In total immigration-based BBO, \(\uplambda_{k}\), 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. Xiong et al. [14, 15] proposed a polyphyletic migration operator; here the current candidate will learn from another solution to extract best features. The migration operation can be expressed in Eq. (7) as follows. When immigration satisfied then,

$$H_{i} ({\text{SIV}}) = \left\{ {\begin{array}{*{20}l} {H_{j} ({\text{SIV}}) + k(H_{j} ({\text{SIV}}) - H_{i} ({\text{SIV}})),} \hfill & {{\text{if}}\;{\text{migration}}\;{\text{satisfied}}} \hfill \\ {H_{j} ({\text{SIV}}),} \hfill & {\text{Otherwise}} \hfill \\ \end{array} } \right..$$
(7)

Simon et al. [16] have proposed an idea of the multi-parent migration operator came from the multi-operators in GA and DE. Orthogonal migration operator was introduced in [17] by employing an orthogonal crossover rule. In standard BBO, if a solution is not selected to be immigrating, migration operator does not run. Thus, Li et al. [18] proposed a new variant of BBO known as Perturb Biogeography-Based Optimization (PBBO) that is used to select a neighborhood solution to update the current one. Based on the previous researches, we are inspired to propose novel and effective migration operator to find the global best feasible optimal solution by using the nearest best solution. Zheng et al. [19] proposed a new variation of BBO, named eco-geography-based optimization (EBO), which regards the population of islands as an ecological system with a local topology.

3 Proposed Work

Recall that BBO is natured inspired algorithm and motivated by the geographical distribution of organisms which involves the study of the migration of biological species between habitats. From subsection 2.2 it is evident that researchers contributed various migration models of BBO with significant results in performance. However, they have their own merits and demerits. To avoid some of the pitfalls of the existing BBO, the proposed LGBBO adapted a novel migration operation which is strongly inspired by the learning mechanisms of school children. The idea is centered on the learning mechanism of a weaker class student for adapting knowledge from stronger students. In nature, it is very often noticed that a weaker student is directly influenced by a student who is better in local context rather than global context. In other words, a weak individual try to adapt best features from the best individual from their nearest neighbor instead of adapting features from best individual of the pool (i.e., global best). However, moving with this strategy a habitat may trap in local optima; therefore, in this approach the combined effort of local best habitat from a predefined size of neighborhood and a global best is explored to uncover the global optimal solution. The model is presented in Eq. (8):

$$H_{i} ({\text{SIV}}) \leftarrow \alpha NN(H_{i} ({\text{SIV}})) + (1 - \alpha )H_{j} ({\text{SIV}}),$$
(8)

where the parameter \(\alpha\) is named as immaturity index, to represent the island immaturity of the geographical system (population), which is inversely proportional to the invasion resistance of the system. The nearest neighbor of habitat \(NN(H_{i} (SIV))\) can be defined in Eq. (9) as

$$NN(H_{i} ({\text{SIV}})) \leftarrow H_{(i \le r?1:i - r)} ({\text{SIV}}),$$
(9)

where r is the radius of neighborhood. Since the HSIs are sorted in manner, the best nearest neighbor habitat can be found at \((i - r)\). When \(i \le r\) then the best habitat has been chosen as the locally best.

4 Experimental Works

The focus of this section is to evaluate the efficiency of the nearly developed model. Hence to accomplish the objectives, this section is divided into three Sects. 4.1, 4.2, and 4.3.

4.1 Test Functions and Environments

The task of any good global optimization algorithm is to find globally optimal or at least sub-optimal solutions. The objective functions could be characterized as continuous, differentiable, unimodal, multimodal, separable, and regular. Table 1 presents the details of the well-established 10 benchmark functions and their features that are used to test the performance of the proposed migration model as LGBBO and the results are compared with other developed models like canonical BBO and BBBO. The more details about benchmark functions can be found in [4]. The simulation has been done in an Octa Core i7 x64 CPU with 8GB 1600FSB RAM. We use R programming on LINUX platform for the analysis.

Table 1 Benchmark functions and their features
Full size table

4.2 Parameter Setup

In order to compare the performances of BBO and BBBO with proposed LGBBO, a series of experiments on benchmark functions are carried out to test the efficiency. For initializing the LGBBO, the maximum species count, the maximum migration rates, the maximum mutation rate, and an elitism parameter are defined. 100 habitats and 250 maximum iterations with initial mutation probability of 0.1 have been considered. An \(\alpha\) value of 0.15, 0.25, 0.35, and 0.5 has been tested for the BBBO and LGBBO. For the LGBBO a fraction of 0.1, 0.15, and 0.2 habitats (i.e., 100 * 0.1 = 10 habitats) has been chosen as the neighbors.

4.3 Results and Analysis

Table 2 presents the simulation result obtained by BBO, BBBO \((\alpha = 0.25)\), and LGBBO \((nndist = 0.1,\;\alpha = 0.25)\) for the 10 benchmark functions over 50 independent runs. The table shows the comparative result of best (min), mean, and standard deviation (Std.) values over the iterations.

Table 2 Simulation statistics obtained by BBO, BBBO \((\alpha = 0.25)\), and LGBBO \((nndist = 0.1,\;\alpha = 0.25)\) on 10 bench mark functions over 50 independent run
Full size table

Figure 2 provides a graphical view of the comparison of BBO, BBBO, and LGBBO. In Fig. 2, the cost over generation has been plotted for the benchmark functions over 50 independent runs. The plot has been built using generation-wise boxplot for three types of BBO. The comparative results of these functions indicate that LGBBO performs significantly better than other BBOs. The experimental results illustrate that LGBBO has the superior searching ability to other methods both on convergence speed and accuracy.

Fig. 2
figure 2

Graphical presentations of the generation-wise cost for the benchmark functions Ackley, Dejong, Griewank, Levy, Powell, and Raster. The simulation has been carried out for 30-D over 50 independent runs. The box plot indicates generation-wise mean and standard deviation for BBO, BBBO, and LGBBO

Full size image

5 Conclusions and Future Research Directions

In this paper, to eradicate the deficiencies of the canonical BBO algorithm, we proposed a new BBO by using a new migration method called LGBBO. By using 10 benchmark test functions including unimodal and multimodal functions, we provide a comparative study of LGBBO with canonical BBO and BBBO. An experimental result shows that LGBBO algorithm has strong local best and global best searching ability. It has improved the convergence speed and convergence precision; therefore, it is very effective to solve complex functions optimization problems. Our future research direction includes (i) performance evaluation of LGBBO in domains like financial engineering and big data analysis, (ii) convergence analysis, and (iii) many more specific problems of computational finance.