APP下载

一种改进模拟退火算法在弱化虚拟机放置中的应用

2018-11-03李尉陈雨高小龙

现代计算机 2018年28期
关键词:模拟退火全局服务器

李尉,陈雨,高小龙

(四川大学电子信息学院,成都610065)

0 引言

云计算概念提出至今已有10年的时间了,在此期间,此项技术得到的巨大的进步与发展,成为计算机技术又一次的巨变。云计算是分布式计算、并行计算、效用计算、网络存储、虚拟化、负载均衡、热备份冗余等传统计算机和网络技术发展融合的产物。其中云计算最为基础性的服务为基础设施即服务(IaaS),其原理是通过将物理服务器进行分块,按照客户需求的大小把物理服务器以虚拟机为最小单位的形式提供给客户。在实际应用中,提供云计算服务的公司根据预估的情况来研究一种高利用率的虚拟机放置方案。这样有利于物理服务器的资源利用率的最大化,降低能耗,提高经济效应。虚拟机放置问题一般被归类为NP难问题中的装箱问题。对于这类问题,当前提出的解决方案主要集中在三个方向:启发算式算法、遗传算法和模拟退火算法。例如,在启发算式BFD算法的基础上进行改进,使得在虚拟机初始化放置是得到有效的优化。通过改进的FFD算法,来寻找虚拟机放置问题的最优解。在传统的遗传算法基础上,针对传统分组问题的适应性差的缺点提出重新构造分组的方法,来提高虚拟机初始化放置的资源利用率。上述三个方向中,启发算式算法的优点是简单、快速、易于实现。但缺点也比较明显,全局化搜索的几率低,容易陷入局部的最优解。遗传算法作为装箱问题的现代优化方法之一,在解决高维度、高复杂及非线性问题的优化中具有全局最优、效率高以及易于并行计算等优点,有很强的问题解决能力,但是有着收敛速度慢和易于陷入局部最优解的缺点。而本文主要研究的方向是弱化的虚拟机的初始化放置问题,一般将其建模为带限定条件的一维离线装箱问题,属于低纬度、高精度的问题,所以上述两种方法不太适用。由于一般组合优化问题与物质的退火过程具有很大的相似性,因此,此种智能优化算法通常被用来解决组合优化的问题。又因为该算法的局部搜索能力较强,而且具有运行时间段的有点。所以本文主要研究模拟退火算法,并针对传统模拟退火算法前期温度下降过快、初始解较差导致全局搜索能力不足和迂回搜索等缺点进行改进。

1 模拟退火算法

1.1 模拟退火算法的实现

模拟退火算法的核心思想与热力学的原理十分相似。热力学上,温度非常高的情况下液体中大量的原子的运动方式是相对的,随着温度渐渐的下降,原子的可动性也随之降低。慢慢的形成一个纯净的晶体,晶体的形态是能量最低的状态,只要是温度缓慢下降的物体都可以慢慢达到这种能量最低的状态。如果降温过程迅速,这种情况下物体不会达到这种状态,能够达到的状态只能是一种能量较高的多晶体或非晶体的状态。所以,缓缓地降温是这个过程的核心,以争取足够的时间,在大量原子的运动性丧失前完成重新的排布,这是确保能量达到低能量状态的必须条件。模拟退火算法(Simulated Annealing,SA)的思想最早由 Metropo⁃lis等人于1953年提出;Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题。模拟退火算法是一种基于Monte Carlo迭代求解策略的随机寻优算法。算法的理论依据是物体的退火过程和组合优化问题的求解相似性,通过模拟高温退火的过程来搜索近似最优解。算法的实现基本步骤为:

(1)选定初始温度,Markov衰减函数,终止温度,初始解,提供解邻域的构造函数。

(2)在每个温度下,由前一个解出发,通过加入随机扰动机制,产生原有解的解邻域。

(3)新解是否被接受是由接受函数来确定,接受函数的主要参数温度,由接受的新解形成一定长度的Markov链。

(4)根据衰减函数,随着温度的降低,接受新解的概率也降低,当温度降低到最低温度时候,解状态也稳定于优化问题的最优状态。

图1 模拟退火算法流程图

1.2 模拟退火算法的基本原理

模拟退火算法与金属退火过程相似。Metropolis准则表明,粒子在温度T时趋于平衡的概率exp(-Δ E/T),其中E为温度T时的内能,ΔE为其改变量。固体退火和组合优化问题很相似,固体的内在能量就相当于组合优化问题中的接受函数的函数值,温度参数T也就相当于组合优化问题的控制参数,这样组合优化问题的模拟退火算法就形成了。模拟退火算法就是从最初的解X0和相当于温度的控制参数初始值T0开始,然后通过反复的迭代,重复“产生新解→计算目标函数差→接受或舍弃→降低控制参数T”的过程,最后,在结束的时候所得到的解就是该组合优化问题的近似最优解,上述过程就是一种基于Monte Carlo迭代求解的随机搜索过程

1.3 模拟退火算法的缺点

传统模拟退火算法虽然能够依概率收敛于全局最优解,但是对于目标函数比较复杂时,为了获得高精度的解,温度参数一般需要设置为一个较大的初始值,并且在每个温度值T下需要重复执行Metropolis算法,所以存在着迭代计算速度慢,计算花费的时间比较长。另外,由于在最优解的搜索过程中,依据Metropolis算法,对于劣质解在一定程度内以某个概率接受,这个概率值由温度值t控制。所以存在丢弃当前遇到的最优解的可能;以及对某个已经访问过的解进行多次重复的搜索,增加运行时间。这些局限使得模拟退火算法无法在实际生产生活中广泛运用。

2 改进的模拟退火算法

2.1 降温函数的改进

(1)根据模拟退火的收敛性理论,温度的高低决定了模拟退火算法进行的是全局搜索还是局部搜索,在温度下降过快的情况下,模拟退火算法将很快从全局搜索转变为局部搜索,很大可能陷入局部最优解的状态,想要跳出局部最优解只能增加内部循环的次数,这样会导致算法运行时间过长;如果温度下降过慢,虽然可以通过减少内部循环的次数的方法来控制时间,但是外部循环次数也影响了算法运行的时间。因此本文希望通过改进温度衰减函数来提高模拟退火算法的性能。传统的温度衰减函数为单一的函数,本文采用分段函数来替代,前半段温度较高的时候,采用衰减较快的函数来快速降低温度。在退火的后期,采用下降平缓的函数来使得算法更好地进行精细搜索。

根据模拟退火的理论,只有在温度衰减函数收敛的变化态势比对数函数1log(k)更慢时,模拟退火算法才能保证依概率1收敛于全局最优解。但是采用对数函数的模拟退火算法的运行时间过长,所以前m次迭代的温度衰减函数决定采用TsIn(k),希望能迅速找到最优解所在的邻域,m次以后的迭代的温度衰减函数使用Ts*0.99k,使得能够在迭代后期精确的找到全局最优解[1]。温度衰减函数:

其中m是预先设定的值,Ts为起始温度。通过比较温度下降函数,找到log函数的拐点所对应的变化次数。对log函数求到可得m=15。针对存在丢弃当前遇到的最优解的可能,本文对传统模拟退火算法增加了记忆功能。

(2)由于接受准则的原理存在接受不是最优解的可能,而导致放弃最优解,所以本文通过增加存储环节,将当前位置的最好状态存储下来[2]来保证最终解为最好的状态。

2.2 改进算法在虚拟机放置问题中的应用

问题建模:首先,因为在确定装箱策略的情况下,所求的解的效果只与待放置虚拟机的放置顺序有关,所以将虚拟机的顺序作为模拟退后算法在虚拟机放置问题中的解,解决的存储方式为数组。这样还能方便加入扰动机制,容易实现新旧解的迭代,即解邻域的构造[3]。新解构造方法采取的方法是引入一个随机数产生函数,用这个函数产生两个合理范围内的随机数,然后交换以这两个随机数为下标的虚拟机得到新的解。本文采用的装箱策略为最佳适应算法(Best Fit):处理方法为将所有非空箱子的按剩余空间的大小做升序排列,找到按升序排列的第一个能够放下当前物品的箱子并将该物品放入,否则开启新的箱子。考虑到改进的模拟退火算法加快了前期的温度下降的趋势,所以算法的全局搜索能力下降,初始解设置为某个局部最优解有利于高效利用算法前期的全局搜索。因此算法的初始解设置为采用最佳适应算法装箱后的每个箱子由底部到顶部的各个虚拟机的顺序。因为在虚拟机的放置问题上的最优解为所用到的服务器的个数最少的情况下每个服务器的利用率最大,所以评价函数为:

其中n为所使用的箱子个数,O(i)为每个箱子的利用率,评价函数的结果为每个箱子的平均利用率。解的接受概率:

其中,E2为新解,E1为旧解。在新解的效果好于旧解的情况下,新解的接受概率依据Metropolis算法为1,在新解的效果差于旧解的情况下,用随机数产生函数得到一个随机概率Rand(x),当随机概率小于exp(-(E2-E1)/T)时候接受新解,否则舍弃新解,保留旧解。

3 实验示例及结果

与MATLAB平台上的仿真不同的是,本文采用C++语言编写代码,实现了性能比较完善的专门放置弱化的虚拟机的程序。普通虚拟机放置主要考虑的方面为内存和CPU的个数。在弱化虚拟机的放置问题上将两方面的因素简化为优先考虑某一方面,例如只考虑保证放置的虚拟机内存总空间不超过服务器内存的情况下,每台服务器CPU的使用率。

3.1 测试用例

本文将服务器规格设置为CPU个数为56,内存大小为128GB。选取8种型号的虚拟机构造两组数据第一组和第二组。每组数据选取8种型号的虚拟机若干。数据构成如表1:

3.2 测试结果

表1 两组数据的构成

在同样的测试数据下,每组数据在每种算法下测试3次,得到的传统模拟退火算法和改进的模拟退火算法的平均结果比较如表2。

表2 算法改进前后的结果比较

从实验结果可以看到,改进的模拟退火算法在数据规模较小的时候,放置虚拟机所需的服务器个数于改进前的一样,但是改进后的模拟退火算法的运行速度明显快于传统的模拟退火算法的运行速度。

4 结语

本文通过改进模拟退火算法实现了弱化虚拟机放置问题的最优解搜寻。根据模拟退火算法的特点,优化了单一温度衰减函数在算法前期温度衰减过慢的缺点,采用组合温度衰减函数既加快算法前期的全局最优解邻域的搜索速度,又保证了后期局部最优解的搜索质量。在解决弱化虚拟机放置问题上将模拟退火算法与启发算式(最佳适应算法)相结合,使得模拟退火算法在弱化虚拟机放置问题上使用更加简单。实验结果表明,改进算法在数据规模较小的情况下,既保证了解的质量也明显加快了模拟退火算法的运行速度。

展开全文▼

猜你喜欢

模拟退火全局服务器
Cahn-Hilliard-Brinkman系统的全局吸引子
量子Navier-Stokes方程弱解的全局存在性
通信控制服务器(CCS)维护终端的设计与实现
模拟退火遗传算法在机械臂路径规划中的应用
落子山东,意在全局
得形忘意的服务器标准
计算机网络安全服务器入侵与防御
基于模糊自适应模拟退火遗传算法的配电网故障定位
SOA结合模拟退火算法优化电容器配置研究
基于遗传-模拟退火算法的城市轨道交通快慢车停站方案