沈炳華

摘 要：本文提出了一種基于遺傳算法的ETL任務(wù)調(diào)度改進(jìn)算法。由于ETL調(diào)度子任務(wù)之間具有先后順序的限制，傳統(tǒng)遺傳算法不能很好的適應(yīng)。本文通過對(duì)傳統(tǒng)遺傳算法的各個(gè)步驟進(jìn)行相應(yīng)處理，得到一種改進(jìn)的ETL任務(wù)調(diào)度算法；實(shí)際應(yīng)用結(jié)果表明調(diào)度算法顯著提高了處理ETL子任務(wù)的效率。

關(guān)鍵詞：數(shù)據(jù)倉庫；ETL任務(wù)調(diào)度；遺傳算法

任務(wù)的調(diào)度問題是一個(gè)NP完全問題，即不可能在多項(xiàng)式時(shí)間內(nèi)找到問題的最優(yōu)解。遺傳算法是計(jì)算機(jī)科學(xué)人工智能領(lǐng)域中用于解決最優(yōu)化的一種搜索啟發(fā)式算法，具有在復(fù)雜解空間中迅速找到最優(yōu)解的能力。本文中所述的算法嘗試使用遺傳算法來解決ETL任務(wù)中要求子任務(wù)具有一定前后約束關(guān)系的任務(wù)調(diào)度問題。

1 交叉運(yùn)算

交叉運(yùn)算的目的是在新一代個(gè)體中基于上一代產(chǎn)生新的個(gè)體，決定了遺傳算法的全局搜索能力。對(duì)于設(shè)置的某一概率pc交換兩個(gè)個(gè)體之間的部分染色體。由于子任務(wù)先后順序之間的約束性，我們在交叉運(yùn)算的同時(shí)也要保持子任務(wù)之間原有的先后順序。

⑴交叉算子1。交叉算子1在兩個(gè)父類調(diào)度方案之間交叉。

步驟1：隨機(jī)選擇兩個(gè)個(gè)體作為要交換的對(duì)象，tsj，tsk。

步驟2：隨機(jī)生成一整數(shù) 作為要交換的層的數(shù)字，在中隨機(jī)選出第j層的所有子任務(wù) 作為要交換的候選子任務(wù)。對(duì)調(diào)度子串，將2個(gè)調(diào)度中的第j層子任務(wù)按順序交換；對(duì)處理機(jī)子串，將這些交換的子任務(wù)所對(duì)應(yīng)的處理機(jī)子串上的位依次進(jìn)行交換。

由于是在同一層的子任務(wù)上進(jìn)行交換處理機(jī)子串，所以不會(huì)改變子任務(wù)處理的先后關(guān)系，滿足調(diào)度任務(wù)的要求。

⑵交叉算子2。交叉算子2的作用是將同一個(gè)調(diào)度方案中的子串進(jìn)行交叉。

步驟1：隨機(jī)選擇一個(gè)調(diào)度方案，記為tsi

步驟2：隨機(jī)生成一個(gè)整數(shù)i作為要交換的層數(shù)，在中找出屬于第i層的候選子任務(wù)。在這些候選子任務(wù)中隨機(jī)選擇兩個(gè)進(jìn)行交叉運(yùn)算。

2 變異運(yùn)算

變異操作的目的是在當(dāng)前的種群中加入新的個(gè)體，并且這個(gè)新的個(gè)體中大部分染色體繼承于父輩，而某些染色體是隨機(jī)產(chǎn)生的，并不繼承于它的父輩。變異操作決定了遺傳算法的局部搜索能力。這種操作可以向種群中加入新的特征，本文采用的變異運(yùn)算是將子任務(wù)從負(fù)載較大的處理機(jī)轉(zhuǎn)移到負(fù)載較小的處理機(jī)上，從而提高當(dāng)前個(gè)體的適應(yīng)度，有助于接近最優(yōu)解。操作步驟如下：

步驟1：隨機(jī)選擇某個(gè)個(gè)體。

步驟2：隨機(jī)生成一個(gè)整數(shù)i作為變異操作所在的層。

步驟3：對(duì)于所有包含該操作的所有處理機(jī)，計(jì)算各個(gè)處理機(jī)的負(fù)載，獲得最大負(fù)載處理機(jī) 和最小負(fù)載處理機(jī) 。

步驟4：在第i層，對(duì)最大負(fù)載處理機(jī)上的子任務(wù)進(jìn)行變異操作，將第i層的子任務(wù)在處理機(jī)子串上的處理機(jī)由Ci變?yōu)镃j

經(jīng)過上述的變異操作，增加了個(gè)體的適應(yīng)度，使解的搜索收斂速度加快。

算法偽代碼實(shí)現(xiàn)：

基于上文給出的各操作的具體描述給出算法的偽代碼實(shí)現(xiàn)如下：

輸入：種群規(guī)模N，交叉概率pc，變異概率pm，迭代次數(shù)Gene

輸出：最優(yōu)調(diào)度TS

實(shí)現(xiàn)：

Begin：

生成初始種群，獲得

//對(duì)種群中的每個(gè)個(gè)體計(jì)算它們的適應(yīng)度

for x ← 0 to N

{

//每臺(tái)處理機(jī)的當(dāng)前調(diào)度長度置零

for y ← 0 to m

for z ← 0 to p //對(duì)于ETL任務(wù)中所有的子任務(wù)循環(huán)

{

j ← 當(dāng)前子任務(wù)所在處理機(jī)序號(hào)；

//如果當(dāng)前子任務(wù)沒有前驅(qū)，即它是第一層

if

{

//子任務(wù)開始時(shí)間為處理機(jī) 的調(diào)度長度

startTime ← T（Cj）；

}

else

{

//當(dāng)前子任務(wù)有前驅(qū)的子任務(wù)

startTime ←T（Cj）；

}

//結(jié)束時(shí)間為開始時(shí)間加上子任務(wù)的時(shí)間

endTime ← startTime + O（z）；

//更新當(dāng)前子任務(wù)對(duì)應(yīng)的處理機(jī)的調(diào)度時(shí)間

T（Cj）← endTime；

}

}

do

{

//選擇操作，生成下一代調(diào)度

Selection（）；

//交叉操作，概率PC

Crossover（）；

//變異操作，概率Pm

Mutation（）；

//計(jì)算種群中所有調(diào)度的適應(yīng)度

Fitness（）；

}

While（count

ts ← max（） //獲得適應(yīng)度最高的調(diào)度作為最后的解

End