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

碩士學(xué)位論文 摘要 任務(wù)分配問(wèn)題是一類典型的組合優(yōu)化問(wèn)題。多處理器系統(tǒng)上的最優(yōu)任務(wù)分配的研究 是有效利用系統(tǒng)資源處理實(shí)際問(wèn)題的熱點(diǎn)課題，這方面的研究結(jié)果在大規(guī)模數(shù)值計(jì)算、 l s i 和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)等方面都有很好的應(yīng)用背景。在理論方面，由于任務(wù)分配問(wèn)題是 被公認(rèn)的n p 難問(wèn)題，所以如何構(gòu)造有效的啟發(fā)式算法或近似算法是目前研究的熱點(diǎn)領(lǐng) 域。 蟻群優(yōu)化算法是受自然界中的螞蟻覓食行為啟發(fā)而提出的一種新穎的仿生進(jìn)化算 法，適用于求解復(fù)雜組合優(yōu)化問(wèn)題。目前，蟻群優(yōu)化算法己成功應(yīng)用于求解旅行商問(wèn)題、 二次分配問(wèn)題，取得了很好的實(shí)驗(yàn)效果。受其影響，國(guó)內(nèi)外許多學(xué)者對(duì)其進(jìn)行了大量的 研究工作，將其推廣到了諸多優(yōu)化領(lǐng)域，并已經(jīng)取得了相當(dāng)豐富的研究成果。 雖然蟻群優(yōu)化算法的應(yīng)用范圍幾乎涉及到各個(gè)優(yōu)化領(lǐng)域，但是還存在很多不足。比 如：對(duì)于蟻群優(yōu)化算法求解分布式系統(tǒng)中的任務(wù)分配問(wèn)題的研究大都是在對(duì)該問(wèn)題試驗(yàn) 條件或約束條件進(jìn)行簡(jiǎn)化的前提下進(jìn)行的。 本文將蟻群優(yōu)化算法應(yīng)用于求解約束條件更復(fù)雜的任務(wù)分配問(wèn)題：一個(gè)任務(wù)只能分 配給一個(gè)處理機(jī)處理，而一個(gè)處理機(jī)可以處理多個(gè)任務(wù)，其中每個(gè)處理機(jī)都有固定成本 和能力限制。將該任務(wù)分配問(wèn)題表示成完全二部圖，通過(guò)螞蟻在完全二部圖上搜索較優(yōu) 路徑來(lái)尋求該問(wèn)題的較優(yōu)解。選擇不同規(guī)模的幾組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，對(duì)每一組數(shù)據(jù)，通過(guò) 反復(fù)試測(cè)探索了信息素?fù)]發(fā)系數(shù)，信息素啟發(fā)式因子和期望值啟發(fā)式因子的合理設(shè)定， 并將所得的計(jì)算結(jié)果與禁忌搜索和隨機(jī)方法作比較。結(jié)果表明蟻群優(yōu)化算法對(duì)不同規(guī)模 的任務(wù)分配問(wèn)題都有較優(yōu)的結(jié)果，具有比禁忌搜索算法和隨機(jī)方法更優(yōu)的性能。 將另一任務(wù)分配問(wèn)題抽象為一種新的有別于二部圖的圖形表示形式。針對(duì)蟻群優(yōu)化 算法易陷入局部最優(yōu)的不足，提出了一種求解任務(wù)分配問(wèn)題的混合算法，該算法將簡(jiǎn)單 禁忌搜索算法嵌入蟻群優(yōu)化算法，利用禁忌搜索算法較強(qiáng)的局部搜索能力，提高了蟻群 優(yōu)化算法的優(yōu)化能力，改善了任務(wù)分配問(wèn)題解的質(zhì)量。仿真實(shí)驗(yàn)表明混合算法的性能優(yōu) 于基本蟻群算法。 最后，對(duì)本文的研究工作進(jìn)行了總結(jié)，并指出了蟻群優(yōu)化算法在該領(lǐng)域進(jìn)一步還要 研究的問(wèn)題。 關(guān)鍵詞：蟻群優(yōu)化算法：任務(wù)分配問(wèn)題：分布式系統(tǒng)；組合優(yōu)化 分布式系統(tǒng)任務(wù)分配問(wèn)題的蟻群優(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 笛a(bǔ)n 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 財(cái)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ù)分配問(wèn)題的蟻群優(yōu)化算法研究 插圖索引 圖1 1 分布式系統(tǒng)示意圖3 圖3 1 四類問(wèn)題的關(guān)系圖。1 5 圖3 2 螞蟻尋找最短路徑示意圖1 6 圖4 1 信息素?fù)]發(fā)系數(shù)與總的花費(fèi)代價(jià)的關(guān)系3 2 圖4 2 參數(shù)設(shè)定界面。3 3 圖4 3 程序運(yùn)行結(jié)果界面：3 3 圖5 1 混合算法求解任務(wù)分配問(wèn)題的總體框架3 6 圖5 2 任務(wù)分配問(wèn)題的圖形表示3 7 圖5 3 混合算法和基本蟻群算法的性能比較4 0 碩士學(xué)位論文 附表索引 表2 1 任務(wù)分配矩陣8 表4 1 啟發(fā)式因子口和盧的不同組合對(duì)算法性能的影響。3 2 表4 2 不同算法的計(jì)算結(jié)果比較3 4 表5 1 混合算法與基本蟻群算法計(jì)算結(jié)果比較。4 0 v 蘭州理工大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說(shuō)明 原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的 研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或 集體已經(jīng)發(fā)表或撰寫(xiě)的成果作品。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均 已在文中以明確方式標(biāo)明。本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。 作者簽名：互靈寢 日期：礎(chǔ)年6 月j 鄉(xiāng)日 學(xué)位論文版權(quán)使用授權(quán)書(shū) 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有 權(quán)保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和 借閱。本人授權(quán)蘭州理工大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù) 庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。同 時(shí)授權(quán)中國(guó)科學(xué)技術(shù)信息研究所將本學(xué)位論文收錄到中國(guó)學(xué)位論文全文數(shù)據(jù) 庫(kù)，并通過(guò)網(wǎng)絡(luò)向社會(huì)公眾提供信息服務(wù)。 作者簽名： 導(dǎo)師簽名： 白期：幻。辟歹月房日 日期：諺年二月i 弓日 碩+ 學(xué)位論文 1 1 分布式系統(tǒng)概述 第1 章緒論 分布式系統(tǒng)是二十世紀(jì)九十年代以來(lái)計(jì)算機(jī)領(lǐng)域的研究熱點(diǎn)之一。作為網(wǎng)絡(luò)一體化 和并行處理分布化的產(chǎn)物，分布式系統(tǒng)解決了系統(tǒng)透明性及處理機(jī)動(dòng)態(tài)分配等問(wèn)題，表 現(xiàn)出了強(qiáng)大的生命力。 一個(gè)被大家公認(rèn)的分布式系統(tǒng)的定義是：“分布式系統(tǒng)是一些獨(dú)立的計(jì)算機(jī)的集合， 但在用戶看來(lái)卻是一臺(tái)計(jì)算機(jī)一【1 1 。在硬件結(jié)構(gòu)上，盡管所有的分布式系統(tǒng)都是由多個(gè) c p u 構(gòu)成的，但可以用不同的方法將硬件組織起來(lái)，形成不同的系統(tǒng)。按照體系結(jié)構(gòu)劃 分，當(dāng)前典型的分布式系統(tǒng)可分為兩種：共享存儲(chǔ)多處理機(jī)與分布存儲(chǔ)多計(jì)算機(jī)。如果 結(jié)點(diǎn)間通過(guò)公用存儲(chǔ)器中的共享變量實(shí)現(xiàn)相互通信，就稱為多處理機(jī)( m u l t i p r o c c s s o r s ) ； 如果結(jié)點(diǎn)間使用消息傳遞方式來(lái)實(shí)現(xiàn)相互通信，就稱為多計(jì)算機(jī)( m u l t i c o m p u t e 喲【2 。 共享存儲(chǔ)多處理機(jī)屬于緊密耦合的分布式系統(tǒng)，采用共享主存通信。一個(gè)典型的共 享存儲(chǔ)多處理機(jī)系統(tǒng)由m 個(gè)存儲(chǔ)模塊、p 個(gè)處理器和d 個(gè)i o 通道組成，( 朋，p ，d ) 的數(shù) 目按情況而定。由于處理機(jī)與主存之間互連網(wǎng)絡(luò)帶寬有限，所以當(dāng)處理機(jī)數(shù)增多時(shí)，訪 問(wèn)主存的沖突概率會(huì)加大，互連網(wǎng)絡(luò)會(huì)成為系統(tǒng)性能的瓶頸。但由于是單一地址空間， 所以較易于編程。 分布存儲(chǔ)多計(jì)算機(jī)屬于松散耦合的分布式系統(tǒng)，它的每個(gè)處理單元都是一個(gè)獨(dú)立性 較強(qiáng)的節(jié)點(diǎn)，系由c p u 、本地存儲(chǔ)器、i o 設(shè)備和消息傳遞通信接口所組成。由于每個(gè) 計(jì)算節(jié)點(diǎn)的本地存儲(chǔ)器容量較大，所以運(yùn)算時(shí)所需的絕大部分指令和數(shù)據(jù)均可取自本地 存儲(chǔ)器。當(dāng)不同計(jì)算節(jié)點(diǎn)上的進(jìn)程需要通信時(shí)，就可通過(guò)接口進(jìn)行消息交換。在有的松 散耦合的多計(jì)算機(jī)系統(tǒng)中，其計(jì)算節(jié)點(diǎn)本身就是一臺(tái)完整的計(jì)算機(jī)，這樣就演變成了現(xiàn) 代的機(jī)群系統(tǒng)。這種松散性耦合結(jié)構(gòu)易于擴(kuò)展，但多地址空間卻使編程較困難。 分布式系統(tǒng)與集中式系統(tǒng)相比，有其自身的優(yōu)點(diǎn)。分布式系統(tǒng)有較高的性能價(jià)格比， 它還可能具有任何價(jià)位上的大型機(jī)都無(wú)法達(dá)到的性能。分布式系統(tǒng)的另一個(gè)優(yōu)點(diǎn)是它有 更高的可靠性，通過(guò)將任務(wù)交由多個(gè)機(jī)器共同承擔(dān)，單個(gè)芯片的故障只會(huì)讓一臺(tái)機(jī)器停 下來(lái)，而其它的機(jī)器將繼續(xù)工作。對(duì)于一些關(guān)鍵性應(yīng)用，例如控制核反應(yīng)堆或飛機(jī)，使 用分布式系統(tǒng)來(lái)達(dá)到高可靠性是最主要的考慮因素，并且在負(fù)載增加時(shí)分布式系統(tǒng)較集 中式系統(tǒng)更容易擴(kuò)展。 1 2 論文選題的背景和意義 眾所周知，一般情形下( 處理機(jī)個(gè)數(shù)大于3 ) 的任務(wù)分配問(wèn)題是n p 難的。人們不 分布式系統(tǒng)任務(wù)分配問(wèn)題的蟻群優(yōu)化算法研究 ” 會(huì)盲目地去尋求解決這類問(wèn)題的最優(yōu)解。但對(duì)于具體的分布式系統(tǒng)，在適當(dāng)假設(shè)條件下， 尋找不一定最優(yōu)但實(shí)際可行且效果較滿意的方法，仍是現(xiàn)今十分活躍的研究課題p j 。在 這方面已經(jīng)研究出了許多各具特色的算法，較有代表性的一些算法是：基于圖論的分配 算法、數(shù)學(xué)規(guī)劃方法、啟發(fā)式算法、各種負(fù)載共享策略、動(dòng)態(tài)投標(biāo)算法以及專家系統(tǒng)方 法等。它們可粗略地分為兩大類：靜態(tài)分配策略和動(dòng)態(tài)分配策略。前者是在系統(tǒng)運(yùn)行的 初始時(shí)刻，將用戶提交的任務(wù)一次性分配給系統(tǒng)中各處理機(jī)，此后直到這些任務(wù)運(yùn)行完 畢，各處理機(jī)上的任務(wù)一般不再變更。其特點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，但效果有限。后者是在運(yùn)行 過(guò)程中，將任務(wù)分配給各處理機(jī)，并對(duì)其上的任務(wù)數(shù)進(jìn)行動(dòng)態(tài)調(diào)整，盡可能使系統(tǒng)中各 處理機(jī)上的負(fù)載達(dá)到基本平衡。其主要特點(diǎn)是能充分發(fā)揮各處理機(jī)的能力，但實(shí)現(xiàn)起來(lái) 復(fù)雜程度高。 本節(jié)介紹分布式系統(tǒng)中的幾種任務(wù)分配( t a s ka l l 0 c a t i ) 策略，這些策略的著眼點(diǎn) 就是設(shè)法減少系統(tǒng)中各處理機(jī)間的通信開(kāi)銷(xiāo)和執(zhí)行模塊所需的開(kāi)銷(xiāo)，以此來(lái)提高整個(gè)系 統(tǒng)的性能。 處理機(jī)間的通信( 簡(jiǎn)稱口c ) 開(kāi)銷(xiāo)是由位于不同處理機(jī)上的模塊互相傳遞數(shù)據(jù)所引 起的。因此，m c 是模塊間的通信( 簡(jiǎn)稱m c ) 和模塊分配的函數(shù)，這里蹦c 是指每 對(duì)模塊間的數(shù)據(jù)傳遞。顯然，如果兩個(gè)模塊同駐在一個(gè)處理機(jī)上，那么，它們就不會(huì)引 起口c ( 假定同駐模塊間的通信開(kāi)銷(xiāo)忽略不計(jì)) 。 通常，若干模塊構(gòu)成一個(gè)任務(wù)，一個(gè)任務(wù)是單一的處理實(shí)體。任務(wù)分解和任務(wù)分配 是用于減少口c 的兩個(gè)必要步驟。任務(wù)分解的目的是把一個(gè)提交的任務(wù)分劃成若干獨(dú)立 的、具有最小玎c 的模塊；任務(wù)分配則是指把這些模塊分配給處理機(jī)，使得它們由于 i p c 所引起的開(kāi)銷(xiāo)最小。假定任務(wù)分解已由軟件設(shè)計(jì)者在設(shè)計(jì)階段完成，提交給系統(tǒng)的 任務(wù)已經(jīng)分解成若干模塊。本節(jié)主要討論如何以最優(yōu)方式將模塊分配給處理機(jī)。注意模 塊的個(gè)數(shù)通常多于( 甚至遠(yuǎn)遠(yuǎn)多于) 處理機(jī)的個(gè)數(shù)，因此，多個(gè)模塊可能分配給一個(gè)處 理機(jī)下面將討論任務(wù)分配環(huán)境、影響系統(tǒng)性能的因素。 1 2 1 任務(wù)分配環(huán)境 一般的分布式系統(tǒng)的示意圖如圖1 1 所示，其中伍，乏，乙) 是一組待處理的模塊， ( 只，只，”、只) 是系統(tǒng)中的筇個(gè)處理機(jī)，它們經(jīng)由互聯(lián)網(wǎng)互相通信；模塊分配機(jī)制s 把坍個(gè) 模塊合理地分配給刀個(gè)處理機(jī)中的某個(gè)處理機(jī)，通常冊(cè) 一。位于不同處理機(jī)上的模塊 彼此交換數(shù)據(jù)是通過(guò)它們所在的處理機(jī)彼此通信來(lái)實(shí)現(xiàn)的。任何一對(duì)模塊的i m c 是由 設(shè)計(jì)階段確定的，而且在模塊分配期間是模塊的一個(gè)固定特性。由于i m c 的總量將隨 著模塊對(duì)的不同而變化，因此，把這些模塊分配給處理機(jī)的方式可能影響整個(gè)系統(tǒng)的處 理開(kāi)銷(xiāo)。例如，若兩個(gè)模塊互和l 的蹦c 量很大，通信也較頻繁，而且它們又分配在 不同的處理機(jī)上，那么，相應(yīng)的口c 開(kāi)銷(xiāo)就會(huì)增大。如果把五和t 分配到同一處理機(jī)上， 就可能減少系統(tǒng)的總處理開(kāi)銷(xiāo)。此外，若兩個(gè)模塊的i m c 較少，而且也無(wú)優(yōu)先制約關(guān) 2 碩士學(xué)位論文 系，把它們分配給不同的處理機(jī)顯然可能加速整個(gè)處理過(guò)程。 圖1 1 分布式系統(tǒng)示意圖 1 2 2 影響系統(tǒng)性能的因素 均衡負(fù)載分配策略是把模塊合理地分配給系統(tǒng)中的所有處理機(jī)，使得這些處理機(jī)差 不多是均勻負(fù)載的。顯然，這種分配策略可最大限度地提高系統(tǒng)的吞吐量。如果只注重 減少口c 而不考慮系統(tǒng)的均衡負(fù)載，就可將待處理的模塊全部分配給同一處理機(jī)處理。 顯然，這種分配策略可使口c 降至最低，但對(duì)同一任務(wù)的處理時(shí)間卻成倍地增加了。 不難看出，均衡負(fù)載和減少口c 是相互沖突的兩個(gè)因素，它們左右著任務(wù)分配策略， 影響著系統(tǒng)的性能。負(fù)載平衡可以提高整個(gè)系統(tǒng)的吞吐量，因?yàn)樗噲D將模塊盡可能均 等地分配給處理機(jī)。但由于坤c 的開(kāi)銷(xiāo)又迫使分配策略不得不盡可能把較多的模塊分配 給盡可能少的處理機(jī)任務(wù)分配策略就是要設(shè)法平衡這兩個(gè)因素，將模塊分配給處理機(jī)， 使整個(gè)系統(tǒng)的性能提至最高。 1 3 研究現(xiàn)狀 計(jì)算機(jī)技術(shù)與應(yīng)用的飛速發(fā)展，使得分布式系統(tǒng)的應(yīng)用越來(lái)越廣泛【4 j 。但隨著分布 式計(jì)算機(jī)系統(tǒng)的發(fā)展，分布式計(jì)算機(jī)領(lǐng)域中出現(xiàn)了很多亟待解決的問(wèn)題，其中任務(wù)的分 配和調(diào)度是一個(gè)關(guān)鍵性的問(wèn)題。因?yàn)楫?dāng)分布式系統(tǒng)中處理器個(gè)數(shù)增多時(shí)，任務(wù)間的通信 開(kāi)銷(xiāo)和處理機(jī)間等待時(shí)間增大，系統(tǒng)效率趨于飽和甚至下降，所以合理的任務(wù)分配策略 是提高分布式系統(tǒng)效率不可缺少的措施任務(wù)的分配將關(guān)系到系統(tǒng)的吞吐量、資源的利 用率等，對(duì)于發(fā)揮各處理單元的作用，從整體上提高系統(tǒng)資源的利用率等具有非常重要 的意義。因此在分布式系統(tǒng)中，任務(wù)分配問(wèn)題一直是重要的研究課題之一 任務(wù)分配問(wèn)題是被公認(rèn)的n p 難問(wèn)題【4 】。任務(wù)分配的目的是減少并行運(yùn)行任務(wù)間的 通信開(kāi)銷(xiāo)和等待時(shí)間，改善負(fù)荷的均衡性，提高實(shí)時(shí)任務(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 圖論 法簡(jiǎn)單直觀，適用于任務(wù)數(shù)和處理機(jī)數(shù)較小的系統(tǒng)；數(shù)學(xué)規(guī)劃法是用數(shù)學(xué)規(guī)劃的方法求 解任務(wù)、處理機(jī)、系統(tǒng)資源間約束關(guān)系對(duì)應(yīng)的一組方程式的最優(yōu)解，由于求解的是m 問(wèn)題，從而失去其工程應(yīng)用價(jià)值；只有啟發(fā)式方法實(shí)用簡(jiǎn)單，它是從系統(tǒng)結(jié)構(gòu)和任務(wù)特 點(diǎn)出發(fā)，運(yùn)用一些有效的分配原則，使某些代價(jià)函數(shù)接近最優(yōu)的任務(wù)分配策略。很多文 章已證明合理的啟發(fā)式方法求得的解雖不是最優(yōu)解，卻是次優(yōu)解，尤其在其它兩類方法 3 分布式系統(tǒng)任務(wù)分配問(wèn)題的蟻群優(yōu)化算法研究 中難以考慮的資源共享、時(shí)間鏈約束、通信開(kāi)銷(xiāo)和延遲、存取i ，o 設(shè)備均可在啟發(fā)式方 法中得以考慮。 1 圖論法 圖論方法中，應(yīng)用于任務(wù)分配最重要的方法是偶圖的匹配算法。將系統(tǒng)描述成一個(gè) 偶圖，在這個(gè)偶圖中存在兩個(gè)集合，分別為任務(wù)集合與結(jié)點(diǎn)集合，并用結(jié)點(diǎn)與任務(wù)問(wèn)的 邊表示任務(wù)的分配。加入任務(wù)間通信費(fèi)用的考慮，文獻(xiàn)【1 2 】提出了相應(yīng)的結(jié)點(diǎn)匹配算法。 在文獻(xiàn)【1 3 】中，使用圖中的結(jié)點(diǎn)來(lái)表示任務(wù)。每?jī)蓚€(gè)任務(wù)間的通信費(fèi)用預(yù)知，并由 連接這兩個(gè)結(jié)點(diǎn)的無(wú)向邊的權(quán)重來(lái)表示。如果費(fèi)用為0 則表示這兩個(gè)任務(wù)間不存在通信； 而費(fèi)用為無(wú)窮則表示這兩個(gè)任務(wù)必須被分配到同一個(gè)處理器( 結(jié)點(diǎn)) 。 2 數(shù)學(xué)規(guī)劃法 這種方法的主要思想是把任務(wù)分配問(wèn)題概括成一種優(yōu)化問(wèn)題，然后利用數(shù)學(xué)規(guī)劃方 法去解決它【7 】【引。 3 啟發(fā)式方法 文獻(xiàn)【1 3 】指出：有些應(yīng)用由于自身的限制，無(wú)法在很重要的時(shí)間限度內(nèi)獲得一個(gè)最 優(yōu)解。對(duì)于這些應(yīng)用，啟發(fā)式方法能夠提供快速而有效的算法。在該方法中，使用很多 假設(shè)以減少任務(wù)分配的計(jì)算時(shí)間和，這些假設(shè)包括網(wǎng)絡(luò)處理器是同構(gòu)的、完全連接的， 或各任務(wù)間的先后次序可被忽略。在這些假設(shè)條件下，可使用啟發(fā)式模型簇算法，來(lái)實(shí) 現(xiàn)基于實(shí)時(shí)與存儲(chǔ)空間限制的任務(wù)分配。 文獻(xiàn)【1 4 】指出：可用圖表示的啟發(fā)式算法可被大致分為：交互式算法與非交互式算 法。非交互式算法利用t f g 的圖論屬性來(lái)得到一個(gè)最優(yōu)化某一費(fèi)用函數(shù)的方案。交互 式算法則是生成一個(gè)初始的隨機(jī)方案，然后逐步優(yōu)化，直到費(fèi)用函數(shù)值最小。由于這兩 類方案的不同，費(fèi)用函數(shù)對(duì)其得到有效方案的影響也不同。一般的費(fèi)用標(biāo)準(zhǔn)，如最小化 總體執(zhí)行時(shí)間，或最小化最重負(fù)載處理器的負(fù)載，被這兩類算法共同采用。 另外，其它啟發(fā)式算法也為解決此類問(wèn)題提供了新的途徑。遺傳算法是一類模擬生 物界自然進(jìn)化和遺傳過(guò)程的隨機(jī)搜索和優(yōu)化算法，具有在大問(wèn)題空間求解近似最優(yōu)解的 能力。正因遺傳算法的強(qiáng)健性和對(duì)復(fù)雜問(wèn)題的求解能力，有人將其應(yīng)用于多處理機(jī)系統(tǒng) 的任務(wù)分配與調(diào)度【1 5 1 【1 6 1 。 模擬退火算法是基于m o n t ec a l l o 迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是 基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。文獻(xiàn)【1 7 】【1 8 】應(yīng)用 模擬退火算法求解任務(wù)分配問(wèn)題。 文獻(xiàn)【1 9 】運(yùn)用改進(jìn)的螞蟻算法來(lái)求解簡(jiǎn)單的任務(wù)分配問(wèn)題，即一個(gè)任務(wù)只能分配給 一臺(tái)機(jī)器處理，且每臺(tái)機(jī)器只能處理一個(gè)任務(wù)。本文主要研究應(yīng)用蟻群優(yōu)化算法求解分 布式系統(tǒng)上約束條件更復(fù)雜的任務(wù)分配問(wèn)題，即一個(gè)任務(wù)只能分配給一個(gè)處理機(jī)處理， 而一個(gè)處理機(jī)可以處理多個(gè)任務(wù)，其中每個(gè)處理機(jī)都有固定成本和能力限制，同時(shí)假設(shè) 每項(xiàng)任務(wù)在不同的處理器上完成具有不同的費(fèi)用，并且不同的處理機(jī)存在著通訊開(kāi)銷(xiāo)。 4 碩士學(xué)位論文 1 4 本文的研究?jī)?nèi)容及結(jié)構(gòu)安排 第一章介紹了分布式系統(tǒng)中的任務(wù)分配問(wèn)題、選題背景及研究現(xiàn)狀。 第二章介紹了較有代表性的任務(wù)分配算法：基于圖論的分配策略、整數(shù)規(guī)劃方法和 啟發(fā)式算法，并對(duì)這三類典型算法進(jìn)行比較和分析 第三章首先從組合優(yōu)化問(wèn)題、n p 問(wèn)題及計(jì)算復(fù)雜性分析入手，對(duì)近年來(lái)被廣泛應(yīng)用 的，具有代表性的仿生進(jìn)化算法的算法原理、特點(diǎn)、研究現(xiàn)狀等進(jìn)行了綜述，重點(diǎn)介紹 了蟻群優(yōu)化算法的原理、特點(diǎn)、改進(jìn)算法以及研究與應(yīng)用現(xiàn)狀。 第四章應(yīng)用蟻群優(yōu)化算法來(lái)解決多處理器分布式系統(tǒng)上約束條件更復(fù)雜的任務(wù)分 配問(wèn)題：一個(gè)任務(wù)只能分配給一個(gè)處理機(jī)處理，而一個(gè)處理機(jī)可以處理多個(gè)任務(wù)，其中 每個(gè)處理機(jī)都有固定成本和能力限制。仿真結(jié)果表明該算法比禁忌搜索和隨機(jī)方法具有 更好的求解能力 在第五章中，為解決蟻群優(yōu)化算法易陷入局部最優(yōu)的不足，提出了一種求解任務(wù)分 配問(wèn)題的混合算法。該算法將簡(jiǎn)單禁忌搜索算法嵌入蟻群優(yōu)化算法，利用禁忌搜索算法 較強(qiáng)的局部搜索能力，提高了蟻群優(yōu)化算法的優(yōu)化能力，改善了任務(wù)分配問(wèn)題解的質(zhì)量。 仿真實(shí)驗(yàn)表明混合算法的性能優(yōu)于基本蟻群算法。 最后，對(duì)本文的研究工作進(jìn)行了總結(jié)和展望。 5 分布式系統(tǒng)任務(wù)分配問(wèn)題的蟻群優(yōu)化算法研究 第2 章分布式系統(tǒng)中的任務(wù)分配問(wèn)題 在分布式系統(tǒng)中，任務(wù)分配問(wèn)題一直是重要的研究課題之一。任務(wù)分配是在分布式 系統(tǒng)環(huán)境中，將給定的一組子任務(wù)，按照系統(tǒng)的當(dāng)前狀態(tài)，按照一定的執(zhí)行時(shí)序分配到 網(wǎng)絡(luò)結(jié)點(diǎn)上，以期獲得較好的系統(tǒng)執(zhí)行性能。現(xiàn)階段，分布式系統(tǒng)任務(wù)分配問(wèn)題的求解 算法大致可分為三類：基于圖論的分配策略、整數(shù)規(guī)劃方法和啟發(fā)式算法，下面對(duì)這三 類典型算法進(jìn)行比較和分析。 2 1 基于圖論的分配策略 基于圖論的分配策略的基本思想【3 l 是把待分配的一組模塊作為圖中的節(jié)點(diǎn)集，連接 兩個(gè)節(jié)點(diǎn)的有向連線上的權(quán)表示每對(duì)模塊之間的i m c 開(kāi)銷(xiāo)。c 開(kāi)銷(xiāo)為0 意指相應(yīng)的 兩模塊之間無(wú)通信發(fā)生，因此它們?cè)趫D中無(wú)連線；m c 開(kāi)銷(xiāo)為意指相應(yīng)的兩模塊間通 信量很大，必須分配給同一處理機(jī)。可見(jiàn)，圖中節(jié)點(diǎn)間連線上的權(quán)表示分配在不同處理 機(jī)上每對(duì)模塊之間的通信開(kāi)銷(xiāo)。假定任何一對(duì)同駐模塊的口c 開(kāi)銷(xiāo)為0 。若把系統(tǒng)的總 開(kāi)銷(xiāo)定義為系統(tǒng)的處理開(kāi)銷(xiāo)和口c 開(kāi)銷(xiāo)之和，那么，這種分配策略的目的就是實(shí)現(xiàn)最小 的總開(kāi)銷(xiāo)。處理開(kāi)銷(xiāo)和口c 開(kāi)銷(xiāo)都是模塊到處理機(jī)分配的函數(shù)，為了表示模塊到處理機(jī) 的分配，可定義下面的分配矩陣x ：而j 一1 表示模塊1 分配到處理機(jī)最處理：毛上，0 表 示模塊正未被處理機(jī)只處理。而處理開(kāi)銷(xiāo)則由下面的q 矩陣給出： q 一饑工 ， f 一1 ，2 ，”，肺，七一1 ，2 ，“，刀 其中，吼。表示模塊正在處理機(jī)最上的處理開(kāi)銷(xiāo)，它是該模塊處理要求的度量。 q 。一隱含模塊互不可能在處理機(jī)罡上執(zhí)行。 令c ；，表示模塊互和疋之間的i m c 開(kāi)銷(xiāo)。于是處理給定任務(wù)的總開(kāi)銷(xiāo)z 可表示為x 的函數(shù)： r1 r 伍) 。；軍卜j + 薈薈q ，t 上工， 佇，、 其中，第一項(xiàng)表示每個(gè)模塊在它所分配的處理機(jī)上的處理開(kāi)銷(xiāo)；第二項(xiàng)則表示非同 駐模塊間的口c 開(kāi)銷(xiāo)。最小開(kāi)銷(xiāo)分配則是在這種圖上執(zhí)行最小分割算法來(lái)獲得。 這種分配策略的最大優(yōu)點(diǎn)是它的簡(jiǎn)明性。但它也存在一些限制和不足：第一，所用 的最小分割算法是一種基本的最小分割算法，它只能用于實(shí)現(xiàn)兩個(gè)或三個(gè)處理機(jī)間的最 小開(kāi)銷(xiāo)分配。若將它擴(kuò)充成處理任意個(gè)數(shù)的處理機(jī)，則需要萬(wàn)維( 刀個(gè)處理機(jī)分配) 的 最小分配算法，該算法是極其復(fù)雜的。這就限制了這種任務(wù)分配策略的應(yīng)用范圍；第二， 這種方法既未提供有關(guān)存儲(chǔ)空間或處理時(shí)間等方面的限制手段，也未提供負(fù)載均衡方面 的機(jī)制；第三，它沒(méi)有能力去觀察排隊(duì)延遲效果。當(dāng)一個(gè)以上的模塊分配給同一個(gè)處理 機(jī)時(shí)，就不可避免地會(huì)出現(xiàn)延遲。因此，基于圖論的任務(wù)分配策略不是任務(wù)分配問(wèn)題的 6 最好解決辦法。 2 2 整數(shù)規(guī)劃方法 該方法的基本思想【3 l 是仍用前面定義的q 矩陣來(lái)表示執(zhí)行開(kāi)銷(xiāo)，但用一個(gè)聊肌矩 陣y 來(lái)定義m c ： y 一饑，j 1 墨fs 歷1 5 j s 小& 屹j 為互向乃傳送的數(shù)據(jù)量j 同時(shí)引進(jìn)一個(gè)尼 的距離矩陣d ： d a 留u1 1s fs 行& 1 5 _ s 刀d “為只與弓問(wèn)的距離 模塊分配函數(shù)用冊(cè) 矩陣z 來(lái)定義： x k ，1 1s fs 用& 1 墨j s 刀毛，一1 表示五分畔上 該分配方法的目標(biāo)函數(shù)定義為： r b ) 2 ；沖以+ 墨荔v ，j 其中，常數(shù)w 用來(lái)調(diào)節(jié)通信開(kāi)銷(xiāo)和執(zhí)行開(kāi)銷(xiāo)間的差異。 此時(shí)，任務(wù)分配即要找使r 最小的那個(gè)x 的指派。因此，這種方法實(shí)質(zhì)是帶有某些 限制條件的隱式枚舉算法，其時(shí)間復(fù)雜度隨問(wèn)題規(guī)模成指數(shù)增長(zhǎng)。這顯然限制了算法的 實(shí)用性。這種方法的優(yōu)點(diǎn)是很容易加入適當(dāng)?shù)南拗茥l件，以滿足實(shí)際環(huán)境的需要。 m a e t a l 提出了一種分支界限法【2 0 l ，它用一棵搜索樹(shù)來(lái)表示分配問(wèn)題，每個(gè)葉子結(jié)點(diǎn) 處表示一個(gè)分配方案。除了存貯限制和實(shí)時(shí)限制外，它還引入了以下限制條件： 蝴阮 ：= 篙不骱一 ， 冊(cè)刪模螄黼唯：二篙礁?jìng)蛱蛇鸵?以及允許一個(gè)任務(wù)( 模塊) 的多份拷貝，以提高系統(tǒng)的可靠性。 該算法在每個(gè)分支處檢查p ，e 關(guān)系和存貯及實(shí)時(shí)限制條件，若不滿足，則剪枝： 若滿足，則檢查這次分配后的部分開(kāi)銷(xiāo)是否超過(guò)已得到的最小全部開(kāi)銷(xiāo)，若超過(guò)，則剪 枝；否則就分配，并選擇下一擴(kuò)充結(jié)點(diǎn)。若全部可能的路徑都被探查完，或規(guī)定的執(zhí)行 時(shí)間己到，則算法結(jié)束。 該算法的空間復(fù)雜度較小，只需記錄當(dāng)前最小開(kāi)銷(xiāo)的分配方案和此開(kāi)銷(xiāo)即可，約為 d b 廳) 。但時(shí)間復(fù)雜度仍可能是指數(shù)級(jí)的，而且沒(méi)有保護(hù)模塊優(yōu)先規(guī)定的機(jī)制和實(shí)施負(fù) 載平衡的機(jī)制。 7 分布式系統(tǒng)任務(wù)分配問(wèn)題的蟻群優(yōu)化算法研究 2 3 基于遺傳算法和模擬退火算法的任務(wù)分配策略 ( 1 ) 算法說(shuō)明 設(shè)有一個(gè)由露個(gè)處理機(jī)p 一切。，p ：，一 p 。 組成( 可以是不同的處理機(jī)) 的分布式系 統(tǒng)【3 l ，需要執(zhí)行川個(gè)任務(wù)r i 。，f ：，一、f ) ，一般刀 朋。為了便于分析問(wèn)題，可以建立下 述五元組： 羅一仃， ，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 是一個(gè)冊(cè)萬(wàn)矩陣， 其元素q u 表示任務(wù)在處理機(jī)p ，上的執(zhí)行時(shí)間( 假設(shè)每個(gè)任務(wù)的運(yùn)行時(shí)間已知) ；c 是 一個(gè)歷刀矩陣，c ；，表示任務(wù) 與f ；之間的通信開(kāi)銷(xiāo)；z 是一個(gè)加刀的任務(wù)分配矩陣， 其中t 。j = 1 表示分配到處理機(jī)p ，上執(zhí)行，否則毛j 一0 。 為了實(shí)現(xiàn)選擇，還必須設(shè)計(jì)一個(gè)目標(biāo)函數(shù)c o s f 。c o s f 是一個(gè)包含多種因素折衷的函 數(shù)，它應(yīng)能體現(xiàn)出設(shè)計(jì)者對(duì)系統(tǒng)的性能要求，例如可以采取下述方法： c 0 酣。善薈【吼上飛上+ 曠薈薈q ，強(qiáng)上呵，j ( 2 3 ) 其中常數(shù)w 用來(lái)調(diào)節(jié)通信開(kāi)銷(xiāo)和執(zhí)行開(kāi)銷(xiāo)之間的差異。在實(shí)際設(shè)計(jì)過(guò)程中，還可以 選取不同的w 的值或其它目標(biāo)函數(shù)。 ( 2 ) 算法描述及簡(jiǎn)單分析 第一階段初始化 隨機(jī)產(chǎn)生一個(gè)任務(wù)分配矩陣集：先設(shè)定一個(gè)全零的任務(wù)分配矩陣x ，然后在x 中的每一行由系統(tǒng)隨機(jī)選定一個(gè)元素為1 。如表2 1 所示，在3 個(gè)處理機(jī)和7 個(gè)任務(wù)的 情況下，f 。、f ：、被分配給p l ；、毛被分配給p ：；氣、f ，被分配給p ，。用同樣的方 法可產(chǎn)生多個(gè)任務(wù)分配矩陣 表2 1 任務(wù)分配矩陣 任務(wù)處理機(jī) p lp 2p 3 f l 1o0 f 2 1oo f 3 1o0 01o 毛 o10 氣 0o1 f 7 0o 1 描述和確定初始任務(wù)分配集：對(duì)一個(gè)給定的任務(wù)分配方案，可用一個(gè)數(shù)據(jù)結(jié)構(gòu) 黝一p ，r 【1 j l 】 來(lái)描述： 8 碩士學(xué)位論文 其中s 是一個(gè)l o g ：刀1 腳位的二進(jìn)制串，每位1 0 9 ：刀1 為一節(jié)，從左到右第f 節(jié)表示 任務(wù)i 所在的處理機(jī)情況，這樣表2 1 中的任務(wù)分配矩陣可以表示為s = 0 00 0 0 00 10 11 0 1 0 。因?yàn)橛? 個(gè)處理機(jī)，所以兩位為一節(jié)，0 0 ，0 1 ，1 0 分別表示任務(wù)被分配到磯，p ：， 以上執(zhí)行，1 1 是無(wú)效編碼。 r 是一個(gè)萬(wàn)鏈表數(shù)組，r p 】表示處理機(jī)阢上的任務(wù)執(zhí)行順序，仍以表2 1 為例，若 任務(wù)之間滿足“ 一優(yōu)先關(guān)系 ) ，則可確定三種任務(wù)分配方案： p 。上執(zhí)行順序?yàn)閒 。，f 2 ；p 2 上執(zhí)行順序?yàn)?，如；p 3 上執(zhí)行順序?yàn)閒 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 由于分配到同一處理機(jī)上的任務(wù)之間有多種排列，所以從一個(gè)任務(wù)分配矩陣可以產(chǎn) 生多種方案。在這些方案中，有一些是違背“ 一優(yōu)先關(guān)系的，稱為無(wú)效分配方案，否 則，稱為有效分配方案。上面列出的就是三種有效分配方案。從每一個(gè)任務(wù)分配矩陣所 產(chǎn)生的分配方案中各選取一種或幾種有效分配方案，便形成初始任務(wù)分配方案集。 設(shè)置模擬退火算法中的初始溫度f(wàn) 研矽。和收斂率口：溫度紉慨+ 1 一口紉，張逐步 降低，這里0 口 ，口以成立的可能性也越大，越容易被接受。反之同理。 2 4 螞蟻算法 任務(wù)分配問(wèn)題【1 9 l 最簡(jiǎn)單的一種情形可描述為，有以個(gè)任務(wù)需要分配給廳個(gè)機(jī)器去完 成，每個(gè)任務(wù)只能分配給1 臺(tái)機(jī)器處理，且每臺(tái)機(jī)器只能處理1 個(gè)任務(wù)，不同的分配花 費(fèi)不同的代價(jià)。任務(wù)分配問(wèn)題要求找到1 種分配方案所花費(fèi)的代價(jià)最小。 若第f 臺(tái)機(jī)器完成第j 項(xiàng)任務(wù)的代價(jià)g 之o ，則可構(gòu)成代價(jià)矩陣q 期。求解如何分 配機(jī)器，才能在完成總?cè)蝿?wù)的條件下，使總的花費(fèi)代價(jià)最小。 設(shè) ；t，-i：!：l：!：j!：!；：!f；li：l；!：!；j!：；：!；l；燃z，-，。，2，t q o1 l o 表示不由第f 臺(tái)機(jī)器完成第f 項(xiàng)任務(wù) q 。 一”一” 、_ 7 則分配問(wèn)題是求解任務(wù)分配陣k 約束條件為 善吩。1 再嘞1 1 嘞- 嘞 | a1 2 ，廳 i ，1 ，2 ，刀 f ，i j 一1 2 ，刀 ( 2 5 ) ( 2 6 ) 在滿足上述約束條件下，使目標(biāo)函數(shù)c 響。善薈q 嘞成立，q c 腳，嘞尺一期。 求解任務(wù)分配問(wèn)題的螞蟻算法的步驟如下：。 ( 1 ) 令c 一1 ，s 一1 七一1 ( 從第1 只螞蟻開(kāi)始) ，首先計(jì)算第七臺(tái)機(jī)器完成廳項(xiàng)任務(wù)的 概率，i ( j 一1 醌，刀) ，選出其中最大的概率，記為i ，即由第七臺(tái)機(jī)器來(lái)完成第 1 0 碩士學(xué)位論文 j 眥項(xiàng)任務(wù)。然后，置第七只螞蟻禁忌矩陣。期j 的第七行所有元素為m ，表明此機(jī)器 已經(jīng)有任務(wù)。同時(shí)置陣虬。上的第j 一列為礬f ，表明此任務(wù)已經(jīng)分配了；置第七只螞蟻 的任務(wù)分配矩陣r 。，的元素，i 一1 ；代價(jià)向量見(jiàn)以的元素以以- c 匈k 。弓i 由式( 2 7 ) 計(jì)算，即 弓 ，韭業(yè) 羅z q ，i ) 口y ( f ，| 尸 7 習(xí) 式中：口，盧為可調(diào)系數(shù)，分別表示先前螞蟻的工作循環(huán)中由第f 臺(tái)機(jī)器來(lái)完成第j 項(xiàng) 任務(wù)的信息素量及第f 臺(tái)機(jī)器完成第j 項(xiàng)任務(wù)的效率的相對(duì)重要性； ( 2 ) s - 2 ，計(jì)算遍歷其余萬(wàn)一1 項(xiàng)任務(wù)分配給其余以一1 臺(tái)機(jī)器的概率弓 ，選出其中 最大的概率，記為最厶 ，即由第臺(tái)機(jī)器來(lái)完成第歹。項(xiàng)任務(wù)然后，置第七只螞蟻禁忌 矩陣虬。i 的第行為腑，表明此機(jī)器已經(jīng)分配了任務(wù)。同時(shí)置陣。- i 的第_ i f 。列為 姍，表明此任務(wù)已經(jīng)分配了；置第七只螞蟻的任務(wù)分配矩陣尺。j 的元素& l 工- 1 ：代 價(jià)向量見(jiàn)以的元素仉以s 仇以+ q 厶；s + 1 ，重復(fù)步驟( 2 ) ，直到s 一萬(wàn)結(jié)束； ( 3 ) 七墨刀，重復(fù)步驟( 1 ) 和( 勁，直到七一刀結(jié)束； ( 4 ) 更新矩陣r 的值。由于信息量的值是不斷增加的，為了防止信息量的無(wú)限增長(zhǎng) 設(shè)一個(gè)蒸發(fā)系數(shù)p 1 ，從第2 次算法循環(huán)開(kāi)始，在每次算法循環(huán)開(kāi)始時(shí)，根據(jù)r r p 來(lái)計(jì)算z 陣，以此來(lái)限制信息量的無(wú)限增長(zhǎng)。引入全體螞蟻的信息量的增量z ，由于 每只螞蟻撒的信息量與其工作循環(huán)所銜憫代價(jià)成反比毗竹。薈羞其帆q 為常數(shù)； ( 5 ) 求出代價(jià)向量d 以中最小的元素，記為d c 柚。c + 1 ，重復(fù)以上各步，直到 c - c 一需要注意的是，每次算法循環(huán)所得到的釓岫與前一次算法循環(huán)得到 d 以吐曲相比較，取其中的較小值作為柚。 2 5 本章小結(jié) 一般說(shuō)來(lái)，在由任意多個(gè)處理機(jī)組成的分布式系統(tǒng)中實(shí)現(xiàn)最優(yōu)的任務(wù)分配是一個(gè) n p 難問(wèn)題。本章主要闡述了分布式系統(tǒng)中任務(wù)分配的一些經(jīng)典算法的過(guò)程及其優(yōu)缺點(diǎn)， 并對(duì)近年來(lái)出現(xiàn)的一些新算法進(jìn)行了探討 分布式系統(tǒng)任務(wù)分配問(wèn)題的蟻群優(yōu)化算法研究 第3 章蟻群優(yōu)化算法 易于表述但難于求解的組合優(yōu)化問(wèn)題始終是研究中的一個(gè)熱點(diǎn)。許多應(yīng)用問(wèn)題都屬 于n p 難問(wèn)題，也就是說(shuō)，人們普遍認(rèn)為在多項(xiàng)式的計(jì)算時(shí)間內(nèi)無(wú)法獲得這些問(wèn)題的最 優(yōu)解。正因?yàn)槿绱?，在解決大規(guī)模的實(shí)際應(yīng)用問(wèn)題時(shí)，人們不得不采取近似的方法以求 在一個(gè)相對(duì)較短的時(shí)間內(nèi)獲得近似最優(yōu)解。在非嚴(yán)格的定義下，人們把這類近似算法稱 為啟發(fā)式算法( h 即融i c s ) 。通常這種算法通過(guò)利用針對(duì)具體問(wèn)題的相關(guān)知識(shí)來(lái)建立或者 改進(jìn)所求得的解。 最近，許多研究者把焦點(diǎn)集中于一種叫做元啟發(fā)式算法( m c t a h c u r i s t i i 對(duì)的新型算法 上。這里所謂的元啟發(fā)式算法指的是一類算法的集合，它可以用來(lái)定義一個(gè)大范圍內(nèi)應(yīng) 用于不同問(wèn)題的啟發(fā)式方法。對(duì)于難解的、與實(shí)際問(wèn)題有關(guān)的組合優(yōu)化問(wèn)題，元啟發(fā)式 算法的使用可以明顯提高算法在一個(gè)合理的時(shí)間內(nèi)找到高質(zhì)量解的能力。 其中一種特別成功的元啟發(fā)式算法的靈感來(lái)源于真實(shí)螞蟻的行為。從螞蟻系統(tǒng)( a n t s y s t 咖，a - s