第 29 卷 第 6 期 No. 6 Vol. 29 计算机工程与设计 Computer Engineering and Design 2008 年 3 月 Mar. 2008 蚁群算法求解分布式系统任务分配问题 王灵霞， 张远平， 吴佩莉 (兰州理工大学 计算机与通信学院，甘肃 兰州 730050) 摘 要：蚁群算法 是受自然界蚂蚁 觅食过程中，基 于信息素的最短 路径搜索食物 行为的启发提出 的一种智能优化 算法。研究 表明 ，在求 解复杂优化问题 方面该算法具 有一定的优越性 。任务分配问 题是一类典型的 组合优化问题。 应用蚁群算法 来解 决多 处理器分布式系 统上的任务分 配问题，一个任务只能 分配给一个处理 器处理，而一个处理 器可以处理多个 任务，其中 每个 处理器都有固定 成本和能力限 制。仿真结果表 明，该算法比禁 忌搜索和随机方 法具有更好的 求解能力。 关键 词：蚁群算法; 任务分配问题; 分布式系统; 组 合优化; 任务; 处理器 中图 法分类号：TP338.8 文章编号：1000-7024 (2008) 06-1472-03 文 献标识码：A Ant colony algorithm for task allocation problem in distributed system WANG Ling-xia, ZHANG Yuan-ping, WU Pei-li (School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China) Abstract：Ant colony algorithm (ACA) is an intelligence-optimized algorithm coming from the illumination of food-seeking behavior by ants based on the shortest route of pheromone. Preliminary study indicates that it has superiority in solving complicated optimization problem. Task allocation problem is a typical combinatorial optimization problem. Ant colony algorithm is proposed for solving the task allocation problem with capacity constraint and fixed cost associated with each processor in distributed system, which each task can be assigned to only one processor, but each processor can execute a number of tasks. The simulation results show that ant colony algorithm can solve it more efficiently than tabu search and random method. Key words：ant colony algorithm; task allocation problem; distributed system; combinatorial optimization; task; processor 0 引 言 1 任务分配问题的数学描述 任务分配问题是一类典型的组合优化问题。多处理器分 本文所考虑的任务分配问题的模型[6]为：给定一个任务集 布式系统上的任务分配问题是指：在分布式计算环境下，如何 最有效地利用系统资源来完成一组有限的任务集合。这方面 的研究结果在大规模数值计算、VLSI 和计算机网络技术方面 都有很好的应用背景。 近年出现的启发式算法模拟退火算法[1-2]、遗传算法[3-4]、具 有混沌特性的神经网络[5]、禁忌搜索[6]，以及蚂蚁算法[7]为解决 此类问题提供了新的途径。蚁群算法是近年新出现的一种从 群体智能思想演变而来的新算法，在解决大规模组合优化问 题上显示了强大的实力。文献[7]运用改进的蚂蚁算法来求解 简单的任务分配问题，即一个任务只能分配给一台机器处理， 且每台机器只能处理一个任务。 本 文应 用 蚁群 算法 来 解决 分布 式系 统 上的 任务 分配 问 题，即一个任务只能分配给一个处理器处理，而一个处理器可 以处理多个任务。 , ｝，一个处理器集合 =｛1,2, 合 =｛1,2, , ｝， 表示任务 的 KOP(thousand operations per second)生产能力。处理器 的固定 成本和能力分别用 和 表示。 表示任务 与任务 之间的通 讯开销，并且只有当任务 与任务 被分配给不同的处理器时 才有 ，假设 = 。 是 0-1 决策变量， = 1意味着第 个任务 由第 台处理器处理， = 0意味着第 个任务不由第 台处理器 处理。如果处理器 被使用过，则 = 1；否则 = 0。该问题的数 学模型为 1 = min 1 + = 1 = +1 = 1 = 1 . . = 1 = 1 ≤ ，= 1, , = 1，= 1, , , ｛0,1｝ = 1, , ，= 1, , (1) (2) (3) (4) E-mail：wanglingxia122@sohu.com 收稿日期：2007-05-08 基金项目：甘肃省自然科学基金项目 (3ZS051-A25-037)。 作者简介：王灵霞 (1981－)，女，甘肃甘谷人，硕士研究生，研究方向为算法设计与分析、图论； 张远平 (1966－)，男，安徽无为人，博士， 教授，硕士生导师，研究方向为算法设计与分析、图论、组合论、矩阵分析、信息论等； 吴佩莉 (1975－)，女，甘肃兰州人，硕士研究生，研 究方向为软件工程、知识管理。 － 1472 － 

限制条件(2)保证了所有分配到处理器 的任务的 KOP 需 求总和不会超过处理器 的能力 ，同样说明处理器可以处理 多个任务。限制条件(3)确保了每个任务只能在一台处理器处 理。我们的任务是求解如何分配处理器，才能在完成总任务 的条件下，使得总的花费代价最小。当处理器数目为 2 时，该 问题转化为最低成本割截问题，可以使用网络流技术来有效 地解决它。而当处理器个数大于 2 时，该问题是 NP-难的。 蚁为它们分配一个新的处理器。当一次迭代完成后，禁忌表 被清空，而且蚂蚁又可以自由选择。 考虑该问题中每台处理器能力的限制，我们给每一台处 理器定义一个标识表 ：如果 ≥0，则 = 1， = 1 意味着处理器 可以处理任务 ；否则 = 0，所有分配到处 理器 的任务的 KOP 需求超过了该处理器的能力限制，处理器 被禁止直到所有的任务都被处理完。 2 基本蚁群算法 Dorigo 首先提出了蚁群算法。蚁群算法是模仿真实的蚁 群行为而提出的一种模拟进化算法。蚂蚁个体之间是通过一 种称之为信息素的物质进行信息传递，从而能相互协作，完成 复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上 留下信息素，而且蚂蚁在运动过程中能够感知这种物质的存 在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该 物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集 体行为便表现出一种信息正反馈现象：某一路径上走过的蚂 蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间 就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的 可能的较短路径。 蚁群算法的步骤可简要地表述为：①设置所有参数，信息 素痕迹初始化；②每只蚂蚁根据状态转移规则建立一个完整 的解，状态转移规则主要取决于信息素和启发式信息；③更新 信息素。这 3 个过程重复直到满足终止条件。 实际上，蚁群算法目前已成功地应用到不同的连续和组 合优化问题，比如旅行商问题(traveling saleman problem，TSP)[8]、 连续函数优化[9]、网格分割问题[10]等。 3 蚁群算法求解任务分配问题 在用于任务分配问题求解的蚁群算法中，每一个人工蚂 蚁是具有下述特性的智能体： (1)当它选择把任务 指派给处理器 时，它会在连接 , 上 留下一种称为痕迹的物质 (等价于信息素)； (2) 它以一定的概率 为一指定任务 选择处理器 ，该概 率为在连接 , 上的启发式信息 和的痕迹量 的函数； (3)在构造一个完整的解时，已经被处理的任务被加以禁 止，所有分配到处理器 的任务的KOP 需求如果超过该处理器 的能力限制，即 ≤0，= 1, , ，则该处理器也被禁止， = 1 在每次迭代开始时， = 1, = 1，也就是说，所有 处理器可以处理任意一个任务，当处理器 处理完某个任务 , ， 后， = 1，更新处理器 的容量 = 了第 +1个即将分配的任务时，计算 ，= 1, +1，如果 , 。当蚂蚁选择 +1≥0，则 = 0，处理器 = 1，任务 +1可以被处理器 处理；否则 被禁止。当一次迭代完成后，标识表 重新赋值为 1。 第 只蚂蚁为第 个任务分配第 台处理器的概率是 = ， ，= 1, , ，= 1, , (5) 式中：，——体现信息素和启发式信息对蚂蚁决策重要性的 两个参数， ——所有符合 = 1的处理器的集合，也 即可用处理器的集合，启发式信息 用下式进行计算 = cos , 1 1 cos 1 (6) 式中： 1——第 只蚂蚁 1个任务的分配方案集合， 与将 , 增加到 1时新增加的额外成本成反比。 在一只蚂蚁完成了所有任务的分配之后，信息素按下式 进行更新 (7) 0≤ ≤1) 为信息素的挥发系数，1 表示随着时间的推 移信息素浓度的残留程度；在分配方案中，如果任务 被分配 + 1 给了处理器 ，则 = / ，其中， 是一个常数，表示此方案中 蚂蚁释放的信息素总量， 表示该任务分配方案所对应的成本 值；否则 = 0。式(7)表明只有属于分配方案中连接 , 上的 信息素才会得到增强。 上述过程重复直到满足终止条件，蚁群算法求解任务分 配问题的过程如下： 设置参数，初始化信息素强度； while (不满足终止条件时) for 蚁群中的每只蚂蚁 for 每个任务(直到所有任务都被处理完) 判断 中处理器的个数，蚂蚁根据式(5) 如此重复直到所有的任务都已被处理器处理为止。 为每个任务分配处理器； 该启发式算法使用由 只蚂蚁组成的群体来一步步地进 行解的构造。每只蚂蚁代表建立解的一个独立过程，这个过 程分两步来完成：①蚂蚁选择将要被分配的任务；②对每个已 经选择的任务，分配处理器执行它。若干蚂蚁过程之间通过 信息素值来交换信息，合作求解并不断优化。所有任务均被 处理器处理完意味着蚂蚁建立解过程的结束。 end end 根据式(7)对属于分配方案中的边进行全局信息素更新； end 4 仿真结果 类似于 TSP 问题，在分配之前，可先为每只蚂蚁建立一个 数据结构，称为禁忌表。 表示第 只蚂蚁的禁忌表， 是这个禁忌表 的第 个元素。 禁忌表 记 忆了已经指派 过 的任务，并在一次迭代结束(即构造了一个完整的解)前禁止蚂 为了验证方法的可行性及效率，对不同规模大小的几组 数据(使用文献[5]中产生随机问题集的方法得出)进行实验。 用蚁群算法仿真计算时，给 赋相同的初始值 1，最大循 , 环次数 max = 1000， = 100，蚂蚁个数与任务总数相等，对 , － 1473 － 

取不同值进行测试。参数的默认值设为 = 2， = 3， = 0.5每次 实验 只 有 一个 参 数 被改 变 ，被 测 试的 值 为： ｛0,1,2,3,4,5｝， ｛0,1,2,3,4,5｝， ｛0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1｝。 实验结果表明，当 = 0或者 = 0时，算法性能最差；如果 = 0，则算法相当于随机贪婪启发式算法。如果 = 0，将只有 信息素起作用，只是一个正反馈过程，这种方法将导致早熟收 敛，因此实验中得到的解质量很差，启发式信息与信息素轨迹 浓度的结合是十分必要的。比如对于 8× 5(8 个任务，5 个处理 器) 的任务分配问题，当 = 3, = 1, = 0.7时，取得较好的结果 5807；而 15× 5 的问题，当 = 3, = 4, = 0.7时，取得较好解 6870。 对蚁群算法进行测试之后，针对相同的数据集再分别利 用随机方法和禁忌搜索求解。3 种算法得出的计算结果如表 1 所示，比较可以看出蚁群算法取得的结果较好。 算法与其它启发式算法，比如遗传算法、禁忌搜索、模拟退火 算法等结合来求解任务分配问题，这一点值得进一步研究。 参考文献: [1] Hamam Y,Hindi K S.Assignment of program modules to proces- sors: A simulated annealing approach [J]. European Journal of Operational Research,2000,122:509-513. [2] Attiya G,Hamam Y.Task allocation for maximizing reliability of distributed systems: A simulated annealing approach[J].Journal of Parallel and Distributed Computing,2006,66:1259-1266. [3] 张聪,马义忠.异构计算机系统中基于遗传算法的任务分配与 调度[J].微电子学与计算机,2004,24(6):74-78. [4] 钟求喜,谢涛.基于遗传算法的任务分配与调度[J].计算机研究 与发展,2000,37(10). 规模 8× 5 10× 6 13× 5 15× 5 18× 7 20× 8 5 结束语 表 1 不同算法的计算结果比较 [5] 王秀宏,王正欧,乔清理.用具有混沌特性的神经网络解任务分 随机方法 禁忌搜索 蚁群算法 配问题[J].系统工程学报,2001,16(2):146-150. 5838 5213 6658 7079 10 251 14 262 6049 5397 6840 8677 10 787 14 498 5807 4938 5929 6870 10 443 13 958 [6] Chen W-H,Lin C-S.A hybrid heuristic to solve a task allocation problem [J]. Computers and Operations Research, 2000,27: 287-303. [7] 杨冬,王正欧.改进的蚂蚁算法求解任务分配问题[J].天津大学 学报,2004,37(4):373-376. [8] Kaji T.Approach by ant tabu agents for traveling salesman prob- lem [C]. Proceedings of the IEEE International Conference on Systems,2001:3429-3434. 通过仿真实验及比较分析，证明蚁群算法可以有效地解 [9] 魏平,熊伟清.用于一般函数优化的蚁群算法[J].宁波大学学报, 决任务分配问题。但是该算法也存在一些缺点，比如求解需 2001,14(4):52-55. 要较长的搜索时间，而且该方法容易出现停滞现象，即搜索进 行到一定程度且所有个体所发现的解完全一致，不能对解空 间进一步搜索，不能发展更好的解。鉴于此，可以考虑将蚁群 [10] Korosec P,Silc J.Solving the mesh-partitioning problem with an ant-colony algorithm [J]. Parallel Computing, 2004,30 (5-6): 785-801. (上接第 1461 页) 4 结束语 基于身份的环签名方案，消除了证书的有效性检测需要 和注册证书的需要。由于双线性对的计算消耗比较大，在设 schemes[C].ICICS.Berlin:Springer-Verlag,2004. [5] Amit K Awasthi,Sunder Lal.ID-based ring signature and proxy ring signature schemes from bilinear pairings[EB/OL].http:// eprint.iacr.org/2004/184.pdf,2004. 计基于双线性对的环签名时，应尽可能减少双线性对的计算。 [6] 王继林,张键红,王育民.基于环签名思想的一种类群签名方案 本文构造了一个基于身份和双线性对的环签名方案，相对于 [J].电子学报,2004,32(3):408-410. 已知的基于身份和双线性对的环签名方案，新方案所需计算 [7] Dan Boneh,Xavier Boyen,Hovav Shacham.Short group signa- 消耗最少，并且在随机预言机模型中是可证安全的。 tures[C].Crypto.Berlin:Springer-Verlag,2004. 参考文献: [1] Rivest R,Shamir A,Tauman Y.How to leak a secret[C].Asiacrypt. [9] Berlin: Springer-Verlag,2001. [2] Zhang Fangguo,Kwangjo Kim.ID-based blind signature and ring signature from pairings [C]. Asiacrypt. Berlin: Springer-Verlag, 2002. [3] Lin ChihYin, Wu TzongChen. An identity-based ring signature scheme from bilinear pairings [EB/OL] .http://eprint.iacr.org/ 2003/117,2003. Javier Herranz,German Saez.New identity-based ring signature [4] － 1474 － [8] Dan Boneh,Xavier Boyen.Short signatures without random Ora- cles[C].Eurocrypt.Berlin:Springer-Verlag,2004. Jae Choon Cha, Jung Hee Cheon. An identity-based signature from gap Diffie-Hellman groups[EB/OL].http://eprint.iacr.org/ 2002/018,2004. [10] Xun Yi.An identity-based signature scheme from the weil pai- ring[J].IEEE Communications Letters,2003,7(2):76-78. [11] Javier Herranz,German Saez.Forking lemmas for ring signature scheme[C].Indocrypt.Berlin:Springer-Verlag,2003. [12] Pointcheval D, Stern J. Security arguments for digital signatures and blind signatures[J].Journal of Cryptology,2000,13(3):361-396.