天牛須搜索算法

來自維基學院

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