云计算任务调度策略与优化算法研究

TURGANBEK DILNUR

摘 要：将云环境运用到科学工作当中，即可以使得任务调度更好的完成，还可以使得用户更加满意，之前解决调度问题的方式是将一个大问题转换成各个小问题，然后树立多数量的目标，将云环境弹性的特点充分发挥出来，之后提出了更加完善的方法是快速非支配排序分布算法，主要目的是使得工作时间缩短降低成本，使得云计算完全运用到服务当中。将快速飞支配排序算法和分布估计计算法共同运用在模拟调度当中，借鉴种群收敛和有关遗传的知识分子呢对种群进行采样分析，培养出全新的个体。这个方法是通过种群来培养新的个体，也就是将种群的特点和个体的特点相结合，使得最好的方式得到充分的运用。将非支配排序算法运用到云计算中，然后在模拟器中进行运行。工作流主要用神经学工作流，同时与运用其他工作流的模拟器进行对比。之后设计出了相关函数，是为了测量培养出的新个体的质量的大小，。通过对实验结果的对比，改进之后的算法可以达到降低时间和成本的目的，同时使得用户的满意度提高。

关键词：快速非支配排序;任务调度;多目标优化;云计算;分布估计

1.课题的研究意义

任务调解和资源的分派在云计算里面起到了两个重要的作用。在系统的工作流调度算法，没有办法在多个时间内求解。这是一个完整的NP问题。事实证明，

针对解决云计算调度问题，启发式比定性算法更合适。因为如果采用不适合解决云计算调度问题的方式，会降低工作效率同时还会增加成本，在云计算中的云服务中会使得经济效益减弱，在满足用户的质量的同时要提升服务的目标是一个宗旨，为此研究科学工作流下的云计算调度优化算法是极其重要的。

通过介绍课题在云计算、科学工作流和调度算法中的研究背景，并结合现有的算法存在一些问题，会造成一定的资源浪费。对现有算法进行改进，不仅能够节省资源成本还能够提升效率，所以说，研究云计算调度策略的优化算法是十分必要且有意义的。

2.非支配排序算法和分布估计算法的研究

为了以更快的方式找出运行过程中最好的方式，主要的方式就是讲非支配排序算法和分布估计法以最快的速度结合起来，首先对非支配排列算法进行了概述。接下来介绍分布估计算法的相关概念。最后介绍两种方法的组合。

2.1非支配排序算法

由于非主要的NSGA计算很复杂，所以针对于. NSGA的维护系统还没有被研制出来。在2000年的时候，Deb等人对NSGA进行全新升级，于是出现了NSGAII，它的出现使得NSGA计算的复杂性降低，之前的适应度都是人主观上决定的，现在NSGAII的出现通过拥挤度代替了之前的方法，这就使得在使用非支配顺序之后，个体遗传还能保持一致，就可以保证种群的种类多。NSGAII还研究出了对NSGA的维护系统，可以将各代个体相结合，之后将培养出的精英新个体保留下来，实现对NSGA系统的维护，以及精英个体的保留。由于个体中的所有个体都是分层存储的，因此不会丢失精英个体，并且可以实现快速增加个体数量的目标。 NSGAⅡ算法的优点是可以均匀分配近似最优解，而不会限制优化目标函数的数量。此功能可以从多个基于Pareto的非主导级别中为当前方案选择最佳解决方案，尤其是用于解决交通信号的多目标优化计时问题。

2.2分布估计算法

所谓分布估算法，最早是在统计学原理中用于对解空间问题从宏观进化角度的解释，

分布估算法和遗传法相比较，分布估算法的优势更大，因为这个方法的搜索能力是很强的，其次就是个体的收敛速度占据优势。近几年分布估算法被频繁的运用到柔性作业车间：Wang等人提出了双种群分布估算法，在培养出很多代之后，运用双种群分布估算法对得到的个体进行分类和筛选，之后将不同的种群进行结合，在合并过程进行之前，要满足合并的原则，然后对结合的种群进行采样，对采样数据进行分析，。因为车间的调度的问题是和云计算有一定关系的，所以采用的方法是多目标的，所以就研制出了一种叫Pareto的分布估计算法，这种方法主要依据的就是概率。但是这样的算法很容易导致培养出的新个体早熟，所以就将两个不同的种群通过不同的当时培养出精英个体，由此看来，通过不同的当时进行精英的开发，是最优解。[1]

针对解决柔性作业车间的这个问题，何小娟等人是有很好的解决办法的，主要的方法就是運用概率，刚开始的时候，将不同的种群进行分类，然后运用不同的当时将工件制作出来， 统计每一种方法制作出工件的时间，筛选出消耗时间最短的方法作为最优解。之后通过实验结果建立概率，然后设计模型，最后通过运用Bayesian将概率和模型总和起来，由于采样的过程太多会导致个体的早熟，为了避免这种现象的出现，他又通过k均值的方法两种群放在一起进行培养，最终得到优势种群。在柔性作业车间调度问题中，分布估算法起到了很明显的作用，然而建立准确的模型对于解决复杂问题是更加重要的。

所谓分布估算法，最早是在统计学原理中用于对解空间问题从宏观进化角度的分布估算法和遗传法相比较，分布估算法的优势更大，因为这个方法的搜索能力是很强的，其次就是个体的收敛速度占据优势。近几年分布估算法被频繁的运用到柔性作业车间：Wang等人提出了双种群分布估算法，在培养出很多代之后，运用双种群分布估算法对得到的个体进行分类和筛选，之后将不同的种群进行结合，在合并过程进行之前，要满足合并的原则，然后对结合的种群进行采样，对采样数据进行分析。因为车间的调度的问题是和云计算有一定关系的，所以采用的方法是多目标的，所以就研制出了一种叫Pareto的分布估计算法，这种方法主要依据的就是概率。但是这样的算法很容易导致培养出的新个体早熟，所以就将两个不同的种群通过不同的当时培养出精英个体，由此看来，通过不同的当时进行精英的开发，是最优解。[1]

针对解决柔性作业车间的这个问题，何小娟等人是有很好的解决办法的，主要的方法就是运用概率，刚开始的时候，将不同的种群进行分类，然后运用不同的当时将工件制作出来， 统计每一种方法制作出工件的时间，筛选出消耗时间最短的方法作为最优解。之后通过实验结果建立概率，然后设计模型，最后通过运用Bayesian将概率和模型总和起来，由于采样的过程太多会导致个体的早熟，为了避免这种现象的出现，他又通过k均值的方法两种群放在一起进行培养，最终得到优势种群。在柔性作业车间调度问题中，分布估算法起到了很明显的作用，然而建立准确的模型对于解决复杂问题是更加重要的。

3.算法研究

3.1非支配排序算法

NSGAⅡ的执行步骤：

（1）随机产生初始种群，此时种群的进化代数Gen=0。

（2）判断第一代种群是否生成，如果是的话，执行下一步，否则通过遗传操作（选择、交叉和变异）来产生第一代的种群。

（3）将父代与子代中的个体进行合并，然后对合并后的种群采取快速非支配排序、分层。对解个体执行拥挤度计算，通过精英策略产生下一代种群。

（4）选择、交叉和变异，生成新的种群。

（5）查看进化代数值是否达到预设值。

（6）所得种群就是所求的即为最优解集，否则使Gen=Gen+1，执行步骤（3）。

快速非支配排序的伪代码：

Fast=nondominated=sort（Pop）

{

For each i in Pop

{

For each j in Pop

{if i dominate j then

Si=Si∪{j};

else if j dominate i then

ni=ni+1;

}

if ni=0 then

Fi=Fi∪{p}

}

i=1

While（Fi！=NULL）

{

H=NULL;

for each i in Fi

{ for each j in Si

nj=nj-1;

if nj=0 then H-H∪{j};

}

i=i+1;

Fi=H;

}

}

計算拥挤度的伪代码：

Crowding-distance-assignment（Pop）

{

N=∣Pop∣

for each I， P[i]distance=0

for each object m

{

Pop=sort（Pop，m）

for i=2 to （N-1）

P[i]distance=P[i]distance+（P[i+1].m-P[i-1].m）

}

P[0]distance=P[N]distance=∞

}

这里将边界值设置为无穷大，保证第一个和最后一个解个体一定会被选中。

3，2分布估计算法

（1）种群的初始化：令t=0，设种群为Pop（t），其中包含N个解。Pop（t）中的解个体适应度值都是采用随机方式生成的。

（2）计算个体适应度：根据适应度函数计算解个体适应度值。

（3）选择策略：运用一定的选择策略选取适应度值最高的M个个体作为优秀个体，令个体集为S（t）。

（4）建立概率模型：根据S（t）估计出概 率分布模型Prob（t）。

（5）采样并更新种群：依据建立的概率模型，采样产生新的个体。令t=t+1，更新种群Pop（t+1）。

（6）终止判断：检查是否满足终止条件，满足，算法结束;否则，返回步骤（2））。

图2为分布估计算法流程图。

优化的非支配排序算法：

NSGA II引入了快速的非优势排序算法和精英策略，但是对于大多数多目标问题，在决策空间中，对于Pareto解集的分布通常有特定的规则。NSGAⅡ基因工程忽略了该规则，仅在各个解决方案之间起作用。分布估计算法EDA中变量之间的关系由概率模型描述，这使得最大化利用人口分布信息并有效利用人口产生的历史信息成为可能。然而，分布估计算法EDA的建模过程复杂且难以操作。在算法的早期阶段，解决方案个体在总体中的分布是随机且完全无规则的。目前，我们已经使用分布估计算法的随机模型来建立新的个体，通常离最优解集很远。此外，分布估计算法没有像快速非优势排序算法NSGAII那样有效地使用单个局部信息。

本文将离散分布估计算法与非优势排序算法结合在一起，以充分利用每种算法。当算法开始运行时，非主导算法的遗传运算（交叉，变异）是分布式模型概率模型，因为初始组的各个解更加分散并且它们之间的关系相对较小。生成个体的可能性要高于生成新个体的可能性。当通过执行算法使总体的分布收敛到预定的期望值时，当总体的解个体显示出特定的分布规律时，使用分布估计的概率模型生成解个体。可能性逐渐增加。

在算法的早期阶段，使用随机建模构建的解决方案的个体通常与Pareto最优解决方案集相去甚远。遗传算法具有快速优化优化的能力。在算法开始时，不满足收敛规则。遗传算法（交叉，变异）用于生成新的求解个体，从而加速了Pareto最优求解集的求解。首先，生成范围为[0，1]的随机变量。设置根据总体收敛性分配的比较变量，并将rand（）与CF进行比较，以确定用于生成新个体的方法。如果个体在人口中的分布是分散的，则没有收敛的趋势，或者收敛程度没有达到期望值，并且如果CF = 0.7，则遗传算法生成的个体数数量会增加。如果人口分布收敛到期望值且CF = 0.3，则概率模型将采样更多新个体。

4.仿真实验及结果分析

要想科学工作流能够在云环境中正常进行，本文在模拟器中进行了实验。针对云计算来说，它是一个可以对基础架构进行建模和仿真的自包含平台。 在进行模拟实验之前，应设置实验参数，例如带宽值和任务长度。

算法完成后，通过检查上一代解决方案的分布。将总体大小设置为70，将迭代次数设置为400，然后运行算法10次以获取非劣性解集。使用快速非支配排序算法对总体进行分层，并使用拥堵作为同一层的选择标准。

这种方式可以将Pareto的最优解被运用到各种地方，使得种群的种类数增大，将种群的信息以及相关信息了解的更加清楚。把NSGAeda算法与NSGAII算法对比一下。如图4，在解决调度问题的时候，通过NSGAeda方法算出来的结果更具普遍性，种群种类数量更多。从图中可以看出改进算法NSG Aeda调度的成本较低。由于这是一个多用途问题，因此在理想情况下，解决方案集中的各个方案无法同时实现调度时间和服务成本。用户可以根据实际情况在执行时间和服务成本之间进行折中选择，并对选择的解决方案进行解码以找到正确的任务调度解决方案。

图4 解分布情况

不同数量的处理器具有不同的处理能力。不同的虚拟资源具有不同的处理任务的能力。当可用资源数量较少时，改进算法NSGAeda的最佳解决方案能力很差，并且通常无法找到最佳解决方案集。随着虚拟资源数量的增加，NSGAeda算法找到最佳解决方案集的能力显着提高，如图5和6所示。

图5 最优解的百分比                            图6 处理器数目

5.总结

为了更充分的理解本课题，首先对云计算、科学工作流和多目标问题的基本概念进行介绍。云计算的弹性特点是非常显著的，在运用到科学工作流中的时候，优点更加明显，主要的优点有：

（1）云计算可以出现在任何时候任何地方，当运用到科学工作中时，科学工作就不仅仅存在于实验室中，还可以在任何地方被运用。

（2）数据云在任务调度中也起到很大作用，而且科学工作流中的数据驱动模式也是需要在任务调度中起作用，于是二者相互配合。

（3）云计算和科学工作流都是具有動态特征的，二者相结合，不会一直持续工作完成成本的浪费，可以节约成本。

（4）用户运用云计算的费用低，这样可以增加用户数量，增加用户的满意度。

综上所述，可以看出在云上执行科学工作流是可行的。且目前分布估计算法和非支配排序算法已经较为成熟，可以将二者相结合解决多目标问题。

对云计算的相关概念和特点进行了介绍，然后对工作流任务调度技术进行了总结，分析了多目标优化问题和相应的最优解。阐述了非支配排序算法和分布估算法的基本概念。此外还将分布估算法的优点运用到非支配排序算法中，对其进行改进，优点共存缺点互补，设计出了新的算法，为了很符合云计算无限资源的特点，设计出了目标函数，然后进行实验，对实验结果进行分析，最终得出结论。

参考文献：

[1]Iuon-Chang Lin，Chen-Yang Cheng，Hsiang-Yu Chen. A real-time parking service with proxy re-encryption in vehicular cloud computing[J]. Engineering Applications of Artificial Intelligence，2019，85.

[2]Bahador Shojaiemehr，Amir Masoud Rahmani，Nooruldeen Nasih Qader. Automated negotiation for ensuring composite service requirements in cloud computing[J]. Journal of Systems Architecture，2019，99.

[3]Services Computing; Recent Findings in Services Computing Described by Researchers from Chongqing University （Energy and Migration Cost-aware Dynamic Virtual Machine Consolidation In Heterogeneous Cloud Datacenters）[J]. Computers， Networks & Communications，2019.

[4]AT&T Intellectual Property I L.P.; Patent Issued for Virtual Zones For Open Systems Interconnection Layer 4 Through Layer 7 Services In A Cloud Computing System （USPTO 10，389，796）[J]. Computers， Networks & Communications，2019.

[5]Information Technology - Cloud Computing; Researchers at Chosun University Target Cloud Computing （Ontology-based Security Context Reasoning for Power Iot-cloud Security Service）[J]. Computers， Networks & Communications，2019.

[6]胡朋.中小企业使用云计算技术的必要性分析[J].决策探索（下），2019（09）：24-25.

[7]Yawen Wang，Yunfei Guo，Zehua Guo，Thar Baker，Wenyan Liu. CLOSURE： A cloud scientific workflow scheduling algorithm based on attack–defense game model[J]. Future Generation Computer Systems，2019.

[8]黄引豪，马郓，林兵，於志勇，陈星.混合云环境下面向代价优化的工作流数据布局方法[J].计算机科学，2019，46（S2）：354-358+386.

[9]尚蕾，刘茜萍.基于任务分配和数据副本的科学工作流数据布局[J/OL].计算机工程：1-8[2020-01-02].https：//doi.org/10.19678/j.issn.1000-3428.0055397.

[10]Perkel Jeffrey M. Workflow systems turn raw data into scientific knowledge.[J]. Nature，2019，573（7772）.

[11]冯复剑.云环境下科学工作流的调度算法[J].计算机系统应用，2019，28（07）：127-132.

[12]党云龙，封筠，殷梦莹.截止时间约束的工作流调度自适应进化方法[J].石家庄铁道大学学报（自然科学版），2019，32（03）：94-100.

[13]张继炎，郑汉垣.云环境下基于预算分配的科学工作流调度研究[J].计算机工程，2019，45（09）：40-48.

[14]Wenjun Ji. Research on Computer Software Engineering based on Scientific Workflow[P]. Proceedings of the 3rd International Conference on Mechatronics Engineering and Information Technology （ICMEIT 2019），2019.

[15]. China approves Thermo Fisher Scientific's PCR workflow to detect ASF[J]. National Hog Farmer，2019.

[16]高天羽. 截止時间约束下的云工作流成本优化算法研究[D].西北大学，2019.

[17]尹成国.云计算技术发展分析及其应用探讨[J].网络安全技术与应用，2019（09）：55-56.

[18]路艳雪，赵超凡，吴晓锋，韩晓霞.基于改进的NSGA-Ⅱ多目标优化方法研究[J].计算机应用研究，2018，35（06）：1733-1737.

[19]吴烨烨，高尚.改进的分布估计算法求解多目标优化问题[J].计算机与数字工程，2019，47（06）：1357-1363.

[20]郑瑛.云计算数据中心节能调度算法改进研究[J].西南大学学报（自然科学版），2019，41（12）：135-142.