基于GAPSO混合算法的網格工作流調度研究.pdf

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

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

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

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

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