一种混合优化的云计算资源调度算法

陈钦荣，刘顺来，林锡彬

（1.汕头职业技术学院经济管理系，广东汕头 515041；2.广州航海学院教务处，广东广州 510725；3.汕头市林百欣科学技术中等学校计算机教研室，广东汕头 515041）

一种混合优化的云计算资源调度算法

陈钦荣1，刘顺来2，林锡彬3

（1.汕头职业技术学院经济管理系，广东汕头 515041；2.广州航海学院教务处，广东广州 510725；3.汕头市林百欣科学技术中等学校计算机教研室，广东汕头 515041）

由于云计算的动态性、异构性等特点，其资源的分配策略面临着极大的挑战.传统的启发式算法由于本身算法原理方面存在一定的局限，难以有效应用到云计算环境的资源分配问题中.对此，充分结合云计算的特点以及云计算资源分配的实际需求，基于遗传算法和蚁群算法的优势设计了一种混合优化的云计算资源调度算法，最后通过分析验证了该算法的可行性.

云计算；资源调度；遗传算法；蚁群算法

1 云计算资源调度概述

1.1 云计算资源调度的特点

云服务的供应链主要包括四个部分的结构，分别为云服务的提供商、运营商、硬件商和用户.在云环境下，由用户和提供商签订相应的云服务租赁协议，然后根据实际的服务等级对云计算资源进行分配.云计算资源主要包括计算、存储以及通信等方面的资源，这些资源一般拥有多样性分布、动态异构性和互操作性等特点，这些特点使云资源的分配也产生了如下特点[1]：第一，资源的分配面向异构平台；第二，资源分配的总体规模较大，但是较为分散；第三，资源的分配必须具备可扩展性；第四，动态适应性.

1.2 云计算资源调度的主要问题

由于云计算资源的新特性，传统的资源分配模型和算法难以很好地解决云计算中的部分问题，比如算法性能的高效性、稳定性、安全性等[2].这些问题导致云计算资源分配策略相对单一，难以满足用户的多样性服务需求，同时，算法测试环境和模型的缺陷也影响了分配结果的真实性和可靠性及算法的效率，针对这些问题还需要进一步研究.

2 常用的云计算资源分配算法

常用的云计算资源分配调度算法包括人工神经网络算法、蚁群算法和遗传算法，下面分别对这三种算法进行介绍，并分析其中存在的优缺点：

2.1 人工神经网络算法

人工神经网络算法是基于生物神经网络运行原理所实现的一种模拟学习的资源分配算法[3].人工神经网络算法以阈值描述神经网络图中的神经元活性，同时会在两层神经元之间设置一个权值.通过人工神经网络算法，可以实现对超大规模数据的并行分布式储存.同时，人工神经网络算法能够同时融合多门科学技术，学习适应不确定系统.但是，其过高的复杂度导致很难精确地计算出各项性能指标的值，只能用来解决对精度要求不高的求解问题.

2.2 蚁群算法

蚁群算法是科学家通过对蚂蚁的觅食的寻路问题进行分析之后，实现的一种模拟搜索算法.蚁群算法具有较好的健壮性、并行性和鲁棒性，容易与其它算法进行组合，早期主要应用于解决TSP问题.目前蚁群算法在资源调度、分配问题等领域取得了较为突出的成果.

2.3 遗传算法

遗传算法是通过对生物自然进化选择的过程进行模仿所实现的一种模拟进化过程的搜索算法，主要用于复杂问题最优解求解[4].遗传算法具有较强的扩展性能，可以通过与其他算法的组合应用来解决大型复杂、动态问题.但是，遗传算法在搜索的过程中未对系统的反馈信息进行很好的利用，导致搜索存在一定的盲目性，算法在早期的效率相对较高，但是对局部的搜索效率较低，而且当迭代次数增加时，会对算法的效率产生影响.

3 云计算资源分配混合优化算法设计

3.1 遗传算法和蚁群算法混合原理

现代信息资源的快速增长使得云计算的规模不断增大，复杂度也迅速上升，在进行云计算资源分配过程中，仅仅通过单一的传统资源调度算法，很难实现最佳的优化分配.本文针对单一遗传算法和蚁群算法在资源调度方面的优缺点，设计了一种混合优化的云计算资源调度算法.该算法充分利用了遗传算法和蚁群算法的优点，能够取得更好的资源分配效果，从而有效解决云计算资源调度面临的多种问题.

本文选择先通过遗传算法的高效性获取资源的初次分配，然后利用分配的结果作为蚁群算法中概率转移公式的信息素，并对云计算资源之间的约束关系进行充分考虑，改进蚁群算法，最后根据具体的约束条件重新分配资源，从而达到最优分配效果.通过分析之后发现，本文所设计的混合优化算法比蚁群算法拥有更高的时间效率，同时收敛速度也优于遗传算法，遗传算法与蚁群算法的速度-时间关系如图1所示.

图1 遗传算法和蚁群算法速度-时间曲线

3.2 基本框架设计

现代社会发展以及云计算技术的发展，使得云计算的总体规模和结构的复杂性迅速上升，面对云计算资源的分配问题，传统算法的缺陷越来越明显，在这种情况下，混合优化算法应运而生.本文基于遗传算法和蚁群算法的优点设计了一种混合云计算资源分配优化算法，该算法的核心思想是通过利用遗传算法和蚁群算法各自的优势，规避各自的缺陷，取长补短，在效率和精度上共同实现最优[5].混合优化算法的基本框架如图2所示.

图2 混合优化算法基本框架流程

3.3 算法转换条件设计

如何选择遗传算法向蚁群算法转化的时间成为了混合优化算法的关键，如果过早进行转化，则会提前终止遗传算法；反之则会导致整个混合优化算法的效率下降，因此，需要合理地选择两种算法的转换时间点，才能同时保证算法的性能和质量.针对该问题，可以利用下面的方法控制遗传算法向蚁群算法的转换时间点[6]：

（1）为遗传算法设置最小和最大迭代次数；

（2）为遗传算法子代设置最小进化率；

（3）在遗传算法迭代区间，当连续n个子代群体的进化效率低于之前设置的遗传算法子代最小进化率，则终止遗传算法，以遗传算法结果作为蚁群算法的初始参数，进入蚁群算法.

3.4 算法流程设计

3.4.1 遗传算法求较优解

（1）设计目标函数

针对云计算资源调度的特点，增加以下几个约束条件，从而使得算法能够更好的应用到实际问题中，具体的约束条件分别为：任务的处理时间约束ProcessTime（e）、网络带宽约束BandWith（e）以及网络延迟约束NetDelay（e）.其中任务处理时间约束主要是指路径e末端的资源处理该任务所消耗的时间；网络带宽约束主要是指路径e提供带宽的最大值；网络延时约束是指路径e的最大网络延时.根据资源在受到上述约束条件之后的情况，将目标函数定义如下：

公式（1）中的maxT、minB以及maxN分别表示任务处理时间上限、带宽的最小限制以及网络延时的上限，三个约束条件的权重值分别利用A、B和C进行表示.

（2）设计适应度函数

通过适应度指标评价种群中的个体的优良度.适应度的值越大，则表明个体的性能越好，通过对适应度函数进行如下定义，能够很好地遵循遗传算法的原则：

公式（2）中的M表示种群的大小，totaltime(i)用于表示当前种群中第i个染色体完成任务分配的最长时间，Min用于表示当前种群所有染色体中的最小total值.由于可能出现totaltime(i)等于Min的情况，因此，需要将分子与分母同时+1，避免出现分母等于0的情况.从公式（2）可以看出，只有totaltime(i)会对f(i)的值产生影响.而这里通过取平方的方式来提高个体的显著程度.

（3）遗传编码

在云计算资源分配过程中应用遗传算法主要是将问题转化为遗传学中“优胜劣汰“的过程.在这个过程中，对基因的编码操作是解决问题的关键，目前常用的基因编码技术包括二进制编码技术、实数编码技术等[7].其中，实数编码技术能够针对问题变量的解空间编码，以便引入具体的领域信息，同时还能大大提高算法的效率和精度，下面选择实数编码技术进行编码：

首先，利用一个一维字符串对算法的解进行编码，其中包括左右两个子字符串，其中左子字符串用于任务分配的表示，右子字符串则用于任务结束的表示.LSrt(i)=a表示当将任务X1分配到资源Ya上进行执行，则必须在第i个位置对任务Xb的前驱任务进行排列.

（4）初始种群生成

初始种群的生成需要经历两个步骤，首先生成一维字符串的左子字符串，然后生成一维字符串的右子字符串.其中右子字符串的生成方式需要遵循一定的规则，从而满足任务调度之间特殊的约束关系.

（5）选择复制

在对所有染色体的适度值进行计算之后，需要以具体的约束条件选择满足条件的染色体，并通过轮盘赌法设置适度阈值，从而从所有染色体中随机选择性能较好的染色体，按照下面的步骤来实现：

Step1：从初始种群中按照概率Pc对染色体进行选择，然后对所选择的染色体的适度值进行计算，并将所有染色体的适度值的和Mi计算出来

Step2：采用随机数算法从[0,Mi]中选取一个随机数M0

Step3：根据染色体的编号顺序累加染色体的适度值，当累加的值≥M0时，则复制最后一个累加的染色体

Step4：反复执行Step2、Step3，当新生染色体数量达到原有染色体数量时，终止选择和复制操作.

（6）终止条件设计

在遗传算法中，涉及到大量的参数，具体参数的选择对算法的具体效率以及结果的精度均存在极大的影响，可以结合遗传算法相关的经验参数，对参数的具体值进行确定.

（7）获取最优解

在遗传算法中，最优解是一个染色体字符串[8]，然后根据所选择的实数编码方式对字符串进行逆向解码，从而获取资源分配的最优方案.

3.4.2 蚁群算法求最优解

（1）初始信息素转换

在本文设计的混合算法中，蚁群算法的初始解为遗传算法的最优解.单一的蚁群算法通常会由于初期信息素积累的缺少影响搜索效率，因此，为了确保算法具有较高的效率，需要将遗传算法获取的最优解进行转换，并将其作为蚁群算法的初始信息素.信息素初始值的设定如果过小则可能导致算法由于陷入到局部最优解而被强制终止，而初始值的值可能由于设置的过大而导致迭代过程失效.此时，结合遗传算法结束时，根据一定的概率从种群中选择具有较高适度值的个体作为蚁群算法的初始信息素，计算公式如下所示

公式中（3）的τ0表示信息素常数，表示根据遗传算法计算结果进行转化的信息素值.

（2）目标函数设计

蚁群算法优化求解的过程是在由遗传算法得到的较优解的基础上进行的.主要是对遗传算法所获取的较优解的二次求解.这里，将蚁群算法的节点域看作无向图Gaco(V,E),E，V和E分别表示所有资源的节点以及网络集合.蚁群算法的最终目的是从无向图的所有资源的网络几何中寻找一条最优路径.

（3）信息素更新

在实际求解时，为了避免陷入局部最优解，应该首先对蚂蚁所选线路的局部信息素进行更新，假设蚂蚁从节点i向j转移后，则可以利用公式（4）更新τij的信息素.

公式（4～5）中的ξ∈(0,1)、1-ξ以及τ0分别表示信息素的更新系数、剩余系数和常数；Δτkij(t)表示t时刻第k只蚂蚁在路径eij上所留的信息素，S表示信息素的强度.

公式（6）和（7）主要是针对所有蚂蚁完成一次迭代更新之后，如何对信息素进行全局更新

（4）终止条件设计

只要满足下面的任意一个条件，即可终止蚁群算法：

达到最大设计迭代次数；

新种群的子代进化率比设计值更低.

（5）算法流程

下面给出了蚁群算法的具体执行流程：

Step1：对蚁群算法的控制参数进行初始化设置

Step2：设置条件满足算法的中断要求

Step3：根据相关的设计规则对遗传算法获取的较优解进行转换，使其能够与蚁群算法的每个资源节点上的蚂蚁一一对应

Step4：对每只蚂蚁分配结果的目标函数进行计算，以获取当前的最优解

Step5：更新局部信息素值，在完成一次完整的迭代更新后，对信息素值进行全局更新

Step6：根据终止条件对算法进行判断，当算法满足终止条件之后终止算法，否则跳转执行Step3.

4 算法模拟分析

4.1 开发环境搭建

选择VB语言模型实现上述算法，并以Windows 7系统作为系统开发环境.在程序设计过程中，主要从两个方面进行：首先是程序的逻辑控制模块的设计，主要包括算法参数模块、问题参数模块等，这些模块主要负责调用逻辑函数，并将结果通过图标的形式展现出来；其次是类模块，对各类逻辑函数进行定义和封装.整个程序设计了问题参数、算法参数、基础参数、基础数据、计算控制界面和分析对比界面等，并在模块中对数据连接、遗传算法核心函数、蚁群算法核心函数以及混合优化算法核心函数等进行了定义.图3、图4分别给出了问题基本参数设计界面和混合优化参数计算控制界面.

图3 问题基本参数设计

图4 混合优化算法计算控制界面

4.2 算例设计

首先，为了方便计算，创建一个包括9个处理任务的虚拟云计算网络，任务的最大并发数为4，最大深度为6，并结合生成的前驱后继关系确定具体的深度值.不同任务在不同资源点的处理时间和各任务节点直接的优先度以及算法的参数值如表1～表3所示.进行算法的参数值的设定时，任务处理时间在区间[1，6]时，通过随机函数获取，并且任务有限度根据DAG图的最大深度并以随机函数获取.表2通过单个DAG图中各个节点的前驱节点以及后继节点对优先度进行说明.

4.3 混合优化算法参数设定

根据相关研究[9]，以应用最多的模型为例，给出了如表3所示的遗传算法和蚁群算法的参数设置情况，下面均基于表3的参数完成算法的计算.

表1 不同任务在不同资源点上的处理时间表

表2 各任务节点的优先度

表3 参数设定表

4.4 分配结果

根据图5给出的系统演示结果可以看出，在整个遗传过程中，种群进化到第332代之后，进化率逐渐稳定，其中，第121代产生了最优解，任务分配时间为28.44 ms，而种群的进化率低于最小进化率出现在122～131代之间，此时，中断遗传算法并开始蚁群算法.蚁群算法在计算到第36条路径之后，获取最优解，最优的路径调配时间为22.13 ms，即在遗传算法结果的基础上获取到更优的解.

下面给出了最优分配方案：（121432233 125436879）—（染色体遗传顺序任务处理的顺序），具体分配执行策略如下所示：

资源点Y1：X1→X3

资源点Y2：X2→X6→X7

资源点Y3：X5→X8→X9

资源点Y4：X4

4.5 算法对比分析

为了了解本文设计的混合优化云计算资源调度算法的实际性能，从调度时间、迭代次数以及负载均衡3个方面的性能与单一遗传算法和蚁群算法进行了对比分析.

图5 系统运行结果演示（注：只截取最优解这一阶段的数据）

通过20～100个任务数以及8个资源点对混合优化算法进行云计算资源调度模拟实验.其中，表4给出了3种算法任务分配时间对比的数据（3种算法采用相同的参数设置）.

表4给出了任务节点数为20～100之间时，3种算法的调度耗时.从表4中的数据能够看出，遗传算法在[20,40]节点区间具有较快的收敛速度，但是当迭代次数继续增加后，收敛速度不断下降；而蚁群算法在前期的收敛速度较慢，而随着信息素的不断积累，任务处理的速度不断提升，而混合优化算法刚好将两种算法的优势利用起来，具有相比单一使用遗传算法和蚁群算法更好的收敛速度.

表4 三种算法的任务分配时间对比（单位：ms）

表5给出了任务数为20～100之间时，3种算法寻找最优解的迭代次数.通过表5中的数据可以看出，3种算法的迭代次数随着任务节点的增加呈现出上升趋势，但是相对来看，单一遗传算法比单一蚁群算法迭代次数更多，性能相对较差，而混合优化算法则具有明显优势.

表6给出了任务数为100时，8个资源点在3种算法下的负载数据.从表6中的数据来看，单一蚁群算法和遗传算法在3、5、8资源点上的负载相对较小，而在1、6、7三个资源点上的负载较高，而混合优化算法每个资源点的负载较为平均，充分说明了混合优化算法具有较好的负载均衡性能.

4.6 结果分析

从上面的分析来看，如果任务数量小于50，则本文所提出的优化算法的性能优势相对较小，而随着任务数量的不断增加，这种优势则逐渐凸显出来.从实际情况来看，云计算资源分配需要进行处理的任务数量规模非常大，因此，本文所提出的优化算法具有较大的优势.

表5 三种算法迭代次数对比

表6 三种算法各资源点负载情况对比

5 结论

本文针对云计算资源分配的特点和面临的问题，基于遗传算法和蚁群算法设计了一种混合优化算法.本文所设计的混合优化算法首先通过遗传算法快速获取较优解，然后利用蚁群算法进一步提高求解精度，这样可以充分利用两种算法的优点，并避开各自的缺点.使得资源分配的效率和精度大大提高，算法也更加符合云环境下资源分配面临的实际问题.

[1]华夏渝，郑骏，胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报（自然科学版），2010（1）：127-134.

[2]林伟伟，齐德昱.云计算资源调度研究综述[J].计算机科学，2012（10）：1-6.

[3]姜华杰.基于QoS的云计算资源分配算法[D].太原：太原理工大学，2012.

[4]徐达宇.云计算环境下资源需求预测与优化配置方法研究[D].合肥：合肥工业大学，2014.

[5]方晓平，陈年生，郭宇，等.云计算资源分配策略研究[J].湖北师范学院学报（自然科学版），2013（4）：56-62.

[6]王登科，李忠.基于粒子群优化与蚁群优化的云计算任务调度算法[J].计算机应用与软件，2013（1）：290-293.

[7]薛景文，田玉玲.基于改进克隆选择算法的云计算任务调度算法[J].计算机应用与软件，2013（5）：167-170.

[8]GARG S K，YEO C S，ANADASIVAM A，et al.Environment-conscious scheduling of HPC applications on distributed cloud-oriented data centers[J].Journal of Parallel and Distributed Computing，2011，71（6）：732-749.

[9]BUYYA R,RANJAN R,RODRIGO N C.Modeling and simulation of scalable cloud computing environments and the cloud-Sim toolkit:challenges and opportunities[R].The Seventh High Performance Computing&Simulation International Conference（HPCS），2009.

A Hybrid Optimization Algorithm for Cloud Computing Resource Scheduling

CHEN Qin-rong1,LIU Shun-lai2,LIN Xi-bin3
（1.Department of Economic&Management,Shantou Polytechnic,Shantou,Guangdong,515041; 2.Dean's Office,Guangzhou Maritime University,Guangzhou,Guangdong,510725; 3.Computer Teaching and Research Section,Shantou Lin Baixin Science and Technology School,Shantou,Guangdong,515041）

Due to the dynamic nature of cloud computing，heterogeneous characteristics，its resource allocation policy faces great challenges.Due to the limitations of traditional heuristic algorithms，it is difficult to effectively applied to the resource allocation problem in cloud computing environment.To fully combine the characteristics of cloud computing with the actual demand for the allocation of cloud computing resources, meanwhile，basing on the advantages of genetic algorithm and ant colony algorithm，we design a kind of hybrid optimization of cloud computing resource scheduling algorithm,and finally through the analysis we verify the feasibility of the algorithm.

cloud computing；resource scheduling；genetic algorithms；Ant Colony algorithm

TP 312

：A

：1007-6883（2016）06-0015-09

责任编辑 朱本华

2016-03-22

汕头职业技术学院2015年“创新强校工程”项目（项目编号：STP-SX-023）.

陈钦荣（1970-），男，广东饶平人，汕头职业技术学院经济管理系实验师.