Biogeography-Based Optimization (BBO) in MATLAB

Biogeography-Based Optimization (BBO) is an evolutionary algorithm and metaheuristic inspired by biogeography: speciation (the evolution of new species), the migration of species between islands, and the extinction of species. Dan Simon proposed it in 2008 in this paper (opens in a new tab).

The algorithm is based on a mathematical model of species migration between habitats. The optimizer turns the migration analogy into rates for exchanging the variables of candidate solutions. The suitability of a habitat is stored as the Habitat Suitability Index, which is defined from the objective function of the problem being solved. A more detailed description is in the Wikipedia article on biogeography-based optimization (opens in a new tab).

How BBO works

Each habitat is a candidate solution, and each decision variable is one feature of the habitat. A good habitat (low cost) has many species. It shares its features with others easily and accepts few new ones. A poor habitat has few species. It accepts new features easily and shares few.

BBO turns this into two rates for each habitat $i$:

• the emigration rate $\mu_i$, the chance that habitat $i$ shares a feature with another habitat,
• the immigration rate $\lambda_i$, the chance that a feature of habitat $i$ is replaced with information from another habitat.

With the population sorted from best to worst, the simplest choice is a linear model, in which $\mu_i$ falls from 1 for the best habitat to 0 for the worst, and

Migration

For each habitat $i$ and each variable $k$, migration happens with probability $\lambda_i$. A source habitat $j \neq i$ is then chosen with a probability proportional to its emigration rate $\mu_j$, so good habitats are chosen more often. In the original BBO, the feature is copied from $j$ to $i$. The code in this post uses a blended migration, which moves the feature only part of the way:

With $\alpha = 1$ this is the original copy. The code uses $\alpha = 0.9$.

Mutation and elitism

After migration, each variable is mutated with a small probability by adding Gaussian noise. Then the best habitats of the old population are kept, and the rest of the new population is filled with the best new habitats. This elitism keeps the best solutions found so far.

Implementation in MATLAB

This post shares a structured, open-source MATLAB implementation of BBO. If you know MATLAB, you will find it easy to use the source code in your research and projects.

What is in the download

The BBO folder holds four files:

• bbo.m: the BBO script, with the problem definition, the parameters, the main loop and the results.
• RouletteWheelSelection.m: picks the source habitat in proportion to the emigration rates.
• Sphere.m: the sample cost function, $f(x) = \sum_{i=1}^{n} x_i^2$.
• main.m: a one line entry point that runs bbo.m.

To run the code, open the BBO folder in MATLAB and run main.m. The program prints the best cost of every iteration and then plots the best cost against the iteration number on a logarithmic scale.

The script creates the first habitats with unifrnd, a function of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

Parameters in the code

With these values, the 10 best habitats of the old population and the 40 best new habitats form the next population. Positions outside the bounds are set back to the nearest bound.

To solve your own problem, write a cost function that takes a row vector and returns a number, and set CostFunction, nVar, VarMin and VarMax in the problem definition section of bbo.m.

Check the result

For the Sphere example, a low cost should correspond to coordinates near the origin and within the bounds. Keep the retained-elite count and new-population count consistent when changing nPop or KeepRate. The linear migration rates need a population with multiple members. Compare several runs to assess whether changing migration or mutation gives a consistent improvement.

Related posts

• YPEA is a MATLAB toolbox that includes BBO and 14 other algorithms that share one problem definition.
• Particle Swarm Optimization in MATLAB is another population based method with the same code structure.

Mostapha Kalami Heris, Biogeography-Based Optimization (BBO) in MATLAB (YPEA113), Yarpiz, 2015. https://yarpiz.com/biogeography-based-optimization-ypea113

@misc{yarpiz-ypea113,
  author = {{Mostapha Kalami Heris}},
  title = {{Biogeography-Based Optimization (BBO) in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA113},
  url = {https://yarpiz.com/biogeography-based-optimization-ypea113}
}