天牛须搜索算法

天牛须搜索算法（Beetle Antennae Search Algorithm, BAS） ^[1] ， 一种生物启发式智能优化算法，是受到天牛觅食原理启发而开发的算法。

算法设计

天牛的觅食原理：

当天牛觅食时，天牛并不知道实物在哪里，而是根据食物气味的强弱来觅食。天牛有两只长触角（天牛须），如果左边触角收到的气味强度比右边大，那下一步天牛就往左飞，否则就往右飞，依据这一原理天牛可以找到食物。

对我们的启发：

食物的气味就相当于一个函数，这个函数在三维空间每个点值都不同，天牛两个须可以采集自身附近两点的气味值，天牛的目的是找到全局气味值最大的点（即食物所在位置）。仿照天牛的行为，我们设计了BAS算法进行函数最优化求解。

此外，天牛在三维空间运动，而天牛须搜索需要对任意维函数都有效才可以。因而，天牛须搜索是对天牛生物行为在任意维空间的推广。我们采用如下模型(Fig.1)描述天牛须搜索算法的寻优策略：

1. 天牛左右两须位于质心两边。

2. 天牛步长step与两须之间距离d0的比值是个固定常数即step=c*d0，其中c是常数。即，大天牛（两须距离长）走大步，小天牛走小步。

3. 天牛飞到下一步后，头的朝向是随机的。

系统建模

1.第一步：对于一个n维空间的优化问题，我们用xl表示左须坐标，xr表示右须坐标，x表示质心坐标，用d0表示两须之间距离。根据假设3，天牛头朝向任意，因而从天牛右须指向左须的向量的朝向也是任意的，所以可以产生一个随机向量dir=rands(n,1)来表示它。对此归一化：dir=dir/norm(dir); 我们这样可以得到xl-xr=d0*dir；显然， xl，xr还可以表示成质心的表达式：xl=x+d0*dir/2; xr=x-d0*dir/2。

2.第二步：对于待优化函数f，求取左右两须的值： fleft=f(xl); fright=f(xr); 判断两个值大小：

如果fleft<fright,为了探寻f的最小值，则天牛向着左须方向行进距离step，即x=x+step*normal(xl-xr)；

如果fleft>fright,为了探寻f的最小值，则天牛向着右须方向行进距离step，即x=x-step*normal(xl-xr)；

如上两种情况可以采用符号函数sign统一写成： x=x-step*normal(xl-xr) *sign(fleft-fright)=x-step*dir *sign(fleft-fright).（注：其中normal是归一化函数）

基本步骤就这两步，总结如下（如Fig.2所示）：

Matlab 程序

function bas()

clear all;

close all

%%%%%%%%%%%%%%

%初始化

%%%%%%%%%%%%%%

eta=0.95;

c=5;%ratio between step and d0

step=1;%initial step set as thelargest input range

n=100;%iterations

k=20;%space dimension

x=rands(k,1);%intial value

xbest=x;fbest=f(xbest);

fbest_store=fbest;x_store=[0;x;fbest];

display(['0:','xbest=[',num2str(xbest'),'],fbest=',num2str(fbest)])

%%%%%%%%%%%%%%

%迭代部分

%%%%%%%%%%%%%%

for i=1:n

d0=step/c;dir=rands(k,1);dir=dir/(eps+norm(dir));

xleft=x+dir*d0;fleft=f(xleft);

xright=x-dir*d0;fright=f(xright);

x=x-step*dir*sign(fleft-fright);f=f(x);

if f<fbest

xbest=x;fbest=f;

end

x_store=cat(2,x_store,[i;x;f]);fbest_store=[fbest_store;fbest];

display([num2str(i),':xbest=[',num2str(xbest'),'],fbest=',num2str(fbest)])

step=step*eta;

end

%%%%%%%%%%%%%%

%数据显示部分

%%%%%%%%%%%%%%

figure(1),clf(1),

plot(x_store(1,:),x_store(end,:); 'r-o')hold on,

plot(x_store(1,:),fbest_store,'b-.');xlabel('iteration');ylabel('minimum value')

end

%%%%%%%%%%%%%

%被优化的函数，这部分需要换用你自己的被优化函数

%%%%%%%%%%%%%

function y=f(x)

y=norm(x);

end

实测效果

为了验证算法的有效性，使用如下两个典型测试函数验证天牛须搜索算法的收敛性。

一Michalewicz函数

$f({x})=\sum _{i=1}^{d}{sin}(x_{i})[{sin}({\frac {ix_{i}^{2}}{\pi }})]^{2m},$

其中 $m=10$和 $i=1,2,\cdots$，最小值$f_{*}\approx -1.801$位于${x}_{*}\approx (2.20319,1.57049)$ in $w=2$维度。对于二维，BAS算法的性能如Fig.3所示，其获得的Michalewicz函数最小值$f_{bst}=-1.8008$位于${x}_{bst}=[2.1997,1.5679]^{T}$。

一Goldstein-Price函数：

${\begin{array}{lcl}f({x})&=&[1+(x_{1}+x_{2}+1)^{2}(19-14x_{1}+3x_{1}^{2}-14x_{2}\\&&+6x_{1}x_{2}+3x_{2}^{2})][30+(2x_{1}-3x_{2})^{2}(18-32x_{1}\\&&+12x_{1}^{2}+48x_{2}-36x_{1}x_{2}+27x_{2}^{2})]\end{array}}$

其中${x_{i}\in [-2,2],i=1,2}$。该函数全局最小值点为${x}^{*}=[0,-1]^{T}$。BAS算法获得的解为：${x}_{bst}=[0.0052507,-0.99933]^{T}$，$f_{bst}=3.0064$,所对应的函数图像如Fig.4所示。

仿真结果充分证实了所提出的BAS算法的有效性。上述两个示例的Matlab代码可在^[2] 中找到。

天牛须搜索算法的优点

1.运算量非常小，收敛非常快；

2.具有全局寻优能力；

3.代码非常短，容易实现；

已有成果

1.BAS-WPT：Beetle Antennae Search without Parameter Tuning (BAS-WPT) for Multi-objective Optimizations^[3]；

2. BSAS: Beetle Swarm Antennae Search Algorithm for Optimization Problems^[4]；

3.BSO: Beetle Swarm Optimization Algorithm: Theory and Application^[5]；

4.基于 BAS-BP 模型的风暴潮灾害损失预测^[6]；

5.binary-BAS；

6.二阶BAS: Beetle Antennae Search Algorithm Based Dynamic Optimization；

应用:

1.智能电网^[7];

2.组合投资分析^[8]；

3.传感器网络覆盖^[9]；

4.水质监测^[10]；

5.直线度公差评定^[11]；

6.多杆机构优化问题；

专利：

1.基于天牛须搜索的SDN网络中多目标组播路由路径构建方法，专利申请号：201711267401.3，申请人西南交通大学。

2.基于天牛须搜索算法的空间直线度误差评定方法-CN201810036579.5，申请人： 湖北汽车工业学院。

软件

1.基于matlab的基本bas算法^[2]

2.基于R的一个各种bas改进型的函数库^[12]