（計算機軟件與理論專業(yè)論文）分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究.pdf

碩士學(xué)位論文 摘要 任務(wù)分配問題是一類典型的組合優(yōu)化問題。多處理器系統(tǒng)上的最優(yōu)任務(wù)分配的研究 是有效利用系統(tǒng)資源處理實際問題的熱點課題，這方面的研究結(jié)果在大規(guī)模數(shù)值計算、 l s i 和計算機網(wǎng)絡(luò)技術(shù)等方面都有很好的應(yīng)用背景。在理論方面，由于任務(wù)分配問題是 被公認的n p 難問題，所以如何構(gòu)造有效的啟發(fā)式算法或近似算法是目前研究的熱點領(lǐng) 域。 蟻群優(yōu)化算法是受自然界中的螞蟻覓食行為啟發(fā)而提出的一種新穎的仿生進化算 法，適用于求解復(fù)雜組合優(yōu)化問題。目前，蟻群優(yōu)化算法己成功應(yīng)用于求解旅行商問題、 二次分配問題，取得了很好的實驗效果。受其影響，國內(nèi)外許多學(xué)者對其進行了大量的 研究工作，將其推廣到了諸多優(yōu)化領(lǐng)域，并已經(jīng)取得了相當豐富的研究成果。 雖然蟻群優(yōu)化算法的應(yīng)用范圍幾乎涉及到各個優(yōu)化領(lǐng)域，但是還存在很多不足。比 如：對于蟻群優(yōu)化算法求解分布式系統(tǒng)中的任務(wù)分配問題的研究大都是在對該問題試驗 條件或約束條件進行簡化的前提下進行的。 本文將蟻群優(yōu)化算法應(yīng)用于求解約束條件更復(fù)雜的任務(wù)分配問題：一個任務(wù)只能分 配給一個處理機處理，而一個處理機可以處理多個任務(wù)，其中每個處理機都有固定成本 和能力限制。將該任務(wù)分配問題表示成完全二部圖，通過螞蟻在完全二部圖上搜索較優(yōu) 路徑來尋求該問題的較優(yōu)解。選擇不同規(guī)模的幾組數(shù)據(jù)進行實驗，對每一組數(shù)據(jù)，通過 反復(fù)試測探索了信息素揮發(fā)系數(shù)，信息素啟發(fā)式因子和期望值啟發(fā)式因子的合理設(shè)定， 并將所得的計算結(jié)果與禁忌搜索和隨機方法作比較。結(jié)果表明蟻群優(yōu)化算法對不同規(guī)模 的任務(wù)分配問題都有較優(yōu)的結(jié)果，具有比禁忌搜索算法和隨機方法更優(yōu)的性能。 將另一任務(wù)分配問題抽象為一種新的有別于二部圖的圖形表示形式。針對蟻群優(yōu)化 算法易陷入局部最優(yōu)的不足，提出了一種求解任務(wù)分配問題的混合算法，該算法將簡單 禁忌搜索算法嵌入蟻群優(yōu)化算法，利用禁忌搜索算法較強的局部搜索能力，提高了蟻群 優(yōu)化算法的優(yōu)化能力，改善了任務(wù)分配問題解的質(zhì)量。仿真實驗表明混合算法的性能優(yōu) 于基本蟻群算法。 最后，對本文的研究工作進行了總結(jié)，并指出了蟻群優(yōu)化算法在該領(lǐng)域進一步還要 研究的問題。 關(guān)鍵詞：蟻群優(yōu)化算法：任務(wù)分配問題：分布式系統(tǒng)；組合優(yōu)化 分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究 a b s t r a c t 1 kt a s ka l l o a n i p r o b l e mi sat ) ，p i c a l0 0 m b i n a t o r i a lo p t i m i z a t i p r o b l e m n e 他s e a r c h 蜘tt h eo p t i m a lt 弱ka l l o c a t i o no n 咖n i - p r o c c s s o rs y s t e mi sah o t s p o tp r o b l e m0 f m a l 【i n gu s e0 fs y s t e m 北刪m st 0s o l v cp n c t i c a lp r o b l e me f f e c t i v e l y ht h e o r y ，t h et a s k a l l o c a t i o np r o b l e mi sar e c 0 印i z e dn p - h a r dp b l e m ，h o wt 0c o n s t m c te 矗b c t i v eh e u r i s t i c 舛a p p r o x i m a t ea l g o r i t h mi sa ni m p o n a n td o m a i no fr 骼e 撒h u n t i ln o w i n s p 訛db yf o r a g i n gb e h a v i o r0 fa n t si nt h en a t l l r c ，t h e 蛆tc o l o n y0 p t 缸血a t i o na 1 9 0 r i t l l m w 弱p m p o s e d 笛an o v e lb i o n i cc v o l u t i a 巧a 1 9 0 r i t h mf o r l v i n gc 0 m p l i c a t e dc 0 恤b i n a t o r i a l 0 p t i m i z a t i o np r o b l e m s ，s 蛐c h 弱t h et r a v c l i l l g 鼢l e s m a np r o b l e m ，t h eq u 舢i ca 鵑i 掣衄e n t p r o b l e m a tp r e s e n t ，n 坨他a r c hd b o u t 鋤t 。0 l o n y0 p t i m i z a t i o na l g o r i t h mh 雒a h e a d y a r o u d a n e n t i o n 丘o mm o r cs c h o l a 璐鋤de x p c n s 孕a d u a l l y t h e yh a v em a d ea1 0 t o fr c s e a r c h 屯 甑t d e di tt 0m 鋤yo p t i i l l i z a t i d o m a i n sa n da c q u 砌c o n s i d e 瑚l b l ya b 蚰d 鋤tr c s e 砌 a c h ic _ v 鋤e n t s 砧t h o u g ha p p l i c a t i o ns c o p eo f t h e 鋤tc 0 l o n y0 p t i m 謝i o na l g o r i 岫i sa h o s tn l a t e dt 0 c v e 巧叩t i m i z a t i o nd o m a i n ，t h e 托s t me x i s t sd e f i c i e 玳i y f 0 fc x 鋤p l c ，t h cr c s e 種c ho n l v i n g t h et a s ka l l o c a t i p “) b l e mi nd i s t r i b u t e ds y s t e mb yt h e 鋤tc o l o n y0 p t i m 婦i a 1 9 0 r i t h mi s 訓(xùn)e do u tu n d e rt h ep r c l n i o fs i l n p l i f i e dc x p c 血e n t 咖d i t i 0 rc o n s 婦i n e dc o n d i t i ht h i st h e s i s ，t h e 勰tc o l 蚰yo p t i m i z a t i 蚰a 1 9 0 r i t h mi sa p p h e dt 09 0 l v ct h et a s ka l l o c a t i p r o b l e mw i t hm o 陀c o m p l i c a t e dc 0 璐t r a i n e d 湖d i t i o n w 址c he a c ht 淞kc a nb e 弱s i 乎屺dt 0 o n l y e 畔s s o b u te a c hp r o c e s s o rw i t hc a p i t yc 0 璐t r a i n ta n d f i x e dc o s t 啪e c i l t ca 嘰m t 財o ft a s k s n ct a s ka l l o t i 衄p r o b l e mi s 既p r c s s c d 弱ac o m p l e t eb i p a n i t c 孕a p h 輒吶p t i m a l l u t i o 璐a 他0 b t a j n c db y 觚t sw l l i c h 疵h 跚b - o p t i m a lr t 鶴i nt h e 卿h s 刳c m l 印u p s0 fd a 婦w i n ld i 虢r c n ts c a l e sa r ec h o s et 0m a l 【ec x p e r i m e n t s ，f o fc v e r ) rg r o u po f d a t a 0 p t i m u m n f i g 盯a t i o no fc o n c c m e dp 猢e t i 哪，a 他s p e c l l l a t e db y t r i a l t e s tr c p c a t e d l y f i l n h 鋤0 r e t h er e s u l t so fa n tc o l yo p t i m j z a t j 伽a l g o r i 岫i s 啪p a 托dt ot a b us e 砌柚d 咖1 d 伽m e t h o d n ee x p c r i m e n t a lr c s u l t sm 姐i f c s tt h a tt h e 柚t l o n yo p t i i n i z a t i a 1 9 0 r i t h m p c r f b 咖sb e t t e ru n d c rd i 骶r e n tp r o b l e ms c a l 鼯鋤dh 弱g r c a ta d v a n t a g e s0 v e r 組b us e 砌卸d m d o mm e t h o di np e r f 0 r m a n c c a n o t h e rt 鴿ka l l 0 c a t i o np r o b l e mi st u m e di n t 0a 玳1 w 粵a p h 他p 托n t a t i o nw l l i c hi s d i 疵r c n t 舶mt h eb i p a n i t c 鯽h a j n l 她a t 哪i l yp l u n g i n gi n t 0l o c a l0 p t i m i z a t i o ft h e 枷 l 蚰y0 p t 血i z a t i 徹a 1 9 0 r i 岫，ah y b r i da l g o r i t h mw h i c hc o m b i n e d 鋤tc o l o n yo p t i m i z a t i o l l a 1 9 0 f i t l l 1w i t ht a b u a r c hf o rt 私ka l l o c a t i 蛐p f o b l e mi sp r o p c 瞎e d o w i n gt 0t h es t i o n g e r h 斌a 砌la b i l i t yo ft a b u 積h ，t h ep r o p o s e dh y b r i da 1 9 0 r i t h mc 趾e n h 鋤c co p t i m i z a t i 佃 a b i l i t y0 ft h e 趾t 砌咖y0 p t i i n i z a t i 衄a l 酬她a n di m p r o v eq u 批y o fs o l u t i 蚰o ft h ct a s k a l l o c a t i 伽p r o b l 鋤ms i m u l a t i o n 陀s u l t sd e m o n s t r a t et h a t t h eh y b r i da l 鰣t l l mp e 渤皿s s i 印i f i c a n t l yb c n e r t h 鋤a n tc o l o n ya 1 9 0 f i t l l i ni np e r f b m 趾 i i lt h ee n d ，t h e n c l u s i o ni sg i v 觚dt h ef u n h e r 心s e 矧hd i r e c t i i sp o i n t e d 伽t k e yw o r d s ：a mc o l o n yo p t i i n i z a t i o na l g o r i t h m ；佻ka l l o c a t i o np r o b l e m ；d i s t 加u t e ds y s t e m ； c o m b i n 納o r i a lo m i m i z a t i o n m 分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究 插圖索引 圖1 1 分布式系統(tǒng)示意圖3 圖3 1 四類問題的關(guān)系圖。1 5 圖3 2 螞蟻尋找最短路徑示意圖1 6 圖4 1 信息素揮發(fā)系數(shù)與總的花費代價的關(guān)系3 2 圖4 2 參數(shù)設(shè)定界面。3 3 圖4 3 程序運行結(jié)果界面：3 3 圖5 1 混合算法求解任務(wù)分配問題的總體框架3 6 圖5 2 任務(wù)分配問題的圖形表示3 7 圖5 3 混合算法和基本蟻群算法的性能比較4 0 碩士學(xué)位論文 附表索引 表2 1 任務(wù)分配矩陣8 表4 1 啟發(fā)式因子口和盧的不同組合對算法性能的影響。3 2 表4 2 不同算法的計算結(jié)果比較3 4 表5 1 混合算法與基本蟻群算法計算結(jié)果比較。4 0 v 蘭州理工大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨立進行研究所取得的 研究成果。除了文中特別加以標注引用的內(nèi)容外，本論文不包含任何其他個人或 集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體，均 已在文中以明確方式標明。本人完全意識到本聲明的法律后果由本人承擔。 作者簽名：互靈寢 日期：礎(chǔ)年6 月j 鄉(xiāng)日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有 權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和 借閱。本人授權(quán)蘭州理工大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù) 庫進行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。同 時授權(quán)中國科學(xué)技術(shù)信息研究所將本學(xué)位論文收錄到中國學(xué)位論文全文數(shù)據(jù) 庫，并通過網(wǎng)絡(luò)向社會公眾提供信息服務(wù)。 作者簽名： 導(dǎo)師簽名： 白期：幻。辟歹月房日 日期：諺年二月i 弓日 碩+ 學(xué)位論文 1 1 分布式系統(tǒng)概述 第1 章緒論 分布式系統(tǒng)是二十世紀九十年代以來計算機領(lǐng)域的研究熱點之一。作為網(wǎng)絡(luò)一體化 和并行處理分布化的產(chǎn)物，分布式系統(tǒng)解決了系統(tǒng)透明性及處理機動態(tài)分配等問題，表 現(xiàn)出了強大的生命力。 一個被大家公認的分布式系統(tǒng)的定義是：“分布式系統(tǒng)是一些獨立的計算機的集合， 但在用戶看來卻是一臺計算機一【1 1 。在硬件結(jié)構(gòu)上，盡管所有的分布式系統(tǒng)都是由多個 c p u 構(gòu)成的，但可以用不同的方法將硬件組織起來，形成不同的系統(tǒng)。按照體系結(jié)構(gòu)劃 分，當前典型的分布式系統(tǒng)可分為兩種：共享存儲多處理機與分布存儲多計算機。如果 結(jié)點間通過公用存儲器中的共享變量實現(xiàn)相互通信，就稱為多處理機( m u l t i p r o c c s s o r s ) ； 如果結(jié)點間使用消息傳遞方式來實現(xiàn)相互通信，就稱為多計算機( m u l t i c o m p u t e 喲【2 。 共享存儲多處理機屬于緊密耦合的分布式系統(tǒng)，采用共享主存通信。一個典型的共 享存儲多處理機系統(tǒng)由m 個存儲模塊、p 個處理器和d 個i o 通道組成，( 朋，p ，d ) 的數(shù) 目按情況而定。由于處理機與主存之間互連網(wǎng)絡(luò)帶寬有限，所以當處理機數(shù)增多時，訪 問主存的沖突概率會加大，互連網(wǎng)絡(luò)會成為系統(tǒng)性能的瓶頸。但由于是單一地址空間， 所以較易于編程。 分布存儲多計算機屬于松散耦合的分布式系統(tǒng)，它的每個處理單元都是一個獨立性 較強的節(jié)點，系由c p u 、本地存儲器、i o 設(shè)備和消息傳遞通信接口所組成。由于每個 計算節(jié)點的本地存儲器容量較大，所以運算時所需的絕大部分指令和數(shù)據(jù)均可取自本地 存儲器。當不同計算節(jié)點上的進程需要通信時，就可通過接口進行消息交換。在有的松 散耦合的多計算機系統(tǒng)中，其計算節(jié)點本身就是一臺完整的計算機，這樣就演變成了現(xiàn) 代的機群系統(tǒng)。這種松散性耦合結(jié)構(gòu)易于擴展，但多地址空間卻使編程較困難。 分布式系統(tǒng)與集中式系統(tǒng)相比，有其自身的優(yōu)點。分布式系統(tǒng)有較高的性能價格比， 它還可能具有任何價位上的大型機都無法達到的性能。分布式系統(tǒng)的另一個優(yōu)點是它有 更高的可靠性，通過將任務(wù)交由多個機器共同承擔，單個芯片的故障只會讓一臺機器停 下來，而其它的機器將繼續(xù)工作。對于一些關(guān)鍵性應(yīng)用，例如控制核反應(yīng)堆或飛機，使 用分布式系統(tǒng)來達到高可靠性是最主要的考慮因素，并且在負載增加時分布式系統(tǒng)較集 中式系統(tǒng)更容易擴展。 1 2 論文選題的背景和意義 眾所周知，一般情形下( 處理機個數(shù)大于3 ) 的任務(wù)分配問題是n p 難的。人們不 分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究 ” 會盲目地去尋求解決這類問題的最優(yōu)解。但對于具體的分布式系統(tǒng)，在適當假設(shè)條件下， 尋找不一定最優(yōu)但實際可行且效果較滿意的方法，仍是現(xiàn)今十分活躍的研究課題p j 。在 這方面已經(jīng)研究出了許多各具特色的算法，較有代表性的一些算法是：基于圖論的分配 算法、數(shù)學(xué)規(guī)劃方法、啟發(fā)式算法、各種負載共享策略、動態(tài)投標算法以及專家系統(tǒng)方 法等。它們可粗略地分為兩大類：靜態(tài)分配策略和動態(tài)分配策略。前者是在系統(tǒng)運行的 初始時刻，將用戶提交的任務(wù)一次性分配給系統(tǒng)中各處理機，此后直到這些任務(wù)運行完 畢，各處理機上的任務(wù)一般不再變更。其特點是實現(xiàn)簡單，但效果有限。后者是在運行 過程中，將任務(wù)分配給各處理機，并對其上的任務(wù)數(shù)進行動態(tài)調(diào)整，盡可能使系統(tǒng)中各 處理機上的負載達到基本平衡。其主要特點是能充分發(fā)揮各處理機的能力，但實現(xiàn)起來 復(fù)雜程度高。 本節(jié)介紹分布式系統(tǒng)中的幾種任務(wù)分配( t a s ka l l 0 c a t i ) 策略，這些策略的著眼點 就是設(shè)法減少系統(tǒng)中各處理機間的通信開銷和執(zhí)行模塊所需的開銷，以此來提高整個系 統(tǒng)的性能。 處理機間的通信( 簡稱口c ) 開銷是由位于不同處理機上的模塊互相傳遞數(shù)據(jù)所引 起的。因此，m c 是模塊間的通信( 簡稱m c ) 和模塊分配的函數(shù)，這里蹦c 是指每 對模塊間的數(shù)據(jù)傳遞。顯然，如果兩個模塊同駐在一個處理機上，那么，它們就不會引 起口c ( 假定同駐模塊間的通信開銷忽略不計) 。 通常，若干模塊構(gòu)成一個任務(wù)，一個任務(wù)是單一的處理實體。任務(wù)分解和任務(wù)分配 是用于減少口c 的兩個必要步驟。任務(wù)分解的目的是把一個提交的任務(wù)分劃成若干獨立 的、具有最小玎c 的模塊；任務(wù)分配則是指把這些模塊分配給處理機，使得它們由于 i p c 所引起的開銷最小。假定任務(wù)分解已由軟件設(shè)計者在設(shè)計階段完成，提交給系統(tǒng)的 任務(wù)已經(jīng)分解成若干模塊。本節(jié)主要討論如何以最優(yōu)方式將模塊分配給處理機。注意模 塊的個數(shù)通常多于( 甚至遠遠多于) 處理機的個數(shù)，因此，多個模塊可能分配給一個處 理機下面將討論任務(wù)分配環(huán)境、影響系統(tǒng)性能的因素。 1 2 1 任務(wù)分配環(huán)境 一般的分布式系統(tǒng)的示意圖如圖1 1 所示，其中伍，乏，乙) 是一組待處理的模塊， ( 只，只，”、只) 是系統(tǒng)中的筇個處理機，它們經(jīng)由互聯(lián)網(wǎng)互相通信；模塊分配機制s 把坍個 模塊合理地分配給刀個處理機中的某個處理機，通常冊 一。位于不同處理機上的模塊 彼此交換數(shù)據(jù)是通過它們所在的處理機彼此通信來實現(xiàn)的。任何一對模塊的i m c 是由 設(shè)計階段確定的，而且在模塊分配期間是模塊的一個固定特性。由于i m c 的總量將隨 著模塊對的不同而變化，因此，把這些模塊分配給處理機的方式可能影響整個系統(tǒng)的處 理開銷。例如，若兩個模塊互和l 的蹦c 量很大，通信也較頻繁，而且它們又分配在 不同的處理機上，那么，相應(yīng)的口c 開銷就會增大。如果把五和t 分配到同一處理機上， 就可能減少系統(tǒng)的總處理開銷。此外，若兩個模塊的i m c 較少，而且也無優(yōu)先制約關(guān) 2 碩士學(xué)位論文 系，把它們分配給不同的處理機顯然可能加速整個處理過程。 圖1 1 分布式系統(tǒng)示意圖 1 2 2 影響系統(tǒng)性能的因素 均衡負載分配策略是把模塊合理地分配給系統(tǒng)中的所有處理機，使得這些處理機差 不多是均勻負載的。顯然，這種分配策略可最大限度地提高系統(tǒng)的吞吐量。如果只注重 減少口c 而不考慮系統(tǒng)的均衡負載，就可將待處理的模塊全部分配給同一處理機處理。 顯然，這種分配策略可使口c 降至最低，但對同一任務(wù)的處理時間卻成倍地增加了。 不難看出，均衡負載和減少口c 是相互沖突的兩個因素，它們左右著任務(wù)分配策略， 影響著系統(tǒng)的性能。負載平衡可以提高整個系統(tǒng)的吞吐量，因為它試圖將模塊盡可能均 等地分配給處理機。但由于坤c 的開銷又迫使分配策略不得不盡可能把較多的模塊分配 給盡可能少的處理機任務(wù)分配策略就是要設(shè)法平衡這兩個因素，將模塊分配給處理機， 使整個系統(tǒng)的性能提至最高。 1 3 研究現(xiàn)狀 計算機技術(shù)與應(yīng)用的飛速發(fā)展，使得分布式系統(tǒng)的應(yīng)用越來越廣泛【4 j 。但隨著分布 式計算機系統(tǒng)的發(fā)展，分布式計算機領(lǐng)域中出現(xiàn)了很多亟待解決的問題，其中任務(wù)的分 配和調(diào)度是一個關(guān)鍵性的問題。因為當分布式系統(tǒng)中處理器個數(shù)增多時，任務(wù)間的通信 開銷和處理機間等待時間增大，系統(tǒng)效率趨于飽和甚至下降，所以合理的任務(wù)分配策略 是提高分布式系統(tǒng)效率不可缺少的措施任務(wù)的分配將關(guān)系到系統(tǒng)的吞吐量、資源的利 用率等，對于發(fā)揮各處理單元的作用，從整體上提高系統(tǒng)資源的利用率等具有非常重要 的意義。因此在分布式系統(tǒng)中，任務(wù)分配問題一直是重要的研究課題之一 任務(wù)分配問題是被公認的n p 難問題【4 】。任務(wù)分配的目的是減少并行運行任務(wù)間的 通信開銷和等待時間，改善負荷的均衡性，提高實時任務(wù)的響應(yīng)速度和系統(tǒng)效率。目前 基本的任務(wù)分配方法有三類：圖論法1 5 】i q ，數(shù)學(xué)規(guī)劃法【7 l 【8 l 和啟發(fā)式方法【4 1 【9 l 【1 0 l 【1 1 1 圖論 法簡單直觀，適用于任務(wù)數(shù)和處理機數(shù)較小的系統(tǒng)；數(shù)學(xué)規(guī)劃法是用數(shù)學(xué)規(guī)劃的方法求 解任務(wù)、處理機、系統(tǒng)資源間約束關(guān)系對應(yīng)的一組方程式的最優(yōu)解，由于求解的是m 問題，從而失去其工程應(yīng)用價值；只有啟發(fā)式方法實用簡單，它是從系統(tǒng)結(jié)構(gòu)和任務(wù)特 點出發(fā)，運用一些有效的分配原則，使某些代價函數(shù)接近最優(yōu)的任務(wù)分配策略。很多文 章已證明合理的啟發(fā)式方法求得的解雖不是最優(yōu)解，卻是次優(yōu)解，尤其在其它兩類方法 3 分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究 中難以考慮的資源共享、時間鏈約束、通信開銷和延遲、存取i ，o 設(shè)備均可在啟發(fā)式方 法中得以考慮。 1 圖論法 圖論方法中，應(yīng)用于任務(wù)分配最重要的方法是偶圖的匹配算法。將系統(tǒng)描述成一個 偶圖，在這個偶圖中存在兩個集合，分別為任務(wù)集合與結(jié)點集合，并用結(jié)點與任務(wù)問的 邊表示任務(wù)的分配。加入任務(wù)間通信費用的考慮，文獻【1 2 】提出了相應(yīng)的結(jié)點匹配算法。 在文獻【1 3 】中，使用圖中的結(jié)點來表示任務(wù)。每兩個任務(wù)間的通信費用預(yù)知，并由 連接這兩個結(jié)點的無向邊的權(quán)重來表示。如果費用為0 則表示這兩個任務(wù)間不存在通信； 而費用為無窮則表示這兩個任務(wù)必須被分配到同一個處理器( 結(jié)點) 。 2 數(shù)學(xué)規(guī)劃法 這種方法的主要思想是把任務(wù)分配問題概括成一種優(yōu)化問題，然后利用數(shù)學(xué)規(guī)劃方 法去解決它【7 】【引。 3 啟發(fā)式方法 文獻【1 3 】指出：有些應(yīng)用由于自身的限制，無法在很重要的時間限度內(nèi)獲得一個最 優(yōu)解。對于這些應(yīng)用，啟發(fā)式方法能夠提供快速而有效的算法。在該方法中，使用很多 假設(shè)以減少任務(wù)分配的計算時間和，這些假設(shè)包括網(wǎng)絡(luò)處理器是同構(gòu)的、完全連接的， 或各任務(wù)間的先后次序可被忽略。在這些假設(shè)條件下，可使用啟發(fā)式模型簇算法，來實 現(xiàn)基于實時與存儲空間限制的任務(wù)分配。 文獻【1 4 】指出：可用圖表示的啟發(fā)式算法可被大致分為：交互式算法與非交互式算 法。非交互式算法利用t f g 的圖論屬性來得到一個最優(yōu)化某一費用函數(shù)的方案。交互 式算法則是生成一個初始的隨機方案，然后逐步優(yōu)化，直到費用函數(shù)值最小。由于這兩 類方案的不同，費用函數(shù)對其得到有效方案的影響也不同。一般的費用標準，如最小化 總體執(zhí)行時間，或最小化最重負載處理器的負載，被這兩類算法共同采用。 另外，其它啟發(fā)式算法也為解決此類問題提供了新的途徑。遺傳算法是一類模擬生 物界自然進化和遺傳過程的隨機搜索和優(yōu)化算法，具有在大問題空間求解近似最優(yōu)解的 能力。正因遺傳算法的強健性和對復(fù)雜問題的求解能力，有人將其應(yīng)用于多處理機系統(tǒng) 的任務(wù)分配與調(diào)度【1 5 1 【1 6 1 。 模擬退火算法是基于m o n t ec a l l o 迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是 基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。文獻【1 7 】【1 8 】應(yīng)用 模擬退火算法求解任務(wù)分配問題。 文獻【1 9 】運用改進的螞蟻算法來求解簡單的任務(wù)分配問題，即一個任務(wù)只能分配給 一臺機器處理，且每臺機器只能處理一個任務(wù)。本文主要研究應(yīng)用蟻群優(yōu)化算法求解分 布式系統(tǒng)上約束條件更復(fù)雜的任務(wù)分配問題，即一個任務(wù)只能分配給一個處理機處理， 而一個處理機可以處理多個任務(wù)，其中每個處理機都有固定成本和能力限制，同時假設(shè) 每項任務(wù)在不同的處理器上完成具有不同的費用，并且不同的處理機存在著通訊開銷。 4 碩士學(xué)位論文 1 4 本文的研究內(nèi)容及結(jié)構(gòu)安排 第一章介紹了分布式系統(tǒng)中的任務(wù)分配問題、選題背景及研究現(xiàn)狀。 第二章介紹了較有代表性的任務(wù)分配算法：基于圖論的分配策略、整數(shù)規(guī)劃方法和 啟發(fā)式算法，并對這三類典型算法進行比較和分析 第三章首先從組合優(yōu)化問題、n p 問題及計算復(fù)雜性分析入手，對近年來被廣泛應(yīng)用 的，具有代表性的仿生進化算法的算法原理、特點、研究現(xiàn)狀等進行了綜述，重點介紹 了蟻群優(yōu)化算法的原理、特點、改進算法以及研究與應(yīng)用現(xiàn)狀。 第四章應(yīng)用蟻群優(yōu)化算法來解決多處理器分布式系統(tǒng)上約束條件更復(fù)雜的任務(wù)分 配問題：一個任務(wù)只能分配給一個處理機處理，而一個處理機可以處理多個任務(wù)，其中 每個處理機都有固定成本和能力限制。仿真結(jié)果表明該算法比禁忌搜索和隨機方法具有 更好的求解能力 在第五章中，為解決蟻群優(yōu)化算法易陷入局部最優(yōu)的不足，提出了一種求解任務(wù)分 配問題的混合算法。該算法將簡單禁忌搜索算法嵌入蟻群優(yōu)化算法，利用禁忌搜索算法 較強的局部搜索能力，提高了蟻群優(yōu)化算法的優(yōu)化能力，改善了任務(wù)分配問題解的質(zhì)量。 仿真實驗表明混合算法的性能優(yōu)于基本蟻群算法。 最后，對本文的研究工作進行了總結(jié)和展望。 5 分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究 第2 章分布式系統(tǒng)中的任務(wù)分配問題 在分布式系統(tǒng)中，任務(wù)分配問題一直是重要的研究課題之一。任務(wù)分配是在分布式 系統(tǒng)環(huán)境中，將給定的一組子任務(wù)，按照系統(tǒng)的當前狀態(tài)，按照一定的執(zhí)行時序分配到 網(wǎng)絡(luò)結(jié)點上，以期獲得較好的系統(tǒng)執(zhí)行性能?，F(xiàn)階段，分布式系統(tǒng)任務(wù)分配問題的求解 算法大致可分為三類：基于圖論的分配策略、整數(shù)規(guī)劃方法和啟發(fā)式算法，下面對這三 類典型算法進行比較和分析。 2 1 基于圖論的分配策略 基于圖論的分配策略的基本思想【3 l 是把待分配的一組模塊作為圖中的節(jié)點集，連接 兩個節(jié)點的有向連線上的權(quán)表示每對模塊之間的i m c 開銷。c 開銷為0 意指相應(yīng)的 兩模塊之間無通信發(fā)生，因此它們在圖中無連線；m c 開銷為意指相應(yīng)的兩模塊間通 信量很大，必須分配給同一處理機。可見，圖中節(jié)點間連線上的權(quán)表示分配在不同處理 機上每對模塊之間的通信開銷。假定任何一對同駐模塊的口c 開銷為0 。若把系統(tǒng)的總 開銷定義為系統(tǒng)的處理開銷和口c 開銷之和，那么，這種分配策略的目的就是實現(xiàn)最小 的總開銷。處理開銷和口c 開銷都是模塊到處理機分配的函數(shù)，為了表示模塊到處理機 的分配，可定義下面的分配矩陣x ：而j 一1 表示模塊1 分配到處理機最處理：毛上，0 表 示模塊正未被處理機只處理。而處理開銷則由下面的q 矩陣給出： q 一饑工 ， f 一1 ，2 ，”，肺，七一1 ，2 ，“，刀 其中，吼。表示模塊正在處理機最上的處理開銷，它是該模塊處理要求的度量。 q 。一隱含模塊互不可能在處理機罡上執(zhí)行。 令c ；，表示模塊互和疋之間的i m c 開銷。于是處理給定任務(wù)的總開銷z 可表示為x 的函數(shù)： r1 r 伍) 。；軍卜j + 薈薈q ，t 上工， 佇，、 其中，第一項表示每個模塊在它所分配的處理機上的處理開銷；第二項則表示非同 駐模塊間的口c 開銷。最小開銷分配則是在這種圖上執(zhí)行最小分割算法來獲得。 這種分配策略的最大優(yōu)點是它的簡明性。但它也存在一些限制和不足：第一，所用 的最小分割算法是一種基本的最小分割算法，它只能用于實現(xiàn)兩個或三個處理機間的最 小開銷分配。若將它擴充成處理任意個數(shù)的處理機，則需要萬維( 刀個處理機分配) 的 最小分配算法，該算法是極其復(fù)雜的。這就限制了這種任務(wù)分配策略的應(yīng)用范圍；第二， 這種方法既未提供有關(guān)存儲空間或處理時間等方面的限制手段，也未提供負載均衡方面 的機制；第三，它沒有能力去觀察排隊延遲效果。當一個以上的模塊分配給同一個處理 機時，就不可避免地會出現(xiàn)延遲。因此，基于圖論的任務(wù)分配策略不是任務(wù)分配問題的 6 最好解決辦法。 2 2 整數(shù)規(guī)劃方法 該方法的基本思想【3 l 是仍用前面定義的q 矩陣來表示執(zhí)行開銷，但用一個聊肌矩 陣y 來定義m c ： y 一饑，j 1 墨fs 歷1 5 j s 小& 屹j 為互向乃傳送的數(shù)據(jù)量j 同時引進一個尼 的距離矩陣d ： d a 留u1 1s fs 行& 1 5 _ s 刀d “為只與弓問的距離 模塊分配函數(shù)用冊 矩陣z 來定義： x k ，1 1s fs 用& 1 墨j s 刀毛，一1 表示五分畔上 該分配方法的目標函數(shù)定義為： r b ) 2 ；沖以+ 墨荔v ，j 其中，常數(shù)w 用來調(diào)節(jié)通信開銷和執(zhí)行開銷間的差異。 此時，任務(wù)分配即要找使r 最小的那個x 的指派。因此，這種方法實質(zhì)是帶有某些 限制條件的隱式枚舉算法，其時間復(fù)雜度隨問題規(guī)模成指數(shù)增長。這顯然限制了算法的 實用性。這種方法的優(yōu)點是很容易加入適當?shù)南拗茥l件，以滿足實際環(huán)境的需要。 m a e t a l 提出了一種分支界限法【2 0 l ，它用一棵搜索樹來表示分配問題，每個葉子結(jié)點 處表示一個分配方案。除了存貯限制和實時限制外，它還引入了以下限制條件： 蝴阮 ：= 篙不骱一 ， 冊刪模螄黼唯：二篙礁傭躺咄覡 以及允許一個任務(wù)( 模塊) 的多份拷貝，以提高系統(tǒng)的可靠性。 該算法在每個分支處檢查p ，e 關(guān)系和存貯及實時限制條件，若不滿足，則剪枝： 若滿足，則檢查這次分配后的部分開銷是否超過已得到的最小全部開銷，若超過，則剪 枝；否則就分配，并選擇下一擴充結(jié)點。若全部可能的路徑都被探查完，或規(guī)定的執(zhí)行 時間己到，則算法結(jié)束。 該算法的空間復(fù)雜度較小，只需記錄當前最小開銷的分配方案和此開銷即可，約為 d b 廳) 。但時間復(fù)雜度仍可能是指數(shù)級的，而且沒有保護模塊優(yōu)先規(guī)定的機制和實施負 載平衡的機制。 7 分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究 2 3 基于遺傳算法和模擬退火算法的任務(wù)分配策略 ( 1 ) 算法說明 設(shè)有一個由露個處理機p 一切。，p ：，一 p 。 組成( 可以是不同的處理機) 的分布式系 統(tǒng)【3 l ，需要執(zhí)行川個任務(wù)r i 。，f ：，一、f ) ，一般刀 朋。為了便于分析問題，可以建立下 述五元組： 羅一仃， ，q ，c ，x ) 其中，z 一量。，f ：，“ o 是任務(wù)的集合；“ 是r 上的任務(wù)優(yōu)先關(guān)系， f ，( 1s fs 肌，1s j s 朋) 表示任務(wù)f j 必須在任務(wù)f ，執(zhí)行之前完成；q 是一個冊萬矩陣， 其元素q u 表示任務(wù)在處理機p ，上的執(zhí)行時間( 假設(shè)每個任務(wù)的運行時間已知) ；c 是 一個歷刀矩陣，c ；，表示任務(wù) 與f ；之間的通信開銷；z 是一個加刀的任務(wù)分配矩陣， 其中t 。j = 1 表示分配到處理機p ，上執(zhí)行，否則毛j 一0 。 為了實現(xiàn)選擇，還必須設(shè)計一個目標函數(shù)c o s f 。c o s f 是一個包含多種因素折衷的函 數(shù)，它應(yīng)能體現(xiàn)出設(shè)計者對系統(tǒng)的性能要求，例如可以采取下述方法： c 0 酣。善薈【吼上飛上+ 曠薈薈q ，強上呵，j ( 2 3 ) 其中常數(shù)w 用來調(diào)節(jié)通信開銷和執(zhí)行開銷之間的差異。在實際設(shè)計過程中，還可以 選取不同的w 的值或其它目標函數(shù)。 ( 2 ) 算法描述及簡單分析 第一階段初始化 隨機產(chǎn)生一個任務(wù)分配矩陣集：先設(shè)定一個全零的任務(wù)分配矩陣x ，然后在x 中的每一行由系統(tǒng)隨機選定一個元素為1 。如表2 1 所示，在3 個處理機和7 個任務(wù)的 情況下，f 。、f ：、被分配給p l ；、毛被分配給p ：；氣、f ，被分配給p ，。用同樣的方 法可產(chǎn)生多個任務(wù)分配矩陣 表2 1 任務(wù)分配矩陣 任務(wù)處理機 p lp 2p 3 f l 1o0 f 2 1oo f 3 1o0 01o 毛 o10 氣 0o1 f 7 0o 1 描述和確定初始任務(wù)分配集：對一個給定的任務(wù)分配方案，可用一個數(shù)據(jù)結(jié)構(gòu) 黝一p ，r 【1 j l 】 來描述： 8 碩士學(xué)位論文 其中s 是一個l o g ：刀1 腳位的二進制串，每位1 0 9 ：刀1 為一節(jié)，從左到右第f 節(jié)表示 任務(wù)i 所在的處理機情況，這樣表2 1 中的任務(wù)分配矩陣可以表示為s = 0 00 0 0 00 10 11 0 1 0 。因為有3 個處理機，所以兩位為一節(jié)，0 0 ，0 1 ，1 0 分別表示任務(wù)被分配到磯，p ：， 以上執(zhí)行，1 1 是無效編碼。 r 是一個萬鏈表數(shù)組，r p 】表示處理機阢上的任務(wù)執(zhí)行順序，仍以表2 1 為例，若 任務(wù)之間滿足“ 一優(yōu)先關(guān)系 ) ，則可確定三種任務(wù)分配方案： p 。上執(zhí)行順序為f 。，f 2 ；p 2 上執(zhí)行順序為，如；p 3 上執(zhí)行順序為f 6 ，f 7 尺表示 為： o r 【1 】：1 2 3 斛2 】：4 5 塒3 】：6 7 尺【1 】：1 3 2 尺【2 】：4 5 塒3 】：6 7 尺【1 】：3 1 2 研2 】：4 5r 【3 】：6 7 由于分配到同一處理機上的任務(wù)之間有多種排列，所以從一個任務(wù)分配矩陣可以產(chǎn) 生多種方案。在這些方案中，有一些是違背“ 一優(yōu)先關(guān)系的，稱為無效分配方案，否 則，稱為有效分配方案。上面列出的就是三種有效分配方案。從每一個任務(wù)分配矩陣所 產(chǎn)生的分配方案中各選取一種或幾種有效分配方案，便形成初始任務(wù)分配方案集。 設(shè)置模擬退火算法中的初始溫度f 研矽。和收斂率口：溫度紉慨+ 1 一口紉，張逐步 降低，這里0 口 ，口以成立的可能性也越大，越容易被接受。反之同理。 2 4 螞蟻算法 任務(wù)分配問題【1 9 l 最簡單的一種情形可描述為，有以個任務(wù)需要分配給廳個機器去完 成，每個任務(wù)只能分配給1 臺機器處理，且每臺機器只能處理1 個任務(wù)，不同的分配花 費不同的代價。任務(wù)分配問題要求找到1 種分配方案所花費的代價最小。 若第f 臺機器完成第j 項任務(wù)的代價g 之o ，則可構(gòu)成代價矩陣q 期。求解如何分 配機器，才能在完成總?cè)蝿?wù)的條件下，使總的花費代價最小。 設(shè) ；t，-i：!：l：!：j!：!；：!f；li：l；!：!；j!：；：!；l；燃z，-，。，2，t q o1 l o 表示不由第f 臺機器完成第f 項任務(wù) q 。 一”一” 、_ 7 則分配問題是求解任務(wù)分配陣k 約束條件為 善吩。1 再嘞1 1 嘞- 嘞 | a1 2 ，廳 i ，1 ，2 ，刀 f ，i j 一1 2 ，刀 ( 2 5 ) ( 2 6 ) 在滿足上述約束條件下，使目標函數(shù)c 響。善薈q 嘞成立，q c 腳，嘞尺一期。 求解任務(wù)分配問題的螞蟻算法的步驟如下：。 ( 1 ) 令c 一1 ，s 一1 七一1 ( 從第1 只螞蟻開始) ，首先計算第七臺機器完成廳項任務(wù)的 概率，i ( j 一1 醌，刀) ，選出其中最大的概率，記為i ，即由第七臺機器來完成第 1 0 碩士學(xué)位論文 j 眥項任務(wù)。然后，置第七只螞蟻禁忌矩陣。期j 的第七行所有元素為m ，表明此機器 已經(jīng)有任務(wù)。同時置陣虬。上的第j 一列為礬f ，表明此任務(wù)已經(jīng)分配了；置第七只螞蟻 的任務(wù)分配矩陣r 。，的元素，i 一1 ；代價向量見以的元素以以- c 匈k 。弓i 由式( 2 7 ) 計算，即 弓 ，韭業(yè) 羅z q ，i ) 口y ( f ，| 尸 7 習 式中：口，盧為可調(diào)系數(shù)，分別表示先前螞蟻的工作循環(huán)中由第f 臺機器來完成第j 項 任務(wù)的信息素量及第f 臺機器完成第j 項任務(wù)的效率的相對重要性； ( 2 ) s - 2 ，計算遍歷其余萬一1 項任務(wù)分配給其余以一1 臺機器的概率弓 ，選出其中 最大的概率，記為最厶 ，即由第臺機器來完成第歹。項任務(wù)然后，置第七只螞蟻禁忌 矩陣虬。i 的第行為腑，表明此機器已經(jīng)分配了任務(wù)。同時置陣。- i 的第_ i f 。列為 姍，表明此任務(wù)已經(jīng)分配了；置第七只螞蟻的任務(wù)分配矩陣尺。j 的元素& l 工- 1 ：代 價向量見以的元素仉以s 仇以+ q 厶；s + 1 ，重復(fù)步驟( 2 ) ，直到s 一萬結(jié)束； ( 3 ) 七墨刀，重復(fù)步驟( 1 ) 和( 勁，直到七一刀結(jié)束； ( 4 ) 更新矩陣r 的值。由于信息量的值是不斷增加的，為了防止信息量的無限增長 設(shè)一個蒸發(fā)系數(shù)p 1 ，從第2 次算法循環(huán)開始，在每次算法循環(huán)開始時，根據(jù)r r p 來計算z 陣，以此來限制信息量的無限增長。引入全體螞蟻的信息量的增量z ，由于 每只螞蟻撒的信息量與其工作循環(huán)所銜憫代價成反比毗竹。薈羞其帆q 為常數(shù)； ( 5 ) 求出代價向量d 以中最小的元素，記為d c 柚。c + 1 ，重復(fù)以上各步，直到 c - c 一需要注意的是，每次算法循環(huán)所得到的釓岫與前一次算法循環(huán)得到 d 以吐曲相比較，取其中的較小值作為柚。 2 5 本章小結(jié) 一般說來，在由任意多個處理機組成的分布式系統(tǒng)中實現(xiàn)最優(yōu)的任務(wù)分配是一個 n p 難問題。本章主要闡述了分布式系統(tǒng)中任務(wù)分配的一些經(jīng)典算法的過程及其優(yōu)缺點， 并對近年來出現(xiàn)的一些新算法進行了探討 分布式系統(tǒng)任務(wù)分配問題的蟻群優(yōu)化算法研究 第3 章蟻群優(yōu)化算法 易于表述但難于求解的組合優(yōu)化問題始終是研究中的一個熱點。許多應(yīng)用問題都屬 于n p 難問題，也就是說，人們普遍認為在多項式的計算時間內(nèi)無法獲得這些問題的最 優(yōu)解。正因為如此，在解決大規(guī)模的實際應(yīng)用問題時，人們不得不采取近似的方法以求 在一個相對較短的時間內(nèi)獲得近似最優(yōu)解。在非嚴格的定義下，人們把這類近似算法稱 為啟發(fā)式算法( h 即融i c s ) 。通常這種算法通過利用針對具體問題的相關(guān)知識來建立或者 改進所求得的解。 最近，許多研究者把焦點集中于一種叫做元啟發(fā)式算法( m c t a h c u r i s t i i 對的新型算法 上。這里所謂的元啟發(fā)式算法指的是一類算法的集合，它可以用來定義一個大范圍內(nèi)應(yīng) 用于不同問題的啟發(fā)式方法。對于難解的、與實際問題有關(guān)的組合優(yōu)化問題，元啟發(fā)式 算法的使用可以明顯提高算法在一個合理的時間內(nèi)找到高質(zhì)量解的能力。 其中一種特別成功的元啟發(fā)式算法的靈感來源于真實螞蟻的行為。從螞蟻系統(tǒng)( a n t s y s t 咖，a - s