Biogeography-based optimization
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Biogeography-based optimization (BBO) is an evolutionary algorithm (EA) that optimizes a function by stochastically and iteratively improving candidate solutions with regard to a given measure of quality, or fitness function. BBO belongs to the class of metaheuristics since it includes many variations, and since it does not make any assumptions about the problem and can therefore be applied to a wide class of problems.
BBO is typically used to optimize multidimensional real-valued functions, but it does not use the gradient of the function, which means that it does not require the function to be differentiable as required by classic optimization methods such as gradient descent and quasi-newton methods. BBO can therefore be used on discontinuous functions.
BBO optimizes a problem by maintaining a population of candidate solutions, and creating new candidate solutions by combining existing ones according to a simple formula. In this way the objective function is treated as a black box that merely provides a measure of quality given a candidate solution, and the function's gradient is not needed.
Like many EAs, BBO was motivated by a natural process; in particular, BBO was motivated by biogeography, which is the study of the distribution of biological species through time and space. BBO was originally introduced by Dan Simon in 2008.
Biogeography-based optimization (BBO) is an evolutionary algorithm (EA) that optimizes a function by stochastically and iteratively improving candidate solutions with regard to a given measure of quality, or fitness function. BBO belongs to the class of metaheuristics since it includes many variations, and since it does not make any assumptions about the problem and can therefore be applied to a wide class of problems.
BBO is typically used to optimize multidimensional real-valued functions, but it does not use the gradient of the function, which means that it does not require the function to be differentiable as required by classic optimization methods such as gradient descent and quasi-newton methods. BBO can therefore be used on discontinuous functions.
BBO optimizes a problem by maintaining a population of candidate solutions, and creating new candidate solutions by combining existing ones according to a simple formula. In this way the objective function is treated as a black box that merely provides a measure of quality given a candidate solution, and the function's gradient is not needed.
Like many EAs, BBO was motivated by a natural process; in particular, BBO was motivated by biogeography, which is the study of the distribution of biological species through time and space. BBO was originally introduced by Dan Simon in 2008. \text{Prob}(x_j)\text{ is selected for emigration} = \frac{\mu_j}{\sum_{i=1}^N \mu_i} for j=1,\cdots,N , where N is the number of candidate solutions in the population.
For each x_k , set immigration probability \lambda_k = 1 - \mu_k do \{ z_k \} \leftarrow \{ x_k \} For each individual z_k (k=1,\cdots,N) do For each independent variable index s \in [1,n] do Use \lambda_k to probabilistically decide whether to immigrate to z_k If immigrating then Use \{ \mu_i \} to probabilistically select the emigrating individual x_j z_k(s) \leftarrow x_j(s) End if Next independent variable index: s \leftarrow s+1 Probabilistically mutate z_k Next individual: k \leftarrow k+1 \{ x_k \} \leftarrow \{ z_k \} Next generation The initial population of candidate solutions \{ x_k \}_{k=1}^N is usually generated randomly. However, it could be generated in a problem-dependent way based on some reasonable guesses or previously known good solutions to the optimization problem.
The termination criterion is problem-dependent, like in any other EA. In most applications the termination criterion is a generation count limit or a function evaluation limit (that is, how often the objective function is evaluated). \{ z_k \} is a temporary population so that all emigrating variables can originate from the population that is in place at the beginning of the generation, which is \{ x_k \} . where \alpha \in [0, 1] , and \alpha = 0 corresponds to standard migration as shown in the algorithm above.
Blended BBO is based on blended crossover in genetic algorithms, and has been shown to outperform standard BBO. The BBO algorithm presented above is called partial immigration-based BBO because the immigrating candidate solution is selected before the emigrating candidate solution is selected, and migration for each independent variable in the immigrating candidate solution is performed independently of all other independent variables.
Other approaches for selecting the immigrating and emigrating candidate solutions have also been proposed. The migration curves in the above figure are linear, but nonlinear migration curves often give better performance. function BBO % Biogeography-based optimization (BBO) to minimize a continuous function % This program was tested with MATLAB R2012b GenerationLimit = 50; % generation count limit PopulationSize = 50; % population size ProblemDimension = 20; % number of variables in each solution (i.e., problem dimension) MutationProbability = 0.04; % mutation probability per solution per independent variable NumberOfElites = 2; % how many of the best solutions to keep from one generation to the next MinDomain = -2.048; % lower bound of each element of the function domain MaxDomain = +2.048; % upper bound of each element of the function domain % Initialize the population rng(round(sum(100*clock))); % initialize the random number generator x = zeros(PopulationSize, ProblemDimension); % allocate memory for the population for index = 1 : PopulationSize % randomly initialize the population x(index, :) = MinDomain + (MaxDomain - MinDomain) * rand(1, ProblemDimension); end Cost = RosenbrockCost(x); % compute the cost of each individual [x, Cost] = PopulationSort(x, Cost); % sort the population from best to worst MinimumCost = zeros(GenerationLimit, 1); % allocate memory MinimumCost(1) = Cost(1); % save the best cost at each generation in the MinimumCost array disp(['Generation 0 min cost = ', num2str(MinimumCost(1))]); z = zeros(PopulationSize, ProblemDimension); % allocate memory for the temporary population % Compute migration rates, assuming the population is sorted from most fit to least fit mu = (PopulationSize + 1 - (1:PopulationSize)) / (PopulationSize + 1); % emigration rate lambda = 1 - mu; % immigration rate for Generation = 1 : GenerationLimit % Save the best solutions and costs in the elite arrays EliteSolutions = x(1 : NumberOfElites, :); EliteCosts = Cost(1 : NumberOfElites); % Use migration rates to decide how much information to share between solutions for k = 1 : PopulationSize % Probabilistic migration to the k-th solution for j = 1 : ProblemDimension if rand Select) && (SelectIndex
External links
BBO Home Page
Text derived from https://en.wikipedia.org/w/index.php?oldid=1345334821 under CC BY-SA 4.0; modifications have been made.