基于改进模拟退火算法的虚拟机调度优化方法

宋杨

（徐州生物工程职业技术学院 江苏省徐州市 221006）

近年来，在计划经济时期的制造企业生产过程中，仍然是采用人为管控的方式进行生产调度的安排，但是人为的调度难免会受到个人主观情绪的影响，也无形中加剧了调度的偏差，影响其可靠性，再加上缺乏理论依据，往往会造成调度的时效性不够理想，针对这一问题，虚拟机调度应运而生。借助云计算这一先进的计算理念展开，云计算调度算法会为虚拟机调度分配的多目标优化。提供更多解决的思路，更能够打破传统人工手动调度存在的弊端。其中，基于云计算的负载均衡，更能够实现资源开销的合理分配，避免过多请求集中在一些硬件节点上所导致的网络拥堵或性能下降[1]。

1 模拟退火算法相关概述

1.1 算法来源

模拟退火算法是由N.Metropolis 学者在1953年所提出的。直到1983年一些学者将模拟退火的核心思想加以优化和改良，并将其于较为复杂组合优化问题里加以利用，收到了很好的效果。至此其得到了越来越多学者关注，在应用上开始逐渐丰富起来，并引起其他国家关注，也开始扩展到更多的行业领域应用中。

1.2 Metropolis接受准则

该准则核心思想正是模拟退火算法，其以固体物质于退火过程里表现出的特点为依据。物理层面固体退火当中，会大致分为三个物理过程。首先是物质升温，当物质吸收了越来越多的热能之后，其内部粒子能量随之攀升，粒子运动加速，当热能蓄积到极限后，这些粒子运动摆脱了原本彼此间达成的平衡限制，固体便会改变形态，有固体进入液体形态[2]。其次，等温过程。物质不再吸热而是不断放热，当温度和环境温度持平时，物质和环境不发生热交换，物质温度稳定在一定范围之内。内部粒子自由会有所降低。当降低到足够稳定的状态不再发生改变时，便处在了平衡状态。第三是冷却过程。当固体温度持续降低最后到一定程度后，地球内部粒子数量会不断降低，也可能会逐渐影响其全部运动时的效果，而一直到所有其他粒子全部运动趋于稳定时，而此时外部环境能量也处在最低状态，不能持续给予地球内部粒子以热能，这会导致所有粒子达到了平衡状态。Metropolis 接受准则的利用，目的是让模拟退火算法终止时所得解成为最优解，这样将模拟退火算法局部最优的可能性得到规避[3]。

1.3 算法操作过程

关于模拟退火处理算法的基本操作步骤主要包括以下几个方面：第一点是数据初始化。第一点是初始化。设置初始解的温度值解为的是t0，初始温度解为的是温度s，每个初始温度t 的迭代替换次数为温度l，初始解为温度的一点设定对于一个算法从随机模式搜索中的过程中开始转换到成为算法局部模式搜索中的过程随机会可以起到明显的提控制度的作用，其中迭加取代替换次数l 的一点设定更是对随机会保证算法局部搜索过程解析度质量的不断提升速度有着一个显著效果，第二点设定是对算法进行搜索步骤。第三点一直到第五点的迭加替代次数操作。初始温度的设定对于算法从随机搜索过程中转换为局部搜索过程会起到明显控制作用,其中迭代次数L 的设定更是对会算法搜索解质量的提升有着显著效果,第二点是对进行步骤第三点到第五点的迭代操作。第三点主要是通过利用算法中的运算可以产生一个新解,第四点主要是通过计算给定目标两个函数的差值,当给定目标两个函数值的差值最大小于0，则计算接受这个新解,否则要以具体的一个概率函数来计算接受这个新解。第五点是接受算法终止的条件并且满足终止条件时需要输出当时的解，从而结束算法[4]。第六点是对当前温度进行衰减系数的衰减计算，并且重复第二点的步骤。具体流程图如图1 所示。

图1：模拟退火算法流程图

图2：云计算中虚拟机调度框架

2 虚拟机调度问题分析

2.1 问题介绍

随着两次工业革命的发展，其进步更是影响甚至决定着国家的持续性经济发展实力和国际话语权，而制造业当中生产调度系统使用频率最高，故而后者质量直接决定了制造业的发展水平，特别是目前在国际国内制造业逐渐与互联网计算机云计算等一些先进的技术相结合下，更是发生着质的转变。生产调度技术因为属于核心技术范畴，故而其受到影响尤为剧烈。云计算驱动下制造业水平有所突破，但信息化技术深入发展无形中也加剧了生产调度问题的复杂度，特别是虚拟机调度作为云计算，云数据环境下成熟发展的产物，更是加剧了其调度的难题和复杂力，目前这种虚拟机调度方法往往超出了个人决策能力范围，若是单纯依靠个人经验和能力进行调度，往往无法达到预期效果。除此之外，因为经济发展速度加快，世界一体化进程加深，人们需要更加复杂的功能产品，这种产品也会越来越左右着人们的生活习惯和生活方式，这要求制造业必须提升该类产品生产能力，意味着其承受着巨大的生产压力，需要其在产量、质量上多做功课解决二者间矛盾，还需要提高生产设备利用水平，这说明之前的调度方式已经不能满足制造企业的发展现状，其中便需要虚拟机调度加以优化，更好的应用云计算模式下来提高调度效率，增强企业的生存发展能力[4]。

2.2 问题类型及特点

目前基于虚拟机调度的问题类型有以下几点，第一点是单机调度，是指在同一台设备上完成所有生产加工任务。需要进行排队优化，第二点是多级并行调度，指的是多个功能相同设备上同时进行多种产品的加工，不过该种调度具有较深的复杂性，需要进行深度优化方可发挥优良作用。第三点是多累积调度，是指产品需要在不同功能的设备上有次序地进行加工生产，多类机经常会出现流水作业调度和柔性流水作业调度这个问题。目前车间的虚拟机调度中出现的问题，也包括了以下几个特点，首先是普遍性，指的是制造业采用虚拟调度机已经是普遍现象。其次是复杂性，这是因为调度的环境载体存在诸多影响因素，在不同的背景下，调度优化目标也各不相同，而伴随着调度规模加大，导致调度问题求解有关计算也变得复杂起来。再次，动态随机性，这是由车间生产环境决定的，其中存在着很多动态变化因素，而这些因素都会无形中加剧虚拟机调度动态灵活的。效果第四点是多样性，在生产调度中所受到的约束条件过多，在不同的需求下，问题目标也各不相同，而基于生产条件完成的时间调度目标，基于生产成本优化等交通目标，也无形中造成了生产车间较多问题的多样性[5]。

3 基于改进模拟退火算法的虚拟机调度优化实验

3.1 系统架构

本文基于改进模拟退火算法的虚拟机，调动优化提出了如图2所示框架，首先，云监控平台系统可以对每个用户所有任务资源进行系统调度优化分配，形成两个一组同时带有一个明确任务调度信息的监控虚拟机任务列表，随后根据任务优化调度目标，按照具体的任务调度分配方法，将虚拟机直接部署到具体的监控物理机上可以执行虚拟机连续运行。在过程中，监控管理单元可能会根据实际的任务状况自动作出明确的任务重置或者迁移等一系列管理操作，确保每个用户的所有任务资源能够正常连续运行，通过上述数据分析可以得知，目前国内有许多大型虚拟机业务调度优化算法更加多的侧重于对于执行时间和总成本资源消耗以及能耗等多个方面的综合优化上，但是对于数据资源综合利用率以及执行时间成本以及吞吐量和一些其他特定因素影响方面的优化研究相对较少，也就是缺乏对企业云服务供应商另一方面的优化考虑。因此，本文更是以系统资源综合利用率系统执行过程成本和系统负载均衡这三者关系作为主要的成本优化规划目标及战略目的，是为了进一步提高系统资源综合利用率并有效减少系统执行过程成本，真正有效实现系统物理机与系统物理机之间的成本负载均衡。

3.2 改进的模拟退火调度算法

为有效率的解决以往人工退火调度以及传统人工调度目标算法全局优化，目标单一等级的缺点，基于云和云计算的调度环境下，调度目标资源更多时就会需要采用各种类似启发式的调度算法，同时我们能够快速达到多种调度目标的全局优化，而模拟退火调度算法就是作为一种根据目标给定调度函数，利用一定概率的计算方式被用来快速获取目标全局最优化求解的一种启发式调度算法，能够在初期时广泛的进行搜索。空间最优通过大量数据搜索空间范围并同时接受一个交叉函数姐输出来可以避免整个算法局部陷入空间局部最优，而它的缺点则是侧重于对空间整体数据解析和空间值的认知能力不足，寻求计算效率和空间锁定要求解空间性能有限。本文提出了HEFT 算法的思想。根据物理机计算性能，可以求出对应解的过程。使得最终所获得的结局有更好的计算性能。

3.3 实验对比

为了更好地评价本文所提出的这种优化算法，将进行云环境的调度模拟。云计算环境技术中的节点负载均衡概念是在泛指各个业务节点相互利用均衡期间不会出现存在的非负载或节点过载的各种情况不会发生。通过该管理算法进行设置并为相关网络限定负载参数，能够有效率地防止上述负载问题，有着更加合理的网络负载均衡管理性能。