第２７卷第７期 计算机应用研究 Ｖｏ１．２７ Ｎｏ．７ ２０１０年７月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｊｕ１．２０１０ 基于量子粒子群优化的ＤＡＧ并行任务调度研究术 张聪，沈惠璋 （上海交通大学安泰经济与管理学院，上海２０００５２） 摘要：任务调度是网络并行计算系统的核心问题之一。在有向无环图（ＤＡＧ）描述问题的基础上，提出了一种 进行并行任务调度的量子粒子群优化算法。首先对ＤＡＣ并行任务调度问题作出定义，并给出了优化问题的目 标；然后分别讨论了问题的编码表示、解码方案、位置向量的计算方法、离散问题连续化、算法的总体流程等；最 后给出算法的仿真实验情况及分析，实验结果表明，该算法有良好的全局寻优性能和快捷的收敛速度，调度效果 优于遗传算法和粒子群优化算法。 关键词：任务调度；量子粒子群优化；有向无环图 中图分类号：ＴＰ３１４ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１０）０７—２４５８—０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１０．０７．０１５ Ｒｅｓｅａｒｃｈ ｏｎ ＤＡＧ ｐａｒａｌｌｅｌ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ｂａｓｅｄ ｏｎ ｑｕａｎｔｕｍ—ｂｅｈａｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ＺＨＡＮＧ Ｃｏｎｇ，ＳＨＥＮ Ｈｕｉ—ｚｈａｎｇ （Ａｎｔａｉ Ｃｏｌｌｅｇｅ ｏｆ Ｅｃｏｎｏｍｉｃｓ＆Ｍａｎａｇｅｍｅｎｔ，Ｓｈａｎｇｈａｉ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００５２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｉｍｐｏｒｔａｎｔ ｐｒｏｂｌｅｍｓ ｉｎ ｐａｒａｌｌｅｌ ｃｏｍｐｕｔｉｎｇ ｓｙｓｔｅｍ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｑｕａｎｔｕｍ－ ｂｅｈａｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｂａｓｅｄ Ｏｎ ｄｉｒｅｃｔｅｄ ａｃｙｃｌｉｃ ｇｒａｐｈ．Ｆｉｒｓｔ ｒｅｄｅｆｉｎｅｄ ｔｈｅ ｐａｒａｌｌｅｌ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ａｎｄ ｉｔｓ ａｉｍ．Ｔｈｅｎ ｄｉｓｃｕｓｓｅｄ ｔｈｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ｅｎｃｏｄｉｎｇ，ｔｈｅ ｐｒｏｃｅｄｕｒｅ ｏｆ ｔｈｅ ｄｅｃｏｄｉｎｇ，ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｍｅｔｈｏｄ ｏｆ ｐｏｓｉｔｉｏｎ ｖｅｃｔｏｒ，ｔｈｅ ｅｏｎｔｉｎｕａｔｉｖｅ ｏｆ ｔｈｅ ｄｉｓｃｒｅｔｅ ｐｒｏｂｌｅｍ ａｎｄ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｒｅｓｐｅｃｔｉｖｅ— ｌｙ．Ｉｎ ｔｈｅ ｅｎｄ，ｐｒｅｓｅｎｔｅｄ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｓｉｍｕｌａｔｉｏｎ，ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔ ａｎａｌｙｓｉｓ ａｎｄ ｔｈｅ ｃｏｎｃｌｕｓｉｏｎｓ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｈｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｈａｓ ｂｅｔｔｅｒ ｇｌｏｂａｌ ｏｐｔｉｍｉｚｉｎｇ ａｂｉｌｉｔｙ ａｎｄ ｎｌｏｒｅ ｒａｐｉｄ ｃｏｎｖｅｒｇｅｎｃｅ，ａｎｄ ｉｔ ｉｓ ｓｕｐｅｒｉｏｒ ｔｏ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ；ｑｕａｎｌｕｍ—ｂｅｈａｖｅｄ ｐａｔｒｉｃｌｅ ｓｗａｒｍ ｏｐｌｉｍｉｚａｔｉｏｎ（ＱＰＳＯ）；ｄｉｒｅｃｔｅｄ ａｃｙｃｌｉｃ ｇｒａｐｈ（ＤＡＧ） 网络并行计算环境下的任务调度问题是指在一定约束条 但是在许多实际应用领域，更胜于遗传算法，尤其是在非线性 件下，如何将一组任务分配到多台处理机 执行的组合优化问 优化问题 。量子粒子群优化（ＱＰＳＯ）算法是在传统的ＰＳＯ 题，其已被证明是ＮＰ完全问题，不可能住多项式时问内找到 基础 提出的一种新型的具有高效率全局搜索能力的进化算 问题的最优解 Ｊ。目前常见的并行任务调度问题按照任务 法 。它主要是引入量子物理的思想改进了ＰＳＯ的进化方 之间有无数据依赖关系可以划分为任务调度和依赖关系 法，即更新粒了位置的方法；在更新粒子位置时重点考虑各个 任务调度。前者在调度任务时不需要考虑任务之问的数据依 粒子的当前局部最优位置信息和全局最优位置信息。ＱＰＳＯ 赖关系；而后者通常用有向无环图（ＤＡＧ）表示任务之间的数 具有调整参数少、容易实现、收敛能力强等优势。为适应任务 据依赖关系，在调度过程中满足任务之间的数据依赖关系。依 分配问题的求解，本文设汁出合适的粒子编码，利用改进的量 赖关系任务调度的求解优化过程比任务调度的要复杂许 子粒子群算法求解任务分配问题，并与其他算法相比较。实验 多，且其适用范围也更广。以ＤＡＧ表示的并行任务模 的研 结果表明，本文提出的算法可以获得质量更高的解。 究得到了广泛关注和迅速发展。近年出现的・些肩发式算法 （如模拟退火算法、遗传算法等）为求解此类ＮＰ完全问题提供 １ 问题描述 了新的途径 Ｊ，但是这些算法有些复杂性太高难以实现，有 本模型的计算系统由一系列异构的处理机组成，需要处理 些实现起来太费时，所以有必要寻求更好的算法来解决此问 的总任务已分解成一系列子任务。模型的约束条件为：任务执 题。 行具有非抢占性，即处理机只有在执行完某个任务之后才能处 粒子群优化（ＰＳＯ）算法是由Ｋｅｎｎｅｄｙ等人 提出的一种 理另外・个任务；另外这些任务之间具有前驱后继的数据依赖 源于对鸟群捕食行为模拟的进化计算技术，已成为进化计算的 关系，某个子任务只有在其所有的前驱任务处理完毕后才能开 一个最吸引人的分支。与遗传算法类似，ＰＳＯ是一种基于迭代 始执行。该模型的调度日标就是要使得整个ＤＡＧ图的调度长 的优化方法，系统初始化为一组随机解，通过迭代搜寻最优值， 度最短 收稿日期：２００９．１２—２２；修回日期：２０１０—０２．１３ 基金项目：国家自然科学基金资助项目（７０６７１０７０）；高等学校博士学科点专顼科研基金 资助项目（２００７０２４８０５４） 作者简介：张聪（１９７５一），男，安徽阜阳人，讲师，博士研究生，主要研究方向为进化计算、数据挖掘（ｚ—ｃ—ｃｎ＠１６３．ｅｏｍ）；洗惠璋（１９５８ ），男，天 津人，教授，博导，博士，主要研究方向为数据挖掘、网络安全． 第７期 张 聪，等：基于量子粒子群优化的ＤＡＧ并行任务调度研究 ・２４５９・ 为了便于分析问题，可以用下列五元组表述： Ⅱ＝（Ｐ，Ｇ，Ｏ， ，力） 前位置。ｂ）整个种群从起始到目前所找到的最优解ｇｂｅｓｔ。每 个粒子按以下两个公式进行动态进化，调整粒子的位置： Ｕｉｄ，其中： Ｐ＝｛Ｐ ，Ｐ：，…，Ｐ ｝为ｎ个处理机的集合。 Ｇ是子任务集 的依赖关系图，它通过ＤＡＧ来表示各个 （ｔ＋１）＝ ．ｄ（￡）＋ｃｌ ｒ１ｄ（ｔ）（ｐｂｅｓｔ 一 ．（ ））＋ （３） （４） ｃ２ ｒ２ ｄ（ｔ）（ｇ￣ｅｓｔｄ（ｔ）一Ｘｉｄ（ｔ）） ，（ｔ＋１）＝ （ｔ）＋ （ｔ＋１） 子任务问的调度约束关系。Ｇ＝（Ｔ，Ｅ），其中Ｔ：｛ ， ，…， ｝为ｍ个子任务的集合，一个子任务 就是图Ｇ中的一个 节点，Ｅ是任务依赖关系图中的有向边集。（Ｔ ，？ ） Ｅ（ｉ，Ｊ＝ １，２，…，ｍ），则表示在子任务 没有完成之前，任务 不能执 其中： 是惯性权重，动态调整惯性权重以平衡收敛的全局性 和收敛速度；Ｃ。和ｃ 为加速常数，通常在０～２取值，Ｃ 调节粒 子飞向自身最好位置方向的步长，Ｃ：调节粒子飞向全局最好 位置方向的步长；ｒ （ｔ Ｆ２ ｄ（ｔ）～Ｕ（０，１），且ｄ＝１，２，…，ｎ。 行。这时称 为７１＿的一个前驱， 为 的一个后继， 可用 为了减少在进化过程中粒子离开搜索空间的可能性，粒子的每 邻接矩阵存储。 一维速度被限定在［一 … ］内。 是一个ｍ ｘｎ矩阵，其元素０ 表示任务 在处理机Ｐ， ２．２ ＱＰＳＯ算法 Ｊ－的执行时间，假设每个任务的执行时间预知（ １，２，…，ｍ； ＝１，２，－一，ｎ）。 ＇Ｓｕｎ等人从量子力学的角度，通过对粒子收敛行为的研 是一个ｍ ｘｍ矩阵，其元素 表示任务 与 之间的 究，基于粒子群算法提出了一种新的算法模型——量子粒子群 数据传输延时（ｉ，Ｊ＝１，２，…，，ｎ），同时假设各处理机问的通信 （Ｑｐｓｏ）算法。在该算法中，由于粒子满足聚集态的性质完全 能力是相同的，且忽略网络拥塞，即传输的数据量是惟一影响 不同，使粒子在整个可行解空间中进行搜索寻求全局最优解， 大小的因素。 因而Ｑｐｓｏ算法在搜索能力上远远优于所有已开发的ＰＳＯ算 是一个ｍ×ｎ的任务分配矩阵，其中 ，＝１表示 分配 法。 ＱＰＳＯ算法参数个数少，进化方程的形式更加简单，更容 到处理机Ｐ，上执行；否则 ，＝０（ １，２，…，ｍ； ＝１，２，…，ｎ）。 易控制。在Ｑｐｓｏ算法中，每一个粒子必须收敛于各自的随机 要实现的目标是寻找一个分配调度策略，将ｍ个子任务 点尸，，粒子按照下面的三式移动： 分配到ｎ个处理机上，合理调度各个子任务的执行次序，使得 ｍｂｅｓｔ＝ ＝（ ，…， １各子任务在满足依赖关系图Ｇ的约束下，整个任务的完成时 ） （５） ｍｉ ＝１ ｍｉ ：１，ｎ ｌ＝ Ｉ 间最短。现假设某一合法的分配调度Ｓ，将 中的ｍ个子任务 ＰＰ Ｖ＝ ＋ｔ１一ｎＰ ，ｆ＝ｒａｎｄ （６） 分配到ｎ个处理机上，其中子任务 被分配到处理机Ｐ，上执 ＝ＰＰ ，±ｎＩｍｂｅｓｂ— ＨＩＩｎ（１／ｕ），Ｍ＝ｒａｎｄ （７） 行，那么子任务 在处理机Ｐ 上的执行时间满足以下两式： 其中：ｍｂｅｓｔ是粒子群ｐｂｅｓｔ的中间位置；Ｐ 为粒子本身所找到 ＆（Ｔｉ， ）＝ｎＥ黼Ｔｉ）（ｎ（ ，Ｐｒ） （ 一 ） （ ） 的最优解ｐｂｅｓｔ；Ｐ 为整个粒子群目前找到的最优解ｇｂｅｓｔ； ｎ（ ，Ｐ，）＝Ｓｔ（ ，，Ｊ，）＋０ ；ｉ，ｋ＝１，２，…， ； ，ｒ＝１，２，…，ｎ（２） ＰＰ 为Ｐ 与Ｐ 之间的随机点；ｎ为Ｑｐｓｏ的收缩扩张系数，它 其中：Ｓｔ（ ，Ｐ，）和Ｆｔ（Ｔｉ，，），）分别表示子任务 在处理机Ｐ， 是ＱＰＳＯ收敛的一个重要参数，第ｔ次迭代时一般可取 上的开始执行时刻和结束执行时刻；Ｐｒｅｄ（ ）表示子任务 Ⅱ＝ｎ…一ｆ（。 。 一ｎ ．）／ｔ （８） 的前驱节点集合，假设子任务 Ｐｒｅｄ（ ）被分配到处理机 其中：ｔ，，ｌａｘ是迭代的最大次数，。…与ｎ 分别是最大和最小系 Ｐ ｊ 数。ＱＰＳＯ的算法流程如下： 根据式（１）（２）迭代计算，可得到所有子任务的结束执行 ａ）迭代次数 ０，对种群的每个粒子的位置向量进行初 时刻。设厂（ｓ）为在调度策略ｓ下完成任务所使用的总时问， 始化。 那么：，（ｓ）＝ｉ￣ｌａｘ（Ｆｔ（ ，Ｐ，））；Ｖ ｉ＝１，２，…，ｍ ＝１，２，‘一，ｎ。 ｂ）根据目标函数计算每个粒子的目标函数值。 任务调度目标就是ｒａｉｎ（Ｆ（Ｓ））ＶＳ，即寻找一个分配调度 ｃ）更新每个粒子的新局部最优位置Ｐ 。 Ｓ，使得，（ｓ）最小。 ｄ）更新粒子群的全局最优位置Ｐ 。 鉴于本文主要考虑任务调度问题，在不失问题一般性的情 ｅ）根据式（５）计算ｍｂｅｓｔ。 况下，可忽略数据传输延时，即在下文中可假设所有的 ，＝０。 ｆ）根据式（６）计算每个粒子随机点ＰＰ 。 ｇ）根据式（７）（以一定的概率取加或减）更新每个粒子的 ２算法 新位置。 ｈ）令ｔ＝ｔ＋１，返回到ｂ），重新计算，直到终止条件满足。 ２．１ ＰＳＯ算法 粒子群优化（ＰＳＯ）算法是一种进化计算方法，是一种基于 ３基于ＱＰＳＯ的ＤＡＧ并行任务调度 迭代的优化工具。该算法通过群体中各粒子问的合作与竞争 来搜索全局最优点。 ３．１编码与解码 系统初始化为一组共ｎ个随机解，通过迭代搜寻整个群体 任务调度的常见编码包括基于任务的编码、基于操作的编 的最优值。粒子ｉ的当前位置为 ：（ ，…， ），其飞行 码和基于优先规则的编码等。由于ＤＡＧ并行任务调度的复杂 速度记为 ：（ ，…， ），在解空间中追随适应度最优的 性，采用任一种上述编码形式均无法保证所有解的合法性，这 粒子进行搜索。在每一次迭代中，粒子通过跟踪两个“极值” 将浪费大量的求解时间。本文设计了一种复合的编码方案：编 来更新自己：ａ）每个粒子本身所找到的最优解ｐｂｅｓｔ。如果粒子 码长度为２ １１１，可描述为两个向量，第一个向量采用基于优先 当前位置对应的适应度小于ｐｂｅｓｔ的适应度，则ｐｂｅｓｔ更新为当 规则的编码方式，为一个包含ｍ维的向量（Ｒ ，Ｒ２，…，Ｒ ）。其 ・２４６０・ 计算机应用研究 第２７卷 中Ｒ 表示在算法迭代过程中第ｉ次迭代时发生的冲突利用优 先规则Ｒ，消除。本文选择了五种优先规则，包括最短执行时 间（ＳＰＴ）、最长执行时间（ＬＰＴ）、最早开工时间（ＥＳＴ）、最早完 工时问（ＥＦＴ）、最晚完工时间（ＬＦＴ），数字０、１、２、３、４分别对 ｂ）从整数组成的子串到实数作一个映射，可表示为 ｒ＝（×∑ｑ Ｘ ６ ｆ－ （９） 其中：ｒ为映射的实数；ｃ是常数，一般取足够小的实数，本文取 值为０．Ｏ１；６为基数，对于 值为 。 应优先规则ＳＰＴ、ＬＰｒｒ、ＥＳＴ、ＥＦＦ、Ｌ 。第二个向量是处理机分 ，６取值为５，对于 ，６取 配向量，即一个包含ｍ维的向量（肘。， ，…，Ｍ ）。其中Ｍ 表示编号为ｉ的子任务被分配到编号为（Ｍ ）的处理机上执行 （所有处理机编号为０，１，…，ｎ—１）。 ｃ）在计算任务执行总时间前，需将ｒ转换为子串，即式（９） 的逆映射： 一１ 在解码过程中，设ｔ为调度的时间步，Ｐｓ为蒯度列表。其 中ＰＳ 为第ｔ步调度执行的子任务；ＴＳ为所有前驱已经被调度 ｑ ＝（ Ｃ一 ｂ ）ｄｉｖ ｂ“ （１０） 其中：ｄｉｖ为整除，得到的商ｑ 为整数，在实际运算时，可用一 的子任务所构成的集合。解码算法如下： ａ）令ｔ＝１，ＰＳ为空，ＴＳ由所有无前驱的子任务构成。 ｂ）由ＴＳ中所有子任务编码，在处理机分配向量（Ｍ ， ，…，Ｍ ）中找到分配给每个子任务的处理机，并在０中找 到具体执行时间。 ｅ）依据约束条件和执行时间，得到Ｔｓ中每个子任务对应 的指标时间（开工、完工或执行时间），由编码 ，所对应的优 先规则选出一个子任务（如优先规则为最短执行时问，则选Ｔｓ 中执行时间最短的子任务，如果有多个子任务符合优先规则， 则任选一个），该子任务就是Ｐｓ ，从Ｔｓ中删除它，并将其』Ｊ口入 Ｐｓ的尾部。 ｄ）逐个考察ＰＳ 的后继子任务，如果该子任务无其他前 驱，或其他前驱都已被调度执行，则将其加入Ｔｓ中。 ｅ）令ｔ＝ｔ＋１，若ｔ＜ｍ＋ｌ，则转ｂ）；台则，算法终止。 通过下面示例说明解码过程： 任务的ＤＡＧ如图１所示。 优先规则向量： （０ ３ ２ ｌ ４ ０） 即：（ＳＰｒｒ Ｅ丌ＥＳＴ Ｉ Ｉ’ＬＦＴ ＳｇＦ） 处理机分配向量： （０ １ １ ０ １ ０） 即（Ｐ１ Ｐ２ Ｐ２ Ｐ１ Ｐ２ Ｐ１） 在＠中查到的处理时间： （２ ４ ６ ５ ３ ７） 处理时间指１～６号子任务在对应处理机上的执行时间。 根据示例数据得到的调度列表Ｐｓ为（ ７ ），甘特图如图２所示。 （１） ，ｊ，ｆ０） 图１ 任务关系图ＤＡＧ 图２任务调度的ｆ 特图 由上述编码方式和解码过程可知，本文编码能保证调度的 可行性，且码长较短，无冗余，解码复杂性 高。 ３．２ ＱＰＳＯ中向量的计算方法 对每个粒子，它的优先规则向量和处埋机分配向量可以表 示为 （１．．ｍ）和 … （１．．ｍ），按式（５）～（７）计算这两 个向量。由于前面所述的ＱＰＳＯ为连续空间算法，而ＤＡＧ并 行任务调度问题为整数规划问题，将离散优化转变成对实数向 量的连续优化，具体过程如下： ａ）将每个向量切断分成若干个子串，各段子串的长度可 以相等，也可以不相等，子串形如（ｑ ，ｑ ，…，ｇ ）。 个循环，ｉ从１～ 得到子串中所有分量。 例如９个子任务的情况， ＝（２ ４ ２ １ ４ ３ ４ １ Ｏ），分为 段，各子串长度均为３。 了串 （２４２）； （１４３）； （４１０） 变换后得到 厂 ０．７２ Ｏ ４８ １．Ｏ５ 经过迭代后的情况： 逆变换后得到 ｒ ０．５３ Ｉ．１２ ０．９ｌ 子串 （２０３） （４２２） （３３１） 往初始化时，可省掉式（９）的转换过程，直接给粒子位置 赋实数。 解决了连续化问题之后，还有一个边界问题，如上例ｒ的 取值为［ｏ，１．２４］，如迭代过程中ｚ的运算结果超出范围时，将ｒ 值取在边界』 。若ｒ＜０，取值０；ｒ＞１．２４，取值１．２４。 通过上述映射和逆映射，整数规划问题转换为连续优化问 题，从而可以利用Ｑ￣，Ｓｏ优化获得高质量的解。 ３．３算法流程 ａ）初始化粒子群，根据编码方案设定各粒子的随机位置。 ｂ）根据式（１０）将每个粒子的实数向量转换为整数向量。 ｃ）对每个粒子的整数向量解码后，计算每个粒子的目标 函数值。 ｄ）更新每个粒＿ｆ的局部最优值Ｐ 。 ｅ）更新粒子群的全局最优值Ｐ 。 ｆ）根据式（５）计算ｍｂｅｓｔ。 ｇ）根据式（６）计算每个粒子随机点ＰＰ 。 ｈ）根据式（７）更新每个粒子的新位置。 ｉ）返回ｂ）步，直到满足迭代的次数。 ４仿真实验与结果分析 ４．１ 实验参数选取 本文的仿真实验是在ＭＡｔ、ＬＡＢ软件上实现的。实验所用 ＤＡＧ图随机生成，每个任务节点有１—４个前驱与后继，估计 运行时间０ 为１～５０ Ｓ的随机数。实验计算了文献［３，４］的算 法、ＰＳＯ与本文的ＱＰＳＯ共四种情况，算法中主要参数：种群大 小为８０，终止代数为１ ５００，ｎ 取值１，ａｍｉｎ取值０．５；ＰＳＯ的惯 性权重 与Ｑｐｓｏ中的收缩扩张系数ｎ取值相同，Ｃ 和ｃ：均 为２，编码、解码、连续化与边界问题均使用本文的方案；文献 ［３］算法的杂交概率为１．０，变异概率为０．０５；文献［４］算法的 内部杂交概率为０．８，迁移概率为０。２，演化策略中的参数为 Ａ＝５。 第７期 张聪，等：基于量子粒子群优化的ＤＡＧ并行任务调度研究 ｛三量餐 ・２４６１・ ２ ２ ｊ １● ４．２计算结果与分析 明显的提高，尤其是子任务数较多、处理机数较多时。 对于随机生成的同一个ＤＡＧ图，分别用上述四种算法进 ｃ）ＰＳＯ与本文ＱＰＳＯ算法比较时，发现ＱＰＳＯ算法的收敛 行计算，记录各算法收敛时得到的最优解的完成时间和收敛时 速度比ＰＳＯ算法慢，但得到的最优解比ＰＳＯ算法好。 的进化代数。计算结果如表１所示。为了｝肖除数据随机性的 这是因为：首先，本文对问题的编码能够覆盖整个解空间， 影响，更好地反映算法的性能，表１中的进化代数是１００次进 相对来说文献［３，４］的算法只能从一个相对较小的空间内搜 化的平均收敛代数，完成时间是所有１００次进化中得到的最优 索；其次，本文采用了离散空间到连续空间的转换过程，它不仅 解的平均完成时问。图３为四个处理机１００个子任务情况下 满足了ＱＰＳＯ算法对待解问题的取值要求，还在一定程度上能 四种算法分别进化的静态性能曲线，列出了各算法在不同进化 更好地保护与遗传优良的解片段。另外，ＰＳＯ算法收敛过快， 代数时所找到的最优解。表２为四种算法在进化中能收敛到 而ＱＰＳＯ的量子搜索方式对传统的ＰＳＯ算法有了很大的改进， 其最优解的次数占实验总次数的百分比。 实验证明可防止早熟。 表１仿真实验结果 ５ 结束语 完成时间／ｓ 墼 丝 塑 文献［３］文献 ４］ＰＳＯ本文 基于ＤＡＧ的并行任务调度问题是ＮＰ难问题，传统的优 算法 算法算法算法 化算法很难求得全局最优解，虽然已有人将遗传算法应用于此 问题，但结果有待进一步改善。本文给出了新的问题定义，对 ＱＰＳＯ算法作出调整与改进，编码表示采用了适合于任务调度 问题的优先规则与处理机分配相结合的形式，并将离散空间优 化问题转换为连续空间优化问题，使得ＱＰＳＯ有较好的搜索能 力。最后通过仿真实验得到的一系列数据，表明了本文的改进 ＱＰＳＯ算法比遗传算法和ＰＳＯ算法有更好的性能，并有理由认 为，合理的编码表示与高效的搜索策略相结合是任务分配调度 各算法 子任务个数２５ 子任务个数５Ｏ 子任务个数１００ 问题全局寻优的有效途径。 参考文献： ［１］ＧＲＡＹ Ｍ Ｒ，ＪＯＨＮＳＯＮ Ｄ Ｓ．Ｃｏｍｐｕｔｅｒｓ ａｎｄ ｉｎｔｒａｃｔａｂｉｌｉｔｙ：ａ ｇｕｉｄｅ ｔｏ ｔｈｅ ｔｈｅｏｒｙ ｏｆ ＮＰ－ｃｏｍｐｌｅｔｅｎｅｓｓ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｗ．Ｈ．Ｆｒｅｅｍａｎ ａｎｄ Ｃｏ．，１９７９． ［２］ＡＨＭＡＤ Ｉ，ＫＷＯＲＫ Ｙ Ｋ．Ｏｎ ｐａｒｌａｌｅｌｉｚｉｎｇ ｔｈｅ ｍｕｈｉｐｒｏｃｅｓｓｏｒ ｓｃｈｅｄｕ— ｌｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓ－ ｔｅｍｓ，１９９９，１０（４）：４１４—４３２． ［３］ＨＯＵ Ｅ Ｓ Ｈ，ＡＮＳＡＲＩ Ｎ，ＨＯＮＧ Ｒｅｎ．Ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｈｉ— ｐｒｏｃｅｓｓｏｒ ｓｃｈｅｄｕｌｉｎｇ『Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｅｔｅｍｓ，１９９４，５（２）：１１３－１２０． ［４］钟求喜，谢涛，陈火旺．基于遗传算法的任务分配与调度［Ｊ］．计算 机研究与发展，２０００，３７（１０）：１１９７—１２０３． Ｕ ｌＵ【Ｊ ２ＵＵ ｊＵＵ ４Ｌ儿Ｊ ＵＵ ｂＬ，Ｕ ［５］张聪，马义忠．异构计算系统中基于遗传算法的任务分配与调度 进化代数 ［Ｊ］．微电子学与计算机，２００４，２１（６）：７４—７８． 图３静态性能曲线 ＝４，ｎｌ＝ｌＯＯ） ［６］ＫＥＮＮＥＤＹ Ｊ，ＥＢＥＲＨＡＲＴ Ｒ Ｃ．Ｐａｒｔｉｃｌｅ ｓｗａｍｉ ｏｐｔｉｎｆｉｚａｔｉｏｎ［Ｃ］／／ 由表ｌ、２和算法的静态性能曲线可以得出： Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．Ｐｉｓｃａ． ａ）在任务数较多、处理机较多的情况下，ＰＳＯ与本文ＱＰ— ｔａｗａｙ：ＩＥＥＥ Ｐｒｅｓｓ，１９９５：１９４２—１９４８． ｓｏ算法的收敛速度比文献［３］算法快很多，但与文献［４］算法 ［７］ＳＵＮ Ｊｕｎ，ＦＥＮＧ Ｂｉｎ，ＸＵ Ｗｅｎ—ｂｏ．Ｐａｒｔｉｃｌｅ ｓｗａｌｎｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｗｉｔｈ 比较时，ＰＳＯ算法的收敛速度明显比文献［４］算法快，本文ＱＰ— ｐａｒｔｉｃｌｅｓ ｈａｖｉｎｇ ｑｕａｎｔｕｍ ｂｅｈａｖｉｏｒ［Ｃ］／／Ｐｒｏｅ ｏｆ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕ— ｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ．２００４：３２５—３３１． ｓｏ算法则与文献［４］算法相当；而在任务数少的情况下，除文 ［８］ＳＵＮ Ｊｕｎ，ＸＵ Ｗｅｎ—ｂｏ，ＦＥＮＧ Ｂｉｎ．Ａ ｇｌｏｂａｌ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ ｏｆ ｑｕａｎｔｕｍ 献［３］算法稍慢，其他算法相差不大 ｂｅｈａｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｂ）本文ＱＰＳＯ算法能找到的最优解比文献［３，４］算法有 ｏｎ Ｃｙｂｅｒｎｅｔｉｃｓ ａｎｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ．２００４：１ Ｉ １．１ １６． （上接第２４５４页） ｔｒａｉｔ？［Ｊ］．Ｂｅｈａｖｉｏｒａｌ Ｅｃｏｌｏｇｙ ａｎｄ Ｓｏｃｉｏｂｉｏｌｏｇｙ，２００３，５４（４）： ［１２］ＡＮＴＹＩＬＡ Ｐ，ＰＡＡＴＥＲＯ Ｐ，ＴＡＰＰＥＲ Ｕ，ｅｔ ａ１．Ｓｏｕｒｃｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ ３９６．４０５． ｂｕｌｋ ｗｅｔ ｄｅｐｏｓｉｔｉｏｎ ｉｎ Ｆｉｎｌａｎｄ ｂｙ ｐｏｓｉｔｉｖｅ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ［Ｊ］．Ａｔ－ ［１ ５］ＧＩＲＶＡＮ Ｍ，ＮＥＷＭＡＮ Ｍ Ｅ Ｊ．Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｓｏｃｉｌａ ａｎｄ ｂｉｏ－ ｍｏｓｐｈｅｒｉｃ Ｅｎｖｉｒｏｎｍｅｎｔ，１９９５，２９（１４）：１７０５—１７１８ ｌｏｇｉｃａｌ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｎａｔｉｏｎａｌ Ａｃａｄｅｍｙ ｏｆ ［１３］ＫＯＮＤＯＲ Ｒ Ｉ，ＬＡＦＦＥＲＴＹ Ｊ．Ｄｉｆｕｓｉｏｎ ｋｅｒｎｅｌｓ ｏｎ ｇｒａｐｈｓ ａｎｄ ｏｔｈｅｒ Ｓｃｉｅｎｃｅｓ ｏｆ ｔｈｅ Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ，２００２，９９（１２）：７８２１— ｄｉｓｃｒｅｔｅ ｓｔｒｕｃｔｕｒｅｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １９ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ７８２６． Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ．Ｓａｎ Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ．２００２． 『１６］ＲＯＳＶＡＬＬ Ｍ．ＢＥＲＧＳＴＲＯＭ Ｃ Ｔ．Ａｎ ｉｎｆｍ＇ｍａｔｉｏｎ—ｔｈｅｏｒｅｔｉｃ ｆｒａｍｅｗｏｒｋ 【１４ ｊ ＬＵＳＳＥＡＵ Ｄ，ＳＣＨＮＥＩＤＥＲ Ｋ，ＢＯＩＳＳＥＡＵ Ｏ Ｊ，ｅｔ ａ１．ｒｒｈｅ ｂｏｔｔｌｅｎｏｓｅ ｏｆｒ ｒｅｓｏｌｖｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｒｏｃｅｅｄ・ ｄｏｌｐｈｉｎ ｃｏｍｎｍｎｉｔｙ ｏｆ ｄｏｕｂｔｆｕｌ ｓｏｕｎｄ ｆｅａｔｕｒｅｓ ａ ｌａｒｇｅ ｐｒｏｐｏｒｔｉｏｎ ｏｆ ｉｎｇｓ ｏｆ ｔｈｅ Ｎａｔｉｏｎａｌ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ ｏｆ ｔｈｅ Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｌｏｎｇ—ｌａｓｔｉｎｇ ａｓｓｏｃｉａｔｉｏｎｓ：ｃａｎ ｇｅｏｇｒａｐｈｉｃ ｉｓｏｌａｔｉｏｎ ｅｘｐｌａｉｎ ｔｈｉｓ ｕｎｉｑｕｅ ｏｆ Ａｍｅｒｉｃａ，２００７，１０４（１８）：７３２７－７３３１．
