一种新的基于邻域结构的骨干正余弦算法

赵永奇，邹 锋，陈得宝

(淮北师范大学物理与电子信息学院，安徽淮北235000)

目前，智能优化算法在越来越多的领域得到应用，并取得了一系列的丰硕成果。研究人员常用的传统智能优化算法包括遗传算法(GA)[1]、粒子群算法(PSO)[2]、萤火虫算法(GSO)[3]等。随着需要优化的问题越来越复杂，在求解这些问题的过程中，传统优化算法暴露出很多自身的缺陷。因此，研究人员开始结合其他算法或者学习策略，通过其他算法或策略的优势来弥补原始算法的不足，从而提高算法的性能。

澳大利亚格里菲斯大学的MIRJALILI[4]在2016年提出一种新型的智能优化算法——标准的正余弦算法(sin cosin algorithm，SCA)。该算法利用随机参数和自适应参数很好地平衡算法的探索阶段和开发阶段。SCA的参数较少，位置更新方程简单，易于实现，收敛速度快，但也存在着计算精度低，后期收敛速度慢等缺点。对此，陈聪[5]引进量子进化的相关理论，利用量子位对个体进行编码，个体对最优解的搜索通过量子旋转门来完成，通过量子门实现个体的变异，从而提高算法的性能。HATHIRAM NENAVATH[6]通过正余弦算法和教学优化算法相结合的方式，前期利用正余弦算法实现全局探索，后期利用教学优化算法实现局部搜索，有效地实现全局搜索和局部搜索的平衡。

针对正余弦算法计算精度低，容易陷入局部最优解，后期收敛速度慢等问题，本文提出一种基于邻域结构的骨干正余弦算法(bare bone sine cosine algorithm based on neighborhood structure，BBNSCA)。首先，建立环形邻域模型[7]，确定每个个体的邻域。然后，利用全局最优解和邻域最优解通过高斯采样[8]产生新的个体，保证种群的多样性。最后，引入线性递减的随机权重系数，提高随迭代次数的增加而增加高斯采样的权重，避免算法陷入局部最优解。

1 正余弦算法

在求解优化问题时，SCA的主要思想是，首先在目标空间中随机产生m个个体的位置，并用Xi=(Xi1,Xi2…,Xi dim)T表示第i(i=1,2,…,m)个个体的位置，其中dim为个体的维度，第t代个体经过最好的位置表示为Pdim，其位置更新方程为：

(1)

(2)

其中，a为常数，一般取2，t为当前迭代次数，T为最大迭代次数。

在SCA中，参数r1具有平衡算法探索和开发的能力。当r1>1时，下一代个体出现的位置在当前解和目标解之外(探索阶段)；当r1<1时，下一代个体出现的位置在当前解和目标解之间(开发阶段)。参数r2决定个体下一代移动的步长。当r3>1时，表明增强当前最优解的作用；当r3<1时，表明减弱当前最优解的作用。参数r4<0.5时，算法按照正弦方式迭代，反之则按照余弦方式迭代。

2 基于邻域结构的骨干正余弦算法

随着对智能优化领域的深入研究，研究人员发现单一优化算法并不能在处理任何优化问题时都能表现出优异的性能。斯坦福大学的WOLPERT和MACREADY[9]在此基础上提出了著名的无免费午餐定理(No-Free-Lunch定理)。No-Free-Lunch定理指出，通过与其他策略相融合的方式，可以利用其他学习策略的优势来弥补本算法的劣势，以此来提高本算法的优化性能。由此，本文提出了一种基于邻域结构的骨干正余弦算法。

图1 环形邻域

2.1 环形邻域结构

邻域结构决定着邻域中的个体如何分配以及个体之间如何相互沟通信息，根据模拟不同的群体行为关系的结构，可以分为环形、星型、金字塔形和冯依曼型[10-12]。环形邻域是一种常见的邻域结构，如图1所示，在环形邻域中，每个个体只与其附近的两个个体交流信息，从而有效地保证种群的多样性，采用环形邻域结构也是为了维持种群多样性的一种有效方式。引入邻域结构的最重要一步是确定每个个体的邻域范围。例如，对于个体i，其邻域的个体为个体i+1和个体i-1，个体之间的信息交流被局限于这个邻域之中。这种环形邻域结构能保证算法对目标空间的不同区域进行充分搜索，从而提高种群的探索能力，而不至于陷入过早收敛的情形，这些邻域结构的优点在实际应用中得到了证明。除此之外，这种环形邻域结构仅与个体的下标有关，可以有效地对目标空间进行搜索。其环形邻域结构数学模型为：

(3)

对邻域结构中的个体进行评价，计算其适应度值，确定邻域中最优个体B，其表达式为：

(4)

2.2 骨干优化思想

研究人员从粒子群优化算法的理论研究中证明，每个粒子的极限收敛于个体最优位置与全局最优位置的加权平均，基于这一理论，研究人员提出了基于高斯采样学习的骨干优化方法。受此思想启发，本文将高斯采样学习引入正余弦算法中，以提高正余弦算法的优化性能。

(5)

2.3 新提出的迭代学习方法

SCA的位置更新方程是利用数学模型的震荡性寻找最优解，前期具有较强的探索能力。但是，在开发阶段，个体一旦陷入局部最优解，就很难摆脱束缚，从而导致算法的多样性降低，寻优精度不高。而高斯采样学习可以提高种群的多样性，避免算法过早收敛。新算法的主要思想是前期利用SCA优秀的探索能力，探寻更广泛的目标区域，在算法后期为了防止陷入局部最优解，利用权重因子调节高斯采样在算法中的比重，使算法具有跳出局部最优解的能力。新算法的迭代方程为：

(6)

(7)

其中，t是当前迭代次数，T是最大迭代次数。

线性递减的权重因子K的作用是随着迭代次数的增加，降低正余弦算法的权重，提高高斯采样学习的权重，更好地平衡算法的探索和开发阶段。权重因子K使新算法在前期继承SCA较强的搜索能力，同时也使新算法具备在后期利用高斯采样学习跳出局部最优解的能力。

2.4 算法步骤

根据标准正余弦算法的优化框架，提出的基于邻域结构的骨干正余弦算法的步骤具体如下：

步骤一：设置种群规模m，空间维度D，最大评价次数E，下界Xmin，上界Xmax。

步骤二：初始化种群的位置和环形邻域，并对种群进行评价确定全局最优解。

步骤三：根据式(1)生成Y，根据式(5)生成Z。

步骤四：据式(6)生成新个体，对个体进行评价。

步骤五：判断新解是否优于当前解，优于当前解即保留，反之，则舍弃。

步骤六：若当前评价次数小于最大迭代次数，则返回步骤三，否则迭代结束。

3 仿真实验分析

为了验证改进的正余弦算法的可行性和有效性，本实验将采用18个有代表性的测试基准函数，将基于邻域结构的骨干正余弦算法与采用相同策略改进的算法(例如BBExp[14]、BBPSO[15]、BBTLBO[16]、BBDE[17])进行比较分析，然后再将新算法与jDE[18]、SaDE[19]、PSOwFIPS[20]、SCA进行仿真比较。

3.1 参数设置

本文所用的18个函数如表1所示。F1(x)～F4(x)是单峰函数，F5(x)～F10(x)为多峰函数，F11(x)～F18(x)分别是F3(x)～F10(x)的旋转函数。本文中所有的实验环境均为：Windows 10操作系统，主频为3.2 GHz，RAM为8 GB，开发工具为MATLAB R2015b。所有算法的种群大小m都为40，分别在维度D=30和D=50的情况下进行仿真实验，以函数值为算法的适应度值，最大函数评价次数(5 000*D)作为算法的终止准则。

其他算法的参数均来自参考文献，相关参数如下所示：

jDE[21]：缩放因子F=0.5，交叉概率Pcr=0.9；

SaDE[22]：缩放因子F满足F～N(0.5，0.3)，初始交叉概率Pcr0=0.5，交叉概率Pcr满足Pcr～N(Pcrm，0.1)，学习代数L=50；

PSO-wFIPS[20]：惯性权重w=0.729 8.

表1 18个基准测试函数

3.2 结果分析

为了验证新算法与采用相同策略改进的算法(例如BBExp、BBPSO、BBTLBO、BBDE)之间的优劣，分别对30维函数进行实验，每种算法独立运行10次，记录各个算法对应各个函数所得到的最优解(best)、平均值(mean)、标准差(Std)进行统计分析，实验结果如表2所示。由于部分基准函数的收敛曲线比较相似，图2中仅给出有代表性的收敛曲线。在下面叙述中，用F1～F18代表F1(x)～F18(x)。

表2 30维函数测试结果

续表

注：带*数据表示最好结果。

为了多方面验证新算法的性能，将新算法与jDE、SaDE、PSOwFIPS、SCA在50维度的情况下对18个基准函数运行10遍，进行仿真实验，记录各个算法对应各个函数所得到的最优解、平均值、标准差并进行统计分析，结果如表3所示。图3为具有代表性的函数平均适应度值变化图。

分析表3中记录的实验数据和图3的平均适应度值变化图，可得到以下结论：对函数F1、F3、F6～F9、F11、F13～F17，从最优解、平均值、标准差这3个性能指标方面分析可以得到新算法的性能优于其他4种算法。从函数F2、F4、F5、F10、F12、F18的实验结果可知，新算法的性能与jDE和SaDE相当，但依然优于PSOwFIPS和SCA。由此可得，新算法的平均性能优于jDE、SaDE、PSOwFIPS、SCA，且相较于基本SCA算法的求解精度和收敛速度都有较大程度的提高。

对于表2中的实验结果以及图2中的收敛曲线，本文将从最优解、平均值、标准差这3个性能指标进行分析：(1)从最优解分析可知，对于函数F1、F3、F6～F17，新算法的最优解优于其他4种算法，且对于函数F1、F3、F6～F9、F11～F12、F14～F17，新算法的最优解得到了理论上的最优值；(2)从平均值可以分析，对于函数F1、F3、F6～F9、F11、F13～F17，新算法的平均值优于其他4种算法，且对于函数F1、F3、F6～F9、F14～F17，新算法的平均值达到理论上的最优值，由此可知新算法的求解精度优于其他算法；(3)对标准差分析可知，对于函数F1、F3、F5～F9、F11、F13～F17，新算法的标准差优于其他4种算法，这说明新算法的鲁棒性优于其他4种算法，性能比较稳定，能够很快地收敛到最优解。

图2 30维部分函数平均适应度值变化图

函数性能指标测试结果jDESaDEPSOwFIPSSCABBNSCAF1best3.81E-89 8.12E-85 6.39E-07 3.17E-08 0.00E+00*mean1.45E-85 2.50E-78 1.20E-06 2.58E+04 0.00E+00*std4.48E-85 5.48E-78 3.79E-07 34 958.49 0.00E+00*F2best7.48E-02*2.25E-01 1.82E+03 1.41E+05 1.43E+01 mean2.70E-01*4.30E-01 2.47E+03 2.33E+05 2.65E+01 std0.136 01*0.193 690 289.841 3 77 987.26 12.474 45 F3best1.74E-90 1.36E-88 1.87E-07 6.64E-07 0.00E+00*mean5.64E-86 2.54E-77 3.38E-07 3.13E+02 0.00E+00*std1.24E-85 7.93E-77 1.50E-07 2 309.106 0.00E+00*F4best3.68E-05*4.81E-05 5.90E+00 1.65E+03 1.68E-03 mean1.87E-04*3.76E-04 1.03E+01 2.91E+04 8.66E-03 std0.000 22 0.000 311*2.620 800 654 406.0 0.006 404 F5best19.675 5*39.494 73 44.635 27 1 375.998 39.584 78 mean21.543 0*42.545 78 45.108 67 1.39E+04 39.901 59 std1.412 26 1.800 157 0.253 649 4 548.549 0.231 145*F6best7.11E-15 3.55E-15 1.45E-04 1.03E-06 0.00E+00*mean9.24E-15 6.04E-15 1.87E-04 1.06E+01 0.00E+00*std3.43E-15 1.72E-15 2.79E-05 10.976 86 0.00E+00*

续表

注：带*数据表示最好结果。

图3 50维部分函数平均适应度值变化图

4 结语

综上所述，本文提出了一种基于邻域结构的骨干正余弦算法，既保留了SCA的全局搜索能力，又利用高斯采样学习增强了算法的多样性，通过线性递减的权重因子较好地调节了高斯采样学习对整个算法的影响，能够较好地平衡算法的探索和开发阶段，避免了算法陷入局部最优解，并利用贪婪选择机制加速算法的收敛速度。通过对18个基准函数的实验结果表明，新算法在求解单峰函数和大部分多峰函数时，在收敛速度、稳定性和求解精度这三方面都有优异的表现。新算法在处理个别复杂函数时，其收敛速度和求解精度不是最好的，但也不是最差的，这也侧面验证了“无免费午餐定理”。总的来说，对标准SCA算法改进的基于邻域结构的骨干正余弦算法是有效的。