基于Spark的自适应差分进化极限学习机研究

杨 敏，刘黎志，邓开巍，刘 杰

智能机器人湖北省重点实验室（武汉工程大学），湖北 武汉430205

自适应差分进化极限学习机（self-adaptive differential evolution extreme learning machine,SaDE-ELM）［1］是由Cao等在2012年提出的一种使用群智能计算改进的极限学习机算法，它将自适应差分进化算法（self-adaptive differential evolution，SaDE）与标准极限学习机算法相结合，从很大程度上解决了标准极限学习机算法中由于随机初始化隐藏层输入权重和偏置导致的算法稳定性不高、预测准确度波动较大的问题，目前已被广泛应用到分类识别［2-4］和回归预测领域［5-7］。随着大数据时代的到来，一个算法能否高效地处理大规模数据集也成为了衡量算法普适性的一个重要指标，为了提升很多传统的机器学习算法的运行效率，如何利用现有的大数据处理框架对其进行并行化也成为目前研究的热点问题［8-10］。SaDE-ELM算法在计算过程中，由于需要多次迭代计算来更新输入层到隐藏层的连接权重和隐藏层偏置，不可避免地增加了算法的运行时间，在数据集规模较大时算法的运行效率十分低下。本文根据SaDE-ELM算法需要迭代计算的特性，采用了基于内存计算的大数据框架Spark对其进行并行化［11-13］，将原本在单机上的计算合理地分布到集群的各台机器中，提出了并行自适应差分进化极限学习机（parallel self-adaptive differential evolution extreme learning machine，PSaDE-ELM），最后通过实验验证了在数据集样本数较大时，PSaDE-ELM算法能够在保证预测准确率基本不损失的基础上，显著地提升算法的运行效率。

1 研究背景

1.1 极限学习机

极限学习机（extreme learning machine，ELM）是2004年黄广斌等［14］提出的一种单隐藏层前馈神经网络（single-hidden-layer feedforward neural networks，SLFNs）机器学习算法。ELM与传统基于反向传播的神经网络算法的不同之处在于，它随机初始化输入层到隐藏层的连接权重和隐藏层节点的偏置，然后使用Moore-Penrose伪逆方法求解隐藏层到输出层的权重，具有学习速度快、泛化能力强的特点。

ELM的算法描述为，给定N个任意不同已知训练集()x i,y i,i=1,…,N，其中x i∈RD,y i∈Rm，L为隐藏层节点个数，g()x为激活函数。如果这个前馈神经网络能以零误差逼近这N个样本，则存在βi,w i,bi使得：

其中，βi∈Rm表示第i个隐藏层节点与所有输出层节点之间的权重向量，w i∈RD表示第i个隐藏层节点与所有输入层节点之间的权重向量，bi∈R表示第i个隐藏层节点的偏置。式（1）可以化简为：

其中H表示ELM的隐含层输出矩阵，当网络中的输入权重和偏置随机确定后，输出矩阵H就唯一确定下来，这样对SLFN的训练就可以转化为一个求解输出权重矩阵的最小二乘解的问题，输出权重矩阵β可以由式（2）得到：

其中H†表示隐含层输出矩阵H的Moorepenrose广义逆。

1.2 自适应差分进化极限学习机

SaDE-ELM算法将极限学习机中的输入层到隐藏层的连接权重和隐藏层的偏置作为种群中一个个体，在自适应差分进化算法中进行迭代优化，对每个个体使用极限学习机算法进行解析计算，以预测值与实际值的根均方误差（root mean square error，RMSE）作为对应个体的适应度，在每次迭代中将保留适应度更优个体进入下一次迭代，直至满足结束条件后，输出当前种群中的最优个体。其相比于差分进化极限学习机（differential evolution extreme learning machine，DE-ELM）和支持向量机（support vector machine，SVM）具有更好的稳定性和更高的运行效率。

对于一个给定的训练数据集，L个隐藏节点的ELM，SaDE-ELM算法流程如下：

1）初始化种群，种群中每个个体的维度为(D+1)×L，其中D为特征个数；

2）计算ELM的输出权重矩阵和RMSE，然后将RMSE作为对应个体的适应度；

3）使用SaDE算法对种群中的每一个个体进行变异和交叉操作；

4）使用适应度评判标准来选择进入下一代的个体，如果当前迭代次数未达到最大迭代次数，则重复步骤2和3，进入下一次迭代。

1.3 Spark平台

Spark是加州大学伯克利分校实验室基于AMPLab的集群计算平台开发的一个基于内存计算的分布式框架，相比于Hadoop分布式框架，Spark将中间计算过程保存在内存中，避免了将中间结果输出到硬盘存储，所以Spark更适合于具有迭代计算的应用场景。其最核心的技术是弹性分布式数据集（resilient distributed datasets，RDD）。RDD是一个不可变的分布式对象集合，对数据的所有操作最终会转换成对RDD的操作，即RDD是数据操作的基本单位。对于RDD的操作，分为transformation（转换）和action（执行）。Spark对于两种操作采取不同机制，对于所有的转换操作都是惰性操作，即从一个RDD通过转换操作生成另一个RDD的过程在Spark上并不会被马上执行，只有在action操作触发时，转换操作才会被真正执行。因此，不同RDD之间的转换操作会形成依赖关系，可以实现管道化，从而避免了中间结果的存储，大大降低了数据复制、磁盘IO和序列化开销。

1.4 群智能算法并行化相关研究

近些年来随着群智能算法的发展，许多学者将分布式计算的思想引入到群智能算法中，提出了多种基于大数据计算平台的群智能并行化算法。2016年李婉华等［15］提出了基于改进粒子群优化的并行极限学习机算法，使用真实电力负荷数据在Spark平台上对算法有效性进行了验证。2017年重庆大学余相君［16］提出了一种使用改进后的布谷鸟搜索算法优化的K-means算法，并在Hadoop平台上对该算法进行并行化处理，在数据集规模较大时，算法运行效率得到了提升。2018年大连理工大学孙康丽［17］基于Spark平台对分布式差分进化算法并行化，提出基于广播变量和Shuffle操作的两种迁移算子实现方式，比较了两种实现在不同计算资源下的加速比。

2 自适应差分进化极限学习机并行化

2.1 算法并行化的思路

自适应差分进化极限学习机算法在迭代过程中，因为种群里的各个个体的进化都是相互独立的，所以可以将原有种群均匀分割为几个子种群，每个子种群并行地独立进化，然后每隔一定的周期各个子种群之间按照一定的拓扑结构进行信息交流，以此来达到既提高了算法的运行效率又保证了种群间多样性的目的。本文提出的基于Spark的SaDE-ELM并行化算法PSaDE-ELM就是按这一思路来实现的。

在PSaDE-ELM算法中，每一个子种群均由一个子种群序号和SaDE_ELM对象组成的元组来表示(i,SaDE_ELMi)，每个SaDE_ELM 对象中均存储了当前子种群在迭代进化中必要的参数信息，这些参数信息随着子种群的进化而改变，然后利用Spark中RDD的分区原理，对子种群列表使用makeRDD方法转换为RDD，并且将其分区数设置为子种群个数，来保证将每一个子种群以及其参数信息均独立地存储在RDD的一个分区中。然后对当前RDD使用map算子，使各个子种群中的迭代计算在各个Task之间并行执行，等待所有Executor中的Task均执行完毕后，将当前迭代周期中各个子种群所产生的最优个体使用collect算子汇总到Driver端，然后由Driver端将这些最优个体信息广播到各个Executor中，以便后续根据一定的拓扑结构在各个子种群间进行信息交换。当各个子种群进行信息交换后，就进入下一个迭代周期，直至满足结束条件后，输出所有子种群中最优的个体，即最优的隐藏层输入权重和偏置。

2.2 两种拓扑结构

各个子种群在每次独立迭代一个周期后，会按照给定的拓扑结构来进行种群信息交换。子种群间的交流拓扑结构主要包括两种：一种是全连接拓扑结构，即每一个子种群可以与其他所有子种群进行信息交换；另一种是邻域拓扑结构，即每一个子种群只能与其相邻的子种群进行信息交换。

对于某一个子种群而言，在一个迭代周期结束以后，全连接拓扑结构会将所有子种群中最优的个体去替换掉当前子种群中的最差个体，每个子种群在信息交流完之后，其总体进化程度都至少为最优个体的适应度，所以这种拓扑结构具有较强的全局收敛速度能力；而邻域拓扑结构会将左右相邻的两个子种群中的最优个体去替换掉当前子种群中的最差个体，这种拓扑结构收敛速度较慢，但可以避免整个种群过早陷入局部最优。

2.3 PSaDE-ELM算法设计

PSaDE-ELM算法在Spark上的实现主要算法流程如下：

1）将原种群均匀分割为多个子种群，设置并行度等于子种群个数，以便将每个子种群及其序号单独存储在种群RDD的一个分区中；

2）使用Spark中的广播变量机制，将训练数据集由Driver端广播到各个机器上的Executor中；

3）在当前迭代周期中，对种群RDD使用map算子，执行optime方法来对各个子种群迭代一个周期，计算并统计各自最优和最坏的个体，返回进化后的子种群对象；

4）使用Cache方法，缓存上一步中进化后的种群RDD；

5）将各个子种群中的子种群序号和最优个体以元组的形式收集到Driver端，组成当前最优个体列表，并将该列表由Driver端广播到各台机器上的Executor中；

6）按照一定的拓扑结构，根据最优个体列表信息来和其他子种群进行信息交换，并返回进化后的子种群对象；

7）判断当前同步次数是否能够被10整除，若能够被10整除，则对种群RDD进行一次CheckPoint操作；否则，进入下一步；

8）判断当前同步次数是否大于设置的最大同步次数，若小于最大同步次数，则返回算法的第3步；否则，输出所有子种群中的最优个体，算法流程结束。

在上述算法流程中，使用了Spark框架中的广播变量、Cache缓存机制和CheckPoint操作。之所以使用广播变量，是因为如果不将数据集以广播变量的方式由Driver端发送给Executor端，那么在每次开启一个Task时，都会产生一个数据集的副本。也就是说，使用广播变量的方式发送副本时，副本个数等于集群中各台机器上Executor的数量；而不使用广播变量的方式，直接在Task中使用数据集时，那么每一个Task中都会保存一份数据集的副本。当Task数大于Executor数时就会产生冗余的数据集副本，不仅占用内存空间，而且会导致算法运行效率不高的问题。

使用Cache方法缓存种群RDD，可以在下一次对种群RDD的行动算子执行完之后将种群RDD缓存在内存中，种群RDD中的每个分区里的子种群信息也都会保留下来，这对于需要在下一个周期继续上次的迭代过程是至关重要的。如果没有使用Cache方法，那么在每一次迭代周期中种群RDD都将被重新计算，将无法承接上一次的进化结果继续进行种群进化，导致算法运行效率大大降低。

在算法流程中定期使用CheckPoint操作的原因是由于在每一个迭代周期中都会由先前的RDD产生一个新的RDD，并由此组成一条RDD关系链，当这条RDD链变得很长时，其依赖关系也会变得很长，通过定期使用CheckPoint来将种群RDD保存在磁盘中，从而切断当前种群RDD与先前种群RDD之间的血缘关系，可以避免在反序列化当前种群RDD时由于过长的血缘关系而导致性能低下的问题。

PSaDE-ELM算法的核心算法描述如下：

3 实验及分析

3.1 实验环境及数据

本实验所用服务器为戴尔R720服务器，它配置为两个物理CPU（Intel Xeon E5-2620V22.10 GHZ，最大睿频2.6 GHz，每个CPU含6个内核，一共12个内核），32 GB内存，8 TB硬盘。该服务器被虚拟划分为4个虚拟机，每个虚拟机的配置为3个内核CPU，8 GB内存，2 TB硬盘。集群使用的主要软件 有 Hadoop2.7.3、Spark2.4.6、JDK1.8、Scala2.12.2等，操作系统为Ubuntu-16.04.1-Serveramd64。Spark集群包括一个Master主节点和4个Worker数据节点（主节点也是数据节点）。实验选用4个UCI公开数据集进行训练和测试，其中训练数据集和测试数据集占比均为70%和30%，实验数据集信息如表1所示。

表1 实验数据集信息表Tab.1 Information table of experimental data set

3.2 实验结果及分析

从3个方面对所提出的PSaDE-ELM算法进行了分析，首先是在不同数据规模的数据集上串行SaDE-ELM算法与PSaDE-ELM算法各自的运行效率与预测准确率的对比；其次，分析了子种群之间采用不同的拓扑结构进行信息交流对PSaDE-ELM算法运行效率和预测准确率的影响；最后分析了在原种群大小不变的前提下，随着子种群数量的增多对PSaDE-ELM算法运行效率和预测准确率的影响。其中，采用手动调参的方式来选择最适合当前数据集的隐藏层节点个数，原种群大小为60，同步次数为20，同步周期为10，每个实验结果均为30次实验数据的平均值。

第一组实验是对于在不同规模数据集上串行SaDE-ELM算法和PSaDE-ELM算法各自的运行效率与预测准确率的对比。对于不同的数据集，选择了最适合的隐藏层节点个数，且子种群数量subPopCount均为6。由表2可知，PSaDE-ELM算法在各个数据集上的预测准确率基本与SaDEELM算法保持不变（上下误差不超过1%）；在数据量较小时串行SaDE-ELM算法相比PSaDE-ELM算法会更有优势，这是由于在数据量较小时，在Spark集群中读取数据集以及启动集群资源所需时间占比会比较大，导致最终的运行时间会比串行SaDE-ELM算法要长。但随着数据集样本量的逐渐增大，PSaDE-ELM算法并行计算的优势会逐渐体现出来，在Car数据集上，时间性能提升了(74.509-29.79)÷29.79≈150%，在Adult数据集上，时间性能提升了(2 652.553-736.908)÷736.908≈260%，在Bank数据集上，时间性能提升了(4 590.235-1 180.954)÷1 180.954≈289%。可以看出，随着训练数据集规模的增大，集群计算的优势就愈发明显。

表2 SaDE-ELM与PSaDE-ELM算法运行结果对比实验数据表Tab.2 Comparison experimental results of SaDE-ELM with PSaDE-ELM algorithm

第二组实验主要分析了子种群之间采用不同的拓扑结构进行信息交流对PSaDE-ELM算法运行效率和预测准确率的影响。在保持其他参数不变的前提下，分别使用全连接拓扑结构和邻域拓扑结构来进行子种群之间信息交流。由表3可知，对于3个数据集而言，邻域拓扑结构相比全连接拓扑结构在算法的运行效率上提升并不明显，其预测准确率却比全连接拓扑结构要低1%～2%。这是由于在邻域拓扑结构中，每个子种群只与其相邻的两个子种群进行交流，在算法的全局收敛上会比较慢，在同步次数不多的情况下，预测准确率会不如全连接拓扑结构。因此，在本次实验中，采用全连接拓扑结构能够更好地在子种群之间进行信息交流。

表3 子种群间不同拓扑结构运行结果对比实验数据表Tab.3 Comparison of running results achieved under different topological structures of subpopulations

图1 不同子种群个数总运行时间趋势图Fig.1 Variation curve of run time with number of subpopulations

第三组实验主要分析了在原种群大小不变的前提下，随着子种群数量的增多对PSaDE-ELM算法运行效率和预测准确率的影响。实验选用Adult数据集，设置隐藏层节点数为60，原种群大小为60，然后逐渐增加子种群个数，并统计每次实验的运行时间和预测准确率。每次实验的预测准确度波动不大，均维持在85%左右。由图1可知，随着子种群个数从2增加至10（由于自适应差分进化算法使用的一个变异算子中需要随机抽取6个个体进行变异，所以每个子种群至少要有6个个体），算法的运行时间呈单调递减趋势，且当子种群个数小于等于4时，运行时间减少的幅度较大，当子种群个数大于4时，运行时间减少的幅度逐渐减小。由于使用RDD的一个分区来单独存储一个子种群及其参数信息，对于每一个分区而言，都会独立地占有一个Task，每一个子种群之中的计算都是并行的。当子种群个数为8时，Spark集群中的4个Executor中，每一个Executor里均有2个Task在并行计算，此时集群已达到负载均衡状态，继续增加Task的个数，将不能再明显地提升算法的性能。

4 结 论

基于Spark高性能内存计算框架，提出了一种并行化自适应差分进化极限学习机算法PSaDEELM，并从3个方面进行了对比实验。实验结果表明，本文提出的PSaDE-ELM算法在预测准确率上与串行SaDE-ELM算法相比基本没有差别，但随着数据规模的增加，PSaDE-ELM算法能够将运行效率提升数倍，从而证明了PSaDE-ELM算法的有效性；对于不同的子种群拓扑结构而言，全连接拓扑结构相比于邻域拓扑结构都能够更好地适用于本文所选数据集；在保持其他参数不变的前提下，随着子种群数量的增加，其预测准确率波动不大，但其运行时间显著减少。本文在对自适应差分进化极限学习机算法进行并行化时采用的是粗粒度方式，即将一个种群均匀划分为多个子种群来共同进化，这种方式对于数据量不是很大的情况下能够显著提升算法的运行效率。但在数据量很大时，计算各个个体的均方根误差时会面临高维矩阵的计算，在后续的实验和研究过程中，将试图将高维矩阵的计算也进行并行化，使改进后的算法能够适用于处理更大规模的数据集，在保证预测准确率的前提下，尽可能地提升运行效率。