《工业控制计算机》２Ｏ１１年第２４卷第２期 ６５ 融合遗传算法和蚁群算法动态网格任务调度算法研究 Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｙｎａｍｉｃ Ｇｒｉｄ Ｔａｓｋ Ｓｃｈｅｄｕｌｉｎｇ 孙玉涛 毕殿杰 （安徽财经大学信息工程学院计算机科学与技术系，安徽蚌埠２３３０４１） 摘 要 网格计算是当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题。未来互联网的发展方向是 将网络中众多闲置的计算资源、存储资源以及科学仪器等可用资源充分合理的加以利用。如何高效地使用网格资源，即网 格调度问题也随之成为研究的重点，虽然在传统的分布式并行计算中有很多成熟的任务调度算法，但由于网格的新特性， 使得必须研究新的算法来解决一些新出现的问题，如调度问题的ＮＰ安全性，调度算法的高效性，资源的异构性以及资源 分配决策的并行性和分布性等。 关键词：网格任务，遗传算法，蚁群算法，任务调度，动态融合 Ａｂｓｔｒａｃｔ Ｈｏｗ ｅｆｆｉｃｉｅｎｔ ｕｓｅ ｏｆ ｇｒｉｄ ｒｅｓｏｕｒｃｅｓ ｇｒｉｄ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ｔｈａｔ ｗｉｌｌ ｂｅｃｏｍｅ ａ ｆｏｃｕｓ ｏｆ ｔｈｅ ｓｔｕｄｙ，ａｌｔｈｏｕｇｈ ｉｎ ｔｒａｄｉｔｉｏｎａｌ ｄｉｓｔｒｉｂｕｔｅｄ ａｎｄ ｐａｒａ ｅｌ ｃｏｍｐｕｔｉｎｇ，ｔｈｅｒｅ ａｒｅ ｍａｎｙ ｓｏｐｈｉｓｔｉｃａｔｅｄ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ａ ｇｏｒｉｔｈｍ，ｂｕｔ ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｎｅｗ ｆｅａｔｕｒｅｓ ｏｆ ｔｈｅ ｇｒｉｄ，ｍａｄｅ ｉｔ ｎｅｃｅｓｓａｒｙ ｔｏ ｓｔｕｄｙ ｎｅｗ ａｌｇｏｒｉｔｈｍｓ ｔｏ ｓｏｌｖｅ ｎｅｗ ｐｒｏｂｌｅｍｓ，ｓｕｃｈ ａｓ ｔｈｅ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ＮＰ ｓｅｃｕｒｉｔｙ，ｅｆｆｉ— ｃｉｅｎｔ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍｓ，ｒｅｓｏｕｒｃｅ ｈｅｔｅｒｏｇｅｎｅｉｔｙ ａｎｄ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｄｅｃｉｓｉｏｎｓ，ｐａｒａｌｌｅｌ ａｎｄ ｄｉｓｔｒｉｂｕｔｅｄ ａｎｄ ＳＯ ｏｎ． Ｋｅｙｗｏｒｄｓ：ｇｒｉｄ ｔａｓｋ，ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ，ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ，ｄｙｎａｍｉｃ ｉｎｔｅｇｒａｔｉｏｎ 本文将遗传算法和蚁群算法相结合，利用遗传算法前期收 示，圈中分数的分子Ｔ表示 敛速度快的特点，进行前期的训练；而得到的信息索作为蚁群算 任务号，分母Ｑ表示计算 法的初始值，进一步进行搜索收敛，最终得到最优或次优调度方 量，而ＤＡＧ图中的箭头表 案。结合网格任务调度的特点，本文借鉴将遗传算法和蚁群算法 示子任务之间的优先关系， 动态融合应用于软硬件划分的思想，选取优化的遗传算法和蚁 Ｃ（ｉ，ｊ）表示任务Ｔ．与Ｔ．之间 群算法的参数设置，将问题转换到网格计算任务调度问题上来， 的通信量。箭头从前驱指向 提出融合遗传算法和蚁群算法的网格任务调度算法。 后继，前驱是后继的必要条 其基本思路是算法前过程采用遗传算法，充分利用遗传算 件，只有在某个任务的所有 法的快速性、随机性、全局收敛性，其结果是产生有关问题的初 前驱都完成的条件下，该任 始信息素分布。算法后期采用蚁群算法，在有一定初始信息素分 务才能被执行。 布的情况下，充分利用蚁群算法并行性、正反馈性、求精解效率 将子任务表示成ＤＡＧ图 图２任务ＤＡＧ图 高等特点。其总体框架如图１所示。 之后，可以得到各种任务分配方 案，这些分配方案的效率是不同 的，需要进行优化。如图３是根 据任务划分得到的分配到三个 计算结点的一种方案。 设有ｎ个计算结点所组成 罔罔目 的网格系统Ｐ＝｛Ｐ ，Ｐｚ，…，Ｐ １， 图３子任务资源分配图 每个结点Ｐ．处理能力为ｒ。需要 运行ｍ个子任务Ｔ＝｛ｔ ，ｔ 一，ｔ ｝，一般地ｎ＜ｍ。将任务调度问题 描述成如下六元组∑＝（Ｔ，＜，Ｑ，Ｃ，Ｘ，Ｗ）。其中：“＜”是Ｔ中子任 务间的优先关系；Ｑ是一个ｍｘｎ维的执行开销矩阵，其元素ｑ 表示子任务ｔ．在处理机Ｐｉ上的执行时间；Ｃ是一个ｍｘｒｎ维通 信开销矩阵，ｃｉｊ表示子任务ｔｉ与ｔｊ之间的通信时间；Ｘ是一个 图１总体框架 １ 任务调度问题描述 ｍｘｎ维的任务分配矩阵，其中Ｘｉｉ＝１，表示ｔ。分配到处理机Ｐ 上 求解网格计算任务调度问题时，通常用有向无环图（ＤＡＧ） 执行，否则Ｘ＿＿：Ｏ；ｗ表示通信开销和执行开销之间的差异。 ２算法实现 来描述，如图２所示。在ＤＡＧ图中，每个子任务用一个圆圈表 遗传算法部分： ｝安徽财经大学信息工程学院青年教师项目（ｘｇｋｙ２００８００３）；安徽财经大学校级科研项目（ＡＣＫＹＱＯ９４７ＺＣ） １）初始化遗传算法控制参数； ２）设置遗传算法结束条件； ３）随机生成初始种群Ｐ（Ｏ），ｇ＝Ｏ；／／ｇ是遗传代数 ４）计算Ｐ（Ｏ）中的个体适应值； ５）反复执行下列操作，直到满足遗传算法结束条件； ①根据个体适应值及选择策略确定Ｐ（ｇ）内个体的选择概 率；②以概率Ｐｎ执行交叉操作；③以概率Ｐ 执行变异操作；④ 计算Ｐ（ｇ＋１）中个体的适应值，ｇ＝ｇ＋１。 遗传算法与蚂蚁算法衔接部分： ６）按一定比例从Ｐ（ｇ）中选择适应能力强的个体，放入集合 中，作为优化集合； ７）对于集合中的每个优化解，将遗传算法求解结果转换为 蚁群算法中的信息素值； 蚁群算法部分： ８）初始化蚁群算法控制参数； ９）设置蚁群算法结束条件； １０）随机地将ｍ只蚂蚁散布到ｎ个计算结点上； １１）对每只蚂蚁的分配结果计算目标函数，选取当前的最佳解； １ ２）更新各个计算结点的信息素值； １３）若满足蚁群算法结束条件，退出；否则，返回执行步骤 （１Ｏ）。 ３测试实验 模拟的网格环境是以２０－９０个用户数，５０个资源为例来演 示ＧＴＤＧ３Ａ算法。表１和表２给出了ＧＴＤＧ３Ａ算法与蚁群算 法、遗传算法进行网格任务调度的实验数据。其中，蚁群算法和遗 传算法中控制参数的设置与ＧＴＤＧ３Ａ算法中相应的设置相同。 表１ 蚁群算法、遗传算法与ＧＴＤＧ３Ａ算法调度时间的对比 Ｕｓ Ａｎｔ ＡｉＥｏｒｉｔ．ｈｍ Ｇ∞出ｃ Ａｌｇｏｒｉｔｈｍ ＧＴＤＧ３Ａ ＡｌＥｏｒｉｔ．ｈｍ Ｎｏｄｅｓ Ｔ 《琊ｓ） Ｔｉｏｒｓ（ｍｓ） Ｔｉｍ，（ｍｓ） ２０ １ ２３ ６６ １１ ３口 ３６６ ２８４ ２１５ ４０ ＃８４ ８５３ ３０４ ５８ １７３５ ２】８Ｄ １】１７ ６口 ２５６２ ４０５４ １４００ ７Ｄ ３６１ ８ ６２１５ ｌ ９３１ ８０ ６４００ １１２２３ ３０３５ 如 ９９６３ １ ９３５０ ４２５８ 表１给出了ＧＴＤＧ３Ａ算法与ＧＡ和ＡＡ在２０－９０个不同 用户下所消耗的时间，从表中我们可以很明显的看出：ＧＡ在前 期（少于５０个用户时）搜索能力较强，所费时间较少，但随后其 迭代计算越来越大，相应得时间花费也就越多。而ＡＡ恰恰相 图４调度时间一用户数曲线 融合遗传算法和蚁群算法动态网格任务调度算法研究 反，因为随着其信息素的不断增加它的正反馈性发挥了作用，使 之时间增加幅度小于ＧＡ。当然ＧＴＤＧ３Ａ算法的优势是显而易 见的。图４给出了相应的仿真结果。 表２蚁群算法、遗传算法与ＧＴＤＧ３Ａ算法迭代次数的对比 Ｕｓｅｒ ＡｎｔＡｌｇｏｒｉｔｌｕｍ ＧｍｅｆｉｃＡｌｇｏｒｉｔｈ￣ ＧＴＤＧ３ＡＡｌｇｏｒｉｔｈｍ Ｎｏｄｅｓ Ｉｔ￣ｃａｔｉｎｎｓ Ｉｔ￣＇ａｔｉｏｎｓ ：ｔ￣－ａｔｉｏｎｓ ２０ ３口５ ６８ ３ 如８ ３０ ２８ ７ ５５ １ ２３ １ ４０ ３６ ３ ７３ ６ ３４ ０ ５０ ３３ ９ ７９ ｇ ３５ ３ ｄⅡ ５９ ６ ８５ ５ ３７ ８ ７０ ４３ ６ ７０ Ｉ ３口７ ８０ ４９ ３ ９口６ ］４ ７ ９０ ５５ ６ ｌＤ０ ５ ４０ ３ 表２给出了ＧＴＤＧ３Ａ算法与ＧＡ和ＡＡ在２０－９０个不同 用户数下找到相对最优解所需要的迭代次数。通过三者的数据 可以看出，ＡＡ所需的迭代次数也比较少，但是ＧＡ就不同，而计 算也肯定耗费ＧＡ大量的时间，使得ＧＡ的整体性能逊色不少。 ＧＴＤＧ３Ａ算法的迭代表现还是很明显的，仿真说明将两种算法 结合对提高效率是非常恰当和必要的。图５给出了迭代的仿真 模拟效果。 图５迭代一用户数曲线 ４结束语 通过实验结果分析比较可以看出，本文提出的ＧＴＤＧ３Ａ算 法在运行性能上具有一定的优势，充分验证了算法的合理性和有 效性。当然，在仿真环境的下，可能实验结果有细微的差别，但 我们相信本文提出的ＧＴＤＧ３Ａ算法不失为合理而有效的算法。 参考文献 ［１］Ｄｏｒｉｇｏ Ｍ，Ｇａｍｂａｒｄｅｌｌａ Ｌ Ｍ．Ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ：Ａ ｃｏｏｐｅｒａｔｉｖｅ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ，ＩＥＥＥ Ｔｒａｎｓ．Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ［Ｊ］，１９９７，１（１）：５３—６６ 『２］ｌ Ｆｏｓｔｅｒ，Ｃ Ｋｅｓｓｅｌｍａｎ．Ｇ ｒｉｄ Ｓｅｗｉｃｅｓ ｆｏｒ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍ Ｉｎ— ｔｅｇ ｒａｔｉｏｎ［Ｊ］Ｃｏｍｐｕｔｅｒ，２００２，３５（６）：３７－４６ ［３］唐志敏，徐志伟，等．网格技术专题［Ｊ］计算机研究与发展，２００２，３９ （３）：８９７—９８０ ［４］董方鹏，龚奕利，李伟，等．网格环境中资源发现机制的研究［Ｊ］．计算 机研究与发展，２００３，４０（１２）：１７４９—１７５５ ［５］杨广文，武永卫，朱晶．一种全局统一的层次化网格资源模型［Ｊ］计 算机研究与发展，２００３，４０（１２）：１７６３—１７６９ ［６］林剑柠，吴慧中．基于遗传算法的网格资源管理调度算法［Ｊ］计算机 研究与发展，２００４，４１（１２） ［７］杨勇，蔡自兴，等基于遗传算法的自适应网格任务调度方法［Ｊ］．计 算机工程与应用，２００５（１）：４８－５０ 『收稿日期：２０１０ １０．１２］
