International Journal of Computational Intelligence Systems

Volume 9, Issue 3, June 2016, Pages 544 - 558

Migration Ratio Model Analysis of Biogeography-Based Optimization Algorithm and Performance Comparison

Authors
Jie-sheng Wang1, wang_jiesheng@126.com, Jiang-di Song2, sjd2011@163.com
1National Financial Security and System Equipment Engineering Research Center, University of Science & Technology Liaoning, Anshan, Liaoning province 114044, China
2School of Electronic and Information Engineering, University of Science & Technology Liaoning, Anshan, Liaoning province 114044, China
Received 11 May 2015, Accepted 2 March 2016, Available Online 1 June 2016.
DOI
10.1080/18756891.2016.1175817How to use a DOI?
Keywords
Biogeography-based optimization algorithm; migration ratio model; function optimization; performance comparison
Abstract

Biogeography-based optimization (BBO) algorithm is based on species migration between habitats to complete information circulation and sharing, which achieves the global optimization by improving the adaptability of habitats. In this paper, the basic migration balance model of biogeography theory is elaborated. Based on the population adaptive migration mechanism of BBO algorithm, the algorithm procedure is set up. Seven linear or nonlinear migration ratio models (including three new migration ratio models) are described. Simulation experiments are carried out on eight testing functions to verify the proposed migration ratio models. Simulation results show that different migration ratio model has different influence on the optimization performance of BBO algorithm, in which the sine migration ratio model has the best optimization performance. This also represents that the nonlinear migration ratio model close to the natural laws outperforms other simple linear migration ratio models.

Copyright
© 2016. the authors. Co-published by Atlantis Press and Taylor & Francis
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

The nature of function optimization problem is to find the optimal solution of an objective function through iterative1. The function features are usually described as continuous, discrete, linear, non-linear, convex function, etc. In that the constraint function optimization problem can be converted into unconstrained problem by using the designed special operators and penalty functions to make solution always feasible, the unconstrained function optimization problem is the main research focus. The swarm intelligent optimization algorithms2 are a kind of random search algorithm to simulate the biological population evolution and evolution, which solves the complex global optimization problems through individual cooperation and competition between species, and is applied in many fields, such as multi-objective optimization, data mining, network routing, signal processing, pattern recognition, etc. The typical swarm intelligence optimization algorithms include ant colony optimization (ACO) algorithm3, genetic algorithm (GA)4, particle swarm optimization (PSO) algorithm5, and artificial bee colony (ABC) algorithm6.

Artificial bee colony algorithm (ABC), which is inspired by the foraging behavior of honey bee swarm, is a biological-inspired optimization. Inspired by PSO, an improved artificial bee colony (ABC) algorithm called g-best-guided ABC (GABC) algorithm was proposed by incorporating the information of global best (g-best) solution into the solution search equation to improve the exploitation. The experimental results tested on a set of numerical benchmark functions show that GABC algorithm can outperform ABC algorithm in most of the experiments7. In that ABC is good at exploration but poor at exploitation, and its convergence speed is also an issue in some cases, an improved ABC algorithm called I-ABC was proposed, where inertia weight and acceleration coefficients are introduced to modify the search process. On the other hand, in order to inherit the bright sides of ABC, GABC and I-ABC, a high-efficiency hybrid ABC algorithm, which is called PS-ABC, is proposed. PS-ABC owns the abilities of prediction and selection. Results show that PS-ABC has a faster convergence speed like I-ABC and better search ability than other relevant methods for almost all functions8. A new modified genetic algorithm with adaptive elitist-population strategies was proposed for multimodal function optimization, which is based on the concept of adaptively adjusting the population size according to the individuals’ dissimilarity and a novel direction dependent elitist genetic operator. Simulation results show that it is very efficient and effective in finding multiple solutions of complicated benchmark and real-world multimodal optimization problems9. A hybrid niching algorithm based on the PSO was proposed to deal with multimodal function optimization problems10, where the recombination-replacement crowding strategy that works on the archive population is introduced to improve the exploration capability. An ensemble of differential evolution algorithms employing the variable parameter search and two distinct mutation strategies in the ensemble was proposed to solve real-parameter constrained optimization problems, which was tested using benchmark instances11. An improved fruit fly optimization (IFFO) algorithm was proposed for solving continuous function optimization problems. A new control parameter is introduced to tune the search scope around its swarm location adaptively and a new solution generating method is developed to enhance accuracy and convergence rate of the algorithm12. Cuckoo search algorithm which reproduces the breeding strategy of the best known brood parasitic bird, the cuckoos has demonstrated its superiority in obtaining the global solution for numerical optimization problems. An improved cuckoo search algorithm with adaptive step size adjustment is introduced and its feasibility on a variety of benchmarks is validated13.

BBO Algorithm is a new type of swarm intelligent optimization algorithms and formally put forward by an American scholar Simon in 200814,15, whose basic idea is based on the species migration to complete the information flow between habitats. It achieves information sharing, the suitability improvement of habitats and obtains the optimal solution through adjusting immigration rate and emigration rate, migration topology, migration interval and migration strategies in the process of migration16. Compared with other swarm intelligent optimization algorithms, the main advantages of BBO algorithm are little adjusted parameters, simple implement, fast convergence velocity and high searching precision, which has been successfully applied in economic load assignment17, combinatorial optimization18, power distribution of wireless sensor network19, function optimization20 and other global optimization problems. In this paper, the basic migration balance model of biogeography theory was elaborated. Seven migrating operators including the newly proposed migration ratio models have been used to realize the information sharing of BBO algorithm. Simulation results show that the different migration strategies have different influence on the optimization performance of BBO algorithm.

2. Biogeography-Based Optimization Algorithm

2.1. Overview of BBO algorithm

The biogeography-based optimization (BBO) algorithm is derived from the biogeography discipline, which is primarily based on the distribution of species in nature. The mathematical model was designed with the following factors in mind: the habitat of many species, the migration route, the formation of new species, and the destruction of the species in nature14,15. Species have certain rules according to which migration is conducted among disconnected islands through various barriers. Species can realize migrations among these islands by drifting, using the wind, and many other ways. A diagram illustrating multiple habitats in biological geography is shown in Fig. 1.

Fig. 1.

Diagram of multi habitats in biological geography.

In addition to the relationship among the islands, each island has its own given factors and survival indicators, which is defined as the Habitat suitability index (HSI). The dependent index variables affecting the HSI are named the independent habitat variables. The higher the island’s HSI index, the lower the immigration rate of the population. The biogeography-based optimization (BBO) algorithm adopts the integer coding rule. A probability-based migration operator (Habitat migration operator) is set up to enable information sharing among the individuals in the population. The individuals also have their antagonistic emigration rate μ and the immigration rate λ so as to control the movement probability of individuals.

2.2. Basic migration balance model of biogeography

A model representing the migration of a single species from an island is shown in Fig. 215. Assuming the ratio of emigration and immigration of the specie migration model of a single HS is μ and λ, respectively, then the number function of species in the island is established.

Fig. 2.

Species migration model of single island.

It can be seen from Fig. 2 that when the number of species is zero, the emigration rate is zero, and when the number of species reaches the maximum capacity of species Smax, the emigration rate reaches the maximum value E. Similarly, when the number of species is zero, the immigration rate assumes the maximum possible value I. When the number of species reaches the maximum Smax, the corresponding emigration rate is zero. Equilibrium is reached at point S0 when the emigration rate μ is equal to the immigration rate λ . Using the BBO algorithm and assuming the number of species on an island is S with probability Ps, its change over time [t,t + Δt] can be described as follows.

PS(t+Δt)=PS(t)(1λSΔtμSΔt)+PS1λS1Δt+PSμS+1Δt

When the number of species on the island is S at time t + Δt, the island’s emigration rate is μs and the immigration rate is λs, and at least one of the following conditions is satisfied.

  1. (1)

    At time t, the number of species is S ; at time [t, t + Δt], there is no emigration and immigration of the species.

  2. (2)

    At time t, the number of species is S + 1 . At time [t, t + Δt], there is at least one of the species available to immigrate.

  3. (3)

    At time t, the number of species is S − 1 . At time [t, t + Δt], there is at least one of the species available to emigrate.

If Δt is sufficiently small for this specie, the probability of emigration and immigration can be ignored regardless of other factors. Define n = Smax and P = [P0,P1,⋯,Pn]T, Ps(S = 0,1,⋯,n) can be arranged into a single matrix:

P=AP
p={(μs+λs)Ps+μs+1Ps+1,S=0(μs+λs)Ps+μs1Ps1+μs+1Ps+1,1S<Smax1(μs+λs)Ps+μs1Ps1,S=Smax
A=E[(μ0+λ0)μ00λ0(μ1+λ1)μ2λn2(μn1+λn1)μn00λn1(μn+λn)]

Assuming E = I, the situation depicted in Fig. 2 can be simplified by reducing it to that shown in Fig. 3 and Eq. (5)(6).

μk=Ekn
λk=I(1kn)
where n = Smax and k is the number of species. Thus, Eq. (4) can be reduced to:
A=E[11n00nnn2n2n1nn001n1]=EA

Fig. 3.

Simplified species migration model on single island.

The probability of each island holding the number of species is given by the following equation:

Pk={P0=11+l=1nλ0λ1λl1μ1μ2μl,k=0Pk=λ0λ1λk1μ1μ2μk(1+l=1nλ0λ1λl1μ1μ2μl),1kn

If the species migration curves in each island (solution) are the same, it can be seen from Fig. 3, S2 would represent a high HSI solution and S1 would indicate a low HSI solution. The emigration rate of S1 is lower than the corresponding emigration rate S2 . Likewise, the immigration rate of S1 is higher than the immigration rate of S2 . The migration rate of each solution enables the information to be shared among islands.

2.3. Biogeography-based optimization algorithm

The BBO algorithm is a method composed by using n habitats with a D -dimension SIV fitness vector. Hi represents the fitness value of the habitat i . By comparing the habitat values of Hi with Smax, the number of all species is denoted as n . Then, the remaining population of the habitat Si is realized by the successive reduction i according to Hi from good to bad, that is to say Si = Smaxi (i = 1,2,⋯,n). By the above calculation, the emigration rate μ and immigration rate λ of Hi can be obtained for the simplified migration model and the probability P(Ki) of species contained in Hi can be calculated

MS=Mmax.(1PSPmax)

Thus, the mutation rate Mi of each Hi is obtained. The global variables are composed of the highest emigration rate E, the immigration rate I, the mutation rate Mmax, the number of the elite individual Z and the global migration rate Pmod . The algorithm procedure is shown in Fig. 4. The flowchart is described as follows.

  • Step 1:

    Initialize all parameters variables and SIV of Hi vector for any chosen habitats.

  • Step 2:

    For different suitability degree Hi, sort the habitats from good to worse. Generally, the update rate of habitat is set as i = 1 .

  • Step 3:

    By comparison, if the desired optimum is reached, output the optimum and the algorithm procedure ends. Otherwise, continue to Step 4.

  • Step 4:

    Suppose one specie in a habitat has the maximum number Smax = n . Then by means of Si = Smaxi (i = 1,2,⋯,n) obtain the population value Si of habitat i, further derive λi and μi from the migration model.

  • Step 5:

    The cycle iteration number of Pmod is the number of habitats n. Pmod is used to judge whether i meets the immigration condition. If it satisfies the corresponding condition, then enter the λi cycle. If SIVij satisfies the immigration condition, the emigration rate of other habitats μm (m = 1,2,⋯,n, mi) is used to perform a random selection to select the m characteristics component SIVmj to replace the precedent i characteristics component SIVij.

  • Step 6:

    By calculating the corresponding habitat Mi, the judgment is carried out on the related variables of habitat i to see whether the mutation occurs or not, then return to Step 2 for next cycle.

Fig. 4.

Flowchart of BBO algorithm.

3. Migration Ratio Models

According to the biogeography species distribution, the different linear and nonlinear migration ratio models of biogeography are obtained, in which four migration ratio model are come from Ref. 21, at the same time, other three migration ratio models are new put forward: sine migration ratio model, migration ratio model with constant emigration rate and migration ratio model with constant immigration rate. As shown in Fig. 5, the immigration rate λk and the emigration rate μk are the function of species diversity k in the habitat; I indicates the maximum immigration rate; E indicates the maximum emigration rate; k0 is the number of species at the point of habitat equilibrium, that is to say the immigration rate is equal to the emigration rate at that point.

Fig. 5.

Seven migration ratio models.

3.1. Exponential migration model

As shown in Fig. 5(a), the immigration rate λk and the emigration rate μk calculated by Eq. (10) are the exponential function of species diversity k in the habitat at the exponential migration ratio model (expressed as eBBO).

{λk=Ieknμk=Eekn1

Seen from Fig. 5(a), when there are fewer species in habitats, the immigration rate decreases rapidly and the emigration rate increases slowly. When the habitat is approaching saturation state, the immigration rate decreases slowly, meanwhile the emigration rate increases rapidly.

3.2. Quadratic migration model

As shown in Fig. 5(b), the immigration rate λk and the emigration rate μk calculated by Eq. (11) are the quadratic function of species diversity k in the habitat at the quadratic migration ratio model (expressed as QBBO).

{λk=I(kn1)2μk=E(kn)2

Seen from Fig. 5(b), the migration characteristic is similar to the exponential migration ratio model. But the difference is that the emigration rate is zero when it has the largest immigration rate, while the emigration rate of the exponential migration model is not zero.

3.3. Linear migration model

As shown in Fig. 5(c), the immigration rate λk and the emigration rate μk calculated by Eq. (12) are the linear function of species diversity k in the habitat at the linear migration ratio model (expressed as LBBO).

{λk=I(1kn)μk=Ekn

Seen from Fig. 5(c), When there is no species in the inhabit, it has the largest immigration rate I and the emigration rate is zero. With the increase of species diversity, the habitat becomes crowded, so the possibility of immigration become smaller and smaller and more and more species move to the adjacent habitat, that is to say the emigration rate increases bigger. Finally, when species reached saturation n, the immigration rate is zero and the emigration rate reaches the maximum value E .

3.4. Cosine migration model

As shown in Fig. 5(d), the immigration rate λk and the emigration rate μk calculated by Eq. (13) are the cosine function of species diversity k in the habitat at the cosine migration ratio model (expressed as cBBO).

{λk=I2(1+cos(kπn))μk=E2(1cos(kπn))

Seen from the Fig. 5(d), when there are fewer or more species in the habitat, the change ratio of immigration rate and emigration rate are relatively stable. While the habitat has a number of species, the change of immigration rate and emigration rate are relatively faster.

3.5. Sine migration model

As shown in Fig. 5(e), the immigration rate λk and the emigration rate μk calculated by Eq. (14) are the sine function of species diversity k in the habitat at the sine migration ratio model (expressed as sBBO).

{λk=I2(1+sin(kπn))μk=E2(1sin(kπn))

Seen from Fig. 5(e), the characteristics of this migration ratio model is contrary to the cosine migration ratio model. When there are fewer or more species in the habitat, the change of immigration and emigration rate are relatively fast, while the habitat has a number of species, the change of immigration rate and emigration rate are relatively stable.

3.6. Migration model with constant emigration ratio

As shown in Fig. 5(f), the immigration rate λk is the linear function of species diversity k in the habitat and the emigration rate μk remains the constant at the migration ratio model with constant emigration ratio (expressed as EBBO), which are calculated by Eq. (15).

{λk=I(1kn)μk=E2

Seen from the Fig. 5(f), when there is no species in the inhabit, it has the largest immigration rate I and emigration rate is E / 2 . With the increase of species diversity, the habitat increasingly becomes crowded, the possibility of immigration becomes smaller, more and more species move to the adjacent inhabits and the emigration rate keeps constant. Finally, when species reach saturation state n, the immigration rate is zero.

3.7. Migration model with constant immigration ratio

As shown in Fig. 5(g), the immigration rate λk remains the constant and the emigration rate μk is the linear function of species diversity k in the habitat at the migration ratio model with constant immigration ratio (expressed as IBBO), which are calculated by Eq. (16).

{λk=I2μk=Ekn

Seen from the Fig. 5(g), when there is no species in the inhabit, the immigration rate I /2 and the emigration rate is 0. With the increase of species diversity, the habitat increasingly becomes crowded, the possibility of immigration remains constant. So the emigration possibility becomes much bigger, namely, more and more species leave to the adjacent habitats. Finally, when species reach saturation state n, the emigration rate is the maximum value E .

4. Simulation Research and Results Analysis

The performance comparison between BBO algorithm and other swarm intelligent optimization has been carried out in literature14. The main purpose of this paper is to verify the impact of various migration ratio models (linear and nonlinear) on the optimizing performance of BBO algorithm. In order to verify the high efficiency of the migration ration strategy, eight benchmark functions are adopted for the optimization experiments, whose function names, expressions and the according domain are listed as follows. The three-dimensional surface figures of these eight functions are shown in Fig. 6(a)-(h).

  • Rastrigin function:

    f1(x)=i=1n(xi210cos(2πxi)+10),15xi15.

  • Schwefel2.22 function:

    f2(x)=i=1D|xi|+i=1D|xi|,10xi10.

  • Griewank function:

    f3(x)=14000(i=1n(xi2))(i=1ncos(xii))+1,600xi600.

  • Ackley function:

    f4(x)=20+e20e(0.21ni=1nxi2)e1ni=1ncos(2πxi),32xi32.

  • Sphere function:

    f5(x)=i=1nxi2,100xi100.

  • Rosenbrock function:

    f6(x)=i=1D1[100(xi+1xi2)2+(1xi)2],2xi2.

  • Step function:

    f7(x)=i=1n(|xi+0.5|)2,100xi100.

  • Schwefel function:

    f8(x)=i=1Dxisin(|xi|),500xi500.

Fig. 6.

Three-dimensional surface figures of eight functions.

The parameters of BBO algorithm are set as follows. The dimension of test functions D =20; The population (habitat) size of the BBO algorithm H = 50; The habitat updated probability is 1; The number of elite individual reservations Keep =2; The migration range of each generation is [0,1]; The probability integral calculation step is 1; The minimum immigration rate I =1; The minimum emigration rate E =1; The mutation rate m =0.005; The evolution generation is 100, independently runs 200 times for every algorithm. The simulation results are shown in Fig. 7(a)-(h).

Fig. 7.

Simulation results of eight functions.

It can be seen from Fig. 7(a)-(h) that the convergence velocity of Ackley function is rather slow, while other functions will gradually reach the stable state with a minimum in the limited iteration number about 35 times or 70 times. Wherein, for Schwefel2.22 function, the curve of IBBO has the fastest convergence speed and the earliest reach the optimal value. Moreover, the curve of LBBO is most obvious in Schwefel function, which can be get stable state soon, the sBBO almost always the first to achieve minimum for most of functions, followed by cBBO. The simulation results show that these migration ratio models make BBO algorithm more quickly and efficient for unconstrained function optimization problems. The comparison of the simulation optimization results under the proposed seven migration ratio models for eight functions are shown in Table 1 and Table 2.

Function Optimal solution
eBBO QBBO LBBO cBBO sBBO EBBO IBBO
f1 11.2 10.51 8.57 10.51 8.92 9.93 10.59
f2 1.8 1.8 1.9 1.6 1.6 1.2 1.3
f3 1.9 1.7 1.86 1.77 1.54 1.85 1.94
f4 3.7 3.86 3.6 3.65 3.43 3.51 3.8
f5 0.25 0.2 0.13 0.22 0.18 0.18 0.21
f6 23.89 21.86 22.78 21.06 21.81 21.85 23.13
f7 62 85 97 44 55 47 75
f8 139.1 132.46 139.93 99.72 77.78 144.24 134.68
Table 1.

Comparison results of the optimal solutions of eight functions.

Function Average solution
eBBO QBBO LBBO cBBO sBBO EBBO IBBO
f1 22.77 16.42 17.83 16.42 13.53 23.51 17.24
f2 4.37 4.86 3.17 4.42 3.14 3.6 3.79
f3 12.88 6.01 12.82 7.67 5.72 6.32 7.41
f4 6.26 6.27 5.33 5.99 6.17 5.46 6.64
f5 2.04 3.05 3.28 1.93 4.1 1.98 4.26
f6 191.66 54.35 51.71 105.07 171.3 215.37 165.35
f7 925.74 772.86 482.08 473.84 545 901.12 699.48
f8 322.68 325.64 453.1 335.83 326.13 356.51 449.34
Table 2.

Comparison results of the average solutions of eight functions

Seen from Table 1 and Table 2, the performance of BBO algorithm is different under the different migration ratio models. In the optimization process of BBO algorithm with seven migration ratio models for eight benchmark functions, the model 3, 4 and 5 all have the minimum either optimal solution or average solution. Wherein, model 5 performs best and model 3 and 4 is followed by it. This show that the BBO algorithm with the migration ratio models close to the natural laws, such as sine, cosine, and so on, outperforms those BBO algorithm with simple linear migration ratio models. Further, according to the simulation results, the different mutation ratio and the number of evolutionary generation can improve the solution fitness to a certain degree, but no obvious advantage on the performance optimization.

5. Conclusions and Future Work

Based on the design principle of BBO algorithm, seven migration ratio models are discussed aiming at the poor convergence and uniformity for the existed function optimization algorithms. Simulation experiments are carried out on the eight benchmark functions to verify the performance of the discussed models. The simulation results show that the seven migration ratio models have a significant impact on the optimization performance of BBO algorithm, in which the sine migration ratio model has the best optimization performance. In the future study, we can use different model such as cosine, sine, linear high order and so on, constitute a different combinations about immigration - emigration rate of cosine/sine - linear respectively four/eight / sixteen times or more high order, on the one hand, which closer to nature discipline, on the other hand, considering the influence degree of the nature of biological migration. Therefore, through the research on the rules of nature evolved over a long period of time, analysis of the mobility model and its different combinations of species of high order hybrid model, it is of great significance for processing optimization problem more unique and effective.

Acknowledgements

This work is partially supported by the National Key Technologies R & D Program of China (Grant No. 2014BAF05B01), the Project by National Natural Science Foundation of China (Grant No. 21576127), the Program for Liaoning Excellent Talents in University (Grant No. LR2014008), the Project by Liaoning Provincial Natural Science Foundation of China (Grant No. 2014020177), the Program for Research Special Foundation of University of Science and Technology of Liaoning (Grant No. 2015TD04) and the Opening Project of National Financial Security and System Equipment Engineering Research Center (Grant No. USTLKEC201401).

References

5.J Kennedy, Particle Swarm Optimization, Encyclopedia of Machine Learning, Springer, U. S., 2010, pp. 760-766.
21.HP Ma, X Li, and SD Lin, Mobility model analysis of biogeography-based optimization algorithm, J. Southeast Univ, Vol. 39, No. S1, 2009, pp. 16-21.
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
9 - 3
Pages
544 - 558
Publication Date
2016/06/01
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.1080/18756891.2016.1175817How to use a DOI?
Copyright
© 2016. the authors. Co-published by Atlantis Press and Taylor & Francis
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

TY  - JOUR
AU  - Jie-sheng Wang
AU  - Jiang-di Song
PY  - 2016
DA  - 2016/06/01
TI  - Migration Ratio Model Analysis of Biogeography-Based Optimization Algorithm and Performance Comparison
JO  - International Journal of Computational Intelligence Systems
SP  - 544
EP  - 558
VL  - 9
IS  - 3
SN  - 1875-6883
UR  - https://doi.org/10.1080/18756891.2016.1175817
DO  - 10.1080/18756891.2016.1175817
ID  - Wang2016
ER  -