[發(fā)明專利]一種MapReduce計(jì)算模型中基于遺傳算法的數(shù)據(jù)平衡方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310015988.4
• 申請(qǐng)日: 2013-01-16
• 公開（公告）號(hào): CN103106253A
• 公開（公告）日: 2013-05-15
• 發(fā)明（設(shè)計(jì)）人: 伍衛(wèi)國(guó);樊源泉;魏偉;朱霍;高顏
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06N3/12
• 代理公司: 西安智大知識(shí)產(chǎn)權(quán)代理事務(wù)所 61215
• 代理人: 賀建斌

1.一種MapReduce計(jì)算模型中基于遺傳算法的數(shù)據(jù)平衡方法，其特征在于，包括以下步驟：

1）、獲取全局Map輸出信息，得到reduce任務(wù)處理的分區(qū)的元數(shù)據(jù)信息，Reduce元數(shù)據(jù)的獲取過程為：

1.1、每個(gè)Map任務(wù)在完成處理過程并將輸出結(jié)果寫入本地磁盤后，會(huì)通過TaskTracker利用心跳信息發(fā)送任務(wù)完成消息到JobTracker；

1.2、JobTracker為每個(gè)MapReduce作業(yè)維護(hù)一個(gè)Map任務(wù)完成消息隊(duì)列，當(dāng)某個(gè)運(yùn)行reduce任務(wù)的TaskTracker請(qǐng)求獲取Map任務(wù)時(shí)，依據(jù)該reduce任務(wù)所屬的作業(yè)，從相應(yīng)隊(duì)列中取出消息并傳遞給TaskTracker；

1.3、同一作業(yè)中的reduce任務(wù)從所在的TaskTracker獲取Map任務(wù)完成消息，從中提取Map任務(wù)的運(yùn)行時(shí)信息，包括Map任務(wù)編號(hào)，執(zhí)行節(jié)點(diǎn)，利用這些信息，reduce任務(wù)建立與執(zhí)行節(jié)點(diǎn)間的HTTP連接，并請(qǐng)求Map任務(wù)輸出的元數(shù)據(jù)信息；

1.4、TaskTracker依據(jù)請(qǐng)求的Map任務(wù)編號(hào)，從本地文件系統(tǒng)中讀取相應(yīng)Map任務(wù)輸出的索引文件，并發(fā)送給請(qǐng)求的reduce任務(wù)；

1.5、reduce任務(wù)合并不同索引文件中的相同編號(hào)虛擬分區(qū)，匯總各個(gè)虛擬分區(qū)中所有同種類型<Key，Value>鍵值對(duì)的數(shù)據(jù)量，由于每個(gè)reduce任務(wù)要獲取所有map任務(wù)輸出的元數(shù)據(jù)信息；

2）、對(duì)Map的輸出數(shù)據(jù)進(jìn)行處理，reduce任務(wù)獲取各個(gè)map任務(wù)輸出的分區(qū)原始數(shù)據(jù)；將匯總后的元數(shù)據(jù)提交給重分區(qū)器，采用基因算法對(duì)元數(shù)據(jù)進(jìn)行平衡分區(qū)，基因算法是對(duì)二進(jìn)制位串進(jìn)行操作，其具體步驟如下：

2.1、將Map輸出數(shù)據(jù)的元數(shù)據(jù)收集起來放在一個(gè)集合中，作為一個(gè)種群，對(duì)種群中的每個(gè)元素進(jìn)行編碼，所謂的編碼就是用“0、1”組成的代碼表示每一個(gè)元素，本發(fā)明采用的編碼方式是用1的個(gè)數(shù)來表示元素所在集合中的下標(biāo)，對(duì)該種群進(jìn)行隨機(jī)劃分，劃分成N個(gè)子集，其中N與reduce的個(gè)數(shù)相對(duì)應(yīng)，每一次的劃分形成一個(gè)基因，經(jīng)過多次劃分之后，形成一個(gè)基因組；

2.2、在基因算法中適應(yīng)度函數(shù)是用來衡量遺傳個(gè)體對(duì)于生存環(huán)境的適應(yīng)程度，適應(yīng)度越高的個(gè)體獲得更多的復(fù)制機(jī)會(huì)，反之亦然，因此，定義一個(gè)適應(yīng)度函數(shù)

min{Σj=1n|Sj-S|}/n]]>公式（1）

,其中，為全部子集的元素之和的平均值，公式（1）中目標(biāo)函數(shù)描述的是各個(gè)子集合到平均值的平均距離，利用該公式（1），對(duì)每一個(gè)基因計(jì)算其適應(yīng)度函數(shù)，形成一個(gè)新的集合，接著求出每一個(gè)基因適應(yīng)度函數(shù)的概率，即一個(gè)基因的適應(yīng)度函數(shù)的值除以整個(gè)基因組的適應(yīng)度函數(shù)值之和；

2.3、將選擇算子應(yīng)用于基因組，采用的選擇算子是輪盤賭選擇法，利用隨機(jī)函數(shù)產(chǎn)生一個(gè)在[0,1]之間的隨機(jī)數(shù)，判斷其在基因組中的適應(yīng)度概率序列中的位置，如果它最多能大于序列中的第m個(gè)值，則表示m號(hào)基因被選中，自由指定需要選擇的基因的個(gè)數(shù)；

2.4、對(duì)選出來基因進(jìn)行交叉運(yùn)算，即把優(yōu)質(zhì)基因的部分結(jié)構(gòu)加以替換重新組合形成新的基因，采用單點(diǎn)交叉算子，具體操作是：隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，對(duì)應(yīng)輪盤賭選擇算法選擇出來的基因，進(jìn)行交叉，即該交叉點(diǎn)前后的兩個(gè)基因的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新個(gè)體，并且確保交換之后的基因組不會(huì)出現(xiàn)有空集合的情況，設(shè)定一個(gè)nullGen標(biāo)志，遍歷交叉后的基因組，如若發(fā)現(xiàn)有空集合存在，即將nullGen標(biāo)志設(shè)置為false，并以此來標(biāo)識(shí)該刪除的基因；

2.5、對(duì)交叉后的基因進(jìn)行變異運(yùn)算，變異運(yùn)算是依據(jù)變異概率將基因組中某些基因用其它的基因來替換從而形成一個(gè)新的個(gè)體，采用固定位變異算子，并且將變異概率設(shè)為0.1，以期獲得最優(yōu)解，固定位變異算子是指對(duì)單個(gè)基因固定的指定的某一位或某幾位基因作變異操作：原有基因?yàn)?的，則變?yōu)?，原有基因?yàn)?的，則變?yōu)?，經(jīng)過變異操作之后，對(duì)變異后的基因進(jìn)行非空檢查，保證編譯后的基因依然會(huì)有N個(gè)子集；

2.6、以上描述了一輪進(jìn)化過程，經(jīng)過多輪進(jìn)化之后依據(jù)精英保留策略選擇保留的基因，采用的基因保留策略是：經(jīng)過以上步驟后，計(jì)算每一個(gè)基因的目標(biāo)函數(shù)值，并將其與基因組中所有基因的目標(biāo)函數(shù)值相比較，將前者小于后者的基因保留下來；

2.7、對(duì)保留下來的基因進(jìn)行解碼，就可獲得對(duì)元數(shù)據(jù)的一個(gè)優(yōu)化的組合，即將元數(shù)據(jù)劃分成N個(gè)大小基本相當(dāng)?shù)淖蛹缓螅瑢⒚總€(gè)子集對(duì)應(yīng)的元數(shù)據(jù)分配到一個(gè)reducer上，這樣就保證每個(gè)reducer所處理的數(shù)據(jù)量是相當(dāng)?shù)摹?!-- SIPO -->