黄华娟,邹鹏程,韦修喜,∗,徐 晨

(1.广西民族大学 人工智能学院 广西 南宁 530006;2.广西民族大学 电子信息学院 广西 南宁 530006)

0 引言

烟花算法(Fireworks algorithm,FWA)[1]是由北京大学谭营教授于2010年提出的模拟烟花爆炸并结合进化计算的随机搜索的群智能算法。烟花算法不同于其他群智能算法,它的多种不同算子分布工作,实现信息交互共享,能够处理复杂的优化问题。爆炸、变异、选择等算子的存在使得算法具备广阔的研究前景。

算术优化算法 ( Arithmetic optimization algorithm, AOA)[2]是Abualigah 等于2021年提出的一种根据算术操作符的分布特性实现全局寻优的元启发式优化算法。该算法通过乘除运算进行全局勘探并通过加减运算进行局部开采,具有可移植性强、参数少及执行效率高等特点。

谱聚类(Spectral clustering,SC)是基于图论的现代聚类算法,根据样本之间的相似度构建无向图,再使用某种切图算法把无向图分割为若干个不相连接的子图,从而实现对样本的划分,将聚类问题转化为图的切割问题[3]。传统的聚类算法在非凸数据上的表现较差,而SC 算法却没有这个限制,对于不同分布的数据都有很好的划分效果。具有解决多路谱聚类能力的NJW(Neue juristische wochenschrift)算法是谱聚类的代表性算法,然而其聚类效果很大程度依赖于对初始类中心敏感的K-means 算法。K-means 算法是一种无监督学习的聚类方法,在聚类过程中,受初始聚类中心的影响,算法易存在聚类精度低、聚类效果不稳定等问题[4]。烟花算法对空间解的搜索具有一定的优势,因此,在NJW 算法的特征空间内对新样本划分时,若采用烟花算法替代K-means 算法,这将融合NJW 和FWA 两种算法的优势。

近年来学界对烟花算法的研究不断深入并针对算法的不足提出一系列改进算法。Zheng 等[5]针对爆炸算子存在的不足提出了引入最小爆炸半径阈值的增强烟花算法(Enhanced fireworks algorithm,EFWA)。仅依据烟花适应度差值计算得到的爆炸半径较难达到较小值,所以FWA 和EFWA 局部搜索能力较差。针对局部寻优能力不足,Zheng 等[6]提出了引入爆炸半径放大缩小机制的动态搜索烟花算法(Dynamic search in fireworks algorithm,dynFWA),当烟花种群搜索到一个适应度值不再变好的位置时,dynFWA 将减小核心烟花的爆炸半径,反之则增大。虽然dynFWA 去除了变异算子加快了寻优速度,但适应度值不再变好时减小半径易使得算法陷入局部最优。自适应烟花算法(Adaptive fireworks algorithm, AFWA)是Li等[7]提出的另一种与粒子群算法全局搜索类似的调整搜索半径的方法。当前个体的爆炸半径为当前个体与当前最优个体的距离,以便算法跳出局部最优。虽然AFWA 能对搜索步长进行自适应调整,表现出了很好的性能改善,但是仅有步长的自适应调整,而没有爆炸火花数的自适应变化,难以平衡算法的开采与勘探能力。只对单一算法改进难以快速找到最优解,为此,一些混合算法相继被提出。Gao 等[8]提出融合文化算法的文化烟花算法(Cultural fireworks algorithm, CA-FWA),并将文化烟花算法应用到滤波器的设计上,并取得了较好的性能。Zheng 等[9]提出融合差分进化算法的混合型烟花算法(Hybrid fireworks optimization method with differential evolution operators, FWADE)。文化烟花算法和差分进化算法都有其特定的优势,用于结合烟花算法的混合算法能兼顾两种算法的优势,但同时也会产生冲突,如何解决两种算法的冲突往往是解决问题的关键。AOA 算法原理简单,易于实现,参数少,为此将AOA 算法与FWA 算法结合,冲突少,易于得到可观的结果。

以上文献对基本烟花算法都有一定程度的改进,但仍有不足。首先,对于爆炸半径的设置,非线性递减的步长具有一定盲目性。其次,对粒子随机维度进行爆炸半径内位置更新操作,并非更新步长为爆炸半径,而是0 到爆炸半径,既无法保证所选维度的有效性,又可能导致多代粒子更新步长相似,爆炸半径起到极其微小的作用。最后,对于变异策略,大多数采用的高斯变异使得粒子变异过程中倾向于0,造成算法对于最优解在原点附近寻优精度高的假象。为此,本文提出了融合AOA 算法的混合型烟花算法(Hybrid fireworks algorithm based on AOA, AOAFWA)。

受半径放大缩小机制及AOA 算法加减乘除机制的启发,结合烟花爆炸的随机性,本文算法引入加减乘除机制代替烟花算法爆炸更新机制,由于加减乘除机制是在当前最优粒子上实施的,本文采用精英选择策略,既没有了轮盘赌[10]选择策略的高复杂度,又更好地迎合加减乘除机制。最后,选取柯西变异[11]策略以增加种群多样性,帮助算法跳出局部最优。本文选取了8 个基本测试函数进行测试并在谱聚类问题上进行测试,验证了AOAFWA 算法在收敛能力和搜索能力上的有效性和优越性。

1 烟花算法

1.1 烟花算法实现步骤

步骤1:种群初始化。随机生成N个烟花,根据优化的目标函数计算每个烟花的适应度值,从而确定烟花质量的好坏。

步骤2:计算烟花的爆炸半径Ai和爆炸火花数Si:

其中:和M为常数,用于调整爆炸半径和爆炸产生火花数;f(xi)为烟花i的适应度值;ymin和ymax分别是最好与最差烟花个体的适应度值;ε为机器最小量,避免除零操作。为防止产生爆炸火花数向优质或劣质烟花压倒性倾斜,文献[1]对于爆炸火花数进行了限制:

其中:a,b是常数;round( )是取整函数。

步骤3:根据式(4)生成爆炸火花,并对其进行越界检测,根据式(5)将超出爆炸空间的爆炸火花映射到可行域空间内:

其中:Nki代表烟花i的第k维度的位置;U(-1,1)代表[-1,1]的随机分布;NkLB和NkUB分别为在维度k上解空间的下、上边界。

步骤4:根据式(6)生成少量的高斯变异火花并根据式(5)进行越界处理,增加了群体多样性:

其中,e～N(0,1)。

步骤5:选择策略。根据式(7)从烟花、爆火花和高斯变异火花组成的候选者集合中选择N-1个烟花和当代适应度值最优的火花作为下一代烟花:

其中d(Ni-Νj)表示候选集中个体i与除i以外所有个体之间的距离。

步骤6:判断是否满足终止条件。满足则终止搜索,否则转至步骤2。

2 算术优化算法

2.1 算术优化算法实现步骤

步骤1:初始化算法相关参数和种群。

步骤2:计算适应度值,并记录最优位置。生成0 到1 之间的随机数r1,r2,r3。

步骤3:根据式(8)计算数学优化器加速函数(Math Optimizer Acceleration function, MOA),记为FMOA,判断是否小于r1,小于则转步骤4 进行全局搜索,否则转步骤5 进行局部搜索:

其中:Mmin和Mmax分别是加速函数的最小值和最大值,为0.2 和1;iter和MaxIter分别为当前迭代次数和最大迭代次数。

步骤4:根据式(9)和式(10)(数学优化器概率(Math optimizer probability, MOP),记为FMOP)进行乘除运算更新粒子位置。其中:μ是调整搜索过程的控制参数,值为0.499;ε为极小值;Xb(iter)为iter代最优位置;UB和LB分别为寻优空间上下界;α是敏感参数,取值为5。转步骤6。

步骤5:根据式(11)进行加减运算更新位置:

步骤6:计算适应度值,并记录最优位置。

步骤7:判断是否满足结束条件,如果满足则输出最优解,否则跳转至步骤3。

3 混合型烟花算法

3.1 基于加减乘除机制的爆炸策略

烟花算法的核心就是烟花爆炸环节,爆炸策略的好坏直接影响寻优能力。传统烟花算法以及大多数改进算法均存在爆炸半径盲目设定的问题,无法实现爆炸半径与寻优进度相适应,同时,在不同半径内爆炸的粒子覆盖率较高(极少部分粒子以爆炸半径为步长进行位置更新),进而导致算法早熟或者过早陷入局部最优。此外,对爆炸粒子随机维度进行位置更新,无法保证所选维度为寻优所需要的维度,即使该维度为寻优所需关键维度,仅对其实施一次0 到Ai之间随机幅度位移操作,难以保证寻优效果,应给予其更大的爆炸幅度及更多的位移次数。

鸟群算法中通过学习因子调节认知经验和社会经验。在搜索前期较大的认知系数和较小的社会系数可以增大认知经验的比重,使得鸟群全局搜索能力增强,搜索后期较小的认知系数和较大的社会系数可以增大社会经验的比重,增强局部搜索能力。

针对上述存在的问题,参考复杂适应理论中的自适应性和个体与种群的协同进化作用[12],采取随机均匀分布的加速度函数的AOA 算法与FWA 算法结合将更好地平衡算法在迭代初期和后期的全局及局部搜索能力。具体通过将AOA算法位置更新方式取代烟花算法爆炸位置更新方式,利用乘除运算实现全局搜索,利用加减运算实现局部开发。

3.2 柯西变异策略

传统烟花算法对随机选择的烟花的随机维度进行高斯变异操作,主要存在以下问题:第一,随机选择的烟花,其位置具有很大随机性,难以保证其位置优越性,再对其部分维度进行变异操作,难保证选到需要变异的维度,假设选到该维度,变异方向与大小又会对结果产生影响,总之,其整体位置变优的概率很小,大多数变异粒子适应度值差于当代最优适应度值而被淘汰,浪费了计算资源。第二,高斯分布特征决定了算法只在当前解领域范围内进行搜索,难以跳出局部最优。针对以上不足,本文根据式

对变异算子进行柯西变异,其中c～C(0,1)。柯西变异算子的全局搜索能力更强,增大了变异范围,增加了种群多样性。

3.3 精英选择策略

传统烟花算法采用基于欧氏距离的轮盘赌选择策略有以下两个主要缺点:第一,计算复杂,限制收敛速度;第二,密度高或适应度值好的粒子周围存在较多粒子,其被选择到下一代的概率较小。为了加快收敛速度、提高收敛精度以及更好地迎合加减乘除机制,本文选用精英选择策略。

3.4 算法伪代码及复杂度分析

算法1 AOAFWA 算法

时间复杂度是指算法执行完成所需的时间,主要取决于问题被重复执行的次数。标准烟花算法的时间复杂度主要取决于种群大小n、迭代次数t和问题维度d。由标准烟花算法的算法步骤可知,它的时间复杂度为O(n×t×d)。

AOAFWA 算法是通过改进FWA 算法而来,由算法伪代码可知,将原算法爆炸更新机制替换为AOA 算法位置更新机制增加了O(t)的工作量,柯西变异策略及精英选择策略均未增加工作量。综上,AOAFWA 算法的时间复杂度仍是O(n×t×d)。

空间复杂度是算法在执行完成所需的存储空间,而标准烟花算法的空间复杂度主要取决于种群大小n和问题维度d,所以标准烟花算法的空间复杂度为O(n×d)。改进算法AOAFWA 中采用几个常量标记MOA 和MOP 的值,同时减少了常量Ai的值,它所消耗的存储空间可以忽略不计,故AOAFWA 的空间复杂度也是O(n×d)。

4 实验仿真与分析

为了验证AOAFWA 算法的有效性,进行了两组实验。第一组是通过8 个标准测试函数(详细信息见表1,F1、F2、F3和F4为单峰函数,F5、F6、F7和F8中为多峰函数,维度均为30,最优值均为0)及FWA、AOA、GFWA[13]、LoTFWA[14]、GWO[15]和BOA[16]6 个对比算法进行测试分析。第二组是应用于谱聚类问题。

表1 标准测试函数Tab.1 Standard test function

所有算法初始种群大小统一设置为30,最大迭代次数设为1 000 次。为了降低算法随机性对实验性能的影响,以30 次独立实验的平均值作为评估算法寻优性能和收敛性能的最终结果。所有算法的实验在同一平台上运行,实验平台为Windows 10 (64bit) 操作系统下的 MATLAB R2018b,硬件条件为 Intel Core i5-4210 CPU 2.90GHz、8GB 内存。参与测试的各算法的具体参数见表2。

表2 具体参数Tab.2 Specific parameters

4.1 基准函数实验测试与分析

表3 列出了7 种算法在不同测试函数下目标函数最优值、最差值、平均值、运行时间以及标准差的详细数据,其中粗体标注为最佳搜索结果。为了更直观地比较,表中将搜索质量进行量化,通过平均值、方差进行排序,排名越靠前,等级值越小,最后一列给出了排列次序。从表中数据可看出:在8 个测试函数中,AOAFWA 算法均排名第一,并且寻找到最优解。在单峰函数F1、F2、F3和F4中,AOAFWA 相较于标准FWA,其收敛精度误差从10-100附近降低至10-300,相较于其他对比算法所提升的数量级更多。在多峰函数F5、F6、F7和F8中,AOAFWA 与标准FWA 均能收敛到最优值,且收敛精度远超其他对比算法。这表明,标准FWA 自身已具备出色的寻优能力,改进后的AOAFWA 进一步增加了原算法的收敛精度。从运行时间看,AOAFWA 算法运行时间远小于FWA 算法及其改进算法,虽然略高于GWO、BOA 和AOA算法,但运行时间的略微增加换取了更高的寻优精度还是可以接受的。

表3 标准函数测试结果Tab.3 Test results of standard function

为补充说明,图1～图8 分别描绘了8 个测试函数寻优迭代对比曲线图。观察可知,改进后的AOAFWA 充分吸收了AOA 和FWA 的优点,既具备了AOA 快速寻优的特点(200 代以内就搜寻到最优解),又具备了FWA 收敛精度高的特点(均快速收敛到最优解,远超其他对比算法)。通过实验数据和收敛图的展示,进一步说明了AOAFWA 算法相比其他FWA 变体算法以及其他智能优化算法在标准函数测试中的表现更优越。

图1 F1 的收敛曲线Fig.1 The convergence curve of F1

图2 F2 的收敛曲线Fig.2 The convergence curve of F2

图3 F3 的收敛曲线Fig.3 The convergence curve of F3

图4 F4 的收敛曲线Fig.4 The convergence curve of F4

图5 F5 的收敛曲线Fig.5 The convergence curve of F5

图6 F6 的收敛曲线Fig.6 The convergence curve of F6

图7 F7 的收敛曲线Fig.7 The convergence curve of F7

图8 F8 收敛曲线Fig.8 The convergence curve of F8

4.2 Wilcoxon 统计校验

仅以算法的平均值、标准差、最优值和最差值作为算法性能的评价指标是不够严谨的。因此对所提出的算法进行统计校验是必不可少的。为了比较文中7 种算法的性能,采用了Wilcoxon 秩和校验。表4 中记录了7 种算法在8 个测试函数上秩和校验后得到的p值。当p值小于0.05 时,说明两种对比算法之间存在较大的差异,否则表明对比算法存在一定的相似性。p值为“NA”表示此校验不适用。

表4 Wilcoxon 秩和校验的p 值Tab.4 p-value of Wilcoxon rank-sum test

由表4 可知,在所有测试函数中,AOAFWA 与其他对比算法有很大的不同,这说明了AOAFWA具有较好的寻优性能。

4.3 NJW 谱聚类问题测试与分析

NJW 谱聚类可以理解为将高维空间的数据映射到低维,然后在低维空间用其他聚类算法(如Kmeans)进行聚类。本文通过AOAFWA 算法代替K-means 算法寻找最优初始中心簇,评价指标选取为所有点到相应重心的距离的平方和F(DK,ξ),

其中:数据集DK为原始数据划分为K类得到新的数据集,聚类中心ξ={ξ1,ξ2,…,ξK},为第k类别中第i个数据,Dist为欧氏距离的平方。

通过2 个UCI 数据集Iris 和Wine 及不同尺度参数σ进行分类实验,由于尺度参数对聚类结果有较大影响,所以进行大量实验以验证算法寻优能力,篇幅有限,表5 只列出了部分AOAFWA 算法与FWA 算法以及K-means 算法在30 次独立运行后的寻优结果,算法具体参数设置见表2。与FWA 相比,无论从平均值、标准差、最优值或者最差值来看,AOAFWA 算法均获得较佳的数据,平均值至少优于原算法3.3%,体现其出色的稳定性与寻优精度;与K-means 相比,AOAFWA 算法平均值依然最低,虽然最优值差于K-means 算法(最多为1.7%),但最差值却优于K-means 算法(最少为3.1%)。从标准差可看出:改进后的AOAFWA 算法标准差远远低于改进前的FWA 算法,鉴于K-means 算法具有较大的随机性,所以出现个别标准差低于AOAFWA 算法的情况也可接受。综上AOAFWA 收敛速度、收敛精度、稳定性都优于FWA,表现出对FWA 改进后的AOAFWA 出色效果 。

表5 不同算法在谱聚类问题测试结果比较Tab.5 Comparison of test results of different algorithms in Spectral clustering problem

5 结论

针对FWA 算法的缺点,本文在传统烟花算法的基础上进行改进,融合了AOA 算法收敛速度快的优点。对于AOA 算法而言,FWA 算法烟花爆炸机制的存在增加了AOA 算法的并行寻优能力,进一步提高了AOA 算法寻优速度与寻优精度;对于FWA 算法而言,AOA 算法的加减乘除机制为已经处于瓶颈期的爆炸策略提供了新的思路,进一步平衡了FWA 算法勘探与开采能力。通过测试,该算法对于函数优化能够较好的寻优求解,在4 个测试函数上精度误差从10-100附近降低至10-300(同时从收敛曲线图能够看出该算法均在300 代以内就收敛到全局最优解),在谱聚类算法的应用中适应度值平均值至少优于原算法3.3%,证明本文AOAFWA 算法相比于其他算法在求解精度方面具有更强的竞争优势,但运行效率稍低于GWO、AOA 和BOA 算法,这也是FWA 算子众多所带来的弊端。这篇文章限于篇幅,并未对FWA 算子进行简化再融合AOA,未来将考虑删除变异算子并将改进后的AOA 融入到FWA 中,进一步减少算法运行时间,提高收敛精度,并用于解决更多实际问题。