天牛须搜寻算法(Beetle Antennae Search Algorithm)，缩写为BAS，是一种2017年预印本发表的生物启发式算法。
基本介绍
- 中文名：天牛须搜寻算法
- 外文名：Beetle Antennae Search Algorithm
- 缩写：BAS
算法设计
天牛须搜寻算法是一种生物启发的智慧型最佳化算法，是受到天牛觅食原理启发而开发的算法，其仿生原理如下：
天牛须搜寻的原理：
当天牛觅食时，天牛并不知道实物在哪里，而是根据食物气味的强弱来觅食。天牛有两只长触角，如果左边触角收到的气味强度比右边大，那下一步天牛就往左飞，否则就往右飞，依据这一原理天牛可以找到食物。
天牛须搜寻对我们的启发：
食物的气味就相当于一个函式，这个函式在三维空间每个点值都不同，天牛两个须可以採集自身附近两点的气味值，天牛的目的是找到全局气味值最大的点（即食物所在位置）。仿照天牛的行为，我们设计了该智慧型最佳化算法进行函式最最佳化求解。
天牛觅食的启示天牛在三维空间运动，而天牛须搜寻需要对任意维函式都有效才可以。因而，天牛须搜寻是对天牛生物行为在任意维空间的推广。採用如下模型描述天牛须搜寻算法的寻优策略：
1. 天牛左右两须位于质心两边。
2. 天牛步长step与两须之间距离d0的比值是个固定常数即step=c*d0其中c是常数。即，大天牛（两须距离长）走大步，小天牛走小步。
3. 天牛飞到下一步后，头的朝向是随机的。
简化模型系统建模
- 第一步：对于一个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.
- 第二步：对于待最佳化的价值函式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是归一化函式）
基本步骤就这两步，总结如下：
核心代码几点说明：
1. 核心代码如上，只有4行。
2.实用中可以设定可变步长，由于假设2中我们认为step=c*d0其中c是常数，变步长意味着d0=step/c为变化的。
步长设定
关于变步长，推荐如下两种：
1.每步叠代中採用step=eta*step，其中eta在0,1之间靠近1，通常可取eta=0.95；
2.引入新变数temp和最终解析度step0，temp=eta*temp，step=temp+step0。
关于初始步长：初始步长可以儘可能大，最好与自变数最大长度相当。
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
实测效果
为了验证算法的有效性，使用如下两个典型测试函式验证天牛须搜寻算法的收敛性。
测试1. Michalewicz函式的最小化
测试2. Goldstein-Price函式的约束最小化
