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

王榮芝,陳 曉

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

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

王榮芝1,陳 曉2

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

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

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

0 引 言

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

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

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

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

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

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

其中式（1）表示儀器j的總最后完成時(shí)間；式（2）表示測(cè)試任務(wù)i必須在測(cè)試任務(wù)e完成后才能開始；式（3）表示某一時(shí)刻測(cè)試儀器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來(lái)更好地控制收斂和探索，即隨著迭代的進(jìn)行，慣性系數(shù)線性減小的策略，形成了標(biāo)準(zhǔn)的PSO算法[3]。粒子群算法概念簡(jiǎn)單、容易實(shí)現(xiàn)，且不需要借助問(wèn)題的特征信息，是一種高效的并行搜索算法，非常適于復(fù)雜環(huán)境中優(yōu)化問(wèn)題的求解，現(xiàn)已廣泛應(yīng)用于各領(lǐng)域。

慣性因子w對(duì)PSO算法的探索和收斂有很大的影響，較大的慣性系數(shù)有利于算法對(duì)搜索區(qū)域的全局探索，較小的慣性系數(shù)有利于提高算法局部的搜索能力。隨著算法迭代次數(shù)的增加，各粒子變得越來(lái)越相似，且都在局部最優(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ì)越來(lái)越高，粒子與歷史最優(yōu)的距離會(huì)越來(lái)越小，如果利用粒子群與歷史最優(yōu)粒子的距離相應(yīng)地動(dòng)態(tài)調(diào)整慣性系數(shù)，就可以改觀粒子的多樣性，從而動(dòng)態(tài)調(diào)整粒子群的全局和局部搜索能力，使得算法具有自適應(yīng)能力。

2.2 算法流程

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

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

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

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

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

m——測(cè)試儀器數(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ù)用來(lái)保持群體的多樣性。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)系的測(cè)試任務(wù)J= {Ji}1≤i≤10，5個(gè)可用的測(cè)試資源Rj（1≤i≤5）。其中測(cè)試任務(wù)J2、J3、J4存在測(cè)試先后的關(guān)系，即任務(wù)J2結(jié)束后才能開始J3，J3結(jié)束后才能開始J4。任務(wù)J7、J8也存在同樣的測(cè)試先后的關(guān)系。測(cè)試任務(wù)關(guān)系樹模型[5]表示如圖1所示，圖中的箭頭表示前一個(gè)測(cè)試任務(wù)完成后才能開始下一個(gè)任務(wù)，沒(méi)有箭頭標(biāo)注的測(cè)試任務(wù)不存在約束關(guān)系。

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

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

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

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

表2 粒子編碼示例

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

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

（1）對(duì)于X_r[L]，如果按粒子位置更新公式計(jì)算出的某個(gè)分類出現(xiàn)小數(shù)，則采取向上取整的方法，而測(cè)試儀器編號(hào)屬于[1，m]的整數(shù)，當(dāng)向量的某個(gè)值超過(guò)了該區(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ì)比分析。通過(guò)仿真實(shí)驗(yàn)，用DPSO算法得到的調(diào)度結(jié)果甘特圖如圖2所示，可以看出，總測(cè)試時(shí)間為10個(gè)單位時(shí)間。應(yīng)用標(biāo)準(zhǔn)的PSO算法由于慣性因子變化比較單一，在迭代過(guò)程中可能會(huì)很快陷入了局部最優(yōu)，得到上述理想結(jié)果的概率較低。

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

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

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

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

5 結(jié)束語(yǔ)

并行測(cè)試技術(shù)是自動(dòng)測(cè)試系統(tǒng)的關(guān)鍵技術(shù)，并行測(cè)試任務(wù)調(diào)度是并行測(cè)試技術(shù)的核心。本文根據(jù)任務(wù)間存在約束關(guān)系的并行測(cè)試任務(wù)調(diào)度模型，首次應(yīng)用DPSO算法實(shí)現(xiàn)并行測(cè)試任務(wù)的調(diào)度，通過(guò)相應(yīng)的實(shí)例證明了該算法的可行性。在本仿真試驗(yàn)中并沒(méi)有把電源、激勵(lì)、信號(hào)發(fā)生器等輔助儀器包括在內(nèi)，而通常自動(dòng)測(cè)試系統(tǒng)中這些輔助儀器是必不可少的測(cè)試資源，因此將輔助儀器加入研究對(duì)象，實(shí)現(xiàn)并行測(cè)試任務(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]梁旭，李行善，于勁松.基于遺傳算法的并行測(cè)試調(diào)度算法研究[J].電子測(cè)量與儀器學(xué)報(bào)，2009，23（2）：19-24.

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

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

[5]陳利安，肖明清，高峰，等.人工蜂群算法在并行測(cè)試任務(wù)調(diào)度中的應(yīng)用[J].計(jì)算機(jī)測(cè)量與控制，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

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

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