網(wǎng)絡計算環(huán)境中基于智能算法的任務調(diào)度研究.pdf

1、智能優(yōu)化算法是近幾年發(fā)展的一類仿生算法，具有自組織、自學習、自適應、多點并行及有指導搜索等特點，已被廣泛應用于工程技術(shù)、非線性優(yōu)化、結(jié)構(gòu)性設計、并行計算和社會科學等領(lǐng)域。本文利用智能優(yōu)化算法能夠較好地解決復雜問題的優(yōu)點，研究網(wǎng)絡計算中任務分配與調(diào)度(Task Matching and Scheduling)問題。任務分配與調(diào)度是充分利用網(wǎng)絡計算潛力的關(guān)鍵技術(shù)，也是NP-hard問題，該問題的解決對于高性能計算的應用與發(fā)展具有十分重要的意

2、義。 針對智能優(yōu)化算法的普適性和具體問題的特殊性，提出算法的改進策略和具體操作算子的設計；基于進化算法的共性，對進化算法用于調(diào)度問題的算法設計進行深入研究。主要研究內(nèi)容如下： (1)針對蟻群優(yōu)化(Ant Colony Optimization，ACO)算法擅長解決離散問題，但信息素設計比較困難的特點，提出利用調(diào)度任務圖靜態(tài)和動態(tài)屬性作為啟發(fā)信息的策略，設計了相關(guān)算法，實驗證明了該算法的優(yōu)良性能。通過分析算法的性能，研究了

3、啟發(fā)信息的選取原則和實施方案。在此基礎上設計了并行蟻群調(diào)度算法，并在MPICH支撐平臺上實現(xiàn)，研究了不同并行方式對調(diào)度性能的影響，以及并行群體中信息交換策略和信息交換頻率的難題，進一步提高了算法的性能和速度。 (2)分析進化算法在優(yōu)化問題中的應用特點，提出了調(diào)度問題解空間的不同編碼方式和解碼方法，研究了算法搜索過程中有效的進化操作。以微分算法為例，對兩種調(diào)度編碼方式分別設計同構(gòu)系統(tǒng)調(diào)度算法，并比較兩種方式的調(diào)度性能。在算法實現(xiàn)過

4、程中，根據(jù)問題設計特殊的交叉、變異算子，并通過隨機拓撲排序方法獲得初始群體，綜合局部搜索策略，加速算法收斂，提高運行質(zhì)量和全局搜索能力。實驗表明，兩種編碼方式都能有效解決調(diào)度問題，且基于任務排列的方式優(yōu)于基于任務優(yōu)先級的方式。 (3)針對任務排列編碼方式較優(yōu)的特點，提出了基于粒子群優(yōu)化(Particle SwarmOptimization，PSO)算法的異構(gòu)調(diào)度算法，設計具有問題特征的進化算子，保證算法能在可接受的時間內(nèi)提供高質(zhì)

5、量的解，避免了現(xiàn)有算法中采用平均值而導致調(diào)度不合理的缺點。量子行為粒子群優(yōu)化算法是對標準PSO的一種改進，參數(shù)少，理論上能保證解全局收斂。針對任務優(yōu)先級編碼方式容易實現(xiàn)的特點，綜合調(diào)度問題的空間信息，設計了混合量子行為粒子群的調(diào)度算法，研究提高算法性能的策略，實驗驗證了算法的有效性。 (4)針對網(wǎng)格任務調(diào)度難點，分析網(wǎng)格異構(gòu)環(huán)境中任務分配與調(diào)度的關(guān)鍵問題，研究了網(wǎng)格計算模型下靜態(tài)任務分配與調(diào)度的算法；同時根據(jù)網(wǎng)格環(huán)境中資源自治和