基于实数编码遗传算法的网格任务调度

摘要：网格任务调度的目的是快速找到全局最优解。将多个任务合理地分配给有限的资源，使得整个任务的完成时间较短。文中提出了一种基于实数编码遗传算法的网格任务调度算法。通过仿真实验证明了该算法有较好的收敛速度。

关键词：任务调度；网格；遗传算法

中图分类号：TP393文献标识码：A文章编号：1671—1580（2013）01—0151—02

1 问题描述

网格任务调度就是把组成并行程序的一组相关的任务或构成工作负载的一组作业，按照一定时序分配到网格的多个资源上，并且安排好每一个计算节点上任务的执行顺序，以获取较好的系统执行性能。为了简化调度过程，文中以简单的网格任务为例，只考虑任务间的约束关系、任务的计算时间和资源分配策略，忽略执行任务时产生的延迟和资源之间传输数据的延迟等，在建模时，各个任务的先后顺序可采用有向无环图（DAG图）来表示。

具体描述如下：

2 算法设计与分析

2.1 遗传算法简介

遗传算法操作对象是一群二进制串（称为染色体），即种群，每个染色体都对应问题的一个解，从初始种群开始，采用基于适应值比例的选择策略在当前种群中选择个体，使用交叉和变异来产生下一代种群，直到满足期望的终止条件。

2.2 改进算法设计

2.2.1染色体编码

文中采用的是整数编码方案，将任务分解成若干个子任务，并且将子任务按照一定的顺序排序，同时，对网格中所有可用的资源按照速度由慢到快的顺序进行排序编号。假设有n个资源，用数值1到n对每个资源进行编号。子任务的排列顺序是固定的，子任务的顺序可以根据DAG图来确定。这样，我们就可以得到一个由任务和资源构成的整数序列。假设有6个子任务，3个资源。子任务的顺序是：M1，M3，M2，M5，M4，M6；对应的资源序列是：3，2，1，3，2，2。

2.2.2种群的初始化

种群的初始化文中采用随机方式产生。初始种群规模为POSIZE，子任务个数为chromlength，资源个数为Rs，遗传因子（即每个子任务占用的资源编号）在资源个数Rs的范围内进行选取。

2.2.3适度函数

在遗传算法中，群体中各个个体的优劣程度是通过适应函数来度量的。根据以上的编码方案，我们很容易就能够得到每一个资源上运行的子任务集合。因此，就可以得到每一个资源完成所有给它分配的子任务所需要的时间，所需运行时间最久的资源的运行时间就是该任务序列的完成时间，我们将适应函数表示为：

2.2.4精英选择

根据适应度的大小，文中采用轮赌盘选择后代。由于选择操作具有随机性，适应度好的个体也有可能产生不了后代，而适应度差的个体可能被选择进行繁衍。为了避免这种情况的发生，文中采用精英选择法，即将种群中最优秀的个体直接复制到下一代，将最差的个体淘汰。这样可以避免优秀的个体经过选择、交叉、变异等操作，失去较好的基因。

2.2.5交叉

遗传算法中，交叉操作起着核心的作用，交叉操作可以改变两个父代的部分基因，并将它们组成新的个体。文中改进后的遗传算法交叉概率在0.85，交叉概率越大，群体中的染色体更新就越快。但是，概率太大，较好的个体容易遭到破坏，反而影响达到最优解的速度，有时候甚至不能达到最优解。交叉操作的具体描述如下：

（1） 随机产生一个[0，1]之间的数值，用该数值与交叉概率进行比较。可以挑选出参加交叉的个体集合和不参加交叉的个体集合，并将交叉个体集合中群体个数调整为偶数。

（2） 随机产生长度为n的0，1序列，n为染色体（即子任务）的个数。随机产生的0-1序列与染色体一一对应，0表示该位置的子任务所占用的资源需要和下一条染色体中的相应位置子任务所占用的资源对换。1表示表示该位置的子任务所占用的资源需要和下一条染色体中的相应位置子任务所占用的资源不进行对换。

（3）将交叉后的个体集合与不参加交叉个体的集合一起组成新的集合。

2.2.6变异

通过变异操作，可以保障群体的多样性，提高遗传算法局部搜索的效率。遗传算法中变异率的取值一般受种群的大小、子任务的多少等因素影响。由于变异概率较低，一般取值范围在0.001～0.1之间。文中变异概率为0.08，文中对传统的变异进行了改进，传统的遗传算法随机产生一个变异位，将该变异位中的基因值进行翻转，由0变为1或者1变为0。文中对变异操作进行了改进：首先，需要对资源集合R根据资源由慢到快进行排序，然后随机生成一个变异位，将该变异位上的资源编号改为比现有资源更快的资源。这样不仅提高了种群的多样性，还能得到更优秀的任务序列。

3 实验仿真

本文在Window XP系统上，选择Matlab工具进行模拟仿真实验。算法所用到的参数如下：种群的大小为200，迭代次数为200，交叉概率为0.6，变异概率为0.2。当资源数为5，任务数为100时，进化代数和适应度之间的关系如图1所示。

图1 进化代数和适应度关系图2 不同任务数在4个资源之间的调度

图2是在资源数一定的情况下，通过改变任务数所模拟出的实验结果。从实验结果中，我们可以看出，改进后的遗传算法的任务完成时间比传统的遗传算法少。图3是在任务数一定的情况下，通过改变资源的数量，所模拟出的实验结果。从实验结果中我们可以看出，改进后的遗传算法的任务完成时间比传统的遗传算法少。

图3 200个任务在不同资源之间的调度

通过仿真实验，我们可以看出虽然传统的遗传算法和改进后的遗传算法在刚开始收敛速度相近，但是随着进化代数的增加，可以明显地看出传统的遗传算法收敛速度比改进后的慢，适应度也比改进前的大。并且改进后的遗传算法能够缩短整个任务的完成时间。

[参考文献]

[1]赵英，李栋.改进的Min-Min网格任务调度算法[J].电子设计工程，2012（13）.

[2]刘芳芳.基于改进进化算法的网格任务调度研究与实现[D].南京信息工程大学，2012.

[3]傅明，贾亚红.基于遗传算法的网格任务调度研究[J].网络安全技术与引用，2007（11）.

[4]丁瑞，庄毅，黄福兴.一种基于改进遗传算法的网格资源调度策略[J].计算机工程与应用，2008（15）.

[5]徐娟，王景华等.基于小生境遗传算法的网格任务调度[J].计算机工程，2010（21）.