基于改进遗传算法的网格任务调度模型构建

潘利强+张燕琴

摘要摘要：网格任务调度属于一个NP完全问题，传统遗传算法很难将这一多对象问题求得最优解。通过生成节点性能评估函数及构建任务动态调度模型，经由函数参数权重值调节，可实现将多对象问题转化为单一对象问题，并对遗传算法的杂交算子和变异算子进行优化，以实现全局最优解的求解。

关键词关键词：网络技术；任务调度；遗传算法；调度模型

DOIDOI：10.11907/rjdk.162355

中图分类号：TP302文献标识码：A文章编号文章编号：16727800（2017）001001803

引言

网格技术以分布式计算为算法基础，解决了跨终端的任务分配与调度及资源共享问题[1]。目前的网格任务调度主要是利用遗传算法的动态迭代机制以及并行搜索的特点进行的，但存在着诸多问题。本文提出构建一个动态的任务调度模型，根据具体调度任务调整节点的性能参数及其权重值，以实现将多对象约束问题转化为单一对象问题，并将传统遗传算法的杂交算子及变异算子进行优化，实现全局最优解的求解。

1问题描述

在网格任务调度模型中，遗传算法容易陷入两大问题，其一便是容易陷入局部最优问题。众所周知，网格中的任务调度问题是一个多对象约束问题，也即是说，是一个NP完全问题[2]。因此，想要在一个NP完全问题中取得全局最优解，通常比较困难。既然如此，想要控制模型求解不陷入局部最优，而总是能够使其取得全局最优的结果，则需要对模型针对的问题进行一定程度上的优化。将这一多对象问题，转化为单一对象问题，问题则迎刃而解。然而，单对象约束问题很难达到网格调度模型期望的动态性。因此，必须引入一个动态调度函数，用以评估每个目标的不同需求，从而根据每个节点的性能参数得出期望中的调度模型，并对原有算法进行优化，以达到最终目标。

2动态调度模型构建

2.1节点性能评估函数ENPF生成

若要使一个属于NP完全问题的多目标异构问题能够保证得到全局最优解，需要引入一个网格系统中资源节点的性能函数。该函数既能够深刻刻画各节点性能，又能够根据用户的不同偏好和具体任务的不同需求进行用户定制[3]。要评估某个节点的性能，除了一些已知的性能参数外，还要考虑以下3个关键因素：

（1）与时间有关，称为活跃度，或者疲劳度，记为TINj。当此时间函数值越高，也即是说，就此网格节点而言，自上次完成任务到当前的时间间隔越长，此网格节点的动态性能评价越低。

（2）与节点使用频度有关，称为历史记录，记为CINj。此指标衡量源于对网格计算中针对任务贡献资源的节点所创立的激励机制，也即是说，对于向任务处理提供资源的节点，给予一定程度的激励回报或费用奖励，其具体方程式为：CINj=1-∑iCi∑iC0（1）其中，∑iCi为网格节点Pj以往所有成功完成任務中的执行时间总和；∑iC0为网格节点Pj以往所有成功完成任务中预计所需的执行时间总和。

（3）网格节点的动态累计可用性Uj，参数定义为：当节点在网格系统中处于可用状态时，此网格节点具体执行任务的时间比例。当网格系统中的某资源节点在某网格任务的接受和处理过程中处于可用状态时，此网格资源节点的可用时长累计为TA （Time of Available），相应的此网格节点的任务执行时长可累积计为TE（Time of Execution）。因此，网格节点的可用性定义如下：Uj=TEpj/TApj（2）其中，Uj为节点Pj的可用性，TEpj、TApj为网格资源节点Pj的执行时间与可用时间。

以上3个要素可以基本控制和调节不同用户、不同具体任务的不同需求，在节点性能评估函数ENPF（Estimate of Node Properties Function）Ej中，节点以上3项要素具体参数值的考量比例由其3个参数值前赋予的权重值决定，3个权重的取值不同，可以影响模型得到不同的最优解，更加能够满足用户和具体任务的需求。根据以上分析，网格中动态节点性能评估函数ENPF（Estimate of Node Properties Function）Ej为：Ej=α×e-TINj+β×CINj+γ×Uj（3）其中，α、β、γ为3个参数的权重值，它们满足下式：α+β+γ=1

0<α，β，γ<1（4）2.2动态调度模型构建

一个网格系统中要进行动态的任务调度，首先要设计一个任务调度池，记为S。接着，要明确模型所解决的问题，即：一个网格系统G拥有多个网格资源节点，以及多个需要其解决和处理的任务。现在需要将这多个任务分配到多个网格内的资源节点上，每个任务可以分配给多个节点协同处理。期望完成的效果是：将任务分配给多个节点，尽可能提高每个节点的处理效率，使任务的调度和完成效率能够达到令人满意的效果[4]。

对此多对象的异构问题进行分析并用数学语言进行描述，即为：已知网格G中拥有任务数n个，计为ai；此网格资源节点集计为A；网格G中拥有网格资源节点m个，计为pj。现将网格系统中有关任务调度效率的几个关键因素分别进行设置。

在网格系统上的任务调度过程中，任务ai在节点pj上的各项指标为：①网格任务调度长度L；②网格任务调度所得的网格节点性能值E；③节点调度代价C。 此外，对于文中涉及的各个变量脚标max与min，分别代表其相应的最大、最小值。这几个关键因素对应的多对象约束函数如下：min（L）=∑ni=1∑mj=1λijLij（5）

max（E）=∑ni=1∑mj=1λijEij（6）

min（C）=∑ni=1∑mj=1λijCij（7）其中，λij的取值为：当任务ai在节点pj上的运行时间tij>0时，λij=1； 否则，λij=0。Lij=fj+gij+tij（8）其中，fj为网格系统节点pj的可用时长，gij为节点间的通信耗时，tij为节点的任务执行时长。因此，求解目标问题的多对象约束，即可归纳成上述约束方程组。

该多对象问题在求解时难以达到全局最优，为保证得出全局最优解，要将问题改进成一个单一对象问题，即要引入上文生成的网格节点性能评估函数Ej。

在遗传算法的种群调度过程中，根据网格节点性能评估函数，将以上3项性能指标参数进行改进。任务ai在节点pj上的各项指标为：①网格任务调度长度LM；②网格任务调度所得的网格节点性能值Ej；③节点调度代价CM。

在IMPGA的种群调度过程中，其中：LMij=Lij-LMminLMmax-LMmin（9）

CMij=λij-Cminλij（10）于是最初确定的需解决的目标问题，多对象网格任务调度模型即可转化为一个单一对象问题，得到目标方程为：min（x）=∑ni=1∑mj=1[ω1Lij+ω2（1-Eij）+ω3Cij]

=∑ni=1∑mj=1[ω1LMij+ω2（1-Eij）+ω3CMij（11）其中，ω1+ω2+ω3=1，0<ωθ<1，（θ=1，2，3）。此时，当用户具有特殊节点性能偏好或具体任务在某些性能上有特殊要求时，只需通过调整权值ω1、ω2、ω3，即可满足用户的定制需求。

3算法改进

3.1算法原型

目标问题为异构网络环境下的任务调度，因此需要考虑网格环境中每一个节点的性能和链路状态，以及它的历史供求关系，以此判断节点的目前状况。这些可以用节点的各项性能参数来表示[5]。

遗传算法构造网格控制中任务动态调度的生成模型，以生成适用于具体任务的任务动态调度，以期在满足任务安全性要求的基础上，达到满意的任务完成效率和资源利用率。针对目标问题的实时性等，以及网格计算的多对象特点，利用遗传算法动态迭代的种群进化机制和搜索特点，构造具有动态特点的任务动态调度生成模型。针对具体任务，通过区间划分、构造遗传算法的适应度函数，确定编码方式以及边界条件；初始化网格平台上的算法种群，在操作过程中，模型还可将可用的优秀染色体在不同的子种群间交换和共享；将各子种群分配至网格的各个集群、节点上，进行选择、交叉和进化操作[6]；确定策略组合，生成合适的任务动态调度。因此，遗传算法是动态调度模型的算法实现原型。

3.2杂交算子优化

不同于传统遗传算法GA中的杂交算子，本文中利用新型的交换策略将其进行模交换。由于此时的代码段不属于任何一个父代个体，而取模行为也不会出现异于种群遗传因子的子代个体，因此可以达到增加搜索广度的目的[7]。

在改进遗传算法中，笔者对作为最主要搜索算子的杂交算子进行改进，改进后的杂交算子意在增加算法的搜索广度，具体实现方法为：在杂交过程中，对父代中两个个体对应位上的值相加后采用模运算求余，从而得到子代个体[8]。

3.3变异算子优化

传统遗传算法的任务调度易陷入局部最优解，在改进的遗传算法中引入起辅助作用的变异算子并对其进行改进，以期增加种群多样性，从而实现改进算法所得解达到全局最优[9]。考虑该变异算子作为辅助算子应具有简单易行的特点，本算法将传统变异算子作以下简单优化，改进为一个均匀变异算子，即可满足要求。设k=（k1，k2，...，kn）为参加变异操作的父代个体。具体实现方法如下：①以均匀概率选取随机数xi∈[1，q]，（i∈N，i∈[1，n]），i从1至n依次取值；②以xi替换ki；③返回步骤①直至i=n结束。从而得到新个体x=（x1，x2，...，xn）为变异后的子代个体。

此改进变异算子不仅简单易行，又可对个体生成产生扰动，增加了种群多样性，有助于避免改进遗传算法所得解陷入局部最优，这一点可以通过改进遗传算法的收敛性来证明。

4结语

在网格的异构环境中，任务调度是一个受多方因素影响、多对象约束的NP完全问题。本文为实现求得全局最优解的目标，提出了一个用来调节网络节点性能的评估函数，并构建了一个任务动态调度模型，将多对象约束问题转化为单一对象问题。同时，对传统遗传算法的杂交算子和變异算子进行改进，从而扩充了算法的搜索广度，实现了网格任务的动态调度，并且求得全局最优解，提高了任务执行效率和资源利用率。

参考文献参考文献：

[1]桂小林.网格技术导论[M].北京：北京邮电大学出版社，2005：115127.

[2]J HERRERA，E HUEDO，R MONTERO，et al.A gridoriented genetic algorithm[C].In Advances in Grid ComputingEGC，2005： 315322.

[3]D LIM，Y ONG，Y JIN，et al.Efficient hierarchical parallel genetic algorithms using grid computing[J].Future Gener.Comput.Syst.，2007，23（4）：658670.

[4]JUDITH MYERSON.Grid computing and cloud computing[Z].IBM Web Development，2008：13.

[5]CHALES J MALMBORG.A genetic algorithm for service level based vehicle scheduling[J].European Journal of Operational Research，1996（93）：121134.

[6]刘丽，杨扬.基于QoS的社区公共服务网格资源调度[J].北京科技大学学报，2004，26（5）：560563.

[7]方勇，刘嘉勇.信息系统安全导论[M].北京：电子工业出版社，2003：7895.

[8]顾恺恺，姚黎，袁家斌.基于安全控制策略的网格安全技术研究[J].中国制造业信息化，2006，35（15）：3387.

[9]陈琛，洪流，陈学广，等.基于网格的遗传算法及其在公交运行计划编制中的应用研究[J].计算机学报，2009，32（12）： 23822388.

责任编辑（责任编辑：黄健）