基于改进自适应遗传算法的并行测试任务调度方法

技术领域

本发明属于电子系统测试技术领域，更为具体地讲，涉及一种基于改进自适应遗传算法的并行测试任务调度方法。

背景技术

随着工业设备、航天设备等高精尖设备的复杂度不断提高，对于复杂系统的自动测试性能提出了新的挑战。特别是在航空航天领域当中，需要测试的参数庞杂且对准确性与实时行有较高要求。并行测试通过调用相应资源同时对多个任务进行测试改善自动测试系统测试效率低、资源利用率低等问题。并行测试需要考虑资源竞争、系统死锁与饿死等问题，其任务调度方案的确定是一个复杂的、优化难度大的非确定性多项式(non-deterministic polynomial，NP)完全问题。

并行测试任务调度问题研究的目标是确定最优调度方案，如测试时间最短，执行价值最大、负载均衡等。目前，主要有两种研究方向：一是只使用智能算法，通过智能算法良好的全局优化性能求解调度方案，比如粒子群算法、遗传算法、蚁群算法、人工蜂群算法、模拟退火算法等；二是使用Petri网与智能算法相结合，首先利用Petri网模型强大的建模能力对调度过程进行建模，然后使用智能算法求解调度方案。

遗传算法具有优秀的全局搜索能力，强鲁棒性，设计简单等特点，其还具有并行性，天然适用于解决并行测试任务调度这类具有并行性的最优化问题。但是，传统遗传算法采用固定的交叉与变异概率，当交叉与变异概率较小时会导致种群的进化速度较低，增加迭代次数，降低算法的收敛速度，影响任务调度的实时性；当交叉与变异概率较大时会导致种群的进化速度过快，一些优势个体的基因会在种群中迅速扩散，种群多样性丧失，容易出现陷入局部最优解的情况，导致得到的调度方案不是最优调度方案，达不到优化的目的。

针对遗传算法的改进，Srinivas等首次提出了自适应遗传算法(adaptivegenetic algorithm，AGA)，该算法根据个体适应度值调节交叉与变异概率，在一定程度上解决了遗传算法陷入局部最优解的问题，但是该算法会使适应度值较大的优势个体的交叉与变异概率接近或者等于零，导致优势个体的特性不被遗传，陷入局部最优解。任子武等提出了一种改进的自适应遗传算法(improved adaptive genetic algorithm，IAGA)，保证所有个体都有一个最低的交叉与变异概率，但是在算法迭代后期个体的适应度值与平均适应度值相近且这些个体数量较大时，会导致大部分个体的交叉与变异概率较低，降低了种群的进化速度。

发明内容

本发明的目的在于克服现有技术的不足，提供一种基于改进自适应遗传算法的并行测试任务调度方法，通过种群相异度对遗传算法的交叉与变异概率进行自适应取值，解决了遗传算法容易陷入局部最优的问题，提高遗传算法收敛速度以及搜索最优解的成功率，使其在解决并行测试任务调度问题时可以快速、准确地求出最优并行测试任务调度方案。

为了实现上述发明目的，本发明基于改进自适应遗传算法的并行测试任务调度方法包括以下步骤：

S1：对于待进行并行测试的电子系统，根据实际情况针对其包含的子系统设计测试任务，获取其并行测试相关数据，包括：

测试任务集T＝{t

测试时间集τ＝{τ

测试资源集R＝{r

任务资源矩阵TR，大小为M×N，用于表示资源被占用的情况，若TR(m,n)＝1则测试任务t

任务约束矩阵TS，大小为M×M，用于表示测试任务执行的先后顺序，若TS(m,m′)＝1则测试任务t

S2：采用实数编码的方式对测试任务进行编码，在编码过程中如果任务约束矩阵TS(m,m′)＝1时，表示测试任务t

S3：将测试任务的编码序列作为遗传算法的个体，对测试任务的编码进行K次随机排序生成K个编码序列，构成遗传算法的初始种群Q，记第i个个体为X

S4：计算初始种群的相异度D

对于当前种群，首先计算任意两个个体之间的相异程度d

其中，i＝1,2,…,K，j＝1,2,…,K，且i≠j，x

然后采用如下公式计算当前种群整体的相异度D：

S5：计算当前种群Q中各个个体的适应度，具体方法为：

根据个体中测试任务编码的顺序、测试时间集τ、任务资源矩阵TR和任务约束矩阵TS生成并行测试任务调度方案，获取该调度方案完成测试所需时间TIME，然后采用如下公式计算个体的适应度f：

适应度越大，个体越优；

S6：判断是否满足终止条件，如果是，则进入步骤S11，否则进入步骤S7；

S7：从当前种群Q中选择优势个体构成新种群Q

S8：对新种群Q

采用步骤S4中的方法计算新种群Q

其中，p

S9：对子代种群Q

采用步骤S4中的方法计算子代种群Q

其中，p

S10：令子代种群Q

S11：选择当前种群中适应度最大的个体，根据该个体中测试任务编码的顺序、测试时间集τ、任务资源矩阵TR和任务约束矩阵TS生成并行测试任务调度方案。

本发明基于改进自适应遗传算法的并行测试任务调度方法，获取电子系统待测任务的相关数据，采用实数编码的方式对测试任务进行编码，编码时受任务约束限制，将测试任务的编码序列作为遗传算法的个体执行遗传算法，在遗传算法迭代过程中，基于种群相异度的变化计算个体的交叉概率与变异概率，迭代完成后选取最优个体得到最终的并行测试任务调度方案。

本发明将遗传算法的交叉与变异概率与种群的多样性关联，当种群的多样性较大时，此时降低交叉与变异概率，减小种群进化速度，提高搜索精度；当种群的多样性较小时，此时增大交叉与变异概率，提高种群进化速度，避免陷入局部最优。上述改进使得在整个迭代过程中，交叉与变异概率都有合适的取值，保证种群的多样性，减小陷入局部最优解的可能性，从而更加快速准确地得到并行测试任务调度方案，提高测试效率。

附图说明

图1是本发明基于改进自适应遗传算法的并行测试任务调度方法的具体实施方式流程图；

图2是本实施例个体对应并行测试任务调度方案的甘特图；

图3是本实施例中个体交叉的示例图；

图4是本实施例中个体变异的示例图；

图5是本实施例中测试任务序列得到的并行测试甘特图；

图6是本发明和2种对比方法的种群相异度随迭代次数变化的对比图；

图7是本发明和2种对比方法的最大适应度值随迭代次数变化的对比图；

图8是本发明和2种对比方法得到最优解的概率随迭代次数变化的对比图。

具体实施方式

下面结合附图对本发明的具体实施方式进行描述，以便本领域的技术人员更好地理解本发明。需要特别提醒注意的是，在以下的描述中，当已知功能和设计的详细描述也许会淡化本发明的主要内容时，这些描述在这里将被忽略。

实施例

图1是本发明基于改进自适应遗传算法的并行测试任务调度方法的具体实施方式流程图。如图1所示，本发明基于改进自适应遗传算法的并行测试任务调度方法的具体步骤包括：

S101：获取并行测试相关数据：

对于待进行并行测试的电子系统，根据实际情况针对其包含的子系统设计测试任务，获取其待测任务的相关数据，包括：

测试任务集T＝{t

测试时间集τ＝{τ

测试资源集R＝{r

任务资源矩阵TR，大小为M×N，用于表示资源被占用的情况，若TR(m,n)＝1则测试任务t

任务约束矩阵TS，大小为M×M，用于表示测试任务执行的先后顺序，若TS(m,m′)＝1则测试任务t

S102：测试任务编码：

编码方式决定了个体上基因的表现形式以及选择、交叉、变异的执行，常见的对基因进行编码方式有二进制编码、格雷码编码、实数编码等。本发明所需解决的是任务调度问题，采用实数编码的方式更加适用于实际情况。但是由于本发明中存在任务约束，因此在编码时还需要考虑任务约束的限制。因此，本发明中测试任务编码的具体方法为：

采用实数编码的方式对测试任务进行编码，在编码过程中如果任务约束矩阵中TS(m,m′)＝1时，表示测试任务t

假设测试任务集中包含10个测试任务，即T＝{t

S103：初始化种群：

将测试任务的编码序列作为遗传算法的个体，对测试任务的编码进行K次随机排序生成K个编码序列，构成遗传算法的初始种群Q，K的值根据实际需要设置，记第i个个体为X

S104：计算初始种群相异度：

种群的多样性由种群的相异度进行表述的，在迭代的过程中，初始种群在整个解空间均匀分布，此时种群的多样性最丰富，相异度最大。随着迭代次数的增加，种群会向最优解方向进化，越来越多的个体会进化出最优解的特征，种群的多样性降低，相异度减小。本发明中，为了保证迭代过程中种群的多样性，需要根据相异度的变化来确定个体的交叉概率和变异概率，因此需要先计算初始种群的相异度D

对于当前种群，首先计算任意两个个体之间的相异程度d

其中，i＝1,2,…,K，j＝1,2,…,K，且i≠j，x

然后采用如下公式计算当前种群整体的相异度D：

S105：计算个体适应度：

在遗传算法中依靠个体的适应度值来评价个体的优劣，决定种群的进化方向。适应度函数根据具体问题的优化方向不同存在差异，本发明并行测试任务调度研究的目标是确定总测试时间达到最短的调度方案，因此使用总测试时间作为评价个体优劣的标准。本发明中计算当前种群Q中各个个体适应度的具体方法为：

根据个体中测试任务编码的顺序、测试时间集τ、任务资源矩阵TR和任务约束矩阵TS生成并行测试任务调度方案，获取该调度方案完成测试所需时间TIME，然后采用如下公式计算个体的适应度f：

f实际上是加速度比，即采用了并行测试后对于测试完成时间的加速程度，是评价并行测试完成测试所需时间长短的函数。那么显然在本发明中，适应度越大，个体越优。

对于并行测试任务调度方案的生成，本实施例采用如下方法生成：

根据个体中测试任务编码的顺序生成测试任务序列，当存在相同的测试任务编码时，根据任务约束矩阵TS确定相同测试任务编码对应的测试任务的顺序。设置一个甘特图，将测试资源集R＝{r

以10个测试任务、5种测试资源为例，任务资源矩阵TR如下：

测试时间集τ＝{1,1,1,2,1,1,1,1,1,1}，测试时间单位为秒，假设测试任务t

S106：判断是否满足终止条件，如果是，则进入步骤S111，否则进入步骤S107。

终止条件可以根据实际需要进行设置，一般有两种，一种是迭代次数达到最大迭代次数，另一种是最优个体适应度收敛。

S107：个体选择：

从当前种群Q中选择优势个体构成新种群Q

选择操作的目的是为了从种群中选择个体进行交叉与变异操作，本实施例中采用轮盘赌算法与精英保留策略进行选择，确保优势基因能够尽可能遗传给子代，产生更优秀子代的可能性也就更大，具体方法为：

设置参数A、B，令A+B＝K，采用轮盘赌算法从当前种群中选择A个个体加入新种群，然后将剩余个体按照适应度从大到小进行排序，选择前B个个体加入新种群。

轮盘赌算法是依据个体的适应度值进行选择，当个体的适应度值越大时，其被选择的概率就越大，使得优秀个体的基因遗传给子代的可能性更大。精英保留策略将一部分优秀个体直接选中，解决使用轮盘赌算法时优秀个体可能没有被选择的问题，使得新种群更加合理。

S108：个体交叉：

对新种群Q

采用步骤S104中的方法计算新种群Q

其中，p

交叉通过交叉两个父代部分基因片段得到子代，将自身的部分特征遗传给子代，以便增加种群多样性，提高全局搜索能力。本实施例中采用两点交叉方式，具体方法为：

1)随机选择需要交叉的父代以及交叉基因片段，记父代个体分别为p

2)初始化空白子代个体c

3)为了防止编码冲突，对于剩余基因片段采用如下方法处理：从父代个体p

图3是本实施例中个体交叉的示例图。如图3所示，选择位置[4:7]的基因片段作为交叉基因片段，然后交换交叉基因片段，个体中空白基因处采用“X”进行占位，然后将父代个体p

S109：个体变异：

对子代种群Q

采用步骤S104中的方法计算子代种群Q

其中，p

变异操作通过父代个体改变自身的某些基因来产生子代个体，以增加种群的多样性，可以在一定程度上避免局部最优的情况。本实施例中采用倒序变异方式，具体方法为：

在父代个体中随机选择变异基因片段，将该变异基因片段中测试任务编码进行倒序，生成新基因片段，从而得到子代个体。

图4是本实施例中个体变异的示例图。如图4所示，在该父代个体中选择变异基因片段[7,10,8,3]，然后倒序得到基因片段[3,8,10,7]。

根据本发明中交叉概率和变异概率的计算公式可知，在迭代前期，当前种群的相异度D与初始种群的相异度D

S110：令子代种群Q

S111：确定并行测试任务调度方案：

选择当前种群中适应度最大的个体，根据该个体中测试任务编码的顺序、测试时间集τ、任务资源矩阵TR和任务约束矩阵TS生成并行测试任务调度方案。

为了更好地说明本发明的技术效果，采用具体实例对本发明进行实验验证。

本实施例中以无人机的测试为例，无人机的并行测试由无人机平台管理系统地面测试设备中的自动测试系统完成，该无人机平台包含刹车子系统、动力子系统、温控子系统、配电子系统、电气子系统等，本实施例中针对以上5个子系统共计设置了15项测试任务，测试所涉及的资源共计7种，分别为模拟量输入板卡，模拟量输出板卡，离散量输入板卡，离散量输出板卡，电阻板卡，同步RS422板卡，异步RS422板卡，为了便于描述，用r

表1

根据表1得到测试任务集T＝{t

表2是本实施例中遗传算法的参数设置表。

表2

采用本发明得到的适应度最大的个体对应的测试任务序列为{8,2,14,9,6,3,1,10,12,13,5,11,15,7,4}。图5是本实施例中测试任务序列得到的并行测试甘特图。如图5所示，本实施例中并行测试的最大执行步数为10。根据并行测试甘特图可以得到本实施例的任务调度矩阵TP，其大小为7×10，其中每个元素表示对应执行步骤中占用对应资源的测试任务。任务调度矩阵TP为：

该并行测试任务调度方案完成测试所需时间TIME为72秒，与最优调度方案用时相同，说明本发明可以有效解决并行测试任务调度问题。

在参数设置相同的情况下，将本发明和现有的AGA算法、IAGA算法、进行对比实验。图6是本发明和2种对比方法的种群相异度随迭代次数变化的对比图。从图6可以看出，种群相异度在初始时达到了最大。在迭代后期，AGA算法与IAGA算法的种群相异度在较小范围波动，种群多样性较小；而本发明种群相异度在较大范围波动，种群多样性较大。可见本发明在迭代的过程中维持了种群的多样性，说明了本发明设计的合理性。

图7是本发明和2种对比方法的最大适应度值随迭代次数变化的对比图。从图7可以看出，AGA算法与IAGA算法都出现了陷入局部最优解的情况，需要多次迭代才能跳出局部最优解，而本发明具有更好的跳出局部最优解的能力。

图8是本发明和2种对比方法得到最优解的概率随迭代次数变化的对比图。从图8可以看出，三种方法在迭代40次后找到最优解的概率趋于稳定，AGA算法稳定在约75％，IAGA算法稳定在约95％，本发明稳定在约99％，IAGA算法与本发明相比较于AGA算法有大幅度提升，本发明相比较于IAGA算法提升约4％。在迭代10次以前，本发明找到最优解的概率与IAGA算法相近；而在迭代10次以后，本发明找到最优解的概率优于IAGA算法，符合设计预期。

在最大迭代次数为50次时，将三种方法分别运行1000次，对结果进行统计。表2是本实施例中本发明和2种对方法的仿真结果对比表。

表2

如表2所示，本发明相比较于IAGA算法，在平均搜索时长不变的情况下，找到最优解的概率提高了约5.5％。

综上所述，本发明引入种群相异度自适应调节交叉与变异概率，改善了传统IAGA算法后期容易陷入局部最优的问题，提升了方法的收敛速度，有着更好的搜索性能，能够快速准确地获取并行测试任务调度方案。

尽管上面对本发明说明性的具体实施方式进行了描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。