基于交叉变异机制的正余弦算法

骆舒婷，陈得宝，邹 锋，王苏霞①

（1.淮北师范大学 物理与电子信息学院，安徽 淮北235000；2.淮北师范大学 计算机科学与技术学院，安徽 淮北235000）

0 引言

实际生活中，很多问题都可转化成优化问题. 通常，求最小值的优化问题可以表示为：

如何设计算法准确快速得到问题的最优解，是解决优化问题的关键所在. 相比传统优化方法，群体智能优化模仿自然界生物种群或自然现象的个体或社会行为来寻找最优解，对问题的精确数学模型依赖性不强，相关算法在解决优化问题中得到广泛的应用. 粒子群优化（PSO）［1]已广泛应用于函数优化、图像处理、机械结构优化等领域. 差分进化（DE）［2]也已应用于解决电力系统、时间序列预测、特征选择等领域的优化问题. 近些年，建立在群体基础上的优化算法（如鲸鱼优化算法（WOA）［3].、社会群体优化（SGO）［4]、回溯搜索优化算法（BSA）［5]、碰撞优化（CBO）［6]等）也在不同的优化领域发挥较好的作用.

正余弦算法（SCA）［7]是Mirjalili在2016年提出的一种基于种群的新型优化算法. 该算法更新方程中待确定参数少，实现简单，在一些优化问题中得到较好的应用. 作为一种年轻的优化算法，SCA算法同样具有其它群体智能优化算法的弱点，如收敛速度较慢、易于陷入局部最优解、算法缺乏自适应性等. 目前，对SCA算法性能的改进主要聚焦在两个方面. 一是通过改善更新方法提高算法寻优能力，二是拓展算法应用领域. 第一方面的主要工作有：修改算法操作算子和与其它优化算法混合. Gupta等［8]通过一个扰动率来产生反向种群，并在搜索方程中加入自适应成分，验证其求解全局优化问题的有效性；Rizk［9]针对全局优化问题，提出基于正交并行信息的SCA改进方案；Li等［10]将levy flight策略集成到SCA中，以提高算法的全局搜索能力；在混合算法的研究方面，与水波优化算法结合，很大程度上提高算法的整体优化性能［11]；正余弦算法与差分算法混合，用于目标跟踪［12]；Issa等［13]将粒子群算法的速度和位置更新方程引入到原算法中，提出一种粒子群优化和自适应正余弦算法的混合；Nenavath等［14]混合正余弦算法和教学优化算法，用于求解优化问题和视觉跟踪；Singh［15]提出一种混合灰狼优化和正余弦算法. 在拓展应用方面，Ismael等［16]应用SCA对径向配电系统中的导体进行优化选择，指出SCA在保持指定约束的同时，减少网络损失方面是有效的；Hafez等17]提出一种基于正余弦算法的特征选择系统，该系统在18个数据集上进行测试，与其他搜索方法相比，在不同的评价指标上具有优势；Sahlol 等［18]用SCA 训练一个神经网络模型，提高某种酶的预测精度.

上述对SCA算法的改进方法，主要集中在修改更新方程参数、利用个体变异或部分群体信息提高算法的性能，同时考虑算法多样性、收敛性和自适应性的研究工作相对缺乏. 与其它算法的混合，虽然发挥多种优化算法的优点，但增加算法的复杂性，有时甚至难以确定是哪种操作作用的权重较大，在一些实时性要求较高的问题中，其作用将受到一定程度的限制. 因此，本文在综合考虑这些因素的基础上，在SCA中引入交叉变异机制，利用两种不同的交叉策略，一方面增强算法的自适应性，另一方面通过个体的交叉改善算法的多样性，设计基于最优解引导变异和贪婪选择方法结合，提高算法的收敛速度.

1 正余弦算法（SCA）

正余弦算法是近年来发展起来的一种基于正弦和余弦三角函数数学特性的优化算法，与其它基于种群的优化算法一样，SCA也从一组随机分布的解开始，然后每个解根据以下方程更新它们的位置：

其中，a是常数，在经典SCA算法中取2，t为当前迭代次数，T为最大迭代次数. 更具体的算法过程可参考文献［7].

2 改进的正余弦算法

在基本SCA算法中，个体均依据式（4）进行位置更新. 实践表明，仅以最优个体引导进化能加快算法的收敛速度，但不利于维持种群的多样性，易发生早熟收敛，陷入局部极值. 而且SCA算法在靠近与远离最优解的搜索过程中，几乎完全依赖于随机参数，导致算法的自适应性能较弱. 因此，通过引入自适应的交叉变异机制，减少算法陷入局部极值的可能，同时提高算法自适应性能.

2.1 自适应交叉策略

自适应交叉策略以固定给定概率确定个体是否进行交叉操作，在交叉操作的个体中根据其适应度值确定所采用的交叉策略. 对于较差的个体，采用扰动性更大的交叉操作，两个体按照随机比例交叉，通过较大的扰动增强较差个体的搜索性能；对于较好的个体，将其适应度值按照一定规律作为比例系数来交叉，按照这种操作方法，优良个体所占权重较大，对优良个体有一定的保护作用，有利于加强算法的局部开发能力，更利于寻找局部最优位置. 自适应交叉的具体过程如下：对第i个个体，首先随机生成0到1之间的均匀分布随机数rand，若rand

其中，fi为当前个体的适应度值，fave为种群平均适应度值，α为（0，1）之间的一随机数为种群中一个个体为种群中不同于i的另一个随机选择个体.

若个体适应度值小于群体平均适应度值，说明该个体距离种群中最优个体位置较近，使其按照以适应度值比例为引导的交叉，交叉方式如下：

2.2 变异策略

个体通过交叉操作后，以一定的概率进行变异操作. 本文加入的变异策略不是按照传统的固定的变异概率进行变异，而是根据不同个体的不同维度采用自适应的变异率. 这种变异率使优良个体发生变异的概率小，从而使优良个体得到较好的保持；对较差的个体，想要它们探索到更好的解，因此给它们更多的变异机会，使其更容易满足变异条件，进行变异操作. 实施变异策略取决于变异概率Pm和预设变异概率Psm之间的关系［19]. 它们的定义分别如下：

式中，N为种群大小，D为种群的维度，rand（N，D）为N行和D列的数组，且各元素为（0，1）的随机数.

将种群个体按适应度值大小升序排列，因此排列后第一个个体为最优个体，第二个个体为次优个体，依次类推，最后一个个体为最差个体，因此，pm是线性递减的，当Pm（i）

2.3 改进算法流程

综合以上分析，改进后正余弦算法流程如图1所示.

图1 改进算法流程图

3 仿真实验

选取18 个典型基准函数优化问题对改进的正余弦算法进行测试，18 个典型基准函数来自文献［20]. 为比较新算法与其它算法的性能，对其他算法也进行仿真实验.

3.1 测试函数与参数设置

由于篇幅原因，在18个测试函数中，挑选F2、F4单模函数，F5、F10多模函数，F11、F12旋转函数的实验结果展示如下. 在本实验中，取函数值作为个体的适应度，所有算法种群大小为40，最大评估次数（FES=5000×D）作为算法的终止条件，D为种群的维度. 其它算法的一些特定参数均来自相应的参考文献，如表1所示. 为比较各算法的性能，所有测试均在同一台机器上操作（处理器为Intel（R）Core（TM）i7-6700T CPU@2.80 GHz 2.81 GHz，内存为8 G），采用Matlab R2012b作为仿真软件.

表1 不同算法的相关参数

3.2 结果分析

3.2.1 收敛精度和速度对比实验

表2 30维函数测试结果

表3 50维函数测试结果

为公平比较各算法性能，对同一函数，每种算法独立运行30次，分别对30维和50维函数进行仿真，将改进算法与其它算法进行比较，对所得的最优值（best）、平均值（mean）、方差（std）和成功收敛到可接受解时的平均评价次数（mFEs）进行统计分析，实验结果如表2 和表3 所示，最好结果用粗体标出，表中‘NaN’表示算法在30次运行中都不能收敛到可接受解.

从表2可以看出，在30维函数的测试实验中，对函数F2、F11、F12，ICMSCA的4项指标均优于或等于其它算法；对函数F4，ICMSCA的最优值、均值、标准差这3项指标均优于其它算法，mFEs指标不是最好，但也优于其它部分算法；对函数F10，BSA算法性能略优于其它算法. 可以看出，ICMSCA在收敛精度、稳定性、收敛速度方面均比标准SCA有明显的提高. 与其他算法相比，改进的正余弦算法平均性能也优于其他算法. 为进一步测试改进方法对更高维函数的优化能力，对以上函数进行50维测试，结果如表3所示.

从表3可以看出，ICMSCA 的最优值、均值、标准差在函数F2、F4、F11、F12上均得到理论最优值，IC⁃MSCA在这6个基准函数上的优良率为66.7%（4/6），高于其它算法. 可以看出在高维问题中，ICMSCA同样具有较好的性能，其优势更明显.

为直观地展示所有算法的收敛过程，显示ICMSCA的收敛速度，实验测试不同算法对50维测试函数的平均最优适应度变化，如图2所示.

图2 50维部分函数的收敛效果图

从图2中可以看出，对于单模函数F2，F4，ICMSCA的收敛速度明显快于其它算法；对于多峰函数F5，其收敛速度也快于大部分算法；对于多峰函数F10，收敛速度优势不明显，但也快于原始SCA；对于旋转函数F11，F12，新算法收敛速度快于其它算法. 虽然在个别函数优化实验中，ICMSCA的收敛速度不是最快，但对于单峰函数、旋转函数，ICMSCA的收敛速度都远远快于其它算法. 图2显示，ICMSCA收敛速度较原始SCA算法有明显的提高.

3.2.2 t-test测试

t-test方法通常被用来测试两种算法之间的差异，本文采用显著水平为0.05的双边t-test对结果进行检验. 在50维函数条件下，新算法对于其它算法的T值和P值如表4所示，表中展示18个函数的测试结果. 表中，B、S、W 分别表示改进后的算法性能优于、等于、劣于其它算法的数量，D是B与W的差值，IC⁃MSCA与其它算法之间的较好结果以粗体标出.

表4 新算法对其它算法的t-test结果（50维）

续表4

从表4可以看出，ICMSCA性能优于其它大多数算法，因为D的最小值为1，ICMSCA的平均优良率为

4 结语

本文在标准SCA算法中，引入自适应交叉操作，较大程度提高低于种群平均优良水平的个体搜索最好解的能力，很大程度地增加种群的多样性，减少陷入局部极值的可能. 针对每个个体不同维度，采用最优解引导的变异，改善算法自适应性能的同时提高收敛速度. 通过在30维、50维典型函数优化问题上进行测试，与一些新型算法比较，实验结果表明ICMSCA显著提高原SCA算法性能，ICMSCA在收敛速度、收敛精度、稳定性方面，总体优于其它算法，但在个别复杂函数优化问题上性能略差.

在未来的工作中，将提高ICMSCA的性能解决更复杂的问题，尝试将多种变异交叉策略集成到算法中. 此外，将ICMSCA扩展到其它应用领域，是下一步要开展的工作之一.