跳转到内容

天牛须搜索算法

来自维基学院

天牛须搜索算法(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函数

其中 ,最小值位于 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]

参考文献

[编辑 | 编辑源代码]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

  1. Jiang X, Li S. BAS: Beetle Antennae Search Algorithm for Optimization Problems[J]. 2017. [引用日期2018-09-05]
  2. https://ww2.mathworks.cn/matlabcentral/fileexchange/64881-bas-beetle-antennae-search-algorithm-for-optimization
  3. https://arxiv.org/abs/1711.02395
  4. https://arxiv.org/abs/1807.10470
  5. https://arxiv.org/abs/1808.00206
  6. 王甜甜, 刘强. 基于 BAS-BP 模型的风暴潮灾害损失预测[J]. 2018.
  7. 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.
  8. Chen T. Beetle Swarm Optimization for Solving Investment Portfolio Problems[J]. The Journal of Engineering, 2018.
  9. 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)
  10. 李明富,凌艳,曹勇.基于BAS TSFNN的水质监测方法研究[J].湘潭大学学报自然科版,2018,(3):100~103
  11. 基于变步长天牛须搜索算法的空间直线度误差评定 陈君宝 等,工具技术2018年第8期。
  12. https://github.com/jywang2016/rBAS