Page 128 - 《软件学报》2021年第11期

3454 Journal of Software 软件学报 Vol.32, No.11, November 2021

1 相关工作

1.1 BAS优化算法
天牛须搜索算法(BAS)是一种高效的智能优化算法,其生物学原理为:当天牛觅食时,天牛并不知道食物在
哪里,而是利用其两条长须判断食物气味的强弱来觅食.如果左须收到的气味强度比右须大,那么天牛就往左
飞;否则就往右飞.依据这一原理,天牛就可以有效找到食物.将这一原理用数学模型去模拟,食物的气味就相当
于一个函数,天牛两个须可以采集自身附近两点的气味值,天牛的目的是找到全局气味值最大的点.仿照天牛的
行为,可以高效地进行函数寻优.类似于粒子群算法、遗传算法、蚱蜢算法等智能优化算法,天牛须搜索算法
(BAS)可以在不知道函数的具体形式和梯度信息的情况下,自动实现寻优过程.BAS 相对于其他算法而言,由于
单只个体的优势,算法设计复杂度较低,能够在更短的时间内解决优化问题.
算法根据天牛个体的初始位置 x 和随机创建的天牛朝向向量 dir 来计算天牛的左、右须坐标.对于天牛朝
向的随机向量 dir 与左、右须位置坐标 x l 和 x r ,计算公式如下:
dir = rands (,1)n (1)
( ,1))
norm (rands n
⎧ x =+ dir /2
xd ×
⎨ l 0 (2)
xd ×
⎩ x =− 0 dir /2
r
其中,d 0 为常数,表示天牛两须间的距离;n 表示搜索空间的维度;rands(n,1)表示 n 维随机向量;norm 为 2 范数.之
后,根据左、右须的适应度值,更新天牛的位置 x,更新公式如下:
x=x+step×dir×sign(T l −T r ) (3)
其中,sign(⋅)为符号函数;T l 和 T r 分别表示左、右两须的适应度值:T l =S(x l ),T=S(x),S 为待寻优函数;step 表示迭代
步长,用来控制区域搜索能力.初始步长应该较大,以使得天牛初期拥有足够的全局搜索能力.步长的迭代采用
如下策略:
step=step×eta (4)
其中,eta 通常取为 0.95.记 v=step×dir×sign(S l −S r ),称为速度项,则更新公式(3)可写成:
x=x+v (5)
BAS 利用天牛朝向的随机性,得到天牛左、右须的坐标,并计算左、右须的适应度值,以此来更新天牛的下
一步位置.算法为保留最优解和收敛性,通过计算天牛位置的适应度值,选择历史最优值,并将相对应的天牛位
置作为最佳位置.假设天牛历史最优位置为 xbest 和其历史最优值 Sbest,如果历史最优值 Sbest 小于当前适应度
值,则将当前位置和适应度值作为 xbest.Sbest,公式如下(以求待寻优函数 S(x)的最大值为例):
(xbest,Sbest)=(x,T),Sbest<T (6)
其中,T=S(x).
对于一个 n 维空间的优化问题,算法 1 给出了 BAS 算法的实现过程.
算法 1. 天牛须算法(BAS).
1. 随机生成天牛初始位置向量 x,并初始化各参数:步长 step 和步长迭代因子 eta,最大迭代次数 Max_iter.
2. 计算天牛初始适应度值 T 0 =S(x),取天牛最优位置 xbest=x,历史最优值 Sbest=T 0 .
3. 根据公式(1)创建天牛须朝向的随机向量 dir.
4. 根据公式(2)创建个体左须 x l 和右须 x r 空间坐标,并计算左、右两须的适应度值 T l 和 T r .
5. 根据公式(3)更新 x.
6. 计算当前天牛的适应度值 T=S(x).
7. 按照择优操作公式(6)完成历史最优位置 xbest 和历史最优值 Sbest 更新.
8. 按照公式(4)进行步长的更新.
9. 重复步骤 3~步骤 8,进行迭代更新,直到达到设置的最大迭代次数 Max_iter 为止.