云数据中心的能效与性能：混合元启发式算法的应用研究

工程科学与技术，国际期刊23（2020）211完整文章HIGA：用于云数据中心Mohan SharmaMr.，Ritu Garg计算机工程系，国立技术学院Kurukshetra，136119，印度阿提奇莱因福奥文章历史记录：收到2018年2019年3月23日修订2019年3月25日接受在线提供2019年保留字：云计算任务调度能量和机架感知遗传算法和声搜索混合元启发式A B S T R A C T降低云数据中心的能耗是云社区的主要问题之一。它降低了与能源相关的成本，延长了部署在云数据中心的高性能计算资源的使用寿命，还有助于减少碳排放。与能源效率一样，任务调度问题也是云数据中心需要考虑的重要问题之一，属于NP类问题。随着能量消耗的考虑，任务调度问题变得更加复杂。元启发式算法被证明可以产生任务调度问题的近似最优解，但其调度开销随着任务数量或资源数量的增加而大大增加。此外，基于元分析的调度算法大部分时间处于解空间的局部最优区域，并且可能仅在局部最优区域中最终确定解。本文主要从遗传算法本身出发，针对现代云数据中心架构下的节能任务调度问题，提出了一种新的混合元启发式算法--和谐启发遗传算法（HIGA）。它还解决了与元数据挖掘- tic算法相关的问题HIGA结合了遗传算法的探索能力和和声搜索的开发能力，它智能地感知局部和全局最优区域，而不会在局部或全局最优区域浪费时间（迭代），并提供快速收敛。我们在这项工作中的主要这些目标共同指导HIGA提高能效和性能，同时减少所需资源（即活动机架）的数量。它还间接地减少了冷却能量，因为一旦机架空闲，我们可以关闭机架组件（鼓风机，冷却入口）。模拟分析已经在独立的任务应用程序以及现实世界的科学应用程序，如CyberShake，表观基因组学和蒙太奇。结果清楚地表明，拟议的HIGA提供了高达33%的节能和47%的应用程序性能（完工时间）的改善，也与39%的执行开销少。©2019 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍几乎每个在线用户都直接或间接地使用云计算。云计算是一种新的计算模式，它将计算作为一种可扩展和可靠的实用工具，我们可以从互联网内部的某个地方借用硬件和软件。这些软件和硬件是提供和托管的*通讯作者。电 子 邮 件 地 址 ： mohan@mohansharma.me （ M.Sharma ） ， nitkkr.ac.in（R.Garg）。由Karabuk大学负责进行同行审查云服务提供商（CSP）（例如Amazon EC2、Google Compute Engine和Oracle Cloud）。CSP提供了许多不同类型的服务，但大致分为架构即服务（IaaS），平台即服务（PaaS）和软件即服务（SaaS）。随着云计算应用的普及和需求的随着对高性能计算资源需求的增加，云数据中心的能耗率也随之大幅增加计算资源和连接的冷却设施消耗的能量是https://doi.org/10.1016/j.jestch.2019.03.0092215-0986/©2019 Karabuk University.出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：www.elsevier.com/locate/jestch212M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211据估计，全球数据中心的能源消耗约占全球电能消耗的1.4%，并且每年以12%的速度增长[1]。加工装置、冷却设施和储存设施消耗的电力最高，分别为42.0%、15.4%和14.3%[2]。因此，云计算的关键问题是：如何在保持生产力和执行性能的同时降低能耗及其相关成本最小化能耗提高了系统的总生产率、可靠性和可用性。此外，最大限度地减少能源消耗不仅可以降低能源相关成本，还有助于保护我们的自然环境，因为它还可以减少碳排放量。高效的资源管理是平衡云性能和成本同时保持服务可用性的关键。在我们的工作中，主要目标是降低能耗和提高云性能。1.1. 相关工作许多研究人员一直关注云数据中心的能源效率问题以及其生产力和 性 能 。 高 能 效 技 术 ， 如 动 态 电 压 和 频 率 缩 放 （ DVFS ） 、SpeedStep[3]、AMD PowerNow！[4]、AMD但是通过控制操作频率会损害云性能。另一种降低能耗的优秀技术是虚拟化，它通过在单个物理服务器上容纳多个虚拟服务器来减少物理服务器的数量[7]。通过使用需求驱动的CRAC装置和变频驱动（VFD）风扇，最大限度地提高冷却效率是降低能耗和能源相关成本的另一个关键因素[1]。因此，在这项工作中，我们的次要目标是减少浪费在冷却非活动资源上的能量。此外，考虑到CPU能量利用率与工作负载[8]或组件利用率与系统功耗[9]之间的相关性，不同作者提出了许多功耗建模技术。这些基于利用率的功耗建模导致能量感知调度机制，其中在机器上运行的单个任务被视为能量分析的基本单元。调度是对于任何业务前景都是一项关键任务。云环境下的任务调度是指将各种可感知的任务提交给一定数量的云资源的过程。应用程序调度极大地影响性能和生产力[2]。因此，在由CSP托管的CDC中，任务调度是要考虑的重要问题之一，因为它可以提高吞吐量和生产率。它还有助于实现能源效率的资源管理。任务调度问题是一个NP难问题。许多研究人员正在研究这个问题，有不同的目标集，如资源利用率，完工时间，服务水平协议，提高吞吐量，能源消耗，和负载平衡。任务调度的效率受处理器性能、网络拓扑和带宽、内存空间、异构程度、任务类型（独立或依赖）、任务截止期、随机任务行为、处理能力、计算资源类型（单核或多核）、频繁数据交换和其他任务要求等诸多因素的影响为了提高能量利用效率，研究人员正致力于将更多的能量相关参数引入到调度算法中。在这项工作中，我们解决了独立以及依赖的任务调度问题，旨在降低能耗，提高云性能。通常，为了解决节能任务调度的复杂问题，研究人员提出了基于DVFS的节能任务调度[10-12]，其中他们依赖于支持DVFS的硬件来减少能耗，使其仅限于计算能量。因此，有必要进一步研究其他组件（如物理主机、虚拟机、机架和冷却设备）的行为，因为它们的能耗受到任务调度器的影响。因此，在这项工作中，我们考虑了现代数据中心架构，包括机架组件及其连接以及传统的能源和性能相关参数。机架硬件用于支持主要资源，并提供有组织的方式来管理不同的模块，如冷却、配电装置、互连机架、鼓风机等。如果机架内的计算资源执行任何任务时，我们可以关闭这些模块以节省能源。因此，次要目标之一是最小化活动机架的数量和机架模块消耗的能量。在[31，32]中，作者提出了用于不确定云计算的节能实时任务调度，并提出了用于任务调度器的不确定性感知架构，但此外，随着能源效率的提高，用户应用在性能方面的服务质量（QoS）也是最重要的。在这种情况下，任务调度问题被转化为多目标优化问题，其目标是对能量效率、执行性能和活动机架数这三个相互冲突的目标进行优化。这个问题可以看作是一个组合问题，使用简单的算法来获得全局最优解。因此，元启发式算法，如遗传算法（GA）[13，14，24]，粒子群优化（PSO）[15]，蚁群优化[16]和和声搜索（HS）[30]被广泛用于解决多目标任务调度问题。在[25]中，作者简要回顾了在云计算中使用元启发式调度技术。这些元启发式调度技术的问题是：1）执行时间主要取决于迭代次数，因此增加了执行时间; 2）引导适应度函数，其定义在目标的集体性质上; 3）优化算法可能被困在局部最优区域内而永远不会到达全局最优区域。因此，我们需要一个元启发式技术，检查局部最优区域以及全局最优区域。如果算法恰好处于局部最优区域，它会尝试跳出陷阱，在不浪费大量迭代的情况下到达全局最优区域，并且一旦到达全局最优区域，它会尽快停止。因此，为了解决这些问题，我们提出了一种新的混合元分析优化算法来解决我们的多目标任务调度问题。它动态地减少所需的迭代次数，每当它遇到局部或全局最优区域，它检测和避免下一个局部最优区域。在我们的混合方案中，主要的元启发式技术是GA，每当我们的计划检测到GA内的陷阱，它把GA再次的方式与HS的帮助下，全球最优区域。选择这两种元启发式方法的唯一原因是它们已被广泛应用于任务调度问题，并被证明在生成解决方案方面是最好的。基本上，我们结合了和声搜索算法的开发能力以及遗传算法的探索能力，以获得快速收敛。此外，我们已经使用了符合我们的主要和次要目标的适应度函数。因此，在这项工作中，我们正在考虑多目标任务调度问题有四个目标，以最小化：1）使跨度;减少云应用程序的执行时间，2）能源消耗;减少计算能源的数量，3）数量M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211213主动机架;减少通信时间，以及正在使用的计算资源的数量，和4）机架消耗的能源;最大限度地减少能源消耗的不同机架组件，如鼓风机，风扇，互连海湾等，因此，我们提出了一种新的和谐启发的遗传算法（HIGA）的机架感知能源效率的任务调度问题，考虑独立和依赖的任务。最后，我们进行了广泛的模拟实验，以验证所提出的算法，考虑独 立 的 任 务 ， 以 及 各 种现 实 世 界 的 科 学 工 作 流 应 用 程序 ， 如CyberShake，表观基因组学和蒙太奇。我们发现，Meta启发式的方法（GA，HS，PSO等）。以及一些基于启发式的方法（HEFT、MinMin、MaxMin等）。被许多研究者所接受因此，我们比较了我们提出的算法与这些标准算法的性能我们提出的算法的关键贡献可以总结如下：确定并提出新的调度目标：活动机架数量和机架消耗的能量以及完工时间和能量消耗提出了一种新的混合算法（HIGA），将和声搜索和遗传算法这两种不同的Meta启发式算法的优点这种混合方法将执行时间复杂度降低了近一半，所需的原始遗传算法考虑了现代云数据中心的架构和机架组件（风机、进风口、机箱风扇等）及其连接性;并针对实时相关和独立任务实现了云数据中心（计算和冷却）的显著节能，同时保持了应用程序性能并降低了执行开销剩下的论文组织如下：在第2节中，我们提出了问题陈述及其假设和环境建模。第三节给出了算法的伪代码。在第4节中，我们介绍了拟议工作的评价。最后，在第5节中，我们总结了我们的工作与未来的工作指示。2. 数学建模和问题表述在本节中，我们将正式描述用于表示现代云环境的数学模型、表示调度器生命周期的调度模型、表示用户工作负载的任务以及用于估计能耗的能耗模型。2.1. 环境模型CSP可以有许多分布在不同地理位置的数据中心，目的是消除停机时间并跨区域共享数据。通常，云数据中心（CDC）表示为分组在一起的高性能计算（HPC）资源的集合。然而，除了这些资源之外，还有其他资源可以支持和延长这些资源的使用寿命，例如机架室、冷却设备（鼓风机、风扇和CRAC单元）、网络交换机、配电单元（PDU）、存储设备等。对于云数据中心建模，我们只考虑以下组件：机架、物理主机和虚拟机。图2.1表示具有多个地理上分布的数据中心的典型CSP。机架在每个机架中，安装固定数量的物理主机（例如，16、25、32个主机）。这些物理主机基于不同的配置参数消耗功率。这些物理主机与 10 个 机 箱 风 扇 和 内 部 网 络 互 连 机 架 捆 绑 在 一 起 ， 根 据 HPBladesupp级的统计数据[17]，功耗除了这些组件，还有与每个机架相关联的鼓风机，以降低机架温度。鼓风机此外，每个机架连接到集群级网络交换机，其可以使用1到10Gbps链路，并且还可以具有到数据中心级交换机的多个上行链路连接图 2.2表示大型数据中心中的典型机架组。物理主机是安装在机架中的高性能计算资源，通过互连机架连接到公共内部网络。在此物理主机中，部署了多个虚拟机，这些虚拟机由虚拟机监视器（VMM）管理。虚拟机监视器-大多数CSP使用虚拟化技术在云用户之间提供可靠、可扩展和经济高效的资源共享（例如Amazon EC2和GoGrid使用Xen虚拟化）。利用虚拟化技术，CSP可以在一台物理主机上拥有多个虚拟机这些虚拟机与同一物理主机上的其他虚拟机共享物理主机基于上 述信息， 我们以数 学方式定 义了一个 典型的数 据中心（DC），如下所示：DC1;R 2 ; R 3：R R 1; R 2;R 3; R3;R4;R5;R6;R7;R8;R9;R9;R9;RBWij1其中，Ri表示第i个机架，BWij表示数据中心内第i个与第j个机架之间的带宽。可能存在与每个服务器机房或机架组相关联的多个PDU和CRAC单元。类似地，可以安装多个集群级网络交换机以形成机架集群，每个机架通过机架集群连接到具有均匀带宽的其他机架每个机架Ri可以表示为一组物理主机，具有10个机箱风扇、互连托架和一个鼓风机，其定义如下：Ri=Hi1;Hi2;Hi3：H i=H i =Fi10;Bi;Ni;BWi=2其中，Hij表示安装在机架Ri中的第j个物理主机机器; Fi10表示机架Ri的一组10个外壳风扇的功耗率，Bi表示安装在第i个机架机柜底部的鼓风机;Ni表示机架Ri（互连机架）中的主机的内部完全连接的网络，每个物理主机通过该网络通过高速本地链路连接到其他物理主机，BWi表示第i个机架内的两个主机之间的带宽。根据机架供应商或DC要求，特定机架中的物理主机数量可能不同，但最常见的是16、25、32或42。外壳风扇建模的原因Fi10和鼓风机Bi与机架Ri的区别在于，一旦没有任务在该特定机架上运行，我们就可以关闭这些组件以节省能量。出于同样的目的，我们分配一个功耗率到每个这样的组件。●●●●214M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211.ΣIJIJIJ图2.1. 典型的数据中心架构。图2.2. 数据中心中典型元素的示意图：物理主机（左），中间带内部网络交换机的机架（中）和小型机架集群的示意图每个物理主机Hij是DVF使能的高性能计算资源，并且支持具有单独存储单元或虚拟存储单元（共享存储单元）的多个虚拟机DVFS技术用于根据当前主机利用率通过降低电压供应水平以及频率（处理能力）来降低能量使用该信息，我们如下定义物理主机Hij：H 1/4。C;PM100 mg/kg与物理机器非常相似，不同之处在于功耗模型是在物理主机级别定义的我们假设虚拟机放置在一个单一的物理主机将执行时间共享的方式。VM定义如下：Vijk¼Cijk4其中，Cijk与物理主机的含义相同，但定义为第k台虚拟机托管在已安装的第j台在第i机架其中，Cij是以每秒百万指令（MIPS）为单位的总计算能力，PMij是基于DVFS技术的功耗模型。虚拟机（VM）是使用VMM创建和管理的虚拟化机器。虚拟机使用/共享基本物理主机的因此，虚拟机的参数是2.2. 调度模型在现实世界中，许多云用户使用CSP提供的前端任务管理面板提交和上传任务配置文件。任务配置文件包含任务工作量详细信息，实际M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211215BWIP.ΣFTT VV2IJK;Vpqr;filesize¼ BBWiCijkp1ijk程序、其他任务依赖关系等。然后，CSP收集来自多个云用户的这些上传的任务配置文件，并将其发送到执行管理器进行进一步处理。执行管理器（EM）将任务映射到可用资源，并在任务完成后通过任务管理面板向云用户反映状态一旦EM有了任务配置文件，它就将它们添加到等待列表中，调度程序将从等待列表中调度可用资源（虚拟机）上的就绪任务。当调度任务完成执行时，EM更新状态，以便其他等待任务可以进入准备列表。缓存为了计算通信时间，我们需要知道文件的大小，源主机和目的主机之间的带宽机架使用互连机架提供高速内部网络，这比两个不同机架之间的速度要快[2]。因此，我们可以说机架内的文件传输比机架之间的文件传输更此外，如果源文件在同一主机上，则文件传输时间为零。因此，数据中心DC内任意两个虚拟机之间的通信时间定义如下：CNOMS将把就绪列表作为输入，并生成任务到资源的映射，其数学定义如下：0.CIBB如果 同一主机上的两个虚拟机¼ 0i：e：i<$p;j<$q如果 同一机架上的两个虚拟机文件大小为1/4Ci：e：i¼pS. T 1; T 2; T 3：Tjreadylistj就绪列表。T1！Vijk：Tjreadylistj！Vxyz5B@如果两个VM在不同的文件夹上都有1/4文件大小CA在哪里，T1？Vijk表示任务T1在虚拟设备上机器Vijk。i：e：ið7Þ2.3. 应用模型任务表示云用户提交的工作负载。每个任务都有不同的工作量和通信要求。有些任务会产生直接发送给云用户的输出，但有些任务会产生中间输出，其他任务会将其作为输入。中间输出存储在具有唯一签名的存储单元中，任务，并在需要时。根据这些信息，我们其中，Vijk和Vpqr分别表示源虚拟机和目的地虚拟机，filesize表示要传输的数据的大小，BWi表示第i个机架内的带宽，BWip分别表示第i个机架和第p个机架之间的带宽。使用上述信息，我们可以计算任务Tp在虚拟机Vijk上的估计执行时间EET（Tp，Vijk），并由下式定义：WP应用程序任务定义如下：EET。T p; V ijkmax FTT.Vsource;Vijk;filesize文件大小Cijkð8ÞTp/Wp;Ip;Op其中，W p表示以百万指令（MI）表示的工作负载参数，I p表示它将等待的一组输入文件签名，O p表示由任务T p产生的一组输出文件签名。定义的任务模型表示工作流（依赖）任务应用程序以及独立的任务应用程序。独立的任务将有空的输入文件集IP.工作流应用一般表示为有向无环图（DAG），在现有模型中也可以实现可视化。图2.3显示了工作流应用程序及其任务配置文件的示例。在图2.3中，任务T1的工作负载为1000 MI，没有输入文件要求，完成后将生成两个输出其中，Wp是任务Tp的工作负载参数，Cijk是虚拟机Vijk的计算能力（MIPS），Vsource是存储所需输入文件（如果有的话）的虚拟机，并且filesize（file）给出由签名文件标识的文件的大小。云环境中任务调度的主要目标之一是最小化完工时间，其中调度S的完工时间基本上是来自调度S的每个任务完成其执行的最大完成时间。我们假设在单个虚拟机上调度的任务将按顺序执行（空间共享）。为了估计完工时间，首先我们需要估计每台虚拟机的完工时间.因此，虚拟机对所有分配的任务的估计完成时间（EFT）定义如下：文件通过签名被称为文件1和文件 2任务T2和T3，500 MI和300 MI的工作负载分别使用这些输出文件作为其输入文件，因此如果没有这些文件，则无法开始执行EFT。V/VXEET.T;V98 T p 2Vijk文件，并且还分别生成任务T4开始其执行所需的输出文件file3和file 4任务T4将生成由签名文件5标识的工作流应用程序的最终输出根据文件的大小和网络带宽，只有在本地读取文件后，任务才可以执行。图2.3.示例工作流应用程序a）任务配置文件b）表示任务配置文件的DAG。其中，Tp表示分配给虚拟机Vijk的任务。此外，所考虑的目标之一是调度S的最大完工时间，其是所有分配的虚拟机器的最大完成时间，并且定义如下：最大完工时间为20小时，最大值为8小时。Vijk10其中，Vijk表示在调度S任务中分配的虚拟机。由于任务的执行时间在调度前无法准确估计，我们可以借助资源监视器来监视资源。如果由于资源可用性的波动而检测到显著延迟，则可以对未执行的任务进行自适应重新调度[33]以处理波动。2.4. 功耗模型我们考虑了与基于第2.1节中建模的云基础设施的物理主机相关联的功耗模型。在现代数据中心中，大多数HPC资源都支持DVF，这意味着它可以通过调整文件2Ipijk216M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211Xt¼0第 十章¼r1R10RRIJCij根据机器工作的频率来调节电压，并且根据当前主机利用率来调节图 2.4演示性能和功率之间的关系使用该等式，我们可以如下计算整个调度S的第二主要消耗，源自配备英特尔至强3075和3040处理器的HP ProLiant ML110 G5和HP ProLiant电子邮件800T p！Vijk2SETp;Vijk 14分别使用增强SpeedStep DVFS技术进行分拣，行业标准基准工具SPECpower[18]。其中，Tp表示分配给虚拟机Vijk的第p任务。基于此信息，我们可以在利用率和功耗数据PDATA的帮助下将物理主机的能耗定义为时间的函数，其定义如下：PDATA1/4 待 机！ w0; UT10！ w1; UT20！ w2; UT30！w3;：;UT90！ w9;UT100！ 10岁以下11 岁以下其中，UT表示主机利用率，w表示UT主机利用率上的以瓦特（W）为单位的功耗。表2.1显示HP ProLiant ML110 G5的功耗数据和G4服务器，如图2.4所示，这是我们用于模拟的目的。此外，每个机架Ri具有10个外壳风扇Fi10、互连机架和鼓风机Bi，如第2.1所述，即使只有一个主机正在执行，它们也一旦它们被关闭，它们就什么也不消耗。没有分配任务的空闲机架可以关闭这些组件，以节省额外的能量。使用该信息，我们定义我们的第一个次要目标机架能量（RE），其表示由机架组件消耗的能量的量，不包括由主机消耗的能量，如下所示：RESXmakespanSXjRjrstatust;r·FBN15为了使用上述信息估计任务Tp在虚拟机Vijk上消耗的能量，我们必须计算时间t处的主机利用率。当前主机利用率的计算方法为：在时间t，虚拟机利用的总主机容量除以总主机容量，定义如下：其中，|R|表示DC中所有机架的集合，rstatus（t，r）为阵列保持每个机架的时间上的二进制状态。如果rsta-tus（t，r）的值为零，则意味着在时间t机架r上没有任务，否则该值将为1。使用数组rstatus（t，r），我们可以计算下一个次要目标 活性在时间表S期间的机架（NAR）如下：H U。H;tP8V ijk2Hijk在时间t使用的容量ð12ÞXjRjr¼1t其中，HU给出了在时间t处的Hij主机的主机利用率。使用该信息，我们可以计算在虚拟机Vijk上执行任务Tp时消耗的能量，V ijk在时间stime开始执行，如下所示：2makespan工作时间2.5. 问题陈述和假设在这项研究中，我们考虑了云环境下的任务调度问题，这是一个映射任务集合的过程E.Tp;VijkEETTp;VijkPDATAUT时间HUHij;tΣð13Þ异构计算单元的集合，目的是减少能耗和活动机架的数量其中，EET（Tp，V ijk）表示Tp在V ijk上的估计执行时间，UT HU（Hij，t）给出在时间t处的H ij的利用率。当量公式（12）用于计算给定时间t的主机利用率，它有助于公式（12）。（13）基于功率数据和主机利用率来估计能量消耗。而不会降低执行性能。在这项工作中，我们安排了一组独立的任务以及一组相关的任务（工作流）。与该问题相关的一些假设如下：图2.4. HP ProLiant ML110 G5（左）和HP ProLiant ML110 G4（右）的服务器能效数据表2.1HP ProLiant G4和G5服务器的功耗相关数据服务器利用率0%的百分比百分之十百分之二十百分之三十百分之四十百分之五十百分之六十百分之七十百分之八十百分之九十百分百HP ProLiant G486瓦89.4瓦92.6瓦96 W99.5瓦102瓦106瓦108瓦112瓦114瓦117 WHP ProLiant G593.7瓦97 W101 W105 W110 W116 W121 W125 W129 W133 W135 W公司简介MaxSrstatust;r16M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211217对于随机主机利用率，任务工作负载随时间均匀分布。主机带宽也均匀分布在数据中心。即使所有主机都处于空闲模式或在未使用相应机架时以编程方式关闭，机架中的盘柜风扇、鼓风机和互连托架也会消耗相同的能量为了降低问题的复杂性，我们没有考虑任何网络参数，除了总可用带宽。此外，数据中心中的机架之间的带宽对于完全连接的所有机架是相同的，并且在机架内每个主机都是完全连接的。我们假设机架内带宽高于机架间带宽，机架内延迟低于机架间延迟3. 和谐遗传算法本节介绍了所提出的和谐启发遗传算法考虑任务调度问题。与元启发式技术相关的问题是，它们往往会增加调度开销，有时它们最终会出现在局部最优区域，而不是给出全局最优解。因此，我们确定需要有一个元启发式技术，可以感觉到局部最优区域，并以某种方式可以避免它。此外，它还应该感知全局最优区域，一旦检测到全局最优区域，它就停止自己。因此，我们提出了一种新的元启发式技术命名为和谐启发式遗传算法。它试图在运行时检测局部最优区域以及全局最优区域，同时进化任务调度。这种混合算法的基本思想是，当遗传算法中的最佳个体在多代中保持在解空间中的同一位置时，它可能处于局部最优区域或全局最优区域。当出现这种情况下，我们的混合方案搜索更好的解决方案在其他解决方案空间的帮助下，和声搜索和更新当前的人口在遗传算法。当和声搜索多次失败时，意味着最优个体可能处于全局最优区域。过程可以自行停止。代替停止算法，我们提出了减少每次算法感知局部或全局最优点时的最大迭代次数。 图 3.1表示任务调度问题的混合方案的工作。为了获得最优调度决策，我们考虑-将遗传算法作为主要的优化算法。遗传算法是从自然选择和遗传学的进化思想中衍生出来的自适应启发式搜索算法。它代表了智能随机搜索，并用于解决许多优化问题[19基本上，GA模拟了个体之间的适者生存，通过世代来解决问题，并且基于与种群中染色体的行为和遗传结构的类比，使用图3.1. 任务调度问题的HIGA混合格式的工作。以下过程：1）个体竞争资源和交配2）最成功的个体将比表现不佳的个体产生更多的后代3）来自最好个体的遗传信息产生比其父母中的任何一个更好的后代4）通过连续的世代，每一代变得更适合他们的环境。在多模态问题的情况下，局部最优解不仅是遗传算法的主要问题，而且是用于找到全局最优解的任何优化算法的主要问题。遗传算法在探索阶段表现得很好，每个个体发现解决方案的一部分，并将它们组合在一起，可以产生更好的解决方案。但是当局部最优点被任何个体发现时，那么该特定个体将设法保持其位置几代人，这是浪费时间和空间。渐渐地，所有其他个体开始接近这个局部最佳点，因为这个局部领导者经历了许多代人的生存最后，整个进化过程停止在局部最优点。为了避免这种局部最优的问题，我们已经试验了许多不同的方法，并提出了一种独特的混合方法，我们正在考虑和声搜索[23]，以使GA回到全局最优点，因为HS具有更好的开发能力。HS是一种用于全局优化的元启发式算法，其灵感来自于观察到音乐的目的是寻找完美的和谐状态，这类似于在我们的优化过程中找到最优性优化的搜索过程可以与爵士音乐家的即兴创作过程相媲美HS具有易于实现、算法特定参数少且收敛快的优点[26]。3.1. HIGA和伪代码的工作所提出的混合方案（HIGA）分四个阶段运行，如图3.1所示。在第一阶段，它使用遗传算法进化当前生成。在第二阶段，它保存进化的一代的最佳个体，并根据最佳个体从过去的几代，它检测遗传算法是否卡在局部最优点或没有。阶段3和阶段4将只执行混合计划检测是否遗传算法是停留在局部或全局最优点。在第三阶段，混合算法对最后进化的一代进行和声搜索，以找到更好的最优区域。进一步执行和声搜索后，混合方案结合最好的个人从进化的一代以及新一代和声搜索。在第四阶段，评估和声搜索的效果，每一个消极的和积极的影响。此外，使用该计数器，混合方案检测遗传算法是否处于全局最优区域。每当混合算法检测到局部最优点时，它将最大迭代次数减少和声搜索中使用的迭代次数。此外，当检测到全局最优区域时，它将最大迭代次数减少了和声搜索中使用的迭代次数的一半。我们的目标是减少浪费在局部或全局最优区域的迭代次数.一般来说，这种元启发式技术执行，直到消耗的迭代的最大数量，但在我们的混合方案中，一旦最大数量的迭代集，它可能会或可能不会消耗每一次迭代。为了实现这一目标，我们在遗传算法中引入了领导者的概念以及其他参数。这些参数将共同决定遗传算法是否正在通过任何局部或全局最优区域。领导者在我们的混合方案中，引入了以下新参数归纳：1）追溯;用于追溯历代领导人的位置。 如果痕迹的价值 是2，这意味着●●●218M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211两代领导者附录1（续）算法1 HIGA（任务，资源）Money搜索不能使遗传算法跳出局部最优，mal区域。基于这两个参数，我们有两个阈值，我们的混合计划检测遗传算法在局部或全局最优区域。阈值参数如下：1) traces_limit;参数trace的阈值，之后我们声明遗传算法在局部最优区域，2) trials_limit;参数试验的阈值，之后我们宣布遗传算法在全局最优区域。除了这些参数，我们还有两个参数，如下所示：1）hs_iterations;这是harmony search用于搜索解空间中另一个更好区域的最大迭代次数;2）worst_cand;该参数表示每次试验时推向最佳个体的个体数量 递增。算法1表示所提出的混合方案的伪代码，并显示所考虑的参数是如何更新的，并帮助我们的算法在优化过程中实现快速收敛。HIGA需要两个输入任务和资源，分别包含任务工作负载信息和物理主机配置文件。(Line1）首先确定算法的具体参数如下：1）max_iterations;迭代次数HIGA假设搜索解，该参数的值应在22.End If23.End If24.i = i + hs_迭代25.End If26.i = i +127. While（i max_iterations）28. Return Leader（GAi）(Line 2）HIGA随机生成初始代个体，在整个解空间中均匀分布。(Line3-27）HIGA通过进化个体来迭代世代，以更好地适应他们的环境，在我们的情况下，每个个体都是有计划的，有些计划更好，有些是最差的。但在下一代中，调度将进化得越来越好，甚至最终收敛到近最优解。(Line 4）首先按照遗传算法中定义的进化方式对当前世代进行进化。它使用GAEvolution函数从遗传算法中获得下一代。GAEvolution函数表示单代进化，其定义如下：函数GAEvolution（生成）最小值大于任务数和数量的乘积资源的BER，2）dim_variables;决策变量的数量必须等于任务的数量，3）lower_bound和upper_bound;每个决策变量的下限必须为1(1) 并 且 每 个 决 策 变 量 的 上 限 必 须 等 于 资 源 的 数 量 ， 4 ）crossover_probability; 这 是 遗 传 算 法 中 的 交 叉 算 子 的 概 率 ， 5 ）mutation_probability;这是遗传算法中发生变异的概率，6）HMCR;这是和声搜索认为它是部分解的必然性的速率，7）PAR;这是和声搜索中的音调调整速率，8）HSBW;这是和声搜索带宽的宽度，9）population_size;任何代中的个体的数量，10）权重i;与每个目标相关联的权重。此外，利用这些参数，新引入的参数也被初始化。算法1 HIGA（任务，资源）29.求给定世代中每个个体的适应度30.使用轮盘选择方法执行父选择31.执行概率为Pc的均匀交叉算子32.以概率Pm对新个体执行变异算子33.根据适应度进行幸存者选择34.将剩余的个体作为新一代(Line 6-如果当前一代的领导者相对于上一代的领导者处于相同的位置，则其增加迹线计数。1.根据输入初始化算法特定参数例如任务、资源2.随机生成初始代HIGA03.做4.GAi = GAEvolution（GAi-1）5.//更新leader跟踪6.如果Leader（GAi）== Leader（GAi-1）7.traces = traces +18.End If9.//检查局部最优区域10.如果trace>= trace_limit11.traces = 012.HS = HarmonySearch（GAi，hs_iterations）13.HIGAi = ExtractBestIndividuals（GAi，HS）14.//检查HS是否失败15.If Leader（GAi）Leader（HS）16.试验次数=试验次数+117.GAi = ImproveWorstIndividuals（GAi）18.//检查全局最优区域19.如果trials >= trials_limit20.i = i +（hs_iterations/2）21.试验= 0（第9行）它检查局部最优区域。如果迹线计数超过由traces_limit设置的阈值，则这将意味着从过去（traces_limit）代开始，leader如果是这样的话，那么从11-34行(Line 11）重置下一次试验的轨迹(Line12）将和声搜索应用于当前代，和声搜索试图在解空间中的任何地方找到更好的区域，并从该区域返回个体。它使用Har-monySearch函数来执行和声搜索。HarmonySearch函数表示一个完整的和声搜索，它将当前生成和分配给和声搜索的迭代次数作为输入。和声搜索基本上是通过搜索更好的和声来模仿音乐即兴创作的过程它遵循三个简单的规则来产生更好的和谐：1）考虑内存中的任何解决方案（第40-43行最后，如果新生成的和声比存储器中已经存在的最差和声好，则用这个新和声替换最HarmonySearch函数定义如下：M. 夏尔马河，巴西-地Garg/工程科学与技术，国际期刊23（2020）211219f-minx17函数HarmonySearch（生成，迭代）35. 记忆=世代36. 做37.生成新的候选人C38.对于候选项C中的第39.如果rand（0，1）hmcr40.从记忆中挑选Ci41.If rand（0，1）par42.Ci =Ci+ rand（0，1）* hsbw43.End If44.其他45.在搜索范围内随机生成Ci46.End If47.结束Foreach48.计算候选人C49.如果适应度优于来自Memory的50.用内存中的C替换Cworst51.End If52. While（i迭代）53. 返回上一个内存作为新一代HS(Line13）在执行和声搜索之后，我们有两个不同的代，一个来自遗传算法，第二个来自和声搜索。我们从两个世代中提取最好的个体，并丢弃剩余的个体。它只是一个接一个地比较两代人中的个体的 适 应 度 ， 并 且 只 选 择 最 好 的 个 体 。 为 此 ， 它 使 用ExtractBestIndividuals函数，定义如下：函数ExtractBestIndividuals（generation1，generation2）函数ImproveWorstIndividuals（生成）67. 按适应度68. 找到一代69. 对于i = population_size70.generation（i）= generation（i）+（2 * rand（0，1）*（leader - generation（i）71. 端72. 返回生成(Line 19）它检查全局最优区域。如果试验次数超过trials_limit设置的阈值，则意味着leader在过去的许多代中都处于相同的位置因此，我们将最大迭代次数（max_iterations）减少和声搜索所使用的迭代次数的一半（hs_i