0 引言

云平台^[1]借助于虚拟化技术使得应用资源的动态按需配置成为可能^[2-3]，可以同时为多个用户提供共享资源池^[4]，既极大地改善了资源的有效使用，又增加了云服务提供商的收益^[5-6]。云环境中的资源分配可以分为两个层次：粗粒度资源分配和细粒度资源分配。粗粒度资源分配是将各应用虚拟机映射到不同的物理节点上，多个应用虚拟机共享同一个物理节点上的硬件资源。粗粒度资源分配解决的是多个应用虚拟机与多个物理节点之间的映射关系^[7-8]。细粒度资源分配是在某一物理节点上调整每个应用虚拟机的具体资源配置，细粒度资源配置解决的是确定单一物理节点上的资源在其上不同虚拟机间的分配配额，以保证各应用虚拟机的服务级目标^[9]。由于细粒度资源分配的局限性，它对云平台整个资源使用效率的影响有限，粗粒度资源分配方法决定了整个云平台系统资源使用的有效性。目前大多数云平台资源分配调度研究都是针对于粗粒度资源分配，本文所讨论的动态资源配置问题主要针对粗粒度资源调度。

云平台的粗粒度资源调度大多关注于合并物理节点上的虚拟机负载，或者缩短各任务的完成时间^[10-11]，以减少激活物理节点的数量，从而达到节能目的，实现绿色计算；还有一些研究侧重于通过资源调度来提升云服务提供商的服务收益^[12]。文献[7]和文献[8]分别采用遗传算法、约束规划的方法来寻找虚拟机在物理节点上的最佳分布，最终使得已使用的物理节点数量最少；文献[10]和文献[11]分别提出改进的基于多目标免疫系统的任务调度算法和离散人工蜂群算法来缩短任务完成时间、降低任务执行费用、实现资源负载均衡等。然而，这些粗粒度资源调度方法忽略了云环境中应用负载的动态性，没有考虑到各物理节点状态的稳定性。尽管各应用虚拟机在当前分布状态中使用了比较少的物理节点，但是随着应用负载的变化，这些物理节点的状态可能在不久的将来又会重新出现资源热点，激发新一轮动态资源的配置需求。

本文就是针对上述现象而提出的一种新的考虑物理节点稳定性的粗粒度资源调度方法。基于应用负载的预测信息，采用遗传算法寻找各物理节点较为稳定的虚拟机分布状态，同时兼顾考虑旧虚拟机分布状态到新虚拟机分布状态之间的转换开销^[13-14]比较小。

本文的工作主要有以下三个方面：1)提出面向物理节点稳定性或者虚拟机分布稳定性的动态资源分配方法；2)设计了基于稳定时间、迁移次数等面向虚拟机分布稳定性的多目标优化的遗传算法(Multi-Objective Genetic Algorithm for nOde Stability, MOGANS)，采用组编码的方式，并基于非支配排序遗传算法Ⅱ(Non-dominated Sorting Genetic Algorithm Ⅱ, NSGA-Ⅱ)定义适应度函数来评判各种虚拟机分布方式的优劣；3)实现了算法MOGANS，将它和文献[7]提出的算法——面向节能和多虚拟机重分布开销的遗传算法(Genetic Algorithm for greeN computing and Numbers of migration, GA-NN)进行了性能比较，并分析了它的运行开销。仿真实验结果表明，MOGANS得到的虚拟机分布方式的稳定时间是GA-NN的10.42倍；同时，MOGANS也较好权衡了多虚拟机分布的稳定性和新旧状态转换所需的虚拟机迁移开销之间的关系。

1 动态资源配置问题

在云环境中，各应用被封装部署在不同虚拟机中^[15-16]，多个虚拟机可以共享同一个物理节点的计算资源。由于系统虚拟化技术的去耦合性，各虚拟机可以在不同的物理节点之间平滑无缝迁移^[14]。虚拟机迁移是云平台下粗粒度动态资源配置的重要方式。动态资源配置是随着虚拟机应用负载的变化，实时调整应用的资源配置。

本文讨论的动态资源配置问题假定云平台是同构环境，即每个物理节点的资源配置参数是一样的，且物理节点和虚拟机数量固定，所有物理节点提供的资源也能够满足所有应用虚拟机的需求。应用虚拟机的资源请求只考虑两类资源——内存和处理器。

为便于讨论，在表 1中给出了一些符号定义。

云平台中，物理节点的状态可以分成如下三种：热状态、温状态和冷状态。热状态下，该物理节点上所有应用虚拟机的总负载量超过了它所能承载的限度，出现了资源热点，资源竞争频繁，应用服务质量有所下降，这时需要动态扩大应用虚拟机的资源配置。热状态下的物理节点称为热节点，热节点需要通过虚拟机迁移方式减少其上应用虚拟机的负载。温状态下，该物理节点上的资源供给和需求大致相当，能保证应用服务质量。物理节点处于温状态是一种比较理想的状态，资源得到有效使用，避免浪费。冷状态是相对于资源供给，资源的需求量相对较低，大多数资源处于空闲状态，造成资源和能源的浪费。

多个虚拟机在物理节点上最理想的分布方式，是每个物理节点都处于温状态，而且这种状况保持尽可能长的时间。为阐述多虚拟机分布的稳定性，我们引入以下几个概念。

定义1 多虚拟机在物理节点上的分布方式D_k，是指虚拟机和物理节点的映射方式，可以用布尔矩阵X=(x_ij)_M×N来表示。

定义2 物理节点node₁的稳定时间T_node1，是指该节点从某个时刻开始保持温状态或冷状态的时间间隔。显然，热节点的稳定时间为0。

定义3 多虚拟机分布方式D_k的稳定时间T_Dk，是指从某个时刻开始，每个节点都保持温状态或冷状态的时间间隔。T_Dk和物理节点稳定时间的关系如下所示：

$ {T_{{D_k}}} = \min \left\{ {{T_{nod{e_1}}}, {T_{nod{e_2}}}, \cdots {T_{nod{e_M}}}} \right\} $

因此，云平台的动态资源分配问题可以模型化如下：已知各虚拟机负载的动态变化(包括现在的状况和预测的未来负载信息)，寻找多虚拟机在物理节点上的最佳放置方案，使其具有最长的稳定时间和最少的虚拟机迁移次数。问题的目标和约束条件定义如下：

$ \left\{ {\begin{array}{*{20}{l}} {\max {T_{{D_k}}}} \\ {\min \sum\limits_{j = 1}^N {{m_j}} } \end{array}} \right. $

(1)

$ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\sum\limits_{i = 1}^M {{x_{ij = 1}};j = 1, 2, \cdots, N} $

(2)

$ {C_i} \ge \sum\limits_{j = 1}^N {{x_{ij}}C{'_j}} ;i = 1, 2, \cdots, M $

(3)

$ Me{m_i} \ge \sum\limits_{j = 1}^N {{x_{ij}}Mem{'_j}} ;i = 1, 2, \cdots, M $

(4)

$ {x_{ij}} \in \left\{ {0, 1} \right\}, {m_i} \in \left\{ {0, 1} \right\};i = 1, 2, \cdots, M, j = 1, 2, \cdots, N $

(5)

动态资源配置问题有两个目标：第一个是使得新的虚拟机分布具有最长的稳定时间(max T_Dk)，这个目标意味着，热节点不会在较短的时间内出现在新的映射状态中; 另一个目标是从当前状态到新的分布状态只需要迁移最小数量的虚拟机($ \min \sum\limits_{j = 1}^N {{m_j}} $)。第二个目标要求虚拟机从当前状态(用X=(x_ij)_M×N表示)向新状态(用X′=(x_ij′)_M×N表示)的转换具有最小的迁移开销。其中，m_j的定义如下：

$ {m_j} = \left\{ {\begin{array}{*{20}{l}} {0, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {x_{ij}} = x{'_{i'j}} = 1{\kern 1pt} {\kern 1pt} {\kern 1pt} {\text{and}}{\kern 1pt} {\kern 1pt} {\kern 1pt} i{\text{ = }}i'} \\ {1, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {x_{ij}} = x{'_{i'j}} = 1{\kern 1pt} {\kern 1pt} {\kern 1pt} {\text{and}}{\kern 1pt} {\kern 1pt} {\kern 1pt} i \ne i'} \end{array}} \right.{\kern 1pt} {\kern 1pt} $

约束条件中：式(2)表示每个虚拟机只在一个物理节点上；式(3)表示一个节点上的所有虚拟机的处理器资源请求总和不会超过该节点所能提供的相应资源总和；式(4)表示一个节点上的所有虚拟机的内存资源请求总和不会超过该节点所能提供的相应资源总和；式(5)说明变量x_ij和m_i是布尔变量。

2 MOGANS

云平台中的动态资源分配问题是非确定多项式完全(Non-deterministic Polynomial Complete, NPC)问题，很难在多项式时间内找到其最优解。遗传算法借助于生物学领域的进化学说和遗传学理论，通过计算机模拟自然生物进化过程与机制来求解问题，可以在多项式时间内找到云平台动态资源配置问题的近似最优解^[17]。遗传算法可以在较大问题解空间内进行全局多方向随机搜索，不需要了解问题域的先验知识^[18]。

本文针对云平台的动态资源分配问题，设计了面向虚拟机分布稳定性的基于多目标优化的遗传算法MOGANS，算法的设计主要考虑以下几个方面：编码和初始代生成、主要操作算子和适应度函数。编码是将云平台的动态资源配置问题中各个因素和生物进化、遗传学中的染色体、基因等要素对应起来，将实际应用的求解问题模拟成自然物种进化演变过程；初始代是遗传算法模拟生物进化演变过程的源头，初始代生成是在虚拟机的当前分布状态的基础上随机进行的；遗传算法的主要操作算子包括交叉、变异和选择，而适应度函数则主要用来量化染色体或个体的某个属性或属性组，并由此来评判染色体或个体的优劣。

2.1 编码和初始代的生成

编码是将云平台的动态资源配置问题的求解数据转换为遗传空间的基因型结构数据，是遗传算法的重要部分。为了准确描述云环境中虚拟机和物理节点之间的映射关系，本文采用组编码方式。组编码方式^[19]将每个物理节点及其上承载的虚拟机共同描述为一个基因，多个基因形成的序列构成染色体或个体，popSIZE个个体构成一个群体。遗传算法以这popSIZE个个体作为初始点开始迭代生成若干子代，在子代中寻找求解问题的近似最优解。

图 1给出了组编码的实例。在图 1中，6个虚拟机被部署在三个物理节点上。相应地，在染色体里包含三个基因，每个基因对应一个物理节点及其上的虚拟机集合。一个染色体或者个体则代表着云平台动态资源分配的一种可能的解决方案——多个虚拟机在物理节点上的一种分布方式。

遗传算法要解决的是云平台的动态资源配置问题，多虚拟机已经分布在各物理节点上，由于应用虚拟机负载的变化，当前的虚拟机分布方式变得不再适合，需要调整虚拟机在物理节点上的分布方式。因此，遗传算法的初始代应该包含虚拟机的当前分布方式信息，虚拟机的当前分布方式对应的组编码作为初始代的一个个体。而初始代的其他个体则随机产生，随机方式可以提供问题求解更大的搜索空间。

群体规模影响着遗传算法的最终结果及其执行效率：当群体规模popSIZE太小时，遗传算法容易陷入局部最优解，性能一般不会理想；而群体规模popSIZE太大时，算法复杂度较高。popSIZE一般为10~160^[20]。

2.2 主要操作算子

遗传算法主要有三个重要的操作算子：交叉、变异和选择。

2.2.1 交叉

交叉是两个父体产生后代并从父代那里遗传更多有意义的信息的操作，是遗传算法的主要操作。由于组编码模式可能造成不同染色体的长度各异，交叉操作应能够在具有不同长度的染色体上进行。

如图 2所示，交叉算子主要有以下4个步骤：

1)在两个父个体A、B中分别随机选择交叉点。交叉点即为染色体中的某个基因，如图 2(a)所示的node₄{v₂, v₇}和node₂{v₅}。

2)相互交换两个父个体中交叉点上的虚拟机。交换后，同一个父个体中会出现包含相同虚拟机的不同基因，如图 2(b)所示的个体A，基因node₃{v₅，v₈}和基因node₄{v₅}，个体B的基因node₂{v₂，v₇}、基因node₃{v₂，v₆}和基因node₄{v₇，v₈}。而在实际的云平台中，同一个虚拟机只能出现在一个物理节点上，相应地，这些包含相同虚拟机的基因需要被调整，保证同一个虚拟机只能包含在一个基因中。

3)处理和交叉点包含相同虚拟机的基因以及由于交叉操作而丢失的虚拟机。两个交叉点相互交换虚拟机后，同一个个体中会出现包含相同虚拟机的不同基因。删除和交叉点含有相同虚拟机的基因上重复的虚拟机，该基因所包含的剩下的虚拟机需要被重新放置，而该基因对应的物理节点的状态由“已使用”变为“未使用”。如图 2(c)中，个体A的基因node₃{v₅，v₈}中的v₅因为和交叉点上的虚拟机重复，需要被删除，node₃上的v₈需要被重新放置，插入到待放置的虚拟机队列中，等待被重新放置。另外，两个交叉点相互交换虚拟机后，会丢失一些虚拟机，如图 2(c)中，个体A少了虚拟机v₂和v₇，这些丢失的虚拟机也需要被插入到待重新放置的虚拟机队列中。

4)使用首次适应探索法将上一步得到的需要重新放置的各虚拟机插入到染色体中。物理节点分为两种状态：“已使用”和“未使用”，将两种不同状态的物理节点分别按节点序号进行排列，形成两个队列。首先，根据虚拟机的资源请求使用首次适应探索法在“已使用”队列上找到合适的物理节点，该物理节点必须有足够的空闲资源容纳该虚拟机。如果“已使用”队列上没有任何物理节点有足够的空闲资源来承载该虚拟机，则在“未使用”队列上选择一个节点。图 2(d)显示了重新放置虚拟机的最后结果。这样，两个父节点(node₁{v₁，v₆}，node₂{v₃，v₄}，node₃{v₅，v₈}，node₄{v₂，v₇})和(node₁{v₁，v₃，v₄}，node₂{v₅}，node₃{v₂，v₆}，node₄{v₇，v₈})经过交叉操作，得到两个子个体：(node₁{v₁，v₆，v₇}，node₂{v₃，v₄，v₈}，node₄{v₅，v₂})和(node₁{v₁，v₃，v₄}，node₂{v₂，v₇，v₆}，node₃{v₅，v₈})。

交叉并不一定在任意两个父个体之间进行，该操作的发生有一定的概率。交叉概率q_c控制着交叉操作被使用的频率。若交叉概率q_c设置过大，遗传算法开辟新的搜索区域的能力会增强，但高性能模式遭到破坏的可能性也会增大；若交叉概率设置太低，遗传算法搜索可能陷入迟钝状态。一般地，交叉概率q_c设在0.25~1.00^[20]。

2.2.2 变异

变异操作可以使得个体变得和其父代个体不一样，它以任意的方式增加新的信息以扩大搜索空间并避免陷入局部优化。变异是遗传算法中辅助性的操作，其主要作用是维持群体的多样性。

在算法MOGANS中，变异操作是按照首次适应探索法重新放置随机选择的变异点上的虚拟机，并将该变异点对应的物理节点的状态由“已使用”变为“未使用”，变异点即为染色体中的一个基因。

图 3给出了一个变异的例子。如图 3(a)所示，在染色体中随机选择变异点node₂{v₅}。虚拟机v₅被插入到待放置的虚拟机队列中，物理节点node₂的状态由“已使用”变为“未使用”。将v₅按照首次适应算法重新放置后，即得到一个变异后的染色体，如图 3(c)所示。经过变异操作，个体由(node₁{v₁，v₃，v₄}，node₂{v₅}，node₃{v₂，v₇}，node₄{v₆，v₈})变成(node₁{v₁，v₃，v₄}，node₃{v₂，v₇}，node₄{v₆，v₈，v₅})。

变异操作也是按一定概率q_m进行的。一般而言，较低的变异概率可防止群体中重要而单一的基因的可能丢失，而较高的变异概率会使得遗传算法趋于纯粹的随机搜索。本文根据经验值设定q_m值为0.05。

2.2.3 选择

选择操作是从子代中选择较优个体作为新一代父体，继续重复迭代过程。个体的优劣是通过定义适应度函数来衡量的，而适应度函数是以个体的属性(比如：个体的稳定时间、迁移次数等)为基础的。本文中，个体的适应度函数的定义是借助于NSGA-Ⅱ的分级排序思想。算法NSGA-Ⅱ先根据个体之间的支配与非支配关系将个体分成若干等级，同一级别内个体再通过定义拥挤距离来排序。适应度函数的具体定义见第2.3节。

2.3 适应度函数

适应度函数主要是用来衡量个体的优劣性，其定义是基于个体的某个属性或者属性组，其目标是将多个个体按照优劣进行线性排序。本文采用非支配排序遗传算法NSGA-Ⅱ^[21]来定义适应度函数。NSGA-Ⅱ根据个体之间的支配与非支配关系分层实现，适合于多目标优化问题，非劣最优解分布均匀，算法的计算复杂度适中^[21]。

适应度函数的计算分成两个步骤：1)首先根据每个个体的稳定时间、迁移次数等计算个体的非支配等级，同一等级内可能包含多个个体；2)在同一等级内，计算每个个体的拥挤距离来体现每个个体的优劣。

非支配等级的计算是基于优化的多个目标判断个体之间的支配关系或非支配关系。遍历所有个体，计算每个个体被支配的个体数及其支配的个体集合。支配关系判断dominate(ch1, ch2)的伪代码如下所示，如果相对于个体ch2，个体ch1的稳定时间长并且迁移次数少(第1)行)，则个体ch1支配ch2，否则，个体ch1不能支配ch2。任意两个个体a、b的支配关系只可能是以下三种情形之一：a支配b；b支配a；a、b相互不能支配。

1)  if(ch1的迁移次数 < ch2的迁移次数﹠﹠

ch1的稳定时间 > ch2的稳定时间)

2)    return TRUE;

3)  else

4)    return FALSE;

如果没有其他任何个体支配个体a，则个体a的等级设为1为最高级，也是最优等级，即个体等级值越低，级别越高，个体越优；其他个体的等级是基于支配个体的等级计算的，个体a的等级为支配a的级别最低的个体的级别加1。计算个体等级non_dominated-sort (CH)的伪代码如下所示。伪代码中，从第1)行到第15)行是计算每个个体ch1支配的个体集dSet[ch1]以及被支配的个体数量ddn[ch1]。如果ddn[ch1]值为0，则ch1的等级为1；第16)行到第30)行是计算除等级1之外的个体的等级，个体的等级取决于支配该个体的最低等级。

CH是所有个体的集合；

dSet[ch1]为个体ch1支配个体的集合；

ddn[ch1]为支配个体ch1的总的个体数；

rank[ch1]表示个体ch1的等级；

CHSet[i]表示种群中处于i等级所有个体的集合；

1)  for each ch1 in CH

           //计算每个个体的支配个体集合、被支配个体数量

2)  Initialize Set dSet[ch1] empty；

3)  ddn[ch1]=0；

4)  for each ch2 in CH

5)    if(dominate(ch1, ch2)) then

6)      add ch2 into set dSet[ch1];

7)    else

8)      ddn[ch1]++;

9)    end if

10)  end for

11)  if ddn[ch1]==0 then//是否为第一等级的个体

12)    rank[ch1]=1;

13)    add ch1 into set CHSet[1];

14)  end if

15) end for

16) i=1；

17) while CHSet[i] is not empty

18)    set tmpSet empty;

19)    for each ch1 in CHSet[i]

20)      for each ch2 in dSet[ch1]

21)        ddn[ch2]--;

22)        if ddn[ch2]==0 then

                  //支配个体ch2的等级最低的个体的等级为i

23)          rank[ch2]=i+1;

24)          add ch2 into tmpSet;

25)        end if

26)      end for

27)    end for

28)    i++;

29)    CHSet[i]=tmpSet; 30) end while

在同一等级内，不同个体的优劣使用拥挤距离来衡量，拥挤距离值越大，该个体越优。为了保证遗传后代的多样性，避免陷入局部搜索，拥挤距离的计算基于个体属性值的分布状况：若个体的属性值分布密集，则该个体的拥挤距离较低；反之，若个体的属性值分布稀疏，则该个体的拥挤距离较高，提供保留该个体更多的几率。拥挤距离计算crowding-distance (CHSet[i])的伪代码如下所示：

1)   LEN=getLength(CHSet[i]);

                        //计算集合CHSet[i]包含的个体数量

2)  for j=1 to LEN

3)    distance[CHSet[i][j]]=0;

4)  end for

5)  for each objective obj

6)    CHSet[i]=sort(CHSet[i], obj);

    //根据优化目标obj的值，对CHSet[i]中的个体进行排序

7)     distance[CHSet[i][1]]=distance[CHSet[i][LEN]]=MAX_LAVUE;

8)     for j=2 to (LEN-1)

9)                distance[CHSet[i][j]]+=(obj[CHSet[i][j+1]]-

                obj[CHSet[i][j-1]])/(max(obj)-min(obj));

                //max(obj)、min(obj)分别表示所有个体的obj属性

                //值的最大值和最小值

10)    end for

11)  end for

3 性能评估

本章主要评估面向物理节点稳定性的多目标优化遗传算法MOGANS的性能。首先将MOGANS和其他算法在得到的虚拟机放置方案稳定时间、迁移次数和激活物理节点数量等方面的表现进行对比；接着，对MOGANS的运行时间开销进行分析。

实验均在Dell optiplex上进行，Dell optiplex配置有第四代Intel Core i5 CPU、8 GB内存和1 TB硬盘。根据实验经验，遗传算法的交叉概率q_c设为0.75，变异概率q_m设为0.05。

3.1 MOGANS和其他算法的比较

对比算法包括面向多虚拟机分布稳定性的遗传算法(Genetic Algorithm for Stability, GA-S)、面向多虚拟机重分布开销的遗传算法(Genetic Algorithm for Numbers of migration, GA-N)、面向节能和多虚拟机重分布开销的遗传算法(Genetic Algorithm for greeN computing and Numbers of migration, GA-NN)。其中GA-NN是基于文献[3]提出的算法思想而实现的，以使用的物理节点数量(即激活物理节点数量)和新旧状态转换所需的迁移开销为优化目标。这些算法均用Java实现。

实验仿真了32个物理节点和86个虚拟机，各应用虚拟机的动态资源需求信息均随机生成，假定各应用的资源需求信息已知，包括各应用在未来的资源需求预测信息。在虚拟机的初始分布状态中，设定约6%的物理节点出现资源过热的状态。目前，虚拟机的资源需求只考虑了二维资源——处理器和内存。各遗传算法中每代的规模大小均设置为48(popSIZE=48)，种群总代数设为32(MAX_GEN=32)。

在相同的初始条件(相同的虚拟机分布初始状态和相同的各应用虚拟机的负载变化)下，运行上述四种算法，分别得到各自的虚拟机的新分布状态，这些新分布状态的稳定时间、迁移次数和空闲物理节点数量如表 2所示。

从表 2中可以发现，MOGANS在虚拟机分布的稳定性和新旧状态所需的虚拟机迁移开销之间作了较好的平衡，保证新的多虚拟机分布状态不仅具有较长的稳定时间，而且从虚拟机的当前分布状态变换到新的虚拟机分布状态需要的虚拟机迁移次数也相对较少。虽然GA-N只需经过最少次数的虚拟机迁移就可以变换到新虚拟机分布状态，但该新虚拟机分布状态只能保持较短时间的稳定性，一旦虚拟机分布变得不稳定，将会激发新的动态资源配置请求而造成新一轮的虚拟机迁移。GA-NN由于考虑了绿色计算，得到的新虚拟机分布状态使用了最少的激活物理节点，剩下的空闲物理节点个数最多，是MOGANS的空闲物理节点数目的8倍左右；但是，GA-NN得到新虚拟机分布方式的稳定时间只有MOGANS的0.096倍，即MOGANS得到新虚拟机分布方式的稳定时间是GA-NN的10.42倍。这说明，GA-NN得到的新虚拟机分布状态尽管更节能，但这种节能状态并不能长久保持，一旦分布状态变得不稳定，将会额外增加新的动态资源配置开销，节能效果也会大打折扣。

3.2 MOGANS的运行时间开销分析

MOGANS中影响算法运行时间的因素主要有两个：种群大小和种群总代数。不断变换种群大小和种群总代数的值，分别测量算法的运行时间，结果如图 4所示。

图 4中，当种群大小从40增加到130(上升幅度为225%)、总代数从100增加到400(上升幅度为300%)时，算法的执行时间从1.46 s增加到7.67 s(上升幅度为425%)。当种群大小从750增加到800(上升幅度为6.67%)、总代数从2600增加到3000(上升幅度为15.38%)时，算法的执行时间从1015 s增加到1566 s(上升幅度为54.29%)。可以看出，当种群大小和总代数上升到一定数量时，算法运行时间的上升幅度是种群大小增幅的若干倍，算法运行时间近似于呈几何级数增长。就目前的运算规模，MOGANS的执行时间开销还在可承受的范围之内，不影响整个云平台动态资源配置进程。当算法的运算规模继续增加时，可考虑并行化遗传算法的运行过程，不同的交叉操作或变异操作具有较好的独立性，比较适合并行化，可以充分利用现有多核计算机的性能，降低算法的时间开销。

4 结语

本文针对云计算的应用负载动态变化的特征，提出了考虑虚拟机分布稳定性的动态资源调度方法，以多虚拟机分布状态的稳定时间和新旧状态转换所需的迁移开销为优化目标，采用遗传算法找到多虚拟机分布的近似最优解。仿真实验结果表明，MOGANS得到的虚拟机分布方式的稳定时间是GA-NN的10.42倍；同时，MOGANS也较好权衡了多虚拟机分布的稳定性和新旧状态转换所需的虚拟机迁移开销之间的关系。然而，多虚拟机分布的稳定性和绿色计算是两个相互矛盾的因素，较好的多虚拟机的稳定分布往往以增加能耗为代价。因此，多虚拟机的稳定分布和绿色计算之间关系的权衡将是下一步的研究工作。