一种基于分解和最优解跟随策略的多目标测试任务调度方法

摘要

本发明公开了一种基于分解和最优解跟随策略的多目标测试任务调度方法，属于并行测试任务调度领域。本方法首先初始化参数设置，然后利用基于分解的方法将多目标问题在其目标函数空间内分解为一系列子问题，子问题通过与其邻域的信息交换得到更新进化。然后对参考点以及每个子问题的邻域进行更新，再采用最优解跟随策略使得解集在整体上进行提高，通过多次迭代以得到更优的解，即得到更优的测试任务序列极其对应的测试方案集合。本发明方法采用基于分解的策略解决多目标优化问题，避免了加权和方法的使用，减少了人为因素的影响；而最优解跟随策略的加入使得每一代解集质量整体提高，最终提高了多目标测试任务调度方法的效率。

主权项

1.一种基于分解和最优解跟随策略测试任务调度方法，包括以下几个步骤：第一步：开始进入调度方法计算接口；第二步：初始化确定目标函数并初始化方法的参数设置，计算权重矢量邻域索引集并给出初始解；2.1 确定目标函数本发明中目标函数为：最大完成时间与资源平均工作负荷；确定测试任务集T＝{t₁,t₂,…,t_j,…,t_N}，t_j为第j个测试任务，N为测试任务总数；确定仪器资源集R＝{r₁,r₂,…,r_i,…,r_M}，r_i为第i个仪器，M为仪器总数，与分别代表在测试任务t_j在资源r_i进行时的起始时间、完成时间以及消耗时间，有判断矩阵表示资源与任务的需求关系，其中t_j为第j个测试任务而r_i为第i个仪器；t_j的测试方案集为其中k_j是测试任务t_j的测试方案总数，表示测试任务t_j选择测试方案的测试消耗时间，r_i表示测试方案中的资源，测试方案集之间的资源约束表示为：其中与分别表示任务t_j的第k个方案选择与任务的第k^*个方案选择；两个目标函数是最大完成时间与资源平均工作负荷，分别用f₁(x)与f₂(x)表示；设任务t_j选择方案时完成时间为r_i表示测试方案中的资源，因此最大完成时间为$f_1\left(x\right)=\underset{\begin{array}{c}1\le k\le k_j\\ 1\le j\le n\end{array}}{\max }{C}_j^k;$设D表示并行步数，初始值设置为1，再给所有的任务都安排测试资源后，如果D＝D+1，计算得到并行总步数，则资源平均工作负荷为：其中表示测试任务t_j选择测试方案的测试消耗时间，判断矩阵表示资源与任务的需求关系；2.2 变量及参数初始化记最优解集为EP，且初始化每个目标函数的暂时最优解z＝(z₁,…,z_i,…,z_m)^T，z_i＝min{f_i(x),x∈Ω}，即z_i为各目标函数在定义域内的理论最小值，基于分解和最优解跟随策略测试任务调度方法的参数包括：迭代次数M，种群大小N，邻域大小T，交叉概率CR，变异概率p，惯性权重w，学习因子c1、c2；2.3 计算权重索引集计算与第i个权重矢量最近的T个权重索引集，其中索引集记为B(i)＝{i₁,…,i_T}，记λⁱ为均匀分布的N个权重矢量中的第i个权重值，i∈[1,N]，是λⁱ的T个最近的权重值，N为基于分解和最优解跟随策略的多目标测试任务调度方法的子问题的数目即种群大小，T为距离每单个的权重矢量最近的权重矢量的数量即邻域大小。2.4 生成初始解随机产生初始种群记为x¹,…,x^N，并令每个个体对应目标函数的解为f_i(x^j)，其中i∈[1,2]，j∈[1,N]；第三步：交叉记t代中一个体为交叉之后产生的个体为具体交叉方式如下：$x_{t+1}^i=\left\{\begin{array}{cc}{x}_t^i+F_1\times (x_t^i-x_t^{i1})+F_2\times (x_t^i-x_t^{i2})& \mathrm{rand}\left(1\right)<\mathrm{CR}\\ x_t^i& \mathrm{rand}\left(1\right)\ge \mathrm{CR}\end{array}\right.$其中：与为权重矢量B(i)中随机挑选的指标，F₁与F₂设置为1，rand(1)为变化范围为0到1的一随机小数；第四步：变异变异采用高斯变异，对于每一个解高斯变异算子如下所示：其中表示变异后的新个体，为一服从正态分布的数，其中为均值，σ为方差，σ在自然数编码中设置为决策变量变化范围的1/20；rand(1)为变化范围为0到1的一随机小数，p为0.05；第五步：邻域与参考点更新更新z：对任意j＝1,…,m，若z_j＜f_j(y′)，则赋值z_j＝f_j(y′)，z_j为任意一最优解；更新邻域：y′为变异后得到的解；定义参考点为z_i的第j个子问题的适应度函数值为其中λ^j为均匀分布的权重矢量组中一个权重矢量，对j∈B(i)，若适应度函数值F(y′)≤F(x^j)，则任意初始种群x^j＝y′,f_i(x^j)＝f_i(y′),其中i∈[1,2]；第六步：最优解跟随具体过程如下：6.1 确定自身最优解在每一代中，如果粒子所到达的点没有被粒子之前所到达的点支配；则自身到达的最优解p_ld为其本身；如果粒子所到达的点被粒子之前所到达的点支配，将支配现在粒子到达点的解保存到一个集合中，则p_ld为此集合中对应的目标函数空间中的点与现在到达点欧式距离最近的解；6.2 确定全局最优解具体确定方法为：每一次迭代过程中，在交叉变异之后，所有的非支配解作为现有的前沿，然后计算每一个粒子与前沿上的点的欧式距离，其中与粒子最近的非支配解即为全局最优解p_gd；6.3 进行最优解跟随操作按照以下公式以及由6.1与6.2中确定的优值来进行最优跟随v_td＝w×v_td+c₁×rand₁×(p_ld-x_td)+c₂×rand₂×(p_gd-x_td)x_td＝x_td+v_td其中x_td代表解，v_td代表粒子飞行速度，p_ld为确定的自身到达的最优解，p_gd为全局最优解，惯性权重w与学习因子c₁、c₂一般设置为1，rand₁与rand₂为变化范围由0到1的随机小数；第七步：更新最优解集从保留最优解的解集EP中删除被支配的解，加入新的非支配解；第八步：输出最优解集在满足停止条件后，计算停止，输出最优解集，进而得到测试方案的任务排序以及各任务所采用的资源。