[發(fā)明專利]一種基于并行遺傳算法的網(wǎng)格資源分配方法

無效

• 申請?zhí)枺?/td>: 200810048464.4
• 申請日: 2008-07-21
• 公開（公告）號: CN101324854A
• 公開（公告）日: 2008-12-17
• 發(fā)明（設(shè)計）人: 李春林;宋曼
• 申請（專利權(quán)）人: 武漢理工大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06N3/12;H04L29/08
• 代理公司: 武漢開元專利代理有限責(zé)任公司
• 代理人: 潘杰

技術(shù)領(lǐng)域

本發(fā)明屬于計算機網(wǎng)格資源的分配方法，特別是一種基于并行遺傳算法的網(wǎng)格資源分配方法。

背景技術(shù)

目前，網(wǎng)格計算已成為高性能計算發(fā)展的主要趨勢，它是未來全球科學(xué)合作、大規(guī)模計算和數(shù)據(jù)處理的基石。由于網(wǎng)格中集成資源的異構(gòu)性、分布性和自治性等特點，需要提供網(wǎng)格中間件來屏蔽這些特性，從而為人們提供透明的服務(wù)。Ad?hoc網(wǎng)格是一個異構(gòu)的計算(HC)通信系統(tǒng)，允許移動的設(shè)施在對立的環(huán)境中完成一組任務(wù)。例如災(zāi)難管理、森林滅火和防護作用等任務(wù)，這些任務(wù)要求如同網(wǎng)格這樣的工作環(huán)境可靠的支持，從而在這些特定環(huán)境下工作的計算機能協(xié)調(diào)工作。這樣能量管理問題成了Ad?hoc網(wǎng)格關(guān)心的主要問題。這里主要研究在Ad?hoc網(wǎng)格中如何靜態(tài)的分配資源給由相互通信的子任務(wù)組成的請求。這樣分配的目標(biāo)是在ad?hoc網(wǎng)格環(huán)境下最小化此請求執(zhí)行時的平均能量消耗。其中，要解決的關(guān)鍵問題就是能量資源分配問題。簡單地說，網(wǎng)格能量資源分配就是將n個獨立的任務(wù)映射到m臺機器的能量資源上，使得任務(wù)在滿足約束的條件下，最大化HC系統(tǒng)性能特性。顯然，在空間大小為2m的資源集合上尋找滿足目標(biāo)的最優(yōu)資源集合，這是一個NP問題。于是人們通常利用啟發(fā)式算法來簡化問題，并尋求問題的最優(yōu)解，但多數(shù)這類算法通常都難以避免局部最小值問題。遺傳算法作為一種最有效的啟發(fā)式全局隨機搜索算法，對于NP問題，能夠得到滿意的結(jié)果。

遺傳算法是根據(jù)自然進化論與遺傳變異理論為基礎(chǔ)求解全局最優(yōu)解的仿生型算法，其本質(zhì)是一種求解問題的高效并行全局搜索算法。它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程，從而得到最優(yōu)解或準(zhǔn)最優(yōu)解。遺傳算法是一個以適應(yīng)度函數(shù)為依據(jù)，通過對群體個體施加遺傳操作實現(xiàn)群體內(nèi)個體結(jié)構(gòu)重組的迭代處理過程。在這一過程中，群體個體一代一代地得以優(yōu)化并逐漸逼近最優(yōu)解。盡管遺傳算法比其他傳統(tǒng)搜索方法有更強的魯棒性，但它更擅長于全局搜索，由于算法的交叉、變異和選擇算子是在概率意義下進行的，容易引起模式的丟失或缺失，導(dǎo)致算法的早熟，因此它的局部搜索能力不足。研究發(fā)現(xiàn)，遺傳算法可以用極快的速度達到最優(yōu)解的90％左右，但要達到真正的最優(yōu)解則要花費很長的時間。一些對比實驗還表明，如果兼顧收斂速度和解的品質(zhì)兩個指標(biāo)，單純的遺傳算法未必比其他方法更優(yōu)越。

遺傳算法已被應(yīng)用于異質(zhì)計算環(huán)境中的任務(wù)匹配和調(diào)度，但它們都采用串行的方法，得到的資源分配速度不夠理想。考慮到遺傳算法的天然并行性，并結(jié)合網(wǎng)格資源分配的特點。

發(fā)明內(nèi)容

本發(fā)明的目的是將能量資源引入到網(wǎng)格資源調(diào)度中，提出了基于并行遺傳算法的網(wǎng)格資源分配方法。

為了實現(xiàn)本發(fā)明的目的，本發(fā)明的具體方法是：

第一步驟：開始；

第二步驟：主線程初始化系統(tǒng)數(shù)據(jù)信息創(chuàng)建子線程，并傳送數(shù)據(jù)；

第三步驟：并行執(zhí)行第四步驟至第十步驟；

第四步驟：產(chǎn)生子群體；

第五步驟：計算個體適應(yīng)度；

第六步驟：向主線程傳送最優(yōu)個體；

第七步驟：判斷當(dāng)前時間是否是遷移率的整數(shù)倍，若是，轉(zhuǎn)第八步驟；若不是，轉(zhuǎn)第九步驟；

第八步驟：執(zhí)行遷移；

第九步驟：執(zhí)行遺傳算子；

第十步驟：判斷是否滿足終止條件，若是，轉(zhuǎn)第十一步驟；若不是，返回到第五步驟；

第十一步驟：執(zhí)行停止，輸出最優(yōu)結(jié)果；

第十二步驟：結(jié)束。

本發(fā)明提出的遺傳算法作為一種最有效的啟發(fā)式全局隨機搜索算法，最時候NP問題的求解。遺傳算法根據(jù)自然進化論與遺傳變異理論為基礎(chǔ)求解全局最優(yōu)解，其本質(zhì)是一種求解問題的高效并行全局搜索算法。它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程，從而得到最優(yōu)解或準(zhǔn)最優(yōu)解。隨著機器數(shù)目和任務(wù)數(shù)量的增加，問題的規(guī)模將以指數(shù)級增長，因此需要研究更為高效的能量管理算法。本發(fā)明根據(jù)遺傳算法天然的并行性提出的并行遺傳算法提高了算法求解的質(zhì)量與速度，是一種有效的網(wǎng)格能量資源優(yōu)化方法，有利于提高網(wǎng)格的服務(wù)質(zhì)量。

附圖說明

圖1為染色體任務(wù)的DAG圖。

圖2為圖1中DAG的2個染色體。

圖3為任務(wù)調(diào)度串交叉操作的例子。

圖4為匹配串交叉操作的例子。

圖5為本發(fā)明的流程圖。

具體實施方式

下面結(jié)合附圖對本發(fā)明作進一步的詳細描述。

在描述本發(fā)明的技術(shù)方案前，先對本發(fā)明中的一些問題作出如下定義：