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

FeastSC

今天为各位讲解生物地理学优化算法（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维适宜度变量组成，其向量如下：



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


（2）变异算子
依次遍历栖息地i中的每一维变量Hi(j)，即 。在每一次遍历过程中，先根据迁入率  和迁出率计算变异概率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,'first');
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(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
   
end

%% Results

figure;
%plot(BestCost,'LineWidth',2);
semilogy(BestCost,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');
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代码

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