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

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

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

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

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

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