基于GAPSO混合算法的網(wǎng)格工作流調(diào)度研究.pdf

1、網(wǎng)格計(jì)算自從上一世紀(jì)九十年代中期出現(xiàn)以來,逐漸被認(rèn)為是支持廣域并行和分布式計(jì)算的下一代主流計(jì)算平臺(tái),可以實(shí)現(xiàn)計(jì)算、信息、數(shù)據(jù)、存儲(chǔ)、知識(shí)等資源的全面共享。網(wǎng)格工作流將工作流管理和網(wǎng)格計(jì)算結(jié)合起來,提供了一種分布式協(xié)作的工作流系統(tǒng)解決方案。目前情況來看,網(wǎng)格技術(shù)更注重于研究面向服務(wù)技術(shù)方面。在工作流執(zhí)行過程中,服務(wù)質(zhì)量(QoS)的應(yīng)用,促使調(diào)度者根據(jù)服務(wù)質(zhì)量來選擇成員服務(wù),這樣網(wǎng)格中的資源可以更好地按照用戶的需求來進(jìn)行組織和分配。網(wǎng)格工作

2、流調(diào)度側(cè)重于研究廣泛分布的資源及任務(wù)調(diào)度,直接影響著網(wǎng)格工作流執(zhí)行的成功率及其效率,可以說是一個(gè)非常復(fù)雜且具有挑戰(zhàn)性的問題。本文通過對(duì)網(wǎng)格工作流進(jìn)行建模并改進(jìn)其任務(wù)調(diào)度算法,來提高網(wǎng)格工作流的性能。
　　 諸如選擇路由、并行路由等多種復(fù)雜情況存在于實(shí)際工作流中,基于DAG圖簡單直觀的特點(diǎn),本文選擇DAG建模來表明網(wǎng)格工作流任務(wù)調(diào)度過程。網(wǎng)格工作流執(zhí)行過程中的任務(wù)或者狀態(tài)表示為DAG圖的結(jié)點(diǎn),任務(wù)之間的時(shí)序依賴關(guān)系表示為有向弧,而

3、一些屬性和參數(shù)則表示為弧上的權(quán)值。接下來為了解決網(wǎng)格工作流任務(wù)調(diào)度過程中多目標(biāo)優(yōu)化問題,本文提出了多QOS條件下網(wǎng)格工作流調(diào)度模型,定義了多維度的QOS參數(shù)標(biāo)準(zhǔn)體系結(jié)構(gòu),并對(duì)各個(gè)參數(shù)進(jìn)行重新定義,重點(diǎn)分析了網(wǎng)格工作流環(huán)境下各種不同約束關(guān)系的結(jié)構(gòu)中服務(wù)質(zhì)量的計(jì)算方式。本文在基于遺傳算法(GA)和粒子群算法(PSO)基礎(chǔ)上,提出了遺傳粒子群(GAPSO)混合算法,引用了特殊的適應(yīng)度函數(shù),在遺傳算法部分設(shè)定了動(dòng)態(tài)的交叉和變異概率,并提出了動(dòng)態(tài)

4、切換算法和終止算法的方法,同時(shí)也改進(jìn)了粒子群算法中慣性權(quán)重的設(shè)置以及對(duì)粒子進(jìn)行離散化。結(jié)合各自算法的優(yōu)勢,在算法運(yùn)行初期利用遺傳算法的全局搜索能力進(jìn)行優(yōu)化搜索,在后期利用粒子群算法快速收斂能力提高算法的運(yùn)行速度。
　　 本文通過MATLAB工具進(jìn)行仿真,共設(shè)計(jì)了三組實(shí)驗(yàn)。首先為了減少參數(shù)的取值對(duì)算法性能帶來的誤差,選取不同的混合算法切換系數(shù)S,根據(jù)它們在相同的初始種群數(shù)量范圍內(nèi)末代種群平均適應(yīng)度值變化情況,來選擇最優(yōu)的S值；然后

5、在一個(gè)具體的工作流實(shí)例中求解滿足服務(wù)質(zhì)量的最優(yōu)解,證明通過改進(jìn)的GAPSO混合調(diào)度算法求解的最優(yōu)解滿足該工作流實(shí)例中不同用戶對(duì)服務(wù)質(zhì)量的要求,符合計(jì)算網(wǎng)格工作流中的復(fù)雜環(huán)境；最后比較了應(yīng)用于網(wǎng)格工作流任務(wù)優(yōu)化調(diào)度的改進(jìn)的GAPSO算法和其它調(diào)度算法在不同服務(wù)個(gè)數(shù)情況下,尋找到最優(yōu)解時(shí)算法的執(zhí)行時(shí)間,證明了混合算法的優(yōu)越性。實(shí)驗(yàn)結(jié)果表明本文提出的改進(jìn)的GAPSO混合算法在網(wǎng)格工作流調(diào)度方面具有更高的效率,能更有效地解決網(wǎng)格工作流調(diào)度問題。