求解并行測試任務(wù)調(diào)度問題的ACIA

李文海，管　晗

(海軍航空大學(xué)　a.科研部；b.研究生管理大隊， 山東 煙臺　264001)

并行測試與傳統(tǒng)串行測試相比，提高了資源利用率，節(jié)約了測試時間。但是其任務(wù)調(diào)度是個復(fù)雜、難以優(yōu)化的NP難題[1]。

國內(nèi)外眾多專家學(xué)者都研究了并行測試的任務(wù)調(diào)度問題。文獻(xiàn)[1]對并行測試技術(shù)進(jìn)行了綜述；文獻(xiàn)[2]提出基于Petri網(wǎng)的并行測試系統(tǒng)建模過程；文獻(xiàn)[3-5]分別運(yùn)用TaskScheduler-T算法、改進(jìn)粒子群算法(IPSO)以及混合遺傳算法，建立了并行測試模型，在任務(wù)調(diào)度問題上取得了一定的成果。

為進(jìn)一步提高系統(tǒng)測試資源利用率和測試效率，本文提出了一種自適應(yīng)混沌免疫算法(Adaptive Chaos Immune Algorithm，ACIA)，即利用混沌優(yōu)化理論的遍歷性、隨機(jī)性等優(yōu)勢，將混沌優(yōu)化理論引入人工免疫算法，形成改進(jìn)的新算法。并將改進(jìn)的算法應(yīng)用于求解并行測試任務(wù)調(diào)度的問題中。

1　混沌優(yōu)化理論

混沌是指在確定系統(tǒng)中出現(xiàn)的一種貌似無規(guī)則，類似隨機(jī)的現(xiàn)象，是存在于非線性系統(tǒng)中的一種較為普遍的現(xiàn)象。混沌并不是一片混亂，而是有著精致內(nèi)在結(jié)構(gòu)的一類現(xiàn)象?；煦缡欠蔷€性動力學(xué)系統(tǒng)在一定條件下所表現(xiàn)的一種運(yùn)動形式，是系統(tǒng)處于非平衡過程中所呈現(xiàn)的隨機(jī)行為[6]。混沌的主要特征有：非線性、對初始條件敏感的依賴性、長期行為的不可預(yù)測性、不可分解性、穩(wěn)定性和不穩(wěn)定性、具有規(guī)律性成分、遍歷性、分形性[7]。

設(shè)連續(xù)自映射f:I→I?R，I是R中的一個子區(qū)間。如果存在不可數(shù)集合S?I滿足：

1)S不包含周期點(diǎn)；

2) 任給X1,X2∈SX1≠X2，有

混沌映射是混沌優(yōu)化理論中重要的一部分，通過混沌映射公式可以產(chǎn)生一系列處于混沌狀態(tài)的值和值空間。一般采用Logistic映射，其計算公式為

xn+1=μxn1-xn

(1)

其中，xn∈0,1，μ∈0,4為混沌控制變量。根據(jù)文獻(xiàn)[9]，當(dāng)μ=4時，xn的取值遍布0,1，達(dá)到最佳混沌效果，因此使用Logistic映射時，一般取μ=4。

2　自適應(yīng)混沌免疫算法

免疫克隆選擇算法(Immune Clonal Selection Algorithm，ICSA)是人工免疫算法的核心算法之一，是模擬自然免疫系統(tǒng)功能的一種新的智能方法，具有學(xué)習(xí)記憶功能[10-11]，該算法具有全局搜索能力強(qiáng)、收斂速度快和魯棒性強(qiáng)等優(yōu)點(diǎn)。其算法的基本流程如圖1所示。

由于免疫算法在搜索過程中易出現(xiàn)早熟、易陷入局部最優(yōu)和尋優(yōu)結(jié)果不穩(wěn)定的特點(diǎn)，本研究結(jié)合混沌優(yōu)化的隨機(jī)性，遍歷性和對初始條件的敏感性等優(yōu)點(diǎn)，提出一種自適應(yīng)混沌免疫算法(ACIA)。

2.1　算法步驟

自適應(yīng)混沌免疫算法的步驟如下：

步驟1混沌初始化種群，生成抗體數(shù)量為N的初始抗體群體P；

步驟2根據(jù)親和度函數(shù)，計算各抗體的親和度，挑選出親和度高的前N1個最優(yōu)抗體，構(gòu)成克隆體種群B；

步驟3對克隆體種群B進(jìn)行自適應(yīng)克隆(復(fù)制)操作，得到新的抗體種群C；

步驟4對克隆體種群C進(jìn)行基于混沌擾動的變異操作，得到抗體種群D，然后加入抗體種群；

步驟5對抗體種群D進(jìn)行濃度調(diào)節(jié)操作，得到抗體種群E；

步驟6將抗體種群E中親和度最高的抗體加入記憶群體集合中；用記憶群體集合中的高親和度個體代替抗體集合中低親和度的抗體，更新抗體群體集合；

步驟7返回步驟2進(jìn)行迭代，直到滿足停止條件，迭代結(jié)束，輸出結(jié)果。

圖1免疫克隆選擇算法流程

2.2　ACIA求解并行測試任務(wù)調(diào)度問題

在并行測試任務(wù)調(diào)度問題中，調(diào)度的目標(biāo)函數(shù)即測試總時間，對應(yīng)于算法中的抗原；調(diào)度的候選序列對應(yīng)于抗體；候選序列相對于目標(biāo)函數(shù)的質(zhì)量對應(yīng)于抗原和抗體的親和度。

算法的改進(jìn)主要在混沌初始化、基于混沌擾動的變異和濃度調(diào)節(jié)操作。改進(jìn)后的算法具體步驟如下：

1) 混沌初始化

(2)

其中，randperm*為隨機(jī)排列函數(shù)。

(3)

d) 將混沌序列轉(zhuǎn)化為免疫算法初始化基因。利用式(3)做逆變換為

(4)

得到自適應(yīng)混沌免疫算法的初始種群

(5)

2) 目標(biāo)函數(shù)和親和度

目標(biāo)函數(shù)MakeP為測試時間，即變遷序列的時延總和。測試的最優(yōu)序列即為測試時間最短的序列，得到任務(wù)調(diào)度最優(yōu)方案的算法的基本思想如下：

a) 每個序列從第一個元素開始，找出能與之連續(xù)并行的選項，以括號標(biāo)記，遇到不能并行的停止；然后以括號截止前一個元素開始，繼續(xù)判斷與后面元素是否并行，直到序列結(jié)束。

b) 若沒有并行關(guān)系，則能確定前一個元素時間。

c) 若存在并行關(guān)系，則比較括號開始前一個元素時間與括號中所有元素時間和的大小。

① 括號開始前一個元素時間大：前一個元素時間不變，括號中所有元素時間置為0；

② 括號中所有元素時間和大：前一個元素時間不變，從括號開始到括號結(jié)束元素前一位元素時間置為0；括號結(jié)束元素時間為括號開始前一個元素時間與括號中所有元素時間和的差值的絕對值。

親和度反映了變遷序列的質(zhì)量，由目標(biāo)函數(shù)的某種變換表示。假設(shè)某測試系統(tǒng)串行測試的總時間為T，所以構(gòu)造第i個測試序列的親和度函數(shù)定義為

Aff1,i=T-MakeP1,i

(6)

3) 自適應(yīng)克隆操作

將抗體種群P中的抗體根據(jù)親和度大小進(jìn)行降序排序，得到親和度較高的前N1個抗體，構(gòu)成克隆體種群B；克隆體數(shù)量N1=Pa×N，其中Pa為克隆選擇概率，N為初始抗體數(shù)；再對克隆體種群B進(jìn)行克隆，克隆數(shù)目MM定義為

(7)

其中，Mn(i)為每個抗體需要克隆的抗體數(shù)，定義為

(8)

其中：M為細(xì)胞克隆數(shù)；Mn(i)可根據(jù)該抗體的親和度自適應(yīng)調(diào)整；Int*為上取整函數(shù)?？寺∵^后，得到新的抗體種群C。

4) 基于混沌擾動的變異操作

變異操作采用位交換方法。首先采用混沌映射公式(1)隨機(jī)生成兩個混沌變量；然后通過變異率決定是否變異，如果變異概率小于變異閾值Pz，則將兩個變量映射到抗體編碼的具體位置上，然后對這兩個編碼進(jìn)行交換，則實(shí)現(xiàn)了抗體的變異。變異結(jié)束后抗體種群D取代種群C，進(jìn)入下一步循環(huán)。

5) 濃度調(diào)節(jié)操作

利用濃度調(diào)節(jié)機(jī)制，實(shí)現(xiàn)抗體間促進(jìn)和抑制的相互關(guān)系。第i個抗體的選擇概率為

Pci=αPAffi+1-αPNongi

(9)

其中：α為常數(shù)調(diào)節(jié)因子；PAffi為親和度概率；PNongi為濃度抑制概率

(10)

(11)

其中：β為常數(shù)調(diào)節(jié)因子；Nong(1,i)為第i個抗體濃度

(12)

其中：Ayy1,i為第i個抗體與本次迭代種群最優(yōu)個體的相似度；Py為濃度抑制半徑。

(13)

其中，Pij為第i個符號出現(xiàn)在第j個基因座上的概率，定義為

(14)

根據(jù)式(9)可知，第i個抗體的選擇概率與該抗體的親和度成正比，與該抗體的濃度成反比。通過該式的濃度調(diào)節(jié)，既能保留親和度高的抗體，又能抑制高親和度、高濃度的抗體，保障了抗體種群的多樣性。

6) 停止條件

設(shè)置算法的停止條件為迭代次數(shù)達(dá)到閾值或者測試序列時間多次迭代保持不變。

3　實(shí)驗(yàn)仿真

以兩臺某型雷達(dá)接收機(jī)的并行測試系統(tǒng)為例。雷達(dá)測試系統(tǒng)的資源集R={r1,r2,r3,r4,r5,r6,r7}，其中r1為掃頻信號源，r2為標(biāo)量網(wǎng)絡(luò)分析儀，r3為頻譜儀，r4為示波器，r5為程控直流電源，r6為矢量網(wǎng)絡(luò)分析儀，r7為功率計。雷達(dá)接收機(jī)的各個待測參數(shù)就是各個測試任務(wù)，表1給出了雷達(dá)測試系統(tǒng)的測試任務(wù)資源集。待測參數(shù)即各項測試任務(wù)，測試時間即完成某待測參數(shù)測試所需的時間，單位為秒。

表1　雷達(dá)接收機(jī)測試任務(wù)資源集

表1中任務(wù)t1-1,t1-2,t1-3都占用資源r1,r2，可合并為一個任務(wù)，記作t1。同理，可將任務(wù)t2-1,t2-2合并為一個任務(wù)，記作t2。由此可得，雷達(dá)接收機(jī)測試任務(wù)與測試資源的關(guān)系為：t1〈r1,r2〉，t2〈r1,r3〉，t3〈r4〉，t4〈r1,r4〉，t5〈r3,r5〉，t6〈r1,r6〉，t7〈r7〉，t8〈r3〉。

以完成兩臺雷達(dá)接收機(jī)所有測試任務(wù)所需測試時間最短的測試序列為最優(yōu)的任務(wù)調(diào)度目標(biāo)，建立并行測試模型。算法參數(shù)設(shè)置為初始抗體數(shù)N=100，迭代閾值IerativeTime=100，串行測試總時間T=202 s，克隆選擇概率Pa=0.7，細(xì)胞克隆數(shù)M=200，變異概率Pz=0.6，濃度抑制半徑Py=0.7。假設(shè)各個測試任務(wù)是相互獨(dú)立的，沒有順序約束。

將自適應(yīng)混沌免疫算法與文獻(xiàn)[3]中的TaskScheduler-T算法和未改進(jìn)的人工免疫算法(ICSA)進(jìn)行比較，得到比較結(jié)果如表2與圖3所示。

表2　各算法資源利用率與測試總時間比較

從表2可以看出，與TaskScheduler-T算法相比，ICSA和ACIA完成測試的總時間減少了32 s，即測試效率提高了24.06%，測試資源的平均利用率提高了9.80%。

由MATLAB仿真得到ICSA和ACIA測試總時間與迭代次數(shù)的關(guān)系對比如圖3所示。

從圖3可以看出，由于ACIA在初始化階段加入了混沌優(yōu)化，與ICSA相比，迭代初期搜索范圍較大，得到的測試序列更具有遍歷性、隨機(jī)性；兩種算法在迭代初期的收斂性都不錯，但隨著迭代次數(shù)的增加，ICSA搜索能力變?nèi)?，且易陷入局部最?yōu)。而ACIA由于添加了混沌擾動，能夠不斷收斂，提高了其種群多樣性；最終，ACIA經(jīng)過14次迭代找到測試時間最短的最優(yōu)序列，而ICSA經(jīng)過21次迭代才找到最優(yōu)序列。因此，ACIA比ICSA的程序執(zhí)行時間大大減少，測試效率大大提高。

綜上所述，自適應(yīng)混沌免疫算法的執(zhí)行時間更短，效率更高，性能更優(yōu)。

4　結(jié)論

本文基于人工免疫算法，結(jié)合混沌優(yōu)化理論能夠克服免疫算法易早熟、易陷入局部最優(yōu)的缺陷，并針對并行測試任務(wù)調(diào)度問題進(jìn)行優(yōu)化。在人工免疫算法初始化階段進(jìn)行混沌優(yōu)化；克隆操作中運(yùn)用與親和度相關(guān)的自適應(yīng)克隆算子；變異操作中添加混沌擾動；并添加濃度調(diào)節(jié)操作。仿真實(shí)驗(yàn)表明，該算法能夠較快地得到任務(wù)調(diào)度最優(yōu)序列，較好地解決并行測試任務(wù)調(diào)度復(fù)雜、難以優(yōu)化的問題。

與TaskScheduler-T算法和ICSA算法相比，該算法還具有迭代次數(shù)少、程序執(zhí)行時間短、測試資源利用率高和測試性能優(yōu)等優(yōu)點(diǎn)。綜上所述，對于解決并行測試任務(wù)調(diào)度問題，自適應(yīng)混沌免疫算法表現(xiàn)出了良好的尋優(yōu)性能。這為今后研究并行測試任務(wù)之間具有順序約束的課題，提供了良好的理論支撐。

參考文獻(xiàn)：

[1]肖明清,朱小平,夏銳．并行測試技術(shù)綜述[J]．空軍工程大學(xué)學(xué)報：自然科學(xué)版,2005,6(3):22-25．

[2]卓家靖,孟晨．基于Petri網(wǎng)的并行測試系統(tǒng)任務(wù)過程建模[J]．計算機(jī)工程與設(shè)計,2010(2):309-312．

[3]姚靜波，辛朝軍，蔡遠(yuǎn)文．一種基于多測試資源的并行測試任務(wù)調(diào)度算法[J]．兵工自動化，2014(10)：22-24,36．

[4]李文海,王怡蘋,尚永爽,等．基于有色Petri網(wǎng)和IPSO的并行測試系統(tǒng)任務(wù)調(diào)度研究[J]．計算機(jī)測量與控制,2011,19(10):2390-2393,2396．

[5]秦勇，梁旭．基于混合遺傳算法的并行測試任務(wù)調(diào)度研究[J]．國外電子測量技術(shù),2016,35(9):72-75．

[6]唐娜，張公讓，李磊．自適應(yīng)混沌搜索的雙粒子群優(yōu)化算法[J]．計算機(jī)工程與設(shè)計,2016(9):2421-2428．

[7]呂曉明，黃考利，連光耀．基于混沌遺傳算法的測試選擇優(yōu)化問題研究[J]．導(dǎo)彈與制導(dǎo)學(xué)報,2009,29(3):265-268．

[8]趙欣.不同一維混沌映射的優(yōu)化性能比較[J]．計算機(jī)應(yīng)用研究,2012(3):913-915.

[9]趙巖松．基于自適應(yīng)混沌的多核任務(wù)調(diào)度算法研究[D]．西安:西安電子科技大學(xué),2014．

[10] 苗國義,穆瑞輝,許加月．基于改進(jìn)人工免疫算法的模糊Petri網(wǎng)參數(shù)優(yōu)化[J]．微電子學(xué)與計算機(jī),2013,30(9):102-105．

[11] 楊斌,陸余良,楊國正,等．人工免疫理論在異常檢測中的應(yīng)用進(jìn)展[J]．計算機(jī)應(yīng)用研究,2016,33(4):961-966．