【摘 要】本文借鉴了面向分组的调度算法的优点，深入分析了遗传算法中编码串各个位的权重特点及个体的模式规律，对传统遗传算法进行了改进，新的算法具有面向分组、有针对性、同时又能够借助优良个体特征模式进行变异的特征，所以能够自适应地、并且有方向性地进行变异，从而增加了种群的多样性、提高了收敛速度。通过在本文后面的对比实验，证明了当标准遗传算法（GA）调度算法与改进遗传算法（MGA）同时应用在相同（资源数和任务数相同）的网格调度系统中时，后者使网格调度的总体响应时间有了明显的减少；并且当调度的规模增大时，具有更好的性能。
【关键词】网格调度；遗传算法；GridSim；GridBroker；仿真
1.网格资源调度简介
在网格系统中，调度是其重要的组成部分，它要根据任务信息采用适当的策略把不同的任务分配到相应的资源结点上去运行。由于网格系统的异构性和动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得资源调度变得极其复杂[1][2]。
一般的网格资源调度问题已被证明是一个NP完全问题[3][4]，因此引起了更多学者的关注，成为目前网格计算研究领域中的一个焦点[5]。
1.1 网格调度数学模型
该数学模型定义调度算法的主要术语，不假设不支持抢先调度。并且该模型是针对已经分解的应用，即假设应用已经分解成N个任务，这些任务之间的关系分为两种情况，即有依赖和没有依赖。为说明问题，本文只讨论简单的无依赖的情况，数学模型假设所有的机器都是调度器可以控制的，多个任务不能在同一个计算节点之上并发执行。
（1）自治域中存在着多个市场，每个市场可以看作是一个虚拟组织。借助文献[6]中的面向分组的思想，将多个任务相似的任务归类到相同的分组。
（2）自治域内网格节点间通信延迟较小；在本文中的一个创新想法的出处来自于文献[6]的面向粗粒度的调度算法，在面向粗粒度的调度中，运用了一种分组调度策略，将相似作业进行分组，再将分组提交到合适的运算资源。在建立模型的时候，在此思想的基础之上，引入分组的思想，有效地把遗传算法和分组（分区）结合起来，经本文后面部分的模拟实验验证，是一种有效可行的方法。
（3）网格自治域中的节点数维持在一个恒定的水平上；
由以上分析，抽象出如数学公式1.2所示：
公式1.2
1.2 抽象调度数学模型
h≥0 //任务j的需求量要大于0；
以上式中，N为一个市场（虚拟组织）中计算资源的个数；M为任务的个数；变量i用于指示网格计算资源；变量j用于指示任务；变量k用于指示评价指标；为任务j到计算资源i的单位运输成本；为任务j的需求量；为第k项因素在选择模型中的影响权重，在本文中它是由专家意见以及经验预测等获得的权重值；为整数变量，当=1时，表示第i个计算资源被选中，反之当=0时，表示未被选中。
2.基于MGA的网格资源调度
2.1 改进遗传算法（MGA）
本文在深入研究了基于传统遗传算法后[7]，提出了一种面向分组的，并且基于优良个体特征方向来变异的变异算子。这样，可以改进传统遗传算法的一些缺陷，使其能够有目的地、自适应地、有方向地进行变异，以此增加种群的多样性并提高其收敛速度。
2.1.1 理论来源
在“模式定理”及“积木块假设”基础上，本文认为每一个个体之所以能够保持其优良与否的地位，原因就是其模式中具有一些一定的特征，对一般的二进制和级连交叉二进制编码来说，码的前面部分的变动使该个体在解空间内移动的范围(距离)比较大，而后面部分段却恰恰相反，它们只能使得个体的解空间在该个体附近稍作变动。
比如：在1011中，从左至右阶码分别为8，4，2，1，所以如果最左边的1变为0的时候，解空间的变化幅度就是8。而同是从1变为0，在最右边的1所能引起的解空间变化幅度是1。
所以，可以先找出一定的优良个体，然后从这些优良个体中提取一些特征模式，建立起来小环境，接下来让这些优良个体通过小（范围）区间的变异寻优，对于那些劣质个体，就需要借鉴优良个体的特征模式从而来进行较大区间的变异。实现有目的、带权重的变异。
2.1.2 总体思路
若有两个染色体：
A＝()
B=()
＝（）
则分段海明距（Segment-Hamming）：
只取染色体部分编码来计算两个体的海明距离。对种群进行交叉操作后，从中选取一定数量的优良个体建立小环境。
通过上面的分析，可以看出，前段的编码对个体影响相对较大，因此，取前面一部分的编码用来计算两个体的分段海明距离。用这种方式来比较两个体是否在同一个小环境中，若有两个个体分段海明距离为零，则认为这样的个体是在同一小环境中，则只取其中一个作为这个小环境的代表。通过对种群中提出一定数量的这样的优良个体，能够建立起若干个小环境。对于这些小环境，在每个局部范围内进行变异搜索，采用后段编码进行穷举变异，找到每个小环境局部的最优(当然全局最优可能在其中)。
具体方法如下；如编码长为12位，若为111111111010，取分段海明距离为8(指前段，即加了下画线的那一段不作变异)，那么后面的4位码长可能就有24个个体，即从0000到1111，我们穷举这些个体(111111110000～111111111111)计算每一个的适应度，找出它们中的最优。
●适应度函数
本文模型是一个求最大值问题，为此建立如下适应度函数：
公式2.1.2适应度函数公式
其中，是网格调度的数学模型公式，其形式见1.2节。是是到当前所有代的最小值，且随着代数变化。
2.2 资源调度实现过程
由上节中的数学模型知：设参与调度的任务集合为S，S={S[0]，S[1]，…S[N-1]}，其中N为任务的总数，参与调度的异构机器集合为H，H={H[0]，H[1]，…H[M-1]}，其中M为机器的数量。如果我们以调度长度为优化性能指标，则任务分配与调度的目标是将这N个计算机任务分配给这M个资源并安排好它们的执行顺序，使整个任务的完成时间最短。
对任务分配与调度的影响因素归纳起来有四类，即任务间的约束关系、任务计算时间等时间属性、资源之间的数据传输延迟和数据分配策略。
结合数学模型，资源调度中的MGA算法应用要遵循如下步骤：
步骤1：初始化执行开销矩阵E和通信开销矩阵c；
步骤2：读入DAG图，生成每个子任务之间的逻辑关系；
步骤3：按照初始种群生成算法产生大小为N的初始种群；
步骤4：计算每条染色体的适应值；
步骤5：判断是否满足遗传算法的终止条件，如果满足，则停止计算，输出最优调度长度和对应的染色体。
●选择、交叉设计
用连续的整数为每一个计算资源赋一个ID号，采用二进制编码方法，编码位串的长度为计算资源的个数N，以N=8为例，则编码串00110100表示ID为3，4，6的计算资源被选中。
在本文中，选择算法过程为首先确定每个个体的适应度，然后选出最优个体直接进入下一代(精英保存策略)，再按照轮盘赌策略进行选择操作。
Selectionoperator() //选择
{
CopyBestChrom(newpop)//保存最优个体到newpop
select()；//轮盘赌策略
{…}
}
交叉算子采用两点交叉，交叉点的位置随机确定。经过交叉生成的两个个体，分别对它们计算适应值。如果生成的子个体的适应值大于父个体，则按照一定的概率替换父染色体。反之，则选择原种群中适应值最小的染色体比较，如果新子个体的适应值大于最低适应值，则替换原染色体；否则舍弃生成的子染色体，并重新选择父染色体进行交叉操作。本文采用的的这种交叉策略，这样有利于新个体的产生又不容易使遗传算法陷入早熟。
CrossoverOperator()//交叉操作
{for(i=0；i { random(pop，*parent1，*parent2)；//当前种群中随机抽取父代个体 cross(*parentl，*parent2，*ehild1，*child2，Pc)；//根据Pc确定交叉点，进行父代个体的交叉重组获取子代个体 insert(*childl，*child2，newpop)；//将新个体插入新种群 }} ●改进变异操作设计 本文变异操作采用前文提出的基于优良个体特征模式的方向变异算子，该算子通过计算种群个体的适应度，再从中抽出适应度较高的个体并分析、选择其特征基因位，然后将适应度较低的个体按照这些特征基因位进行变异，以控制种群的变异方向。实质上就是将某个子任务迁移到另一个资源上执行。为了防止子任务在迁移后，执行的时间增大而造成种群退化，在此规定，迁移后子任务占用的资源不是随机产生的，而是在除了该子任务目前占用的资源外的资源集中，选择使该子任务执行时间最短的资源，并将其迁移到该资源上进行执行。 该变异过程需要保证劣质个体的方向变异所用的码长和用来衡量的分段海明距离所用的码长和交叉点前段的码长不能相同，否则这种变异就成为了一种变相的交叉，会抑制种群的多样性，由此，在变异算子中给出其控制约束函数： CrossDMMutation 在此，Cross表示通过交叉算子获得的交叉位，DMMutation表示经过变异过程发生变异的位。 MutationOperatior()//变异操作 {Sort(pop)； //种群内个体按适应度大小进行排序 findbestpop()； //按比例选择出最佳个体放入newpop findworstpop()； //按比例选出最差个体放入worstpop int haiming=random()； //随机获取一个整数做为海明距离 mutation(oldpop，newpop，haiming)； //根据newpop与haiming对oldpop内个体进行变异操作，并将新产生的个体加入新种群} 改进后算法的好处显而易见：一方面，这样作可以增加种群的多样性，从而加大了其在解空间上的寻优能力，另一方面，这样作还增加了有方向的变异，目的明确，所以可提高算法的收敛速度。对于网格调度系统的总体响应时间的缩短起了十分重要的作用。 3.模拟实验 本论文采用GridSim模拟器进行仿真实验。 GridSim网格仿真模拟器是由Melbo- urne大学的网格计算和分布式系统实验室(GRIDS)领导的gridbus项目中开发的网格仿真工具集。 3.1 参数选择 在开始验证本论文提出的改进遗传算法前，要对遗传算法的参数进行设定，这包括种群大小，交叉概率，和变异概率的设定。对于交叉算子和变异算子，根据参考文献[8]的方法，选择按照DAG图结构的10个具有50个任务的作业进行实验，初始种群为100。可以发现在交叉概率取为0.74和0.76间时，适应度函数比较稳定，且是最优值，故在本实验中，取交叉概率为0.75。 同时对于变异概率，参考文献[8]实验表明只有设为0.01时能够收敛。如果选取比0.01大的变异概率，无论交叉概率为多大，都不可能收敛。所以本论文中把变异概率设为0.01。 对于初始种群大小设为100。 3.2 仿真代码嵌入 前面已经给出了改进算法的代码，现在需要将这些代码嵌入到模拟工具当中： 文献[9]对GridSim的Jar包里面一些主要类进行介绍，并指出： “对Gridbroker的Jar包部分的修改，就集中在对broker类的修改上了，因为这个类涉及到了算法的部分。”依据此，本文将上一章中设计的算法分别放入相应的broker类中。 用可视化工具Visualmodeler设置好资源数和任务数以及对应的属性，再自动生成Gridbroker所需要的JAVA文件。在本实验中设置两种情况： 1:3资源，20任务； 2:5资源，50任务； 前面已经分析了各个步骤的实现过程，下面给出改进遗传算法应用于网格调度的主调程序的伪代码： …//定义算法的控制参数（略） Void main(void)//主程序 { Generation=0： Generatelnitia1_Populatlon()；//产生初始群体 Ca1culate_object_value()；//计算目标函数值 Calculate_Fitness_Value()；//计算个体适应度 Find_Best_And_worst_Individual()；//找出最优和最差个体 while(generation generation++；//下一代 Selection_operator()；//选择操作 Crossover_operator()；//交叉操作 Mutation_operator()；//变异操作 Calculate_objectvalue()；//计算目标函数值 Ca1culate_FitnessValue()；//计算个体适应度 Find_Best_And_worst_lndividual()；//找出最优和最差个体 Perform_Evolution()；//最优个体保存 Output_TextReport()；//结果输出 } 3.3 实验结果及对比分析 实验结果如图3.3.1及图3.3.2所示。 由图3.3.1（3资源，20任务）看来，粗黑曲线大体均处于细黑曲线之下，这说明，当使用改进的MAG之后，算法的平均完成时间大部分情况下均要小于没有改进前。从而体现了改进遗传算法应用于网格资源调度更为有效。这种难点在图3.3.2中（5资源，50任务）得到了更明显的体现，在图3.3.2当中，不仅平均完成时间有明显的下降，并且可以看出粗黑色曲线更为平缓，这说明了当任务数和资源数同时增大即调度规模变大时，改进的MGA算法更趋于稳定。从而证明了改进算法比传统算法性能有了较大提升。为什么会有这种提升呢？笔者认为可以从以下几个方面来分析。 （1）在设计改进算法的时候，根据编码位的权重不同，进行了有目的的交叉和变异操作，这样可以大幅提高算法的性能，反映到实验结果上就是完成时间有了明显的缩短； （2）借鉴了面向粗粒度的分组调度算法，在改进算法中加入了面向分组的思想。与传统算法相对比，作业能以细分的形式执行并最终返还用户。该策略能有效减少开销，提高处理能力。 （3）根据模理定理，具有低阶和短定义距以及适应度高于平均适应度的模式在后代中将以指数级增长，在改进的遗传算法MGA中，对于劣质个体，是按优良个体的特征模式进行变异的，所以在一定程度上可以说优良个体就是那些具有适应度高于种群平均适应度模式的个体集合，这样加快了算法的方向制导速度；由于在MGA算法中采用了小环境技术，并且由上点分析可以知道劣质个体的变异不是随机的，而是据优良个体的特征模式所建立的小环境来进行有方向有目的的变异的，这样有利于种群的多样性形成，因此可以扩大其在解空间里的搜索能力，不易陷人局部最优。 参考文献： [1]都志辉,陈渝,刘鹏.网格计算[M].北京,清华大学出版社,2002:3-25. [2]罗红,慕德俊,邓智群,王晓东.网格计算中资源调度研究综述[J].计算机应用研究,2005,22(5):16-19. [3]Abraham A,Buyya R,Nath B.Nature’s Heuristics for Scheduling Jobs on Computational Grids.In:Proc of the 8th Int’l Conf.on Advanced Computing and Communications(ADCOM 2000).New Delhi:Tata McGraw-Hill Publishing,2000:45-52. [4]The DOE Common Component Architecture Project..cn/qkpdf/wany/wany201215/wany20121511-2.pdf" style="color:red" target="_blank">原版全文
