基于DPSO算法的并行测试任务调度

王荣芝;陈晓

【摘 要】为解决并行测试任务调度复杂、难以优化的难题,利用惯性因子动态调整的粒子群算法(dynamic particle swarm optimization,DPSO)建立任务间存在约束关系的并行测试任务调度模型,给出模型求解算法,并通过仿真实验验证该模型的有效性和DPSO算法应用于并行测试任务调度的可行性. 【期刊名称】《中国测试》 【年(卷),期】2014(040)003 【总页数】4页(P101-104)

【关键词】并行测试;DPSO算法;约束关系;任务调度 【作 者】王荣芝;陈晓

【作者单位】呼伦贝尔学院计算机科学与技术学院,内蒙古呼伦贝尔021008;中国航天科技集团第八○三研究所,上海200233 【正文语种】中 文

【中图分类】TN911.7;TP274+.4;TP301.6;TP391.97

并行测试（parallel test）是下一代自动测试系统（NxTest）的主要关键技术之一[1]，是指ATS在同一时间内完成多项测试任务，包括在同一时间内完成对多个UUT的测试；或者在单个UUT上异步或者同步地运行多个测试任务，同时完成对UUT多项参数的测量[1]。其核心是软件上的测试任务调度。常规的任务调度算法有遗传算法[2]、图染色法[3]、蚁群算法[4-5]等，这些算法都把任务看作相互

的个体，没有分析任务间的前后约束关系，而自动测试系统中很多任务存在测试顺序的约束关系，例如测某罗盘灵敏度必须在调谐完成后才能测量。

基于上述情况，本文首先建立了一个任务间存在约束关系的并行测试任务调度模型，然后将改进后的PSO算法应用于并行测试任务调度模型中，最后用一个任务间存在约束关系的例子说明模型的有效性和DPSO算法应用于并行测试任务调度的可行性。

测试资源、测试任务和目标函数是并行测试任务调度的三要素[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.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为粒子的维数。 （3）对所有粒子进行编码。

（4）对每个粒子评价其适应度。本文应用的适应度函数为所有测试仪器最后完成时间的最大值，如方程（1）所示。

式中：Cj——测试仪器j的完工时间； m——测试仪器数目。

（5）确定迄今为止每个粒子找到的最好位置pi=（pi1，pi2，…pid…piD）。最好位置是由适应度值确定的，如方程（5）所示。

（6）确定迄今为止整个群体找到的最好位置pg=（pg1，pg2，…pgd…pgD）。pg的确定由方程（6）求得。

（7）计算每个粒子与历史最优粒子的距离dig，更新每个粒子的惯性因子wi。dig的计算如式（7）所示，惯性因子wi更新公式如式（8）所示。 式中：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）。

假设有10个存在某种约束关系的测试任务J= {Ji}1≤i≤10，5个可用的测试资源Rj（1≤i≤5）。其中测试任务J2、J3、J4存在测试先后的关系，即任务J2结束后才能开始J3，J3结束后才能开始J4。任务J7、J8也存在同样的测试先后的关系。

测试任务关系树模型[5]表示如图1所示，图中的箭头表示前一个测试任务完成后才能开始下一个任务，没有箭头标注的测试任务不存在约束关系。

测试任务与测试资源的测试时间对照见表1，“*”表示测试仪器不能测试相应的任务。

并行测试资源调度问题的解空间是离散的，而标准粒子群算法适用于连续搜索空间，对于离散的搜索空间，不能直接应用于并行测试资源调度问题，所以在利用粒子群算法前需要对粒子进行编码[8-10]。在求解该问题时，DPSO算法粒子群中的每一个粒子代表一个候选调度方案，这里用一个2L（L为测试任务总数）维的向量表示一个粒子的位置矢量。它由两个L维的向量组成，这两个L维向量每一维上的向量相互对应，其中X_t[L]的每个分量都是不大于n（n为测试任务关系树模型的分支数）的自然数，它们构成的序列决定了对应约束测试任务的测试先后顺序。X_r[L]的每个分量都是不大于m（测试仪器总数）的自然数，表示测试任务X_t[L]每个分量所对应的测试仪器。表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]新的排列组合。

实验所用机器配置为：Inter（R）Core（TM）*****************；内存为2 G；操作系统为Windows XP，采用Matlab7.1软件进行编程运算。 本仿真实验中将参数νmax、c1、c2、ε、s分别设置为2.09，2，2，200，30。针对实验例子用DPSO算法进行仿真，并与标准的PSO算法性能进行对比分析。通过仿真实验，用DPSO算法得到的调度结果甘特图如图2所示，可以看出，总测试时间为10个单位时间。应用标准的PSO算法由于惯性因子变化比较单一，在迭代过程中可能会很快陷入了局部最优，得到上述理想结果的概率较低。 图3为DPSO算法与标准PSO算法的性能比较，可以看出，在算法的迭代过程中，标准PSO算法快速地降到某个值后，向更优解跳跃的幅度非常小，容易陷入局部最优，而DPSO算法可以经过几次比较大的跳跃，从而得到更优的解，求解效果比标准PSO算法好。表3列出了两种算法试验100次的结果，DPSO算法成功率达到93%，在解决该问题的成功率上高于标准PSO算法。

并行测试技术是自动测试系统的关键技术，并行测试任务调度是并行测试技术的核心。本文根据任务间存在约束关系的并行测试任务调度模型，首次应用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.