天牛须算法

Posted on | In

一、介绍

天牛须算法（Beetle Antennae search algorithm, BAS）是由 Jiang 等人于2017年提出的一种智能优化算法，该算法模拟了天牛寻食物时的搜索方式，是一种单体搜索算法，该算法原理简单、参数少、计算量少，在处理低维优化目标时具有优势。

天牛在觅食过程中，会被食物的气味吸引。天牛通过其两只触角对空气中的食物气味进行感知，由于食物距离两只触角的距离远近不同，因此触角所感知的气味浓度也有所差异。当食物处于天牛左侧时，左侧触角感知的气味浓度强于右侧触角感知的气味浓度，因此天牛可以根据两只触角所感知的浓度差，向着浓度强的一侧随机前进。多次迭代后最终找到食物的位置。

二、原理

介绍算法前可以先设定一些概念：

在 n 维空间中天牛的位置为：

天牛左右两只触角的位置：

其中 $l$ 表示天牛质心与触须的距离，$\bar{d}$ 表示随机单位向量，需要对单位向量进行归一化操作：

由于两只触角获得两个位置的目标函数信息，因此需要对两个位置择优前进：

其中 $t$ 表示迭代次数，$f$ 函数为目标函数，$\delta_t$ 表示第 $t$ 次探索时的步长，$sign$ 为符号函数。通常在每次迭代过程中步长需要不断变小，因此可以将其设置为：

其中 $\eta$ 表示每次迭代步长缩短的速度，通常设定为 0.95 。

三、参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function bas()
    clear all;
    % 初始化部分
    eta=0.95;
    c=1;% 步进和d0之间的比率
    step=5;% 初始步骤设置为最大输入范围
    n=100;% 迭代器
    k=4;% 空间维数
    x=rands(k,1);% 随机位置
    xbest=x;
    fbest=f(xbest);% f为目标函数
    fbest_store=fbest;
    x_store=[0;x;fbest];% 用于存储路径
    display(['0:','xbest=[',num2str(xbest'),'],fbest=',num2str(fbest)]);
    % 迭代部分
    for i=1:n
        d0=step/c;% d0表示质点与须之间的长度
        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);% 判优
        flag=f(x);
        if flag>fbest
            xbest=x;
            fbest=flag;
        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('maximum value');
end

此代码为最大值模板，若要改为最小值，需要改变下面的代码：

1
2
3
x=x-step*dir*sign(fleft-fright);% 第24行，将加号改为减号

if flag<fbest% 第26行，将大于号改为小于号