天牛须搜索算法
天牛须搜索算法(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所示):
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函数
其中 和 ,最小值位于 in 维度。对于二维,BAS算法的性能如Fig.3所示,其获得的Michalewicz函数最小值位于。
一Goldstein-Price函数:
其中。该函数全局最小值点为。BAS算法获得的解为:,,所对应的函数图像如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]
- ↑ Jiang X, Li S. BAS: Beetle Antennae Search Algorithm for Optimization Problems[J]. 2017. [引用日期2018-09-05]
- ↑ https://ww2.mathworks.cn/matlabcentral/fileexchange/64881-bas-beetle-antennae-search-algorithm-for-optimization
- ↑ https://arxiv.org/abs/1711.02395
- ↑ https://arxiv.org/abs/1807.10470
- ↑ https://arxiv.org/abs/1808.00206
- ↑ 王甜甜, 刘强. 基于 BAS-BP 模型的风暴潮灾害损失预测[J]. 2018.
- ↑ Zhu Z, Zhang Z, Man W, et al. A new beetle antennae search algorithm for multi-objective energy management in microgrid[C]//2018 13th IEEE Conference on Industrial Electronics and Applications (ICIEA). IEEE, 2018.
- ↑ Chen T. Beetle Swarm Optimization for Solving Investment Portfolio Problems[J]. The Journal of Engineering, 2018.
- ↑ Dianna Song, Application of Particle Swarm Optimization Based on Beetle Antennae Search Strategy in Wireless Sensor Network Coverage, International Conference on Network, Communication, Computer Engineering (NCCE 2018)
- ↑ 李明富,凌艳,曹勇.基于BAS TSFNN的水质监测方法研究[J].湘潭大学学报自然科版,2018,(3):100~103
- ↑ 基于变步长天牛须搜索算法的空间直线度误差评定 陈君宝 等,工具技术2018年第8期。
- ↑ https://github.com/jywang2016/rBAS