ToB企服应用市场:ToB评测及商务社交产业平台

标题: BCGO：一种生物开导式云计算任务调度算法 [打印本页]

---

作者: 南七星之家    时间: 2024-6-15 00:55
标题: BCGO：一种生物开导式云计算任务调度算法
BCGO：一种生物开导式云计算任务调度算法

代码链接: https://github.com/Chadnon/Cloud-scheduling

摘要 随着应用程序计算需求的快速增长，异构计算资源不停地增多，任务调度成为云计算领域中重要的研究标题。云计算提供了一个异构的环境来执行各种操纵，对于任何应用程序，将异构任务高效地调度到异构处理器是获得高性能的关键。云环境下的任务调度是一个NP-Hard优化标题，研究者提出了各种开导式和元开导式技能来提供标题的次优解决方案。本文提出了一种基于天牛须搜索（BAS），并团结蚁群优化（ACO）和遗传算法（GA）的任务调度算法天牛群遗传优化（BCGO）来优化系统的最大竣工时间和淘汰均匀等候时间。计划的算法在CloudSim模拟器上实现并仿真。仿真结果与蚁群算法，Min-Min算法，Max-Min算法，轮询算法和随机算法举行了比较，得到了满意的结果。
简介

随着信息期间的快速发展，在分布式计算、并行计算和网格计算渐渐发展成熟的底子上，云计算应运而生。 作为一种新兴的贸易计算模型，云计算( Cloud Computing)［1］已经成为了工业界和学术界研究的热门。“云计算”指的是将计算资源作为服务提供。其核心思想是将大量计算资源、储存资源和服务资源等通过网络毗连起来形成资源池，根据用户的需求对资源举行同一调度和管理。大量的服务器需要向大量的云用户提供服务。CSP (cloud service provider)管理全部的云资源，以提供服务，并维持肯定的服务质量(QoS)。云用户将他们的任务提交给CSP，而且在他们之间达成了一项协议。该协议通常称为服务程度协议(SLA)。CSP根据SLA协议提供服务。违反SLA的行为会对利润产生影响。
捏造资源(CPU、主存、磁盘、带宽等)的分配在低沉系统能耗、优化最大竣工时间、淘汰等候时间、提高系统吞吐量等方面发挥着重要作用。 然而，由于不停增长的用户量和云计算网络中节点的异构性和复杂性，怎样及时、高效地举行任务调度，合理地利用资源，提高资源利用率和任务执行的效率，成为云计算研究的核心标题之一［2］。 在云平台中，调度分为两个级别。起首，当任务上传到云上时，调度器将请求的任务分配给不同的捏造机，试图淘汰跨捏造机的多个应用程序的完成时间。第二，将捏造机分配给物理机，以平衡负载或淘汰能耗等。我们的研究重点将在于第一个级别的任务调度。
云计算的任务调度的目标是对用户提交的任务实现最优调度，具体包罗实现最优时间跨度(Optimal Makespan)，保障服务质量(Quality of Service，QoS)，保证负载均衡(Load Balancing)以及节省经济成本(Economic Principles)。时间跨度是从云计算系统中第一个任务开始，直到最后一个任务执行完成过程中所消耗的时间，时间跨度越短证明调度策略越好。跨度是调度中重要且常见的目标，因此，实现最优跨度是用户和云计算提供商的共同目标。负载均衡是云计算系统中的资源分配负载平衡，到达最优化资源使用、最大化吞吐量和最小化响应时间，避免过载[3]。
任务分配或调度标题是一个闻名的NP-Hard标题。该标题的NP完备性引起了研究人员极大的爱好。比年来，许多开导式智能算法引起了浩繁学者的关注和爱好，常用的开导式思想的智能化算法包罗两类[ 4 ]1) 基于生物开导 (Biological Inspiration, BI)：遗传算法 (Genetic Algorithm, GA)、模因算法(Memetic Algorithm, MA)、狮子算法 (Lion Algorithm,LA)、帝国竞争算法 (Imperialist Competitive Algorithm,ICA), 是在云计算中与任务调度相关的少数生物开导算法。(2) 基于群体智能 (Swarm Intelligence, SI)：蚁群优化 (Ant Colony Optimization, ACO) 、布谷鸟算法（cuckoo search algorithm）、粒子群优化 (Particle Swarm Optimization, PSO) 算法、模拟退火 (Simulated Annealing, SA) 算法、人工蜂群(Artificial Bee Colony, ABC) 算法、猫群优化 (CatSwarm Optimization, CSO) 算法、蝙蝠算法 (BatAlgorithm, BA)、风驱动优化 (Wind Driven Opti-mization, WDO) 算法等[4]。这些算法以各自的优点对NP hard 标题和组合优化标题举行求解。
文献[5]提出基于蚁群算法的任务调度算法,该算法以优化竣工时间和均匀等候时间为目标。文献［6］提出了一种基于改进的群居蜘蛛优化的任务调度算法，该算法根据群居蜘蛛觅食行为计划了调度模型，并接纳混沌惯性权重提高算法的寻优能力，在最小化完成时间的同时平衡资源利用率。文献［7］提出基于改进遗传算法的任务调度算法，调度总任务完成时间和任务均匀完成时间较短。文献[ 8 ]提出了将蚁群算法和粒子群算法相团结来提高系统性能的想法。他们提出这样做是为了提高收敛速率，消除陷入局部最优解的标题，文献［9］利用余弦相似度判断任务所需资源与总资源的相似度，并利用粒子群算法将任务分配给相似度较高的资源，最后计算整个系统利用率的标准差，判断是否到达负载均衡标准。
相对而言，天牛须搜索算法(BAS)是一种比较新颖的单体智能开导式优化算法，国内外一些学者在此方面做了一些研究。文献[10,11]将BAS与群体智能算法PSO团结后应用于电力调度方面。文献[12]将BAS应用于无人机感知、避障，提高了了无人机的避障能力。文献[13]将BAS算法与二维Ostu相联实用于图像分割,利用二维灰色Ostu模型来作为BAS算法的适应度函数，实验结果表明,该算法在收敛速率和分割效果两方面均优于基于遗传算法的分割算法。还有PID控制[ 14 ]，SVM优化[ 15 ]，机器人路径规划[16]等方面的应用。但是，目前还没有人将此算法应用于求解云计算任务调度上，主要缘故原由在于BAS主要用于求解连续标题的优化，而任务调度是一种离散标题。
在这篇文章中，我们使用预期时间计算(ETC)模型作为任务模型。这个ETC模型代表了任务和机器的异构性。ETC矩阵表现第i个任务在第j个VM上计算的预期时间。使用TASK_LIST中的任务长度和VM_LIST中VM的处理速率构建ETC矩阵。我们提出了一种基于一种基于天牛须搜索(BAS)，并团结蚁群优化(ACO)和遗传算法(GA)的任务调度算法天牛群遗传优化(BCGO)来优化系统的最大竣工时间和淘汰均匀等候时间。具体的，我们的贡献如下：
（1）初次将原本应用于连续优化的天牛须搜索算法应用到云计算的任务分配标题中；
（2）将天牛须搜索算法群体化并团结遗传算法使天牛须搜索算法离散化；
（3）使用蚁群算法为天牛群算法初始化。
（4）将我们所提出的算法与其他六种任务调度算法举行了仿真实验比较，证明了我们算法的有效性。
本文第1节介绍云计算任务调度模型，第2节对天牛须搜索算法做一个介绍；第3节介绍蚁群算法；第4节简要介绍遗传算法；第5节介绍我们提出的天牛群遗传算法(BCGO)以及怎样应用到任务调度；第6节将对我们所提出的算法的性能举行实验测试，并与蚁群算法，遗传算法，Min-Min算法，Max-Min算法，轮询算法和随机算法举行比较；最后总结全文。
1 任务调度模型

图1 云计算任务调度模型
假设如今有N个任务到达，任务集T={T1, T2, T3, T4}，此中第i个任务的任务长度是task_leni。捏造机聚集，此中第j个捏造机的执行速率是VM_speedj。在捏造机j上执行任务i的估计计算时间由下式给出：

调度算法的最终输出是一个NM分配矩阵，该分配矩阵表明哪个任务应该由哪个VM执行。分配矩阵界说为：

限制条件

即一个任务只能分给一个捏造机
因此，第j*个捏造机执行时间由下式给出：

则系统最小完成时间为

为了简化代码，我们在代码中将分配方案表现为一个长度任务纵然长度len(T)的数组schedule[len(T)]，schedule存储的是任务i分配到的捏造机编号。
2 天牛须搜索算法

2.1 根本算法

天牛须算法 (Beetle Antennae search algorithm, BAS) 是由Jiang[ 17 ]即是2017年提出的一种智能优化算法，与其他仿生类算法不同，天牛须算法是一种单体搜索算法，具有原理简朴、参数少、计算量少等优点，在处理低维优化目标时具有非常大的上风：时间复杂度低、搜索能力较强。
天牛须搜索算法模仿自然界中天牛觅食行为。在天牛觅食过程中，食品会产生特别气味，吸引天牛向着食品进步。天牛通过其两只触角对空气中的食品气味举行感知，且根据食品间隔两只触角的间隔远近不同，两只触角所感知的气味浓度也有所差异。当食品处于天牛左侧时，左侧触角感知的气味浓度强于右侧触角感知的气味浓度，天牛根据两只触角所感知的浓度差，向着浓度强的一侧随机进步。通过一次次迭代，最终找到食品的位置。
BAS算法主要是通过在不停的左右触角气味浓度比对中进步，同其他算法相比，原理十分简朴。在举行两只触角气味浓度计算之前，需要对其举行一系列准备工作，在N维空间中天牛的位置为X={x1, x2, x3, … xn},天牛左右两只触角的位置被界说为如下公式所示模型：

上式中，l表现天牛质心与触须的间隔,d表现随即单位向量，需对其举行归一化操纵：

根据左右两根触角感知的气味浓度差举行对比，判断天牛下一步的位置：

式中，t表现当前的迭代次数；f表现适应度函数；xita表现第t次迭代时的探索步长，sign函数为符号函数，各个变量的具体界说为：

此中eta是步长衰减因子。
.

2.2 算法流程

输入：解空间维度、最大迭代次数、初始步长；
输出：极值点g_best；
Step1：初始化步长衰减因子、狩猎空间，位置信息X
Step2：根据公式(1-2)举行归一化处理；
Step3：根据公式(1-1)确定天牛的左须与右须位置；
Step4：根据公式(1-3)更新天牛的位置
Step5 ：计算天牛位置的适应度函数值并存储，根据公式(1-4)更新步长；
Step6 ：判断是否到达迭代停止条件，如果则输出全局最优解，否则跳转至Step2。
3 蚁群优化算法

本节将梳理蚁群优化的算法流程。由于许多使用蚁群算法举行任务调度的文献都没有表述清楚怎样将原始的蚁群算法应用到云计算的任务调度中，因此本节还将具体表述怎样将原始的蚁群算法应用到云计算的任务调度中。
3.1 根本算法
蚁群算法是一种用来寻找优化路径的概率型算法。它由Colorni[18]于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食品过程中发现路径的行为。这种算法具有分布计算、信息正反馈和开导式搜索的特征，本质上是进化算法中的一种开导式全局优化算法。由于蚁群算法本身就是用来搜寻路径的，因此很容易就可以或许移植到云计算的任务调度算法上。
蚂蚁一开始是随机寻找食品的，在找到食品后，蚂蚁会增加从食品地到蚁群的路径上的信息素。一旦它们找到了食品路径，下次它们就不再随机观光，而是沿着信息素多的地方，盼望这条线索能找到食品。然而，随着时间的推移，信息素痕迹开始消失，这导致吸引力削弱。如果蚂蚁花更多的时间在这条路上走，就会呈现更多的信息素痕迹。与此同时，从食品来源到食品的较短路径有更多的信息素痕迹，由于蚂蚁习惯于找到这条短路径并穿过这条短路径。因此长路径上的信息素密度小于短路径上的信息素密度。信息素的蒸发消除了局部最优解的收敛性。
在蚁群优化系统中，每个蚂蚁都是一个计算代理。它迭代地构造出对该标题的最佳解决方案。在每一代中，每个蚂蚁都从一个状态i过渡到状态j，并朝着局部最优解决方案过渡。因此，在每次迭代中，每个蚂蚁都通过使用概率来计算针对其当前状态的一组可行解，并将其移至局部最优状态之一。对于每个蚂蚁k，从状态i迁移到状态j的概率 P i , j k P_{i, j}^{k} Pi,jk​通常取决于两个参数， τ i , j \tau_{i, j} τi,j​表现信息素浓度，代表先前的移动，而 η i , j \eta_{i, j} ηi,j​表现的移动的可见性，表现过去的价值。这些值会不停更新，以在每次迭代中获得更好的最佳解决方案。在每次迭代中，它们的值可能会根据其效果而增加或淘汰，从而获得最佳解决方案。通常，蚂蚁将任务i分配给捏造机j的概率由公式(3-1)给出。

此中， τ i , j \tau_{i, j} τi,j​

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4