优化算法 | 生物地理学优化算法（附MATLAB代码）

FeastSC · 发表于 2022-1-6 10:34

今天为各位讲解生物地理学优化算法（BBO，Biogeography-Based Optimization）。BBO算法源于物种在栖息地之间迁移过程中蕴含的优化思想。BBO算法与遗传算法、蚁群算法、粒子群算法等群智能优化算法相比，其特殊之处在于：1）不涉及繁殖或产生下一代；2）依靠迁移概率调整每一代解；3）采用根据不同栖息地的种群数量选择不同操作强度的生物激励机制。
▎生物地理学优化算法基本思想
BBO算法是2008年Simon教授提出的一种群智能优化算法。Simon教授受生物地理学启发，通过设计迁移算子和变异算子，分别模仿生物地理栖息地之间的物种迁移和变异过程。
首先提出一个问题，物种为什么需要迁移？
答：一般情况为原来的栖息地发生了变化，导致物种不适应原来的栖息地了，进而迁移至其它栖息地。
那么如何选择新的栖息地呢？
常规思路肯定是选择最“好”的栖息地，只不过栖息地的“好与坏”是通过适宜度指数(HSI，Habitat Suitability Index）来进行评价的。与HSI有关系的特征包括降雨量、植被的多样性、地质的多样性和气候等因素，这些特征变量形成一个描述栖息地适宜度的向量SIV(SIV，Suitable Index Vector)，其中的每个适宜度变量被称为SIVs(Suitable Index Variables)。
从上述描述中可以看出，物种喜欢生存在高HSI的栖息地。这就导致了高HSI栖息地的物种数量较多，生存空间饱和，竞争激烈，导致大量物种迁出到相邻栖息地，少量的物种迁入；而低HSI栖息地由于物种稀少，而有较多的物种迁入，较少的物种迁出。
进一步分析，可以发现使用BBO算法求解优化问题主要依赖3方面：
（1）SIV对应优化问题的解，HSI是SIV优劣的度量值，对应优化问题的适应度函数。好的解决方案对应具有较高HSI值的栖息地，反之亦然。
（2）栖息地的迁入和迁出机制对应优化算法中的信息交互机制。高HSI的解决方案以一定的迁出率进行相应操作，将信息共享给低HSI解决方案。低HSI解决方案从高HSI的解决方案接受许多新的特征，这些额外的新特征可以提高低HSI解决方案的质量。若栖息地较高HIS使得该栖息地种群数量增多，则调低迁入率、调高迁出率。
（3）BBO算法能够根据栖息地容纳种群数量的不同，计算相应的突变率，对栖息地进行突变操作，使得算法具备较强的自适应能力。
▎生物地理学优化算法的数学描述
假设在BBO算法中，栖息地数目为n，即算法的种群数目为n，Hi表示第i个栖息地。每个栖息地由M维适宜度变量组成，其向量如下：

$x_{i}=\left(x_{i 1}, x_{i 2}, \cdots, x_{i M}\right), i=1,2, \cdots, n$

$x_i$ 代表优化问题在M维搜索空间中潜在的解。栖息地i的适宜度可以通过f(xi)进行度量。栖息地i的参数还包括其迁入率和迁出率。
BBO算法中最核心的2个算子分别为迁移算子和变异算子，因此，接下来分别介绍这2个算子。
（1）迁移算子
首先根据栖息地Hi的迁入率决定该栖息地的每个分量是否需要修改；若需要修改，然后根据迁出率选择被迁入的栖息地Hj；最后将栖息地Hj的 SIV（即σ）替换到栖息地Hi的SIV（即σ）。

（2）变异算子
依次遍历栖息地i中的每一维变量Hi(j)，即 $x_{ij}$ 。在每一次遍历过程中，先根据迁入率  和迁出率计算变异概率Pi；根据变异概率Pi选择Hi(j)；如果Hi(j)被选择，则用一个随机产生的SIV替换Hi(j)。

▎BBO算法MATLAB代码
（1）目标函数
function z=Sphere(x)
z=sum(x.^2);
end
（2）轮盘赌函数
function j=RouletteWheelSelection(P)
r=rand;
C=cumsum(P);
j=find(r<=C,1,&#39;first&#39;);
end
（3）主函数
clc;
clear;
close all;

%% Problem Definition

CostFunction=@(x) Sphere(x);       % Cost Function

nVar=5;          % Number of Decision Variables

VarSize=[1 nVar]; % Decision Variables Matrix Size

VarMin=-10;       % Decision Variables Lower Bound
VarMax= 10;       % Decision Variables Upper Bound

%% BBO Parameters

MaxIt=1000;       % Maximum Number of Iterations

nPop=50;          % Number of Habitats (Population Size)

KeepRate=0.2;                % Keep Rate
nKeep=round(KeepRate*nPop);    % Number of Kept Habitats

nNew=nPop-nKeep;             % Number of New Habitats

% Migration Rates
mu=linspace(1,0,nPop);       % Emmigration Rates
lambda=1-mu;                   % Immigration Rates

alpha=0.9;

pMutation=0.1;

sigma=0.02*(VarMax-VarMin);

%% Initialization

% Empty Habitat
habitat.Position=[];
habitat.Cost=[];

% Create Habitats Array
pop=repmat(habitat,nPop,1);

% Initialize Habitats
for i=1:nPop
pop(i).Position=unifrnd(VarMin,VarMax,VarSize);
pop(i).Cost=CostFunction(pop(i).Position);
end

% Sort Population
[~, SortOrder]=sort([pop.Cost]);
pop=pop(SortOrder);

% Best Solution Ever Found
BestSol=pop(1);

% Array to Hold Best Costs
BestCost=zeros(MaxIt,1);

%% BBO Main Loop

for it=1:MaxIt

newpop=pop;
for i=1:nPop
      for k=1:nVar
         % Migration
         if rand<=lambda(i)
            % Emmigration Probabilities
            EP=mu;
            EP(i)=0;
            EP=EP/sum(EP);

            % Select Source Habitat
            j=RouletteWheelSelection(EP);

            % Migration
            newpop(i).Position(k)=pop(i).Position(k) ...
                  +alpha*(pop(j).Position(k)-pop(i).Position(k));

         end

         % Mutation
         if rand<=pMutation
            newpop(i).Position(k)=newpop(i).Position(k)+sigma*randn;
         end
      end

      % Apply Lower and Upper Bound Limits
      newpop(i).Position = max(newpop(i).Position, VarMin);
      newpop(i).Position = min(newpop(i).Position, VarMax);

      % Evaluation
      newpop(i).Cost=CostFunction(newpop(i).Position);
end

% Sort New Population
[~, SortOrder]=sort([newpop.Cost]);
newpop=newpop(SortOrder);

% Select Next Iteration Population
pop=[pop(1:nKeep)
      newpop(1:nNew)];

% Sort Population
[~, SortOrder]=sort([pop.Cost]);
pop=pop(SortOrder);

% Update Best Solution Ever Found
BestSol=pop(1);

% Store Best Cost Ever Found
BestCost(it)=BestSol.Cost;

% Show Iteration Information
disp([&#39;Iteration &#39; num2str(it) &#39;: Best Cost = &#39; num2str(BestCost(it))]);

end

%% Results

figure;
%plot(BestCost,&#39;LineWidth&#39;,2);
semilogy(BestCost,&#39;LineWidth&#39;,2);
xlabel(&#39;Iteration&#39;);
ylabel(&#39;Best Cost&#39;);
grid on;▎参考文献
[1]Simon D. Biogeography-based optimization[J]. IEEE transactions on evolutionary computation, 2008, 12(6): 702-713.
[2]王存睿, 王楠楠, 段晓东,等. 生物地理学优化算法综述[J]. 计算机科学, 2010, 37(7):5.
[3]https://yarpiz.com/239/ypea113-biogeography-based-optimization.
▎生物地理学优化算法代码获取方式
优化算法 | 生物地理学优化算法（附MATLAB代码）

咱们下期再见
▎近期你可能错过了的好文章：
新书上架 | 《MATLAB智能优化算法：从写代码到算法思想》
优化算法 | 灰狼优化算法（文末有福利）
优化算法 | 鲸鱼优化算法
遗传算法（GA）求解带时间窗的车辆路径（VRPTW）问题MATLAB代码
粒子群优化算法（PSO）求解带时间窗的车辆路径问题（VRPTW）MATLAB代码

▎作者新书购买链接
京东自营购买链接
当当自营购买链接

		自动登录	找回密码
密码			立即注册

优化算法 | 生物地理学优化算法（附MATLAB代码）

本帖子中包含更多资源