一种BP神经网络和遗传算法混合的云平台负载预测方法

吴俊伟 姜春茂

摘要：在云計算提供高效，便捷等强大服务的背后，是日益攀升的能耗问题。准确的预测云平台的负载（如CPU，内存的使用）在任务调度，云能效方面具有重要意义。在以往研究中，线性自回归算法在预测请求资源的粒度上存在不足，本文提出一种基于BP神经网络与遗传算法混合的负载预测方法，结合遗传算法良好的全局搜索能力与神经网络强大的非线性拟合能力，建立CPU资源的请求预测模型。实验通过Google的云平台数据作为训练，测试集。实验结果表明该方法有效的预测了CPU资源请求量，进而可以在此基础上调整服务资源，实现绿色调度。

引言

在云平台提供的强大功能背后，是巨大的能源消耗问题。一个占地500平方米的数据中心每天消耗的电力就高达38000度，这一数字超过了3500户欧洲家庭日用电量的总和。到2020年，预计数据中心的建设规模几乎将是2010年的两倍。从上述数字明显可以看出，为云计算设计高能效的解决方案迫在眉睫。

云能耗的优化可以从云任务和云平台的两个角度进行研究。

从云任务的角度，主要是分析云任务的多维属性，并利用算法来对云任务进行优化调度。云任务包括有静态属性和动态属性。静态属性如需要的CPU数量，任务的开始时间，截止时间，任务的类型等。动态属性如访问频率，存储要求，时间分布，用户请求模型等。挖掘出任务与能耗之间的关系将有助于提前预测负载，降低能耗。

从云平台的角度包括服务器，软件以及网络。从服务器角度来看，云能耗来源于处理器与数据中心两个层面，处理器的能耗的主要影响因素是应用程序的使用模式，而数据中心面临的是不断增长的主机数量与低使用率带来的能源浪费，据统计分析，云数据中心服务器的使用率一般在11%?50%之间。因此，如果能够较好的预测云平台cro的使用情况对于关闭部分服务器，提高调度效率具有重要意义。本文提出了一种基于神经网络和遗传算法混合的云负载的预测方法，根据历史数据预测未来短期CPU资源的需求，提高数据中心CPU的使用率，提局能效。

本文第1部分介绍相关工作的研究情况。第2部分提出基于神经网络与遗传算法混合的预测方法，第3部分实验及其结果分析，最后总结与展望。

1 相关工作

在服务器领域，一台完全空闲的服务器的能耗能达到其峰值的70%左右。处理器高能耗随之带来的问题是配套冷却设施的开销。据统计，计算资源消耗的每1瓦电能就需要额外的0.5?1瓦特进行冷却。Bohra等人采用“主成分分析”方法对监控事件的相互关联关系进行分析发现{CPU，Cache}对和{Disk，DRAM}

对有很高的相关性，由此把系统负载分成CPU密集负载和IO密集负载。Kaushik提出的绿色HDFS概念，将hadoop集群逻辑分为热区和冷区，采用数据分类与节能的策略确保在冷区存储的数据长期不被访问，从而关闭冷区的数据节点，但当冷区节点被唤醒的频率较高时，反而消耗更多能源。从软件层面上看，文献提出的一种绿色云架构实现虚机的重新配置，分配与再分配，以OPU的能耗为模型测量云平台的能源消耗。Biirge等人在异构的数据中心处理请求的调度上，关注用户任务布署的时间与节点，得出甚至只要运用很简单的启发信息都可以提高能效。在网络方面，文献中提出了一种域内流量工程机制GreenTE，能够在保证用户需求的前提下最大限度让数据链路进入休眠状态，Cianfrani等人提出一种能耗每女感的OSPF路由协议，通过优化Dijkstra算法与共享效率低的路由器最短路径树的方式，提供最少路径数的路由服务。

在预测资源请求方面，文献中通过分析主机状态间转换花费的时钟频率与电功率，提出绿色调度算法，用神经网络作为云资源的预测原型。但实验仅对NASA、Clark Netweb服务器url请求数作预测，粒度不够精细。John J.Prevost等人同样是预测url请求数，他们通过不同时间间隔模拟神经网络与线性自回归模型，从实验数据来看，二者都有较理想的近似曲线，但神经网络在90s间隔的案例中均方差值较大，预测效果不理想，分析得出神经网络存在收敛速度慢，易陷于局部最优解等不足。

2011年google对外公布了其29天的云平台实际数据，为进一步研究云平台信息提供了重要的实践依据。基于该数据，已经取得了相关的研究成果。其中，ZitaoLiu等人对此进行多方面的统计分析得出，在云计算中心任务的调度呈现周期性，其中被杀死（loll）和完成（finish）的任务（task）的数量相对稳定，而被杀死的任务占用CPU60%的时钟周期，可成功完成的任务仅占10%?15%，结论表明合理运用启发信息可提高完成任务所占用CPU时钟周期的比例。文献中提出一种预测失败任务的普适框架。作者分析云任务属性，以任务结束状态作为结构体数据，选择中长型任务，以上述的结构体作为输入，用周期神经网络训练预测器，训练完成后用该预测器对任务结束状态作预测。但资源消耗的范化丢失了数据的一些原始特性，无法辨别任务失败的具体原因，预测器无法在短时间内规避相同错误的作业。

综上所述，国内外研究从多个方面寻求云节能方案。对于请求资源预测这一方面，资源粒度未能具体到物理或虚拟的静态资源，而云能耗的度量大多都是以此构建模型的。算法单一，神经网络虽具有良好的非线性映射能力，但同时它也存在收敛慢等不足；多元线性回归可以准确地计量各个因素之间的相关程度与回归拟合程度的高低，提高预测方程式的效果，但可能忽略了交互效应和非线性的因果关系。本文将主机的CPU作为能效的研究对象，在系统使用率层面，通过准确预测CPU的需求量来对服务平台进行休眠，关闭等操作将极大降低云平台的能耗水平。本文提出一种基于神经网络和遗传算法混合的用户资源请求预测模型，预测未来短期CPU请求量，以此值为参照关闭闲置主机，从而提高系统使用率，降低能耗。

2 算法模型

2.1 BP神经网络

BP（Back Propagation）神经网络是一种按误差逆传播算法训练的多层前馈网络。从信息处理角度对人脑神经元网络进行抽象，建立某种突触联系强

度可变的简单模型，按不同的连接方式组成不同的网络。每个节点代表一个神经元（Neuron），接受一组输入信号，通过激励函数生成特定输出。神经网络模型拓扑结构包括输入层（inputlayer）、隐含层（hidelayer）和输出层（outputlayer），如图1所示：

输入信号依次通过输入层、隐含层、输出层逐级前馈，直至网络输出。之后学习系统计算网络的实际输出与期望输出的误差，根据这个误差逐级反馈调整网络权值，缩小实际输出与期望输出的差值，完成网络的学习过程。其具体过程如下：

（1）前馈计算

在该过程中，第层神经元的输入为该神经元相连的第层神经元输出的權重和，再将该和作为激励函数的参数，计算出该神经元的输出，设在第时刻第个神经元的输入为，输出为以，该神经元的输出可表示为：

其中，表示节点到节点的输入信号，表示节点到节点的权重，表示节点的阈值，为激励函数。

（2）反馈传播

反馈传播的含义在于，第层神经元的误差项是所有与该神经元相连的第层的神经元误差项权重和与该神经元激活函数/梯度的乘积。

对于/为sigmoid函数，输出层第时刻第个神经元，其误差计算公式可表示为：

其中，表示期望输出值，为实际输出值。

而对于隐含层第《时刻第个神经元，其误差计算公式可表示为：

第时刻第层第个神经元根据误差项，调整与该神经元连接的第层所有神经元的权重值，其调整计算公式可表示为：

其中，表示学习率，为节点的输出。

2.2 遗传算法

遗传算法（Genetic Algorithm）是模拟物竞天择的生物进化与自然选择的计算模型，通过维护一个潜在解的群体执行多方向的搜索，以问题潜在解集作为初始化种群，以直接或间接的方式为该种群的每个个体进行基因编码，实现从表现型到基因型的映射。在下一代中，根据问题域个体的适应性函数（fitness）选择个体，并借助遗传学的遗传算子（geneticoperators）对染色体进行组合交叉（crossover），变异（mutation），繁衍出代表新解集的种群。这个过程将导致后代种群像生物进化一样更加适应于环境，逐渐逼近问题的全局最优解。

2.3 混合遗传算法

2.3.1 算法描述

通过2.1，2.2的描述可以发现，神经网络与遗传算法都具有自适应，自组织的特点，神经网络虽具有良好的非线性映射能力，但易陷于局部最优解，而遗传算法从问题解集开始搜索，覆盖面大，易于寻找全局最优解。结合上一节的神经网络，具体给出遗传算法的关键步骤。

（1）基因编码

遗传算法的基因编码有直接与间接编码两种方式。以直接的方式对神经网络相邻层的权重矩阵进行编码，建立这样一个神经网络拓扑模型，3个输入节点，4个隐含节点和一个输出节点。如图2所示：

其中表示节点1与节点4的连接值，表示节点2与节点4的连接值，以此类推，用权值矩阵记录的节点间连接关系作为种群个体的遗传信息。

（2）自然选择

确定输入；经过神经网络的前馈计算，以均方误差：

作为适应性函数（fitness），值越小表示适应性越好。其中，分别表示第n时刻输出节点k的预测值与实际值。以轮盘赌的方式模拟自然选择，在轮盘赌中，权重矩阵代表种群个体，用矩阵对应的适应值计算该个体在轮盘中所占据的扇形比例，以此近似该个体被自然环境所选中的概率。

（3）组合交叉

组合交叉模拟父母双方染色体配对过程，使子类更加逼近问题的最优解。组合的方式多种多样，这里介绍种群内部与种群间的基因重组，如图3，图4所示。

种群内部的重组体现在保留当前最优解的种群权值矩阵，种群间则使用的是单点组合交叉的方式组合交叉重组父母双方权值矩阵，以产生新的解集空间。种群内部的重组体现在保留当前最优解的种群权值矩阵，种群间则使用的是单点组合交叉的方式组合交叉重组父母双方权值矩阵，以产生新的解集空间。（4）基因变异

变异算子定义为以小概率事件修改基因重组后子类的权重矩阵，使得对问题的求解有机会从当前空间跳跃到另一个搜索空间，逼近问题的全局最优解。

（5）过渡条件

如此重复以上步骤，当达到预期的适应值或种群的适应值趋于稳定时，将适应性最好的基因作为神经网络的权值矩阵，进入第6步。

（6）前馈传播

对于每一组输入，计算其实际输出。

（7）反馈传播

根据公式（2）（3），调整权值矩阵，当达到公式（8）小于预期的阈值或达到最大迭代次数时，结束算法。否则回到第6步。该算法的伪代码如表1所示。

2.3.2 实例分析

以拓扑结构为3-4-1的神经网络为例，假定初始条件下资源统计如下表2所示：

任选一组输入数据（以编号1为例），通过前馈算，三组基因的输出值分别为0.55，0.61，0.66，其适应值为0.013，0.005，0.001。对应的在轮盘中所占的比例为0.06，0.16，0.78。在轮盘赌中选中的基因为基因B与基因C。其基因重组，变异过程如图7所示：

产生下一代个体，其适应值为0.0128。重复轮盘赌步骤构建新一代种群。假设图9的基因适应值满足迭代结束条件，则进入神经网络训练过程。

任选一组输入（以编号2为例），经过网络传播，输出值为0.63，根据实验误差与函数梯度调整矩阵，设学习率为0.25，阈值b设置为0。过程如图8所示：

重复网络训练过程，直到达到最大迭代次数或均方差小于阈值，结束程序。

3 实验及其数据分析

3.1 实验环境与参数设置

本文实验是在单机环境下完成的。华硕AllSeries台式电脑，CPU为InterCorei5-4590

3.30GHz，8GB内存，1TB硬盘，主板集成声卡和网卡，独立显卡。编程平台为java环境。文献使用了神经网络和线性回归模型对服务器资源的请求数做出预测，而神经网络的预测效果相比下并不理想。实验主要目的是测试神经网络结合遗传算法是否能突破局部最优解，更加逼近全局最优解的非线性曲线。因此设计了以下实验。

实验1GA扩大搜索范围，寻找全局最优解区间。对谷歌数据的分析得出，集群的资源请求数据具有周期性，且一周为一个周期，换言之，上周一与这周一在请求值上具有相似性，所以我们明确以上周一与这周一的数据作为训练样本，预测下周一的请求数据。以上周一的数据作为网络的输入，这周一同一时刻的数据作为输出，这样就可以在夜间轻量负载的时间段执行预测程序。

初始化一个3-7-1的网络拓扑结构，分别对应于输入层，隐藏层和输出层。输入层3个节点分别是时间戳，CPU请求核数，任务请求量，输出层为CPU的预测值。基于此拓扑的权值矩阵构建GA的编码基因，首先随机初始化矩阵集合，接着确定输入值，每隔5mini己录一次{timestamp，request Core，request Tasknum}结构数据，以24小时为整个时间跨度，可得到容量为288的数组。通过神经网络前馈传播输出预测值，以均方差：

作为个体的适应性函数值，遵循优胜劣汰的规则，将适应值最高的个体基因直接遗传给下一代，接着用轮盘赌的方式在种群中选择待交配的双方，采用单点基因重组构造新的权值矩阵。其变异率设置为0.05，变异区间[-0.5，0.5]。实验中设置的参数如表4所示。实验2BP神经网络再训练，逼近全局最优解。由实验1训练的适应值最大的编码基因，作为BP神经网络的权值矩阵，进入神经网络训练过程，得出逼近全局最优解的权值矩阵。设定sigmmd函数为激活函数，学习率为0.5。实验中设置的参数如表5所示。

3.2 实验分析

统计下周一的CPU资源请求数据，如图9所示。使用神经网络，以上周与本周的数据样本作为训练集，输出结果如图10所示。

混合算法，训练集同上，测试结果如图11所示。BP神经网络与混合算法预测值与实际值差值样本抽样，如表6，表7所示。

如图10所示，除个别数据节点，其它节点预测值与实际值相差较大，曲线逼近程度不理想。出现这种过拟合现象的主要因素是BP算法本身易陷于局部最优解。而在图11中，除去少数节点，二者曲线波形相似，预测值曲线逼近实际值。表7中，混合算法均值为正数，说明该算法预测值平均高于集群的实际值，从而保证集群的SLA。本文提出的混合算法，在查找全局最优解方面借鉴遗传算法，以面的方式搜索解集空間，寻找全局最优解区间，再用神经网络逼近该区间的最优解，二者的混合更适用于复杂的非线性曲线问题求解。

4 总结和进一步研究

云数据中心的高能耗与低使用率的巨大反差催生了绿色节能的槪念。麵艮务器，网络，软件为提高能效的三大研究目标。针对服务器领域，本文提出的基于神经网络与遗传算法混合预测模型，自身具#辙子的学习能力，搜索全局最优解的能力较强，对云资源请求量的逼近效果较为理想，可为数据中心资源分配与任务调度提供参考。但该模型输入参数类型较为局限，仅为timestamp、core、tasknum，且本文中该模型仅用于预测CPU资源，未来将考虑基于此构建云平台资源请求的普适框架。