没有合适的资源?快使用搜索试试~ 我知道了~
基于多目标混合细菌觅食算法在云计算中的任务调度
可在www.sciencedirect.com在线获取ScienceDirectFutureComputing and Informatics Journal 3(2018)210e230http://www.journals.elsevier.com/future-computing-and-informatics-journal/基于多目标混合细菌觅食算法Sobhanayak Srichandana,*,Turuk Ashok Kumarb,Sahoo Bibhudattaba印度奥里萨邦布巴内斯瓦尔理工学院计算机科学系b印度奥里萨邦NIT Rourkela计算机科学系接收日期:2017年10月10日;修订日期:2018年1月19日;接受日期:2018年3月7日在线发售2018年摘要云计算是通过互联网提供计算服务。云服务允许个人和其他企业组织使用由第三方或其他人在远程位置管理的数据。大多数云提供商都在服务水平协议(SLA)定义的约束下支持服务。SLA由提供商承诺的不同服务质量(QoS)规则组成。云环境可以分为两种类型:计算云和数据云。在云计算环境中,任务调度对于保证服务质量和服务水平至关重要。高效的任务调度是有效利用云计算潜力的主要步骤之一本文探讨了使用混合方法的任务调度算法,它结合了两个最广泛使用的生物启发式算法,遗传算法(GAs)和细菌觅食(BF)算法在计算云的理想特性。本文的主要贡献有两个方面。首先,调度算法最大限度地减少了最大完工时间,其次,它减少了能源消耗,经济和生态的角度。实验结果表明,该算法的性能优于其他算法的收敛性,稳定性和解决方案的多样性。Copyright© 2018埃及未来大学计算机与信息技术学院由爱思唯尔公司制作和主持这是CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。关键词:云计算;资源分配; Pareto解;细菌觅食;遗传算法1. 介绍随着互联网接入和大数据在数量、速度和种类上的普遍增长,云计算在工业、学术界和社会中变得越来越普及。云计算由分布式计算、网格计算、效用计算和自主计算组成[1]。云计算提供了高性能和高可扩展性的按需计算和存储服务。几种计算范例已经承诺提供这种效用计算。* 通讯作者。电子邮件地址:srichandan@iiit-bh.ac.in(S.Srichandan),nitrkl.ac.in(T.Ashok Kumar),bdsahu@nitrkl.ac.in(S. Bibhudatta)。同行审查,由埃及未来大学计算机和信息技术系负责。云计算就是这样一种可靠的计算范例。然而,云数据中心能耗的不断上升已经成为一个突出的问题。任务调度是提高云计算整体性能的重要环节。传统的监控和管理机制是为企业环境,特别是统一环境而设计的。然而,大规模、异构的资源调配给多数据中心的管理和监控机制带来了严峻的挑战。 据我们所知,这是第一篇在异构系统的IaaS云中使用多目标混合细菌觅食算法解决调度问题的论文。近几年问题的任务调度在分布式环境中的应用引起了研究者的注意。任务调度被认为是一个关键问题,https://doi.org/10.1016/j.fcij.2018.03.0042314-7288/Copyright© 2018埃及未来大学计算机与信息技术学院。Elsevier B. V.制作和托管这是CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230211通过考虑不同的因素,如完成时间,执行所有用户任务的总成本,资源利用率,功耗和容错能力,来评估云计算环境。优先级约束的并行应用程序在求解时间和能耗之间寻求最佳折衷是一个双目标优化问题。这个问题的解决方案是一组帕累托点。帕累托解是指一个目标的改善只能伴随着至少另一个目标的恶化而发生的解。因此,双目标问题的解决方案不是问题的唯一解决方案,而是一组(可能是无限的)帕累托点。任务调度已被证明是一个NP完全问题[2,3]。云计算不仅有助于各种各样的用途,而且还为应用程序提供了一个虚拟化的条件,使其以高效和最小的努力方式保持运行[4]。云数据中心通常由一大群服务器组成连接到互联网。云数据中心需要任务调度器来安排任务执行。任务调度器必须有效地利用云数据中心的资源来执行任务。调度算法的性能问题包括最大完工时间和能量消耗。一个好的调度器可以使用更少的资源和时间来完成任务的执行。使用更少的资源意味着消耗更少的能源最小化能耗和最大完工时间是构建大规模云的主要问题之一人们对云计算的不同前景进行了研究,以充分利用云计算的多样性,即针对特定任务、具有实时截止期的容错任务或依赖或独立等节能任务存在与资源供应和任务调度相关联的某些固有问题优化目标一旦在设计时设置大量的任务调度和资源提供策略和算法,虽然有不同的优化目标,往往有助于一些广泛的功能机制,并采用类似的软件工程框架执行。然而,添加新的调度能力需要对每个调度算法一次一个地进行,这不仅单调而且成本高,并且导致错误。自然选择倾向于通过寻找、处理和摄取食物的方法淘汰那些觅食策略不佳的动物,并有利于那些有成功觅食策略的动物的基因繁殖,因为它们更有可能获得繁殖成功。经过许多代之后,糟糕的觅食策略要么被淘汰,要么被重新构建成好的策略。由于觅食生物体/动物采取行动以最大化每单位时间花费觅食所利用的能量,因此考虑到由其自身生理学呈现的所有约束,诸如感测和认知能力以及环境参数(例如,猎物的密度,来自捕食者的风险,搜索区域),自然进化可能导致优化。 本质上,这个想法可以应用于复杂的优化问题。优化问题搜索空间可以被建模为一个社会觅食环境,其中参数组协作通信,以找到困难工程问题的解决方案[5]。作者在Ref.[6]通过引入云计算环境中任务调度的几种变体,提供了关于GA的详细思想他介绍了一种通过修改遗传算法来解决任务调度问题的算法,其中初始种群是由最大e最小的方法来产生的,以获得更优的结果在“最大完工时间”。作者在Ref.[7]提出了一种考虑每个不同工作负载的执行时间的资源调度算法,但最重要的是,整体性能也基于工作负载的类型,即具有不同QoS要求(异构工作负载)和具有相似QoS要求(同构工作负载)。为了并行地完成任务执行,必须回答以下问题:(1)如何将资源分配给任务;(2)由于任务具有数据依赖性,云应该以什么顺序执行任务;(3)当物理机(PM)设置、完成或切换任务时,如何调度开销。资源分配和调度可以解决这三个问题。资源分配和任务调度已经在高性能计算[8]和嵌入式系统[9]中进行了研究。然而,云[10]内的自主特性和资源异构性以及PM实现需要不同的算法来进行IaaS云计算中的资源分配和任务调度,特别是在联合的异构多云系统中。虽然已有大量的文章分析了BFA作为单目标优化器的觅食行为和自适应特性,但迄今为止,对多目标混合BFA算法的分析尚不多见。本文提出了一种新的多目标混合细菌觅食算法(MHBFA),该算法由遗传算法和多目标细菌觅食算法组成MHBFA算法的主要组成部分是遗传算法和多目标优化BFA算法的选择,变异和交叉[11e13],由Passino于2002年提出,是自然启发优化算法家族BFA是一种相对较新的群体智能算法,其灵感来自于大肠杆菌的觅食行为。大肠杆菌)。在E. 大肠杆菌进行通信。我们考虑组合优化问题,制定提出的任务调度问题的能源和最大完工时间最小化。本文的主要贡献是:提出了一种适用于异构云环境的调度算法。本文提出了一种混合细菌觅食算法来解决多目标优化问题,即最小化生产周期和能耗。●●212S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230¼将遗传算法中的变异和交叉技术应用于细菌觅食算法中,以获得局部和全局最优解。我 们 验 证 了 所 提 出 的 多 目 标 混 合 细 菌 觅 食 算 法(MHBFA)的有效性,特别是它在解决方案的多样性和质量,收敛性和稳定性的作用。将遗传算法中的变异和交叉技术应用于细菌觅食算法中,以获得局部和全局最优解。我们验证了所提出的多目标混合细菌觅食算法(MHBFA)的有效性,特别是它在解决方案的多样性和质量,收敛性和稳定性的作用。采用显著性检验对所得结果与GA、PSO、BFA的结果进行统计学验证。本文其余部分的结构如下。在第二节中,描述了任务调度算法的框架。资源调度的系统模型和定义已在第3节中介绍。第4节描述了问题公式化。第五节介绍了多目标方法,简要介绍了基于BFA的多目标方法。第7节详细介绍了基于BFA的拟议战略。第8节给出了模拟结果。结论和未来的工作已在第9节中提出。2. 任务调度算法为了设计和提供IaaS云中工程实施的调度管理框架,本节介绍了云计算资源管理中的一个重要方面,即,任务调度云计算的目标是提供一个最优的任务调度,为用户和整个云系统提供最优的运行时间,同时提高QoS和负载均衡。在云计算环境中,负载均衡和任务调度是紧密联系在一起的。任务调度是为了实现任务和资源的最佳匹配[14]。为了设计和提供IaaS云环境下工程实施的调度管理框架,本节介绍了云计算资源管理中的一个重要方面,任务调度云主要是为用户提供服务质量(QoS)。任务调度算法的主要目标是实现两个主要目标,即任务调度有助于最小化完工时间和能量。现在我们简要描述整个能量感知任务调度框架。该框架由四个主要组件组成:用户门户、信息服务、任务调度器和具有物理机(PM)的云数据中心。用户门户为用户提交任务单元提供了接口。任务单元进一步划分为要在PM中执行的小任务。信息服务保存资源利用率的详细信息和其他日志信息,以帮助调度程序将任务调度给数据中心中的PM调度程序接受任务单元并使用信息服务在云数据中心中选择适当的PM。在任务单元完成其执行之后,资源将被发送回信息服务以进行另一调度。3. 系统模型和定义在这项工作中要考虑的云系统模型可以描述如下[15]。我们描述了不同的模型和定义与本文中制定的问题。在本文中,我们假设云调度环境是高度异构的,并且物理机具有不确定的利用率信息。 我们设计了多个目标,以最大限度地减少能源消耗和最大完工时间。在最优条件下,求出了多目标优化的Pareto集3.1. 定义云服务提供商保存有关用户请求到达和数据中心PM可用利用率的详细信息。完整的场景可以通过使用直接的非循环图来表示,其中呈现了用户请求。这里捕获任务的属性、任务单元关系和任务单元到达我们考虑的任务的基本属性是CPU限制的任务,它的大部分时间都花在计算上,分配有多个处理单元,大RAM大小。而I/O绑定任务仅依赖于连接到机器的外围设备。因此,它可能需要一台具有足够网络带宽和大容量缓冲区的机器。任务单元的一个重要属性是添加输入和输出指令大小以保留PM中可用的资源。任务单元之间可能存在依赖关系。如图2中给出的示例是DAG,其中每个节点表示任务单元及其任务类型,有向线描绘任务之间的依赖关系,并且我们可以添加权重以连接两个任务,边表示流大小。该图可以通过使用如下的5元组来表示:G(TD,TS,D,Mi,Mout)。语义和所有元组的定义如下:定义1. 用户请求(TD):这是由1/n个任务单元组成的用户请求集。定义2. 任务类型(TS):是从1 / m开始的每个单个任务单元的任务类型,其中Tm表示任务单元中的最大任务数量。例如,如果我们有三个任务单元f TD 1; TD 2;TD 3g,则每个任务单元可以具有任务类型T D11/4TS1;1/TS1;mΩ ,TD1/2/2TS2;1/TS2;m和 TD31/2TS3;1/TS3;mΩ。定义3. 任务依赖性(D):它表示TD中任务单元之间的依赖性。设Dij1/4,即TDj使用从TDi获得的数据。否则,Dij¼0。●●S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230213667¼ðÞÞðÞ¼ ð«««««TD iTSi;1TSi;2…730 1062TD1TD2TD37Fig. 1.云架构。下午2 点1 下午2点...下午3点TD1 0 1 0D¼TD1TS1; 1TS1; 2…3; 34TD2 1 0 05ES 1/4 TDTSTS.TS7TDij6422; 12; 22;j75定义4.输入数据Min:表示输入数据任务单元的大小。定义5. 输出数据Mout:它表示输出任务单元的数据大小我们假设资源池是所述资源可以是异构的,并且所述资源可以是物理机器,或者远程的服务器或PC构成数据中心。相同的资源具有不同的配置。下一结果是不同的,即使他们处理同一类型的任务通过改变网络带宽和物理机容量,可以概括总体异构性特征。PM的容量给出了执行任务中存在的数据所需的最小时间,该任务在CPU容量和可用内存大小之间建立了直接网络带宽有助于提高两台物理机之间数据通信的速率和成本。但是,它不区分任务的类型,而是处理唯一的数据流。资源信息M由六个元组组成,即M(PS,CP,R,CE,N_bw,E_com)。每个元组的定义如下。定义6. 物理 机器 (PS): 让 PS PM1; PM2; PM3;定义7. 计算能力(ES):假设ES是一个矩阵,它给出了PM的计算能力。任务单元类型i在物理机PMj上的执行时间表示为ESij。PMj的平均功率表示为ESavg;j,我们通过计算矩阵ESj的列中元素的平均值来计算ESavg;j值。详细说明如下:214S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230ðÞðÞð Þ ¼定义8.PM(R)中的RAM:它是可用的RAM(内存)大小每个PM。定义9. 计算能源(CE):CE这是矩阵它给出了执行任务单元的消耗率,CE ij表示计算能量,CEij表示计算能量消耗的能量。PMj每单位时间每单位数据执行i个定义10.带宽体重:Nbw表示频带-PM之间的宽度,以及PMi到PM i之间的数据传输速率。PMj被表示为Nbw;i j。定义11. 通信能源Ecom:Ecom表示用于通信的能量消耗率,即,在每单位时间每单位数据从物理机PMi到PMj的数据传输期间消耗的能量表示为Ecomi,i,j。定义12. 映射变量(c):c是映射任务单元和PM的映射变量。 ci j表示将任务单元i分配给待执行的PMj3.2. 模型本节重点介绍了各种模型和几个定义,这些模型和定义是问题形成的基础。在云计算资源调度优化中,我们考虑的两个最重要的目标是最小化最大完工时间和能耗。这两个目标的矛盾性质产生于平行性和异质性。前者指出,制造跨度是以严格的PM间数据传输为代价的S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230215ð ÞX2P¼ ¼ ð Þ任务,它直接影响数据中心的总能耗,后者表示,自然界中速度更快的资源不一定是最便宜的。3.2.1. Makespan模型我们将makespan定义为从用户提交请求到完成最后一个任务单元所花费的时间。它包括处理时间和等待时间。用户请求的处理时间计算如下:将用户请求分解为任务单元,然后应用拓扑排序以确保每个任务单元只能依赖于具有较小索引的任务单元总处理时间实际上与任务单元TDi的完成时间相同。我们通过将当前任务单元的执行时间与在当前PM到达所有所需数据所花费的时间相加来计算每个任务单元TDi的完成时间CTi考虑图2中描绘的DAG作为示例。 我们通过将任务单元和TD8的完成时间与TD5、TD6和TD7的处理时间相加来计算任务单元TD8的完成时间(即,任务单元TD8的所有输入数据将到达的时间)。上述信息可以数学建模如下:Ctagitagitagitagitagi等待时间最终将与处理时间相加,因为当某些PM过载或分配了更多任务单元时,多线程的级别并不太高。对该过程的深入分析表明,数据中心中存在的PM之间的负载平衡是任务调度的基本属性。但是,这是不可能的,直到我们有适当的信息之间的负载分布的PM的数据中心。即使这些信息是可测量的,但云代理或资源提供商也不会使其公开访问。为了承担更多的任务,资源提供者倾向于理解过程。正是由于上述原因,我们不得不寻找其解决之道。由于我们有关于尚未分配的任务的先验信息,即使我们可能不知道关于已经分配的任务的信息,这也足以预测不同PM上的负载。这是一种有效的方法,但似乎是限制性的。在这个提议中,我们假设每个PM的负载分布比平均计算能力和负载分布[16]。我们将负载平衡定义如下:nLB¼Ai-B i21/1其中,n是数据中心中PM的数量其中,Taux是从所有所需任务到达当前任务所需的时间,如下所示:mj¼1 M i;j. 我的天.D×M¼IJAmj¼1 Mi;jð3Þ托最大i-1j1Dij ×CTjN出来BBW;p;q其中,p和q定义如下:Ri,ECavg;iTex 是执行当前任务所需的时间,表示为BðiÞ¼nRi,EC平均值;ið4Þ如下所示:TexESg;hMi;ici其中g和h定义如下:TDi,hci.CT向量的元素的值可以递归地计算。当忽略等待时间时,我们声明用户请求的最大完工时间CT(n)值,其中n是用户请求的最后一个任务单元。云计算工作在虚拟化的概念上,其中执行硬件抽象。它的工作原理是创建一个虚拟化的环境,每个物理机器都有自己的运行执行环境。这里的场景在用户的脑海中创造了一种错觉,即用户拥有整个CPU、内存和其他硬件附件:但实际上,它只是一个虚拟环境,用户仍然需要将数据从物理内存传输当我们观察到Eq。(1),只有当PM被直接分配给它被分配到的任务单元时,它才成立。从上一篇文章中得出的结论是,多线程的水平不能太高;一般来说,CPU会投入大量的时间,精力在设置开关和页面错误上,更遗憾的是可能会导致thrashing。1/1有一些风险与偏离理想的比率,即一些PM可能会保持忙碌,迫使其他任务进入等待队列很长一段时间,不利地增加了系统的完工时间。因此我们已经假设理想比率被考虑用于初始载荷分布。因此,负载均衡是一个有风险的参数,间接影响系统的完工时间。因此,新的最大完工时间的数学模型如下:CTf<$CTn×eb5其中b是负载平衡因子。B随着数据业务量的增加而增加,并且完工时间也增加,这表明负载分布不均匀的影响。负载均衡对最大完工时间的影响很小,表明数据流量处于空闲状态。3.2.2. 能量模型云中的能量消耗是在用户请求的服务期间参与的单个单元的能量消耗的总和。作者在Ref。[17个]PP216S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230XN¼ ð Þ ¼ ð Þ.Σ≤≤.Σ提出了一个能量模型,指出CPU消耗更多的能量相比,其他设备或硬件参与任务调度过程。CPU能耗取决于资源利用率、电压和频率。特别是CPU,其能耗主要取决于其电压和频率,这意味着只要CPU的电压和频率足够高,因为CPU的工作状态是恒定的。计算和通信过程中消耗的能量可以计算如下:nECCEg;hE com;g;hMi;i61/1其中,g和h定义如下:g/TD i,h/C/TDi。n i-1指定的QoS要求。目前,云数据中心中的任务调度旨在提供高性能,同时满足SLA,而不关注分配PM以最小化能耗和完工时间。云计算中的任务调度是一个NP完全问题[18]。参考文献[17]中的作者提出了一种节能的资源调度算法,该算法降低了运营成本并提供了服务质量。通过虚拟机的调度来实现节能和资源利用。QoS由以每秒百万指令(MIPS)为单位测量的CPU容量所需的资源量、主存储器(RAM)的量以及网络带宽速率来建模。这些资源的不足导致违反SLA。见参考文件[19]作者提出了一种负载共享优化方法,远程和本地云服务之间的问题。 他们的ECE ¼X XDj;iMo;j×E com;bmp;qð7Þ多目标方法 限定 到 优化能源节约,1/1j1bw;pw;q基于Poisson到达的就业率。其中p和q定义如下:c j,qC i最后,总能量消耗的数学表达式是两部分的总和,第一部分是通信能量和计算能量,其由以下等式表示:TE¼ECECE804. 问题公式化从任务调度算法的框架出发,首先分析了任务完成时间与能耗之间的关系,然后制定了任务调度的目标。4.1. 先验分析云操作包括五个阶段:来自用户的请求的到达,促进资源需求的资源探索,资源调度,调度资源以执行用户的请求,服务和过程监控以及最后一个反馈提交。在这些步骤中,第三个步骤在用户请求执行生命周期中的服务质量和总成本中起着至关重要的作用。影响这一阶段的主要因素是最大完工时间和能源消耗。为了探索最大完工时间和能源效率,必须解决三个关键问题。首先,服务器的过度电源循环可能会降低其可靠性。其次,从QoS的角度来看,在动态环境中关闭资源是有风险的。由于工作负载的可变性和积极的整合,一些PM可能无法在峰值负载下获得所需的资源,并且无法满足期望的QoS。第三,确保SLA给云计算环境中的精确应用程序性能管理带来了挑战。所有这些问题都需要有效的调度策略,可以最大限度地减少能源消耗,并在不影响用户的情况下,作者在Refs。[20e22]提出了DVFS启用技术,以最小化分布式系统中的功耗,而忽略性能。从上面的研究中,我们观察到,这是一个权衡,以最大限度地减少完工时间和能源。因此,在拓扑排序时最小化这两个冲突参数以最小化完工时间和能量可以更好地实现为下面讨论的多目标优化问题。4.2. 问题目标在本节中,整个问题被定义并命名为任务调度算法的多目标优化(MOOTS)问题。4.3. 目标函数根据定义和方程。(1)e(8)在前面的部分中,我们的目标定义如下。目的(1):最大限度地减少完工时间最小值CT值n×eb×LB9目标(2):能量最小化(TE)最小值TE100适应度函数m¼aCTBIN×eb×LBTE11其中0a1和0b1是对适应度函数的分量进行优先级排序的权重。<<4.4. 约束考虑以下约束约束条件1. 该约束确定了每个任务单元只能从云数据中心可用的资源池中选择一台物理机。这是如下给出的S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230217×MaxMaxMaxMaxP¼]¼ ðÞIJo;iIi imax我我ci2f1;ci2f1;2;其中n是任务单元,m是每个任务单元的任务数。处理用户任务单元所需的最长时间约束2. 每个任务单元的最大处理时间;使用的箱的总数是最小值(用L * 表示)[23,24]。提案1. 的优化问题描述由方程式(11)是一个NP难问题。证据这个命题可以通过将问题简化为装箱问题[23,24]来容易地证明,装箱问题是一个众所周知的NP难题。仓的数量m等于可用的N个数据中心。的维度CPTSciMi;i≤Tpczh应用j包括两个参数dj和ej。然而,在这方面,我其中TpMax是最大处理时间。eji取决于数据中心i的CPU的频率。通过定义一个变换函数r:RR/R,我们可以将eji变换为ej。此限制仅考虑所有CPU具有相同频率的数据中心。因此,约束条件3. 每个任务单元最大通信时间;fd j;e jx ji 和 通过 定义 1, 它 是 一 装箱i-1。Dij×Mo;jc问题.▫最大值j¼0牛磺酸钠≤Tmaxc≤14℃5. 多目标方法其中,j是任务单元,i是PM的数量,Tc最大通信时间是5.1. 附件和背景约束4. 每个任务单元最大处理能耗;通常,多目标优化问题涉及多个相互冲突的目标。为了获得多目标挑战的解决方案,目标被聚合CETSciCPTSciMi;i≤Epczh15标量函数,并解决了在本文中,我们发现帕累托最优其中Ep是加工能量。这是一个最佳的权衡。详细场景和 局部和全局帕累托最优集差已被约束5. 每个任务单元通信期间的能耗。XJDMN定义如下。在多目标优化问题中,偏序表示两个解是相互关联的.一种方式是,一个目标优于另一个目标,没有人占主导地位。1/1bw;cicj=Ecomicj定义1. 让我们考虑一个多目标的小-其中Ec是沟通的能量。化问题。在这种情况下,我们有m个决策变量和n个目标。约束6. 为了正确利用PM,负载分布应该是某个阈值,在我们的情况下,阈值下限为0,上限如以下等式所示:Pn.uMinimizey<$ff1x;f2x;.; f n xg 18其中x x1;x2; 判定向量a2x被称为支配向量b2x上的decisi,当且仅当n1/1 Mi;i≤Thczk1717在那里,是执行任务的上限阈值di2f1;基于上述关系,我们可以定义非支配解和帕累托最优解。4.5. MHBFA问题定义1. 设L x1;装箱问题是将每个xji分配到一个唯一的bin中,每个bj2B中的数字之和不超过1,使得定义2. 设a2x为任意决策向量。帕累托最优决策向量不能在任何目标中得到改善,而不会导致至少一个其他目标的退化在用我们的术语来说,它们代表着全球最优的解决方案。然而,类似于单目标优化问题,也可能存在局部最优解,其构成非支配优化问题。设置内一某些小区C≤Emaxc ≤16 Ω218S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230这对应于Deb [25]引入的全局和局部帕累托最优集的概念。请注意,全局帕累托最优集不一定包含所有帕累托最优解。如果指的是整个帕累托最优解,只需写“帕累托最优集”。相应的目标向量集表示为“帕累托最优前沿”。为了用BFA求解多目标优化问题,人们提出了一些BFA的变体和混合BFA。作者在Refs。[26e 28]提出了多目标细菌觅食优化(MBFA)。 他们的建议的缺点是陷入了局部最优。因为他们的基本技术来自于BFA。 然而现在很多的处理方法都忽视了一天中多维度处理问题的方法。作者在Refs。[28e31]提出了考虑一维方法的混合HBFA任务调度算法。在所提出的工作中,我们包括多目标优化与健康排序方法和帕累托优势机制之间的集成,其中多目标优化问题的主要目标是获得一个非支配的前沿,这是接近真正的帕累托前沿。6. HBFA原理遗传算法缺乏局部搜索能力,但具有很好的全局搜索能力。细菌觅食(BF)的全局搜索能力较差,局部搜索能力非常高[32e38]。当我们将这两种算法通过选择性地组合某些有利的函数结合起来时,可以得到一个具有最佳局部和全局搜索能力以及更快收敛时间的解。HBF包含GA和BF的所有合并属性[30,39,40]。GBF似乎是BF而不是GA的实现,但它结合了两种算法的特点。文献综述了BF算法与其它算法的杂交,并从理论上验证了所提出算法的有效性。在所有这些文献中,已经观察到HBF保持了一般有效性,并且优化的特征可以应用于许多其他应用中。HBF继承了群集和消除,从BF扩散。我们的目标是使BF具有更强的全局搜索能力,因此我们需要保留HBF的这些特性,并改变那些不支持全局搜索能力的函数。在全球化搜索过程中,淘汰、分散和群集是关键的程序,因此它们一直被保留在程序中。另外两个功能,即,趋化性和繁殖的焦点是转化为全局搜索能力。遗传算法的概念是由Holland在1973年提出的,它是受生物进化的启发而提出的。它是一种模拟自然选择和遗传机制的随机搜索算法。遗传算法用字符串用数字模拟染色体生物个体,通过选择、交叉和变异算子,描述了生物进化的基本过程。适应度函数代表解的质量,通过种群的不断升级可以提高每代的平均适应度,通过适应度函数可以引导种群的进化方向,并在此基础上使最优个体所代表的解逼近全局最优解。7. 调度问题的MHBFA本节提出了MHBFA细菌觅食优化算法来解决云计算中的任务调度问题。在每一步迭代中对目标函数进行估值,从而得到多目标优化问题的较好解。细菌的位置(坐标)表示待优化的参数。用一句简单的话来说,我们可以说细菌代表了任务调度问题的解决方案。我们已经为算法输入生成了许多细菌。对目标函数的细菌进行评估,以获得最小的完工时间和能量。参数在适当的范围内离散化,每一组离散值代表空间坐标中的一个点。这些参数在理想的范围内离散化。这些离散值中的每一个描述空间坐标上的点。在所提出的MHBFA算法中,在每次迭代中,根据溶液质量的测量来评估所有细菌。我们的首要目标是减少完工时间和能源消耗,这是细菌的位置。算法中使用的参数如下:p:搜索图二、任务单元和任务的DAGS. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230219X21 x xP¼51/4fgð Þ表1任务单位及其任务。2x11X12X13…TSi1 TSi2 TSi3 TSi4TD1 TS11 TS12 TS13TD2 TS21 TS22 TS23TD3 TS31 TS32 TS33 TS34升四分之一...xn1xn2xn3…空间; S:种群中细菌的数量;Ci:翻滚时的随机方向;Nc:趋化步骤;将任务TSi分配给PM的可能性。PMj表示为xij。我们从区间[0,1]上的均匀分布中将值分配给l,满足以下条件:Ns:游泳长度;Nre:繁殖步数;Ned:淘汰和扩散事件;Ped:淘汰和扩散概率.7.1. 初始位置生成xi;jXm2½0;1];i2f1;2;xi;j¼1;i2f 1; 2;从图2的DAG导出的任务单元细节如下给出(参见表1)。细菌持有问题域的解决方案,这是与所提出的算法相关联的新颖性。对于所提出的问题,我们得到解的中间表示如下:细菌用两个变量h和l编码,这两个变量h和l表示线性向量,另一个是矩阵。h给出了PM上所有任务的调度顺序。l表示任务的映射j1分配矩阵值保持在0和1之间。当值超过这个范围时,我们将其设置为最接近的边界值。在(21)中给出的公式有助于这一点。当我们观察公式(22)时,它给出了分配TDi的所有概率值的总和,其中i是任务,它还肯定了该值不应大于1。而更新l值公式(22)可能会被违反,因此我们使用公式(23)对值进行归一化。xi;j到PM。xi;j<$nk¼1ð23Þ7.2. 细菌代表性为了选择用于调度任务TDi的资源,我们检查行中的最高可能值以找到匹配。细菌的表示是所识别的与能量消耗有关的问题的潜在解决方案,n i¼ max.Xi;j;i2f1;2;示于图 3.细菌的集合由S S1;S2;每种细菌的h和l编码如下。给定定义3.1中给出的任务,h可以表示如下。hn<$fTDn1; TDn2;h的初始内容为使用广度优先搜索生成 程序 来达格。h包含任务编号。h中的任务编号不允许重复。h的重要性在于它指定了云中任务的执行顺序resource.假设 我们 是 给定 h、 资源PS PM1; PM2; PM3;图三.细菌的结构具有四个PM和DAG中给出的任务的l的示例如下所示:基于l值,c(任务到PM的映射)在表2中给出。7.3. 杂种趋化性杂交趋化性是指E.大肠杆菌是由鞭毛携带的。它包括三个基本步骤,即:表2c值。PM3 PM3 PM4 PM2 PM1 PM2 PM1 PM4 PM3 TS11 TS12 TS13 TS21TS22 TS23 TS31 TS32 TS33 TS34220S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 230ðÞðÞðþ Þþ半-]ð Þ ¼ ðÞðÞðþ Þð Þðþ Þþ66772019-06-2500 :00:00 00:00 00:00 00:00 00:0023667764752367¼¼ðÞþð Þ ð Þð Þðþ Þðþ Þ ¼ðþ Þ0点 44分 零点十二分 时间00: 43 00:01翻滚游泳和变异通过翻滚(随机方向的运动)和游泳(同一方向的运动),细菌向前移动以收集营养。加入遗传算法的变异步骤,使趋化过程成为混合趋化过程。这里我们初始化细菌集合Sn。我们启动一个循环找到细菌集合中每个细菌的适应度函数。从集合中提取第一细菌,即h1和l1,找到适应度函数m作为Ji;j;k;l,其对应于第j个混合趋化性、第k个再生和第l个消除和扩散步骤中的初始位置向量qi;j;k;l在本文中,我们考虑qi;j;k;l作为当前l和h值。分配Jlasti;j;k;lJ i;j;k;l.下一个是如下计算第(j1)个混合趋化步骤的qi;j1;k;lqi;j1;k;l i; j;k; lC ifj25qi;j1;k;l在第(j1)个混合趋化步骤处产生适应度函数Ji;j1;k;l。C i是在翻滚指定的随机方向上迈出的步的大小。生成一个随机方向fj,它是区间1; 1之间的一个值。它是第j个混合趋化步骤的方向角。如果在qqi;j1;k;l处的Ji ;j1;k;l优于然后细菌进行另一个步骤,ðÞ表3突变前的c值TS11 TS21 TS32 TS31 TS33 TS34 TS12 TS23TS22TS13PM3 PM3 PM4 PM2 PM1 PM1 PM2 PM1 PM4 PM3突变(更新l):在l中进行突变,生成新的l0。零点十二分 0点 26分 时间00: 4600: 16零点二十三分 零点十九分 时间00: 34 00: 24零点三十二分 0时 06分 时间00:3000: 330点 26分 0点 28分 2019 - 01- 2500:00:突变前l0:44 零点十二分 零点四十三分0:01;及0点 38分 0点 31分 时间00:05: 260点 62分 零点十六分 时间00:1200: 090点 31分 零点二十分 时间00: 1100: 370点 13分 0点 10分 时间:2019- 05 -23 00:00:000点 46分 0点 26分 时间00:12 00:16零点二十三分 零点三十四分 2019 -01 - 24 00:00:00零点三十二分 0时 06分 时间00:3000: 330点 26分 0点 28分 2019 - 01- 2500:00:6 7大小为C i,否则它在大小为fj的随机方向上翻滚。这个过程一直持续到j Nc。在趋化过程中,细菌细胞在游动和翻滚之间交替。混合趋化性中涉及的步骤在算法4中给出。游泳、移动和翻滚过程如下进行:7.3.1. 滚筒式在这个过程中,细菌以随机的方向翻滚。我们在新位置计算Ji;j;k;l,并将此值赋给Jlasti; j; k; l。新的位置基于Eq.(25).7.3.2. 移动在此步骤中,我们将位置更新为li;j1;k;l到如下得到l的新值:设li;j 1;k;lli;j;k;l C ifj,因为这导致大小为C i的步长 在细菌j的翻滚方向上。根据公式(23)将l归一化。 计算健身函数Ji; j 1; k; l。7.3.3. 游泳细菌的游动和翻滚取决于Ji;j1;k;l和Ji;j;k;l的值,即如果Ji;j1;k;l大于Ji;j;k;l,则细菌以Ci的步长游动,否则以fj步的随机方向翻滚更新qi;j1;k;l。 这里我们只更新l。 的该更新过程的意义在于,我们得到不同的C值,但是H值保持相同。更新过程如下,即通过如下示例中给出的突变来更新l0S. Srichandan等人/Future Computing and Informatics Journal 3(2018)210e 23022166772019-06-2100:00:00 00:0000:00 00:00ð ðþÞ ðÞÞðÞ00:00:00 00:00: 00 00: 00:00零点二十七分 零点三十三分 2019- 01 -25 00:00: 000点 09分 零点十六分 时间:2019 -02-0点 1
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功