基于DPSO算法的并行測試任務調度

王榮芝,陳 曉

（1.呼倫貝爾學院計算機科學與技術學院，內蒙古 呼倫貝爾 021008；2.中國航天科技集團第八○三研究所，上海 200233）

基于DPSO算法的并行測試任務調度

王榮芝1,陳 曉2

（1.呼倫貝爾學院計算機科學與技術學院，內蒙古 呼倫貝爾 021008；2.中國航天科技集團第八○三研究所，上海 200233）

為解決并行測試任務調度復雜、難以優化的難題，利用慣性因子動態調整的粒子群算法（dynamic particle swarm optimization，DPSO）建立任務間存在約束關系的并行測試任務調度模型，給出模型求解算法，并通過仿真實驗驗證該模型的有效性和DPSO算法應用于并行測試任務調度的可行性。

并行測試；DPSO算法；約束關系；任務調度

0 引 言

并行測試（parallel test）是下一代自動測試系統（NxTest）的主要關鍵技術之一[1]，是指ATS在同一時間內完成多項測試任務，包括在同一時間內完成對多個UUT的測試；或者在單個UUT上異步或者同步地運行多個測試任務，同時完成對UUT多項參數的測量[1]。其核心是軟件上的測試任務調度。常規的任務調度算法有遺傳算法[2]、圖染色法[3]、蟻群算法[4-5]等，這些算法都把任務看作相互獨立的個體，沒有分析任務間的前后約束關系，而自動測試系統中很多任務存在測試順序的約束關系，例如測某羅盤靈敏度必須在調諧完成后才能測量。

基于上述情況，本文首先建立了一個任務間存在約束關系的并行測試任務調度模型，然后將改進后的PSO算法應用于并行測試任務調度模型中，最后用一個任務間存在約束關系的例子說明模型的有效性和DPSO算法應用于并行測試任務調度的可行性。

1 任務間存在約束的并行測試任務調度模型

測試資源、測試任務和目標函數是并行測試任務調度的三要素[2]。假設m為測試儀器數量；n為測試任務數量；測試任務中某些測試任務存在約束關系。R={Rj}1≤j≤m為所有測試儀器集合；J={Ji}1≤i≤n為所有測試任務的集合；Rj?R表示測試任務j的可選測試儀器集；Tij為測試任務i在儀器j上的測試時間；Sij為測試任務i在儀器j上的開始測試時間；Eij為

測試任務i在儀器j上的結束測試時間；Cj為測試儀器j的完工時間；當測試任務e和測試任務j要占用同一臺測試儀器，且測試任務i先于e時，Xie=1，否則Xie=0；若測試任務i在測試儀器j上測試，Yij=1，否則Yij=0。

在測試資源和測試任務都給定的情況下，并行測試任務調度的目的是根據測試需求調度測試資源，使得資源使用代價最小、利用率最高、測試時間最短。在自動測試系統中測試時間是衡量測試性能的重要指標，所以這里用最短完成時間作為目標函數。目標函數描述為

其中式（1）表示儀器j的總最后完成時間；式（2）表示測試任務i必須在測試任務e完成后才能開始；式（3）表示某一時刻測試儀器j只能被一個任務占用。

2 模型求解方法

2.1 標準粒子群（PSO)算法

粒子群優化算法（particle swarm optimization，PSO）是Eberhant和Kennidy于1995年開發的一種進化計算技術，源于對鳥群捕食的研究[6-7]。Y.Shi與R.E-berhart引入了慣性因子w來更好地控制收斂和探索，即隨著迭代的進行，慣性系數線性減小的策略，形成了標準的PSO算法[3]。粒子群算法概念簡單、容易實現，且不需要借助問題的特征信息，是一種高效的并行搜索算法，非常適于復雜環境中優化問題的求解，現已廣泛應用于各領域。

慣性因子w對PSO算法的探索和收斂有很大的影響，較大的慣性系數有利于算法對搜索區域的全局探索，較小的慣性系數有利于提高算法局部的搜索能力。隨著算法迭代次數的增加，各粒子變得越來越相似，且都在局部最優附近徘徊，容易陷入局部最優，所以標準PSO算法存在早熟收斂的缺點。

文獻[4]提出了一種慣性權重動態調整的新型粒子群算法，但是該方法收斂較慢。在標準的粒子群算法中，隨著迭代的進行，粒子的聚集度會越來越高，粒子與歷史最優的距離會越來越小，如果利用粒子群與歷史最優粒子的距離相應地動態調整慣性系數，就可以改觀粒子的多樣性，從而動態調整粒子群的全局和局部搜索能力，使得算法具有自適應能力。

2.2 算法流程

結合存在約束關系的并行測試任務調度模型，基于DPSO的并行測試任務調度算法過程如下：

（1）設置最大迭代次數Nmax；粒子群的大小s；粒子最大飛行速度νmax；結束閥值ε。閥值的設置以最優解未變化的次數為界線，當最優解連續ε次未變化，程序結束。

（2）初始化每個粒子的位置（初始解）與速度xi（0）=（xi1，xi2，…xid…xiD），i=1，2，…；νi（0）=（νi1，νi2，…νid…νiD），i=1，2，…，s；D為粒子的維數。

除了印發《讀本》，順義區還組建了一支近1000人的黨風政務監督員隊伍，監督員來自全區各個崗位，甚至覆蓋了電影院、社區、商場、餐飲企業。為了方便群眾監督舉報，順義區紀委區監委還搭建了網絡監督舉報平臺,舉報平臺二維碼通過海報的形式，張貼在全區426個行政村、80個居委會和60余個政務服務大廳。舉報人通過手機掃描二維碼，即可進入舉報頁面，第一時間反映問題。

（3）對所有粒子進行編碼。

（4）對每個粒子評價其適應度。本文應用的適應度函數為所有測試儀器最后完成時間的最大值，如方程（1）所示。

式中：Cj——測試儀器j的完工時間；

m——測試儀器數目。

（5）確定迄今為止每個粒子找到的最好位置pi=（pi1，pi2，…pid…piD）。最好位置是由適應度值確定的，如方程（5）所示。

（6）確定迄今為止整個群體找到的最好位置pg=（pg1，pg2，…pgd…pgD）。pg的確定由方程（6）求得。

式中：dmax——所有粒子之間的最大距離；

dig——當前粒子與歷史最優粒子的距離；

wmax——最大慣性因子；

wmin——最小慣性因子。

（8）更新所有粒子的速度xi（t）和位置νi（t）。粒子速度與位置更新如式（9）、式（10）、式（11）所示。

式（9）中r1d?U（0，1）和r2d?U（0，1）是兩個獨立的隨機數，這兩個隨機數用來保持群體的多樣性。c1和c2是正常數且0＜c1，c2＜4，它們稱為加速因子，使

粒子具有自我總結和向群體中優秀個體學習的能力。wi為慣性因子決定了粒子先前速度對當前速度的影響。νmax限定了粒子最大飛行速度。

（9）若滿足閥值條件ε或迭代次數達到Nmax，計算結束，輸出計算結果。否則，轉向（3）。

3 實驗分析

假設有10個存在某種約束關系的測試任務J= {Ji}1≤i≤10，5個可用的測試資源Rj（1≤i≤5）。其中測試任務J2、J3、J4存在測試先后的關系，即任務J2結束后才能開始J3，J3結束后才能開始J4。任務J7、J8也存在同樣的測試先后的關系。測試任務關系樹模型[5]表示如圖1所示，圖中的箭頭表示前一個測試任務完成后才能開始下一個任務，沒有箭頭標注的測試任務不存在約束關系。

圖1 測試任務的關系樹圖

測試任務與測試資源的測試時間對照見表1，“*”表示測試儀器不能測試相應的任務。

表1 測試任務與測試資源的時間對照表

并行測試資源調度問題的解空間是離散的，而標準粒子群算法適用于連續搜索空間，對于離散的搜索空間，不能直接應用于并行測試資源調度問題，所以在利用粒子群算法前需要對粒子進行編碼[8-10]。在求解該問題時，DPSO算法粒子群中的每一個粒子代表一個候選調度方案，這里用一個2L（L為測試任務總數）維的向量表示一個粒子的位置矢量。它由兩個L維的向量組成，這兩個L維向量每一維上的向量相互對應，其中X_t[L]的每個分量都是不大于n（n為測試任務關系樹模型的分支數）的自然數，它們構成的序列決定了對應約束測試任務的測試先后順序。X_r[L]的每個分量都是不大于m（測試儀器總數）的自然數，表示測試任務X_t[L]每個分量所對應的測試儀器。表2是針對上述例子對其中某個粒子的編碼示例。

表2 粒子編碼示例

表中X_t[L]向量的數字代表圖1關系樹中的某一個分支，例如4代表第4個分支。相同的數字代表具有約束關系的測試任務，例如X_t[L]向量中第3個2代表關系樹中第2個分支的第3個測試任務。與位置向量對應，粒子的速度向量也表示為兩部分：V_t[L]和V_r[L]，初始速度隨機生成。

由于測試任務間存在先后的約束關系，所以對算法的迭代過程作如下修改：

（1）對于X_r[L]，如果按粒子位置更新公式計算出的某個分類出現小數，則采取向上取整的方法，而測試儀器編號屬于[1，m]的整數，當向量的某個值超過了該區間，則按邊界取值。

（2）對于X_t[L]，針對任務間的約束關系，將更新后的粒子向量的各分量按從小到大或從大到小的順序進行排序，并根據排序后的結果，將與計算后的值所對應的初始值重新排列，即X_t[L]新的排列組合。

4 實驗結果與分析

實驗所用機器配置為：Inter（R）Core（TM）2 Duo E4600@2.40 GHz；內存為2 G；操作系統為Windows XP，采用Matlab7.1軟件進行編程運算。

本仿真實驗中將參數νmax、c1、c2、ε、s分別設置為2.09，2，2，200，30。針對實驗例子用DPSO算法進行仿真，并與標準的PSO算法性能進行對比分析。通過仿真實驗，用DPSO算法得到的調度結果甘特圖如圖2所示，可以看出，總測試時間為10個單位時間。應用標準的PSO算法由于慣性因子變化比較單一，在迭代過程中可能會很快陷入了局部最優，得到上述理想結果的概率較低。

圖2 任務間存在約束的并行測試甘特圖

圖3為DPSO算法與標準PSO算法的性能比較，可以看出，在算法的迭代過程中，標準PSO算法快速地降到某個值后，向更優解跳躍的幅度非常小，容易陷入局部最優，而DPSO算法可以經過幾次比較大的跳躍，從而得到更優的解，求解效果比標準PSO算法好。表3列出了兩種算法試驗100次的結果，DPSO算法成功率達到93%，在解決該問題的成功率上高于標準PSO算法。

圖3 DPSO算法與PSO算法的性能比較

表3 PSO與DPSO比較結果

5 結束語

并行測試技術是自動測試系統的關鍵技術，并行測試任務調度是并行測試技術的核心。本文根據任務間存在約束關系的并行測試任務調度模型，首次應用DPSO算法實現并行測試任務的調度，通過相應的實例證明了該算法的可行性。在本仿真試驗中并沒有把電源、激勵、信號發生器等輔助儀器包括在內，而通常自動測試系統中這些輔助儀器是必不可少的測試資源，因此將輔助儀器加入研究對象，實現并行測試任務的最優調度將成為下一步研究工作的重點。

[1]Ross W A.The impact of next generation test technology on aviation maintenance[C]∥Autotestcon 2003 IEEE Systems Readiness Technology Conference Proceedings Anaheim.IEEE Instrumentation and Measurement Society，2003：2-9.

[2]梁旭，李行善，于勁松.基于遺傳算法的并行測試調度算法研究[J].電子測量與儀器學報，2009，23（2）：19-24.

[3]李昕，沈士團，路輝.基于圖染色理論的并行測試任務調度算法[J].北京航空航天大學學報，2007，33（9）：1068-1071.

[4]邊澤強，孟曉風，陳粵.基于多色蟻群的柔性測試系統測試資源匹配[J].測試技術學報，2007，21（6）：488-492.

[5]陳利安，肖明清，高峰，等.人工蜂群算法在并行測試任務調度中的應用[J].計算機測量與控制，2012，20（6）：1470-1472.

[6]Eberhait R C，Kennedy J.A new optimizer using particle swarmtheory[C]∥The 6th Int’l Symposium on Micro Machine and Human Science，1995.

[7]Kennedy J，Eberhart R C.Particle swarm optimization[C]∥Proc IEEE Int’1 Conf Neural Networks.IEEE Service Center，1995：1942-1948.

[8]Shi Y，Eberhait R C.A modified particle swarm optimizer[C]∥Proc the IEEE Int’l Conf Evolutionary Computation.IEEE Press，1998：69-73.

[9]劉建華，樊曉平，瞿志華.一種慣性權重動態調整的新型粒子群算法[J].計算機工程與應用，2007，43（7）：68-70.

[10]郝淑珍.復雜產品柔性調度優化研究[D].哈爾濱：哈爾濱理工大學，2009：16-19.

Parallel test task scheduling based on DPSO algorithm

WANG Rong-zhi1，CHEN Xiao2
（1.College of Computer Science and Technology，Hulunbeier College，Hulunbeier 021008，China；2.The 803th Research Institute of CASC，Shanghai 200233，China）

In order to solve the complex and difficult optimization problem of parallel test task scheduling，the authors established the model of the constraint relations between tasks in parallel test task scheduling，and combined with the inertia factor DPSO （dynamic particle swarm optimization，DPSO）algorithm.The model algorithm is demonstrated.Finally，the authors verified the effectiveness and feasibility of the DPSO algorithm in parallel test task scheduling through experimental analysis.

parallel test；DPSO；constraint；task scheduling

TN911.7；TP274+.4；TP301.6；TP391.97

：A

：1674-5124（2014)03-0101-04

10.11857/j.issn.1674-5124.2014.03.027

2013-02-30；

：2013-05-11

國家社科基金西部項目（11XTQ009）內蒙古自治區自然科學基金項目（2011BS0905）

王榮芝（1975-），女，河北陽原縣人，副教授，碩士，研究方向為軟件工程、網絡教育應用。