基于改进遗传算法的网格资源调度研究

【摘 要】本文借鉴了面向分组的调度算法的优点，深入分析了遗传算法中编码串各个位的权重特点及个体的模式规律，对传统遗传算法进行了改进，新的算法具有面向分组、有针对性、同时又能够借助优良个体特征模式进行变异的特征，所以能够自适应地、并且有方向性地进行变异，从而增加了种群的多样性、提高了收敛速度。通过在本文后面的对比实验，证明了当标准遗传算法（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个资源并安排好它们的执行顺序，使整个任务的完成时间最短。