一種求解多處理機問題的混合蟻群算法

劉 洋,曾 錚

(信陽職業(yè)技術(shù)學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院,信陽 464000)

?

一種求解多處理機問題的混合蟻群算法

劉 洋,曾 錚

(信陽職業(yè)技術(shù)學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院,信陽 464000)

經(jīng)常用于各種最優(yōu)化處理過程的蟻群算法具有無法解決數(shù)據(jù)分類、動態(tài)請求、在線事務(wù)處理等一系列問題，嚴重時還可能發(fā)生停滯狀況.在分析蟻群參數(shù)、參數(shù)選擇、最優(yōu)調(diào)度等問題的基礎(chǔ)上，提出一種遺傳算子結(jié)合螞蟻任務(wù)分配模型的混合蟻群算法.仿真實驗表明，這種算法在求解多處理機問題時，能在較短的時間內(nèi)得到較優(yōu)的調(diào)度策略，且該算法具有良好的有效性和收斂性.

多處理機問題；蟻群算法；遺傳算子

0 前 言

目前，計算機逐漸走向智能化、網(wǎng)絡(luò)化的道路，在發(fā)展中便出現(xiàn)了并行分布式計算的難題.克服并行分布式計算的難題的關(guān)鍵需要妥善的處理分布式系統(tǒng)中的任務(wù)高度的問題.得出一種最優(yōu)的運算模式才能在規(guī)定的時間內(nèi)運算得出分布式系統(tǒng)的最優(yōu)調(diào)度.通常情況下我們應(yīng)用蟻群算法(ant colony optimization，ACO)運算最優(yōu)的運算模式，但是蟻群算法具有一定的缺陷性，它無法良好的處理數(shù)據(jù)挖掘的數(shù)據(jù)分類、動態(tài)請求、在線事務(wù)處理等等一系列問題，嚴重時可能引發(fā)停滯狀況.停滯狀況指的是當搜索進程開展到一定程度是所得到的結(jié)果不具有真實性，導(dǎo)致所有個體得到到的結(jié)果是同樣的.因此，本文提出了一種螞蟻任務(wù)分配模型結(jié)合遺傳算子改良的混合蟻群算法應(yīng)對多處理機問題的混合算法.

1 多處理機調(diào)度問題

多處理機調(diào)度問題(multiprocessor scheduling problem)的含義為：若有n臺一樣的處理機(p1，p2，…，pn)各不相關(guān)的對m個問題進行作業(yè)(j1，j2，…，jm)，其中的任何作業(yè)都不涉及其他處理機.若作業(yè)未完成也不允許中斷作業(yè)且不能劃分為更小的子作業(yè)，一項任務(wù)不能在不同的處理機中進行.同時，調(diào)度的任務(wù)是給出一種最優(yōu)的作業(yè)解決方式，使m個作業(yè)盡量在最短的時間內(nèi)由n臺一樣的處理機工作完成.多處理機調(diào)度則是在滿足優(yōu)先限制條件的基礎(chǔ)上最優(yōu)的作業(yè)解決方式發(fā)送至各個處理機上執(zhí)行，并盡量在最短的時間內(nèi)完成，則可假設(shè)：

①任何任務(wù)在開始后便無法中斷.

②每臺處理機僅僅能夠同時處理一項任務(wù).

③任務(wù)具有連續(xù)性.

④任務(wù)之間存在優(yōu)先約束，這決定了任務(wù)的執(zhí)行順序，杜絕循環(huán)優(yōu)先關(guān)系.

⑤一項任務(wù)不能在不同的處理機中進行，也就是設(shè)定每臺處理機僅能夠同時處理一項問題.

⑥全部的處理機的配置是相同的，則任何問題均可在任意處理機中進行，且理論上的處理時間是一致的.

處理機調(diào)度是離散優(yōu)化問題中的一種，而蟻群算法在求解問題上優(yōu)于離散優(yōu)化問題，則應(yīng)用蟻群算法求解處理機調(diào)度問題成為了可能.

2 蟻群算法數(shù)學(xué)模型及其多處理機調(diào)度過程

蟻群算法數(shù)學(xué)模型最早來源于螞蟻的群體智能，螞蟻經(jīng)常出現(xiàn)在我們的生活當中，在通常情況下，都是多個螞蟻協(xié)同作業(yè).在面對復(fù)雜、工程量巨大的問題時，螞蟻通過分配來降低問題的難度.因此，我們可將一臺處理機看成一只螞蟻，則得到了蟻群算法數(shù)學(xué)的初始模型.要應(yīng)用蟻群算法數(shù)學(xué)模型必須對處理機問題設(shè)置限定，也就是設(shè)定每臺處理機僅能夠同時處理一項問題，每臺處理機的配置是一致的；任何任務(wù)在開始后便無法中斷；任務(wù)具有連續(xù)性，任務(wù)之間存在優(yōu)先約束，這決定了任務(wù)的執(zhí)行順序，杜絕循環(huán)優(yōu)先關(guān)系，則任何問題均可在任意處理機中進行等等.

定義1：將一臺處理機看成一只螞蟻，每只螞蟻均具有它所代表的處理中的信息、屬性、儲存狀態(tài)等等信息，例如：過去的使用信息、當前的狀況、位置等等.

定義2：人工螞蟻也就是處理機當前的狀態(tài)

sti≤0即人工螞蟻也就是處理機pi當前代表空閑狀況，sti≥1即人工螞蟻pi代表忙碌狀況，同時statei為pi的預(yù)計處理時間.

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

通過網(wǎng)格Grid=[0..w(n)-1]×[0..h(n)-1]來表示人工螞蟻所能夠活動的空間，則它便成為全部格點(x，y)所構(gòu)成的二維數(shù)組，其中x∈[0..w(n)-1],y∈[0..h(n)-1],h(n)∈Z+所代表的是人工螞蟻個數(shù)n的函數(shù)值.

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

Aij代表處理機pi所得出的需求濃度為sj的jobj幾率，其中sj是jobj的需求強度值，需要用jobj來表示緊急需要的程序.

定義5：蟻群算法的數(shù)學(xué)模型

螞蟻模型任務(wù)包括五元組，也就是TAM=(Grid，State，n，m，DAG)，其中Grid的含義為二維網(wǎng)格，則：agent的活動范疇有限，其中state代表agent(處理機)的有限狀態(tài).m所代表的是任務(wù)的數(shù)量，n所代表的是處理機的數(shù)量，也等于agent的數(shù)量.因此，DAG所表示的是任務(wù)間關(guān)系，DAG圖G=J，E，Et.

則蟻群算法的多處理機的調(diào)度方法如下：

(1)將全部的人工螞蟻也即是處理機P隨機放入網(wǎng)格Grid中的格子內(nèi)，且將任務(wù)job隨機放置在Grid中的格子內(nèi)，從而計算每個人工螞蟻到每個任務(wù)job的d(pi,jobj)距離值.

(2)在系統(tǒng)時鐘的設(shè)定中，為了確定算法最后時段tmax.在(0，tmax)時段內(nèi)，人工螞蟻將不間斷的暈組任務(wù)序列.但完成所有任務(wù)后，算法將輸出該次人工螞蟻調(diào)度序列.并準備運行下一次的人工螞蟻調(diào)度.當時間至tmax后，在全部的輸出結(jié)果中，篩選出計算結(jié)果的最優(yōu)解.

3 加入遺傳算子的混合蟻群算法

螞蟻任務(wù)分配模型包括：處理數(shù)據(jù)挖掘的數(shù)據(jù)分類、數(shù)據(jù)分類聚類、動態(tài)請求、在線事務(wù)處理、規(guī)則發(fā)現(xiàn)等等.在蟻群算法中加入遺傳算子便可得出混合蟻群算法的雛形.

蟻群算法結(jié)合遺傳算子使之成為螞蟻任務(wù)分配模型，需要解決繁殖算子、變異算子、交叉算子方面的問題.首先，設(shè)每個處理器中的任務(wù)是以高度升序的方式進行排列的.不同的交叉點選取導(dǎo)致交叉點出現(xiàn)了不同的高度，且在交叉點最前面的最優(yōu)任務(wù)的高度是一直的，則剛生成的符號為有效符串號.

其中，任務(wù)Ji的高度為max(Height(Ji))+1和max(Height(Ji))-1中的任意隨機數(shù).在此可認為適應(yīng)值較高的有效符串號存活的幾率最高.在舊的群體中得到適應(yīng)值最高的有效符串號來構(gòu)成新的群體從而實現(xiàn)有效符串號自我繁殖.在隨機選擇兩個相同高度的問題進行變異運算.

由此可得到混合算法的實現(xiàn)關(guān)鍵代碼，其中部分代碼如下：

Begin

算法的初始化參數(shù)α,β,sj,θij,tmax的矩陣state，則矩陣R與網(wǎng)格G

…

while(not termination)

while t

t←t+1,state←state-1

運算得出的調(diào)度方案將以符串號的形式在Group中保存，從而計算Group中每個方案的適應(yīng)度范疇.

調(diào)用繁殖算法

令BESTTSIRING為Group中適應(yīng)值的最大有效符串號

for i=1to GroupNum/2do

在Group中得出兩個有效符串號并以概率P調(diào)用交叉操作；

if(則交叉操作發(fā)生)

將生成的有效符串號加入Temp；

else

將原符號串加入Temp；

end if

對Temp中的每個有效符串號，可通過概率q調(diào)用突變算法；

if(則突變算法出現(xiàn))

將新生成的有效符串號加入NewGroup

else

在原符號串加入NewGroup；

并用BESTSIRING帶圖Group中得出適應(yīng)度值最小的有效符串號

end if

end for

end while

output所有P的調(diào)度方式

end while

End

4 仿真實驗與分析

為驗證算法的有效性、收斂性，構(gòu)建了仿真環(huán)境進行實踐驗證.在分析中，遺傳算法中解的群體規(guī)模為10、雜交概率為pc=1.0、變異概率為pm=0.04.算法最多可延伸至1000代，其中，遷移概率為pmirgration=0.3、內(nèi)部雜交概率為pINCX=0.7.混合蟻群算法所包含的DAG圖是一項隨機生成的圖，每個節(jié)點中有1～4個后繼節(jié)點，運算的預(yù)計運行實踐為1～50之間的隨機數(shù)，演化策略的參數(shù)為μ/λ=4.

仿真實驗與分析的實驗數(shù)據(jù)為：設(shè)定3臺處理機、9項作業(yè)，則作業(yè)所需的運行時間分別為：79、 41、27、 6、62、96、54、73、18.文中采用基本蟻群算法、遺傳算法(Genetic Algorithm)以及本文算法，則0.8}Q=100)，經(jīng)過50次循環(huán)后得到結(jié)果，如表1所示，所得最優(yōu)解為P1(98，53)，P1(73，47，26，5)，P1(68，63，20)，完成時間為151.

表1 實驗結(jié)果比較

此外，還可通過Job-Shop中的常見問題MT10、MT06來進行比較，應(yīng)用遺傳算子的蟻群算法(IJSA)與一般蟻群算法(JSA)的效率比較.

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

從圖1中可見，通過混合蟻群算法可到出更優(yōu)化的解，混合蟻群算法在滿足優(yōu)先約束的條件下最大限制的保存下調(diào)度中任務(wù)的優(yōu)先順序排列，進而使最優(yōu)的計算結(jié)果能夠保存下來.在一般蟻群算法(JSA)中加入遺傳算法中的混合蟻群算法IJSA.混合蟻群算法IJSA與原算法JSA相比收斂性更快，且一般不會使運算陷入局部最優(yōu)解的狀況中.算法通過實驗實踐證實，混合蟻群算法能在較短的時間內(nèi)得到較優(yōu)的調(diào)度策略，且該算法具有良好的有效性、收斂性，可優(yōu)化全局性能.

5 結(jié)論

本文對傳統(tǒng)蟻群算法加以改進，提出了一種螞蟻任務(wù)分配模型結(jié)合遺傳算子改良的混合蟻群算法應(yīng)對多處理機問題的混合算法.在處理多處理機的任務(wù)調(diào)度問題中得到了良好的收效.但是，蟻群算法在處理機的任務(wù)調(diào)度問題中僅為初步嘗試.在改進和優(yōu)化螞蟻任務(wù)分配模型結(jié)合遺傳算子改良的混合蟻群算法而得出更好的時間性能以及測試時間不穩(wěn)定性、環(huán)境影響等問題仍需要業(yè)內(nèi)人士加以研究.

[1] 鄧 酩,謝曉蘭,程小輝.多處理機調(diào)度問題的蟻群優(yōu)化算法[J].桂林工學(xué)院學(xué)報,2013(2):329-332.

[2] 張 勇,張曦煌.改進型蟻群算法的多處理機任務(wù)調(diào)度研究[J].計算機工程與應(yīng)用,2007,43(35):74-76.

[3] 陳 晶,劉加中.一種求解多處理機調(diào)度問題的自適應(yīng)蟻群算法[J].聊城大學(xué)學(xué)報(自然科學(xué)版),2009,22(4):86-89.

[4] 段傳林,謝偉鐸.一種混合粒子群與蟻群算法在多處理機調(diào)度中的應(yīng)用研究[J].計算機時代,2008(9).

[5] 孫 凱,吳紅星,王 浩,丁家棟.蟻群與粒子群混合算法求解TSP問題[J].計算機工程與應(yīng)用,2012,48(34):60-63.

[6] 管顯筍,石偉鉑,鄧成玉,劉永山.基于粒子群優(yōu)化和禁忌搜索的混合調(diào)度算法[J].計算機應(yīng)用與軟件,2011,28(5).

[7] SU Rina,WANG Yu.Research of Grid Task Schedule Based on Quantum Ant Colony Algorithm[J].Computer Engineering and Applications,2011,47(12):46-48.

[8] XIAO Hong-feng,TAN Guan-zheng.Study on Fusing Genetic Algorithm into Ant Colony Algorithm[J].Mini-micro Systems,2009,30(3).

Research on a Hybrid Ant Colony Algorithm Solving the Multiprocessor Problem

LIU Yang，ZENG Zheng

(College ofmathematics and Computer Science,Xinyang Vocational and Technical College,Xinyang 464000,China)

The ant colony algorithm commonly used in the optimization process has a series of problems.It is unable to solve data classification,dynamic request and no-online transaction processing.Sometimes,it turns out to be stagnant.Based on the analysis of ant colony algorithm parameters,this paper parameter selection and optimal scheduling,presents an ant colony algorithm combining genetic operators with the ant task allocationmodel.The simulation experiment shows that this algorithm can get a better scheduling strategy in a relatively short period of time when solvingmultiprocessor problems,and it has good effectiveness and convergence.

multiprocessor problem; Hybrid ant colony algorithm; genetic operator

2015-11-05作者簡介：劉 洋(1975-)，男，碩士，講師，研究方向：高等數(shù)學(xué)、計算數(shù)學(xué).

TP391.41

A

1671-119X(2016)02-0037-04