史振华

(绍兴职业技术学院，浙江绍兴 312000)

0 引言

云计算中资源负载关系到云服务质量的高低，通过预测未来资源负载能够有效的提高云计算的资源调度效率［1］。由于云计算资源具有实时性，动态性等特点，导致了资源负载预测同样具有不确定性和非线性［2］等特点，因此，国外学者使用很多的方法对其进行研究，文献［3-6］主要是以静态的对象研究为主，但是无法达到很好的预测效果。国内学者在此基础上进行了相应的研究，对一些算法［712］从不同的角度提出了预测方法，文献 ［13-17］从不同的角度提出了云计算资源的预测方法，都取得了比较好的效果。

本文将人工蜂群算法与SVM相结合构建预测模型，通过对人工蜂群算法的种群进行初始化，采用差分进化算法对个体选择、吸引子策略构建蜜源选择、使用反馈机制和森林法则等措施提高人工蜂群算法的性能，并进一步优化SVM中参数，提高了预测精度。

1 人工蜂群算法简述及不足

人工蜂群算法 (Artificial Bee Colony Algorithm，简称ABC)是一种根据蜜蜂采蜜行为而受到启发提出的一种群智能优化算法，其工作的过程是每一个蜂群个体之间进行分工与信息分享、信息交流，从而相互合作完成采蜜工作，ABC算法具有操作简单、参数控制少、鲁棒性强的优点。特别是ABC算法用于处理某个最优问题的时候，其算法中对应的蜜源的位置就是优化问题中的可行解，而蜜源中花粉的数量对应优化问题可行解的质量高低，蜜蜂寻找花蜜速度对应可行解的优化速度，获得最大的花蜜量对应着优化问题的最优解。首先，算法随机产生N个初始解，采蜜蜂的数量为N，将蜜源与采蜜蜂进行一对一对应，其次，当采蜜蜂进行搜索蜜源的时候会移动到新位置，通过将新位置的花蜜与上一个位置的花蜜的数量进行对比，选择优质的蜜源，在采蜜蜂完成全部的搜索后，将搜索结果对比花蜜容量，从中选择优质蜜源，当所有的采蜜蜂完成搜索之后，观察蜂会根据采蜜蜂提供的蜜源信息以一定的概率选择蜜源，最后，判断蜜源花蜜量经过有限次的搜索之后得到最优解即为最优质的蜜源。在ABC算法中，蜜蜂被分为三类，分别是雇佣蜂、跟随蜂和侦察蜂。这3种蜜蜂的搜索行为如下:

(1)雇佣蜂搜索。算法中的雇佣蜂主要是为了能够围绕在特定的蜜源周围随时进行搜索，当需要在另一个蜜源附近进行开采花蜜的时候，雇佣蜂在该蜜源附近进行新的搜索，其搜索公式如 (1)。当寻找到新的蜜源之后，进行适应度 (公式2)方面的评价，并与上一个蜜源的适应度对比，如果高于上一个蜜源，则进行依靠。

式中，φij表示在 ［－1，1］中的随机数，fit(v)是适应度评价函数。

(2)跟随蜂搜索。雇佣蜂主要将蜂蜜送到蜂巢之后，会邀请跟随蜂一起飞向蜜源。跟随蜂是否接受邀请主要与雇佣蜂依靠的蜜源质量具有一定的关系，通常来说当蜜源的质量越高，就能够吸引到更多的跟随蜂前往，反之，则会失去更多的跟随蜂，导致该蜜源被放弃，跟随蜂选择的概率如公式 (3)所示。

(3)侦察蜂搜索。当蜜源采摘完毕之后，在蜜源附近的雇佣蜂就变成了侦察蜂，从而进行全局搜索。其搜索的公式如 (4)所示。

式中，R为 ［－1，1］之间的随机数。

虽然该算法在很多实际问题中被广泛的应用，但还是存在一定的不足，比如种群的初始化是随机的，没有考虑对整个种群的共享信息的有效利用，导致算法在进行局部搜索的过程中能力差且陷入局部最优，收敛速度还需要进一步提高等问题。

2 人工蜂群算法的改进

2.1 种群初始化及其个体选择

基本的ABC算法的种群是没有初始化的即位置是随机的，这样会导致种群在分布的时候不均匀，因此整个算法的性能也会受到一定的影响，为了能够有效的避免这种情况的发生，有效的提高算法的搜索效率。本节采用反向学习的策略对种群进行初始化，用来增加种群多样性，以便更好的产生最优解。其解决的策略是在反向学习策略中，将一个可行解计算出对应的反向解，然后将这两个解进行合并排序，按照设定的条件选出一个个体作为下一代个体。其步骤如下:

步骤1:初始化种群规模N。

步骤2:随机初始化阶段。

步骤4:从 {X(N)∪OX(N)}中选择适应值最好的前N个值作为种群初始解。

在种群的初始解初始阶段，首先通过对种群中个体进行差、变异等操作重新得到一个新的种群，其次与父代个体进行交叉操作，计算种群中的个体适应度值进行排列，从中选择出优秀的种群个体，得到新一代群体。最后进行包括变异、交叉和选择3个操作的进化过程．

(1)变异。对于个体xi，按照如下生成变异个体:

式中，xr1，xr2和xr3从进化种群中随机选取3个个体，设定F为缩放比例因子用以控制向量产生的影响。

(2)交叉。为了进一步增加种群多样性，引入差分进化算法:

式中，j=1，2，…D，D为空间维数，CR为0到1之间的概率。

(3)选择。使用贪婪策略，将交叉后的个体vi和父代个体xi按照公式 (7)生成子代个体:

对个体进行差分进化算法步骤如下。

步骤1:初始化种群，对种群进行评价。

步骤2:对其中的个体按公式执行 (5)产生变异。

步骤3:对个体和变体执行 (6)和 (7)生成新的个体。

步骤4:对新的个体组成的新的种群进行总体评价，从而确定下一代种群。

2.2 跟随蜂的蜜源选择

在ABC算法中，跟随蜂是通过轮盘赌策略来选择蜜源的，虽然能够保证优秀的蜜源能被选中，但有的时候从整体上也会错失更加优秀的蜜源，显然这样会延长耗费计算的资源，导致迭代时间延长，本文算法在遵守这种理念初衷的前提下，提出一种“吸引点”策略，通过引入cr来改变跟随蜂的搜索方式。所有的跟随蜂全部以吸引点为中心的周围等比例的缩放来共同开发，从而从整体上有效的提高算法的开发能力。而吸引点cr作为蜂群中的“蜂王”，按照一定的比例范围吸引所有跟随蜂靠近它，搜索示意如图1所示。白色框表示吸引子，黑色球表示不同的种群的初始位置，三角形表示围绕吸引点后的种群所在的新位置。

本文对于吸引点的获得按照两种方式来进行。第一种情况是当种群的个体获得全局最优解的时候，吸引点cr的值通过公式 (8)得到，第二种情况就是没有获得全局最优解的时候，吸引点按 (9)得到:

图1 搜索示意图

式中，vi表示当前可行解的蜜源，r1，r2，r3是一组随机数目，且r1+r2+r3=1，吸引点cr作为整个蜂群的中心，而每一个侦察蜂都以它为中心，从远到近根据一定的比例进行缩放，这样能够有效的降低个体飞越边界的可能性，同时个体的整体算法的寻优能力得到了加强，整体算法开发能力也逐步增强。因此对种群个体进行位置更新为:

式中，xmax和xmin是种群中的上限和下限，在算法的每一步进化过程中，r的值恒定，保证种群个体不丢失原先的社会信息。

2.3 反馈机制和森林法则

为了进一步解决ABC算法陷入局部最优，容易产生收敛速度慢的问题，本文将反馈机制和森林法则进行整体融合，其主要思想是在ABC算法的全局搜索的过程中引入反馈机制，这样可以扩大算法的感知的范围，因此整体上提高算法的开发能力和探索能力，通过线性微分递增来平衡算法中的开发能力和探索能力，模拟森林法则中的优胜劣汰的方式，随机的选择较差的个体进行初始化。

(1)反馈机制:

从雇佣蜂搜索公式中可以发现，ABC算法主要用于搜索而不是进行开发，随着算法的不断深入，如何能够更好的开发是算法后期中薄弱环节，特别是从平衡算法的角度出发，其探索能力和开发能力上如何解决算法的收敛能力是非常重要的，本文根据粒子群算法的中的全局最优解的概念启发，在搜索公式中引入线性微分递增策略和全局最优解的思路来解决以上问题，采用公式如 (10)，(11):

式中，xgj表示全局最优解，xij代表当前解，xkj是当前不同于xij的一个随机解，rij是一个属于 (－1，1)之间的随机数，wmax和wmin分别表示自适应因子中的最大值和最小值，设T为最大迭代次数，t为当前迭代次数。在公式 (10)的描述中，rij是不确定的随机数，通过相应的反馈机制使得最优解的蜜源的质量能够在上一代蜜源中得到更新，因此说明目前的方向是正确的，因此可以继续在该方向上搜索，反之，则向相反的方法搜索。当上一代蜜源得到更新的时候，d=1，否则d=0，通过反馈机制，可以直接搜索可能存在最优解的区域。

(2)树林法则。

自然界中存在这样一种优胜劣汰的现象。速度慢的动物往往会被凶猛的动物吃掉，本文中的适应度差的解就好比速度慢动物，容易被重新初始化。在算法中，适应度差的解个体周围的其他解的适应度也比较差，对这些个体按照随机原则重新初始化，设定全局适应度最差的个体gw的领域半径范围如公式 (12)。

式中，Range表示全局适应度最差个体的领域半径，本文将全局最优解与最差解之间的欧式距离作为领域范围的半径。显然，根据公式 (12)所确定的领域范围，从适应度差的个体中随机抽取个体需要满足如 (13)条件:

式中，a表示为一个范围系数，只有满足公式 (13)的种群个体被才能被重新初始化。

3 云计算流量预测模型构建

云计算的资源负载预测可以通过SVM来建立预测模型，在模型中使用非线性映射函数φ(x)将云计算中的短时间中的负载数列x1，x2，…xn作为样本从低维空间投影到高维的特征空间中，并进行线性回归，SVM在高维特征空间中的回归函数为:

ω为权向量，b为偏置向量。根据风险最小化原则，公式 (14)转换为如下优化问题表达:

式中，‖ω‖是与函数f具有相关复杂度相关的项，ε表示不敏感损失稀疏，，ζi和C表示松弛因子和惩罚因子。为了将问题 (15)转换为凸二次优化问题，特引入朗格朗日乘子:

式中，αi和α*i表示拉格朗日乘子，γi表示损失因子，将公式 (16)转换为对偶形式，如下:

因此，SVM回归函数为:

为了简化 (18)，将使用核函数 K(xi，x)代替 (φ(xi)，φ(x))，因此SVM函数如下:

从以上式中发现，建立基于SVM的云计算负载预测模型的目的就是为了找到最优支持向量参数σ。即也就是云计算负载预测值。

4 构建IABC－SVM预测模型

步骤1:输入云计算资源负载序列，产生SVM的训练集和验证集。

步骤2:设定SVM的核函数参数σ的范围，并设置改进的ABC算法参数。

步骤3:设置ABC算法的中蜜源对应每一个支持向量参数σ。

步骤4:SVM通过初始的参数σ对训练集进行学习。

步骤5:使用改进的方法对ABC算法中三类蜜蜂的初始解和相关搜索进行操作。

步骤6:当迭代次数超过最大迭代次数的时候，训练结束，输出种群最优位置，即为SVM中的向量参数σ最优值，否则转向步骤5继续执行。

步骤7:采用向量参数σ来建立预测模型f(x)，对验证集合的预测结果进行分析。

5 实验与分析

5.1 数据来源

为了能够有效的说明本文算法在云计算资源负载中发挥的作用，选择Clarknet［18］的网络负载作为本文实验的研究对象，在时间的设定上选择连续7天的100个历史数据作为训练数据，数据间隔为4个小时，预测未来2天的的云计算下的负荷数据。本文使用平均绝对误差MAE来计算预测模型的有效性，公式如下，其中yt为实际负载数据为预测数据，T为预测时间序列，如公式 (20)所示，但由于SVM对于［0，1］之间的数据具有非常高的敏感度，因此需要对网络流量数据进行归一化处理，公式 (21)所示。

式 (21)中，x表示原始网络流量，max(x)和min(x)表示最大值和最小值。

5.2 仿真结果分析

5.2.1 本文算法的预测效果

本文选取了连续9天的云计算的网络流量简化结果，单位为Gb/S，对应结果如表1所示。表2为采用本文算法来预测得到第8～9天的云计算下流量预测结果。从表2中发现，根据相同的时间序号下的云计算的云计算网络流量预测与表1种的网络流量的仿真结果的误差基本上在5%之内，图2显示了Clarknet平台中的实际负载和预测负载的效果，图中的两条线大部分都重合或者十分相近，从以上的分析中可以说明本文算法具有良好的预测效果。

表1 连续9天的云计算中网络流量仿真实际结果

表2 第8－9天的云计算中的网络流量仿真结果

5.2.2 Clarknet平台下的几种预测方法的研究

在Clarknet平台中将本文算法、SVM方法，IABC－LSSVM［19］在CPU负载和网络负载的条件下进行对比，对比结果如3～4所示。

图2 Clarknet平台的网络负载预测结果

图3 4种算法下的CPU负载的MAE值比较

图4 4种算法下的云中网络负载的MAE值比较

从图4得到本文提出的算法在不同的云计算CPU负载条件下相比于其他两种预测方法明显具有良好的效果，预测精度更高，预测误差小，这说明本文预测方法能够适应CPU在不同负载变换下的预测结果。图5中发现本文算法的曲线相对于其他两种算法曲线的波动性小，相对平缓，这说明本文算法能够适应不同条件下的网络负载预测。从以上2个实验中发现本文算法能够有效的提高蜂群种群在解空间中的搜索能力，提高全局搜索效率，从而使得基于IABC的预测具有更好的效果。

6 结束语

针对云计算中的资源负载的预测效果，本文提出了云计算中的基于ABC优化的SVM预测模型。仿真实验说明本文算法能够在CPU负载和网络负载中具有比较好的预测精度，能够为云计算下的资源预测提供了一种参考。