您好,欢迎来到小侦探旅游网。
搜索
您的当前位置:首页融合遗传算法和蚁群算法动态网格任务调度算法研究

融合遗传算法和蚁群算法动态网格任务调度算法研究

来源:小侦探旅游网
《工业控制计算机》2O11年第24卷第2期 65 融合遗传算法和蚁群算法动态网格任务调度算法研究 Genetic Algorithm and Ant Colony Algorithm for Dynamic Grid Task Scheduling 孙玉涛 毕殿杰 (安徽财经大学信息工程学院计算机科学与技术系,安徽蚌埠233041) 摘 要 网格计算是当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题。未来互联网的发展方向是 将网络中众多闲置的计算资源、存储资源以及科学仪器等可用资源充分合理的加以利用。如何高效地使用网格资源,即网 格调度问题也随之成为研究的重点,虽然在传统的分布式并行计算中有很多成熟的任务调度算法,但由于网格的新特性, 使得必须研究新的算法来解决一些新出现的问题,如调度问题的NP安全性,调度算法的高效性,资源的异构性以及资源 分配决策的并行性和分布性等。 关键词:网格任务,遗传算法,蚁群算法,任务调度,动态融合 Abstract How efficient use of grid resources grid scheduling problem that will become a focus of the study,although in traditional distributed and para el computing,there are many sophisticated task scheduling a gorithm,but because of the new features of the grid,made it necessary to study new algorithms to solve new problems,such as the scheduling problem NP security,effi— cient scheduling algorithms,resource heterogeneity and resource allocation decisions,parallel and distributed and SO on. Keywords:grid task,genetic algorithm,ant colony algorithm,task scheduling,dynamic integration 本文将遗传算法和蚁群算法相结合,利用遗传算法前期收 示,圈中分数的分子T表示 敛速度快的特点,进行前期的训练;而得到的信息索作为蚁群算 任务号,分母Q表示计算 法的初始值,进一步进行搜索收敛,最终得到最优或次优调度方 量,而DAG图中的箭头表 案。结合网格任务调度的特点,本文借鉴将遗传算法和蚁群算法 示子任务之间的优先关系, 动态融合应用于软硬件划分的思想,选取优化的遗传算法和蚁 C(i,j)表示任务T.与T.之间 群算法的参数设置,将问题转换到网格计算任务调度问题上来, 的通信量。箭头从前驱指向 提出融合遗传算法和蚁群算法的网格任务调度算法。 后继,前驱是后继的必要条 其基本思路是算法前过程采用遗传算法,充分利用遗传算 件,只有在某个任务的所有 法的快速性、随机性、全局收敛性,其结果是产生有关问题的初 前驱都完成的条件下,该任 始信息素分布。算法后期采用蚁群算法,在有一定初始信息素分 务才能被执行。 布的情况下,充分利用蚁群算法并行性、正反馈性、求精解效率 将子任务表示成DAG图 图2任务DAG图 高等特点。其总体框架如图1所示。 之后,可以得到各种任务分配方 案,这些分配方案的效率是不同 的,需要进行优化。如图3是根 据任务划分得到的分配到三个 计算结点的一种方案。 设有n个计算结点所组成 罔罔目 的网格系统P={P ,Pz,…,P 1, 图3子任务资源分配图 每个结点P.处理能力为r。需要 运行m个子任务T={t ,t 一,t },一般地n<m。将任务调度问题 描述成如下六元组∑=(T,<,Q,C,X,W)。其中:“<”是T中子任 务间的优先关系;Q是一个mxn维的执行开销矩阵,其元素q 表示子任务t.在处理机Pi上的执行时间;C是一个mxrn维通 信开销矩阵,cij表示子任务ti与tj之间的通信时间;X是一个 图1总体框架 1 任务调度问题描述 mxn维的任务分配矩阵,其中Xii=1,表示t。分配到处理机P 上 求解网格计算任务调度问题时,通常用有向无环图(DAG) 执行,否则X__:O;w表示通信开销和执行开销之间的差异。 2算法实现 来描述,如图2所示。在DAG图中,每个子任务用一个圆圈表 遗传算法部分: }安徽财经大学信息工程学院青年教师项目(xgky2008003);安徽财经大学校级科研项目(ACKYQO947ZC) 1)初始化遗传算法控制参数; 2)设置遗传算法结束条件; 3)随机生成初始种群P(O),g=O;//g是遗传代数 4)计算P(O)中的个体适应值; 5)反复执行下列操作,直到满足遗传算法结束条件; ①根据个体适应值及选择策略确定P(g)内个体的选择概 率;②以概率Pn执行交叉操作;③以概率P 执行变异操作;④ 计算P(g+1)中个体的适应值,g=g+1。 遗传算法与蚂蚁算法衔接部分: 6)按一定比例从P(g)中选择适应能力强的个体,放入集合 中,作为优化集合; 7)对于集合中的每个优化解,将遗传算法求解结果转换为 蚁群算法中的信息素值; 蚁群算法部分: 8)初始化蚁群算法控制参数; 9)设置蚁群算法结束条件; 10)随机地将m只蚂蚁散布到n个计算结点上; 11)对每只蚂蚁的分配结果计算目标函数,选取当前的最佳解; 1 2)更新各个计算结点的信息素值; 13)若满足蚁群算法结束条件,退出;否则,返回执行步骤 (1O)。 3测试实验 模拟的网格环境是以20-90个用户数,50个资源为例来演 示GTDG3A算法。表1和表2给出了GTDG3A算法与蚁群算 法、遗传算法进行网格任务调度的实验数据。其中,蚁群算法和遗 传算法中控制参数的设置与GTDG3A算法中相应的设置相同。 表1 蚁群算法、遗传算法与GTDG3A算法调度时间的对比 Us Ant AiEorit.hm G∞出c Algorithm GTDG3A AlEorit.hm Nodes T 《琊s) Tiors(ms) Tim,(ms) 20 1 23 66 11 3口 366 284 215 40 #84 853 304 58 1735 2】8D 1】17 6口 2562 4054 1400 7D 361 8 6215 l 931 80 6400 11223 3035 如 9963 1 9350 4258 表1给出了GTDG3A算法与GA和AA在20-90个不同 用户下所消耗的时间,从表中我们可以很明显的看出:GA在前 期(少于50个用户时)搜索能力较强,所费时间较少,但随后其 迭代计算越来越大,相应得时间花费也就越多。而AA恰恰相 图4调度时间一用户数曲线 融合遗传算法和蚁群算法动态网格任务调度算法研究 反,因为随着其信息素的不断增加它的正反馈性发挥了作用,使 之时间增加幅度小于GA。当然GTDG3A算法的优势是显而易 见的。图4给出了相应的仿真结果。 表2蚁群算法、遗传算法与GTDG3A算法迭代次数的对比 User AntAlgoritlum GmeficAlgorith ̄ GTDG3AAlgorithm Nodes It ̄catinns It ̄'ations :t ̄-ations 20 3口5 68 3 如8 30 28 7 55 1 23 1 40 36 3 73 6 34 0 50 33 9 79 g 35 3 dⅡ 59 6 85 5 37 8 70 43 6 70 I 3口7 80 49 3 9口6 ]4 7 90 55 6 lD0 5 40 3 表2给出了GTDG3A算法与GA和AA在20-90个不同 用户数下找到相对最优解所需要的迭代次数。通过三者的数据 可以看出,AA所需的迭代次数也比较少,但是GA就不同,而计 算也肯定耗费GA大量的时间,使得GA的整体性能逊色不少。 GTDG3A算法的迭代表现还是很明显的,仿真说明将两种算法 结合对提高效率是非常恰当和必要的。图5给出了迭代的仿真 模拟效果。 图5迭代一用户数曲线 4结束语 通过实验结果分析比较可以看出,本文提出的GTDG3A算 法在运行性能上具有一定的优势,充分验证了算法的合理性和有 效性。当然,在仿真环境的下,可能实验结果有细微的差别,但 我们相信本文提出的GTDG3A算法不失为合理而有效的算法。 参考文献 [1]Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem,IEEE Trans.Evolutionary Computation[J],1997,1(1):53—66 『2]l Foster,C Kesselman.G rid Sewices for Distributed System In— teg ration[J]Computer,2002,35(6):37-46 [3]唐志敏,徐志伟,等.网格技术专题[J]计算机研究与发展,2002,39 (3):897—980 [4]董方鹏,龚奕利,李伟,等.网格环境中资源发现机制的研究[J].计算 机研究与发展,2003,40(12):1749—1755 [5]杨广文,武永卫,朱晶.一种全局统一的层次化网格资源模型[J]计 算机研究与发展,2003,40(12):1763—1769 [6]林剑柠,吴慧中.基于遗传算法的网格资源管理调度算法[J]计算机 研究与发展,2004,41(12) [7]杨勇,蔡自兴,等基于遗传算法的自适应网格任务调度方法[J].计 算机工程与应用,2005(1):48-50 『收稿日期:2010 10.12] 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- xiaozhentang.com 版权所有 湘ICP备2023022495号-4

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务