融合振荡禁忌搜索的自适应均衡优化算法

刘成汉，何 庆

1.贵州大学 大数据与信息工程学院，贵阳550025 2.贵州大学 贵州省公共大数据重点实验室，贵阳 550025

在过去的二十年中，随着科技的发展和技术的革新，各种复杂优化问题层出不穷，启发式算法由于其简单性、灵活性和较高的鲁棒性，成为解决复杂优化问题的有力工具。常见的启发式算法有：粒子群优化（particle swarm optimization，PSO）算法[1]、灰狼优化（grey wolf optimization，GWO）算法[2]、鲸鱼优化算法（whale optimization algorithm，WOA）[3]等。

均衡优化（equilibrium optimizer，EO）算法是Faramarzi等人[4]2019年提出的一种新型启发式算法，其灵感来源于用于估计动态和平衡状态的控制体积质量平衡物理模型。EO算法具有搜索能力强、参数简单的优点[4]，已被成功应用到多阈值图像分割[5]、经济调度[6]、路径规划[7]等多个领域，为解决复杂优化问题提供了新的思路。但是EO算法仍存在着收敛精度不高、收敛速度慢、易受局部最小值影响的问题。针对上述问题，众多学者对EO算法做出了改进。例如：Fan等人[8]提出了一种基于对立学习和改进位置更新方式的均衡优化算法，利用高斯变异和基于种群划分和重构概念的探索性搜索机制，提高了算法的收敛速度和跳出局部极值点的能力；Gao等人[9]采用S型和V型传递函数将EO算法转换成二进制离散类型算法，提高了算法搜索能力；Abdel-Basset等人[10]提出了一种具有勘探开发优势的多目标均衡优化算法，采用存档策略保存最优解并通过拥挤距离方法来保留非主导解的多样性，从而提高了算法的搜索和开发能力；Mousa等人[11]将基于混沌理论的局部搜索算法引入到EO算法中，提出了一种基于混沌搜索的均衡优化器算法，提高了算法的局部搜索能力；Wunnava等人[12]提出了一种自适应均衡优化算法，通过对非性能搜索个体施加分散性自适应决策，提高了算法全局搜索能力和多样性；Too等人[13]提出了一种基于通用学习的均衡优化算法，利用一种通用的学习策略，使个体能够从不同维度的潜在候选对象中学习，从而帮助算法逃脱局部最优值并探索更多区域。

分析以上学者的研究经验可知，找到一种简单有效的策略提升EO算法的性能是必要的，因此，本文针对EO算法存在的上述问题，提出一种融合振荡禁忌搜索的自适应均衡优化算法。首先，在初始化时结合精英反向学习策略贪婪保留原始种群和精英反向种群中的较好个体，提高种群初始化质量，加快种群收敛；然后，引入自适应调整收敛因子，平衡算法的搜索能力，提高算法的收敛精度；最后，引入融合振荡算子的禁忌搜索策略，利用禁忌表的记录功能和振荡算子削弱局部极值点对算法的影响。通过10个基准测试函数及其Wilcoxon秩和检测和部分CEC2014测试函数的仿真实验结果验证了CfOEO算法的优越性。

1 EO算法介绍

EO算法来源于一个描述容器内进出物质质量平衡的一阶常微分方程，方程描述了容器内质量随时间变化的规律，其数学模型如式（1）所示：

式中，V表示容积；C表示浓度；Q为单位时间内进出的容量流率；Ceq为平衡状态下的浓度；G表示质量生成速率。分析式（1）可知，平衡体系中质量随时间的变化等于进入系统的质量加上系统内部产生的质量减去离开系统的质量，当V·dC/dt=0时，系统达到平衡状态。

求解式（1）所示微分方程，得到结果如式（2）所示：

式中，C0为初始浓度；λ表示流动率；F表示求解微分方程所得的指数项系数，其数学模型描述如式（3）所示：

EO算法采用上述浓度C作为个体的解，主要根据式（2）进行迭代更新，其中浓度C、C0和Ceq分别代表当前解、上一次迭代产生的解和当前最优解。算法具体优化过程起源于一个随机初始化的浓度集合，数学模型描述如式（4）所示：

式中，UB和LB分别是搜索空间上下限，表示浓度范围；r i是取值为[0，1]的随机向量，维度与优化问题维度一致。

平衡池（即最优个体）定义如下：

式中，Ceq1、Ceq2、Ceq3、Ceq4和Ceqa分别表示当前迭代前4个最优个体及其平均值，它们被选中的概率相等。

指数项系数和质量生成速率数学模型描述如式（6）和式（7）所示：

式中，a1为常系数；sign表示符号函数；r和λ表示随机向量，取值为[0，1]；Gcp为控制参数，数学模型描述如式（8）所示：

式中，r1和r2为取值[0，1]的随机向量。

综上所述，EO算法位置更新数学模型如式（9）所示：

2 CfOEO算法原理介绍

在基本EO算法中，种群初始化处理采用随机分布的方式，这种随机方式会导致个体前期寻优存在一定的盲目性，使得算法寻优速度慢；其次，算法用来平衡局部搜索和全局搜索能力的指数项系数F采用常系数权重，得到的系数变化趋势趋于常数，并不符合算法迭代过程中的非线性寻优规律；最后，对于加强算法局部寻优能力的质量生成速率G，其有50%几率随机取值为0，具有很大的不稳定性，虽然有一定的几率带领个体跳出局部最优值点，但是并没有考虑寻优过程中个体位置信息的变化。

综上所述，本文针对上述算法原理上的缺陷，引入相应策略进行改善。具体策略介绍如下。

2.1 精英反向学习初始化

文献[14]指出，与随机方法相比，找到具有随机方向及其相反方向的候选解为寻找未知最优解提供了更高的机会。为了提高算法搜索能力，加快算法前期收敛速度，本文引入精英反向学习策略初始化种群，定义X i=(X i,1,X i,2,…,X i,d)为搜索空间内的一个点，其中d为优化问题的维度，则其反向点X′i定义如式（10）所示：

式中，UB和LB分别为搜索空间的上界和下界。

然而，粒子自身反向解受固定的搜索空间边界限制，导致反向点较为发散地分布在搜索空间。因此，本文引入精英反向解，通过精英个体构成动态边界，使反向解分布在空间较优位置，初始个体Xi的精英反向解定义如式（11）所示：

式中，r为取值[0，1]的随机数；a i和b i分别表示Xi在维度d上的最大值和最小值。当精英反向解超出动态边界，则重置反向解，如式（12）所示：

最后，通过贪婪策略保留当前个体和精英反向个体中较优的个体组成新的初始化种群。

2.2 自适应调整收敛因子

收敛因子在目标函数优化中起着很重要的作用，合适的收敛因子能够加快算法收敛，提高算法收敛精度。针对EO算法寻优过程中收敛速度慢、精度不高的问题，引入一种自适应调整的收敛因子，在算法迭代前期，种群全局搜索最优解，此时应该给予足够的搜索空间发散种群，因此给予一个较大的收敛步长有利于算法的开发；在算法迭代中后期，算法逐渐收敛，个体开始进行局部搜索，此时给予一个较小的收敛步长有利于算法进行局部探索。此外，引入收敛因子速率下降调节算子Q，可自动调节收敛因子下降速率，自适应可调整收敛因子Cf的数学模型描述如式（13）所示：

式中，Tm为最大迭代次数；Cm表示收敛因子的初始值；α为常量系数；Q为控制参数。当Q取值为1.0、2.5和5.0时的收敛因子对比曲线如图1所示。

图1 收敛因子曲线图Fig.1 Feedback factor curve

由图1可知，改进的收敛因子曲线的下降速率随着调节因子Q的增大而增大。在具体算法调试中，Q值的选取不宜过大也不能太小。Q值太大可能会导致算法前期收敛过快，算法开发能力减弱从而陷入局部极小值点；而Q值太小则不能体现收敛因子在平衡算法搜索能力上的优势，算法收敛速度变慢。为了平衡算法的搜索能力，本文经过大量实验分析，最后选取Q=2.5最为合适。

2.3 振荡禁忌搜索策略

禁忌搜索（tabu search，TS）开创了搜索过程中存储功能的系统性探索，是用于全局搜索的一种启发式过程，为多种类型的组合优化难题提供了有效的解决方案[15]。禁忌搜索思想的核心是禁忌表，禁忌表的存储功能可以避免算法迂回搜索，提高算法应对复杂优化问题的能力。同时，禁忌搜索策略的赦免机制保证了算法对于优质资源的利用，在提高算法多样性的同时提高算法的全局搜索能力。禁忌搜索策略源于一个当前解Fp和解的搜索空间N，在当前解的搜索空间内迭代产生多个候选解F={F1,F2,…,F n}（n为优化问题所需迭代次数），当候选解属性优于当前解，则此候选解为非禁忌对象，用它代替当前解，并加入禁忌表；若候选解存在于禁忌表中或劣于当前解，则保持当前解不变。l决定禁忌表的容量大小，当禁忌对象超过禁忌长度l，则赦免最初的禁忌对象，用新的禁忌对象替代，以此充分利用优质解。

综上所述，为了提高EO算法的全局搜索能力，改善EO算法易早熟收敛的问题，本文采用禁忌搜索策略更新位置，同时引入振荡算子，当候选解出现在禁忌表中，说明算法存在迂回搜索，因此对位置更新施加振荡，以提高算法多样性。振荡算子o数学模型描述如式（10）所示：

式中，r1、r2和r3都是取值为[0，1]的随机数；Tm为最大迭代次数。由式（10）可知，迭代前期，振荡因子较大，提高了算法搜索范围，增加了算法多样性；迭代后期，振荡因子较小，从而扩大了最优解影响，增加了算法勘探能力。

2.4 CfOEO算法实现过程

综上改进策略，CfOEO实现流程图如图2所示。

图2 CfOEO实现流程图Fig.2 CfOEO implementation flowchart

CfOEO算法实现步骤如下所示：

步骤1参数初始化：设置搜索上下界UB、LB，种群规模N，最大迭代次数Tm，维度d，生成速率控制参数Gcp和常系数a1、a2。

步骤2初始化种群：随机生成种群，计算精英反向种群，贪婪保留较优个体。

步骤3计算个体适应度值，记录较优个体，生成平衡状态池Ceq,pool。

步骤4根据式（9）更新候选解位置。

步骤5根据禁忌搜索策略对候选解进行禁忌操作。

步骤6引入振荡算子对存在于禁忌表中的候选解进行振荡操作。

步骤7判断结束条件，若满足迭代条件则算法终止，否则重复步骤3~步骤6。

步骤8输出最优值，算法结束。

3 仿真实验与结果分析

3.1 参数设置说明

仿真实验采用的计算机配置为Intel Core i5-7500U，32 GB内存，64 bit操作系统，计算环境为Matlab2016（a）。本文选取基本灰狼优化（GWO）算法、蜉蝣算法（mayfly algorithm，MA）、黏菌算法（slime mould algorithm，SMA）以及EO算法与CfOEO算法进行寻优实验对比，基本参数统一设置为：最大迭代次数Tm=500，低维维度d=30，高维维度d=200，种群规模N=30。各基本算法内部参数设置如表1所示。

表1 算法参数设置Table 1 Algorithm parameter setting

3.2 基准测试函数介绍

本文采用10个基准测试函数对CfOEO算法进行寻优性能测试，其中f1~f5为单峰测试函数，f6~f9为多峰测试函数，f10为固定维度测试函数，基准测试函数相关信息如表2所示。

表2 基准测试函数介绍Table 2 Introduction to benchmark functions

3.3 本文各改进策略仿真分析

本节分别对本文提出的三个策略进行性能分析，其中CEO算法是本文引入精英反向学习初始化的EO算法，CfEO算法是本文引入自适应调整收敛因子的EO算法，OEO算法是本文引入振荡禁忌搜索策略的EO算法。统一仿真实验数据为：维度d=30，最大迭代次数Tm=1 000，种群规模N=30，其他固定参数由表1给出，各算法独立运行30次取平均值和标准差。

3.3.1 CEO算法性能分析

本文在初始化中引入优化问题的适应度评价函数，通过适应度函数评价随机种群与其精英反向种群的位置，并贪婪保留较优位置，从而加快算法收敛。为了验证CEO算法的性能，选取单峰测试函数f1和多峰测试函数f8进行仿真实验，实验结果如图3所示。

图3 CEO算法与EO算法平均收敛曲线图Fig.3 Convergence curves between CEO and EO

由图3对比结果可知，CEO算法在单峰测试函数f1和多峰测试函数f8上虽然没能找到理论最优值，但是CEO算法的收敛速度明显快于EO算法，说明本文引入精英反向学习初始化策略能有效加快EO算法的收敛速度。

3.3.2 CfEO算法性能分析

为了平衡EO算法的开发和探索能力，引入自适应可调整的收敛因子，平衡算法搜索能力，提高EO算法收敛精度。为了验证CfEO算法的性能，选取单峰测试函数f2、f5和多峰测试函数f7、f9进行仿真实验，实验结果如图4所示。

图4 CfEO算法与EO算法平均收敛曲线图Fig.4 Convergence curves between CfEO and EO

由图4结果可知，对于单峰测试函数f2和多峰测试函数f7、f9，CfEO算法能够直接收敛到理论最优值，而对于单峰测试函数f5，CfEO算法的收敛精度优于EO算法，说明收敛因子对于EO算法的搜索能力提升有一定帮助，能提高EO算法收敛精度。

3.3.3 OEO算法性能分析

针对EO算法早熟收敛问题，本文引入禁忌搜索策略并结合振荡算子对EO算法进行振荡禁忌操作，以提高算法规避局部极值点的能力。为了验证OEO算法的性能，选取单峰测试函数f3和多峰测试函数f6、f7以及固定维度测试函数f10进行仿真实验，实验结果如图5所示。

图5 OEO算法与EO算法平均收敛曲线图Fig.5 Convergence curves between OEO and EO

由图5结果可知，对于单峰测试函数f6和固定维度测试函数f10，OEO算法能跳出局部极值点，收敛到最优值，说明振荡禁忌搜索策略能提高算法跳出局部极值点能力；对于f3函数，OEO算法能找到0，说明禁忌搜索对于优质解的利用以及振荡算子的动态调整，对于算法搜索能力的提升也有一定的帮助。

3.4 各改进EO算法性能对比

选取基本EO算法、AEO算法[12]、m-EO算法[16]与CfOEO算法进行基准测试函数寻优性能对比，以验证CfOEO算法的有效性，其中AEO算法是文献[12]提出的自适应均衡优化算法，m-EO算法是文献[16]提出的具有突变策略的数值优化均衡优化算法。实验统一采用维度d=30，最大迭代次数Tm=500，种群规模N=30，各算法独立运行30次取平均值和标准差，实验结果如表3所示。

表3 各改进EO算法性能对比Table 3 Performance comparison of improved EO algorithms

由表3结果可知，相比于其他改进的EO算法，本文提出的CfOEO算法在基准测试函数上的表现优秀，10个基准测试函数都取得了最优精度，其中有7个测试函数能够收敛到全局最优解。对于f5、f6和f8测试函数，虽然CfOEO算法没能找到最优解，但是其收敛精度在各个EO算法变体中是最高的，说明本文改进策略具有一定优势。

3.5 CfOEO算法高维寻优性能测试

为了验证CfOEO算法对于高维度优化问题的处理能力，选取基本灰狼优化（GWO）算法、黏菌算法（SMA）、蜉蝣算法（MA）和EO算法与CfOEO算法进行高维基准函数寻优对比实验。实验数据统一为：维度d=200，最大迭代次数Tm=500，种群规模N=30，各算法内部参数由表1给出，测试函数相关信息由表2给出。为了更直观地分析ISMA处理高维问题的性能，图6给出了在200维时各算法独立运行30次后的适应度平均值收敛曲线。

由图6可知，对于200维度的基准测试函数，CfOEO算法不管是在求解速度和精度，还是对于局部极值点的处理能力上都优于其他基本算法，对于单峰测试函数f1~f4和多峰测试函数f7、f9以及固定维度测试函数f10，CfOEO算法能够收敛到理论最优值；对于f6和f8测试函数，虽然CfOEO算法的求解精度并不是最高的，但是其求解速度明显优于其他算法；而f5函数则体现了CfOEO算法对于局部极值点具有一定的规避能力。本文提出的CfOEO算法在高维问题的处理上具有明显的优势。

图6 基准测试函数平均收敛曲线（200维）Fig.6 Function average convergence curves（200D）

3.6 Wilcoxon秩和检测

Wilcoxon秩和检测常用来对比两组数据之间的差异，并分析这些差异，以确定它们是否在统计上存在显著不同。本文将EO算法、黑猩猩优化算法（chimp optimization algorithm，ChOA）、PSO算法、CEO算法、CfEO算法和OEO算法与CfOEO算法进行12个基准测试函数上的Wilcoxon秩和检测对比分析，以验证CfOEO算法寻优结果在统计学上的优势。其中CEO算法、CfEO算法和OEO算法分别是本文3个单独改进策略与EO算法形成的变体，当计算结果p＜5%时，可以被认为是拒绝零假设的有力验证[17]。结果+、-和=分别表示CfOEO算法秩和统计结果优于、差于和等于对比算法，NaN表示没有数据进行对比，Wilcoxon秩和检验结果如表4所示。

由表4结果可知，除了没有数据对比情况外，CfOEO算法相较于其他算法的Wilcoxon秩和检测结果p值基本上都小于5%，说明CfOEO算法对于基准测试函数的优化结果在统计学上具有很大的优势，验证了CfOEO算法的鲁棒性。

表4 Wilcoxon秩和检验结果Table 4 Wilcoxon rank sum test results

3.7 CEC2014测试函数寻优对比

为了进一步验证CfOEO算法处理具有复杂特征问题时的鲁棒性，本文选取部分具有复杂特征的CEC2014单目标优化函数进行寻优对比分析，其中包括单峰（UF）、多峰（MF）、混合（HF）和复合（CF）类型函数，函数相关信息如表5所示。本文将CfOEO算法与标准PSO算法、SCA算法、L-SHADE算法和本文引入振荡禁忌搜索的EO算法（OEO算法）进行对比。其中，L-SHADE算法在CEC2014测试函数中表现卓越，常用来进行对比实验。实验参数取种群规模N=50，维度d=30，最大迭代次数Tm=2 000，每个函数独立运行50次取平均值和标准差。其中L-SHADE算法的数据来源于文献[18]，CfOEO算法运行结果及与其他算法对比如表6所示。

表5 部分CEC2014函数介绍Table 5 Part of CEC2014 function

表6结果展示了CfOEO算法在CEC2014测试函数上的优秀表现，除了单峰CEC03函数，CfOEO算法在其他7个测试函数上都取得了最优精度。对于CEC05、CEC12和CEC19测试函数，CfOEO算法基本收敛到了理论最优值；对于复合特征CEC28和CEC30函数，CfOEO算法寻优标准差为0，说明其对于复合特征函数寻优稳定性很高。上述CEC2014测试函数寻优结果分析说明，本文提出的CfOEO算法对于具有复杂特征的函数寻优同样具有很大优势，验证了CfOEO算法的鲁棒性。

表6 CEC2014函数优化对比Table 6 CEC2014 function optimization comparison

3.8 CfOEO算法时间复杂度分析

CfOEO算法时间复杂度主要由精英反向学习初始化种群、自适应收敛因子和振荡禁忌搜索策略组成。设基本EO算法的时间复杂度为O(N×d×Tm)，其中N、d和Tm分别表示种群规模、优化问题维度大小和最大迭代次数。

（1）计算精英反向种群时间复杂度为O(N×d×Tm)，因此反向学习初始化种群的时间复杂度为O(2N×d×Tm)；

（2）设计算自适应收敛因子所需时间为t1，则引入自适应收敛因子时间复杂度为O(N×d×T m+t1)；

（3）设计算振荡算子所需时间为t2，禁忌表长度为l，振荡禁忌搜索策略时间复杂度为O(N×d×T m+t2+N×d×T m×l)。

综上所述，虽然CfOEO算法的时间复杂度有所增加，但是与EO算法属于同一个数量级，这种时间复杂度的增加在可以接受的范围内，并且通过上面实验分析可以看出CfOEO算法的性能是卓越的。

4 结束语

为了改善EO算法存在的搜索能力弱、易受局部极值点影响的问题，本文提出一种融合振荡禁忌搜索的自适应均衡优化算法，通过引入精英反向学习策略初始化种群提高初始化时种群的质量；采用自适应可调整的收敛因子，以平衡算法的搜索能力；考虑到禁忌搜索策略强大的全局管理能力，引入融合振荡算子的禁忌搜索策略，提高算法跳出局部极值点的能力，也加快了算法收敛。最后，通过10个基准测试函数和部分CEC2014测试函数仿真实验以及基准测试函数Wilcoxon秩和检测结果验证了CfOEO算法的优越性。下一步工作考虑将CfOEO算法应用到实际工程设计问题中，进一步验证CfOEO算法相对于其他算法的优越性。