基于Petri网和模拟退火遗传算法的并行测试研究

Research on parallel test based on Petri net and GASA algorithm

针对自动测试系统中并行测试任务调度复杂、难以优化的问题,提出了一种Petri网技术和模拟退火遗传算法相结合的任务调度优化算法。首先为并行测试系统建立时间Petri网模型,然后将激发的变迁序列集作为并行测试任务调度路径。为了得到最优路径,引入模拟退火遗传(GASA)算法进行搜索。在搜索过程中,将能激发的变迁序列作为染色体,进行选择、交叉和变异。为了防止算法出现收敛过早,陷入局部最优解的现象,还要对个体进行模拟退火操作,最后得到测试完成时间最短的任务调度序列。

Because parallel test task scheduling in automatic test system is complicated and difficult to optimize, a new method based on Petri net and GASA algorithm is proposed. At first, a timed Petri net model for the parallel test system is established, then the fired transition sequence is used as the task scheduling path of parallel test. In order to get the optimal path, the GASA algorithm is added to search. In the searching process, the fired transition sequence is used as chromosome. The selection, crossover and mutation of the genetic algorithm are applied to find the optimal sequence. In order to prevent the algorithm appearing early convergence or getting local optimal sequence, the simulated annealing algorithm is used to deal with the individuals. At last, the task scheduling sequence with the shortest test time is found.