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]存储的是任务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$通常取决于两个参数，${\tau }_{i,j}$表示信息素浓度，代表先前的移动，而${\eta }_{i,j}$表示的移动的可见性，表示过去的价值。这些值会不断更新，以在每次迭代中获得更好的最佳解决方案。在每次迭代中，它们的值可能会根据其效果而增加或减少，从而获得最佳解决方案。通常，蚂蚁将任务i分配给虚拟机j的概率由公式(3-1)给出。

其中，${\tau }_{i,j}$