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

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

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

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

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