第２２卷第４期 聊城大学学报（自然科学版） Ｖｏ１．２２ Ｎ ４ ２００９年１２月 Ｊｏｕｒｎａｌ ｏｆ Ｌｉａｏｃｈｅｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔ．Ｓｃｉ．） Ｄｅｃ．２００９ 一种求解多处理机调度问题的自适应蚁群算法 陈 晶Ｄ 刘加中 （”聊城大学计算机学院，山东聊城２５２０５９， 山东新时代药业，山东费县２７３４００） 摘要将蚁群算法应用于求解多处理机调度问题，提出一种自适应蚁群算法．算法以最小化 ｍａｋｅｓｐａｎ为调度目标，根据蚂蚁留下的信息素指导蚁群在解空间展开全局搜寻，将任务分配在 恰当的机器上，并通过自适应调整阈值实现全局探索与精细查找的平衡．实验结果表明算法具有 较好的优化性能． 关键词 多处理机调度，蚁群算法，启发式算法 中图分类号ＴＰ３０１ 文献标识码Ａ 文章编号１６７２—６６３４（２００９）０４—００８６－０４ Ｏ 引言 近年来以最小化ｍａｋｅｓｐａｎ为目标的多处理机调度问题日益受到学者的重视并加以研究．多处理机 调度是一类重要的组合优化问题，具有广泛的生产应用背景，如并行与分布式计算、工农业生产、交通运输 行业等．其研究内容是将一批给定的任务（或作业）分配给多个处理器资源，以获得最小的生产周期．多处 理机调度问题已被证明是ＮＰ完全问题［１］，不存在多项式时间复杂性的算法以找到问题的最优解．目前研 究这类问题的算法较多，大都属于启发或近似算法，在降低问题复杂度的同时尽可能问题解的要求，如 ＬＩＳＴＦＩＴ［２］等元启发式算法（Ｍｅｔａ Ｈｅｕｒｉｓｔｉｃ Ａｌｇｏｒｉｔｈｍ），这些算法在问题规模增大时效果不尽人意；伴 随着近年来现代智能优化算法的出现，不少学者运用模拟退火算法、微粒群算法求解多处理机调度问题， 并取得了一定的成绩． 受到自然界中真实蚁群觅食行为的启发，意大利学者Ｍ．Ｄｏｒｉｇｏ等人于２Ｏ世纪９Ｏ年代初提出了蚁 群优化算法（ＡＣＯ，Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）［引．该算法是一种基于群体智能的全局进化搜索 算法，具有较强的鲁棒性、自组织性和正反馈性等优良特性，一经提出就引起了学者的广泛重视，算法最早 成功应用于求解旅行商（ＴＳＰ，Ｔｒａｖｅｌｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ）问题，后来被推广到求解各种组合优化问 题，如工件排序问题、图着色问题、车辆调度问题等，研究证明该算法在求解复杂优化问题方面具有明显的 优越性．本文使用蚁群优化算法对多处理机调度问题进行了研究，首先给出了多处理机调度问题建模的方 法，然后使用蚁群优化算法进行了全局分配寻优算法设计，最后利用设计的算法对ｂｅｎｃｈｍａｒｋｓ问题进行 了仿真，验证了算法的正确性和有效性． １ 问题描述 多处理机调度问题通常用Ｐ『ｌ Ｃｍ 表示，其描述如下：设有 个任务Ｊ一（Ｊ ，Ｊ：，…，， ）和ｍ台 机器Ｍ一（Ｍ１，Ｍ２，…， ），每个任务仅有一道工序，可以安排到任一处理机上 行，任务在运行过程中 不允许被中断，任务具有原子性，不能拆分成更小的子任务，调度目标是将 个任务合理地分配到ｍ台机 收稿日期：２００９—０３—０５ 基金项目：山东省自然科学基金资助项目（２００４ＺＸ１４）、山东省教育厅科研发展计划（Ｊ０９ＬＧ２９）和山东软科项目 （２００９ＲＫＢ１２５） 通讯作者：陈晶，Ｅ－ｍａｉｌ：ｃｈｅｎｊｉｎｇｌ＠ｌｃｕ．ｅｄｕ．．ｃｎ． 第４期 陈 晶：一种求解多处理机调度问题的自适应蚁群算法 ８７ 器上执行，使总的执行时间（ｍａｋｅｓｐａｎ，又称为调度长度）最短．设任务Ｊ 的估计执行时间为Ｐ ，若处理机 Ｍｉ上获得的任务子集为Ｓ ，处理机Ｍｉ的完成时间表示为Ｃ ，则ｍａｋｅｓｐａｎ可定义为ｍａｘＣｉ．多处理机调 度的数学模型可表示如下 ａｒｉｎｙ—ｒａｉｎ（ｍａｘＣｆ≤ｆ≤ ）一ｍｉｎ（ｍａｘ∑Ｐ ）ｓｌ＜／＜ｍｅ ．ｔ．Ｐ‘≥ｏ 忌一１，…，扎，＞：ｌｉ—＝—１ ｓ Ｉ一，ｚ ｉ一１，…， ， 其中，ｌ Ｓ埘ｉ表示机器Ｍｉ分配的任务数量． ２基本蚁群算法 仿生学家经过大量研究发现，蚂蚁个体之间是通过一种称为信息素的物质进行信息传递的，觅食中的 蚂蚁在经过路径上能够留下信息素，而且蚂蚁通过感知信息素的强度来指导自己的运动方向，并倾向于朝 着信息素强度高的方向移动．因此蚂蚁群体的觅食行为表现出一种信息正反馈现象：路径越短，走过的蚂 蚁越多，留下的信息素强度也就越大，因此后来者选择该路径的概率就越大．蚂蚁个体通过这种方式来选 择最短路径并达到搜索食物的目的．蚁群优化算法正是基于模拟蚁群的觅食行为而提出的一种优化算 法［３］．下面以 个城市的ＴＳＰ问题为例介绍基本蚁群系统模型： 设 是蚁群中蚂蚁的数量， 为ＴＳＰ规模，即城市数，ｄ （ ， 一１，２…．， ）表示城市 和城市 之间 的距离，ｂ （ ）表示 时刻位于城市ｉ的蚂蚁数目， （￡）表示ｔ时刻在城市ｉ， 问的路径上残留的信息量． 初始时刻，各条路径上信息量相等，设 （ｏ）＝＝＝Ｒ（Ｒ为常数）．蚂蚁ｋ（五一１，２…．，ｍ）在运动过程中，根据 各条路径上的信息量决定转移方向． （ ）表示在ｔ时刻蚂蚁ｋ由城市ｉ转移到城市Ｊ的概率 ∽一ＪＩｆｌ 。 ｎ 。 。擘）＿ ７， Ｊ∈ ｌ一 ｌｏｗｅｄ ，， （１） ｏ，其 ， 式中，ａ为在路径（ ， ）上残留信息的重要程度；吼为先验知识或称为能见度，在ＴＳＰ问题中为城市ｉ转移 到城市Ｊ的启发信息，一般取７１ｏ一１／ｄ ，说明较近的城市有更大的可能性被选中；卢为启发信息的重要程 度；与实际蚁群不同，人工蚁群系统具有记忆功能，ｔａｂｕ （志一１，２ ．．， ）用以记录蚂蚁ｋ当前所走过的 城市，称为禁忌表，集合ｔａｂｕ 随着进化过程作动态调整．ａｌｌｏｗｄ 一（Ｃ—ｔａｂｕ ）表示蚂蚁ｋ下一步允许 选择的城市集合，其中ｃ表示全部的城市集合． 经过 个时刻，所有蚂蚁都完成了对 个城市的遍历，将ｔａｂｕｔ清空，计算每一只蚂蚁所走过的路径 ，并保存最短路径．所有蚂蚁从上一次的出发点开始，准备进行下一轮的遍历． 为避免信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或遍历ｎ个城市后，对路径上的 残留信息按照式（２）进行更新处理 （￡＋，ｚ）一（１一ｐ）・ （￡）＋△ ＝∑Ａｒ ， （２） △ 一∑△ｒ ， △ 一 芒，当第足只蚂蚁经过路径（ｆ，－『）时， ｌ０，当不经过时， 其中，参数ｐｃＥｏ，１）表示信息素挥发系数，△ 表示本次循环中路径（ ， ）上的信息素增量，△ｒ 表示第ｋ 只蚂蚁在本次循环中留在路径（ｆ，．『）上的信息量，Ｑ为常数， 表示第ｋ只蚂蚁在本次循环中所走过的路 径的长度． 一般设置遍历次数计数器Ｎ ，当达到设定值时结束，输出找到的最短路径Ｌ ．ｍ． ８８ 聊城大学学报（自然科学版） 第２２卷 ３ 求解多处理机调度的自适应蚁群算法 与ＴＳＰ问题不同，基于ＡＣＯ算法求解多处理机调度算法的关键问题是需要与特定问题域结合，采用 恰当的编码方案，并将信息素更新公式和随机概率选择公式重新进行定义，使蚂蚁的搜索过程与问题的寻 优达到一致和统一．下面首先介绍算法思想． ３．１ 问题定义、编码方案及适应值表示 设有ｄ只蚂蚁，对于 个任务、 台处理机的调度问题，每只蚂蚁工作，每经过￡个时刻遍历一 次，为 个任务选择处理机，完成１次任务分配．用 维向量（ ，ｄ：…．，ｄ ）表示一只蚂蚁一次周游获得 的一个调度方案，ｄ 表示任务Ｊ 分配到处理机ｄ （１≤ｄ ≥ｍ）上执行．例如 一５，ｍ＝２时，向量（１，１，２，２， １）对应一个可行解，第二个元素“１”表示把任务２分配到处理器１上执行． 本问题中，将调度长度ｍａｋｅｓｐａｎ作为调度方案的适应值用来评价解的质量，将蚁群经过多次迭代后 搜索到的具有最小ｍａｋｅｓｐａｎ的解作为最优解输出． ３．２随机概率选取规则 在多处理机调度问题中，将各符号的含义重新定义如下ｒ （ ）表示 时刻蚂蚁群体在搜索过程中将任 务Ｊ 分配在机器Ｍｊ上时所留下的信息素浓度；ＦＳ 为机器Ｍ 在ｔ时刻的可用时间，若Ｓ 是Ｍ 已分配的 任务集合，则 一 ：Ｐ ；ＬＢ定义为（ ：Ｐ ）Ｉｎ，显然ＬＢ是调度问题的解的下界，如果存在的话，将是问 ∈Ｓ１ ｉ １ 题的最优解； 为先验知识，定义为ＦＳ ／（ＬＢ－ＦＳ ），当机器Ｍｌ上未分配任务时，珈最大， 上的负载越大，珊越 小，使得该机器被选中的概率越小；上式中出现＂ＬＢ￣ＦＳ 时，说明该处理机的负载已经基本饱和，令 一 ０，以避免出现个别机器负载过重的现象． △矗定义为ｊ ’当第五只蚂蚁经过路径 ，＿『 时， ｌ０，当不经过时． 本文使用全局信息素更新规则，蚂蚁ｋ将依据下式按伪随机比例规则为任务．厂 选择机器Ｍ （ａｒｇ…Ｉｎｒｄｘ，ｒ；・ ，ｉｆｑ≤ｑｏ， ｓ＝ 。ｕｏ 。ｄ＾ （３） ｌ公式（１），ｅｌｓｅ． 其中，ｑ。是［Ｏ，１］区间的一个常数；ｑ为［Ｏ，１］区间均匀分布的随机数，当ｑ≤ｑｏ时，按先验知识选择最好的 下一点，否则按基本蚁群算法中的随机比例规则概率的选择下一点． ３．３ 自适应阈值的设计 下面重点讨论ｑ。的选取． 作为一种演化算法，ＡＣＯ需要在“探索”和“利用”（ｅｘｐｌｏｒａｔｉｏｎ ａｎｄ ｅｘｐｌｏｉｔａｔｉｏｎ）之间建立一个平衡 点，而阈值ｑ。的大小就体现了先验知识与探索新路径之间的相对重要性，恰当的ｑ。值既能够保证算法的 搜索空间尽可能的大，又能在迭代后期将搜索重点放在较好个体的临近区域内．传统的ＡＣＯ算法为ｑ。选 取常数值表示，本文将ｇ。重新定义如下： 一ｌｏｇＮ￣／ｌｏｇ Ｎ ，其中Ｎ 表示算法规定的最大迭代次数， Ｍ为当前迭代次数． 根据上述定义，ｑ。将随着算法的执行而发生动态变化．经过分析不难发现，在迭代初期ｑ。较小，这时 蚂蚁倾向于依据随机比例规则选择路径，以保证算法能够搜索足够大的解空间；随着迭代次数的增加，ｑ。 逐渐增大，蚂蚁将以较大的概率选择精英蚂蚁走过的路径，向具有最优解的区域靠拢．可见，ｑ。的这种自 适应的变化能够很好的在探索与利用之间建立一种平衡关系． 由此可得求解任务分配问题的蚁群算法如下：（１）初始化蚁群算法控制参数，设置初始信息素；令ｚ 一０，循环计数器Ｎ 一０，设定初始信息量 （Ｏ）一Ｒ，△ —Ｏ，ｍ只蚂蚁分别随机选择一个任务 ，并将其 第４期 陈晶：一种求解多处理机调度问题的白适应蚁群算法 ８９ 随机分配到一台机器上，ｔａｂｕｋ＝｛夕 ）．（２）依据公式（３）给出的伪随机概率选取原则，每只蚂蚁分别为所 有任务依次选择目标机器直至ａｌｌｏｗｄ 为空；（３）利用适应值评价函数对各蚂蚁构建的分配方案给出评 价，并利用评价结果根据公式（２）进行信息素更新；（４）蚁群找到的最优分配方案满足要求或算法迭代次 数大于最大允许值？若是，则循环结束；否则，转向步骤（２）．（５）输出算法找到的最好解，算法终止． ４仿真实验及结果 以ＶＣ＋＋作为开发环境，采用ｂｅｎｃｈｍａｒｋｓ问题对算法进行仿真，验证了算法的有效性．数据来源于 文献Ｅ５１，设有３台处理机和９个作业，作业需要运行时间分别为８１，４Ｏ，２６，４，６５，９８，５３，７１，１５． 采用经典启发式算法ＬＰＴ、模拟退火算法和本文算法分别测试其调度性能．本文算法的参数设置为： 蚂蚁数目为１Ｏ，口一１，口一５，Ｒ一１，最大迭代次数为５Ｏ次．模拟退火算法和本文算法均重复测试１００次，统 计出最好解、最差解、最好解的次数和平均解．已知问题的最优解是１５１（即该问题的ＬＢ值）．经计算，ＬＰＴ 算法求得的最小ｍａｋｅｓｐａｎ为１６０，无法获得问题的最优解．表１给出了另外两种算法仿真实验的结果，并 与文［５］的实验数据进行了对比． 表１实验结果比较 图１不同迭代次数达到的调度长度 表中第二行数据选取的是文Ｅｓ］的最优结果．比较可知：采用本文算法在求解处理机调度问题时具有 更小的平均调度长度，而且性能更为稳定，大多数情况下都能找到最优解，其最好解出现的次数优于模拟 退火算法及文［５］中的算法． 为了观察算法的收敛特性，图１给出了算法在５Ｏ次迭代过程中的调度长度变化曲线，从图中可以看 出，算法具有较好的收敛特性，能够比较快地找到问题的最优解． ５ 结束语 针对多处理机调度问题，提出了一个自适应蚁群调度算法，算法中使用蚁群算法进行全局寻优，通过 动态变化的阈值控制算法的搜索粒度，使算法在空间探索和局部精化间取得了很好的平衡，仿真实验表明 该算法具有良好的性能．蚁群算法存在的问题是算法运行时间较长，并且容易陷入局部最优，因此与其他 算法融合以避免算法的早熟收敛是下一步的研究重点． 参考文献 ［１］Ｇａｒｅｙ Ｍ Ｒ，Ｊｏｈｎｓｏｎ Ｊ Ｓ．Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｔｒａｃｔａｂｉｌｉｔｙｌ Ａ Ｇｕｉｄｅ ｔｏ ｔｈｅ Ｔｈｅｏｒｙ ｏｆ ＮＰ—Ｃｏｍｐｌｅｔｅｎｅｓｓ［Ｍ］．Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＣＡ：Ｆｒｅｅ— ｍａｎ，１９７９． ［２］Ｏｕｐｔａ ＪＮＤ，Ｒｕｉｚ—Ｔｏｒｒｅｓ ＡＪ．Ａ ＬＩＳＴＦＩＴ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｍｉｎｉｍｉｚｉｎｇ ｍａｋｅｓｐａｎ ｏｎ ｉｄｅｎｔｉｃａｌ ｐａｒａｌｌｅｌ ｍａｃｈｉｎｅｓ［Ｊ］．Ｐｒｏｄｕｃｔｉｏｎ Ｐｌａｎｎｉｎｇ ｂ－ Ｃｏｎｔｒｏｌ，２００１，１２（１）：２８～３６． ［３］Ｄｏｒｉｇｏ Ｍ，Ｍａｎｉｅｚｚｏ Ｖ，Ｃｏｌｏｒｎｉ Ａ．Ａｎｔ Ｓｙｓｔｅｍ：Ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ ａ Ｃｏｌｏｎｙ ｏｆ Ｃｏｏｐｅｒａｔｉｎｇ Ａｇｅｎｔ［刀．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ， Ｍａｎ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ—Ｐａｒｔ Ｂ（Ｓ１０８３－４４１９），１９９６，２６（１）ｚ ２９～４１． ［４］段海滨，王道波，于秀芬．蚁群算法的研究进展评述口］．自然杂志，２００６，２８（２）：１０２￣１０５． ［５］ 高 尚，杨静宇．多处理机调度问题的粒子群优化算法［Ｊ］．计算机工程与应用，２００５，４１（２７）：７２～７３．
