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

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

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

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

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

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