云计算任务调度算法的改进

陈春玲++张瑞霞++曹萌萌

摘 要：云环境下的工作流，进行合理的任务调度，可以克服地理限制，节省资源，从而提高用户的满意度。本文提出改进算法：快速非支配排序贝叶斯算法NSGAboa，该算法是快速非支配排序算法NSGAII和贝叶斯算法BOA的结合，根据种群中个体间的分布收敛程度来改变产生个体的方法，利用了种群个体信息和全局信息。实验证明该算法使得最优解的分布更加均匀，加快了个体产生的速度，缩短了种群的收敛速度。

关键词：任务调度；快速非支配排序；贝叶斯；云计算

Improvement of Cloud-based Scheduling Algorithm

Ruixia Zhang Chunling Chen Mengmeng Cao（Nangjing University of Posts

and Telecommunications School of Computer Science &Technology，School of Software；Nanjing China；210003）

Abstract：The workflow reasonable scheduling in the cloud environment， which has the ability to improve user satisfaction， can overcome geographical restrictions and saving resources. The article process a new algorithm： NSGAboa. the NSGAboa algorithm is a union of the fast nondominated sorting algorithm and Bayesian algorithm. NSGAboa algorithm， based on the degree of convergence of the distribution of the population among individuals changes the methods of generating solution individuals. The algorithm takes full advantage of the individual information of the populations and global information. Experiments show that this approach allows a more uniform distribution of the optimal solution， and reduces the convergence rate of population.

Key words：task scheduling；fast nondominated sorting；BOA；cloud computing

任务调度[1]策略对云计算的性能具有重要的影响，调度不同环境中的不同任务在云计算中是一种常见现象，传统的分布式计算和并行计算却不能满足这种应用。任务调度算法有很多，它们在一定程度上提高了工作流的执行效率，减少了执行时间。在云环境中任务调度的优化可以减少任务完成时间，提高服务质量，所以研究任务调度算法意义重大。传统算法各有其优点，我们将快速非支配排序算法和贝叶斯算法结合，让贝叶斯算法弥补快速非支配算法不能利用种群全局信息的不足，最终是改进后算法充分利用种群的全局信息和局部信息。在种群个体收敛到适当的时刻由快速非支配排序算法转换成贝叶斯算法，使得个体产生的速度加快，提高新算法的效率。

1 云计算中任务调度相关介绍

云计算作为一种计算模式，区别于传统的分布式计算和网格计算。云计算中的计算任务分布在虚拟的资源池上。这些资源池由许多地理位置分散的网络终端构成，这些网络终端通过互联网和路由器进行通信。各种应用系统按需透明地获得性价比较高的计算能力、存储资源和信息服务。云计算具有虚拟化、灵活性、可扩展性、可靠性等特点[2]。

云计算中，任务调度的实质是将n个相互独立的任务分配到m个异构的可用资源上，使得总任务的完成时间最少，并能充分的利用资源[3]。由于云计算系统的异构性和动态性，资源类型和任务的差异性，性能较低的调度算法，会增加任务执行时间，从而降低系统的性能，甚至引起系统崩溃。

调度算法的好坏对云计算的性能表现具有重要的意义，很多现有算法都不能完全满足云环境下对算法的需求。本文将快速非支配排序[4，8]和贝叶斯两种算法结合，充分利用了种群的局部和全局信息，提高了算法的性能，使得新算法更好的适应云计算系统。

2 任务调度算法研究

2.1 非支配排序算法NSGAⅡ

2.1.1 快速非支配排序算法

NSGA II引入了快速非支配排序算法，降低了计算的复杂度。在保持种群个体多样性并可以使Pareto最优解分布的更加均匀的前提下，对种群个体进行分层，把种群个体的拥挤度作为衡量个体品质的标杆，选出高品质个体。为了扩大采样空间，使用精英策略即把子代种群和它的父代种群合并，让两个时代的所有个体相互竞争产生下一代。精英策略让所有的基因都参与竞争，不仅剔除了不良基因而且保证了优良基因的传承。

现用pop表示种群，设pop中有N个个体i（i=1，2，…，N），种群中有ni个解支配个体i，Si为这ni个解组成的集合，我们称其为支配集，ni、Si是个体i的两个重要参数。将种群pop分为m层，每层设为一个子集Fi，则共有m个子集Fi、…、Fm，则∪Fj，其中j=1，2，…，m。

快速非支配排序算法的描述如下：endprint

（1）将ni=0即支配集为空的个体划分到分层集合F1中，组成非支配层。（2）遍历分层集F1，设F1每一个个体k的支配集为 Sk，支配集Sk中的个体数为nk，若nk≠o则将n减1，若nk=o，则将个体k放入F2中，组成非支配层F2。（3）把集合pop当做当前非支配层集合重复1-2，直到种群pop中的个体都被划分到非支配层中。

2.1.2 拥挤度[5]、精英策略和基因操作

通过个体支配集和支配集中个体数筛选产生下一代种群，种群中的个体是分散存在。每个个体与相邻个体间的距离叫做这个个体的拥挤度，如个体i的拥挤度表示为P[i]distance。拥挤度计算的主要步骤是排序，排序完成后再依次计算个体的拥挤度。排序操作是以种群中个体的目标函数值的大小为依据对个体进行排序。如果有m个目标函数，并使用速度较快的快速排序时，该算的时间复杂度为o（m*N*logN）。

NSGA II引入了精英策略，为了防止在传统的遗传算法进化过程中，出现破坏或者丢失父代中具有优秀基因个体的现象。精英策略就是把子代的个体和其父代的个体合并在一起，让他们共同参与到进化过程中。使用精英策略后再用快速非支配排序算法对合并后的种群进行分层。

NSGA II算法产生的子代种群之所以继承了父代的优秀基因是因为利用了遗传算法[6]。遗传算法在算法设计中，是依据进化论中生物繁衍优胜劣汰的真实情况设计的，包括选择、杂交和变异。NSGA II所用的遗传算法采用二元锦标赛选择个体，采用模拟二进制交叉SBX和多项式变异来完成交叉和变异操作。好的遗传算法不仅是要能理论实现，更重要的是可以达到实际需要的目标，并能够得到包括所有优秀基因的最优解。

2.2 贝叶斯优化算法（BOA）[8]

在分布式算法中，变量之间相互独立或者存在某种依赖关系，不同分布式算法的主要区别在于选取下一代的概率模型不同。贝叶斯优化算法具有良好全局收敛性，这正是是本文改进算法所需要的。

贝叶斯优化算法是多变量相关型分布式算法的一种。贝叶斯算法的初始种群是根据概率分布模型均匀分布随机产生的。我们通过很多进化算法来选出优秀个体，如比例选择、截断选择和二进制锦标赛选择等。选择出的优秀个体组成新的种群，然后在这个新种群上建立贝叶斯网络概率模型。对模型进行采样，从中获取新的个体，并将新的个体重新放入原有种群中或者是完全替代原有种群，在满足终止条件之前一直重复这个过程。贝叶斯优化算法的终止条件有：最优解已经找到，种群的多样性已经消失或者是陷入了局部最优。

贝叶斯优化算法：（1）set：t=0，均匀分布随机产生初始种群P0；（2）根据个体指标从Pt中选择优秀个体集St；（3）在一定的选择方法（本文实验中采用的是比例选择）和限制条件下构建符合要求的贝叶斯网络B；（4）根据贝叶斯网络B的联合分布函数产生新的解集合Ot，形成新的种群Pt+1：将Ot放入Pt中，或者用Ot完全替代P，为了保证优秀基因的完整，本文采用的是前一种做法；（5）转向（2）直到满足终止条件结束。

贝叶斯算法的核心和关键是通过数据分析来获得贝叶斯网络。贝叶斯网络是具有结构和参数的有向无环图模型，其中的节点对应的是变量，边对应的是变量间的关系，而参数就是由变量间的关系决定的。这些参数和变量间存在联合概率分布： ，这里的X=（X1，X2，…，Xn）是一个向量，是网络中所有变量的集合， 是Xi的所有父辈的集合， 是Xi在给定父辈 下的条件概率。

2.3 两种算法的对比

NSGAⅡ引进了快速非支配算法和精英策略，但是它的遗传操作忽略了多目标问题解空间Pareto解集分布的规律性，仅作用于个体之间。即该算法只考虑到了种群的局部信息没有全局概念，没有很好地利用Pareto解集分布的规律性。

贝叶斯算法的初始种群是根据概率分布模型均匀分布随机产生的，充分利用到了种群的全局信息。在种群当中的个体开始呈现一定的分布规律的情况下使用该算法，可以增大产生个体的概率，从而能提高算法的收敛速度。

3 改进算法NSGAboa

NSGAⅡ的遗传操作忽略了多目标问题解空间Pareto解集分布的规律性，只考虑到解的个体特征，而分布式估计算法充分地利用了种群的全局信息，但是分布式估计算法较且复杂操作困难[12]。贝叶斯算法简单易懂且充分利用到了种群的全局信息，因此本文将贝叶斯算法和NSGAⅡ算法结合。在个体比较分散的初期使用NSGAⅡ算法，随着算法的运行，种群中个体分布越紧凑，收敛程度越高，当其收敛到一定程度时使用贝叶斯优化算法。此时使用贝叶斯算法可以充分利用解集的规律性和种群的全局信息，增加个体的生产速度，最终提高了算法的性能。

NSGAⅡ中遗传算法，一代代繁衍的过程中，个体不断向Pareto目标靠近，即不断收敛。我们利用个体的这种收敛程度来判断用哪种算法产生新的种群。目标空间中的每一个个体都可以看做一个点，种群就是一个点集，判断种群中个体的收敛程度就是判断这个点集中点的收敛程度。

改进算法NSGAboa的描述：

（1）set：t=0，初始化种群P0；

（2）评价群体；（3）判断是否收敛，如果收敛set：CF=0.7，否则set：CF=0.3；

（4）判断是否0﹤rand（）﹤1，是则改用贝叶斯优化算法，建立概率模型产生下一代，否则继续采用NSGAⅡ算法用遗传操作产生下一代；

（5）从Pt中选择，产生新种群Ot，将Ot加入或完全替代Pt，形成新的种群Pt+1；

（6）返回（2）直到满足终止条件。

4 NSGAboa算法测试

此处使用三个基准函数测试改进后的算法，判断改进算法NSGAboa的性能。分别通过连续凸形、连续非凸形和具有五段离散性的三个函数来测试算法性能。endprint

函数1：

函数2：

函数3：

其中，n=50， 。

在多目标优化问题测试中，我们选取的测试目标有两个：收敛性测度M1和分布性测试sd。收敛性是实际解集与理论解集的最短距离的平均值，这个值越小说明其收敛性越好。分布性测度是个体间距离的标准差，标准差越小，说明实际解集中个体分布越均匀，个体间的距离相近。

假设实际解集为Y'，理论解集为 ，定义：

假设解集中个体数为n，di表示个体i到其他个体的距离的最小值， 是di的平均值，定义： 。

实验结果如图1，改进后的算法得到的Pareto前沿与真实前沿曲线基本吻合，由表1可发现NSGAboa算法与NSGAⅡ相比，在收敛性和分布性上有很大的改进。

5 结论

MSGAⅡ引进快速非支配排序算法并根据拥挤度选择优异个体，在保持种群个体多样性的前提下降低了复杂程度，使最优解分布更均匀。贝叶斯优化算法根据多目标优化问题的实质，将变量之间的关系量化，估计概率模型，用非占先排序及拥挤度来选择优异个体。MSGAⅡ关注的是种群中的个体信息，而贝叶斯优化算法则充分考虑了种群的全局信息。本文将两种算法结合，根据种群中个体间的分布收敛程度来改变个体的产生方法。通过实验证明这样做产生了显著的效果，结合产生的新算法NSGAboa加快了个体产生的速度，提高了算法的性能，在收敛性和分布性上有了很大的提高。对于资源消耗、负载均衡、种群初始化等问题本文没有进行过多的考虑，还需进一步深入研究。

[参考文献]

[1]徐小龙，程春玲，熊婧夷，王汝传.一种基于移动Agent的云端计算任务安全分割与分配算法[J].北京理工大学学报，2011，31（8）：922-926.

[2]曹萌萌.基于云计算的调度算法的研究与改进[D].南京邮电大学， 2012.

[3]史恒亮.云计算任务调度研究[D].南京理工大学，2012.

[4]江敏.贝叶斯优化算法的若干问题研究及应用[D].上海大学，2011.

[5]KRUATRACHUE B，LEWIS T.Grain size determination for parallel processing [J].IEEE Software，1988，5（1）：23-32.

[6]SEHADRI A，Multi-objective optimization using evolutionary algorithms（MOEA）[J].IEEE Transactions on evolutionary Computation，2002，Volume 6，Issue 5，：526-526.

[7]陈静.改进的非支配排序多目标遗传算法及应用[D].湘潭：湘潭大学，2009.

[8]PELIKAN M，GOLDBERG D E，CANTUPAZ E B：The bayesian optimization algorithm[C].Proceedings of the Genetic and Evolutionary Computation Conference，Orlando，Florida， USA.1999：525-532.

[9]王浣尘.可行性研究和多目标决策[M].北京：清华大学出版社，1995.

[10]LARRANAGA P，LOZANO J.Estimation of distribution algorithms：A new tool for evolutionary computation[M]. Holland：Kluwer Academic Publishers：2002.

[11]张林，罗晓初，徐瑞林，赵理.基于时间序列的电力负荷预测新算法研究[J].电网技术，2006-12-30.

[12]李小俊，熊励.基于对称点对序列的带状图骨架化算法研究[J].计算机工程与应用，2006-10-21.endprint

函数1：

函数2：

函数3：

其中，n=50， 。

在多目标优化问题测试中，我们选取的测试目标有两个：收敛性测度M1和分布性测试sd。收敛性是实际解集与理论解集的最短距离的平均值，这个值越小说明其收敛性越好。分布性测度是个体间距离的标准差，标准差越小，说明实际解集中个体分布越均匀，个体间的距离相近。

假设实际解集为Y'，理论解集为 ，定义：

假设解集中个体数为n，di表示个体i到其他个体的距离的最小值， 是di的平均值，定义： 。

实验结果如图1，改进后的算法得到的Pareto前沿与真实前沿曲线基本吻合，由表1可发现NSGAboa算法与NSGAⅡ相比，在收敛性和分布性上有很大的改进。

5 结论

MSGAⅡ引进快速非支配排序算法并根据拥挤度选择优异个体，在保持种群个体多样性的前提下降低了复杂程度，使最优解分布更均匀。贝叶斯优化算法根据多目标优化问题的实质，将变量之间的关系量化，估计概率模型，用非占先排序及拥挤度来选择优异个体。MSGAⅡ关注的是种群中的个体信息，而贝叶斯优化算法则充分考虑了种群的全局信息。本文将两种算法结合，根据种群中个体间的分布收敛程度来改变个体的产生方法。通过实验证明这样做产生了显著的效果，结合产生的新算法NSGAboa加快了个体产生的速度，提高了算法的性能，在收敛性和分布性上有了很大的提高。对于资源消耗、负载均衡、种群初始化等问题本文没有进行过多的考虑，还需进一步深入研究。

[参考文献]

[1]徐小龙，程春玲，熊婧夷，王汝传.一种基于移动Agent的云端计算任务安全分割与分配算法[J].北京理工大学学报，2011，31（8）：922-926.

[2]曹萌萌.基于云计算的调度算法的研究与改进[D].南京邮电大学， 2012.

[3]史恒亮.云计算任务调度研究[D].南京理工大学，2012.

[4]江敏.贝叶斯优化算法的若干问题研究及应用[D].上海大学，2011.

[5]KRUATRACHUE B，LEWIS T.Grain size determination for parallel processing [J].IEEE Software，1988，5（1）：23-32.

[6]SEHADRI A，Multi-objective optimization using evolutionary algorithms（MOEA）[J].IEEE Transactions on evolutionary Computation，2002，Volume 6，Issue 5，：526-526.

[7]陈静.改进的非支配排序多目标遗传算法及应用[D].湘潭：湘潭大学，2009.

[8]PELIKAN M，GOLDBERG D E，CANTUPAZ E B：The bayesian optimization algorithm[C].Proceedings of the Genetic and Evolutionary Computation Conference，Orlando，Florida， USA.1999：525-532.

[9]王浣尘.可行性研究和多目标决策[M].北京：清华大学出版社，1995.

[10]LARRANAGA P，LOZANO J.Estimation of distribution algorithms：A new tool for evolutionary computation[M]. Holland：Kluwer Academic Publishers：2002.

[11]张林，罗晓初，徐瑞林，赵理.基于时间序列的电力负荷预测新算法研究[J].电网技术，2006-12-30.

[12]李小俊，熊励.基于对称点对序列的带状图骨架化算法研究[J].计算机工程与应用，2006-10-21.endprint

函数1：

函数2：

函数3：

其中，n=50， 。

在多目标优化问题测试中，我们选取的测试目标有两个：收敛性测度M1和分布性测试sd。收敛性是实际解集与理论解集的最短距离的平均值，这个值越小说明其收敛性越好。分布性测度是个体间距离的标准差，标准差越小，说明实际解集中个体分布越均匀，个体间的距离相近。

假设实际解集为Y'，理论解集为 ，定义：

假设解集中个体数为n，di表示个体i到其他个体的距离的最小值， 是di的平均值，定义： 。

实验结果如图1，改进后的算法得到的Pareto前沿与真实前沿曲线基本吻合，由表1可发现NSGAboa算法与NSGAⅡ相比，在收敛性和分布性上有很大的改进。

5 结论

MSGAⅡ引进快速非支配排序算法并根据拥挤度选择优异个体，在保持种群个体多样性的前提下降低了复杂程度，使最优解分布更均匀。贝叶斯优化算法根据多目标优化问题的实质，将变量之间的关系量化，估计概率模型，用非占先排序及拥挤度来选择优异个体。MSGAⅡ关注的是种群中的个体信息，而贝叶斯优化算法则充分考虑了种群的全局信息。本文将两种算法结合，根据种群中个体间的分布收敛程度来改变个体的产生方法。通过实验证明这样做产生了显著的效果，结合产生的新算法NSGAboa加快了个体产生的速度，提高了算法的性能，在收敛性和分布性上有了很大的提高。对于资源消耗、负载均衡、种群初始化等问题本文没有进行过多的考虑，还需进一步深入研究。

[参考文献]

[1]徐小龙，程春玲，熊婧夷，王汝传.一种基于移动Agent的云端计算任务安全分割与分配算法[J].北京理工大学学报，2011，31（8）：922-926.

[2]曹萌萌.基于云计算的调度算法的研究与改进[D].南京邮电大学， 2012.

[3]史恒亮.云计算任务调度研究[D].南京理工大学，2012.

[4]江敏.贝叶斯优化算法的若干问题研究及应用[D].上海大学，2011.

[5]KRUATRACHUE B，LEWIS T.Grain size determination for parallel processing [J].IEEE Software，1988，5（1）：23-32.

[6]SEHADRI A，Multi-objective optimization using evolutionary algorithms（MOEA）[J].IEEE Transactions on evolutionary Computation，2002，Volume 6，Issue 5，：526-526.

[7]陈静.改进的非支配排序多目标遗传算法及应用[D].湘潭：湘潭大学，2009.

[8]PELIKAN M，GOLDBERG D E，CANTUPAZ E B：The bayesian optimization algorithm[C].Proceedings of the Genetic and Evolutionary Computation Conference，Orlando，Florida， USA.1999：525-532.

[9]王浣尘.可行性研究和多目标决策[M].北京：清华大学出版社，1995.

[10]LARRANAGA P，LOZANO J.Estimation of distribution algorithms：A new tool for evolutionary computation[M]. Holland：Kluwer Academic Publishers：2002.

[11]张林，罗晓初，徐瑞林，赵理.基于时间序列的电力负荷预测新算法研究[J].电网技术，2006-12-30.

[12]李小俊，熊励.基于对称点对序列的带状图骨架化算法研究[J].计算机工程与应用，2006-10-21.endprint