在现有关于虚拟化资源优化分配的研究中，应用通常为单层或多层逻辑组成结构. 然而，对于由不同组件服务按照多种组合逻辑( 如顺序结构、分支结构、并行结构和循环结构等) 构成的与已有研究不同，本文针对基于 SBS 的云应用的资源优化分配问题，提出了一种以满足端到端平均响应时间为约束，以最小化资源使用成本为目标的虚拟化资源分配优化模型及其遗传算法的实现. 在该模型中，定义了组件服务资源配置的概念，并给出了组件服务候选资源配置的确定方法，从而将资源优化分配问题转换为一个资源配置组合优化问题，进而采用遗传算法求解. 实验验证了本文的资源分配优化模型的有效性，并且表明提出的遗传算法实现收敛速度快，且与线性规划算法相比，在较大问题规模上可以快速获得质量更高的解.
1 基于成本的 SBS
资源分配优化模型本节首先定义组件服务的资源配置，并给出其确定方法，进而将 SBS 资源优化分配建模为一个资源配置的组合优化问题.
1. 1 确定候选资源配置为了确定组件服务的候选资源配置，需要获取任意资源向量与该组件服务平均响应时间之间的映射关系，本文称描述该映射关系的模型为组件服务的资源模型. 另外，还要确定资源使用成本的计算模型，即资源定价模型.
1. 1. 2 资源定价模型实际中，不同的资源类型可以采用多种定价模型，如线性定价模型、指数型定价模型等. 本文假设资源使用成本与资源分配量、资源使用时长呈正比，并对所有资源类型均采用线性定价模
2 基于遗传算法
求解优化模型根据优化模型可知，组件服务的资源配置组合优化是个 NP 难问题，而遗传算法是解决最优化问题的有效方法之一，因此本文采用遗传算法进行求解. 首先，采用一维编码方式对个体进行二进制编码，基因位取值满足式( 5) 和式( 6) ; 然后，采用通用的遗传算子进行种群的繁殖，为了减少无效解，对交叉操作和变异操作进行了一定限制，使其满足优化模型的约束条件. 另外，在适应度函数中引入了罚函数，从而降低在解空间中无对应可行解的个体的适应度，加快收敛速度.随机等距的方式抽取个体，从而更好地保持种群多样性.交叉算子采用单点交叉. 为了使新的个体仍然满足约束条件式( 5) ，将交叉点的取值限制为不同段基因的分割点.变异算子采用位点变异，将变异基因位的值取非. 与交叉算子类似，为满足式( 5) ，如果变异后的值为1，则将该基因位所属基因段中其他基因位的值均置为0，否则，则在变异后，随机从该基因位所属基因段中的其他基因位中选择一个并取非.最后，本文通过设定遗传代数作为终止迭代的条件，相比通过设定精度来终止迭代，可以防止由于种群过大、要求精度较高而引起的搜索时间过长的情况.
3 实验与分析
本节主要验证本文的遗传算法的收敛速度，并将其与线性规划算法在 SBS 资源分配优化模型上解的质量和求解效率两方面进行比较.
3. 1 实验设置
3. 2. 1 遗传算法的收敛速度该组实验考察本文提出的遗传算法的收敛速度，这对于在合理时间内求得最优解具有重要意义. 为了使算法能以较大概率收敛到最优解，本文在适应度函数中引入了罚函数，以物理机个数取值15 为例，与未采用罚函数的适应度函数相比较，结果如图3 所示.根据图4 可知，对于不同的物理机数量，遗传算法得到的最小资源使用成本略高于线性规划算法，而且随着物理机数量的增加，两种算法得到的最小资源使用成本均呈降低趋势，这是由于解空间扩大增加了求得更优解的可能性，同时物理机增多也会有助于减少资源配置之间的冲突，进而产生更多的可行解.2) 求解优化模型消耗的时间. 在求解优化模型时，遗传算法和线性规划算法消耗的时间对比结果如图5 所示.明显要高于未引入罚函数时，这是因为在解空间中没有可行解的个体不会遗传到下一代，因此可在一定程度提高收敛到最优解的概率.
3. 2. 2 与线性规划比较该组实验通过物理机数量在 10 ～50 之间的变化，与常用的求解约束优化问题的线性规划算法在解的质量( 以部署 SBS 的资源使用成本度量) 和求解效率( 以求解优化模型消耗的时间度量) 两方面进行比较.1) 部署 SBS 的资源使用成本. 遗传算法和线性规划算法求得的最小资源使用成本对比如图 4所示.图4 最小资源使用成本对比Fig. 4 Comparison of the lowest resource costs根据图4 可知，对于不同的物理机数量，遗传算法得到的最小资源使用成本略高于线性规划算法，而且随着物理机数量的增加，两种算法得到的最小资源使用成本均呈降低趋势，这是由于解空间扩大增加了求得更优解的可能性，同时物理机增多也会有助于减少资源配置之间的冲突，进而产生更多的可行解.2) 求解优化模型消耗的时间. 在求解优化模型时，遗传算法和线性规划算法消耗的时间对比结果如图5 所示.图5 消耗时间对比Fig. 5 Comparison of solving time根据图5 可知，两种算法的时间消耗均随着物理机数量的增加而呈上升趋势. 当物理机数较小( 小于25) 时，线性规划算法的时间消耗要低于遗传算法; 而当物理机数量较大时，线性规划算法的时间消耗显著增加，此时遗传算法的效率要优于线性规划.
综上实验结果表明: 本文的遗传算法能够在可接受的时间内收敛到最优解，并且适应度函数中的罚函数对于提高算法的收敛速度具有比较明显的效果; 遗传算法求解得到的资源分配方案的资源使用成本比较接近线性规划得到的最优解;与线性规划相比，当组件服务的候选资源配置较多时，本文的遗传算法可以在更短时间内求得最优资源配置组合.4 结 语本文针对基于SBS 的应用在云环境部署时的资源优化分配问题，提出了一种基于资源配置的组合优化思想、以最小化资源使用成本且满足应用SLA 和物理机资源约束的资源分配优化模型，并根据该优化模型的特点给出了改进的遗传算法.
实验验证了本文提出的优化模型的有效性，并且表明其基于遗传算法的实现具有较快的收敛速度，同时可获得接近线性规划最优解的资源配置组合，但在问题规模较大时求解效率明显优于后者.