第 2期
张京军等:基于改进免疫遗传算法的网格任务调度
8 l
在算法执行之前,任务信息、资源信息以及任务在 相应资源上的执行时间都是已知的。假定 G表示 一
复制操作按照公式 ( 3 )进行。 t = .
t
6+:Ⅳ( 0, 1 ) , 1、
( 3 )
个网格系统,由 G={ T, P, E}这样的三元组进
式中:”一子代个体第个分量; t 一父
行定义:
定义 1任务集合 T={ t , t ,…t },资源节点 集合 P={ P , P:,…P }; 定义 2任务的估计执行时间用一个 n× 矩阵 E( t , P i )表示,对 P的所有资源分配所形成 的矩阵 E表示为 E =E( t , p ); 1 i n, 1≤ m o
代个
体第i个分量;” = t e x p f卜 .父代群体 、 ,
第i个分量的标准差,分母一总进化代数,分子 A 标准差动态调整系数, t一当前进化代数; N( 0, 一
1 )一服从标准正态分布的随机数; 步骤 5:计算由公式 ( 3 )进化生成的个子代群体中每个个体的适应值,确定最优个体 t+ l,比较与父代最优个体的适应值,若满足 F( ; )≥F .
用b e g i n ( P )表示任务 t 被派送到计算资源 P 执行的开始时间, in f i s h ( t , P )表示任务 t 在计算资源上的完成时问,则有: in f i s h ( t , P f ):b e g i n ( P f )+ E( t i, P ) ( 1 )
( t ),则选择 t + l 为最优个体,否则,最优个体仍保留父代的 t ; 步骤 6:迭代的执行步骤 3— 5,直到满足终止 条件,输出最后一代的最优解。 2 . 2改进免疫遗传算法实现过程
设 C A P( j )表示在调度策略 A下,计算资源 P 完成分配到该资源上的最后一个子任务所需的时间。若 c( A)表示在调度策略 A下任务完成所花 费的总时间,则 C ( A)=似 ( C . p ( j ), V1<i<m) ( 2 )
蚁群算法( A n t C o l o n y O p t i m i z a t i o n )其原理是 通过蚂蚁群体之间的正反馈信息传递机制而达到寻优目的。将蚁群算法作为一个算子加入到免疫遗传算法中,利用蚁群算法的并行性以及求解高
网格任务调度要解决的问题就是找到一个调度策略 A,使得 c( a)最小。
2任务调度算法的优化 2 . 1免疫遗传算法
效性等特征进行全局搜索,避免了单纯的免疫遗传算法系统中反馈信息没有利用而导致的冗余迭代。算法调度流程如图 1所示。 算法的具体过程描述如下: 步骤 1:确定参数,初始化种群规模Ⅳ,变异概率P和最大迭代次数 G。 步骤 2:初始化抗体种群,在解空间中随机产生Ⅳ个抗体构成初始种群 P( 0 )={ a , a ,…, a }。 其中,每个初始抗体对应于一个满足网格任务调度约束关系的可
行调度方案,每个任务选择相应的资源节点映射,选择的原则是对该任务有较快执行速度的机器有较大的机会被选中。由于二进制编码会产生问题所不能接受的等位基因, 本文采用十进制的实数编码,抗体为 m位,每个基因位取值范围为 1一 n,表示为: A 6={ b 1, b 2,…, b}; l≤6 n ( 4 )
本文中,把网格任务调度优化问题抽象为抗 原,对应的每一个抗体就是一种可行的调度方案。 首先,根据网格任务调度问题的相关参数 G构造
算法的第一个染色体,并据此生产初始群体,而抗 原对应于调度问题的目标函数,抗体对应于调度
问题的候选解,算法的核心在于通过记录克隆变 异后所形成的最优个体信息来代替整个群体的进化,以减少网格计算任务调度总时问。 免疫遗传算法的具体实现过程如下: 步骤 1:随机生成群体规模为的初始父代 群体一引;
步骤 2:根据先验知识抽取疫苗,构造优化目 标函数;选择当前代中的最优解,确定初始最优个
体
.
及 M个初始群体分量 i分量的标准差取
步骤 3:对第代种群, 05 度值升序进行排列。
G 计算抗体
值; 步骤 3:判断当前种群中是否已包含最佳个
群中每个抗体的亲和度, i=1, 2,…,Ⅳ,并按亲和
体,若是则算法结束,否则进行以下步骤; 步骤 4:父代种群选取 i个分量进行复制,在解空问内生成种群规模仍为的新的子代群体,
步骤 4:对第 k代种群 P 的前 z个抗体实施克隆变异得到新抗体群,再次计算亲和度并排 序,选出A 中最好的抗体作为蚁群算法的初始信

任务图将每一个可能的任务调度方案表示成一个任务一资源分配图,将网格任务调度问题转化为任务一资源分配图优化选取问题.提出了一种基于免疫遗传算法的、实现任务一...
基于改进遗传算法的网格任务调度_专业资料。为在网格环境下完成任务调度,使服务运行时间和费用2个指标达到最优化,将这2个指标作为网格任务调度模型的衡量指标,将...
改进遗传算法在网格任务调度中的应用_专业资料。为了提高遗传算法的搜索性能,... 遗传算法在制造网格资源... 4人阅读 4页 2.00 基于免疫遗传算法的网格...
基于改进遗传算法的网格任务调度研究基于改进遗传算法的网格任务调度研究隐藏>> 第3卷7 第7期 计 算 机 科 学 210 0年 7月 Compue Scec trine Vo.7No713 ...
的遗传算法.采用理论分析与仿真实验相结合的方法,提出了一种改进的遗传算法解决网格的任务调度问题.这种遗传算法所处理的任务不仅可以包含多个有前后约束关系的子任务...
基于负载均衡的免疫遗传算法网格调度研究_信息与通信_工程科技_专业资料。内蒙古... 基于免疫遗传算法的网格... 3人阅读 4页 2.00 基于改进免疫遗传算法的...
基于遗传算法的网格任务调度方法研究_专业资料。文章提出了一种以资源代理为基础... 改进遗传算法在网格任务... 4人阅读 4页 2.00 基于改进免疫遗传算法的...
基于改进遗传算法的网格资源调度算法_专业资料。网格计算关注大规模的资源和任务调度,要求采用的调度算法能够具有高效性。提出一种基于改进遗传算法的资源调度算法,该...
基于改进遗传算法的网格资源调度策略算法_专业资料。网格的资源调度是网格的核心应用之一,是一个完全NP问题。遗传算法是解决任务调度的全局优化搜索算法。提出了一种...
基于改进遗传算法的网格资源调度策略算法研究_专业资料。提出了一种基于改进遗传算法的任务调度策略算法,该算法并将子任务按照层次深度排序,兼顾网格资源的运算能力。...
热门文档