劉 洋,曾 錚

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

?

一種求解多處理機(jī)問(wèn)題的混合蟻群算法

劉 洋,曾 錚

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

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

多處理機(jī)問(wèn)題；蟻群算法；遺傳算子

0 前 言

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

1 多處理機(jī)調(diào)度問(wèn)題

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

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

②每臺(tái)處理機(jī)僅僅能夠同時(shí)處理一項(xiàng)任務(wù).

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

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

⑤一項(xiàng)任務(wù)不能在不同的處理機(jī)中進(jìn)行，也就是設(shè)定每臺(tái)處理機(jī)僅能夠同時(shí)處理一項(xiàng)問(wèn)題.

⑥全部的處理機(jī)的配置是相同的，則任何問(wèn)題均可在任意處理機(jī)中進(jìn)行，且理論上的處理時(shí)間是一致的.

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

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

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

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

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

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

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

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

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

Aij代表處理機(jī)pi所得出的需求濃度為sj的jobj幾率，其中sj是jobj的需求強(qiáng)度值，需要用jobj來(lái)表示緊急需要的程序.

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

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

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

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

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

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

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

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

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

由此可得到混合算法的實(shí)現(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

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

調(diào)用繁殖算法

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

for i=1to GroupNum/2do

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

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

將生成的有效符串號(hào)加入Temp；

else

將原符號(hào)串加入Temp；

end if

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

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

將新生成的有效符串號(hào)加入NewGroup

else

在原符號(hào)串加入NewGroup；

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

end if

end for

end while

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

end while

End

4 仿真實(shí)驗(yàn)與分析

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

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

表1 實(shí)驗(yàn)結(jié)果比較

此外，還可通過(guò)Job-Shop中的常見(jiàn)問(wèn)題MT10、MT06來(lái)進(jìn)行比較，應(yīng)用遺傳算子的蟻群算法(IJSA)與一般蟻群算法(JSA)的效率比較.

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

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

5 結(jié)論

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

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

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

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

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

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

[6] 管顯筍,石偉鉑,鄧成玉,劉永山.基于粒子群優(yōu)化和禁忌搜索的混合調(diào)度算法[J].計(jì)算機(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作者簡(jiǎn)介：劉 洋(1975-)，男，碩士，講師，研究方向：高等數(shù)學(xué)、計(jì)算數(shù)學(xué).

TP391.41

A

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