求解大规模优化问题的改进正弦余弦算法

张超，杨忆

1）宿州职业技术学院计算机信息系，安徽宿州 234101；2）淮北师范大学计算机科学与技术学院，安徽淮北 235000；3）安徽省认知行为智能计算与应用工程研究中心，安徽淮北 235000

优化问题的求解难度与问题维度规模紧密相关．一般决策变量超过100维的优化问题被定义为大规模优化问题．大规模优化问题的决策变量之间相互关联，使求解问题的难度和计算的复杂度极大增加［1］．求解大规模优化问题时，搜索空间和问题复杂度随着维度的增加呈指数级增长，找到最优解的概率呈指数级下降，极易造成“维数灾难”的局面［2］．在大数据时代的优化问题，如智慧交通控制和智能电网分布式优化等［3］的决策变量更多也更复杂．因此，具有高维决策变量和耗时目标函数的大规模优化日渐成为工程优化中最具挑战性的问题之一［4］．

大规模优化问题具有不可微和非线性等特点，其明确的数学特征越来越难以得到，传统的梯度下降法不能求解［1］．目前解决大规模优化问题的方法主要有协同进化策略和非协同进化策略两类．协同进化策略主要采用分而治之的思想，通过降维分组独立求解［5］．一些基于协同进化框架的大规模优化算法已经被提出，如协同进化的遗传算法［6］和协同进化的差分进化算法［7］等．非协同进化策略主要使用群体智能优化算法将大规模优化问题当作整体进行求解．但传统的群体智能算法如粒子群算法、遗传算法等在求解低维优化问题时表现良好，当优化问题维度大于100维时，性能急剧下降［8］．因此，新的群体智能优化算法或已有算法的变体不断被提出以解决大规模优化问题．陈暄等［3］引入深度神经网络、尺度系数等策略，提出一种改进的狼群算法解决大规模优化问题．WANG等［9］提出一种多策略学习粒子群算法，在种群迭代的不同阶段使用不同的学习策略，提高了算法的搜索能力．龙文等［10］提出一种非线性收敛因子的鲸鱼优化算法，使用非线性收敛因子平衡全局和局部搜索．李煜等［11］提出一种改进花授粉算法，在函数维度达到5000维时收敛精度表现良好．TIAN等［12］提出了一种求解具有稀疏Pareto最优解的大规模多模态多目标优化问题的进化算法．以上大规模优化算法研究的重点都是在解决大规模优化问题时，如何更好地平衡算法的全局搜索与局部开发，保持种群的多样性，提高算法的探索和开发能力，使算法能够有效逃离局部最优解．

正弦余弦算法［13］（sine cosine algorithm，SCA）是一种新颖的基于种群的智能优化算法，自诞生以来受到广泛的关注和研究［14-16］．研究重点主要集中在两个方面：①提高正余弦算法寻优性能的变体和应用；②将正余弦算法作为策略帮助提高其他群体智能算法的寻优性能．在求解大规模优化问题上研究较少．SCA在求解大规模优化问题时随着维度的大幅增长，易陷入“维数灾难”的不足．

本研究提出一种适应于求解大规模优化问题的带Lévy飞行的改进正弦余弦算法（sine cosine algorithm with Lévy flight，SCAL）．SCAL主要做了两方面的改进工作：①将Lévy飞行分布与正弦余弦种群个体位置向量进行对应元素相乘运算，赋予种群中每个个体Lévy飞行能力，从而提高个体在大规模搜索空间的搜索和逃离局部极值的能力；②提出基于个体与全局最优解的空间距离的非线性参数调整方法，对SCA的局部开发和全局探索转换参数r1进行改进，加快算法在高维搜索空间的收敛速度．实验结果表明，SCAL在100、1000和5000维时具有良好寻优性能，能够有效求解大规模优化问题．

1 预备知识

1.1 大规模优化问题描述

大规模优化问题可描述为

其中，F(x)为优化问题的目标函数；min/max表示优化问题的类型，min为最小化问题，max为最大化问题；xi为决策变量；d为决策变量的个数，即问题的维度，讨论大规模优化问题时要求d≥100，通常要达到1000维或以上；xi∈[xmin，xmax]为边界约束．本研究仅对最小化问题进行求解，问题的维度分别设定为100、1000和5000．

1.2 SCA

SCA利用正弦余弦函数的周期性和波动性驱动种群搜索，从而实现寻优的目的．算法首先在解空间内随机初始化种群个体，每个个体都围绕着当前获得的全局最优解，并使用式（2）迭代更新位置．

其中，t为当前迭代次数；tmax为最大迭代次数；a为常量，一般取值为2．

2 基于Lévy飞行的正弦余弦算法

2.1 Lévy飞行

Lévy飞行是一种随机游走模式，在飞行模式中表现出自相似和分形行为，其行走的随机步长服从一个重尾的Lévy分布，通常用一个简单的幂律公式表示，即L(s)～|s|-1-β．其中，β为Lévy分布的形状参数，其值越大，生成的随机步长越小，0＜β≤2，s为随机步长．从数学的角度来看，Lévy分布的简单形式［17］可定义为

其中，μ为传输参数；γ为尺度参数，其值越大Lévy分布越分散．

一般情况下，Lévy分布定义为傅里叶变换形式

其中，k为自由变量；α为尺度参数．

计算这个积分的逆比较困难，除少数特殊情况外，它无解析形式．文献［18］给出了随机步长s的一种计算方法，可通过式（6）进行计算．

其中，u和v分别为符合期望为0，方差分别为和的正态分布随机变量，σv=1，

这里，Γ(·)为标准伽玛函数，本研究设β=1.5．

Lévy飞行的方差(σ2)随时间(t)呈指数级关系，即σ2(t)～t3-β，1＜β≤2，因此，Lévy飞行在未知的大规模空间搜索时更加有效［17］．

2.2 Lévy飞行学习机制

SCA种群中每个个体使用式（2）更新位置，只利用了自身信息xit和全局最优个体pt的信息，就能使种群快速向最优个体靠拢，但这也易导致算法陷入局部最优．因此，本研究让正弦余弦种群每个个体学习都拥有Lévy飞行的飞行能力，利用Lévy飞行在未知大规模空间的较强搜索能力，使改进算法SCAL能够解决大规模优化问题．SCAL种群个体的位置更新公式为

2.3 基于距离的非线性调整策略

参数r1对SCA比较重要，大部分变体都是对其进行改进以提高算法性能．在大规模高维度搜索空间中，当个体离全局最优解较远时，需大步长向全局最优解靠拢，以提高算法收敛速度；而当个体离全局最优解较近时，又需在个体和最优解之间的小空间内进行精细开发．

鉴于此，本研究提出一种新的r1计算方法，基于个体与全局最优解的空间距离自适应地非线性调整，以提高算法求解大规模优化问题的收敛速度．新的r1计算公式为

其中，d为维度；为到第t次迭代全局最优解的第j维．当个体离全局最优解较近时，r1≤1，算法进入局部开发；反之，r1＞1，进入全局搜索．新策略里r1的值包含了全局最优解信息和个体的信息，比基本SCA中单纯给定标量线性递减效果更好．

用两种算法对Schwefel1.2函数（d=1000）寻优为例进行说明，图1直观展示了新的r1计算策略的收敛速度优势．其中，TSCA为测试对比算法，该算法加入了Lévy飞行机制，但仍使用原SCA的r1计算方法．为便于观察，图1对适应度值做了以10为底的对数处理．由图1中的收敛曲线可见，新的r1计算方法能够帮助SCAL算法大幅提高收敛速度，收敛到函数理论极值时能够有效减少迭代代数近500代，因此，在处理大规模优化问题时，SCAL算法可以有效降低算法的计算复杂度．

图1 r1策略收敛速度对比（TSCA为加入了Lévy飞行机制，但仍使用原SCA的r1计算方法，在此仅作为测试对比算法）Fig.1 Comparison of policy convergence speed.For comparison，TSCA uses Lévy flight without new r1 calculation method.

可见，SCAL没有改变SCA的结构，保持了SCA结构简单的优点，算法具体的执行步骤及时间复杂度分析请扫描论文末页右下角二维码查看补充材料1.1和1.2节．

3 仿真实验与结果分析

3.1 测试函数与实验设计

选取14个经典测试函数，包括8个单峰函数Sphere(f1)、Schwefel2.22(f2)、Schwefel1.2(f3)、Step 2(f4)、Quartic(f5)、Elliptic(f6)、Sum squares(f7)、Zakharov(f8)和6个 多 峰 函 数Alpine(f9)、Rastrigin(f10)、Ackley(f11)、Schaffer＇s F7(f12)、Weierstrass(f13)、Cosine mixture(f14)，在100维、1000维和5000维3种高维状态下进行仿真实验，以模拟验证SCAL算法在解决大规模优化问题时的寻优性能．测试函数详情请扫描论文末页右下角二维码查看补充材料表S1．

将SCAL与基本SCA［13］、花授粉算法（flower pollination algorithm，FPA）［19］、粒子群优化（particle swarm optimization，PSO）算法［20］、麻雀搜索算法（sparrow search algorithm，SSA）［21］和鲸鱼优化算法（whale optimization algorithm，WOA）［22］5个经典或新兴的群体智能算法进行比较，以客观评价其处理大规模优化问题的性能．本研究使用6个算法在不同测试函数上独立运行30次，求解后的实验结果的平均值和标准差两个指标来评价算法的寻优性能．

所有算法种群规模均设为20，最大迭代次数设为600，其 他 参 数 设 置 为：SCAL和SCA的r2∈[0，2π]，r3∈[0，2]，r4∈[0，1]．SCA的a=2．FPA转换概率p=0.2．PSO学习因子c1=c2=2，惯性权重w∈[0.9，0.4]．SSA的搜索者占比参数Ppercent=0.2．WOA的常数b=1，收敛因子a从2线性递减到0．

3.2 寻优结果分析

限于篇幅，表1只展示了6种算法在f1—f4函数上，3种高维状态下分别独立进行30次实验的结果．在14个基准函数上的完整实验结果，请扫描论文末页右下角二维码查看补充材料表S2．从表1可见，SCAL在f1—f4函数3种高维度上每次都能成功收敛到函数的理论极值，随着问题规模的快速增长，算法寻优性能保持了较好的稳定性，没有陷入“维数灾难”的局面．而SCA、FPA、PSO和SSA在4个测试函数上均不能收敛到函数的理论极值，并且随着维度的提升，均值和标准差两个指标增长较快，算法陷入“维数灾难”．尤其在f2函数上，当维度为1000和5000时，SCA、FPA和SSA不能对解空间进行任何搜索，鲁棒性较差，而SCAL能求解到该函数的理论极值，寻优优势明显．WOA在f4函数3种高维度上能收敛到函数的理论极值，但在其他3个函数上均不能．

表1 SCAL、SCA、FPA、PSO、SSA和WOA算法在4个基准函数上的实验结果与比较1），2）Table 1 Experimental results and comparison of SCAL with SCA,FPA,PSO,SSA and WOA on four benchmark functions

结合补充材料表S2中的完整实验结果可见，SCAL在f1—f4、f6—f10和f12—f14这12个函数上每次都能成功收敛到函数的理论极值；在f5和f11函数上，SCAL收敛到的最优解优于所有对比算法．SCA、FPA、PSO和SSA在14个函数上均不能收敛到函数的理论极值，求解的精度较低．WOA在f4、f13和f14函数上能收敛到函数的理论极值，但在其他11个函数上均不能．

3.3 寻优性能对比分析

3.3.1 收敛曲线分析

限于篇幅，本研究仅选择测试函数f2、f8和f14，直观展示6种算法在d=1000时的收敛曲线，结果如图2．为方便观察，对算法在所有目标函数上的适应度值做了10为底的对数处理．

由图2可见，SCAL收敛曲线平滑，在f2和f8函数上分别使用约150次和80次迭代即可收敛到函数的理论极值，而在f14函数上只需几次迭代就收敛到函数的理论极值．WOA在f14函数上迭代约220次亦能够收敛到函数的理论极值．其他算法在迭代600次时均不能收敛到函数的理论极值，求解结果离理论极值偏差较大，算法陷入了局部最优．

图2 d=1000时不同算法在测试函数（a）f2、（b）f8和（c）f14上的适应度收敛曲线Fig.2 Fitness convergence curves of different algorithms on（a）f2，（b）f8，and（c）f14 with d=1000.

在图2（a）中无SCA、FPA和SSA的收敛曲线，这是因为它们在f2函数的解空间中不能进行任何搜索寻优，算法陷入了“维数灾难”，SCAL能够找到函数的理论极值，进一步说明了SCAL寻优性能优越．SCAL良好的收敛速度保证了其在处理大规模优化问题时可以有效降低问题的计算复杂度．

3.3.2 算法稳定性分析

图3为6种算法在不同测试函数上，d=1000时30次独立实验的全局最优解的箱线图（限于篇幅，本研究仅展示f1、f3和f6上的结果）．由图3可见，SCAL在不同测试函数上均能收敛到函数的理论极值，最优值分布稳定，算法的鲁棒性较好；SCA、FPA、PSO、SSA和WOA求解的结果离函数理论极值偏差较大，波动性较强，说明算法的鲁棒性较差．

图3 d=1000时不同算法在测试函数（a）f1、（b）f3和（c）f6上的最优适应度箱线图Fig.3 Optimal fitness boxplots of different algorithms on（a）f1，（b）f3，and（c）f6 with d=1000.

3.4 计算复杂度与维度增长关系

求解大规模优化问题时，搜索空间和问题复杂度会随维度的增加呈指数级增长，这要求求解的算法具备较好寻优性能的同时，消耗的时间成本不宜过高，处理问题时的计算复杂度要尽可能小．

表2是SCAL与对比算法中性能较好的WOA，在部分测试函数上，运行600次迭代寻优的平均运行时间．由表2可见，当d=100时，SCAL在5个测试函数上的平均运行时间都比WOA略长；当d增至1000时，目标函数的复杂度大幅增加，SCAL的平均运行时间均明显比WOA短；当d增至5000时，目标函数变得极为复杂，SCAL在所有函数的平均运行时间都远短于WOA．从平均运行时间的增长速度来看，SCAL的运行时间与维度增长之间的比例关系适中，而WOA在d从1000增至5000时，运行时间大幅跃升，验证了本研究所提改进策略的有效性，算法因拥有了Lévy飞行能力的正弦余弦种群，增强了个体的局部开发和逃离局部极值的能力，同时新的r1计算策略大幅提高了算法的收敛速度，有效减少了算法在处理大规模优化问题时的计算复杂度．

表2 SCAL和WOA在不同维度下的平均运行时间1）Table 2 Comparison of the average running time of SCAL with WOA on different d. s

3.5 Lévy飞行参数对算法性能的影响

SCAL的r1参数基于个体与全局最优解的空间距离自适应调整，而r2、r3和r4参数在SCA中是服从均匀分布的随机数．因此，Lévy飞行的参数β是影响SCAL寻优性能的重要参数．为分析参数β对SCAL性能的影响，设d=1000，并取β不同值时，在f1、f3和f6函数上分别独立运行SCAL算法30次，实验结果请扫描论文末页右下角二维码查看补充材料中表S3．由表S3可见，无论β取何值，SCAL都能收敛到函数的理论极值，说明所提改进策略有效．但当β取值分别为0.8、1.0和1.2时，算法在鲁棒性上存在偶尔陷入局部极值的缺陷．当β取值1.5和1.7时，从实验的4个评估指标来看，算法的鲁棒性得到改善，每次均能收敛到函数的理论极值．

4 与其他大规模智能算法的比较

为进一步验证SCAL在解决大规模优化问题时的性能，将SCAL算法与近期出现的4种大规模智能优化算法，包括改进狼群算法（improved wolf pack algorithm，IWPA）［3］、改进花授粉算法（improved flower pollination algorithm，IFPA）［11］和鲸鱼算法的两种改进版本（improved whale optimization algorithm，IWOA）［10］和（modified whale optimization algorithm，MWOA）［23］进行比较．为使比较有意义，将SCAL的种群规模和最大迭代次数设置的更为严苛，分别设为20和200，即SCAL的最大适应度函数计算次数为4×103次．

表3为SCAL、IWPA、IFPA、IWOA和MWOA算法在14个测试函数（d=1000）上进行寻优实验的结果．其中，SCAL来自30次独立实验结果，其他算法结果来源于各自文献；符号“/”前后分别是平均值和标准差．由表3可见，SCAL在严苛的实验条件下，在f1—f3、f5和f7—f9这7个函数上的寻优结果明显好于IFPA算法；在f1—f4、f6、f8、f12和f13这8个函数上的寻优结果好于IWPA算法；在f1、f2、f5—f7、f9和f11这7个函数上的寻优结果好于IWOA算法．可见，SCAL的整体寻优性能比IFPA、IWPA和IWOA算法更好．SCAL在f14函数上的寻优结果好于MWOA；MWOA在10个函数上虽然都能收敛到函数的理论极值，但从最大适应度函数的计算次数看，SCAL为4×103次，MWOA为3×104次，说明SCAL在收敛速度和时间复杂度上优于MWOA．综上，SCAL在求解大规模优化问题智能优化算法中具有一定优势和竞争力．

表3 SCAL、IWPA、IFPA、IWOA和MWOA算法在测试函数（d=1000）上的寻优结果1），2）Table 3 Optimization results of SCAL with IWPA,IFPA,IWOA,and MWOA on test functions in d=1000

结语

针对SCA算法处理大规模优化问题的不足，将Lévy飞行分布与种群个体进行逐元素相乘运算，使用基于空间距离的非线性参数调整策略对r1参数进行改进，生成了一种新的正弦余弦算法SCAL．在14个大规模优化测试函数（维度分别为100、1000和5000）上的实验结果表明，SCAL的寻优性能优于SCA、FPA、PSO、SSA和WOA算法．SCAL求解的精度基本不受维度增长的影响，计算复杂度与维度增长之间的比例关系适中．与IFPA、IWPA、IWOA和MWOA等大规模优化智能优化算法比较的结果表明，SCAL在最大适应度函数计算次数远小于对比算法的情况下，求解的结果整体好于对比算法，在大规模优化算法中具有一定优势和竞争力．在今后的研究工作中将运用SCAL算法解决大规模约束优化问题和实际工程问题．