基于协方差分析的合作协同进化差分进化算法

2023-02-20王彬任露王晓帆曹雅娟

通信学报 2023年1期

王彬，任露，王晓帆，曹雅娟

（1.西安理工大学计算机科学与工程学院，陕西西安 710048；2.西安理工大学陕西省网络计算与安全技术重点实验室，陕西西安 710048）

0 引言

随着现代科技的不断发展，为了得到最佳的解决方案，需要对工程问题进行数学建模求解，但是许多大规模优化问题在建模之后目标函数不可导，导致传统的优化算法难以求解。为了更好地求解大规模优化问题，研究者不断探索并设计出更加高效的进化算法[1-10]。求解大规模优化问题有2 种主流进化方法，具体介绍如下。

1) 基于非分解的方法

文献[11]提出了多轨道搜索算法，该算法有3 个全局搜索能力和局部搜索能力不同的搜索算子，在进化过程中，使用这3 个搜索算子对目标空间进行搜索，3 个搜索算子在种群进化过程中相辅相成，使全局搜索和局部搜索能够得到均衡。文献[12]提出了多后代采样算法，具体是在种群进化的开始为每种算法分配相同的计算资源，在之后的进化过程中，根据种群中个体的适应度值对每种算法进行评价，然后计算出2 种算法在进化过程中的参与率，根据参与率计算出下一轮优化过程中每种算法被分配的计算资源，不断进化直到计算资源用尽。与其他算法相比，其性能较好，但是多后代采样算法对优化算子的选择比较敏锐，不同优化算子会影响算法的性能。

2) 基于分解的方法

比较典型的是合作协同进化（CC,cooperative coevolution）算法，即对优化问题进行分解，将高维优化问题分解为多个低维优化问题，然后对每个子组件进行优化。合作协同进化算法的性能取决于分解策略，目前研究者已经提出了多种分解策略。文献[13]为了提高遗传算法的性能，首次提出将问题进行分解，使用的分解策略是单维分解和折半分解。单维分解是将M维问题分解成M个一维问题；折半分解是将整个优化问题一分为二。在30 维测试函数上进行测试，对于可分的问题，该算法的性能比遗传算法好；对于不可分的问题，由于在分解过程中2 种策略并没有考虑变量之间的相关性，因此算法性能不如遗传算法好，并且随着优化问题维度的增加，这2 种分解策略会失效。文献[14]将CC框架应用到粒子群优化算法，使用的分解策略是固定分组策略，它将一个M维的优化问题分解成S个k维的问题，即M=Sk，但是这种固定分组策略只对低于30 维的优化问题有效。以上几种分解策略都需要预先设置问题分解的数目，且对高维问题效果不佳。文献[15]提出了随机分组策略，可以对变量进行随机分组，这种分组方法增大了将有关联性的变量分到同一子组件的概率，但是随着有关联性变量的数目增加，随机分组的性能就会下降。文献[16]提出了多层次的协同进化算法用来解决上述问题，设置了一个分解器池，里面不同的分解器代表不同的分组数目，记录每个分解器的性能，在进化过程中根据记录的历史数据自适应地选择合适的分解器，根据分解器中的分组数目，将目标向量分解成设定的子组件。虽然多层次的协同进化克服了随机分组手动设置分组大小的缺点，但是在实际应用中并不广泛。文献[17]提出了差分分组（DG,differential grouping）策略，能够检测变量之间的关联性。DG与其他的分组策略相比具有良好的性能，但它只能检测变量之间的直接相关性，并不会检测间接相关性，在一些测试集上的效果并不理想。文献[18]提出了扩展的差分分组（XDG,extended differential grouping）策略来解决DG 的缺陷。

总之，合作协同进化算法利用分组策略将大规模优化问题进行分解，加快了进化过程的收敛速度，但当决策变量部分可分离或完全不可分时，协同进化的优化效果并不理想，因为合作协同进化只是根据变量之间的相关性将变量进行一个大的分类，并没有考虑分类之后每个子组件中变量之间的相互作用是否影响进化过程。基于上述分析，本文提出了一种基于协方差分析的合作协同进化差分进化算法，简称CC-COV-DE 算法。

本文的主要研究工作如下。

1) 在协同进化利用分组策略对决策变量进行分组之后，针对子组件中变量之间的相关性对种群进化过程的影响进行了分析。

2) 在种群进化开始时对问题进行传统分解，在优化每个子组件时利用协方差分析子组件中变量的数据特征，构造协方差矩阵，根据特征向量旋转原始坐标系，目的是消除组内变量之间的相关性，提高算法的性能。

3) 提出了一种基于协方差分析的合作协同差分进化算法，并在CEC 2014 测试集上与最新的差分进化算法进行了仿真实验，实验结果证实了所提算法的有效性、高效性以及可竞争性。

1 相关工作

1.1 差分进化

进化算法作为元启发式的算法，其思想类似于达尔文进化论，简单易懂，操作容易，可被广泛应用于求解优化问题。差分进化（DE,differential evolution）是经典的进化算法[19]。

差分进化的操作包括突变、交叉和选择，使用一组实参向量xi=(xi1,…,xiD),i=1,2,…,N表示，其中，D是问题的维度，N是种群规模。在种群开始进化之前，随机初始化种群中的个体；在进化过程中，通过突变操作产生突变向量，根据交叉操作产生实验向量，最后通过选择操作为下一代选择适应度值较好的个体。差分进化的操作过程如下。

1) 突变

在进化过程中，通过目标向量xi,G来产生突变向量vi,G。突变计算式为

其中，r1,r2,r3是从[1,N]中随机选择的不同于i的下标，F是比例因子。

2) 交叉

根据目标向量xi,G和突变向量vi,G，生成实验向量ui,G。二项式交叉操作为

其中，rand(0,1)是0 和1 之间的随机数，jrand是从[1,D]中随机选择的决策变量的下标，CR 是交叉率。

3) 选择

使用贪婪选择，在目标向量xi,G和实验向量ui,G之间根据目标函数的适应度值选择较好的个体进入下一代，选择计算式为

由DE 的操作过程可以看出，当控制参数较少时，操作相对简单，可以在低维优化问题中快速找到最优解。

1.2 合作协同进化框架

合作协同进化框架最早在1994 年被提出来解决大规模优化问题，首先将高维问题分解成多个低维问题，然后对子组件进行循环优化。合作协同进化算法的伪代码如算法1 所示。

算法1合作协同进化算法

1) 初始化种群

2) 使用分组策略将原始问题分解为m个低维度子组件

3) seti=1 开始一个新循环

4) 使用特定的进化算法来优化第i个子组件并分配固定数量的评估时间

5) ifi＜mtheni++，转至步骤3)

6) end if

7) if 满足停止条件do

8) 停止循环

9) else

10) 转至步骤2)进行下一个循环

11) end if

1.3 扩展的差分分组策略

协同进化求解大规模优化问题的核心是如何对问题进行分解，即选择什么样的分解策略。

实际工程领域中的优化问题较复杂，扩展的差分分组策略弥补了差分分组在识别相互关系上的缺陷，XDG 可以识别变量之间的2 种交互类型，如图1 所示。类型Ⅰ表示变量之间的直接交互关系，如x1和x2、x2和x3；类型Ⅱ表示变量之间的间接交互关系，如x1和x3。

图1 变量之间的2 种交互类型

变量之间的相关性定义如下。

定义1f(x)是部分可分函数，对于 ∀a,b1≠b2,δ∈R,δ≠ 0，如果满足

则xp和xq不可分离，存在相关性，其中，

定义2在目标函数f(x)中，如果xi和xj是直接相关的，则存在候选解x*满足式（6），直接相关定义为xi↔xj。

如果xi和xj是间接相关的，则所有的候选解满足式(7)。

XDG 根据决策变量之间的相互关系将原问题进行分解。在对问题进行分解时，其可分成3 个阶段。第一阶段是确定变量之间的直接交互，根据定义1 以成对的方式检测变量之间的交互关系。第二阶段是为了确定变量之间的间接交互关系，搜索第一阶段中子组件中的重叠部分，合并公共变量的子组件。第三阶段是将所有可分离变量分配到同一子组件中，XDG 分组之后每个子组件之间是可分离的，但是子组件中的变量是相互关联的。

2 算法设计

2.1 研究动机

1) 高维问题中子组件变量相关增加

求解大规模优化问题最常见的方法是将高维问题分解成低维问题，即根据决策变量的相关性对所求解的优化问题，将有相互依赖关系的变量分配到同一个子组件中，然后对所有的子组件循环进行优化。在问题完全可分的情况下，利用这种方法求解优化问题可以很大程度地提高算法的性能，加快种群的收敛。

如果在没有端元光谱库的情况下，利用该模型进行混合像元分解，通常的做法是先估计出端元的个数，然后提取端元光谱，再结合高光谱遥感图像，进行基于最小二乘或其他方法的丰度估计[14]。然而，基于这种解混方法的思路，如果端元数目估计不准确，会给解混结果造成一定的影响。另外，由于同类地物端元存在光谱变异性，如果每种地物仅用一条标准的光谱定义也会造成结果不精确。为了解决上述问题，需要摆脱传统解混方法思路的束缚，寻找新的解混框架和模型，获取更精确的解混结果。随着端元光谱库的普及以及稀疏表示理论的发展，可以借助端元光谱库对高光谱遥感图像进行稀疏解混，具体介绍如下。

如图2 所示，低维优化问题中，由于维度较低，部分子组件内部变量关联性较低的概率较大，其中，子组件1、子组件2 和子组件4 中的变量有相互依赖关系，子组件3 中的变量在进化过程中不依赖其他任何变量，因而在进化过程中子组件3 的进化速度要比其他组件的进化速度快。

图2 低维优化问题的变量相关

如图3 所示，高维优化问题中，随着维度的增加，子组件中被分配到的变量数目增加，相较于图2中的低维问题，分组之后，每个子组件中变量之间的关联概率增加。

图3 高维优化问题的变量相关

2) 子组件的变量相关性影响协同进化

协同进化在种群的进化过程中并没有考虑子组件中相互作用的变量对进化的影响，利用差分算法对子组件进行优化的过程中，变量之间的相互性会影响子组件的优化。

相关变量对DE 搜索过程的影响如图4 所示。理想情况下，根据DE 的突变计算式在目标空间中产生的突变向量是vi,G，但是向量与向量是相关的，向量的变化会影响向量。在进化过程中，会受的影响，从而产生突变向量vi,G，vi,G相较于vi,G偏离了全局最优向量。

图4 相关变量对DE 搜索过程的影响

3) 采用协方差分析的坐标旋转消除变量相关

基于种群个体分布特征向量的坐标旋转如图5所示。优秀个体往往分布在最优解周围，在假设高斯分布的基础上，利用优秀个体的位置，计算种群的协方差矩阵，估计分布的特征向量和特征值；利用计算出来的特征向量，对原坐标系（X,Y）进行旋转，并重新计算个体在新坐标系（X′,Y′）下的坐标；在新坐标系下，个体的变量相关性降低，进化效率得到提高；将在新坐标系下进化得到的个体映射回原坐标系，计算适用度。

图5 基于种群个体分布特征向量的坐标旋转

2.2 CC-COV-DE 算法设计

在进化过程中，根据变量之间的相关性对变量进行分组，当子组件中相互依赖的变量数目有很多时，会受变量之间的相互依赖牵引，种群在进化过程中很容易陷入局部最优。因此，为了提高算法的性能，提出了基于协方差分析的合作协同进化差分进化算法，在使用分组策略对决策变量进行分组之后，使用协方差分析每个子组件中变量的特征，根据特征向量对坐标进行旋转，消除变量之间的相关性。

CC-COV-DE 算法的流程如图6 所示。

图6 CC-COV-DE 算法的流程

1) 利用XDG 策略根据变量之间的相关性对问题进行分解。

2) 在子组件优化过程中，使用协方差对子组件中的变量进行特征分析，构造协方差矩阵，对原始坐标系进行旋转，使子组件中变量之间的关联性可以消除，从而避免在进化过程中陷入局部最优，导致种群进化过程停滞。

在差分进化优化器中，对于子组件中的M个个体，计算协方差矩阵

其中，cov(i,j)是子组件中M个个体的第i和第j维度的协方差，计算式为

其中，R表示D×D正交矩阵特征坐标系，R的每一行都是协方差矩阵R′表示从特征坐标系到原始坐标系的变换，∧表示由特征值组成的对角矩阵。

在目标空间中，子组件中的个体xi在特征坐标系中可表示为

子组件中的个体使用DE 搜索方程在特征坐标系下生成候选解

其中，r1,r2,r3是从[1,M]中随机选择的。将特征坐标系中的候选解转换到原始坐标系中，有

3) 根据目标函数的适应度值，选出最优的个体进入下一代。

CC-COV-DE 算法如算法2 所示，其中步骤21)～步骤29)是协方差分析的过程。

算法2CC-COV-DE 算法

输入种群规模N，决策变量的维数D，当前种群的更新代数gen，比例因子F，交叉率CR，函数的最大评价次数FESmax

输出评价次数FES，最优值Best

3 实验结果分析

为了评估CC-COV-DE 的性能，本文在CEC 2014 基准测试函数集进行了仿真实验。对比实验表明CC-COV-DE 在解决大规模优化问题的算法性能。

3.1 对比算法

为了证明CC-COV-DE 算法的有效性，本文引入了其他7 个对比算法，分别是基于合作协同进化的差分（CCDE）算法[20]、基于协方差分析的差分进化（COVDE）算法[21]、差分进化（DE）算法[19]、基于自适应维度水平调整框架的差分进化（ADLADE）算法[3]、基于全局数值优化组合策略的自适应差分进化（CSDE）算法[22]、基于时变策略的差分进化（TVDE）算法[23]、基于合作协同进化和协方差的自适应差分进化（A-CC/COV-DE）算法[24]。

3.2 测试函数

CC-COV-DE 在CEC 2014 上进行数值实验，为了确保实验结果的准确性，每个算法在测试函数上独立运行50 次，CEC 2014 的测试函数可以分为4 类。F1～F3：单峰函数，不可分函数；F4～F16：简单多峰函数，F8 和F10 为可分函数，其余为不可分函数；F17～F22：混合函数，不可分函数；F23～F30：复合函数，不可分函数。

3.3 参数设置

所有的仿真实验都是在配置3.40 GHz CPU和8 GB RAM、Microsoft Windows 7 操作系统、Intel（R）Core™ i7-3770M 的计算机端进行的，测试软件是Microsoft Windows 7 操作系统下的MATLAB 2016a。其中，对比算法中公共参数设置如下。

1) 种群规模：N=2D。

3) 停止准则：为了使算法能够正常停止运行，对于CEC 2014 测试函数集，函数的最大评价次数（FESmax）设置为10 000D。

4) 独立运行次数：在本文实验中，设置最大独立运行次数（runmax）为50 次。

3.4 数值实验

本节对8 个算法进行了对比实验，利用收敛速度和数值分析对实验结果进行了比较，体现了各个算法的差异。

1) 收敛速度。将8 个算法在不同测试函数上的收敛情况用曲线绘制出来，能够很直观地看出各个算法求解出的最优解在收敛过程中的误差值。

2) 数值分析。为了更加客观地评价基于协方差分析的合作协同差分进化算法与对比算法之间的性能，本文使用Wilcoxon 秩和检验（0.05 显著水平）对实验结果进行统计分析，如果得到的p＞0.05，则认为比较的2 个算法没有显著的差异，否则就是有显著的差异。根据 Wilcoxon 秩和检验结果将CC-COV-DE 与其他对比算法之间的实验结果标记为“+/–/～”，即CC-COV-DE 与其他算法的结果相比较好、较差或相近。表1 记录了8 个算法在50维CEC2014 上的统计结果（运行50 次）。

从表1 中可以看出，CC-COV-DE 的实验效果比CCDE 好，说明在使用XDG 根据决策变量之间的相关性对问题进行分解之后，子组件中变量的相关性影响种群的进化过程，利用协方差分析子组件中变量的数据特征，根据坐标旋转可以消除变量之间的关联性，提高了算法的性能。从CC-COV-DE 与其他对比算法的实验结果可以看出，CC-COV-DE 的算法性能整体较好，尤其是在优化混合函数和复合函数的效果方面，说明CC-COV-DE算法在优化复杂函数时的性能良好，稳健性强，与最新的算法相比具有可竞争性。

表1 8 个算法在50 维CEC2014 上的统计结果（运行50 次）

为了能够更加清楚地比较CC-COV-DE 与对比算法的收敛速度，图7 和图8 分别给出了8 个算法在30 维和50 维的测试集上的平均收敛效果。从图7和图8 可以看出，CC-COV-DE 的整体收敛效果优于其他对比算法。

图7 8 个算法在30 维的测试集上的部分收敛效果

图8 8 个算法在50 维的测试集上的平均收敛效果

通过计算CC-COV-DE 与其他7 个算法在30 维的CEC2014 测试函数集上的运行时间，并且比较其运行时间的比率，分析CC-COV-DE 的计算效率，实验结果对比如图9 所示，横线代表运行时间的平均值。在30 个测试函数中，CC-COV-DE 的平均运行时间分别是CCDE、COVDE、DE、ADLADE、CSDE、TVDE、A-CC/COV-DE 的0.211 2、1、1.271 5、1.414 6、0.888 6、1.503 0、0.516 7 倍。通过分析可得，CC-COV-DE的计算成本高的原因是在优化子组件的过程中需要计算协方差矩阵，计算的时间成本比其他算法稍大。