方加娟，黃春華

（鄭州職業(yè)技術(shù)學(xué)院，鄭州 450121）

一種解決多處理機(jī)問(wèn)題的混合算法的研究

方加娟，黃春華

（鄭州職業(yè)技術(shù)學(xué)院，鄭州 450121）

0 引言

今天計(jì)算機(jī)都向并行化、網(wǎng)絡(luò)化、智能化進(jìn)軍，但隨之而來(lái)的是并行分布式計(jì)算這一道難題。要解決并行分布式計(jì)算，就要合理地解決分布式系統(tǒng)中的任務(wù)高度問(wèn)題。要在有限時(shí)間內(nèi)求得分布式系統(tǒng)中的最優(yōu)化調(diào)度，就要尋找到一種解決最優(yōu)化的算法。過(guò)去都是采用蟻群算法，但蟻群算法有不能很好處理動(dòng)態(tài)請(qǐng)求、數(shù)據(jù)挖掘中的數(shù)據(jù)分類(lèi)聚類(lèi)、規(guī)則發(fā)現(xiàn)、在線(xiàn)事務(wù)處理等問(wèn)題，甚至還會(huì)出現(xiàn)停滯現(xiàn)象，所謂的停滯現(xiàn)象就是說(shuō)當(dāng)搜索到一定程度時(shí)，得出的結(jié)果是不真實(shí)的，所有個(gè)體所得到的結(jié)果是完全一致的。本文在析螞蟻任務(wù)分配模型的基礎(chǔ)上，提出加入遺傳算子對(duì)其模型進(jìn)行改良，提出一種解決多處理機(jī)問(wèn)題的混合算法的解決機(jī)制。

1 螞蟻任務(wù)分配模型

螞蟻任務(wù)分配模型來(lái)源于螞蟻的群體智能，在日常生活中，我們會(huì)發(fā)現(xiàn)多個(gè)單一的螞蟻經(jīng)常會(huì)通過(guò)協(xié)同作用來(lái)解決比較復(fù)雜的問(wèn)題，他們通過(guò)分配任務(wù)來(lái)完成不同的任務(wù)來(lái)解決復(fù)雜的問(wèn)題。我們假想處理機(jī)就是一只螞蟻。要設(shè)計(jì)出螞蟻任務(wù)分配模型，先要對(duì)處理機(jī)問(wèn)題作些約定。即假設(shè)：每臺(tái)處理機(jī)同時(shí)只能處理一個(gè)任務(wù)，每個(gè)處理機(jī)是相同的；任務(wù)是連續(xù)的，存在優(yōu)先約束；一個(gè)任務(wù)不能同時(shí)在不同的處理機(jī)上進(jìn)行處理等等。

定義1：一個(gè)螞蟻代表一個(gè)處理機(jī)，每個(gè)螞蟻包含有它所代表的處理機(jī)的所有屬性和信息，還可能包含它自身的一些信息，如當(dāng)前的位置、當(dāng)前的狀態(tài)、少量的過(guò)去信息的記憶等。

定義2：人工螞蟻（處理機(jī)）的狀態(tài)

sti≤0表示處理機(jī)Pi當(dāng)前是空閑，sti≥1表示處理機(jī)Pi當(dāng)前忙碌，且此時(shí)statei為Pi的處理時(shí)間。

定義3：人工螞蟻的活動(dòng)空間

用網(wǎng)格Grid＝[0.. w (n)－1]×[0.. h (n)－1]表示人工螞蟻的活動(dòng)空間，它是所有格點(diǎn)(x，y)構(gòu)成的二維數(shù)組，其中x∈[0.. w (n)－1]，y∈[0..h (n)－1]，h (n)∈Z+是關(guān)于人工螞蟻個(gè)數(shù)n的函數(shù)。

定義4：調(diào)度選擇概率

Aij表示處理機(jī)Pi響應(yīng)需求濃度為Sj的jobj的概率，Sj是jobj的需求強(qiáng)度值，用來(lái)表示jobj的需求迫切程序。

定義5：螞蟻任務(wù)分配模型

螞蟻模型任務(wù)分配用一個(gè)五元組來(lái)表示，即TAM＝(Grid, State, n, m, DAG)。這里Grid代表二維網(wǎng)格，即agent所在的活動(dòng)空間；State表示agent(即處理機(jī))的有限狀態(tài)集；m表示任務(wù)的個(gè)數(shù)，n為處理機(jī)的個(gè)數(shù)，也是agent的個(gè)數(shù)；DAG為表示任務(wù)間關(guān)系的DAG圖G ＝J, E, Et。

基于螞蟻任務(wù)分配模型的多處理機(jī)的調(diào)度過(guò)程如下：

1）將所有的處理機(jī)P（即人工螞蟻）隨機(jī)放置到網(wǎng)格Grid的某些格子中，同時(shí)將任務(wù)job隨機(jī)放置到網(wǎng)格Grid的某些格子中。計(jì)算每個(gè)處理機(jī)P到每個(gè)任務(wù)job的之間的距離d (Pi，jobj)。

2）設(shè)置系統(tǒng)時(shí)鐘，確定算法結(jié)束時(shí)間tnax。在(0, tnax)時(shí)間內(nèi)，處理機(jī)將循環(huán)處理任務(wù)序列。但是，當(dāng)任務(wù)序列處理完成后，算法輸出這次的處理機(jī)調(diào)度序列，同時(shí)開(kāi)始下一輪的處理機(jī)調(diào)度。在時(shí)間到達(dá)tnax后，在眾多的輸出結(jié)果中，選擇出最優(yōu)解。

2 混合蟻群算法

螞蟻任務(wù)分配模型中存在著處理動(dòng)態(tài)請(qǐng)求、數(shù)據(jù)挖掘中的數(shù)據(jù)分類(lèi)聚類(lèi)、規(guī)則發(fā)現(xiàn)、在線(xiàn)事務(wù)處理等問(wèn)題，我們?cè)谙伻核惴ㄖ屑尤脒z傳算子，設(shè)計(jì)了混合蟻群算法。

要將遺傳算子加到螞蟻任務(wù)分配模型中去，我們就要解決交叉算子、繁殖算子。變異算子的問(wèn)題。我們先假設(shè)在調(diào)度中每個(gè)處理器上的任務(wù)是按高度升序進(jìn)行的。如果交叉點(diǎn)的選取使得每個(gè)交叉點(diǎn)兩側(cè)任務(wù)的高度不一樣，并且交叉點(diǎn)前面最優(yōu)任務(wù)的高度而是一樣，那新生成的符號(hào)串有效。任務(wù)Ji的高度為max (Heignt (Ji))＋1和max (Heignt (Ji))－1之間的一個(gè)隨機(jī)數(shù)。我們認(rèn)為具有較高適應(yīng)度值的符號(hào)串應(yīng)有更多的機(jī)會(huì)存活下來(lái)，通過(guò)從舊的群體中選取較高適應(yīng)度值最大的符號(hào)串來(lái)構(gòu)成新的群體，進(jìn)爾實(shí)現(xiàn)繁殖。由隨機(jī)交換兩個(gè)高度相同的任務(wù)來(lái)實(shí)現(xiàn)變異。

混合算法的實(shí)現(xiàn)部分關(guān)鍵代碼如下：

3 實(shí)驗(yàn)結(jié)果與分析

我們最主要是將混合蟻群算法與遺傳算法在搜索能力方面進(jìn)行比較分析。

為了研究需要我們對(duì)兩種算法中的部分參數(shù)進(jìn)行假設(shè)。遺傳算法中解的群體規(guī)模為10，雜交和變異概率分別為pc＝1.0和pm＝0.04，算法的最多迭代代數(shù)1000代，內(nèi)部雜交概率為pINCX＝0.7，遷移概率為pmirgration＝0.3。而混合蟻群算法中的DAG圖是隨機(jī)生成的，每個(gè)節(jié)點(diǎn)有1-4個(gè)后繼，估計(jì)運(yùn)行時(shí)間為1-50的隨機(jī)數(shù)，演化策略中的參數(shù)為 /＝4。各處理機(jī)之間數(shù)據(jù)傳輸延時(shí)也是隨機(jī)生成的。當(dāng)算法能收斂到全局最優(yōu)解時(shí)，運(yùn)行時(shí)間通常在2s以?xún)?nèi)，當(dāng)算法不能收斂到全局最優(yōu)解時(shí)，就會(huì)一直進(jìn)化到預(yù)先設(shè)置最多迭代代數(shù)，所用的時(shí)間用minmaxtime來(lái)表示。

我們通過(guò)比較遺傳算法和混合蟻群算法在處理機(jī)數(shù)為2，任務(wù)數(shù)為20個(gè)的情況下和處理機(jī)數(shù)為3，任務(wù)數(shù)為20的情況下的靜太性能曲線(xiàn)。通過(guò)比較我們會(huì)發(fā)現(xiàn)混合蟻群算法會(huì)更快更好地逼近最優(yōu)值，更容易找到最佳方案，而且有一定的穩(wěn)定性。我們認(rèn)為混合蟻群算法更適合解決多處理機(jī)問(wèn)題。圖中的橫坐標(biāo)X表示進(jìn)化代數(shù)，縱坐標(biāo)Y表示任務(wù)完成時(shí)間。從圖中可以看出混合蟻群算法更快地逼近最優(yōu)解，而且穩(wěn)定性也更好。

圖1 算法的靜態(tài)性能曲線(xiàn)（m＝2，n＝20）

另外，我們還利用Job-Shop中的常見(jiàn)問(wèn)題

圖2 算法的靜態(tài)性能曲線(xiàn)（m＝3，n＝20）

MT06和MT10來(lái)比較引入遺傳算子(IJSA入遺傳算子(JSA)的基于TAM的蟻群算法的效率。

圖3 兩種蟻群算法的minmaxtime比較

從圖3要可以得到，混合蟻群算法能找到更好的解，該算法不僅使優(yōu)先約束的要求得到滿(mǎn)足，而且可以最大限度的保留原有調(diào)度中的任務(wù)優(yōu)先順序，從而使優(yōu)良的計(jì)算結(jié)果得以保存。在算法JSA中添加遺傳算法中的混合蟻群算法IJSA相對(duì)于原算法JSA可以更快的收斂，且不容易陷入局部最優(yōu)解。

螞蟻在網(wǎng)格中動(dòng)態(tài)地響應(yīng)任務(wù)、處理任務(wù)。而任務(wù)也可以有一個(gè)產(chǎn)生、處理、完成的動(dòng)態(tài)過(guò)程。因此，混合算法任務(wù)分配模型完全可以用到動(dòng)態(tài)任務(wù)調(diào)度中，模型可以通過(guò)一定的機(jī)制將動(dòng)態(tài)調(diào)度中不斷出現(xiàn)的任務(wù)依次放入網(wǎng)格中，根據(jù)任務(wù)的屬性不同，賦予不同的響應(yīng)度，就可以實(shí)現(xiàn)動(dòng)態(tài)調(diào)度，改進(jìn)后算法的靈活性和健壯性提高了很多。

[1]張擁軍, 張怡, 彭宇行, 陳福接.一種基于多處理機(jī)的容錯(cuò)實(shí)時(shí)任務(wù)調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展, 2000, 37(4):425-429.

[2]俊奇. 基于多處理機(jī)系統(tǒng)的最短路徑并行算法的高效實(shí)現(xiàn)[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2009, 18(10): 76-80.

[3]單汨源, 張冠群, 晏敏, 吳娟. 一種求解多模式資源受限項(xiàng)目調(diào)度問(wèn)題的新方法[J]. 科技管理研究, 2009(6).

The research of an hybrid algorithm in task scheduling problems

FANG Jia-juan, HUANG Chun-hua

并行處理在各行各業(yè)的發(fā)展非常迅速，而要解決并行處理過(guò)程中的調(diào)度問(wèn)題不是件容易的事，最近幾年越來(lái)越多的研究生加入到這個(gè)隊(duì)伍中來(lái)，并加以研究。本文提出一種加入遺傳算子的混合蟻群算來(lái)解決多處理機(jī)問(wèn)題，避免了傳統(tǒng)的螞蟻任務(wù)分配模型的缺點(diǎn)。

多處理機(jī)；螞蟻任務(wù)分配模型（TAM）；遺傳算法

方加娟（1975－），女，河南鄭州人，講師，研究方向?yàn)橛?jì)算機(jī)技術(shù)及應(yīng)用。

TP391

A

1009-0134(2011)4(下)-0140-03

10.3969/j.issn.1009-0134.2011.4(下).41

2010-12-15