查看“︁天牛须搜索算法”︁的源代码

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

== 算法设计 ==
天牛的觅食原理：

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

对我们的启发：

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

此外，天牛在三维空间运动，而天牛须搜索需要对任意维函数都有效才可以。因而，天牛须搜索是对天牛生物行为在任意维空间的推广。我们采用如下模型([https://baike.baidu.com/pic/%E5%A4%A9%E7%89%9B%E9%A1%BB%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95/22564230/0/adaf2edda3cc7cd9e09701923501213fb90e91c6?fr=lemma&ct=single#aid=0&pic=adaf2edda3cc7cd9e09701923501213fb90e91c6 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是归一化函数）

基本步骤就这两步，总结如下（如[https://baike.baidu.com/pic/%E5%A4%A9%E7%89%9B%E9%A1%BB%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95/22564230/0/fcfaaf51f3deb48f096e9595fc1f3a292df57871?fr=lemma&ct=single#aid=0&pic=fcfaaf51f3deb48f096e9595fc1f3a292df57871 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函数

<math>
 f({x})=\sum_{i=1}^d{sin}(x_i)[ {sin}(\frac{ix_i^2}{\pi})]^{2m},
</math>

其中 <math> m = 10 </math>和 <math> i = 1,2,\cdots </math>，最小值<math> f _ * \approx-1.801 </math>位于<math>{x}_* \approx(2.20319,1.57049)</math> in <math>w= 2 </math>维度。对于二维，BAS算法的性能如[https://baike.baidu.com/pic/%E5%A4%A9%E7%89%9B%E9%A1%BB%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95/22564230/0/4b90f603738da9779079e19abc51f8198618e329?fr=lemma&ct=single#aid=0&pic=4b90f603738da9779079e19abc51f8198618e329 Fig.3]所示，其获得的Michalewicz函数最小值<math> f_  {bst} = - 1.8008 </math>位于<math>  {x} _ { {bst} } = [2.1997,1.5679] ^ {T} </math>。

一Goldstein-Price函数：

<math>
\begin{array}{lcl}
  f({x})&=&[1+(x_1+x_2+1)^2(19-14x_1+3x_1^2-14x_2 \\
            &&+6x_1x_2+3x_2^2)][30+(2x_1-3x_2)^2(18-32x_1\\
            &&+12x_1^2+48x_2-36x_1x_2+27x_2^2)]
\end{array}
</math>

其中<math> { x_i \in [-2, 2], i = 1,2 } </math>。该函数全局最小值点为<math>  {x} ^ * = [0,-1] ^  { T}</math>。BAS算法获得的解为：<math>  {x} _ { {bst}} = [0.0052507,-0.99933] ^{T} </math>，<math> f_{bst} = 3.0064 </math>,所对应的函数图像如[https://baike.baidu.com/pic/%E5%A4%A9%E7%89%9B%E9%A1%BB%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95/22564230/0/d1a20cf431adcbef622f18b7a0af2edda3cc9f63?fr=lemma&ct=single#aid=0&pic=d1a20cf431adcbef622f18b7a0af2edda3cc9f63 Fig.4]所示。

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

== 天牛须搜索算法的优点 ==
1.运算量非常小，收敛非常快；

2.具有全局寻优能力；

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

== 已有成果 ==
1.BAS-WPT：Beetle Antennae Search without Parameter Tuning (BAS-WPT) for Multi-objective Optimizations<sup>[3]</sup>；

2. BSAS: Beetle Swarm Antennae Search Algorithm for Optimization Problems<sup>[4]</sup>；

3.BSO: Beetle Swarm Optimization Algorithm: Theory and Application<sup>[5]</sup>；

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

5.binary-BAS；

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

应用:

1.智能电网<sup>[7]</sup>;

2.组合投资分析<sup>[8]</sup>；

3.传感器网络覆盖<sup>[9]</sup>；

4.水质监测<sup>[10]</sup>；

5.直线度公差评定<sup>[11]</sup>；

6.多杆机构优化问题；

专利：

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

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

软件

1.基于matlab的基本bas算法<sup>[2]</sup>

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

==参考文献==
{{reflist}}<ref>Jiang X, Li S. BAS: Beetle Antennae Search Algorithm for Optimization Problems[J].  2017. [引用日期2018-09-05]</ref>

<ref>https://ww2.mathworks.cn/matlabcentral/fileexchange/64881-bas-beetle-antennae-search-algorithm-for-optimization</ref>

<ref><nowiki>https://arxiv.org/abs/1711.02395</nowiki></ref>

<ref>https://arxiv.org/abs/1807.10470</ref>

<ref><nowiki>https://arxiv.org/abs/1808.00206</nowiki></ref>

<ref>王甜甜, 刘强. 基于 BAS-BP 模型的风暴潮灾害损失预测[J]. 2018.</ref>

<ref>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.</ref>

<ref>Chen T. Beetle Swarm Optimization for Solving Investment Portfolio Problems[J]. The Journal of Engineering, 2018.</ref>

<ref>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)</ref>

<ref>李明富,凌艳,曹勇.基于BAS TSFNN的水质监测方法研究[J].湘潭大学学报自然科版,2018,(3):100~103</ref>

<ref>基于变步长天牛须搜索算法的空间直线度误差评定 陈君宝 等，工具技术2018年第8期。</ref>

<ref>https://github.com/jywang2016/rBAS</ref>

[[Category:算法]]
[[Category:人工智能]]