[基于改进遗传算法的网格资源调度研究]遗传算法matlab程序

摘 要本文借鉴了面向分组的调度算法的优点，深入分析了遗传算法中编码串各个位的权重特点及个体的模式规律，对传统遗传算法进行了改进，新的算法具有面向分组、有针对性、同时又能够借助优良个体特征模式进行变异的特征，所以能够自适应地、并且有方向性地进行变异，从而增加了种群的多样性、提高了收敛速度。通过在本文后面的对比实验，证明了当标准遗传算法（GA）调度算法与改进遗传算法（MGA）同时应用在相同（资源数和任务数相同）的网格调度系统中时，后者使网格调度的总体响应时间有了明显的减少；并且当调度的规模增大时，具有更好的性能。

关键词网格调度；遗传算法；GridSim；GridBroker；仿真

1网格资源调度简介

在网格系统中，调度是其重要的组成部分，它要根据任务信息采用适当的策略把不同的任务分配到相应的资源结点上去运行。由于网格系统的异构性和动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得资源调度变得极其复杂[1][2]。

一般的网格资源调度问题已被证明是一个NP完全问题[3][4]，因此引起了更多学者的关注，成为目前网格计算研究领域中的一个焦点[5]。

11 网格调度数学模型

该数学模型定义调度算法的主要术语，不假设不支持抢先调度。并且该模型是针对已经分解的应用，即假设应用已经分解成N个任务，这些任务之间的关系分为两种情况，即有依赖和没有依赖。为说明问题，本文只讨论简单的无依赖的情况，数学模型假设所有的机器都是调度器可以控制的，多个任务不能在同一个计算节点之上并发执行。

（1）自治域中存在着多个市场，每个市场可以看作是一个虚拟组织。借助文献[6]中的面向分组的思想，将多个任务相似的任务归类到相同的分组。

（2）自治域内网格节点间通信延迟较小；在本文中的一个创新想法的出处来自于文献[6]的面向粗粒度的调度算法，在面向粗粒度的调度中，运用了一种分组调度策略，将相似作业进行分组，再将分组提交到合适的运算资源。在建立模型的时候，在此思想的基础之上，引入分组的思想，有效地把遗传算法和分组（分区）结合起来，经本文后面部分的模拟实验验证，是一种有效可行的方法。

（3）网格自治域中的节点数维持在一个恒定的水平上；

由以上分析，抽象出如数学公式12所示：

公式12

12 抽象调度数学模型

h≥0 //任务j的需求量要大于0；

以上式中，N为一个市场（虚拟组织）中计算资源的个数；M为任务的个数；变量i用于指示网格计算资源；变量j用于指示任务；变量k用于指示评价指标；为任务j到计算资源i的单位运输成本；为任务j的需求量；为第k项因素在选择模型中的影响权重，在本文中它是由专家意见以及经验预测等获得的权重值；为整数变量，当=1时，表示第i个计算资源被选中，反之当=0时，表示未被选中。

2基于MGA的网格资源调度

21 改进遗传算法（MGA）

本文在深入研究了基于传统遗传算法后[7]，提出了一种面向分组的，并且基于优良个体特征方向来变异的变异算子。这样，可以改进传统遗传算法的一些缺陷，使其能够有目的地、自适应地、有方向地进行变异，以此增加种群的多样性并提高其收敛速度。

211 理论来源

在“模式定理”及“积木块假设”基础上，本文认为每一个个体之所以能够保持其优良与否的地位，原因就是其模式中具有一些一定的特征，对一般的二进制和级连交叉二进制编码来说，码的前面部分的变动使该个体在解空间内移动的范围(距离)比较大，而后面部分段却恰恰相反，它们只能使得个体的解空间在该个体附近稍作变动。

比如：在1011中，从左至右阶码分别为8，4，2，1，所以如果最左边的1变为0的时候，解空间的变化幅度就是8。而同是从1变为0，在最右边的1所能引起的解空间变化幅度是1。

所以，可以先找出一定的优良个体，然后从这些优良个体中提取一些特征模式，建立起来小环境，接下来让这些优良个体通过小（范围）区间的变异寻优，对于那些劣质个体，就需要借鉴优良个体的特征模式从而来进行较大区间的变异。实现有目的、带权重的变异。

212 总体思路

若有两个染色体：

A＝()

B=()

＝（）

则分段海明距（Segment-Hamming）：

只取染色体部分编码来计算两个体的海明距离。对种群进行交叉 *** 作后，从中选取一定数量的优良个体建立小环境。

通过上面的分析，可以看出，前段的编码对个体影响相对较大，因此，取前面一部分的编码用来计算两个体的分段海明距离。用这种方式来比较两个体是否在同一个小环境中，若有两个个体分段海明距离为零，则认为这样的个体是在同一小环境中，则只取其中一个作为这个小环境的代表。通过对种群中提出一定数量的这样的优良个体，能够建立起若干个小环境。对于这些小环境，在每个局部范围内进行变异搜索，采用后段编码进行穷举变异，找到每个小环境局部的最优(当然全局最优可能在其中)。

具体方法如下；如编码长为12位，若为111111111010，取分段海明距离为8(指前段，即加了下画线的那一段不作变异)，那么后面的4位码长可能就有24个个体，即从0000到1111，我们穷举这些个体(111111110000～111111111111)计算每一个的适应度，找出它们中的最优。

●适应度函数

本文模型是一个求最大值问题，为此建立如下适应度函数：

公式212适应度函数公式

其中，是网格调度的数学模型公式，其形式见12节。是是到当前所有代的最小值，且随着代数变化。

22 资源调度实现过程

由上节中的数学模型知：设参与调度的任务集合为S，S={S[0]，S[1]，…S[N-1]}，其中N为任务的总数，参与调度的异构机器集合为H，H={H[0]，H[1]，…H[M-1]}，其中M为机器的数量。如果我们以调度长度为优化性能指标，则任务分配与调度的目标是将这N个计算机任务分配给这M个资源并安排好它们的执行顺序，使整个任务的完成时间最短。

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

量子遗传算法是量子计算与遗传算法相结合的产物。

量子遗传算法对于遗传算法的优点，搜索范围更广,适应性更强,效率更高,效果更好。

首先要清楚常规潮流计算和最优潮流的不同，尤其是计算过程。

常规潮流计算是给定PV,PQ和平衡节点相应的已知条件，根据网络拓扑计算线路功率和网损等运行指标，所给定的条件不一定使电网的运行达到最优水平；并且在电力市场环境下这些条件是未知的。因此需要寻找最优的已知条件，使调度运行成本、安全性、稳定性等最优，即成为最优潮流。在寻找最优运行条件的过程就需要到如遗传算法等智能算法搜索或者数值方法如内点法等。

遗传算法与潮流计算的结合就是用遗传算法搜索最优运行条件。

现假定网损是判定最优与否的原则，即网损越小越优，同时定义遗传算法的适应度为一大数减去网损(即f=C-PL)将最小化问题转化为最大化问题；待求运行条件的个数为m；遗传算法的种群数为n。

由以上分析不难知道，最优潮流计算过程需要反复调用常规潮流计算，这也是计算耗时的原因。

若将遗传算法的收敛判据设定为相邻两代的最大适应度值趋于稳定，则结合过程如下：

（1）初始化：用遗传算法产生初始种群（n行m列），初始最优适应度为0。转（2）

（2）计算适应度：将产生的种群（已知条件）分别代入常规潮流程序，计算每个个体下的网损，从而得到每个个体相应的适应度值，保存最优适应度值。判定最优适应值变化情况，若|f2-f1|<ε（ε为一很小的正数），迭代终止，输出最优个体，否则转（3）。

（3）进行遗传算子的 *** 作：调用遗传算法的选择、交叉和变异 *** 作，从而得到新的种群。转（2）

根据以上三个基本步即可实现遗传算法与潮流计算的结合。

以上就是关于[基于改进遗传算法的网格资源调度研究]遗传算法matlab程序全部的内容，包括:[基于改进遗传算法的网格资源调度研究]遗传算法matlab程序、你好，遗传算法在网络编码中可以应用吗，还有就是遗传算法和量子遗传算法的本质区别是啥啊求回答啊、遗传算法程序与潮流计算程序怎么结合等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！