分布式系統(tǒng)任務分配問題的蟻群優(yōu)化算法研究.pdf

1、任務分配問題是一類典型的組合優(yōu)化問題。多處理器系統(tǒng)上的最優(yōu)任務分配的研究是有效利用系統(tǒng)資源處理實際問題的熱點課題，這方面的研究結果在大規(guī)模數(shù)值計算、VLSI和計算機網(wǎng)絡技術等方面都有很好的應用背景。在理論方面，由于任務分配問題是被公認的NP難問題，所以如何構造有效的啟發(fā)式算法或近似算法是目前研究的熱點領域。 蟻群優(yōu)化算法是受自然界中的螞蟻覓食行為啟發(fā)而提出的一種新穎的仿生進化算法，適用于求解復雜組合優(yōu)化問題。目前，蟻群優(yōu)化算法已

2、成功應用于求解旅行商問題、二次分配問題，取得了很好的實驗效果。受其影響，國內(nèi)外許多學者對其進行了大量的研究工作，將其推廣到了諸多優(yōu)化領域，并已經(jīng)取得了相當豐富的研究成果。 雖然蟻群優(yōu)化算法的應用范圍幾乎涉及到各個優(yōu)化領域，但是還存在很多不足。比如：對于蟻群優(yōu)化算法求解分布式系統(tǒng)中的任務分配問題的研究大都是在對該問題試驗條件或約束條件進行簡化的前提下進行的。 本文將蟻群優(yōu)化算法應用于求解約束條件更復雜的任務分配問題：一個任

3、務只能分配給一個處理機處理，而一個處理機可以處理多個任務，其中每個處理機都有固定成本和能力限制。將該任務分配問題表示成完全二部圖，通過螞蟻在完全二部圖上搜索較優(yōu)路徑來尋求該問題的較優(yōu)解。選擇不同規(guī)模的幾組數(shù)據(jù)進行實驗，對每一組數(shù)據(jù)，通過反復試測探索了信息素揮發(fā)系數(shù)，信息素啟發(fā)式因子和期望值啟發(fā)式因子的合理設定，并將所得的計算結果與禁忌搜索和隨機方法作比較。結果表明蟻群優(yōu)化算法對不同規(guī)模的任務分配問題都有較優(yōu)的結果，具有比禁忌搜索算法和隨

4、機方法更優(yōu)的性能。 將另一任務分配問題抽象為一種新的有別于二部圖的圖形表示形式。針對蟻群優(yōu)化算法易陷入局部最優(yōu)的不足，提出了一種求解任務分配問題的混合算法，該算法將簡單禁忌搜索算法嵌入蟻群優(yōu)化算法，利用禁忌搜索算法較強的局部搜索能力，提高了蟻群優(yōu)化算法的優(yōu)化能力，改善了任務分配問題解的質量。仿真實驗表明混合算法的性能優(yōu)于基本蟻群算法。 最后，對本文的研究工作進行了總結，并指出了蟻群優(yōu)化算法在該領域進一步還要研究的問題。