张啸宇, 方忠庆, 杜 义, 孔维宾, 王玉婷, 程子耀

(盐城工学院信息工程学院, 江苏 盐城 224051)

0 引言(Introduction)

元启发式算法是一类独立于问题的优化算法,能够有效探索一个搜索空间并找到全局最优解。这类算法主要通过模拟自然界优胜劣汰的规律以及生物行为,实现种群的整体进步,最终求解最优解。典型算法有遗传算法(GA)[1]、差分进化算法(DE)[2]、粒子群算法(PSO)[3]、灰狼算法(GWO)[4]、鲸鱼优化算法(WOA)[5]、金豺狼优化算法(GJO)[6]等。

按阈值对图像分割是一种常用的图像分割方法,目前国内外已经有很多学者将元启发式算法用于图像的阈值分割优化中。KHAIRUZZAMAN等[7]将灰狼优化算法应用于图像的多级阈值分割,取得了很好的效果。于洋等[8]为了解决红外相机采集行人图片时图像分割效果问题,提出一种自适应粒子群优化二维OSTU的阈值分割算法,能够快速且准确地得到最佳阈值,提高了图像预处理的分割效果。UPADHYAY等[9]将Kapur熵作为适应度函数,并通过乌鸦搜索算法求得最大Kapur熵,达到最优阈值。

非洲秃鹫算法(AVOA)[10]是受非洲秃鹫觅食和导航行为启发而提出的高性能智能算法,具有求解精度高的优点,但其全局搜索能力弱、易陷入局部。本文通过分段线性混沌映射(PWLCM)进行种群初始化,增强种群多样性;在全局搜索阶段引入β分布更好地控制种群在搜索空间上的重新划分;提出了新的基于饥饿率的全局搜索策略,用于增强算法搜索能力。将改进算法运用在二维Otsu图像阈值分割任务中取得了不错的效果。

1 基础非洲秃鹫优化算法(Basic African Vulture Optimization Algorithm)

非洲秃鹫优化算法(AVOA)是通过对非洲秃鹫的觅食行为和生活习惯进行模拟和建模而提出的。在AVOA中,非洲秃鹫的生活习惯和觅食行为主要包括以下4个阶段。

1.1 阶段一:随机选择最佳秃鹫

初始化种群后首先计算种群的适应度,其次选择最优个体为最优秃鹫,选择次优个体作为次优秃鹫。每次的最佳秃鹫会在这两个个体中通过如下公式计算产生,同时在每次更新迭代后重新计算整个总体。

(1)

其中,L1和L2为搜索操作之前给定的参数,其值介于0～1且两个参数之和为1。选择最优解的概率pi使用如下公式的轮盘赌方式获得,并为每组选择最优解。

(2)

1.2 阶段二:计算秃鹫的饥饿率

秃鹫的饥饿率由如下公式计算得出:

(3)

(4)

其中,F表示秃鹫的饥饿率,l表示当前的迭代次数,maxiterations表示最大迭代次数,z为介于-1～1且每代变化的随机数,h是介于-2～2的随机数,rand1是介于0～1的随机数。

同时,当F的绝对值大于1时,算法进入探索阶段;当F的值小于或等于1时,算法进入开发阶段。

1.3 阶段三:探索

AVOA的探索阶段秃鹫有两种不同的搜索策略,在两组最佳秃鹫之一的周围区域寻找食物和根据其饥饿程度在环境中随机搜索。

P(i+1)=R(i)-D(i)×F

(5)

D(i)=|X×R(i)-P(i)|

(6)

公式(5)模拟了在两组最佳秃鹫之一的周围区域寻找食物,其中P(i+1)为下一次迭代的位置,F是由公式(4)计算得出的秃鹫的饥饿率,R(i)是由公式(1)给出的最佳秃鹫,D(i)为到两组最佳秃鹫之一的随机距离,通过公式(6)计算得到。在公式(6)中,R(i)是由公式(1)给出的最佳秃鹫。X被用作增加随机运动的系数向量,由X=2×rand计算得到,其中rand为介于0～1的随机数。P(i)为当前秃鹫的位置。

P(i+1)=R(i)-F+rand2×((ub-lb)×rand3+lb)

(7)

公式(7)模拟了秃鹫根据其饥饿程度在环境中随机搜索,其中rand2是介于0～1的随机值,lb和ub表示变量的上界和下界,rand3是用于增加随机性的系数。

这两种策略会根据P1的值进行选择,P1是介于0～1的数。设randP1为介于0～1的随机数。如果randP1的值小于或等于P1,则使用公式(5),反之,使用公式(7)。

1.4 阶段四:开发

1.4.1 开发(第一阶段)

当F的绝对值介于0.5～1时,AVOA进入开发阶段的第一阶段。在开发阶段的第一阶段,执行缓慢围攻和旋转飞行两种不同的策略。

(1)缓慢围攻:当|F|≥0.5时,秃鹫相对能量充足。当许多秃鹫聚集在一个食物源上时,会在食物获取上引起严重的冲突。身体强壮的秃鹫不喜欢分享食物,而弱小的秃鹫试图聚集并引发小冲突以便获取食物,如下两个公式模拟了这两个过程。

P(i+1)=D(i)×(F+rand4)-d(t)

(8)

d(t)=R(i)-P(i)

(9)

公式(8)中,D(i)为到两组最佳秃鹫之一的随机距离,通过公式(6)计算得出,rand4为介于0～1的随机值。公式(9)中,R(i)是在当前迭代中使用公式(1)选择的最佳秃鹫。

(2)旋转飞行:秃鹫经常进行旋转飞行,可用于模拟螺旋运动。所有秃鹫与最佳和次佳秃鹫中的一只建立了一个螺旋方程,公式如下所示:

(10)

(11)

P(i+1)=R(i)-(S1+S2)

(12)

其中,rand5和rand6是介于0～1的随机数,最后通过公式(12)更新秃鹫的位置。

这两种策略会根据P2的值进行选择,P2是介于0～1的数。设randP2为介于0～1的随机数。如果randP2的值小于或等于P2,则根据公式(8)实施缓慢围攻策略,反之,使用公式(12)执行旋转飞行策略。

1.4.2 开发(第二阶段)

当|F|<0.5时,AVOA进入开发阶段的第二阶段,秃鹫开始进行聚集围攻和争夺食物。

(1)几种秃鹫在食物源上的聚集。

描述秃鹫这种运动的公式如下所示:

(13)

(14)

(15)

公式(13)和公式(14)中,BestVulture1(i)是当前迭代中第一组的最佳秃鹫,BestVulture2(i)是当前迭代中第二组的最佳秃鹫。用公式(15)计算得到下一代秃鹫的位置P(i+1)。

(2)对食物的激烈竞争。

当|F|<0.5时,领头的秃鹫变得饥饿和虚弱,没有足够的能量对抗其他秃鹫。而其他秃鹫会从不同方向朝着领头秃鹫的位置移动,可以使用如下公式模拟该现象:

P(i+1)=R(i)-|d(t)|×F×Levy(d)

(16)

其中,d(t)表示秃鹫与两组中最佳秃鹫之间的距离,该距离通过公式(9)计算得出。莱维飞行机制用于提高公式(16)中AVOA算法的有效性,莱维飞行生成的随机分量用以下公式计算。

(17)

其中

(18)

公式(17)、公式(18)中,α为固定值1.5。u和v服从正态分布:

(19)

第二阶段的两种策略会根据P3的值进行选择,P3是介于0～1的数。设randP3是介于0～1的随机数,如果randP3小于或等于P3,则根据公式(15)更新位置;反之由公式(16)实施对食物的激烈竞争。

2 改进非洲秃鹫优化算法(Improved African Vulture Optimization Algorithm)

针对非洲秃鹫算法全局搜索能力不足、局部搜索策略冗余及收敛速度慢等缺点,β-PAVOA主要做了以下改进。

2.1 基于PWLCM混沌映射的种群初始化

混沌映射是生成混沌序列的一种方法,被广泛地应用于各种算法中。PWLCM[11]作为混沌映射的典型代表,其数学形式简单,具有遍历性和随机性。如图1所示,PWLCM在空间中的分布非常均匀。

(a)PWLCM混沌映射图

通过PWLCM初始化种群,可以使β-PAVOA在初始化种群时更好地搜索整个解空间。PWLCM映射的描述如公式(20)所示:

(20)

公式(20)中,PZ=0.4,如果t≥2,则z(t)值可根据公式(20)计算得到,如果t=1,则z(1)为映射的初始值,z(1)取值是介于0～1的随机数。

将生成的值映射到解空间,如下公式所示:

P(i)=(ub-lb)×z(i)+lb

(21)

其中,P(i)是映射后的种群位置,ub和lb分别是位置的上界和下界,z(i)是由公式(20)得到介于0～1的混沌映射随机值。

2.2 基于β分布的全局增强搜索策略

β分布[12]是指一组定义在区间[0,1]的连续概率分布。在使用元启发式算法解决工程问题时,将β分布用于其中很有效,它可以近似模拟包括正态高斯分布在内的几种分布,也允许近似线性或指数递减的分布,可以是一维的,也可以是多维。一维β分布表达式如下:

(22)

(23)

其中,通过改变参数p和q就可以得到可能的β分布的多样性。基于β分布的全局增强搜索策略如公式(24)所示:

P(i+1)=(ub-lb)×betarand+lb

(24)

其中,P(i+1)为更新后的位置,betarand是p=1、q=1的情况下生成的β随机数。

2.3 基于饥饿率F的改进搜索策略

在测试过程中发现,AVOA在探索阶段的全局搜索表现不佳,因此提出了基于秃鹫饥饿率的改进搜索策略如公式(25)所示,用于改善这一问题。

P(i+1)=(rand-F)×X(randi(1,pop_size))

(25)

其中,P(i+1)为更新后的位置,rand为介于0～1的随机值。X为种群的历史最优位置,randi(1,pop_size)为1至种群大小之间的随机整数值。

2.4 改进局部搜索策略

β-PAVOA针对局部搜索策略冗余、收敛慢的缺点,对开发阶段策略进行了精简,整个开发阶段只使用AVOA在开发阶段的第二阶段中的更新策略,rand是介于0～1的随机数。如果rand小于0.3,则根据公式(15)更新位置;反之由公式(16)实施对食物的激烈竞争。β-PAVOA的算法流程如图2所示。

3 实验仿真与结果分析(Experimental simulation and result analysis)

3.1 实验环境设置

β-PAVOA在8个基准测试函数上进行了测试,选取了非洲秃鹫算法(AVOA)、金豺狼优化算法(GJO)、灰狼算法(GWO)、鲸鱼优化算法(WOA)和粒子群算法(PSO)作为对比算法。测试函数分为两类:F1～F4为单峰函数,F5～F8为多峰函数,测试函数设置见表1,算法默认参数设置见表2。将测试结果进行秩和检验,确定β-PAVOA获得结果的平均值与对比算法之间是否存在显著差异,当ρ>0.05时,认为β-PAVOA与对比算法的寻优性能相当。种群大小设置为50,最大迭代次数为1 000次,测试维度为30。为了减少不确定性,每个测试独立进行30次,计算30次测试的平均数和方差。实验是在配备32 GB RAM与i7-12700H处理器的个人计算机上进行的。

表1 测试函数设置Tab.1 Benchmark function settings

表2 算法参数设置Tab.2 Algorithm parameter settings

3.2 精度与收敛性分析

β-PAVOA与其他算法的测试结果见表3和表4。在F1～F8上,β-PAVOA展现出了极强的优势,从表3和表4中可以看出,相比其他算法在F3、F4、F7、F8上的测试结果,β-PAVOA有着领先几个量级的精度,在F1、F2、F5、F6上的测试结果相近的情况下,其稳定性有着明显的优势。同时,从图3和图4中的算法收敛曲线可以明显看出,β-PAVOA在F1～F8上的收敛精度与收敛速度均优于其他算法。

表3 各类算法在 F1～F4上的测试结果Tab.3 Test results of various algorithms on F1～F4

表4 各类算法在F5～F8上的测试结果Tab.4 Test results of various algorithms on F5～F8

(a)F1函数的收敛对比曲线

(b)F2函数的收敛对比曲线

(c)F3函数的收敛对比曲线

(d)F4函数的收敛对比曲线图3 不同算法的F1～F4收敛曲线对比Fig.3 Comparison of convergence curves of different algorithms on F1～F4

(a)F5函数的收敛对比曲线

(b)F6函数的收敛对比曲线

(c)F7函数的收敛对比曲线

(d)F8函数的收敛对比曲线图4 不同算法的F5～F8收敛曲线对比Fig.4 Comparison of convergence curves of different algorithms on F5～F8

4 Otsu图像阈值分割(Otsu image threshold segmentation)

Otsu阈值分割常用于图像二值化或阈值化[13]。图像阈值化是将灰度图像转换为二值图像的过程,其中每个像素根据特定的阈值被赋予黑色或白色值。Otsu阈值分割法简单高效,适用于分割、目标检测和特征提取[14]。Otsu阈值分割法在具有双峰直方图的图像上效果最好,即图像中有清晰的表示背景和前景像素强度的峰值。对于具有更复杂分布的图像,其他阈值化方法或更高级的技术可能更合适。

Otsu阈值分割法是找到能够使类间方差最大化的阈值,从而有效地将像素分为两个类别:前景和背景。类间方差测量两个类之间的扩展或可分性,并根据图像中的像素强度和概率计算。

4.1 Otsu阈值分割

假设图形大小为M×N,图像灰度范围为[0,L-1],ni为图像灰度级i的像素点数,则灰度级i出现的概率为pi=ni/(M×N)。在单阈值分割模型中,图像被分割成两类,其中C0类像素点灰度级为[0,T],C1类像素点灰度级为[T+1,L-1]。P0(T)、P1(T)分别为C0、C1出现的概率,u0(T)、u1(T)分别为C0、C1的平均灰度级,由如下公式计算得出:

(26)

(27)

(28)

(29)

(30)

(32)

4.2 Otsu多阈值分割

(33)

(34)

(35)

(36)

(37)

图像的类间方差用公式(36)表示,公式(37)则是最终的目标函数。

4.3 二维Otsu模型测试结果及分析

在二维Otsu模型测试中测试了β-PAVOA及对比算法的性能表现,测试选取了2张常用测试图片与1张内容复杂的图片(如图5所示)。测试结果如图6所示,β-PAVOA在找到最优解时,收敛速度与稳定性相比其他算法有明显的优势,这也验证了优化策略的有效性。

(a)相机

(b)人像

(c)月球图5 测试用图Fig.5 The text pictures

(a)相机二维Otsu测试结果

(b)相机二维Otsu模型迭代曲线

(d)人像二维Otsu模型迭代曲线

(e)月球二维Otsu测试结果

(f)月球二维Otsu模型迭代曲线图6 测试结果图Fig.6 The test results graph

5 结论(Conclusion)

本文提出了一种基于PWLCM与β分布的非洲秃鹫算法β-PAVOA。首先,通过PWLCM扩大种群在解空间的覆盖程度,提高寻优能力。其次,使用基于β分布的全局增强搜索策略增强算法的全局搜索能力。基于饥饿率F的改进搜索策略进一步增强了全局搜索能力。最后,通过简化局部搜索策略提升局部收敛速度。为了验证β-PAVOA的有效性,通过8个基准测试函数和二维Otsu图像阈值分割模型与非洲秃鹫算法(AVOA)、金豺狼优化算法(GJO)、灰狼算法(GWO)、鲸鱼优化算法(WOA)和粒子群算法(PSO)进行对比实验,采用均值、标准差与秩和检验方法进行评估。结果表明,β-PAVOA算法在探索能力和求解精度上都有显著优势。