BSA

回溯搜索算法与高光反射学习的全局优化

• 概要

概要

这项工作报告了一个新的技术，称为镜面反射学习，以提高优化性能的元启发式方法。镜面反射学习是由物理中的镜面反射现象激发的。请注意，对立学习和镜面反射学习之间有密切的关系。基于对立的学习可以看作是镜面反射学习的一种特殊情况。为了检验镜面反射学习的有效性，利用镜面反射学习对回溯搜索算法进行了改进。利用从著名的CEC 2013、CEC 2014和CEC 2017测试组件中提取的88个测试函数，研究了所提出的带有高光反射学习的回溯搜索算法的性能

基础回溯搜索算法（BSA）

** BSA的优缺点 ** 回溯搜索算法(BSA)是最近报道的一种元启发式方法[7]。BSA具有以下特点:(1)控制参数只有一个，即混合速率;(2)结构简单，易于实现;(3)历史种群与当前种群的微分向量引导BSA的搜索方向。基于这些特点，BSA已被用于解决各类优化问题，如建模海滩重组[8]、短期电价预测[9]、光伏模型[10]的参数识别和铸造热处理收费计划[11]问题。然而，BSA的人口更新策略在很大程度上依赖于历史人口与当前人口的微分向量，无法充分利用人口信息。随着迭代次数的增加，历史人口与现在人口的差异逐渐变小，这将削弱对BSA的探索。因此，一旦BSA陷入一个局部最小值，BSA就很难摆脱它。

基于对立的学习的基本思想可以描述如下。一个解决方案的相反解决方案可能更接近最优解决方案。因此，可以通过同时检验一个解和它的对立解来选择一个更合适的解，从而加速收敛。

基于对位学习的基本思想和物理学中的镜面反射现象，本研究提出了一种新的BSA变体，称为基于镜面反射学习的回溯搜索算法(BSA_SRL)，用于全局优化。在该方法中，引入了一种改进元启发式方法的新技术，即基于镜面反射现象的镜面反射学习。根据基于对立的学习，在一个解决方案和它的对立解决方案之间存在一种一对一的对应关系。而对于镜面反射学习，一个解与其邻域之间存在对应关系。也就是说，通过同时检查这个邻域的一个解和另一个解，可以选择一个更合适的解。显然，基于对立的学习可以看作是镜面反射学习的一个特例。此外，像基于对立的学习，当用于元启发式方法时，镜面反射学习也作为一个变异算子。本工作的主要贡献可以总结如下。

** BSA的基本过程 **

回溯搜索算法的结构非常简单，它由初始化、选择- i、变异、交叉和选择- ii五个部分组成

初始化: 这个阶段是为了初始化种群 X = x 1 , x 2 , . . . , x N X={ x_{1} ,x_{2},...,x_{N}} X=x1​,x2​,...,xN​,和历史种群 X o l d = x o l d , 1 , x o l d , 2 , . . . , x o l d , N X_{old}={ x_{old,1} ,x_{old,2},...,x_{old,N}} Xold​=xold,1​,xold,2​,...,xold,N​.其中N是指种群的大小。X的具体初始化方式如下：
x i , j = l j + ( u j − l j ) ⋅ ξ , i = 1 , 2 , . . . N , j = 1 , 2 , . . . , D x_{i,j}=l_{j} + (u_{j}-l_{j})\cdot\xi,i=1,2,...N,j=1,2,...,D xi,j​=lj​+(uj​−lj​)⋅ξ,i=1,2,...N,j=1,2,...,D
其中 X o l d X_{old} Xold​的初始化方式与X相同。 l l l和 u u u是指种群的上下界。D是指问题的维度。 ξ \xi ξ是【0，1】之间的随机数。
选择-I X o l d X_{old} Xold​起着重要作用，用于指导种群X的搜索方向。 X o l d X_{old} Xold​的更新方式如下：

其中 ρ 1 \rho_{1} ρ1​和 ρ 2 \rho_{2} ρ2​是服从正态分布的[0,1]之间的随机值.

permuting是一个随机变换函数用来对Xold的个体进行随机排序.
**变异:**变异算子产生一组新的基本解 ψ i = ( ψ i , 1 , ψ i , 2 , . . . , ψ i , D ) \psi_i=(\psi_{i,1},\psi_{i,2},...,\psi_{i,D}) ψi​=(ψi,1​,ψi,2​,...,ψi,D​)来更新 x i x_i xi​,具体的更新方式如下：

在基本的回溯搜索算法中，F叫做比例因子，设置为3m，m是服从标准正态分布的随机数
**交叉:**交叉算子是生成最终解 χ i , 1 , χ i , 2 , . . . , χ i , D \chi_{i,1},\chi_{i,2},...,\chi_{i,D} χi,1​,χi,2​,...,χi,D​的算子，它是由一个二进制整数矩阵 E = ( e 1 , e 2 , . . . , e N ) E =( e_1,e_2,...,e_N) E=(e1​,e2​,...,eN​)来执行的。E的大小是X*N具体的更新方式如下：

其中 e i = ( e i , 1 , e i , 2 , . . . , e i , D ) e_i = (e_{i,1},e_{i,2},...,e_{i,D}) ei​=(ei,1​,ei,2​,...,ei,D​)是第i个个体的整值向量。此外，根据回溯搜索算法的定义，将混合速率M_rate设置为1来控制E。
**选择-II:**这个阶段是在 χ i \chi_{i} χi​和 x i x_i xi​之间选择更适合的解进入下一代种群，可以计算

具体代码：

function [BestCost,BestValue,Best]=ROBSA(fhd,nPop,nVar,VarMin,VarMax,MaxIt,X,varargin)
it=0;
FES=0;
FE_best=[];
DIM_RATE=1;
for i=1:nPop
    val_X(i) =  feval(fhd,(X(i,:))',varargin{:}); 
end
historical_X = repmat(VarMin, nPop, 1) + rand(nPop, nVar) .* (repmat(VarMax-VarMin, nPop, 1));
M_X=rand;
while  FES < MaxIt
    it=it+1;
    if rand<rand
        historical_X=X;
    end
    historical_X=historical_X(randperm(nPop),:);
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
    map=ones(nPop,nVar);     %%%更新E，E相当于map
    if rand<rand
        for i=1:nPop
            u=randperm(nVar);
            map(i,u(1:ceil(DIM_RATE*rand*nVar)))=0;
        end
    else
        for i=1:nPop
            map(i,randi(nVar))=0;
        end
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    F=3*randn;%更新F
    for i=1:nPop
        
        Xi=X(i,:)+F.*map(i,:).*(historical_X(i,:)-X(i,:));
        
        Xi = boundConstraint_absorb(Xi, VarMin, VarMax);
        val_Xi =  feval(fhd,(Xi)',varargin{:}); 
        FES = FES+1;
        if val_Xi<val_X(i)
            val_X(i) = val_Xi;
            X(i,:) = Xi;
        end
    end
    [~,index_Best] = sort(val_X);
    BestValue=val_X(index_Best(1));
    Best=X(index_Best(1),:);
    BestCost(it)=BestValue;
end
end

镜面反射学习模型