kiayun手机版登录入口 用遗传算法进行容量管理 让虚拟机放置策略更优

by 王国兵

于互联网技术迅猛发展之际，云计算已然化作各行各业的“水电煤”，变为“互联网 +”的基础设施，并且数据中心乃是云服务背后的刚性保障。不管是传统的数据中心，亦或是云形态的数据中心，虚拟化技术都是用以提升其资源利用率、降低管理成本的重要方式。

据统计，早在二零一六年的时候，A.W.S的服务器规模已然达到五十五万台，然而虚拟机数量却超过了八百万。在虚拟机数量迅猛增加的状况下，虚拟机的放置方案自然而然地变成了决定数据中心资源利用率以及其他需求的关键所在。

要是打算提升数据中心的资源利用率，那就得采用恰当的放置方案，运用最少的物理机方可达成资源利用率的最优化，还能起到节能的成效。另外，为了维系系统的高可用性，同样得挑选合适的放置方案，让不同服务器之间的资源使用率尽可能趋于均衡。

众多研究把虚拟机放置形容成“多维装箱”这样的问题，被装入的物品便是虚拟机，其所运用的资源是物品大小，箱子是物理机，箱子容量那是物理机配置阈值，资源包含CPU、内存、磁盘、网络带宽等，资源的种类数量就是装箱问题的跨度。

设有物理机数量为M，又有虚拟机数量为Nkiayun手机版登录，那么理论上最多存在M的N次方种部署方案，此为NP - hard问题。在解决NP - hard问题的诸多方法里，像遗传算法、模拟退火算法这类启发式算法都有着出色的表现。在此处我们要介绍在解决该问题时经典遗传算法的思路以及具体的落地方案。

遗传算法是一种用于全局优化搜索的算法，它具备简单通用的特性，拥有很强的鲁棒性，适合进行并行处理，具有高效以及实用等突出的特点，在各个不同的领域都获得了广泛的应用。

遗传算法将群体中的所有个体当作对象，运用随机化技术对被编码的参数空间展开高效搜索。其中，选择、交叉以及变异构成遗传算法的遗传操作，编码、初始群体设定、适应度函数设计、遗传操作设计、控制参数设定这五个要素组成遗传算法的核心内容。那么，针对”虚拟机放置在物理机上”这个问题，该如何理解遗传算法的五个要素呢？

我们借助以下概念的释义，把现实世界里的虚拟机提出，把物理机提出，把虚拟机放置方案提出，对评价当前方案的指标等问题考量之后，将这些内容映射到“遗传算法”过程里的专有名词上，然后凭借遗传算法来进行求解：

染色体，当中的一条，它代表着一种“方案”，此方案是关于“当前虚拟机序列的放置”，它还被称作种群里的单独个体， 。

评估染色体的方式是，不同的放置方案存在不同的适应值，适应值决定了当前方案的优良与否；通常运用物理机使用数量来评估染色体，同时要考虑高可用限制、虚拟机数量限制等因素，这种面向多目标的问题能够使用“快速非支配排序”结合“局部拥挤距离”算法来进行求解。

l 遗传组合行为有两种，一种是交叉行为，另一种是变异行为，交叉或变异行为，乃是致使染色体之上所涉及的一部分虚拟机放置序列发生改变的行为 。

其种群，系由多个染色体所构成，此所意味者，乃代表着于当前进化次数情形之下的染色体集合，而该染色体集合，实则当属多种放置方案的集合 ；。

把现实当中的实体以及问题，映射到遗传算法所特有的专有名词之后，我们会演示，怎样把遗传算法的五个要素，映射到现实里的问题当中：

编码

就像上面所展示的那样，把每一个“全量虚拟机序列于物理机序列之上的放置方案”当作一条染色体，这属于典型的开展“组编码”的形式，能够瞧见，因为运用了不一样的物理机，所以两条染色体最终运用的物理机数量也是不一样的。

初始群体设定

着眼于启发式这一特性的初始化群体办法，是能够有助于削减算法优化进程的复杂程度的kiayun手机版登录打开即玩v1011.速装上线体验.中国，然而于此同时，还得确保群体里染色体具备多样性质，此种作为是为了促使搜索解范畴愈发宏大，进而去求取趋近于全局层面最优解，而非仅仅是局部最优解，。

在启发式算法里头，首个虚拟机被放置到首家物理机那儿，接着依据虚拟机序列所拥有的顺序，逐个去放置别的虚拟机，一直到首家物理机的资源变得不够用。对于随便的某一台虚拟机而言，它要先去逐个查看当下已然有着的物理机序列排列，一直到被使用的那些物理机没办法去满足该资源所需要求。在这个时候全新开辟一台物理机用于其使用，这是去生成一条染色体的方式方法，并且为了能够确保种群的繁杂多样特点，在每一次生产全新染色体之际，我们得要随机去搅乱了虚拟机序列的排列顺序，这样一来此种方法明显是简易可行而且成效较佳的。

适应度函数的设计

适应度是针对当前种群里个体的评价办法，在多目标优化问题当中，通常能够采取二代多目标优化算法NSGA2里的快速非支配排序来对个体等级予以划分，接着借助局部密度算法开展密度估计，进而确定每一个个体的优先级。

这个过程听起来很抽象，它的具体操作是怎样进行的呢？假若 Costf1以及Cost f2各自代表个体于“使用物理机数量”还有“整体高可用性”方面 的度量 值，而且取值越大表明该方案于该维度 越出色开·云app体育登录入口，那么对于 个体集合{1,2,3,4}来讲，每一个元素都起码存在另外一个于各个方面比自身出色的个体，就像对于个体4而言，个体5在“使用物理机数量”以及“整体高可用性”方面都比个体4优越，这时我们讲“个体5支配个体4”；然而对于集合{5,6,7}来说，由于不存在支配它们的个体，所以它们被称作“非支配解”；这种“非支配解”的适应度理论上应是最高 的。

遗传操作设计

遗传算法以内，核心操作涵盖“选择”，以及“基因交叉”，还有“基因变异”，此三者决定种群进化方向，是促使算法朝着我们目标持续优化的根基。

“选择”（Selection）：用到2 - 约束竞赛选择法，在此方法里，从当前种群当中随机挑出两个个体，接着把适应值最大的那个个体当作父个体，持续开展该步骤，一直到个体数量达成预定的种群规模，从而为作为下一代种群被选出得父个体。两个个体的比较方式借助NSGA2所引入的拥挤比较算子 。

Crossover：在挑选两个选择过程里，把被选定的父个体当作交叉对象A、B来挑选，随机选A里的物理机a，使得该物理机a进到B中，接着将B个体里含a的虚拟机序列当初所在的原物理机从B中去除，另外记录被删掉的虚拟机再放置到B上。此操作达成了某台物理机的虚拟机序列重新分配，并且鉴于物理机的挑选是随机的，保证了交叉的多样性；。

“变异”（Mutation），其操作相对而言较为简单，并且有着易于理解的解释性，从父个体里随机选取一个染色体A，接着从个体A上随机挑选一个物理机a，把它删除，随后将原来处于a上的虚拟机序列重新插入到A之中，如此这般的目的在于减少物理机的使用，然而鉴于物理机a是随机选出来的，它没办法确保每次变异的方向都是正确的，所以我们能够降低“变异”操作发生的概率，而且这恰恰凸显了正确的“选择”的重要意义。

控制参数设定

所谓参数设定，主要是针对遗传操作里各操作的发生概率而言，比如说，我们能够设定“交叉”操作的发生概率是0.6，“变异”操作的发生概率为0.05 ，而有效的参数设定能够控制种群更快且更好地给出近似最优解 。

经由达成上述五个要素，我们就能够依照遗传算法的既定步骤，开展虚拟机放置问题的求解了 。

大致来讲，用以跳出算法迭代的条件存在两个方面，一方面是当下最优染色体的适应值已然满足目标所设定的值，另一方面是达成了指定的迭代次数，借由凭借人为经验去择取合理的遗传操作策略，我们能够迅速获取我们的目标方案。