王榮芝,陳 曉

（1.呼倫貝爾學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古 呼倫貝爾 021008；2.中國航天科技集團(tuán)第八○三研究所，上海 200233）

基于DPSO算法的并行測試任務(wù)調(diào)度

王榮芝1,陳 曉2

（1.呼倫貝爾學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古 呼倫貝爾 021008；2.中國航天科技集團(tuán)第八○三研究所，上海 200233）

為解決并行測試任務(wù)調(diào)度復(fù)雜、難以優(yōu)化的難題，利用慣性因子動(dòng)態(tài)調(diào)整的粒子群算法（dynamic particle swarm optimization，DPSO）建立任務(wù)間存在約束關(guān)系的并行測試任務(wù)調(diào)度模型，給出模型求解算法，并通過仿真實(shí)驗(yàn)驗(yàn)證該模型的有效性和DPSO算法應(yīng)用于并行測試任務(wù)調(diào)度的可行性。

并行測試；DPSO算法；約束關(guān)系；任務(wù)調(diào)度

0 引 言

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

基于上述情況，本文首先建立了一個(gè)任務(wù)間存在約束關(guān)系的并行測試任務(wù)調(diào)度模型，然后將改進(jìn)后的PSO算法應(yīng)用于并行測試任務(wù)調(diào)度模型中，最后用一個(gè)任務(wù)間存在約束關(guān)系的例子說明模型的有效性和DPSO算法應(yīng)用于并行測試任務(wù)調(diào)度的可行性。

1 任務(wù)間存在約束的并行測試任務(wù)調(diào)度模型

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

測試任務(wù)i在儀器j上的結(jié)束測試時(shí)間；Cj為測試儀器j的完工時(shí)間；當(dāng)測試任務(wù)e和測試任務(wù)j要占用同一臺(tái)測試儀器，且測試任務(wù)i先于e時(shí)，Xie=1，否則Xie=0；若測試任務(wù)i在測試儀器j上測試，Yij=1，否則Yij=0。

在測試資源和測試任務(wù)都給定的情況下，并行測試任務(wù)調(diào)度的目的是根據(jù)測試需求調(diào)度測試資源，使得資源使用代價(jià)最小、利用率最高、測試時(shí)間最短。在自動(dòng)測試系統(tǒng)中測試時(shí)間是衡量測試性能的重要指標(biāo)，所以這里用最短完成時(shí)間作為目標(biāo)函數(shù)。目標(biāo)函數(shù)描述為

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

2 模型求解方法

2.1 標(biāo)準(zhǔn)粒子群（PSO)算法

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

慣性因子w對(duì)PSO算法的探索和收斂有很大的影響，較大的慣性系數(shù)有利于算法對(duì)搜索區(qū)域的全局探索，較小的慣性系數(shù)有利于提高算法局部的搜索能力。隨著算法迭代次數(shù)的增加，各粒子變得越來越相似，且都在局部最優(yōu)附近徘徊，容易陷入局部最優(yōu)，所以標(biāo)準(zhǔn)PSO算法存在早熟收斂的缺點(diǎn)。

文獻(xiàn)[4]提出了一種慣性權(quán)重動(dòng)態(tài)調(diào)整的新型粒子群算法，但是該方法收斂較慢。在標(biāo)準(zhǔn)的粒子群算法中，隨著迭代的進(jìn)行，粒子的聚集度會(huì)越來越高，粒子與歷史最優(yōu)的距離會(huì)越來越小，如果利用粒子群與歷史最優(yōu)粒子的距離相應(yīng)地動(dòng)態(tài)調(diào)整慣性系數(shù)，就可以改觀粒子的多樣性，從而動(dòng)態(tài)調(diào)整粒子群的全局和局部搜索能力，使得算法具有自適應(yīng)能力。

2.2 算法流程

結(jié)合存在約束關(guān)系的并行測試任務(wù)調(diào)度模型，基于DPSO的并行測試任務(wù)調(diào)度算法過程如下：

（1）設(shè)置最大迭代次數(shù)Nmax；粒子群的大小s；粒子最大飛行速度νmax；結(jié)束閥值ε。閥值的設(shè)置以最優(yōu)解未變化的次數(shù)為界線，當(dāng)最優(yōu)解連續(xù)ε次未變化，程序結(jié)束。

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

除了印發(fā)《讀本》，順義區(qū)還組建了一支近1000人的黨風(fēng)政務(wù)監(jiān)督員隊(duì)伍，監(jiān)督員來自全區(qū)各個(gè)崗位，甚至覆蓋了電影院、社區(qū)、商場、餐飲企業(yè)。為了方便群眾監(jiān)督舉報(bào)，順義區(qū)紀(jì)委區(qū)監(jiān)委還搭建了網(wǎng)絡(luò)監(jiān)督舉報(bào)平臺(tái),舉報(bào)平臺(tái)二維碼通過海報(bào)的形式，張貼在全區(qū)426個(gè)行政村、80個(gè)居委會(huì)和60余個(gè)政務(wù)服務(wù)大廳。舉報(bào)人通過手機(jī)掃描二維碼，即可進(jìn)入舉報(bào)頁面，第一時(shí)間反映問題。

（3）對(duì)所有粒子進(jìn)行編碼。

（4）對(duì)每個(gè)粒子評(píng)價(jià)其適應(yīng)度。本文應(yīng)用的適應(yīng)度函數(shù)為所有測試儀器最后完成時(shí)間的最大值，如方程（1）所示。

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

m——測試儀器數(shù)目。

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

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

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

dig——當(dāng)前粒子與歷史最優(yōu)粒子的距離；

wmax——最大慣性因子；

wmin——最小慣性因子。

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

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

粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力。wi為慣性因子決定了粒子先前速度對(duì)當(dāng)前速度的影響。νmax限定了粒子最大飛行速度。

（9）若滿足閥值條件ε或迭代次數(shù)達(dá)到Nmax，計(jì)算結(jié)束，輸出計(jì)算結(jié)果。否則，轉(zhuǎn)向（3）。

3 實(shí)驗(yàn)分析

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

圖1 測試任務(wù)的關(guān)系樹圖

測試任務(wù)與測試資源的測試時(shí)間對(duì)照見表1，“*”表示測試儀器不能測試相應(yīng)的任務(wù)。

表1 測試任務(wù)與測試資源的時(shí)間對(duì)照表

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

表2 粒子編碼示例

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

由于測試任務(wù)間存在先后的約束關(guān)系，所以對(duì)算法的迭代過程作如下修改：

（1）對(duì)于X_r[L]，如果按粒子位置更新公式計(jì)算出的某個(gè)分類出現(xiàn)小數(shù)，則采取向上取整的方法，而測試儀器編號(hào)屬于[1，m]的整數(shù)，當(dāng)向量的某個(gè)值超過了該區(qū)間，則按邊界取值。

（2）對(duì)于X_t[L]，針對(duì)任務(wù)間的約束關(guān)系，將更新后的粒子向量的各分量按從小到大或從大到小的順序進(jìn)行排序，并根據(jù)排序后的結(jié)果，將與計(jì)算后的值所對(duì)應(yīng)的初始值重新排列，即X_t[L]新的排列組合。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)所用機(jī)器配置為：Inter（R）Core（TM）2 Duo E4600@2.40 GHz；內(nèi)存為2 G；操作系統(tǒng)為Windows XP，采用Matlab7.1軟件進(jìn)行編程運(yùn)算。

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

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

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

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

表3 PSO與DPSO比較結(jié)果

5 結(jié)束語

并行測試技術(shù)是自動(dòng)測試系統(tǒng)的關(guān)鍵技術(shù)，并行測試任務(wù)調(diào)度是并行測試技術(shù)的核心。本文根據(jù)任務(wù)間存在約束關(guān)系的并行測試任務(wù)調(diào)度模型，首次應(yīng)用DPSO算法實(shí)現(xiàn)并行測試任務(wù)的調(diào)度，通過相應(yīng)的實(shí)例證明了該算法的可行性。在本仿真試驗(yàn)中并沒有把電源、激勵(lì)、信號(hào)發(fā)生器等輔助儀器包括在內(nèi)，而通常自動(dòng)測試系統(tǒng)中這些輔助儀器是必不可少的測試資源，因此將輔助儀器加入研究對(duì)象，實(shí)現(xiàn)并行測試任務(wù)的最優(yōu)調(diào)度將成為下一步研究工作的重點(diǎn)。

[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]梁旭，李行善，于勁松.基于遺傳算法的并行測試調(diào)度算法研究[J].電子測量與儀器學(xué)報(bào)，2009，23（2）：19-24.

[3]李昕，沈士團(tuán)，路輝.基于圖染色理論的并行測試任務(wù)調(diào)度算法[J].北京航空航天大學(xué)學(xué)報(bào)，2007，33（9）：1068-1071.

[4]邊澤強(qiáng)，孟曉風(fēng)，陳粵.基于多色蟻群的柔性測試系統(tǒng)測試資源匹配[J].測試技術(shù)學(xué)報(bào)，2007，21（6）：488-492.

[5]陳利安，肖明清，高峰，等.人工蜂群算法在并行測試任務(wù)調(diào)度中的應(yīng)用[J].計(jì)算機(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]劉建華，樊曉平，瞿志華.一種慣性權(quán)重動(dòng)態(tài)調(diào)整的新型粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（7）：68-70.

[10]郝淑珍.復(fù)雜產(chǎn)品柔性調(diào)度優(yōu)化研究[D].哈爾濱：哈爾濱理工大學(xué)，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

國家社科基金西部項(xiàng)目（11XTQ009）內(nèi)蒙古自治區(qū)自然科學(xué)基金項(xiàng)目（2011BS0905）

王榮芝（1975-），女，河北陽原縣人，副教授，碩士，研究方向?yàn)檐浖こ?、網(wǎng)絡(luò)教育應(yīng)用。