文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于改进免疫遗传算法的网格任务调度
侵权投诉

基于改进免疫遗传算法的网格任务调度

第 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页

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email