优化算法测试函数综述及应用分析

1. 引言

自2009年以来，信息通信技术发展迅猛，全球数据量爆炸式增长，人类历史从互联网时代迈向大数据时代 [1]。面对海量、复杂的数据，由于大数据的5V特性 [2]，即Volume (数据体量大)、Variety (数据类型多样)、Value (数据价值密度低)、Velocity (数据产生速度快)、Veracity (数据真实性)，对于大数据环境下的实际应用问题，很多传统的优化算法已不适用。因此，算法改进孕育而生，通过改进传统的优化算法，以适应新时代下诸多的生活和生产问题。与此同时，优化算法测试函数也随即产生，优化算法测试函数作用在于通过仿真实验验证算法改进后是否达到预期的效果。

本文主要介绍常见的5个优化算法测试函数及使用标准差分进化算法计算测试函数。测试函数包括Ackley函数 [3]、Griewank函数 [4]、Rastrigin函数 [5]、Schaffer函数和Sphere函数 [6]。

2. 优化算法测试函数

2.1. Ackley函数

Ackley函数是由指数函数加上放大的余弦函数所得的一种连续型实验函数 [7]，余弦波进行调制以形成波峰或波谷，从而使函数图形表面波动，由于Ackley函数的独特性，导致Ackley函数在寻找全局最优解过程中不可避免地陷入局部最优解的陷阱，因此Ackley函数被广泛用于优化算法的测试，以验证优化算法寻找全局最优解的能力 [8]。Ackley函数数学公式如式(1)所示：

$f\left(x\right)=?20{\text{e}}^{?0.2\sqrt{\frac{{\displaystyle {\sum }_{i=1}^d{x}_i^2}}{d}}}?{\text{e}}^{\frac{{\displaystyle {\sum }_{i=1}^d\cos \left(2\text{π}{x}_i\right)}}{d}}+22.71282$ (1)

其中， $x_i\in \left[?32.768,32.768\right]$ ，Ackley函数在三维空间的图像如图1所示。

从图1中可以看出其特征，Ackley函数在实数范围内是一个多峰函数，存在多个局部最优解和一个全局最优解。观察图1的图像特点，图像外部较为平坦，中心有一个大孔，越靠近中心，即越接近全局最优解，这将会给优化算法寻找全局最优解带来困难，使优化算法容易陷入局部最优解，但是也能很好的考验优化算法寻找全局最优解的能力。

2.2. Griewank函数

Griewank函数于1981年被德国洪堡大学(Humboldt University)的Andreas Griewank作为测试函数首次提出，现在Griewank函数已成为进化计算大会(CEC)中的典型多模态测试函数，并被广泛应用于测试最先进的全局优化算法及改进算法，如差分进化(DE)、粒子群优化(PSO)、模拟退火(SA)等 [9]。

Griewank函数是一个典型的多峰函数，全局最小值是唯一，位于原点，存在大量局部极小值，其复杂结构容易使优化算法陷入局部最优解。n阶的Griewank函数定义如式(2)所示：

$f_n\left(x_1,x_2,x_3,?,x_n\right)=1+\frac{1}{4000}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_i^2}?{\displaystyle \underset{i=1}{\overset{n}{\prod }}\cos \left(\frac{x_i}{\sqrt{i}}\right)}$ (2)

其中， $x_i\in \left[?600,600\right]$ ，Griewank函数在三维空间中的函数图像如图2所示：

当n=1时，Griewank函数在二维平面上的函数图像如图3所示：

从图2和图3中可以看出Griewank函数广泛存在局部最优解，并且它们是规则分布的。并且从Griewank函数二维平面图中还可以看出，在x=0的情况下，Griewank函数收敛至全局最优解，且全局最优解为0，即全局最小值等于0。

2.3. Rastrigin函数

Rastrigin函数是一个非凸、具有多个局部极小值的多峰函数，最早由Rastrigin提出，由Mühlenbein等人 [10] 推广。Rastrigin函数因搜索空间大，存在大量局部极小值，求其全局最小值是一个相当棘手的问题，故被用作优化算法的性能测试问题，被广泛应用在优化算法的测试过程中。Rastrigin函数是高度多模态的，但最小值的位置是规则分布的。n阶Rastrigin函数的定义如式(3)所示：

$f\left(x\right)=10n+{\displaystyle \underset{i=1}{\overset{n}{\sum }}\left[x_i^2?10\cos \left(2\text{π}{x}_i\right)\right]}$ (3)

其中， $x_i\in \left[?5.12,5.12\right]$ ，Rastrigin函数在三维空间中的函数图像如图4所示：

当传统的基于梯度的算法被用来计算Rastrigin函数，寻找该函数的全局最优解，是十分困难的，因为Rastrigin函数具有非常多的局部极小点，所以这也是该函数被用来测试优化算法的原因之一。

2.4. Schaffer函数

Schaffer函数是一个二维的多峰复杂函数，该函数由J. D. Schaffer等人提出。Schaffer函数在其收敛范围内存在无数个极小值点，只有一个全局最小值，在 $x_1=x_2=0$ 处取得全局最小值；该函数 [11] 因其强烈振荡性质及其全局最优点被无数局部最优点所包围的特性使得一般算法很难找到其全局最优点，故常被用于优化算法性能检验。Schaffer函数定义如式(4)所示：

$f\left(x\right)=0.5+\frac{{\sin }^2\left(x_1^2?x_2^2\right)?0.5}{{\left[1+0.001\left(x_1^2+x_2^2\right)\right]}^2}$ (4)

其中， $x_i\in \left[?100,100\right]$ ， $i=1,2$ 。Schaffer函数在三维空间中的函数图像如图5所示：

从图5中可以看出，Schaffer函数三维图像四周较为平坦，中心部分呈现一个两极分化，存在极大值和极小值，具有强烈震荡的性态。实验证明，Schaffer函数也存在多个局部最优解，在寻找到全局最优解是有一定难度，但是在帮助测试优化算法具有不错的性能。

2.5. Sphere函数

Sphere函数是一个简单的单峰函数，只存在全局最优解，不存在局部最优解，因此可利用该函数可以较好的测试出优化算法的收敛速度。Sphere函数定义如式(5)所示：

$f\left(x\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_i^2}$ (5)

其中， $x_i\in \left[?5.12,5.12\right]$ ， $i=1,2,3,?,n$ 。Sphere函数在三维空间中的函数图像如图6所示。

从图6中可以得出，Sphere函数三维图像是一个连续的、凹的和单峰的函数图像；并且从式(5)中可以得知，当x=0时，Sphere函数收敛至全局最优解，即全局极小值等于0。

3. 标准差分进化算法计算测试函数

3.1. 标准差分进化算法

3.1.1. 定义

差分进化算法(Differential Evolution Algorithm, DE)是一种高效的全局优化算法，其主要求解的问题是实数优化问题。差分进化算法是一种模拟生物进化的概率模型，在每一代种群的进化过程中，每个个体矢量作为目标个体一次，算法在不断进化计算之下，创造和存储适应环境的优质个体，并用全局最优解方案指导算法搜索过程。

3.1.2. 进化流程

差分进化算法具体进化流程如下：第一步是确定差分进化算法的控制参数，并且确定适应度函数；第二步是随机创建初始种群；第三步是计算初始种群中每个个体的适应度；第四步是确定算法是否达到终止条件或者进化代数达到最大，差分进化算法的终止条件是用于确定循环进化代数结束的一个标记，在算法计算优化问题过程中，是判断最优解诞生的一个重要依据 [9]；第五步是进入变异操作阶段，得到变异个体，然后把变异个体代入交叉操作进行计算，得到中间种群；第六步是在原种群和中间种群中选择个体，得到新一代高质量的种群；第七步是进化代数t=t + 1，转至第三步，以此循环 [12]。

3.2. 计算步骤

3.2.1. 测试函数MATLAB程序

首先正确键入这5个优化算法测试函数的MATLAB程序，调用function模块，并将这五个优化算法测试函数的程序文件分别命名为ackley.m、griewank.m、rastr.m、schaffer2.m和sph.m，便于在算法主程序中调用，如下表1~5所示：

3.2.2. 标准差分进化算法MATLAB程序

正确的键入标准的差分进化算法 [13] 主程序，其中设置算法参数种群数量NP=50，变量的维度D=20，最大进化代数G=1000，缩放因子F=0.6，交叉概率CR=0.9，然后再根据不同优化测试函数 [14] 的变量取值范围设置变量的界限，如表6所示：

3.2.3. 标准差分进化算法计算测试函数

使用标准的差分进化算法调用测试函数程序 [15]，独立计算5个优化测试函数，算法每次计算循环运行20次，取其平均值，输出目标函数收敛曲线图如图7所示。

5个优化测试函数在算法改进中的应用方向如表7所示。

3.3. 计算结果分析

在图7中，除了图7(c)外，其余4个优化算法测试函数均能在有限进化次数内收敛至全局最优解，而优化测试函数Rastrigin未能收敛至全局最优解，是因为Rastrigin函数本身是一个高度多模态的具有多个局部极小值的多峰函数，并且标准差分进化算法在计算函数时，设置的变量维度为20维，在一定程度上提高了算法寻优的难度，因此Rastrigin函数未能在有限的进化次数内收敛至全局最优解。在其他实验环境不变的情况下，调整算法中的变量维度，调至10维，以及增加算法进化次数，再次计算Rastrigin函数，得出Rastrigin函数收敛曲线如图8所示：

由此可见，标准差分进化算法程序能准确的计算优化问题。并且从5个优化测试函数的收敛曲线中发现，收敛曲线在往下收敛的过程中，曲线呈现出时而水平向前时而垂直向下的状态。实验证明，在函数曲线水平向前时，因为差分进化算法在寻优过程中，因此导致优化测试函数收敛到局部最优解，正处在函数的某个局部最优解范围内进行种群进化；在函数曲线垂直向下时，因为差分进化算法在函数局部最优解进化过程中，跳出了该局部最优解的范围，进入了优化测试函数的下一个最优解(若函数曲线在之后的进化过程中保持水平直线向前，该最优解则为全局最优解；若在此后的进化过程中仍有垂直向下的状态，该最优解则仍为局部最优解)。函数收敛曲线呈现这样的状态完全符合优化测试函数的特征。

基金项目

《基于重点对象特征及行为模式分析的“智慧监护”平台研究及体系应用》，2020年度贵阳市国家创新城市“百城百园”行动项目，贵阳市科技局(筑科项目[2020] 22号)。