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