基于遗传算法的网格资源分配与调度研究-科技论文发表

Research on Task Allcation Scheduling Based on  Genetic  Algorithm in Grid

Abstract: Reasonable resource scheduling can greatly improve the utilization of the grid.Based on the research of existing scheduling algorithms,this method described the adaptive selection probability combined with niche technology, PCC(Father And Son Competition) crossover operator and new mutation operator, improved GA algorithm, it keeps the population's convergence and increase the efficiency of local and global search capability. Simulation results show that this algorithm is more effective to the allocation of resources compared with other algorithms,it can be successfully applied to the independent task scheduling in grid .

Key words:grid; genetic algorithm;task scheduling;

1  引言

网格计算是当今互联网研究中的一个热点,也是并行和分布处理技术的一个发展方向；在网格环境中,任务调度是网格计算研究的核心问题. 在网格环境下的任务调度,常考虑的是一组相

互独立彼此间没有通讯和数据依赖的元任务的调度,称为独立任务调度,该模型应用于很多方面,比如定积分、生物上的DNA测序、无线传感器网络等,独立任务调度以时间跨度(makespan)为优化目标,其已经是一个众所周知的NP难题, 不存在多项式时间复杂性的算法找到全局最优解. 因此,研究网格下任务调度是一项很有意义的工作.

关于网格环境下独立任务的调度问题,国内外学者做了大量研究工作,先后提出了许多启发式调度算法.Min-Min算法^[1-2]尽量把更多的任务分配到执行它的速度最快并能最早完成它的机器上, 但可能导致系统负载很不平衡；Max-Min算法^[2-3]虽然能产生比较平衡的负载, 但由于有更多的任务没有分配到最佳的机器上, 其性能比Min-Min差.文献^[4]使用了分而治之的思想提出了一个分段Min-Min算法(SMM), 它首先把任务按最小完成时间从大到小的顺序排序, 然后把它们分成4段, 在每段内运行Min-Min算法, 这样在段间先保证了负载平均, 而段内保证有更多的任务被分配到其最佳的机器上,执行速度也更快. Suffrage算法^[5]计算每个任务的最小完成时间和次小完成时间的差值,选取所有任务中差值最小的任务和计算资源.以上经典的调度理论都是基于优先级确定性调度技术,以牺牲全局最优解来降低算法的时间复杂度.近年来,遗传算法(Genetic Algorithm , GA)因具有强大稳健的隐并行解空间搜索功能,被广泛应用于任务分配和调度问题的求解. 对GA的研究表明,收敛性和多样性的平衡是其改进的关键,因此，本文从初始种群、选择、交叉、变异入手改进GA的性能，使其成功应用于网格任务调度.

2  问题的描述

一个网格计算通常由m 台异构处理器组成, 有n 个独立任务要竞争使用处理器, 分配的目标是把这n个任务合理地分配到m台处理器上执行, 使总的执行时间最短. 由于网格环境是异构的,因此用一个n×m 矩阵EXT来表示任务的估计执行时间, 其中元素EXT(i,j)表示任务T_i在机器M _j上的估计执行时间.定义机器运行时间MAT_j为机器完成分配给它的所有任务所需的时间, 任务T_i在机器M_j的完成时间CT_ij= MAT_j+EXT_ij,任务Ti的最小完成时间MCTi是所有CT_ij中的最小值.

任务分配的目标是使具有最大运行时间的机器的运行时间最短:

3免疫遗传算法

3.1群体规模选择
　　合适的群体规模对遗传算法的收敛具有重要意义，群体太小难以求得满意的结果,群体太大则计算复杂.根据经验,群体规模一般取10-160.

3.2染色体表示

与文献^[1]中采用的表示方法相同,染色体采用直接编码的方案.假设任务数为n机器数m,染色体上的每个基因的位置编号代表任务编号, 染色体中的每个基因位表示一个任务,而每个基因位的值就是对应任务被分配的机器编号. 在这种表示方式中, 每个染色体就是一种分配方案,对应着一个调度长度.例如,任务数n=10,机器数m=3, 染色体（1,2,1,3,2,2,3,1,1,2）,表示第1台机器执行第1、3、8、9个任务,第2台机器执行第2、5、6个任务,第3台机器执行第4、7个任务，算法的初始种群采用随机方式生成.

3.3 与小生境技术结合的自适应选择概率

选择操作的目标就在于使种群中个体的适值增大，即提高解的性能，但由于在遗传算法执行的不同阶段，个体间差异也不同，若用相同的选择策略可能会导致问题的出现：1）当个体差异较大时，淘汰掉劣势个体也就意味着也遗失了存在于劣势个体中的部分优良基因；2）当个体差异很小时，使搜索趋于随机化而导致收敛速度慢。为了解决这些问题,将小生境技术引入到算法中,采用动态变化的自适应选择策略，小生境技术通过个体亲合力距离定义的排挤策略能够在算法的后期仍然维持较高的多样性。定义个体I_i(P_i1P_i2⋯P_in)和I_j(P_j1P_j2⋯P_jn)的亲合力:

n任务数m传感器数.

本文提出的个体亲合力不仅比较两个抗体相同基因位的数值是否相同,还计算出两基因位数值的差距,基因位之间最大差距为m-1. A(i,j)取值范围0～1,值越大,表示i, j 两个个体越相似,A(i,j)=1则表示i, j两者基因完全一致即任务分配策略相同, A(i,j)=0则表示i, j两者基因完全不同.当A(i,j)<VALVE（VALVE为亲合力比较阀值）,比较个体Ai 和个体Aj 的适应度大小,并对其中适应度比较低的个体处以罚函数:min(F(Ai),F(Aj))=Penalty ，其中Penalty 为一个很小的正数。自适应选择概率为^[6]：

p_c1=0.7,p_c2=0.3,由式（9）得最优个体的交叉概率1.0,当个体适应度等于平均值时，其交叉概率为0.7，当个体适应度小于平均值时，交叉概率为0.3.

3.4 交叉算子

交叉方法是模仿自然生态系统的双亲繁殖机理而获得新个体的方法,遗传算法的全局搜索能力能够得以飞跃地提高它可使父代不同的个体进行部分基因交换组合产生新的优良个体.交叉概率P_c较大时可以增强算法开辟搜索区域的能力,但会增加优良子代被破坏的可能性.若交叉概率较小,则遗传算法搜索可能陷入迟钝状态.研究结果表明, 应取为0.25-1.00之间对于基因串交叉可以采用部分匹配(PMX)交叉操作、顺序交叉(Ordered Crossover,OX)、循环交叉(Cycle Crossover,CX)等.

算法采用PCC（Parents and Children Competition）交叉算子,三个父代抗体互交叉产生六个子代抗体,从中择优选择三个最优抗体加入到抗体群,在生产子代的过程中综合更多(相对两父辈而言)父代个体的信息,提高了解空间搜索效率的同时还增强了收敛性.PCC交叉算子流程如下:

Step1 从抗体群中随机选取3个父抗体P_1,P_2,P_3,随机生成交叉位POS_i(1≤POS_i≤n);

Step2 将父抗体P_1,P_2,P₃从交叉位POS_i处拆分成2个基因段,例如父个体P₁被拆分后得到左段基因PL₁和右段基因PR;

Step3 将任一父代左段基因与不同父代的右段基因组合得到2个子代抗体,例如子代抗体C₁=PL₁+PR₂,C₂=PL₁+PR₃,经不同交叉组合得到六个子代抗体;

Step4 从六个子代抗体和三个父代抗体中竞争选取三个最优秀解.

3.5  变异算子

当前任务调度算法中可用的变异算子都为交换变异，即相互交换染色体中两个被选取的基因座之间的基因值，从而产生出一个新的调度列表。这种变异算子的最大缺点是容易产生无效染色体，这一缺陷降低了遗传算法在运行时特别是算法运行后期的局部搜索能力。算法将采用一种被称为插入变异的变异算子，其方法是先在染色体中随机选取两个基因座，然后再将其中的一个基因座插入到另一个基因座之后或之前。

3.6 最优保存策略 　

用历代最优个体替换掉当前群体中的最差个体, 使迄今为止所得到的最优个体不会被选择、交叉、变异等遗传运算所破坏. 其具体操作如下:

Step1 找出当前群体中适应度最高的个体和适应度最低及次低的个体.

Step2 若当前群体中最佳个体的适应度比历代最优个体的适应度高时,则复制当前群体中的最佳个体取代原先的最优个体而成为新的历代最优个体.

Step3添加一个与oldpop 种群的最优个体有较大的相异因子的个体,计算它的适应值,并将它与种群newpop 的次劣个体进行比较,若比次劣个体的适应值小的话,则不替换种群newpop 的次劣个体,反之则替换。

3.7  算法流程

step 1  将Min-Min算法产生的解加入随机在产生的初始种群、初始化控制参数和记忆库；

step2  根据公式（2）、（3）对种群实施选择操作,得到新的种群；

step3  对新的种群实施PCC交叉操作；

step4  执行变异操作；

step5  实施最优保存策略；

Step6  检验新一代群体适应度是否满足要求或是否已经满足最大世代数的要求,若满足则结束输出最优解,否则转向step2. 

4  对比实验和结果分析

4.1 不同算法性能的比较

对于上述设计的算法进行多个n个任务、m个处理器分配问题的仿真测试,所有仿真实验运行在P4 1. 8 GHzCPU、内存2GB的同一计算机平台上,采用MATLAB编程进行了实现.种群规模为50,表示任务的估计执行时间矩阵EXT随机生成,EXT（i,j）为1-100均匀分布的随机值,最大世代数为300.将本文算法与基本遗传算法（SGA）、文献^[7](Min-Min Genetic Algorithm)MMGA算法作比较, MMGA算法是将Min-Min算法生成的最优解作为初始种群的一个个体再与遗传算法结合, 每个问题各运行100次, 取其最小时间跨度的平均值,仿真实验结果如下.

表1：仿真实验比较结果(单位时间)

Tab.1 Comparison of simulation results (unit time)

图1   算法静态性能曲线(m = 128, n= 16)              

Fig.1  algorithm static performance curve

从表1和图1可以看出, 本文算法的性能明显优于SGA和MMGA ,SGA和MMGA由于采用最优保存策略，运行到较大代数时还是无法收敛,本文算法性能曲线在较短的时间内就快速收敛，随着运行代数的增加,而最小时间跨度曲线几乎保持水平一段时间,又陡降,曲线保持水平是因为收敛性缘故,而又突发陡降是采用新变异算子,增加抗体的多样性,在进化过程中找到了更优秀的抗体,表现出较强的局部搜索能力,以上特征充分说明了本文提出的算法是成功的.

5 结论

针对网格计算异构环境下独立任务调度问题, 本文改进遗传算法,继而提出与小生境技术相结合自适应选择概率来提高种群的收敛性、采用父子竞争(PCC)交叉算子和新的变异算子增强多样性，在空间探索和局部求精间取得了很好的平衡.仿真实验结果表明, 本文算法与传统调度算法比较,更能有效地实现资源的分配,可以成功应用于网格环境下独立任务调度.

参考文献：

[ 1 ] Braun T, Siegel H, Beck Netal. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems [ A ]. In: 8th IEEE Heterogeneous Computing Workshop [C].1999,15-29.

[2]Moreno R.Job scheduling and resource management techniques in dynamic grid enviroment[C]//1st European Across Grids Conference,2003.

[3]Yarkhan A,Dongarra J.Experiments with scheduling using simulated annealing in a grid enviroment[C]//Proc of Grid Computing,Baltimore,2002.

[4] Min-You Wu, Wei Shu, Hong Zhang. Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems [ A ]. In: 9th IEEE Heterogeneous  Computing Workshop [C ]. 2000, 375-385.

[5]Yarkhan A,Dongarra J.Experiments with scheduling using simulated annealing in a grid enviroment[C]//Proc of Grid Computing,Baltimore,2002.

[6]叶菁，张莹，阮一文.一种改进型交叉算子和自识别高变异算子新型遗传算法的研究[J].福州大学学报（自然科学版），2008（6）：808-811.

[7] 马景奕,隋兵,舒万能.基于Min-Min遗传算法的网格任务调度方法[J].计算机工程与应用.2008,44（23）102-104.