天牛須搜索算法

天牛須搜索算法（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]