一種解決多處理機問題的混合算法的研究

方加娟，黃春華

（鄭州職業技術學院，鄭州 450121）

一種解決多處理機問題的混合算法的研究

方加娟，黃春華

（鄭州職業技術學院，鄭州 450121）

0 引言

今天計算機都向并行化、網絡化、智能化進軍，但隨之而來的是并行分布式計算這一道難題。要解決并行分布式計算，就要合理地解決分布式系統中的任務高度問題。要在有限時間內求得分布式系統中的最優化調度，就要尋找到一種解決最優化的算法。過去都是采用蟻群算法，但蟻群算法有不能很好處理動態請求、數據挖掘中的數據分類聚類、規則發現、在線事務處理等問題，甚至還會出現停滯現象，所謂的停滯現象就是說當搜索到一定程度時，得出的結果是不真實的，所有個體所得到的結果是完全一致的。本文在析螞蟻任務分配模型的基礎上，提出加入遺傳算子對其模型進行改良，提出一種解決多處理機問題的混合算法的解決機制。

1 螞蟻任務分配模型

螞蟻任務分配模型來源于螞蟻的群體智能，在日常生活中，我們會發現多個單一的螞蟻經常會通過協同作用來解決比較復雜的問題，他們通過分配任務來完成不同的任務來解決復雜的問題。我們假想處理機就是一只螞蟻。要設計出螞蟻任務分配模型，先要對處理機問題作些約定。即假設：每臺處理機同時只能處理一個任務，每個處理機是相同的；任務是連續的，存在優先約束；一個任務不能同時在不同的處理機上進行處理等等。

定義1：一個螞蟻代表一個處理機，每個螞蟻包含有它所代表的處理機的所有屬性和信息，還可能包含它自身的一些信息，如當前的位置、當前的狀態、少量的過去信息的記憶等。

定義2：人工螞蟻（處理機）的狀態

sti≤0表示處理機Pi當前是空閑，sti≥1表示處理機Pi當前忙碌，且此時statei為Pi的處理時間。

定義3：人工螞蟻的活動空間

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

定義4：調度選擇概率

Aij表示處理機Pi響應需求濃度為Sj的jobj的概率，Sj是jobj的需求強度值，用來表示jobj的需求迫切程序。

定義5：螞蟻任務分配模型

螞蟻模型任務分配用一個五元組來表示，即TAM＝(Grid, State, n, m, DAG)。這里Grid代表二維網格，即agent所在的活動空間；State表示agent(即處理機)的有限狀態集；m表示任務的個數，n為處理機的個數，也是agent的個數；DAG為表示任務間關系的DAG圖G ＝J, E, Et。

基于螞蟻任務分配模型的多處理機的調度過程如下：

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

2）設置系統時鐘，確定算法結束時間tnax。在(0, tnax)時間內，處理機將循環處理任務序列。但是，當任務序列處理完成后，算法輸出這次的處理機調度序列，同時開始下一輪的處理機調度。在時間到達tnax后，在眾多的輸出結果中，選擇出最優解。

2 混合蟻群算法

螞蟻任務分配模型中存在著處理動態請求、數據挖掘中的數據分類聚類、規則發現、在線事務處理等問題，我們在蟻群算法中加入遺傳算子，設計了混合蟻群算法。

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

混合算法的實現部分關鍵代碼如下：

3 實驗結果與分析

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

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

我們通過比較遺傳算法和混合蟻群算法在處理機數為2，任務數為20個的情況下和處理機數為3，任務數為20的情況下的靜太性能曲線。通過比較我們會發現混合蟻群算法會更快更好地逼近最優值，更容易找到最佳方案，而且有一定的穩定性。我們認為混合蟻群算法更適合解決多處理機問題。圖中的橫坐標X表示進化代數，縱坐標Y表示任務完成時間。從圖中可以看出混合蟻群算法更快地逼近最優解，而且穩定性也更好。

圖1 算法的靜態性能曲線（m＝2，n＝20）

另外，我們還利用Job-Shop中的常見問題

圖2 算法的靜態性能曲線（m＝3，n＝20）

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

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

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

螞蟻在網格中動態地響應任務、處理任務。而任務也可以有一個產生、處理、完成的動態過程。因此，混合算法任務分配模型完全可以用到動態任務調度中，模型可以通過一定的機制將動態調度中不斷出現的任務依次放入網格中，根據任務的屬性不同，賦予不同的響應度，就可以實現動態調度，改進后算法的靈活性和健壯性提高了很多。

[1]張擁軍, 張怡, 彭宇行, 陳福接.一種基于多處理機的容錯實時任務調度算法[J].計算機研究與發展, 2000, 37(4):425-429.

[2]俊奇. 基于多處理機系統的最短路徑并行算法的高效實現[J]. 計算機系統應用, 2009, 18(10): 76-80.

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

The research of an hybrid algorithm in task scheduling problems

FANG Jia-juan, HUANG Chun-hua

并行處理在各行各業的發展非常迅速，而要解決并行處理過程中的調度問題不是件容易的事，最近幾年越來越多的研究生加入到這個隊伍中來，并加以研究。本文提出一種加入遺傳算子的混合蟻群算來解決多處理機問題，避免了傳統的螞蟻任務分配模型的缺點。

多處理機；螞蟻任務分配模型（TAM）；遺傳算法

方加娟（1975－），女，河南鄭州人，講師，研究方向為計算機技術及應用。

TP391

A

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

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

2010-12-15