求解并行測試任務調度問題的ACIA

李文海，管　晗

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

并行測試與傳統串行測試相比，提高了資源利用率，節約了測試時間。但是其任務調度是個復雜、難以優化的NP難題[1]。

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

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

1　混沌優化理論

混沌是指在確定系統中出現的一種貌似無規則，類似隨機的現象，是存在于非線性系統中的一種較為普遍的現象。混沌并不是一片混亂，而是有著精致內在結構的一類現象。混沌是非線性動力學系統在一定條件下所表現的一種運動形式，是系統處于非平衡過程中所呈現的隨機行為[6]。混沌的主要特征有：非線性、對初始條件敏感的依賴性、長期行為的不可預測性、不可分解性、穩定性和不穩定性、具有規律性成分、遍歷性、分形性[7]。

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

1)S不包含周期點；

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

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

xn+1=μxn1-xn

(1)

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

2　自適應混沌免疫算法

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

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

2.1　算法步驟

自適應混沌免疫算法的步驟如下：

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

步驟2根據親和度函數，計算各抗體的親和度，挑選出親和度高的前N1個最優抗體，構成克隆體種群B；

步驟3對克隆體種群B進行自適應克隆(復制)操作，得到新的抗體種群C；

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

步驟5對抗體種群D進行濃度調節操作，得到抗體種群E；

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

步驟7返回步驟2進行迭代，直到滿足停止條件，迭代結束，輸出結果。

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

2.2　ACIA求解并行測試任務調度問題

在并行測試任務調度問題中，調度的目標函數即測試總時間，對應于算法中的抗原；調度的候選序列對應于抗體；候選序列相對于目標函數的質量對應于抗原和抗體的親和度。

算法的改進主要在混沌初始化、基于混沌擾動的變異和濃度調節操作。改進后的算法具體步驟如下：

1) 混沌初始化

(2)

其中，randperm*為隨機排列函數。

(3)

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

(4)

得到自適應混沌免疫算法的初始種群

(5)

2) 目標函數和親和度

目標函數MakeP為測試時間，即變遷序列的時延總和。測試的最優序列即為測試時間最短的序列，得到任務調度最優方案的算法的基本思想如下：

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

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

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

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

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

親和度反映了變遷序列的質量，由目標函數的某種變換表示。假設某測試系統串行測試的總時間為T，所以構造第i個測試序列的親和度函數定義為

Aff1,i=T-MakeP1,i

(6)

3) 自適應克隆操作

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

(7)

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

(8)

其中：M為細胞克隆數；Mn(i)可根據該抗體的親和度自適應調整；Int*為上取整函數。克隆過后，得到新的抗體種群C。

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

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

5) 濃度調節操作

利用濃度調節機制，實現抗體間促進和抑制的相互關系。第i個抗體的選擇概率為

Pci=αPAffi+1-αPNongi

(9)

其中：α為常數調節因子；PAffi為親和度概率；PNongi為濃度抑制概率

(10)

(11)

其中：β為常數調節因子；Nong(1,i)為第i個抗體濃度

(12)

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

(13)

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

(14)

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

6) 停止條件

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

3　實驗仿真

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

表1　雷達接收機測試任務資源集

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

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

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

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

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

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

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

綜上所述，自適應混沌免疫算法的執行時間更短，效率更高，性能更優。

4　結論

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

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

參考文獻：

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

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

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

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

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

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

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

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

[9]趙巖松．基于自適應混沌的多核任務調度算法研究[D]．西安:西安電子科技大學,2014．

[10] 苗國義,穆瑞輝,許加月．基于改進人工免疫算法的模糊Petri網參數優化[J]．微電子學與計算機,2013,30(9):102-105．

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