-
天牛須搜索算法
鎖定
- 中文名
- 天牛須搜索算法
- 外文名
- Beetle Antennae Search Algorithm
- 縮 寫
- BAS
天牛須搜索算法算法設計
天牛須搜索的原理：
當天牛覓食時，天牛並不知道食物在哪裏，而是根據食物氣味的強弱來覓食。天牛有兩隻長觸角，如果左邊觸角收到的氣味強度比右邊大，那下一步天牛就往左飛，否則就往右飛，依據這一原理天牛可以找到食物。
天牛須搜索對我們的啓發：
食物的氣味就相當於一個函數，這個函數在三維空間每個點值都不同，天牛兩個須可以採集自身附近兩點的氣味值，天牛的目的是找到全局氣味值最大的點（即食物所在位置）。仿照天牛的行為，我們設計了該智能優化算法進行函數最優化求解。
天牛覓食的啓示
天牛在三維空間運動，而天牛須搜索需要對任意維函數都有效才可以。因而，天牛須搜索是對天牛生物行為在任意維空間的推廣。採用如下模型描述天牛須搜索算法的尋優策略：
1. 天牛左右兩須位於質心兩邊。
2. 天牛步長step與兩須之間距離d0的比值是個固定常數即step=c*d0其中c是常數。即，大天牛（兩須距離長）走大步，小天牛走小步。
3. 天牛飛到下一步後，頭的朝向是隨機的。
簡化模型
天牛須搜索算法系統建模
- 第一步：對於一個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.
- 第二步：對於待優化的價值函數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是歸一化函數）
基本步驟就這兩步，總結如下：
核心代碼
幾點説明：
1. 核心代碼如上，只有4行。
2.實用中可以設置可變步長，由於假設2中我們認為step=c*d0其中c是常數，變步長意味着d0=step/c為變化的。
天牛須搜索算法步長設定
關於變步長，推薦如下兩種：
1.每步迭代中採用step=eta*step，其中eta在0,1之間靠近1，通常可取eta=0.95；
2.引入新變量temp和最終分辨率step0，temp=eta*temp，step=temp+step0。
關於初始步長：初始步長可以儘可能大，最好與自變量最大長度相當。
天牛須搜索算法程序
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
天牛須搜索算法實測效果
為了驗證算法的有效性，使用如下兩個典型測試函數驗證天牛須搜索算法的收斂性。
測試1. Michalewicz函數的最小化
測試2. Goldstein-Price函數的約束最小化
- 參考資料
-
- 1. BAS: Beetle Antennae Search Algorithm for Optimization Problems ．arxiv.org．2017-10-30[引用日期2018-05-05]
- 2. BAS: Beetle Antennae Search Algorithm for Optimization Problems ．International Journal of Robotics and Control．2018-04[引用日期2018-05-05]
- 3. 天牛須搜索算法Matlab程序 ．MathWorks．2017-10-31[引用日期2018-05-12]
