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

霍星 等:改进的元启发式优化算法及其在图像分割中的应用 3457

取值线性递减,速度项 v′的取值也在随着迭代逐渐减小.
将速度项 v′通过 Sigmoid 函数转变为位置项 x′中每位取 1 的条件,得到天牛位置更新公式如下所示:
if (rand ⋅< Sig ( ))v′ then x′ = 1 ⎫
( )
d d ⎬ (16)
else x′ = d 0 d ∈ {0,1,2,..., } ⎭
m
其中,Sig(⋅)为 Sigmoid 函数,rand(⋅)为[0,1]间的随机数, v′ 是第 d 维的速度项, x′ 是第 d 维的位置坐标值.
d
d
根据文献[9]中的分析,速度项经 Sigmoid 函数处理后,其二进制位置坐标 x′每一位的变化概率随着速度项
每一位的值的变化关系呈类似于正态分布的曲线.因此,随着速度项 v′的每一位逐渐接近于 0,天牛二进制位置
坐标 x′的位发生改变的概率在逐渐增大,即在迭代后期将有更强的全局搜索能力,这为迭代后期避免陷入局部
收敛提供了保证.为避免天牛速度项 v′经 Sigmoid 函数转化为概率时太靠近 0 或 1 而导致全局搜索能力下降,
设定天牛的最大速度 v max 和最小速度 v min ,即 v′∈[v min ,v max ].若速度超过边界,则取相应的边界值.
定义左、右须的速度项为
v′ = ⎧ d × dir /2
⎨ l 0 (17)
⎩ v′ =− d × dir /2
r
0
其中,d 0 为常数.BBAS 算法步骤见算法 3.
算法 3. 二进制离散天牛须算法(BBAS).
1. 随机生成天牛二进制位置 x′和速度 v′,并初始化各参数.
2. 计算初始适应度值 T′,取历史最优位置:xbest′=x′和历史最优值 Sbest′ = T′ .
0
0
3. 根据公式(17)生成左、右须的速度项 v′ 和 v′ .
l
r
4. 根据公式(16)进行天牛左、右须 x′ 与 x′ 的更新.
l
r
5. 根据公式(14)计算速度项 v′.
6. 对速度项 v′利用公式(16)完成天牛位置 x′的更新.
7. 根据择优操作公式(6)完成历史最优位置 xbest′和历史最优值 Sbest′的更新.
8. 更新步长 step′.
9. 重复步骤 3~步骤 8,直到终止条件达到.
10. 返回天牛历史最优位置 xbest′和历史最优位置 Sbest′.
2.2 一种基于BBAS优化的改进的BAS算法(NBAS)
对以上 BBAS 算法分析可知,BBAS 不太可能收敛于全局最优值.因为随着速度项越接近 0,经 Sigmoid 函数
计算后的值越来越大,即二进制位发生改变的概率越来越大.此时,搜索具有更强的随机性,全局探测能力也更
强,缺乏局部探索性.因此,BBAS 算法是缺少局部搜索性的全局随机搜索性算法.
单纯的 BBAS 算法运行到最后时,更具有随机性,这是一种全局搜索能力.考虑到原始 BAS 易陷入局部收
敛,且用二进制方法将其离散化后的 BBAS 因全局搜索性过强而无法全局收敛的问题,本文将原始 BAS 与
BBAS 结合起来,利用 BBAS 辅助原始 BAS 算法,提出一种新的天牛须搜索算法(NBAS).NBAS 算法将解空间分
为并行的两部分:BAS 算法个体和 NBAS 算法个体.具体地:横向上,主个体利用原始 BAS 算法进行寻优搜索;纵
向上,辅个体利用 BBAS 算法较强的局部全局寻优能力,对主个体和辅个体进行比较选择,促进主个体的全局寻
优能力.对于主个体 x 和其适应度值 T 以及辅个体 x′和其适应度值 T′,公式如下(以求最大值为例):
(x,T)=(x′,T′),T<T′ (18)
如此,将纵向二进制全局进化和横向 BAS 搜索动态结合,提高了原 BAS 算法的求解精度和收敛速度.算法 4
给出了 NBAS 算法的实现步骤.
算法 4. 二进制离散天牛须算法优化的改进的天牛须算法(NBAS).
1. BAS 主个体初始位置和参数初始化.随机生成主个体位置 x,初始化 BAS 中各参数,并计算主个体的初
始适应度值 T 0 .
2. BBAS 辅个体位置和参数初始化.随机生成辅个体二进制位置 x′和速度项 v′,初始化 BBAS 中各参数,