前言:
此刻兄弟们对“二维装箱启发式算法”可能比较着重,小伙伴们都想要学习一些“二维装箱启发式算法”的相关文章。那么小编同时在网摘上汇集了一些关于“二维装箱启发式算法””的相关文章,希望姐妹们能喜欢,你们快快来学习一下吧!文丨五年宝
编辑丨五年宝
前言
数据中心是云计算的支柱,云服务的全球可用性不断提高,需要大量数据中心的支持,所以为数据中心供电,电力需求的增长不可避免。
根据估计,数据中心每年使用200太瓦时(TWh),占全球电力需求的1%,之后根据美国能源情报署(EIA)2016年5月能源月度报告显示。
在2013年美国数据中心能源消耗总成本为130亿美元,占总用电量的2.4%,详细统计显示,数据中心约26%的能耗用于服务器和存储。
在当前硬件服务器的效率水平下,数据中心能源消耗需求的急剧增加将需要每年额外建造50座大型发电厂,提高数据中心的能源效率对于数据中心的管理和运营至关重要。
虚拟网络及虚拟机
云服务通常通过虚拟化来配置,对虚拟网络和虚拟机(VM)等虚拟资源的有效管理是云数据中心的基本要求。
在空气冷却等众多因素中,虚拟机放置到物理机(PM)对于提高大型数据中心的能源效率起着重要作用。
由于数据中心能源成本的很大一部分是为PM供电,因此通过优化VM放置来最大限度地减少能源消耗是有益的。
最近的报告显示,通过改进数据中心的虚拟机放置,可以实现超过的显著节能 ,这促使研究人员的研究和开发节能虚拟机放置策略,以进一步降低数据中心的能耗。
但尽管数据中心的能源效率有所提高,以现有的虚拟机放置解决方案主要源自简单的启发式策略,比如首次适应递减(FFD)算法和元启发式进化计算(例如遗传算法(GA)。
虽然FFD运行速度非常快,可以提供可行的解决方案,但GA在数据中心的能源效率方面更好地解决了虚拟机放置问题。
遗传算法对计算的要求很高并且运行速度太慢,特别是对于大型数据中心,这限制了其在大规模系统和需要高质量的快速虚拟机放置解决方案的场景中的应用。
因此,虚拟机放置的能源效率在数据中心的管理和运营中受到影响。
节能VM设备以及FFD的研究
节能VM放置问题是一个组合优化问题,可以描述为装箱理论上,也可以通过穷举搜索得出此类问题的最佳解决方案。
但此类优化问题是非确定性多项式时间困难(NP困难),当问题规模很大时,他们需要大量的计算工作才能获得最佳解决方案。
在考虑到小型数据中心放置500个VM到100个PM,组合总数为,假设检查这些组合中的每一个以实现能量优化需要10次浮点运算。
那么,总共有100500将执行浮点运算以进行详尽的搜索,可如果使用世界上最快的超级计算机之一神威太湖之光进行计算,其Linpack性能(Rmax)为93,014.6Tflops。
研究人员们将不得不等待超过times10^年获得全局最优解,所以穷举搜索技术对于解决能量优化问题实际上并不可行,从而激发了各种虚拟机放置的启发式策略。
FFD通常用于启发式VM放置,因为它可以有效地处理一般的装箱问题,比如说虚拟资源管理,而在最近,一种先进的FFD算法被实现用于VM放置。
虽然它并不针对数据中心的能源效率,但当按照能源效率对PM进行排序时,可以很容易地采用它来实现节能的VM放置。
与FFD类似,最佳拟合递减(BFD)是另一种有效处理装箱问题的启发式算法,它已被用于能源优化的虚拟机布局,其实施是基于资源利用率而不是实际的利用率衡量标准。
通过元启发式,GA还被研究用于数据中心虚拟化资源的优化管理,GA在每一步中搜索比FFD和BFD更大的空间。
因此可以提供比FFD或BFD更高质量的解决方案,但代价是执行时间增加。为了提高执行时性能,遗传算法的计算需求已被削减,同时仍保持解决方案的质量。
作为另一种元启发式方法,蚁群优化(ACO)已被研究用于多目标、云工作流调度,通过对五种类型的现实世界工作流程的分析。
ACO已被证明优于粒子群优化(PSO)和非支配排序遗传算法-II(NSGA-II),而且ACO还通过改进的公式和新的启发式方法进行了研究,以实现节能VM放置。
由于ACO和GA都属于元启发式方法,因此它们有许多相似的特征,比如说经过多代迭代,ACO和GA都会计算适应度函数来评估解决方案是否有改进。
研究人员在这次的研究工作重点是将GA作为节能虚拟机放置元启发式优化的典型示例,与数据中心能源效率相关的是虚拟机整合。
之前提出的工作表明,VM整合可以在估计基准程序时节省能源,但这种能源感知虚拟机整合通常会改变任务执行和虚拟机操作的行为。
它需要与服务质量(QoS)和服务级别协议(SLA)一起考虑,许多人在工作中并不直接考虑虚拟机整合,但可以通过配置文件引导的三阶段虚拟机放置框架来减少虚拟机迁移的数量。
遗传算法的实现
GA现在在数据中心的虚拟资源管理中被多层实施,它专为向虚拟机进行配置文件引导的应用程序分配而设计。
与PM的VM放置类似,VM的应用程序分配也是一种装箱问题,配置文件和元启发式遗传算法的概念有助于降低数据中心的能耗。
因此,GA是一种通过虚拟资源管理来优化数据中心能源的有前景的工具,但GA的一个关键问题是其在提高数据中心能源效率的情况下执行质量解决方案的速度缓慢。
比如说,GA的运行速度比FFD慢得多,通过VM的VM放置问题,FFD的计算复杂度为。
相比之下,群体大小为的非支配排序GA(NSGA)的初始排序部分的计算复杂度为氮电压Nvm,为了在数据中心中进行高能效的VM放置。
根据遗传算法组件(例如交叉和变异)的多代计算是非常耗时的,GA在更现实的数据中心场景中的应用还需要加速。
这几十年来,研究人员一直在努力调整GA,并且讨论了遗传算法的控制参数,比如种群大小、交叉率、突变率、代沟、缩放窗口和选择策略。
但这些参数的设置经过优化以获得更好的性能,从而产生具有增强交叉和变异的自适应遗传算法。
这激励他们对交叉和变异进行深入研究,以实现节能虚拟机放置中的加速GA,而为了提高GA的性能,研究了GA的种群大小及其与选择率和染色体长度的关系。
并且通过对这些关系的分析,设计了一个紧凑的遗传算法,它通过压缩选择率和种群规模来节省计算资源,这些发现已被嵌入到一般的GA实施中。
最近一项关于基于GA的数据中心虚拟资源管理的工作重点关注GA的计算性能,以能量成本作为适应度函数,它使用FFD的结果作为初始(可行)解决方案。
之后它采用减治的概念来简化遗传算法的计算,这可以提高GA的执行时间性能,实现节能的虚拟机放置。
技术差距和动机
遗传算法已应用于节能数据中心的虚拟机放置问题,研究人员一直在努力提高遗传算法的性能,特别是在优化其参数和选择更好的初始可行解决方案方面。
当遗传算法运行得更快时,就会在给定的时间内导出更节能的改进解决方案,对于整个GA计算过程中执行时间花费最多的地方还有待深入理解。
这种理解将有助于进一步研究和开发计算效率高的GA,以便将节能的VM放置到云数据中心的PM中。
在这次的研究工作中表明,标准GA的执行时间主要消耗在适应度计算上,所以研究人员的工作主要集中在适应度函数的计算上。
它嵌入了从我们之前的研究扩展而来的新数据结构,以降低适应度计算的复杂性,结合该数据结构,提出了一种计算需求少得多的替代适应度函数。
对节能虚拟机放置的GA计算的见解
而这次的研究重点是介绍标准GA的计算(在执行时间方面),以实现节能的VM放置,通过分析,我们的目标是深入了解如何有效加速GA。
为了实现节能的虚拟机放置,标准GA由许多组件组成,其中一些组件按顺序执行,而另一些组件则重复运行,标准遗传算法的总体流程由实验可以得出结果
而GA从初始化模块开始,包括数据输入、任务分配和初始种群,之后它运行选择模块作为锦标赛选择,如果成功选择了两个父母,则继续进行交叉模块,否则重复选择过程。
交叉过程之后是突变和个体验证,检查适应度值和种群,并决定返回种群模块或评估模块。评估完成后,要么返回到下一代GA生成的种群模块,要么输出结果并终止GA计算。
为了了解GA在计算中花费大部分时间的地方,研究人员从执行时间角度分析了GA计算,以实现数据中心中节能虚拟机的放置。
对于典型场景,他们获得了最新的研究结果,而结果进行定量分析表明,遗传算法总执行时间的大约80%花在了SCE计算上,变异大约消耗总执行时间的10%。
Population消耗的时间不到总执行时间的10%,而在SCE中,适应度函数注入计算占主导地位,消耗了GA总执行时间的约60%。
所以为了提高GA在节能VM放置中的计算性能,研究人员应该关注适应度计算的简化,从这个理解出发,他们对遗传算法中的适应度计算进行了详细的分析。
结论
为了使遗传算法在大型数据中心的节能虚拟机部署中切实可行,这次研究了如何在不牺牲节能方面解决方案质量的情况下加速遗传算法计算。
通过研究人员的分析表明,与适应度相关的计算消耗了标准GA中的大部分执行时间,所以重点关注加速GA计算中的适应度评估,以实现节能的VM放置。
加速是从两个主要方面实现的:用于降低复杂性的新数据结构,以及用于减少指令计数的替代适应度函数。
从他们之前的研究中扩展出来的新数据结构将GA计算的复杂性从关于VM放置问题的输入大小的二次到线性降低,从而加快了GA计算的速度。
除了这种数据结构之外,还提出了另一种适应度函数,该函数仅与活跃PM的数量相关,它导致每个适应度评估实例所需的指令数量大幅减少,进一步加速了GA计算。
而实验研究表明,在结合新数据结构的替代适应度函数下的加速GA比标准GA快约11倍,可在约1,500PM的大型数据中心中实现节能虚拟机放置。
而不会影响能源效率数据中心的性能,它导致每个适应度评估实例所需的指令数量大幅减少,进一步加速了GA计算。
而在这次研究中提出的工作重点,是通过新的数据结构和替代适应度函数来加速GA计算,它没有考虑QoS和SLA要求对数据中心能源效率的影响。
然而,QoS和SLA在实际数据中心的实际管理和运营中非常重要,如何将QoS和SLA要求嵌入到节能的VM放置问题中值得未来进一步研究。
标签: #二维装箱启发式算法 #使用遗传算法求解函数最大值 #遗传算法在影像处理与分析中的应用研究 #遗传算法中的代沟是什么意思