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

传统的调度算法有以下三种常见的分类：一、Sufferage贪心算法。根据网格中的节点优先权重中将次小任务完成时间与最小任务完成时间的差定义为任务执行损失,称为 Sufferage值。Sufferage值用于表示云计算实际调度过程中的优先顺序。二、Min-Min算法。Min-Min算法的核心思想是“小问题优先制”，将时间作为调度过程中的唯一变量，即以最快的时间将任务由小到大处理完，其中，小问题表示该项任务在任意一台可用机器上的最早完成时间。三、Max-Min算法。Max-Min算法与Min-Min算法相反，即该算法首先处理大任务，任务到资源的映射是将具有最早完成时间最大的计算资源分配给最大的任务。

上述算法中，总的来说，传统的资源调度算法收敛速度慢、进化速率不高，具有明显的缺点。具体来说，最容易造成负载Min-Min算法负载不均衡的原因，是它算法的适应度低，导致部分资源节点负载集中。而Max-Min算法的优势仅存在于可执行任务资源固定时。Sufferage算法仅略优于前两种算法，但是也不一定能满足用户任务的服务质量要求等其他一些目标。

三、基于智能算法的资源调度

第2章中的传统的云计算资源调度算法存在诸如适用范围小、仅对算法效率做要求等问题，现阶段已经不能满足现有的云计算要求，许多科研工作者将智能算法与资源调度结合并进行改进，在初始化种群、算法搜索能力以及收敛速度上进行改进，对基于智能算法的资源调度进行大量研究改进，列举如下。

（一）传统的智能算法

智能算法包括遗传算法、进化策略和进化规划等在内的几个组成部分，本文涉及的智能算法特指智能算法中的遗传算法。由于可伸缩性、异构性和复杂性得到了重视，各种基于自然的计算技术被用来处理更高的复杂性和提高熟练程度。仿生计算是一种快速增长的通信和网络新模式。许多研究人员一直致力于使用生物系统的作用，并讨论了各种智能算法。智能算法是参考物种起源的理论，在计算机算法领域模拟生物自然进化操作对实际问题求解的算法。在函数优化、组合优化、车辆调度问题中均有应用。传统的智能算法包括种群初始化、个体评价、选择、交叉、变异几个操作流程。智能算法的主要具有以下几个方面的优点：一、易于进行并行化计算。遗传算法根据种群作为操作单位，因此同时对一个种群内的多个个体（区域）进行搜索；二、编码方式可选择性强。由于引入了生物学中基因的概念，可采用多种个体编码方式，如浮点型、结构式、位串式编码等；三、和传统算法比较，子代传递采用概率性传递方式，易于寻找全局最优解；四、不要求被求解问题数学公式化。因此不要求被求解问题一定要可导或者可微分。传统智能算法正是由于以上几个优势在云计算调度中得到广泛使用。

但传统的智能算法仍旧有较为明显的缺点：搜索效率低、收敛速度慢及容易早熟现象的问题。传统算法早已经不适应于现代化计算机发展需求，针对这种情况，科研工作者改善传统算法的劣势，提出了改进的智能算法。

（二）横向改进的进化算法

从横向看，进化算法可以与别的算法结合成混合算法从而进行改进。多种算法混合的算法可以互相取长补短，而单一算法常存在较多缺陷，如、模拟退火、蚁群算法、PSO算法、禁忌搜索算法等。

1.模拟退火与进化算法结合

模拟退火算法是用来处理大规模的组合优化问题时被首次引入的，是基于仿生学的迅速发展，模仿物理学科中固体退火思维，模拟退火算法中初始解的依赖性低，在求解的过程中，可以接受一定程度的坏解，因而可以在某种程度上能跳出局部最优解。所以模拟退火算法相比较优势在于模拟退火算法至少得到全局次优解。它改善了传统的遗传算法容易陷入的局部最优解的状况。它是一种启发式方法，用于获得各种离散问题的最优解。该算法的起源是统计机制，它的基本思想是在容器中最昂贵的项目用一个随机项替代，拥有最低的成本。在这种方法中，随机请求被分配到容器中，直到当前容器中的一个参数完全填满为止。它是基于两个约束条件的，即软约束，使得一个解决方案能被更好的解决方案所取代，在硬约束下，资源的容量决不能超过容器的大小。迭代交换直到解决方案达到稳定状态才完成。该方法是一种高度灵活的局部搜索方法，可以成功地应用于实际生活中的大多数问题。模拟退火算法需要较长的时间才能找到全局最优解。通过仔细指定温度的冷却速率证明了模拟退火算法可以收敛到全局最优解。该算法首先生成初始解，并初始化温度参数，这纯粹是一个假设，这是主要的缺点。该算法通常与本地最大值相匹配，不需要的分配被产生和算法也取决于请求可用性和容器容量。这种方法在高温下很有效。但模拟退火也存在弊端：在实际退火过程中，如果要使算法收敛速度快，即使降温的速度加快，则算法很可能得不到全局最优解。                                                                                                                                                

因此，有人提出将遗传算法于模拟退火算法合并，虽然算法的复杂度增加，但融合后的优势明显，具体优势有以下几个方面：一、种群进化方向多样性。遗传算法的搜寻形式是并行的，模拟退火则采取串行优化形式，因此二者结合引导种群演化方向多样化；二、增强全局搜索能力，模仿退火算法的时变性和突变性弥补了遗传进化算法将可能陷入局部最优的情况；三、参数敏感性降低。

2.蚁群算法与进化算法结合

蚁群算法是通过模仿自然界蚂蚁搜寻食物的过程来设计的，蚁群能释放随着时间消失的信息素，并最终使大部分蚂蚁逐渐认同聚集到最短路径，因此，蚁群算法具有正反馈的特点，蚁群算法的缺点是在算法早期蚁群可获得的信息量少，因此早期算法求解速度慢。尽管遗传算法进行全局搜寻的能力强，但在收敛后期常陷入局部最优，不能获得全局最优解。

赵俊普等人提出在云计算资源调度中结合遗传算法和蚁群算法的新算法，先用遗传算法迭代出可能的最优解，并将最优解用于蚁群算法的初始信息素分布，将其带入蚁群算法对蚁群算子双向收敛。最终算法在收敛速度、迭代时长、解集精度上均优于原始算法，并且均有良好的QOS，达到了优势互补的结果。