云计算任务调度的第三代遗传算法NSGAIII

沙特国王大学学报一种用于云计算任务调度的第三代遗传算法NSGAIIILatreche Imenea，Saha，Slatnia Sihema，Kazar Okbaa，b，Batouche Mohamedca阿尔及利亚比斯克拉大学计算机科学系，BP 145，07000b阿拉伯联合酋长国阿拉伯联合酋长国大学信息技术学院信息系统和安全系cP.O. Nourah bint Abdurrahman公主大学计算机和信息科学学院信息技术系。地址：沙特阿拉伯利雅得11671阿提奇莱因福奥文章历史记录：收到2021年2022年3月10日修订2022年3月15日接受2022年3月31日在线提供保留字：元启发进化多目标算法NSGAIII任务调度云优化A B S T R A C T云中的任务调度被认为是一个困难的多目标优化问题。它是指在可用的云虚拟机上分配用户任务。这个问题可以通过结合两种或更多种方法来有效地解决，以提高任务执行和增加资源的使用。在本文中，第三代多目标优化方法，称为非支配排序遗传算法（NSGA-III）首次被用于我们所知的基于一个新的多目标自适应函数，以最小化运行时间（TE），功耗（CE）和成本（cout）在云中的一组可用虚拟机（VM）上调度一组用户任务。此外，NSGAIII的性能进行了比较，它的前一个版本，非支配排序遗传算法（NSGAII）的性能，其中NSGAIII的结果优于NSGAII的结果所提出的方法的实验结果是令人鼓舞的，因为它们被用来显示其在解决此类问题的有效性。版权所有©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍云计算可以被定义为一场经济和技术革命，其中信息技术（IT）资源（CPU、内存、存储等）通过安全的互联网连接作为服务提供。各种云功能，如按需、自助服务和服务质量、基于使用的计费、虚拟化和弹性，使云在行业和研究社区中很受欢迎。此外，云计算为管理数据和基础 设 施 提 供 了 更 好 的 解 决 方 案 （ Slaheddine ， 2012; Thibaud ，2012）。随着云计算的IT服务和资源的发展（参见（Franck，2007）和（Nassima和Salima，2016）），出现了许多挑战;例如，安全性和可靠性，对于资源管理问题，我们有它可以被认为是最重要的一部分，*通讯作者。电子邮件地址：imene. univ-biskra.dz（L. Imene）。沙特国王大学负责同行审查用于在给定时间将特定任务分配给某些资源的云，以优化一组服务质量（QoS）值，从而有效使用其资源。后者被认为是一个组合优化问题，使用简单的算法或规则先进先出（FIFO）和最早期限优先（EDF）（Thibaud，2012）是不可能找到全局最优解的。它被称为NP完全问题，因为它必须在可用资源内调度大量任务。在云中调度任务（Sonia，2014）被认为是一个复杂的多目标优化问题，随着参数数量的增加而增加，因为有几个性能参数需要考虑（运行时间，成本和能源...）。Pareto方法中的元进化算法是解决云任务调度问题的一个很好的选择。因为他们在研究过程中直接使用了帕累托最优的概念。生成的解决方案的选择过程是基于非优势的概念（Elmir，2017）。在这项工作中，我们将使用第三代多目标优化的元启发式方法基于参考点）。拟议工作的主要贡献是：https://doi.org/10.1016/j.jksuci.2022.03.0171319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comL. Imene，S. Sihem，K. Okba等人沙特国王大学学报75161) 提出了NSGA-III算法并实现了其在云计算中的任务调度问题。2) 由于NSGA-III算法是NSGA-II的改进，我们强调了以前版本NSGA- II的局限性以及为解决这些问题所做的修改。3) 对算法实现过程中发现的归一化问题进行了介绍和解释。注意，这个细节在算法的原始论文4) 在应用各种技术后，对归一化过程问题5) 将该方法与其早期版本的非支配遗传排序算法（NSGA-II）的结果进行比较。本文的其余部分组织如下。第二节介绍了相关的工作。第3节介绍了基地概念的背景。第4节解释了所提出的改进的云计算优化系统，第5节介绍了所使用的数据结构。然而，实验结果和讨论在第6节中给出。第七部分是讨论和比较研究。最后在第8节中给出了结论和展望。2. 相关作品云计算中的任务调度是一个难题，进化算法等元算法是解决这一难题的很好的候选方法。在云中调度的方法中，有一些经典的方法，如最早截止日期优先（Franck，2007）;循环调度，最短作业优先（Insaf，2016）;以及以下智能方法。Atul Vikas和Dharmendra（Atul and Dharmendra，2015）提出了一种用于云计算吞吐量优化的多目标任务调度算法。此外，这项工作的目标是分配一组用户任务到一组虚拟机，以最小化运行时间（最佳运行时间）。代理接收任务列表和VM列表。为每个QoS值分配一个QoS值，以定义其优先级值，并为每个VM分配一个QoS值。按优势对任务进行排序，其中将VM链接或分配给任务的过程根据任务和VM的列表顺序完成。VM列表中的第一虚拟机与任务列表中的第一任务关联，并且VM列表中的第二虚拟机与任务列表中的第二任务关联。一旦分配到达最后一个虚拟机，下一个任务将重新提交给VM列表中的第一个虚拟机，并且将对所有任务重复分配过程。最后将该算法与传统算法进行了比较。为了提高其功能，可以考虑更多的目标（QoS）。Panda和Prasanta（Panda和Prasanta，2015）提出了一种异构多云系统的分配感知任务调度，目标是将一组客户端任务分配给云虚拟机，以便使用ATS算法（分配感知任务调度）最小化运行时间。在云模型中，多云系统中的每个云都有自己的数据中心，由一组服务器组成，用于部署虚拟机。每个云服务提供商（CSP）都有自己的调度程序，可以使用自己的调度策略将任务分配给VM。但是，云调度策略可以不同。Jena（Jena，2015）提出了一种基于嵌套粒子群优化（PSO）框架的云环境下多目标任务调度本文采用多目标优化方法嵌套粒子群算法（TSPSO）对能量和加工时间进行优化。并将TSPSO的结果与最佳资源进行选择（BRS）和随机调度算法（RSA），其中所提出的方法优于BRS和RSA。因此，优化模型应增加更多的目标，并应侧重于更强大的算法。Shekhar和Mala（Shekhar，2014）使用增强的遗传算法提出了云计算中独立任务的任务调度优化。这项工作的目标是最小化运行时间和平衡资源的负载通常，在遗传算法（GA）中，初始种群是随机生成的;这些随机生成的解是低效的，因为存在解可以重复的概率。因此，本文提出的算法的思想是用改进的最大-最小算法产生初始种群。因此，这项工作的未来前景是使用资源的执行成本作为适应性标准。Zuo等人（Zuo等人，2015）提出了一种改进的多目标蚁群优化算法（PBACO）来解决多目标任务调度问题，通过优化四个目标：成本、完工时间、资源利用率和时间截止线。首先，针对云计算中资源和任务的生物多样性，提出了一种更详细地定义任务对资源需求的将该算法与原蚁群算法进行了比较。此外，经典的启发式算法Min-Min算法和先来先服务（FCFS）调度。因此，所得到的结果表明，所提出的方法是优于其他类似的方法。但该方法仍易陷入局部最优，主要是与传统方法进行比较研究。Naik等人 （Naik等人， 2019年）提出了一种多目标优化混合算法非支配排序遗传算法-II（NSGA-II）和引力搜索算法（GSA），名为NSGA-II &GSA。通过优化响应时间、成本和能耗三个目标，选择最适合的GSA选择具有较少能量消耗的VM，其将是NSGA II的群体，其中后者将找到具有较少响应时间和成本的VM因此，该算法的结果优于原始NSGA II和非支配排名遗传算法（NRGA）的结果。在（Adamuthe等人， 2013），Amol et al. 基于利润最大化、负载均衡最大化和资源浪费最小化三个目标，实现因此，所实现的算法得到的结果是很好的解决方案。然而，NSGA-II提供了更好的和多样化的解决方案相比，其他两个。在（Zhou等人，2020），Zhou等人提出了一种新的多目标算法来在云环境中调度任务，称为MGGS（结合贪婪策略的改进遗传算法（GA））。MGGS算法的总完成时间，平均响应时间和QoS参数的基础上进行评估。所提出的遗传算法优于其他任务调度算法，如经典的遗传算法，先来先服务（FCFS），最小最小算法。Alkayal等人 （Alkayal等人， 2016年）使用了基于新的排名策略的多目标粒子群优化算法（MOPSO）进行云调度。主要目标是优化 三 个 冲 突 目 标 ， 即 期 望 完 成 时 间 （ ECT ） ， 任 务 执 行 成 本（TEC），和VM处理。因此，改进表现在等待时间和吞吐量方面。但是，缺少资源利用率和负载平衡的影响L. Imene，S. Sihem，K. Okba等人沙特国王大学学报75172 ≤2在（Yuan等人，2015年），作者介绍了一种基于网格划分的非支配排序遗传算法。它们的目的是提高现有NSGAs算法的多样性和收敛性，以减少计算时间。此外，文中提出的算法NSGA-G的性能优于NSGA版本（NSGA II/NSGA III）和基于分解的多目标进化算法（MOEA/D）。然而，该算法是基于DTLZ问题进行评估的，DTLZ问题通常用于评估多目标进化算法的质量（表1）。In （ Slim and Rituparna ， 2016 ） ， Deb and Jain. 提 出 了NSGA-III算法，该算法与NSGA-II算法相似，但在选择机制上有所改变。因为它侧重于那些不受人口支配但接近所提供的一组参考点的成员 。 NSGA-III 适 用 于 具 有 2 到 15 个 目 标 的 多 目 的 问 题 （ 参 见（ Kalyanmoy 和 Fellow ， 2013 ） 和 （ Haitham 和 Kalyanmoy ，2017）。3. 背景3.1. 优化问题优化问题定义为：研究（决策）空间：由决策变量所取的不同值一个或多个被称为目标的函数，要优化（最小化或最大化）。● 一系列需要遵守的限制问题的最优解是在搜索空间中找出最能满足目标函数的点或结果被称为最优或最优值（Mahdi，2007）。优化问题可以分为两类;当一个解决方案与单个值相关联时，我们称之为单目标问题;当它与多个值相关联时，我们称之为多目标（或多标准）问题（Layeb，2010）。3.2. 单目标优化当只给定一个目标（准则）时，优化问题是单目标的。在这种情况下，最优解为明确定义;它是具有最佳成本（最小，最大）的一个（Mahdi，2007）。3.3. 多目标优化真正的问题并不总是那么“简单”。有时我们需要为同一个问题定义几个要优化的目标。多目标问题的特殊性在于其解之间缺乏全序关系，在这种情况下，最优或高质量的解决方案不再是一个单一的，而是一组解决方案之间的不同目标进行优化妥协。因此，最著名的和最全面的顺序关系是帕累托意义上的支配关系。最佳妥协的集合被称为帕累托前沿，妥协表面或有效解决方案集（Mahdi，2007）。定义1. 多目标优化问题。具有多个目标的优化问题可以由以下程序表示：优化F（S）=（f1（S），f2（S）. fp（S））。当S2O和p≥ 2时.S：解向量（x 1. x n）的维数n的空间，表示-发送决策变量xi的实例。O：表示关于等式、不等式和显式边界的一组约束CF（f1，f2.. . fp）：是要优化的目标函数向量，p表示目标的数量。定义2. 支配地位y domine z当且仅当6i [1.. n] yi zi和$i [ 1..（Talbi，2000年）。定义3. 帕累托最优。一个x*2 C解是帕累托最优的，当且仅当无×2C解使得F（x）优于F（x*）.（见图。第一章定义4. 妥协的表面。通过基于帕累托支配原则的排序获得的解形成所谓的妥协表面（或帕累托前沿）。表1对上述相关工作进行了总结。文章优化方法目标限制Jena，Jena（2015）嵌套粒子群算法优化能源和处理时间与经典算法- 必须增加更多的目标。Shekhar和Mala（Shekhar，2014）增强型遗传算法最小化运行时间和平衡负载资源- 必须增加更多的目标来评估绩效。Zuo等人（Zuo等人，（2015年）一种改进的多目标蚁群优化算法成本、完工时间、资源利用率和时间期限。- 该方法仍然落入局部最优。- 与传统方法进行对比研究。Naik等人（Naik等人， 2019年度）响应&时间、成本、能耗。更快的收敛可能导致过早收敛。Amol等人（Adamuthe等人， 2013年度）Zhou等人（Zhou等人， 2020年）最大化利润，最大化负载平衡和最小化资源浪费。MGGS总完成时间、平均响应时间和QoS参数多样性不能保持两个以上的目标。与传统方法进行对比研究。Alkayal等人（Alkayal等人，（2016年）基于一种新的排序策略的多目标粒子群算法。期望完成时间（ECT）、任务执行成本（TEC）和虚拟机处理缺少资源利用率和负载平衡的影响●●L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7518Fig. 1.最优帕累托解的精确集合（Talbi，2000）。操作员Pt。随后，Pt和Qt被合并以形成大小为2N个个体的新群体Rt 由于这些个体将根据不同战线（F1，F2）的帕累托优势进行排序。. ，Fn）。然后，通过从第一前沿F1开始选择前沿直到群体St的大小变得等于N或第一次大于N来构造新的群体St假设最后一个接受的级别是第l个级别。因此，所有水平（l +1）的解都被拒绝。在大多数情况下，最后一个前F1部分被接受。在这种情况下，只选择最大化第l个前沿的多样性的解决方案。这是通过计算高效但近似的小生境保持算子来实现的，该算子将每个最后一级成员的拥挤距离计算为两个相邻解之间的客观归一化距离的总和。因此，最分散的解决方案（具有更大的拥挤距离）被添加，直到人口Pt +1完成（Kalyanmoy和研究员，2013）。图二. 多目标优化方法的分类（Elmir，2017）。3.4. 多目标优化方法图2显示了不同的多目标分类方法，更多细节请访问（Elmir，2017）。在我们的工作中，我们感兴趣的近似方法，特别是Metabolistics的，往往是灵感的优化机制，在自然界中遇到的。它们提供了通用的解决方案，使它们能够潜在地应用于所有问题。元语言学的几种分类方法已被提出。因此，最突出的是两类：基于单一解决方案的解决方案和基于解决方案群体的解决方案（Mahdi，2007）。具体而言，我们感兴趣的遗传算法的Pareto方法，Metacallistics方法为基础的人口的解决方案。3.5. NSGA-III：非支配排序遗传算法IIIDeb和Jain（Slim和Rituparna，2016）提出了NSGA-III，它与NSGA-II算法相似，但其选择机制有所变化。由于NSGAIII算法是对NSGAII算法的改进，我们首先对NSGA-II算法进行了简要的描述3.5.1. NSGA Ⅱ算法产生了一个含有N个个体的随机亲本群体Pt.重复以下步骤，直到满足终止条件。首先，该算法通过创建具有通过应用遗传算法获得的N个个体的后代群体Qt开始。3.5.1.1. NSGA-III工作流程。如前所述，NSGA-III与NSGAII相似，但在图3中其选择机制有一些变化（从13到18）; NSGAII的选择机制是一种拥挤距离度量，对于许多客观问题来说表现不佳。因此，通过尊重所提供的参考点对St中的成员进行更系统的分析来修改NSGA-III中的选择机制（Yuan等人，2014年）。NSGA-III使用一组预定义的参考点来确保获得的解决方案的多样性。然而，所选择的参考点可以以结构化的方式预定义或者由用户优先提供（为了获得更多细节，参见（Kalyanmoy和2013年）。NSGA III的选择机制如下：它首先对群体成员和给定的参考点进行归一化，使所有目标向量和参考点都具有比例值。接下来，将计算St中的解与连接理想点和参考点的每条参考线之间的垂直距离（d（））。因此，St的每个个体与具有最小垂直距离的参考点相关联。接下来，使用保守的利基策略来选择与Pt + 1中代表性最低的基准相关的FL成员（Slim和 Rituparna，2016）。第四节详细介绍了这一进程图3解释了NSGAIII算法的工作原理。4. 该方法在本研究中，我们将使用第三代多目标启发式优化方法，这是非支配的L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7519图3.第三章。NSGAIII算法的工作过程（Haitham和Kalyanmoy，2017）。排序遗传算法（NSGA-III），基于参考点的多目标NSGA-II。然而，我们选择的原因是：NSGA-III在涉及3至15个目标的几个问题此外，众所周知，它能够找到良好收敛和多样化的解决方案，因为它不需要任 何 额 外 的 参 数 （ Slim 和 Rituparna ， 2016; Haitham 和Kalyanmoy，2017; Ibrahim等人， 2016年），以及据我们所知它不习惯于云任务调度。我们的工作目标是在云中的一组可用VM上调度一组用户任务，以最大限度地减少运行时间，能耗和成本。图 4给出了系统的体系结构。1. 云客户端：客户端将向云服务提供商发送一组请求（任务），以通过互联网请求服务。2. 代理：代表客户和云提供商之间的中间实体;这是调度发生的地方。3. 任务列表：表示客户向云服务提供商发送的所有请求。4. VM列表：表示云服务器中可用的所有虚拟机。5. NSGAIII处理虚拟机/任务6. 将任务分配给VM：这是代理应用最佳解决方案并将每个任务分配给特定VM的最后一步。7. 数据中心：是执行任务的中心，一旦完成，结果将直接发送到客户端。4.1.1. 建模阶段见图4。 系统架构。4.1. 基于多特征选择的NSGA-III算法一个新的改进的NSGA-III使用多个功能选择的任务分配在云计算（见图。（5）基于两个主要阶段。1. 用户请求由分配给每个VM的任务集定义。因此，它由列表的列表表示，或者第一个表示VM，第二个表示cloudlet。此外，个体（解决方案）中的基因将代表与VM相关的任务（见图1）。 6）。L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7520图五、使用参考点选择任务的NSGAIII算法2. 人口是一组解决方案（个人）Pt由一个大小为N的列表初始种群的个体将随机生成。而尺寸N由用户选择（见图1）。 7）。3. 参考点在种群初始化后，我们将定义所有的参考点，这将确保所获得的解的多样性。这些点的数量是根据对象M和划分数量P计算的。所选择的参考点可以以结构化的方式预定义，或者优选地预先定义。图7.第一次会议。初始群体的组织结构图见图6。代表一个人。由用户提供。如果它们是由用户提供的，它们将被归一化，然后分布在一个超平面上。在我们的研究中，我们使用了10个参考点，用于多个分割（p =3）和多个目标（M = 3），这些点在顶点（1.0，0），（0.1.0），（0.0.1）的归一化超平面（三角形）上创建4.1.2. 演化阶段在本小节中，我们介绍了进化阶段的主要阶段1. 对个人个体的评估是通过一个称为目标或适应度函数的函数完成的，该函数的作用是为每个个体分配一个适应值，该适应值将具有来自我们系统中施加的目标的适应度值（最小化运行时间，最小化能耗和最小化成本）。L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7521时间：是任务运行所需的时间。成本：是在虚拟机上执行任务的总价格能耗：是数据中心在运行解决方案时消耗的能源。2. 选择在这一步中，我们将选择N/2个个体，他们将成为新种群的父母，我们将使用均匀选择，其中包括随机选择个体，而不需要适应度值的干预。3. 交叉是确保个体多样化概念的操作者，其操作如下：选择两个人。在两个个体的代表性上选择一个分界点。通过交叉位于父交叉点之后的两个部分来生成两个子。4. 突变我们随机选择两个虚拟机，并以概率Pm在选定的个体中，我们交换这两个虚拟机的任务列表5. 个人分类在多目标优化中，在评价之后，我们必须根据个体的优势对目标函数进行分类，然后建立Pareto前沿（F1，F2... Fn）（见图 8）。6. 更换通过对Pt上遗传算子的选择和应用，得到一个新的群体Qt，它将与旧的Pt合并，形成一个大小为2N的群体Rt，后者将被评估和分类为一组前沿，并且，这些前沿中的每一个都被添加到群体St中，直到|St|≥N。如果St=|N|我们使Pt+1=St。否则，NSGAIII选择使用预定义的参考点来构造Pt+ 1（参见图9）。6.1. 正常化在此阶段，每个个体的目标在0和1之间进行标准化，因此个体将分布在三个轴（1，0，0）（0，1，0）（0，01）的超平面。图10显示了原始NSGAIII论文的归一化过程（参见Kalyanmoy和Fellow，2013）。在对原始论文（Kalyanmoy and Fellow，2013）中提到的规范化过程进行深入而精确的理论研究后，我们发现它可能会遇到影响NSGAIII有效性的问题。见图8。 个人分类，帕累托前沿。i. 图10中的红框显示了在计算极值点的方法和归一化目标的方法中可能出现的问题的位置。第一种情况出现在极值点重复，从而影响截距的计算（不可能构建单个超平面）。第二种情况在于目标本身的归一化，其中在某些情况下归一化值将超过值1。ii. 为了验证这些问题的真实存在，我们将实现规范化过程并对其进行测试。6.2. 协会在标准化每个目标之后，我们必须计算每个参考点和理想点之间的参考线，然后我们将计算St的每个标准化个体之间的距离以及参考线（垂直距离），最后，其线最接近群体成员的参考点将与它相关联（图10）。 11）。6.3. 小生境见图9。 更换过程。●●●●●●●●L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7522见图10。正常化进程。见图11。 关联过程。在这种方法中，我们将使用关联方法获得的结果来选择最后一个前沿的k个图12示出了小生境过程，重复该过程直到Pt+1=Pt。p：与每个参考点相关联的总体的成员数Pt+1 = St/ Flpj：与参考点j相关联的总体的成员数Pt+1 = St/ FlJmin：具有最小p的参考点的集合。|j：与参考点j相关联的前构件F1。|j: the front members F lwhichare associated with the refer- ence point j.S：p（s）=j，s Fl：F l中距离最短的成员垂直于参考线。7终止标准只要不满足作为预定义的代数的停止标准，算法就保持功能。最优解是位于第一前沿平衡，在这个意义上说，没有任何改善可以在一个目标，而不降低至少另一个目标。当NSGAIII算法的过程结束时，我们采取位于第一Pareto前沿的最后一代中获得的最佳解，最后，我们将每个任务列表分配给相应的VM。4.2. NSGAIII的实施4.2.1. 的主要算法在实现所提出的架构（图。 4）在Eclipse环境下，用Java语言实现了Pareto前沿算法、置换算法（归一化、关联、小生境）等主要算法。● 快速非支配排序（Pareto front）。在算法1中，我们定义了第一前沿（最优解）并将它们存储在一个名为“NotDominatedSol”的列表中，其他解（支配解）存储在一个名为“DominatedSol”的列表中。在算法2中，我们创建了一个名为“Front”的列表列表来存储不同的Pareto前沿。首先，我们添加了非支配解作为第一个前沿（F0）;然后我们从支配解列表中识别出第二个前沿（成员），并将其添加到前沿列表中作为（F1），依此类推，直到最后一个前沿。然而，在识别前端成员之后，我们将它们从支配列表中删除。算法1 NotDominatedSolution（）1：对于p（pPopulation）中的每个个体，执行2：对于q（qPopulation）中的每个个体，执行3：如果q支配p，则4：计数递增15：如果6：结束锻造7：如果count = 0，则8：将p添加到NotDominatedSol//非劣势解列表。9：其他10：将p添加到DominatedSol//一个劣势解列表。11：如果12：结束见图12。 小生境过程。L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7523←算法2前（非主导溶胶，主导溶胶）1：将NotDominatedSol添加到第一前（F0）2：i13：whileDominatedSol.Size（）4：对于p（pPopulation）中的每个个体，执行5：对于q（qPopulation）中的每个个体，执行6：如果q支配p，则7：计数递增18：如果结束9：结束10：如果count = 0，则11：将P添加到前面（Fi）12：将P添加到列表13：如果14：结束15：iflist.size（）16：从“DominatedSol”列表中删除列表中存储的个人17：如果18：i i+1第19章：结束NSGAIII的优势在于它能够确保使用一套参考点和一种选择替换阶段缺失个体的机制获得的解决方案的多样性因此，本文提出了一种基于三种归一化方法的改进NSGAIII.● 人口成员实施归一化后，发现假设中极值点的计算存在问题，验证了归一化方法的正确性。算法3归一化（Stfit）1：计算理想点的最小Z2：对于每个个体fi（fi Stfit） do//具有目标的Stfit3：对于每个目标m do//m目标数4：f5：结束6：结束锻造7：计算极值点8：计算截距9：对于每个个体fi（fi Stfit），10：对于每个目标m做11：fi.m = f'i13：结束问题1. 如前所述，极端点重复的情况可能会出现，并导致截距（结果我们得到Nan =为解决此问题，Tsung-Che Chiang提出了一种解决方案，即在（ns-ga 3cpp版本1.0）中添加一项旨在验证计算截距方法中是否存在重复的该解决方案的详细步骤如下：算法4 Cal_Intercepts（极值点）1：重复= Is_duplicate（extreme_points）//极值点2：如果重复，则3：对于每个目标m do4：am = extreme_points（m）.m5：//极值点的每个对角点成为截距am6：结束锻造7：其他8：List x = Gaussian-Elimination（）//找到超平面方程9：//找到被拦截的10：对于每个目标m do11：am =（1/xm）;//am =interceptm 12：end for13：如果该方案实施后，解决了重复点的问题，并计算了截距。问题2. 解决第一个问题后遇到的第二个问题是归一化方程;在某些情况下，目标值超过值 1。建议的解决方案：对整个归一化过程的测量监控使我们能够发现问题的原因，以及截距值am必须大于目标值fm。更确切地说，问题出现在极端点重复或截距计算为负的情况下。由以上所述，我们得出结论，蒋提出的解，帮助我们计算截距，而不是理想的解决方案。因此，我们必须寻找另一种更有效的方法。1. 我们将选择所有极值点的每个目标的最大值，而不是选择极值点的对角线作为截距am算法5 DiagonalExtreme（）1：如果重复，则2：对于每个目标m do3：Max = findMax（extreme_points（0）.m，extreme_points（1）.m，extreme_points（2）.m）4：am = Max5：结束6：如果这个方案实施后，问题仍然存在，因此，这不是所寻求的解决办法。2. 我们实验过的另一个解决方案是给出比较低值中的值1大的值。测试该解决方案仅用于验证与参考点相比解决方案分布的多样化，然而，所获得的结果与寻求的目标相去甚远（参见图13），这使我们得出结论，问题在于重复情况下截距值的选择。L. Imene，S. Sihem，K. Okba等人沙特国王大学学报75243. 第三种解决方案是Yuan等人的解决方案（Yuan等人，2015）谁提议创建一个FindMaxObjectives方法来查找● 关联算法在当前解决方案中的目标的最大值然后在端点重复或截距为负的情况下，用这些值替换截距。算法6 FindMaxObjectives（pop）1：对于每个Objectives m do2：Max_point（m）= pop（0）.m3：对于pop中的每个i，4：Max_point（m）= Max（Max_point（m），pop（i）.m）5：结束6：结束锻造7：return Max_point算法7 Cal_Intercepts（ExtPoits）1：Duplicate = Is_duplicate（extreme_points）2：if！那就复制吧3：List x = guassianElimination//找到超平面方程4：对于每个目标i 3 do//找到截距<5：interceptes.add（1/xi）6：如果xi 0，则<7：负截距=真; 8：中断9：如果10：结束11：如果12：如果重复或负截距，则13：max_objs =FindMaxObjectives（pop）14：对于每个目标m，15：截取（m）= max_objs（m）16：结束17：如果这种解决方案使我们能够解决问题，并使正常化功能正常工作。因此，我们上面提到的问题并没有出现在NSGAIII的原始论文算法8关联运算1：对于（pi Stfit）中的每个单独的pi，2：Min_rp =-1;3：Min_dist = Double.Max_Value4：对于（ri referencepoints）中的每个参考点ri，执行5：计算ri和pi之间的距离6：如果距离min dist，则Min_dist =距离; Min_rp = ri;7：如果8：结束9：将pi及其附近的ri添加到关联列表10：结束● 小生境算法算法9小生境（St，K，关联，ptsize）1：k02：创建p3：while k K do<4：计算Jmin;5：计算j;6：计算Ij; 7：如果Ij = 0，则8：如果pj = 0，则9：将具有最小距离的前Fl的解加到Pt +110：其他11：选择F12的随机个体：如果13：pj = pj + 1;14：移除Fl的s 15：k = k +116：其他17：删除参考点j 18：如果第19章：结束(see 图 14）。图十三.参考点，归一化后的人口。L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7525见图14。 表示参考点和归一化后的总体，参考点：红色，St：绿色。表3算法的实验参数表2CloudSim配置值。参数值类型参数值人口规模10、50、100、200、500、800、1000数据中心DC数量1迭代次数十，一百，五百，一千每个DC10突变概率0.01主机的速度。20000穿越概率0.9每个主机1VMs任务虚拟机总数虚拟机任务总数任务的规模30100010050004.2.2. 个人评估个体评估通过适应度函数完成，该适应度函数计算每个个体的运行时间、成本和能耗在下文中，我们将解释计算个人这三个值的方法。(a) TE = Max（单个i的每个VM的所有任务的TE之和）。PE数量(b) 成本对于每个分配的虚拟机，分配成本为每3600 1美元。成本=每个VM针对单个i的成本之和表4第一代（前三列）和最后一代（其余列）的最优解（第一前）。种群规模= 100代数= 100TE（s）费用（美元）CE（Kw）TE（s）费用（美元）CE（Kw）TE（s）费用（美元）CE（Kw）32.9800.1830.17524.4600.1560.17518.8790.1400.18321.5930.1780.17515.5600.1580.17516.6770.1430.17520.7830.1710.17515.5600.1560.17516.6770.1430.17618.740.1550.17516.2170.1550.17516.2170.1440.17522.3020.1480.18015.5600.1540.17518.9580.1410.17530.4820.1720.17518.8790.1430.17515.7690.1470.23119.7440.1530.17516.9890.1470.17515.7690.1480.18020.6420.1470.23716.0980.1470.17516.3360.1430.21619.5250.1520.20218.9580.1410.17518.7300.1410.17517.150.1560.17916.40.1440.17516.5860.1430.18019.8420.1520.18515.7690.1510.17516.6770.1430.18017.5790.1570.17916.5860.1440.17516.3360.1430.17620.1130.1510.17818.9580.1420.17518.9580.1400.17619.3620.1530.22518.8790.1400.17516.6770.1420.18320.3890.1490.18015.9960.1470.17515.7690.1500.17519.8420.1480.19515.9960.1450.17715.5600.1490.21024.2160.1450.22516.0980.1440.17516.6770.1420.19224.2160.1470.21416.8200.1420.18216.6770.1420.20519.7910.1500.24118.7300.1410.17515.5600.1490.17618.9210.1550.19816.5860.1430.17515.7690.1480.21120.3890.1470.24418.7300.1400.19019.1360.1510.23816.2170.1440.181L. Imene，S. Sihem，K. Okba等人沙特国王大学学报7526(c)至于能源消耗，我们使用线性功率模型，其计算能源如下：消耗的功率= Pmin+（Pmax-Pmin）* 利用率。其中Pmin是空闲状态下消耗的最小功率，Pmax是最高负载下消耗的最大功率。用法介于0和1之间。5. 实验结果我们的系统是在Intel（R）CORETM i3微型便携式环境（1.70 GHzCPU，4 GB RAM）Microsoft Win-2007下开发的.我们提出了用于在云中调度任务的NSGAIII算法的实验结果。实验的目的是证明和评估使用不同的参数的算法的性能，除了与另一种算法的比较研究。我们还将介绍用于每个数据中心、VM、Cloudlets、处理元素（PE）的参数的CloudSim配置（见下表）。对于我们的实验，我们使用：表2中提到的云参数。下表参数为NSGAIII和NSGAII遗传算法（表3）。5.1. 实验1在该实验中，我们通过首先比较单次运行的结果（运行的第一代和最后一代结果）来评估NSGAIII算法的结果，以验证第一代和最后一代之间的