基于智能算法的云计算资源调度的研究与实现(四)

另外，还有针对非约束多目标优化问题的结合人工蜂群算法的MO-ABC /DE 算法[19]。由于篇幅问题，本文不再赘述。

3.禁忌搜索

禁忌搜索简称TS（Tabu Search或Taboo Search），禁忌搜索的思想由Glover在1986年首先提出。总体上来说，禁忌搜索是索属于全局搜索、逐步寻优的一种算法，禁忌搜索通过模仿人类智力过程进行，它借助引入灵活的存储结构和对应的禁忌基准来避免冗余搜索，同时，利用藐视准将被禁忌的良好状态部分赦免，从而确保搜索的多样化、全局化，不同于模拟退火算法和传统遗传算法。

禁忌搜索算法中最核心的思想，是借助标注对应已搜索的局部最优解对象，并在后继迭代过程中，尽量避开他们，以避免局部最优、保证搜索路径的多元化。

   以禁忌搜索为代表的启发式算法，初始解的最佳拟合启发得到的解集，利用随机移动的方法搜索邻居。直到达到满足需要的移动时间终止。通常来说，解决池中候选数应为移动时间的一半，借助随机移动来提高访问不同候选解的概率。禁忌搜索使用代表短期记忆的近因和代表长期记忆的频率，为了禁止搜索从其他地区寻求解决空间高效的发现是局部最优并迫使其他地区尚未遇到的探索。

4.PSO算法与进化算法结合

PSO算法（粒子群优化算法）也属于智能优化算法的一种，每个粒子表示种群中可能的的最优解，算法对粒子的运动位置记性迭代记录，记录的属性为粒子的位置、速度和适应值，对于同一个粒子，有粒子个体所经历的适应值最高的最优位置记为Pbest。在整个粒子群中有种群中所有粒子的最优位置记为Gbest。其中Pbest代表个人最佳，而Gbest代表全局最佳。相比进化算法与PSO算法的不同点，易知粒子群信息在PSO算法中单向流动，随着粒子的迭代时间增加，粒子将单方向传递至局部收敛，因而PSO算法收敛速度较快，但容易陷入局部最优。学者周丽娟等将PSO算法与进化算法结合，利用进化算法交叉、变异策略，使全局搜索范围扩大，该算法借由定义的取向矩阵引导了粒子的搜索方向，限定了粒子的搜寻方向，有助于得到全局最优解，提升了云计算资源调度的效率。

此外，PSO算法还有其他几种发展方向：（1）调整PSO的参数来平衡算法的全局探测和局部开采能力。如Shi和Eberhart对PSO算法的速度项引入了惯性权重，并依据迭代进程及粒子飞行情况对惯性权重进行线性（或非线性）的动态调整，以平衡搜索的全局性和收敛速度。2009年张玮等在对标准粒子群算法位置期望及方差进行稳定性分析的基础上，研究了加速因子对位置期望及方差的影响，得出了一组较好的加速因子取值。（2）设计不同类型的拓扑结构，改变粒子学习模式，从而提高种群的多样性，Kennedy等人研究了不同的拓扑结构对SPSO性能的影响。针对SPSO存在易早熟收敛，寻优精度不高的缺点，于2003年提出了一种更为明晰的粒子群算法的形式：骨干粒子群算法（Bare Bones PSO，BBPSO）。（3）采用小生境技术。小生境是模拟生态平衡的一种仿生技术，适用于多峰函数和多目标函数的优化问题。例如，在PSO算法中，通过构造小生境拓扑，将种群分成若干个子种群，动态地形成相对独立的搜索空间，实现对多个极值区域的同步搜索，从而可以避免算法在求解多峰函数优化问题时出现早熟收敛现象。基于“分而治之”思想的多种群PSO算法，其核心思想是将高维的目标函数分解成多个低维函数，然后每个低维的子函数由一个子粒子群进行优化，该算法对高维问题的求解提供了一个较好的思路。

（三）纵向改进的进化算法

差分进化算法是基于差分变异操作的群体智能算法，因为其构造单一、容易完成、收敛迅速、鲁棒性强等长处，被广泛使用于全局优化问题。标准的DE 算法的流程分为初始化种群、评估、变异、交叉、选择等操作产生下一代的种群，进过迭代更新直至出现全局最优解。

标准的 DE 算法虽然总体上优于进化算法，但参数选择困难，控制参数选择不合适，容易造成搜索停滞和个体早熟收敛的问题。许多科学家针对计算复杂度较高的工程问题，提出了改进的DE 算法。有科研工作者提出基于差分进化算法的多目标优化算法; Das 等利用随机设置和时变设置来改变参数F; Liu提出基于模糊逻辑控制器的自适应调节参数的算法; Epitropakis 等研究的BDE 算法将线性混合搜索与开发变异算子；ROY提出分布式存储池进化算法，从而改善了传统分布进化算法松散耦合的缺陷。改进的DE 算法具有增加种群的多样性、加大全局搜索能力、稳健、快速收敛的优势。

差分演化算法的参数优化方法求解优化问题的基本思想是: 模仿生物进化的原理，使种群不断地向目标进化。差分进化算法分为以下几个步骤：

种群初始化：差分演化算法优化中种群的个体通常采用实数编码。

适应值函数：采用交叉验证准确率作为适应值，用个体的适应值作为选择依据。

变异：可采用多种变异方法，如采用DE/rand/1变异方法，即：

其中，、、为种群中随机抽取的三个不同的个体，F为缩放因子。

交叉：可采用二项式交叉算子，将变异种群和原种群进行交叉操作，具体如下：

其中表示交叉后得到的种群，为之间的随机数，j表示个体的第j个分量，为交叉概率，为 [1,2,…,n]之间的随机量，用于保证新个体至少有一维分量由变异个体贡献。首先，给交叉算子随机产生一个维标识，确保最后产生的试验个体至少有一维来自变异个体，保证种群的多样性。然后，针对当前个体的每一维随机产生一个0到1之间的实数，如果该随机实数小于交叉率，则试验个体来自变异个体；否则，试验个体来自当前个体。

选择：选择保留适应值高的个体作为优秀的个体，不断淘汰适应值低的较差个体。

四、结论与展望

（一）结论

本文重在解决利用智能算法进行云计算资源调度。云计算广泛运用的同时高能耗问题也随之而来。云计算资源调度在云计算中是最关键一个环节之一，要对云数据中心的高能耗进行节能减排，首先可以在云计算资源调度中进行。本文的目的在于从提升智能算法在云计算资源调度中的作用，降低云计算中的能耗。本文首先对云计算的概念和资源调度进行简要介绍，然后从云计算中心的能耗来源方面引出优化资源调度的重要性。接着从智能算法在资源调度中的应用进行展开，列举了传统的智能算法、横向改进的进化算法，如模拟退火与进化算法结合、蚁群算法与进化算法结合、禁忌搜索算法、PSO算法与进化算法结合 ，纵向改进的进化算法如差分进化算法等。归纳对比了几种资源调度算法的特点。这几种智能算法不仅在云计算资源调度问题上都能产生重大作用，而且对提高算法效率和节能减排上都有益处。

（二）展望

本文对基于进化算法的云计算资源调度相关工作进行了总结和分析，虽然云计算资源调度算法越来越高效，但仍然存在着一些问题，本节将对未来基于进化算法的云计算资源调度进行展望，并归纳总结为三个方面。分别是结合云计算安全性、结合用户满意度和结合数据中心的异构性。 结合云计算安全性，即对于数据保密等级高的特殊机构来说，云计算的安全性仅依赖于提供云计算服务商来保障，而对于云计算本身的安全问题约束，将是下一步研究的重点；结合用户满意度，即传统的众多云计算资源调度过程中进化算法着重考虑算法的执行效率和算法性能上减低能耗，因此云计算服务质量常不作为约束。可以在算法优化时建立用户满意度机制，若超过设置的SLA阈值，就停止优化或以别的方式改进算法，这也将是下一步研究的重点；结合数据中心的异构性，即不同的数据中心采用配置的服务器不可能完全一致。因此计算中心的节点的性能也是异构的，今后的算法优化需要数据中心的异构性，把硬件设备的性能纳入算法优化的考虑范围之内。

参考文献

 [1] 李坤成,江亮,鲜明.一种面向云计算环境下虚拟机的威胁建模方法[J].现代电子技术,2012,35(19):70-72.

[2] Singh S, Jeong Y S, Park J H. A survey on cloud computing security: Issues, threats, and solutions[J]. Journal of Network & Computer Applications, 2016, 75:200-222.

[3] 许小龙. 支持绿色云计算的资源调度方法及关键技术研究[D].南京大学,2016.

[4] Tsai J T, Fang J C, Chou J H. Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm[J]. Computers & Operations Research,2013, 40(12):3045-3055.

[5] 顾阳,李敏,李华.云计算任务调度算法综述[J].现代计算机(专业版),2018(13):31-34.

[6] 刘东山,周显春.云计算调度算法综述[J].计算机安全,2012(10):49-53.

[7] Singh S, Chana I. A Survey on Resource Scheduling in Cloud Computing: Issues and Challenges[J]. Journal of Grid Computing, 2016, 14(2):217-264.

[8] 李翔. 云数据中心的温度建模与节能调度方法研究[D].浙江大学,2017.