融合多策略改进的自适应乌鸦搜索算法

陈志鹏 李环 魏文红

(东莞理工学院 计算机科学与技术学院,广东东莞 523808)

近些年来,启发式优化算法吸引了众多研究者的关注。通过模拟自然界的现象,生物行为和物理现象,一系列的启发式算法不断被提出。根据NFL定理,不存在一种算法能够解决所有问题。因此,研究者需要不断改进现有算法或提出更优秀的算法来优化不同问题。自20世纪以来,受自然界生物的启发,研究人员提出了多种优化算法,如蝙蝠算法[1]、灰狼算法[2]以及鲸鱼优化算法[3]等。这些算法一经提出就受到了广泛的关注和研究,为不同领域问题的求解提供了更多技术支持。

乌鸦搜索算法(Crow Search Algorithm,CSA)[4]是由Askarzadeh于2016年提出的一种新的优化算法,其灵感来源于乌鸦觅食行为。CSA模拟了乌鸦进行觅食和藏匿食物的两种行为,和其他智能算法比较,CSA具有控制参数较少、结构简单、易于掌握且全局搜索能力强等优点。当下,乌鸦搜索算法已经成功在特征选择[5]、图像处理[6]、航空运力调度[7]、无人机路径规划[8]等领域取得了应用。

与其他的智能优化算法相比较,乌鸦搜索算法具有全局搜索能力强,搜索过程中能够保持较高的种群多样性优点。然而,由于该算法在搜索过程中缺乏最优个体或精英个体的引导,即使在搜索后期,算法仍然难以收敛,导致种群分散并陷入多个局部最优点。为此,国内外不少研究者提出了各种策略对乌鸦搜索算法进行了相应的改进。文献[9]提出了正余弦指引的乌鸦搜索算法,通过采用嵌入正余弦算子的方式对乌鸦进行位置更新的引导,提高了算法的收敛精度。文献[10]提出了动态自适应的感知概率AP和飞行长度fl,以此来调控算法在不同时期的全局搜索和局部寻优的能力。文献[11]在算法中使用交叉算子和变异算子,从而防止CSA在运行过程中陷入局部最优。文献[12]提出向最优粒子学习的策略,并在不同阶段加入扰动策略,提升了算法的收敛速度和精度。文献[13]采用高斯变异进行优化全局最优个体,并引入Jaya引导策略提升个体位置更新的精度,从而提升了算法的整体性能。尽管上述文献提出的改进CSA比经典CSA在优化精度方面有了一定的提升,但在维护种群多样性和提升算法的收敛速度和精度等方面,仍需要进一步改进。针对该问题,本文融入记忆遗忘机制对乌鸦搜索算法进行了改进,通过选取优秀记忆对乌鸦的个体位置进行引导,进一步提升算法在前期的收敛性,同时也避免算法在迭代后期种群多样性低的问题,并且在算法中嵌入黄金正弦算子,以减少位置更新的盲目性。以上改进加快了算法的收敛速度和收敛精度,并在仿真数值实验中验证。

1 乌鸦搜索算法

1.1 基本理论

乌鸦搜索算法模拟的是乌鸦,藏匿食物和窃取其他乌鸦食物的两种行为。一方面它们会在觅食之后,将食物藏匿于某个地点;另一方面,乌鸦也会观察其他乌鸦的食物储藏点以便窃取其他乌鸦更好的食物。

在上述情况中,fl表示乌鸦的飞行距离,r1则是一个服从 [0,1] 均匀分布的随机数。

同时还存在另一种情况,即乌鸦j意识到乌鸦i在追踪自己以窃取食物。为了保护食物,乌鸦j选择随机飞往搜索空间中的任意一个位置,以欺骗乌鸦i。综上两种情况,乌鸦i的位置更新公式如式(1)。

(1)

其中,r2表示为服从[0,1]均匀分布的一个随机数;AP表示乌鸦j发现乌鸦i追随的感知概率。

1.2 乌鸦搜索算法基本流程

CSA算法具体步骤如下:

步骤1:初始化变量种群总数n,感知概率AP,飞行距离fl和迭代次数T;

步骤2:初始化每只乌鸦在d维搜索空间的位置和记忆。由于初始时乌鸦并没有先前记忆,所以乌鸦的初始位置即为乌鸦的初始记忆;

步骤3:设置目标函数,并且计算每只乌鸦所在位置的适应度值;

步骤4:根据式(1)计算,生成乌鸦在空间中的新位置;

步骤5:检测新位置是否超出搜索空间。如果还在空间内,则将新位置更新,否则停留在原来的位置。

步骤6:计算新的位置的适应度;

步骤7:对于当前的乌鸦,比较其记忆位置和新位置的适应度值,若新位置的适应度值更优,则将该新位置作为该乌鸦的新的记忆位置;

步骤8:不断重复步骤4～步骤7,直到达到最大迭代次数。

2 改进乌鸦搜索算法

为提升经典乌鸦搜索算法的搜索精度和收敛速度,本文提出了融合多策略改进的自适应乌鸦搜索算法(ACSA)。该算法引入记忆遗忘机制,选取优秀记忆对乌鸦进行引导。同时,对原有的位置更新公式进行改进,并融入黄金正弦算子,克服算法位置更新的盲目性。最后,使用自适应感知概率和飞行长度对原有算法进行改进,从而对算法的性能有了较大的提升。下面是对改进算法的详细表述。

2.1 引入记忆遗忘机制

遗忘是自然界中普遍存在的一种生物现象。学习和遗忘被认为是相互互补的过程,因此也有部分学者将遗忘现象运用到各种算法中。例如,文献[14]将多目标策略和遗忘机制相结合,以此改进了粒子群算法的更新公式,充分提升了粒子群算法的性能。文献[15]利用遗忘机制和平均信息,改进了算法群体的搜索能力。这让粒子群算法能够更好地寻找到全局最优。通过引入遗忘机制,这些算法的性能都得到了一定的提升。因此,本文将遗忘机制引入乌鸦搜索算法。

乌鸦搜索算法的个体位置更新是通过向个体记忆进行学习更新,因此记忆的优异程度对于产生解的好坏有着重要的影响。但在算法初期阶段,乌鸦的记忆位置分布比较分散,如果进行随机选择个体记忆进行位置引导,这样的策略并不利于算法的收敛。为了解决这个问题,本文提出遗忘适应度值较差记忆,使用优质记忆的策略进行个体位置的更新。同时,提出记忆阈值的概念以此用于衡量记忆的优劣。其中,记忆阈值Fv(Forgetting value)用于衡量记忆的优劣,记忆阈值的表达如公式(2)所示:

Fv=fit(Mt)min+(fit(Mt)max-fit(Mt)min)×

e-(tmax/t),

(2)

式中:fit(Mt)min为第t代种群记忆中的适应度值最优个体的适应度值;fit(Mt)max为第t代种群记忆的适应度最差个体的适应度值。当乌鸦的记忆适应度值优于记忆阈值时,则被判定为优秀记忆,可以有机会被选为下一次乌鸦位置更新的引导记忆;否则,被选择遗忘。从式(2)中可以看出,在算法初期,种群的分布较为发散,这时让Fv趋近于种群记忆的最优值,可以选出更为优质的个体记忆对乌鸦进行搜索引导,这避免了算法初期的盲目搜索。随着迭代次数的增加,记忆阈值逐渐增大,这时可被选择的引导记忆越来越多,也避免了种群一直由最优个体引导,从而能够较好地保持种群的多样性。

2.2 融合黄金正弦引导和改进原有搜索方式

鉴于经典的CSA的个体更新方式单一,这不仅不利于算法的全局搜索,同时也不利于局部的寻优,就导致CSA产生收敛精度低,收敛速度较慢的问题。本文借鉴粒子群算法的速度更新方式,将全局最优位置引入CSA,帮助算法能够有着更快的收敛速度。具体改进如式(3)。

(3)

c1=1.5×e-(tmax/t),

(4)

c2=1.5×e-(tmax/t),

(5)

其中,c1和c2为权重系数,根据式(4)、式(5)。当迭代次数t不断增加时,c1不断增加,c2不断减小。目的是让迭代初期,全局最优个体的引导占据更大的比重,提高算法的收敛速度。在迭代后期时,随机选取的个体占据更大比重,以提高算法跳出局部最优的可能。

同时根据式(1)可知,当r2小于AP时,乌鸦的位置更新是搜索空间中随机产生一个位置。虽然有助于提高算法跳出局部最优的概率,但也存在极大的盲目性,导致算法的收敛速度和寻优精度并不理想。为克服该缺点,本文采用引入黄金正弦算子来解决此问题。

黄金正弦算子是根据黄金正弦算法[16]提出的,是Erkan Tanyildizi在2017年根据数学中的正弦函数提出的一种新型智能算法,具有收敛速度快、寻优能力强的优点。当r2小于AP时,使用黄金正弦算子对乌鸦进行引导,帮助算法获得更快的寻优能力和收敛精度。融合黄金正弦算子和改进原有的位置更新方式如式(6)。

(6)

2.3 自适应飞行长度和感知概率

为平衡全局搜索和局部开发的程度,本文使用动态自适应参数。其中,引入动态感知概率AP,随着迭代次数的增加,AP逐渐增大。在算法的后期,将更有可能使用黄金正弦算子进行局部寻优,以找到最优解。此外,为解决固定飞行长度带来的问题,本文采用动态飞行长度fl,即在算法初期,飞行步长较大,有利于进行全局搜索,而在迭代的后期,飞行步长逐渐缩小,使算法可以更好地进行局部寻优。通过非线性动态飞行步长的控制,将能够有效地平衡算法的全局搜索和局部搜索能力,提高算法的收敛速率和寻优精度。其中,飞行步长的变化如式(7),感知概率的变化如式(8)。

(7)

AP=ρ×1.5(t/tmax).

(8)

2.4 ACSA的算法基本流程

综合上述改进策略,ACSA的算法基本流程如下。

步骤1:初始化乌鸦种群位置,乌鸦记忆,初始感知概率ρ,初始飞行步长flinit和最大迭代次数tmax;

步骤2:计算每只乌鸦个体的适应度值并找出当前最优位置;

步骤3:计算当前乌鸦的记忆阈值,并从中找出较为优异的记忆位置;

步骤4:判断产生的随机数是否大于当前的感知概率,若是则使用式(3)进行乌鸦位置更新。否则,采用式(6)进行更新乌鸦位置;

步骤5:判断乌鸦新位置是否可行,若可行则更新乌鸦的位置和记忆,否则保持原样;

步骤6:进行最大迭代次数的判断,若达到,则输出最优位置和其适应度值;否则,重复步骤2～步骤6,直到满足终止条件。

3 仿真实验和结果分析

3.1 实验参数设置

本文选取鲸鱼优化算法(WOA)[3]、经典的乌鸦搜索算法(CSA)[4]、正余弦指引的乌鸦搜索算法(SCACSA)[9]和多段扰动的共享型乌鸦算法(MISCSA)[12]进行对比实验,所涉及算法的种群规模均为30,迭代次数为1 000,其余共有参数保持一致,各算法的参数设定如表1。

表1 算法参数设置

3.2 测试函数

将ACSA在13个基准测试函数上进行寻优测试,同时和上述提及的算法进行分析比较,其中13个基准测试函数的相关基本信息见表2。

表2 基准测试函数信息

3.3 实验结果分析

为验证本文提出的ACSA的性能。使用13个测试函数对其进行实验,同时为避免偶然性形成的误差,算法需要在每个函数上进行30次的寻优。表3列出ACSA、鲸鱼优化算法(WOA)、CSA、SCACSA、MISCSA在多个测试函数上运行30次后产生的实验结果。

表3 测试函数实验结果

从表3和图1可知,对于函数F1(x)、F3(x),ACSA相比其他的5种算法能够在更少的迭代次数的情况下找到理论最优值,而其他4种算法却无法达到全局最优。对于F2(x)和F4(x),由图2、图3以及表3中数据可得,虽然ACSA也无法寻得理论最优值,但收敛精度却远远高于其他算法,对于函数F5(x),ACSA的平均值不如SCACSA和MISCSA,但是从最优值的情况来看,ACSA是优于所有算法的。综上,ACSA对于高维单峰函数拥有较好的寻优能力。

图1 F1(x)的收敛曲线

图2 F2(x)的收敛曲线

图3 F4(x)的收敛曲线

由表3可知,ACSA在求解高维多峰函数F6(x)、F7(x)、F8(x)时,能够表现出较为优异的寻优精度。虽然别的算法在某些测试函数中也可得到最优值,但通过图4可知,ACSA的收敛速度相对更为占优。对于F9(x),由表3和图5所知,只有ACSA在规定的迭代次数内寻找到了最高精度的解,这也表明了ACSA具有不错的求解高维多峰函数的能力。对于F10(x),ACSA的结果劣于大部分比较算法,但与最优值的求解数据差距不大,求解精度均在一个数量级内。对F11(x)、F12(x)和F13(x)进行比较,ACSA在这3个函数中均求得了最优值,同时标准差在这3个函数的求解中,仅次于CSA,说明ACSA在求解精度较好的同时,也有着还不错的稳定性。同时根据图6,ACSA的收敛速度也更优于其他算法。

图4 F7(x)的收敛曲线

图5 F9(x)的收敛曲线

图6 F13(x)的收敛曲线

3.4 统计校验

参考文献[17]指出,仅仅通过对算法独立执行30次后得到的最优值、平均值和标准差进行评价,并不够严谨。因此,本研究将采用统计检验方法对算法进行更为科学的性能评估。

为了比较文献中所提出的6种算法,将使用Wilcoxon秩和检验和Friedman检验来进行分析。

3.4.1 Wilcoxon秩和检验

通过上一节中ACSA在每个测试函数中的收敛曲线和表3可以得出。

ACSA相比于其他算法有着更好的收敛速度和收敛精度。同时,为提高实验的严谨性,避免少数的偏离数据影响算法的性能评价,本部分将采用Wilcoxon秩和检验进行算法评估。根据参考文献[18]中描述的p值的统计理论,可以得出结论:当p值小于0.05时,表示两种对比算法之间存在显著差异;当p值大于或等于0.05时,表示两种对比算法存在一定程度的相似性。从表4可以看出,ACSA在F5(x)函数中的优化结果和SCACSA以及MISCSA存在一定的相似性,以及在F10(x)中,ACSA和WOA的优化结果存在一定相似性,而在其他函数的比较中都具有较大的不同,这说明了ACSA有着优异的性能。

表4 Wilcoxon秩和检验的p

3.4.2 Friedman检验

对ACSA算法和其他5种比较算法在13个基准测试函数上获取的平均值,进行Friedman检验。表5列示了这6种算法在13个测试函数上进行Friedman检验的结果。

表5 Friedman检验秩均值表

通过表5可知,ACSA的秩均值是所有算法中最小的,仅为2.03,在比较的算法中位居第一,相比未改进过的CSA的秩均值大幅减小。这表明了本文中对原有算法的改进具有一定的有效性。

4 ACSA求解三杆桁架设计问题

从上一节可知,ACSA对比其他的算法在函数寻优方面有着更好的性能。为进一步探究ACSA的优化性能。本节将使用ACSA对三杆桁架设计这一实际问题求解,并且和其他多种算法的求解结果进行对比。以表明ACSA可运用于实际工程问题的求解。三杆桁架设计的目标是通过不断调整x1和x2,并在一定的约束条件下,使三杆桁架的体积达到最小。相关设计示意图如图7,该问题的数学模型表示如式(9)。

图7 三杆桁架示意图

l=100 cm,p=2 kN/cm2,σ=2 kN/cm2.

(9)

本实验的求解迭代次数设置为500,对比算法各个独立运行30次,其余参数设置和相关参考文献保持一致,ACSA求解数据和其他CSA[4]、MVO[19]、GOA[20]、MFO[21]、MFCSA[22]的对比结果如下表6所示,实验结果对比得出ACSA能够在相比较的其余5种算法中取得最优的求解结果。

表6 不同算法对于三杆桁架问题的测试结果

5 结语

本研究提出了一种融合多策略改进的自适应乌鸦搜索算法(ACSA),该算法结合了记忆遗忘机制和黄金正弦算子来改进乌鸦搜索算法。ACSA通过使用记忆阈值来挑选出优秀的记忆,并使用这些优秀记忆来引导乌鸦个体的位置更新,该方法有效地提高了算法前期的收敛速度,同时能够防止算法后期种群多样性的降低。此外,ACSA还嵌入了黄金正弦算子来避免个体位置更新的盲目性,从而提高了算法的整体性能。

通过对13个测试函数和一个工程约束设计问题进行实验可以得出结论,ACSA在函数优化方面具有更出色的寻优性能,并且能够有效地解决三杆桁架的设计问题。未来,研究计划将重点关注如何将改进后的算法应用于实际应用。