（计算机应用技术专业论文）应用蚁群算法解决多处理机调度问题的研究.pdf

于广建：应用蚁群算法解决多处理机调度问题的研究 摘要 并行分布式处理是当前计算机发展的主要挑战问题之一，也是当前计算机科 学的一个热点。在并行分布计算中，调度问题是分布计算的瓶颈问题之一。这个 问题对发挥系统的并行计算能力、提高系统吞吐量具有非常重要的影响。良好的 调度算法可以充分运用系统中每个处理机的计算能力，提高并行分布计算的效率。 调度问题得不到解决，则会导致分布计算效率低下。 上世纪5 0 年代中期创立了仿生学，蚁群算法正是从仿生学的机理中受到启发 而提出的一种新型进化算法和启发式随机搜索算法。蚁群算法具有分布式、鲁棒 性好以及易于与其他方法结合的优点。蚁群算法主要用于求解不同的组合优化问 题。目前蚁群算法的研究已经渗透到了多个应用领域，可以解决多维动态组合优 化问题、离散优化问题等。 处理机调度问题属于组合最优化问题，更是离散优化问题。而蚁群算法在求 解离散优化问题上的卓越性能为使用蚁群算法求解处理机调度问题提供了可行 性。 本文主要研究蚁群算法在处理机调度问题中的应用。文章首先详细介绍调度 问题和蚁群算法的定义、模型及其研究现状等，分析讨论了当前国内外一些求解 调度问题的各类算法，为利用蚁群算法求解处理机调度问题提供了一定的理论基 础。 文章的主体部分包括三个方面：基于蚁群算法求解处理机调度问题、基于混 合蚁群算法求解处理机调度问题以及基于蚁群算法求解实时系统中有时限约束的 调度问题。文章的主要贡献及创新之处如下所示： 1 文章提出了一种求解多处理机调度问题的蚁群优化算法。该算法在d a g 图的基础上，用a o e ( a c t i v eo ne d g e ) 图来表示任务之间拓扑顺序，图中的每一边 条代表一个任务，边上的权重表示该任务的完成时间。a o e 图比一般的d a g 图 更能表现出任务之间的优先约束关系，也能更好地贴近蚁群算法的设计思路。其 次，将关键路径、任务的最早开始时间和任务的最迟开始时间等多种因素有机结 合在一起，设计出了概率公式，避免了任务选择策略的单一，在一定程度上避免 陷入局部最优解。最后用任务之间的“配合程度”来定义信息素，加快了算法的 i i 扬州大学硕士学位论文 收敛速度。 2 文章提出了一种适合蚁群算法的任务分配模型( t a s k a l l o c a t i o nm o d e l ， t a m ) ，该模型结合具体类型的处理机调度问题的特点，具有很好的可扩充性和灵 活性。在t a m 的基础上，设计了基于t a m 的求解处理机调度的蚁群算法。为了 克服蚁群算法的收敛速度慢、易陷入局部最优等局限性，我们在蚁群算法中加入 遗传算予，设计了一种混合蚁群算法。充分发挥了两者的优点，既保证了较高的 搜索效率，又保证了解的全局最优性；最后，在t a m 的基础上，对动态处理机调 度算法的设计与实现进行了探讨，为进一步的研究工作奠定了基础。 3 文章提出一种求解有时限约束的调度问题的蚁群算法( t h ea c of o r d e a d l i n es c h e d u l i n gp r o b l e m ，简称a d s d ) 。此算法首先对任务集所对应的d a g 图 进行了扩展，得到了扩展的d a g 图。根据这种设计，人工蚂蚁在图中遍历可以得 到任务的拓扑序；此算法包括两种优化，一方面是任务列表的优化；另一方面是 处理机分配策略的优化。由这两种优化衍生出两种概率公式的设计和两种信息素。 算法利用启发式信息保证优先调度截止时间最早的任务，通过概率选择保证了其 它情况的出现，避免出现局部最优解。 上述三种算法的实验结果表明，我们提出的算法比其他类似的算法在较短的 时间内找到更好的调度策略，更具有鲁棒性和灵活性。 关键字：蚁群算法、调度、任务分配模型、d a g 、时限约束 于广建：应用蚁群算法解决多处理机调度问题的研究 i i i a b s t i 。a c t i nr e c e n tt i m e ，p a r a l l e la n dd i s t r i b u t e dc o m p u t a t i o ni so n eo ft h em a i nc h a l l e n g i n g a r e a si nt h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y i ti sa l s oaf o c u so ft h er e s e a l e hi n c o m p u t e rs c i e n c e t h es e h e d u l i n gp r o b l e m i sab o t t l e n e c ki nt h ep a r a l l e la n dd i s t r i b u t e d c o m p u t a t i o n t i l i sp r o b l e mg r e a t l y a f f e c t st h ep a r a l l e lc o m p u t i n gc a p a b i l i t ya n dt h e p e r f o r m a n c eo ft h ep a r a l l e ls y s t e m ag o o ds c h e d u l i n ga l g o r i t h m c a l lt a k ef u l l a d v a n t a g eo f t h ec o m p u t i n gc a p a b i l i t yo f e a c hp r o c e s s o ri nt h es y s t e m ，a n dc a ni m p r o v e t h ee f f i c i e n c yo ft h ep a r a l l e la n dd i s t r i b u t e dc o m p u t a t i o n t h ee f f i c i e n c yo f t h ep a r a l l e l a n dd i s t r i b u t e ds y s t e mw i l lb ed e c r e a s e di ft h et a s k si nt h es y s t e mc o u l dn o tb e s c h e d u l e dp r o p e r l y s i n c et h em i d - 1 9 5 0 s ，w h e nb i o n i c sw a sa d v a n c e d ，m a n yn e we v o l u t i o n a l a l g o r i t h m sa n dh e u r i s t i cr a n d o m - s e a r c ha l g o r i t h m sh a v eb e e np r e s e n t e d a m o n gt h e s e o p t i m i z a t i o na l g o r i t h m s ，a n tc o l o n yo p t i m i z a t i o n ( a c o ) a l g o r i t h mi sa no p t i m i z a t i o n m e t h o di n s p i r e df r o mt h em e c h a n i s mo fb i o n i c s a c oa l g o r i t h mi ss t a b l e ，d i s t r i b u t e d a n dc a ne a s i l yb ec o m b i n e dw i t ho t h e rh e u r i s t i co p t i m i z a t i o nm e t h o d s t h ea c oh a s b e e na p p l i e di nm a n yc o m b i n a t i o no p t i m i z a t i o np r o b l e m s i th a sd e m o n s t r a t e si t ss 仃o n g c a p a c i t yi nc o m b i n a t i o no p t i m i z a t i o na n d d i s c r e t eo p t i m i z a t i o ne t c s c h e d u l i n gi se s s e n t i a l l y ap r o b l e mo fc o m b i n a t i o no p t i m i z a t i o na n dd i s c r e t e o p t i m i z a t i o n t h es t r o n go p t i r n i z a t i o nc a p a c i t yo fa c oa l g o r i t h mo ns o l v i n g t h e d i s c r e t eo p t i m i z a t i o ns u g g e s t st h ef e a s i b i l i t yt os o l v et h es c h e d u l i n gp r o b l e mu s i n gt h e a c o a l g o r i t h m t l l i sp a p e rf o c u s e so nt h er e s e a r c ho fa p p l y i n ga n tc o l o n yo p t i m i z a t i o ni nt a s k s c h e d u l i n gp r o b l e m s w ef i r s t i l l u s t r a t et h ed e f i n i t i o n , m o d e la n de x i s t i n gr e s e a r c h r e s u l t so fs c h e d u l i n gp r o b l e ma n dt h ea c oa l g o r i t h m t h e nw ed i s c u s e sa n da n a l y s i s s o m er e c e n t l yp r e s e n t e da l g o r i t h m sf o rs o l v i n gs c h e d u l i n gp r o b l e m ss o a st os e tu pa t h e o r e t i c a lf o u n d a t i o nf o ra p p l y i n gt h ea c oa l g o r i t h mt os o l v es c h e d u l i n gp r o b l e m s i nt h i sp a p e rt h r e ea l g o r i t h m sf o rs o l v i n gs c h e d u l i n gp r o b l e ma l ep r e s e n t e d ：t h e a c oa l g o r i t h mf o rs o l v i n gt h es c h e d u l i n gp r o b l e m ，t h eh y b r i da c oa l g o r i t h mt os o l v e t h ep r o b l e ma n dt h ea c o a l g o r i t h mf o rs o l v i n gt h et i m e r e s t r i c ts c h e d u l i n gp r o b l e m i n t h er e a l - t i m es y s t e m t h em a i nc o n t r i b u t i o n sa n di n n o v a t i o n so ft h i sp a p e ra l ea s f o l l o w s 1 t h i sp a p e rp r e s e n t sa na c oa l g o r i t h mf o rs o l v i n gt h es c h e d u l i n gp r o b l e m 1 1 1 e a l g o r i t h mu s e sa na o e ( a c t i v eo ne d g e ) g r a p h o nt h eb a s i co ft h ed a gt oe x p r e s st h e t o p o l o g i c a lo r d e ro ft h e s et a s k s i nt h i sg r a p h ，e a c he d g ep r e s e n t sat a s k ，t h ew e i g h to f t h ee d g ee x p r e s s e st h ec o m p u t a t i o nt i m eo ft h i st a s k n l ca o ec a nd e m o n s t r a t et h e i v 扬州大学硕士学位论文 r e l a t i o ns h i po ft h e s et a s k sb e t t e rt h a nd a 6i ti sa l s os u i t a b l ef o ru s i n gt h ea r t i f i c i a l a n t st ot r a v e la n ds e a r c ht h eo p t i m a ls o l u t i o n w h e nt h ea n t ss e l e c tt h ep a t h s ，t h e a l g o r i t h mp r o v i d e st h ep r o b a b i l i t yf u n c t i o nw h i c ht a k e sm a n yo ff a c t o r si n t oac o u n t ， s u c ha st h el e n g t ho fc r i t i c a lp a t h ，t h ee a r l i e s ts t a r tt i m ea n dl a t e s ts t a r tt i m eo ft a s k s i t c a ne x t e n dt h es e a r c hs p a c ef o rt h ea n t sa n dp r e v e n tt h el o c a lo p t i m i z a t i o no fr e s u l t s f i n a l l yt h ep a p e rd e f i n e dt h ep h e r o m o n e sa st h e c o o p e r a t i v ed e g r e e o ft a s k st o a c c e l e r a t et h ec o n v e r g e n c eo f t h ea l g o r i t h m 2 t h ea r t i c l ep r e s e n t sat a s k - a l l o c a t i o nm o d e l ( t a m ) w h i c ha d a p tt ot h ea c o a l g o r i t h m t h i sm o d e li ss u i t a b l ef o rt h ec h a r a c t e r so fs c h e d u l i n gp r o b l e m s ，a n dh a s g o o de x t e n s i b i l i t ya n da g i l i t y b a s e do nt h et a m ，t h ep a p e rp r e s e n t saj o bs c h e d u l i n g a l g o r i t h m ( j s t os o l v et h es c h e d u l i n gp r o b l e m t oo v e r c o m et h ed r a w b a c k so fa c o s u c ha sl o wc o n s t r i n g e n c y , l o c a lo p t i m i z a t i o n ，t h ep a p e rp r e s e n t sah y b r i da c o a l g o r i t h mn a m e d i si m p r o v e dj o b - s c h e d u l i n ga l g o r i t h mb yu s i n gg e n e t i co p e r a t o r s t h i sa l g o r i t h mc a l ls u f f i c i e n t l ye x e r tt h ee x c e l l e n c e so ft h ea c 0a n dt h eg e n e t i c a l g o r i t h m i tn o to n l y h a sb e t t e rs e a r c he f f i c i e n c y , b u ta l s oe n s u r e st h e g l o b a l o p t i m i z a t i o no fr e s u l t s t om a k eaf o u n d a t i o nf o rf u r t h e rr e s e a r c h ，t h ep a p e ra l s o d i s c u s s e st h ep o s s i b i l i t yo f a p p l y i n gd e s i g nt a mo nd y n a m i ct a s ks c h e d u l i n gp r o b l e m s 3 t h ep a p e rp r e s e n t san e wa c oa l g o r i t h mf o rd e a d l i n es c h e d u l i n gp r o b l e m ( a d s d ) f i r s t ，t h ea l g o r i t i m ae x t e n d st h ed a ga n dg e n e r a t e sa ne x t e n s i b l ed a g ；t h e a n t st r a v e li nt h eg r a p hs ot og e n e r a t eat o p o l o g i c a lo r d e ro fa l lt a s k s t h ea l g o r i t h m c o n s i s t so ft w ot y p eo p t i m i z a t i o n si n c l u d i n gt h eo p t i m i z a t i o no ft a s k so r d e ra n dt h e o p t i m i z a t i o no ft h es t r a t e g yo fa s s i g n i n g t h ep r o c e s s o r s t h e r e f o r et h e a l g o r i t h m p r o v i d e st w op r o b a b i l i t yf o r m u l a sa n dt w ot y p e so f p h e r o m o n e s t h i sa l g o r i t h mc a nn o t o n l ye n s u r et h et a s k sw h i c hh a v et h ee a r l i e s td e a d l i n et oh a v et h eh i 鲈e s tp r i o r i t yo f s c h e d u l i n g ，b u tc a na v o i dt h el o c a lo p t i m i z a t i o nb yu s i n gc h o o s i n gp r o b a b i l i t y t h ee x p e r i m e n tr e s u l t so ft h et h r e ea l g o r i t h m sa b o v ei l l u m i n a t et h a to u ra l g o r i t h m s c a ng e tb e t t e rs c h e d u l i n gs t r a t e g yt h a no t h e ra l g o r i t h m si ns h o r t e rt i m e f u r t h e r m o r e ， o r ra l g o r i t h m sa l s oh a v eb e t t e rr o b u s t n e s sa n df l e x i b i l i t y k e y w o r d ：a c o ，s c h e d u l i n g ，t a s k a l l o c a t i o nm o d e l ，d a g , d e a d l i n e - r e s t r i c t i o n 于广建：应用蚁群算法解决多处理机调度问题的研究 第一章绪论 本文针对传统或现有的解决任务调度问题的算法的有限性，拓展蚁群算法的 优势，将其运用到任务调度问题中去。本章首先介绍一些相关的研究背景，智能 优化算法的出现，蚁群算法的发展，作为一种进化或仿生算法，它如何运用到各 个领域；作为当今社会发展及科学研究的热点，处理机调度问题的出现、发展以 及一些经典算法与应用。基于这些背景知识的介绍，本章给出了本文的主要工作， 即利用蚁群优化算法解决调度问题。本章的最后列出了本文的组织结构。 1 1 研究背景 自然界的许多自适应优化现象不断给人类以隐喻：生物体和自然生态系统可 以通过自身的演化就使许多在人类看来高度复杂的优化问题得到令人满意的解 决，这种能力让最好的计算机程序也相形见拙。上世纪5 0 年代中期创立的仿生学 使计算机科学家们不断地从生物系统中获得灵感，并通过模仿自然世界的内在机 制，去获取解决复杂计算问题的新思路，提出了许多用于解决复杂优化问题的新 方法，如遗传算法( g a ) 、进化规则法( e p ) 、进化策略法( e s ) 等。意大利学者m d o r i g o 于1 9 9 1 年在他的博士论文中首次系统地提出了蚁群算法1 1 1 ( a n tc o l o n y o p t i m i z 蒯o na l g o r i t h m , a c o ) ，它是受自然界中的蚂蚁行为的启发而产生的一种新 型的模拟进化算法。在该算法中，可行解经过多次迭代后，最终将以最大的概率 逼近问题的最优解。 蚁群算法是一种与经典的数学规划原理截然不同的、试图通过模拟自然生态 机制来求解复杂优化问题的新型智能优化方法。蚁群优化算法的出现孕育了许多 新的计算机技术和解决问题的方法，特别是，它大大地丰富了最优化技术，也为 那些用传统的最优化技术难以处理的组合优化问题提供了切实可行的解决方案。 众所周知，在计算机科学、工程学和管理科学等学科以及许多实际应用领域 都不断涌现出许多复杂的组合优化问题，它们都难以在现有的技术条件下，在比 较合理的有限时间内采用经典最优化方法( 如数学规划) 得到解决，这类问题大 多数属于n p - h a r d 问题。所以，人们退而次之，试图采用各种启发式方法，以便在 2 扬州大学硕士学位论文 合理的时间范围内找到满意的解，蚁群优化算法成为解决此类问题的有力工具。 蚁群优化算法最初被用于解决旅行商问题。自从在著名的旅行商问题 ( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 1 2 ，3 上取得成效以来，己陆续渗透到其它问题领域 中，如：图着色问题【4 】、大规模集成电路设计i s 、通讯网络中的路由问题以及负载 平衡问题e l 6 1 、车辆调度问题【l 8 1 等等。另外，蚂蚁同心协力进行搬运食物，是我 们见得最多的蚂蚁行为，有人以此为蓝本设计出几个机器人共同推盒子的算法。 如美国阿尔伯塔大学设计出几个机器人共同推盒子的实验。又如美国 m c i w o r l d - c o m 公司一直研究人工蚂蚁，并用于管理公司的电话网，对用户记账收 费等工作。另外，还设计“人工蚂蚁”用于因特网的路由管理。国内也有研究者 用蚁群算法求解全国1 4 4 个城市的最短回路问题，求得的解同其它方法求到的解 一样精确，这说明蚂蚁算法不但是求解组合优化问题的可行方法，而且是一种很 有竞争力的算法。在电力系统中，蚁群算法用于求解经济负荷分配问题【9 】，输电网 络扩展规划f 1 0 1 以及热机组短期发电计划【1 1 1 等问题。总之，蚁群算法在解决实际问 题中得到了非常广泛的应用。 1 2 课题的引出 并行化、网络化、智能化是当今计算机发展的主要趋势，而并行分布式计算 是这些发展的主要的挑战性问题之一，也是当前计算机科学的热点之一。目前并 行分布式计算面临大量困难的课题，如：并行算法的设计、任务的划分、通信的 协调和同步、任务的调度。在这些阀题中，任务的调度是一个重要的问题。如果 这个问题得不到解决，则有可能导致分布计算效率低下。因此，调度问题是分布 计算的瓶颈问题之一。 分布式系统中的任务调度问题属于组合优化问题，它通常是由目标函数和约 束条件两部分构成。组合优化的对象是解空间中的离散状态。我们将组合优化问 题中满足所有约束条件的解空间s 称为可行域，可行域中的解称为可行解，将可 行域中使目标函数最小的解称为最优解。对于最大化问题，可将目标函数转化为 最小化问题求解。当s 为离散集合构成的解空间时，其研究对象可视为是在有限 集合上定义的函数在各种条件下的极值问题。从理论上来说，这类问题若有解， 于广建：应用蚁群算法解决多处理机调度问题的研究 3 总是可以用枚举的方法找到，这意味着以枚举为基础发展起来的一些常规优化算 法一分枝定界法、割平面法和动态规划法等【1 2 1 具有普遍适用性。但实际上，这 些方法一般要有较严格的数学模型。但当模型复杂的时候，如变量的维数多、约 束方程数多、非线性强等，或模型结构复杂，不能使用显式的方程来表达时，这 些方法往往不能进行有效求解，或者求解的时间过长。这些方法的计算时间一般 为输入数据量的指数函数，计算时间会迅速增加到现代计算工具难以承受的地步； 或者会出现求解的效果差的现象，如陷入局部极值、初始值直接影响寻优的结果 等【1 3 1 。 处理机调度问题的编码复杂且多样化、解的空间巨大、存在约束条件的限制、 必须考虑解的可行性。此外，处理机调度问题对应的优化超曲面也要复杂得多， 存在多个分布无规则甚至彼此相邻的极小点，对算法的优化造成极大困难。这些 种种因素决定了处理机调度问题属于复杂优化问题，是n p 完全问题。因此，寻求 一种在有限时间内求得可行解的优化算法是实时进行处理机调度的需要。 蚁群算法作为一种基于种群寻优的启发式搜索算法，已经在求解旅行商问 题、指派问题上取得了一系列较好的实验结果。而且一些研究结果已经显示出蚁 群算法在求解复杂优化问题，特别是离散优化问题方面的一些优越性，证明它是 一种很有发展前景的优化方法。 蚁群算法是模拟蚁群觅食行为而提出来的。觅食行为是蚁群一个重要而有趣 的行为。据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可 见提示下找出从蚁穴到食物源的最短路径，并且能随环境的变化而变化适应性地 搜索新的路径，产生新的选择。蚁群的这种觅食行为与组合优化问题有很大的相 似性，见下表。 表1 1 蚂蚁的觅食行为与组合优化问题的相似性 蚂蚁觅食 组合优化问题 蚂蚁走过的路径 解 最短路径 最优解 信息素的数量各状态的吸引度 信息素更新状态更新 路径长度 目标函数 4 扬州大学硕士学位论文 而处理机调度问题属于组合最优化问题，这就为使用蚁群算法求解处理机调 度问题提供了可行性。 1 3 论文的主要工作 蚁群优化算法属于随机搜索算法，蚁群在搜索食物源的过程中所体现出的寻 优能力可以解决一些离散系统优化中的复杂问题。蚂蚁的觅食行为与组合优化问 题的相似性，为使用蚁群算法求解处理机调度问题提供了可行性。 本文的主要工作是研究蚁群算法与处理机调度问题以及如何将蚁群优化算法 应用于处理机调度问题中去。其中论文的主要工作有： 1 提出一种可以求解处理机调度问题的蚁群算法 研究如何将蚁群优化算法应用于求解处理机调度问题，必须深入了解蚁群算 法与处理机调度问题，将蚁群算法中的各个要素与处理机调度问题中的各要素结 合起来。首先，必须为处理机调度问题进行形式化描述，给出准确的数学定义， 并建立数学模型。而这必须先为处理机调度问题给出准确的定义。 在分布式系统中，一个程序可以看成是一个任务集，这些任务可以并行或串 行地执行，任务之间有一定的优先次序约束关系。调度问题的目标是在满足一定 的性能指标和优先约束关系的前提下，将可并行的任务按适当的分配策略确定一 种分派和执行顺序，合理分配到各处理机上有序执行，以达到减少总的执行时间 的目的。 由此，可以将处理机调度问题用图论中的有向无环图( d i r e c t e da c y c l i cg r a p h , d a g ) 来表示，用结点表示任务，边表示任务之间的优先约束关系。在我们的算法 中，我们从d a g 图出发，对调度问题用a o e 图来表示。 有了a o e 图来表示一个任务系统，a o e 图的边与点可以很好地表示任务集中 的任务及其关系，而且为建模与编程提供了了方便。在结合了基于图论的调度问 题的大量研究【1 _ 7 】表明，a o e 图的关键路径的调度长度在很大程度上决定了调度 总的执行时间。可以这么说，它是最后调度长度的一种理想情况。 我们从这点出发，定义了任务系统中各个任务的最早开始时间( e a r l i e s ts t a r t t u n e ，e s d 、最迟开始时间( l a t e s ts t a r tt u n e ，l s t ) 来表示调度过程中各个任务的紧 于广建：应用蚁群算法解决多处理机调度问题的研究5 迫程度。在此基础上，文章考虑这样一个理想情况：一个任务系统上的玎任务平 均地分配到所个处理机上，处理机上没有空闲，即每个处理机上的任务量相同而 且没有空闲，此时，每个处理机完成调度时间相同并且这个时间就是一个理想调 度时间瓦。 我们从此理想调度时间7 k 出发，定义两种概率选择公式：当某处理机上任务 总的调度时问远未接近时，概率公式主要由e s t 、l s t 构成；否则，在概率 公式中加入一种约束机制，使得任务尽可能平均被分配到各个处理机上，从而减 少总的执行时间的目的。 我们求解处理机调度问题的蚁群算法的基本思想为：将 个任务调度到肌个 处理机上，使用r n 只蚂蚁代表脚个处理机，每一只蚂蚁依次按一定的概率给一个 处理机选取适当的任务。一次迭代以后，所有蚂蚁所代表的处理机的任务序列就 形成了一个初始解。经过信息素的更新，由于信息素的正反馈作用，在多次迭代 以后，会逐步趋向最优解。 我们将蚁群算法中的概率公式和信息素等因素与处理机调度问题中各要素结 合起来，分析、建立求解处理机调度问题的蚁群算法，取得较好的调度策略。相 关实验证明，该算法可比传统算法取得有更好运行效率的调度策略。 2 提出了一种适合蚁群算法的任务分配模型 d a g 图等任务模型在一定的程度上不适合蚁群算法的求解。因此，我们提出 了一种适合处理机调度问题的任务分配模型( t a s k - a l l o c a t i o nm o d e l ，t a m ) 和在此 模型上的蚁群算法。该模型结合处理机调度问题的特点，具有很好的可扩充性和 灵活性。它的基本思想就是将任务和蚂蚁按照一定的策略放置在网格上，使用蚂 蚁代表处理机在网格上移动去响应这些任务。在t a m 的基础上，我们设计了基 于t a m 的求解处理机调度的蚁群算法。相关的实验表明，基于t a m 的蚁群算法 在解决处理机调度问题上具有很好的性能。 3 提出一种求解调度闯题的混合蚁群算法 蚁群算法有并行、鲁棒性高、易于其他方法结合的优点，而且众多的研究已 经证明了蚁群算法具有很强的发现较好解的能力。虽然蚁群算法有如上优点，但 它毕竟是一种新兴的算法，还存在一些缺陷，如收敛速度慢、计算时间长；易于 6 扬州大学硕士学位论文 过早的陷入局部最优，会出现停滞现象( s t a g n a t i o n b e h a v i o r ) ，即搜索进行到一定程 度后，所有个体所发现的解完全一致，不利于对解的空间进一步搜索，以发现更 好的解。 在最优化理论研究领域中，最值得一提的是w o l p e r t 和m a c r e a d y 于1 9 9 7 年在 m e et r a n s a c t i o n so i le v o l u t i o n a r yc o m p u t a t i o n ) ) 上发表了题为“n of r e el u n c h t h e o r e m sf o ro p t i m i z a t i o n ”的论文，提出并严格论证了所谓的无免费午餐定理 1 9 - 2 0 。 该定理的主要思想可以描述为：假定有a ，b 两种任意不同的优化算法，对于 所有的问题集，它们的平均优化性能是相同的( 性能可采用多种方法度量，如最优 解、收敛速率等) 。 根据n f l 定理可以得出这样的结论：没有一种算法对任何问题都是最优的。 不同的算法都有其不同的应用优势与不足，算法之间存在着互补性。从解决实际 问题角度出发融合不同类型机制的优化算法，充分发挥它们各自的优势，是拓宽 算法适用域和提高算法性能的有效手段，是解决问题的必然发展趋势，n f l 定理 为这种趋势提供了理论支持。l d a v i s 也提出这样一个原则：“h y b r i d i z ew h e r e p o s s i b l e ” 2 t 1 。国内外对于混合优化算法的研究结果也表明，混合算法在结果的鲁 棒性、寻优效率以及找到的最优解明显比单一优化算法要好。鉴于算法混合在提 高优化精度和寻优效率的潜力， 蚁群算法在组合优化问题上取得了极大的成功 2 2 1 。然而由于基本蚁群优化算 法本质上的一些缺陷，这就要求我们寻求更好的新型算法来解决处理机调度问题。 混合优化策略的成功给新型算法的设计以很大的启发，可以利用其他算法的 机制完成优化的任务，又可以利用蚁群优化策略有效地提高混合算法的性能。这 将是开发新型蚁群算法的一个好途径。 遗传算法( g e n e t i ca l g o r i t h m , g a ) 是j h o l l a n d0 9 7 5 ) 受生物进化的启发而提出 的，g a 是基于“适者生存，优胜劣汰”原则的一种高度并行、随机和自适应的优 化算法，它将问题的求解表示成染色体( 个体) 的适者生存过程，通过种群的一代代 不断进化，包括选择，交叉和变异等操作，最终收敛到“最适应环境”的个体， 从而求得问题的最优解或满意解。 于广建：应用蚁群算法解决多处理机调度问题的研究7 我们在蚁群算法中加入交叉，变异等遗传算子来解决基本蚁群算法的收敛速 度慢、易于过早的陷入局部最优等缺陷。我们提出的基于t a m 的混合蚁群算法很 好地发挥了蚁群算法与遗传算法的优点，既保证了较高的搜索效率，又保证了解 的全局最优性，在解决处理机调度问题上具有很好的性能。在t a m 的基础上， 我们还对动态处理机调度算法的设计与实现进行了探讨，为进一步的研究工作奠 定了基础。 4 提出一种求解有时限约束的调度问题的蚁群算法 我们提出一种求解有时限约束的调度问题的蚁群算法( t h ea c of o rd e a d l i n e s c h e d u l i n ga l g o r i t h m ，简称a d sa l g o r i t h m ) 。a d sa l g o r i t h m 首先对任务集所对应 的d a g 图进行了扩展，得到了扩展的d a g 图。根据这种设计，人工蚂蚁在图中 遍历可以得到任务的拓扑序；a d sa l g o r i t h m 包括两种优化，一方面是任务列表的 优化；另一方面是处理机分配策略的优化。由这两种优化衍生出两种概率公式的 设计和两种信息素。算法利用启发式信息保证优先调度截止时间最早的任务，通 过概率选择保证了其他情况的出现，避免出现局部最优解。我们对算法进行了模 拟实验并与e d f 算法进行比较。模拟实验表明该算法比e d f 算法更优，这个蚁群 算法利用启发式信息保证优先调度截止时间最早的任务，通过概率选择保证了解 的多样性，避免出现局部最优解。 1 4 论文组织结构 论文的第一章介绍了论文的研究背景和一些主要工作；第二章和第三章详细 介绍了蚁群优化算法的基本原理、研究现状以及相关应用，并对处理机调度问题 的基本原理、研究现状以及相关应用作了具体的介绍；在第四章我们提出了一种 求解处理机调度问题的蚁群算法。我们结合d a g 图及a o e 图对处理机调度问题 进行了说明，并给出了一些相关定义，阐述了算法的基本思路，最后给出了具体 算法以及相关的实验数据；在第五章中，我们提出了一种结合遗传算子的混合蚁 群算法。我们首先提出了蚂蚁任务分配模型t a m ，详细说明了如何将遗传算子加 入到蚁群算法中，然后给出了算法的基本思路以及具体算法，最后给出了相关的 实验数据；在第六章中我们提出了一种解决实时系统中有时限约束的处理机调度 问题的蚁群算法。我们首先提出了一种扩展的d a g 图，通过蚂蚁在图上寻径的思 8 扬州大学硕士学位论文 路对任务调度问题进行优化，通过对任务序列和处理机分配策略进行双重优化， 提出了两个不同的信息素和概率选择公式。最后与经典的e d f 算法比较，模拟实 验表明我们算法在保证所有任务在截止时间之前完成的前提下，使得m i n m a x t i m e 最优。第七章是文章的总结和展望。在这章中，总结了本文的主要工作和贡献， 并对未来的工作及发展动向作了展望。 于广建：应用蚁群算法解决多处理机调度问题的研究 9 第二章处理机调度问题 本章给出了调度问题的定义和一些基本概念，提出了调度的目标，即如何减 少调度的完成时间，并且详细地介绍了调度问题的分类。然后分别介绍了任务系 统、d a g 图和g a n t t 图等概念，讨论当前调度问题的研究现状。最后详细介绍当 前几种启发式调度算法的基本思想。 2 1 引言 计算机从1 9 4 5 年开始发展到现在，经历了半个多世纪。从1 9 4 5 年到1 9 8 5 年， 计算机系统一直是庞大昂贵的设备。然而，从8 0 年代开始，由于微处理机的性能 迅速增强，新的快速网络不断出现，可移植的高可靠性通信软件的产生促成了一 种新的计算机系统分布式系统。通过高速网络，将许多处理单元连接起来构 成一个计算系统的做法变得可行，并且非常容易。这种系统通常称为分布式系统。 目前，分布式系统己成为计算机领域中的研究热点。著名学者j h g i l d e r 早在1 9 7 6 年就预言，下一代计算机系统体系结构的关键与核心必然是以分布式结构为主l 刀j 。 在一个分布式系统环境中，大部分结点在大部分时间内都处于低利用率状态。 加州大学b e r k e l e yn o w 研究小组的研究结果表明：即使在每天下午最繁忙的时 候，平均也有近6 0 的结点处于空闲可利用状态。分布式系统中这些闲置结点， 如果不加以合理的利用的话，其c p u 等计算资源就白自的浪费了。而实际上在一 个局域网或高速网络内，在适当的任务调度机制的控制与管理下，可以充分利用 这些闲置结点来执行大规模并行计算，充分利用系统资源。 另外在分布式系统中，很可能出现负载不平衡的现象。当一些处理机处于重 载时，另一些处理机却处于轻载或闲置状态，这种负载的不平衡将直接影响分布 式系统的整体性能。这就有必要在分布式系统中，按任务的静态分配和动态调度 要求做到负载平衡，以提高系统性能。 在论及任务调度的必要性时，r i c h a r df f r e u n d 等人列举过一个假设具有多层 1 0 扬州大学硕士学位论文 并发度计算需求的计算实例剀经计算分析表明“该程序对于普通串行机需要运行 1 0 0 个时间单位，对于向量机需要5 0 个时间单位，而采用由5 种机器构成的分布 式系统，计算过程仅需5 个时间单位。显然，后者所付出的代价是：必须进行适当 的任务分解、分配和调度。” 可见，任务调度策略是影响分布式系统性能的关键问题之一，为了最大限度 的提高系统的资源利用率和减少任务的平均响应时间，必须采取有效的任务调度 策略，合理地分配子任务到各个工作结点机上，保证总任务在最短的时间内完成。 分布式系统的求解过程大体分为四个步骤： 1 任务分解是指把一个大任务划分为可并行执行的相关任务的过程； 2 任务调度是指将这些子任务分配到各个并行处理机上，并安排处理机上任 务的执行次序的过程； 3 并行运算是指这些任务在被分配的处理机上进行并行运算； 4 解的合成是指将任务的运行结果合成为整个大任务的运行结果。 其中任务调度这一步骤对发挥系统的并行计算能力、提高系统吞吐量具有非 常重要的影响。良好的调度算法可以充分运用系