CN-115617690-B - Parallel test task scheduling method based on improved adaptive genetic algorithm

CN115617690BCN 115617690 BCN115617690 BCN 115617690BCN-115617690-B

Abstract

The invention discloses a parallel test task scheduling method based on an improved self-adaptive genetic algorithm, which is characterized in that related data of a task to be tested of an electronic system is obtained, a real number coding mode is adopted to code the test task, the coding is limited by task constraint, a coding sequence of the test task is used as an individual of the genetic algorithm to execute the genetic algorithm, in the iterative process of the genetic algorithm, the cross probability and the variation probability of the individual are calculated based on the variation of the population dissimilarity, and the optimal individual is selected after the iteration is completed to obtain a final parallel test task scheduling scheme. The invention carries out self-adaptive value of the crossover and variation probability of the genetic algorithm through the population dissimilarity degree, solves the problem that the genetic algorithm is easy to fall into local optimum, improves the convergence speed of the genetic algorithm and the success rate of searching the optimum solution, and can rapidly and accurately calculate the optimum parallel test task scheduling scheme when solving the parallel test task scheduling problem.

Inventors

HAN YAO
JIANG RUI

Assignees

电子科技大学

Dates

Publication Date: 20260508
Application Date: 20221102

Claims (5)

1. The parallel test task scheduling method based on the improved adaptive genetic algorithm is characterized by comprising the following steps of: S1, designing a test task for a subsystem contained in an electronic system to be tested in parallel according to actual conditions, and acquiring related data of the parallel test of the electronic system, wherein the method comprises the following steps of: Test task set t= { T 1 ,t 2 ,···,t M }, where T m represents the mth test task, m=1, 2,..m, M represents the number of test tasks; A test time set τ= { τ 1 ,τ 2 ,···,τ M }, where τ m represents the time required to complete the mth test task; The test resource set r= { R 1 ,r 2 ,···,r N }, where R n represents the nth resource required for testing the test task set T, n=1, 2,..; The task resource matrix TR is m×n, and is used for indicating the situation that the resource is occupied, if TR (M, N) =1, the test task t m needs to occupy the resource r n during testing, and if TR (M, N) =0, the test task t m does not occupy the resource r n during testing; A task constraint matrix TS, the size of which is m×m, for indicating the execution sequence of the test task, where if TS (M, M ')=1, the test task t m needs to be executed before the test task t m′ , and if TS (M, M ')=0, the sequence of the test task t m and the test task t m′ is not limited, M ' =1, 2,..; S2, encoding the test task by adopting a real number encoding mode, wherein in the encoding process, if a task constraint matrix TS (m, m')=1, the execution sequence of the test task t m and the execution sequence of the test task t m′ are indicated, at the moment, the encoding of the test task t m and the encoding of the test task t m′ are the same, otherwise, the encoding of the test task t m and the encoding of the test task t m′ are different; s3, taking the coding sequence of the test task as an individual of the genetic algorithm, carrying out K times of random sequencing on the codes of the test task to generate K coding sequences, forming an initial population Q of the genetic algorithm, and recording the ith individual as X i ＝{x i,1 ,x i,2 ,···,x i,M },x i,m to represent the test task code carried out by the mth individual X i , wherein i=1, 2; S4, calculating the dissimilarity degree D 0 of the initial population, wherein the specific method for calculating the dissimilarity degree of the population is as follows: for the current population, the degree of dissimilarity d i,j between any two individuals is first calculated: wherein i=1, 2,..k, j=1, 2,..k, and i+.j, X i,m 、x j,m are each encoded for the test task performed by the mth of individuals X i 、X j in the current population; and then calculating the overall dissimilarity D of the current population by adopting the following formula: S5, calculating the fitness of each individual in the current population Q, wherein the specific method comprises the following steps: Generating a parallel test task scheduling scheme according to the sequence of test task codes in an individual, a test TIME set tau, a task resource matrix TR and a task constraint matrix TS, acquiring TIME TIME required by the scheduling scheme to finish the test, and calculating the fitness f of the individual by adopting the following formula: The greater the fitness, the better the individual; S6, judging whether a termination condition is met, if so, entering a step S11, otherwise, entering a step S7; s7, selecting preferred individuals from the current population Q to form a new population Q 1 ; S8, carrying out cross operation on individuals in the new population Q 1 to obtain a child population Q 2 , wherein the cross probability of each individual is calculated by adopting the following method: The dissimilarity D 1 of the new population Q 1 is calculated by the method in step S4, the fitness of each individual in the new population Q 1 is calculated by the method in step S5, and then the crossover probability of the individual is calculated by the following formula: wherein p c represents the crossover probability, p cmax is the preset maximum crossover probability, p cmin is the preset minimum crossover probability, f' is the larger value of the fitness of the two parent individuals performing crossover operation, f max is the maximum fitness value of the new population Q 1 , f avg is the average fitness value of the new population Q 1 , and γ is the preset minimum value; S9, carrying out mutation operation on individuals in the child population Q 2 to obtain a child population Q 3 , wherein the mutation probability of each individual is calculated by the following method: Calculating the dissimilarity D 2 of the child population Q 2 by adopting the method in the step S4, calculating the fitness of each individual in the child population Q 2 by adopting the method in the step S5, and then calculating the mutation probability of each individual in the child population Q 2 by adopting the following formula: wherein, p m is the variation probability, p mmax is the preset maximum variation probability, p mmin is the preset minimum variation probability, f is the fitness value of the variant individual, f ' max is the maximum fitness value of the child population Q 2 , and f' avg is the average fitness value of the child population Q 2 ; S10, making the offspring population Q 3 be the population Q, and returning to the step S5; S11, selecting an individual with the greatest adaptability in the current population, and generating a parallel test task scheduling scheme according to the sequence of test task codes in the individual, the test time set tau, the task resource matrix TR and the task constraint matrix TS.
2. The parallel test task scheduling method according to claim 1, wherein the generating method of the parallel test task scheduling scheme in step S5 is as follows: The method comprises the steps of generating a test task sequence according to the sequence of test task codes in an individual, determining the sequence of test tasks corresponding to the same test task codes according to a task constraint matrix TS when the same test task codes exist, setting a Gantt chart, taking N test resources in a test resource set R= { R 1 ,r 2 ,···,r N } as items of the Gantt chart, sequentially drawing work processes of each test task on the required resources according to the test task sequence in the Gantt chart according to the TIME required by each test task in a test TIME set tau and the resources required by each test task in the task resource matrix TR to obtain a serial test Gantt chart, then moving the test tasks to a movable forefront position according to the execution sequence of the test tasks in the serial test Gantt chart on the premise of not occupying the resources of the previous test tasks to obtain a parallel test Gantt chart, and obtaining a parallel test task scheduling scheme and a TIME TIME required by the test scheme according to the parallel test Gantt chart.
3. The parallel test task scheduling method according to claim 1, wherein the specific method selected individually in step S7 is as follows: setting parameters A, B to enable A+B=K, selecting A individuals from the current population to be added into the new population by adopting a roulette algorithm, then sequencing the rest individuals according to the fitness from large to small, and selecting B individuals before adding into the new population.
4. The parallel test task scheduling method according to claim 1, wherein the individual intersection in step S8 adopts two-point intersection, and the specific method is as follows: 1) Randomly selecting father and crossing gene fragments needing crossing, wherein father individuals are p 1 、p 2 , and the crossing gene fragments are respectively M 1 represents the start sequence number M 1 ,m 2 of the crossover gene fragment and M 2 ,1＜m 1 ≤m 2 < M of the crossover gene fragment; 2) Initializing blank offspring individual c 1 、c 2 , crossing gene segments of parent individual p 2 Filling in the position [ m 1 :m 2 ] of the offspring individual c 1 , and crossing the gene segment of the parent individual p 1 Filling into the child individual c 2 position [ m 1 :m 2 ]; 3) Crossover gene fragments from parent individuals p 1 The test task codes contained are deleted, and the remaining test task codes are sequentially filled into the positions [1:m 1 -1] and [ m 2 +1:M ] of the child individual c 1 , and similarly, the crossover gene fragment is deleted from the parent individual p 2 The test task codes contained are deleted and the remaining test task codes are sequentially padded to positions [1:m 1 -1] and [ m 2 +1:M ] of child individual c 2 .
5. The parallel test task scheduling method according to claim 1, wherein the individual variation in step S8 is a reverse variation, and the specific method is as follows: randomly selecting a variant gene segment from a parent individual, and carrying out reverse sequence on test task codes in the variant gene segment to generate a new gene segment, thereby obtaining a child individual.

Description

Parallel test task scheduling method based on improved adaptive genetic algorithm Technical Field The invention belongs to the technical field of electronic system testing, and particularly relates to a parallel test task scheduling method based on an improved adaptive genetic algorithm. Background With the continuous increase of the complexity of high-precision equipment such as industrial equipment, aerospace equipment and the like, new challenges are presented for the automatic test performance of a complex system. In particular, in the aerospace field, parameters to be tested are numerous and complicated, and high requirements on accuracy and instantaneity are provided. The parallel test improves the problems of low test efficiency, low resource utilization rate and the like of an automatic test system by calling corresponding resources and simultaneously testing a plurality of tasks. The parallel test needs to consider the problems of resource competition, system deadlock, starvation and the like, and the determination of a task scheduling scheme is a complete problem of a complex non-deterministic polynomial (non-DETERMINISTIC POLYNOMIAL, NP) with great optimization difficulty. The aim of the parallel test task scheduling problem research is to determine an optimal scheduling scheme, such as shortest test time, maximum execution value, load balancing and the like. At present, two research directions are mainly that an intelligent algorithm is only used, a scheduling scheme is solved through good global optimization performance of the intelligent algorithm, such as a particle swarm algorithm, a genetic algorithm, an ant colony algorithm, a manual bee swarm algorithm, a simulated annealing algorithm and the like, and a Petri network is used for combining with the intelligent algorithm, a scheduling process is modeled by means of strong modeling capacity of a Petri network model firstly, and then the scheduling scheme is solved by means of the intelligent algorithm. The genetic algorithm has the characteristics of excellent global searching capability, strong robustness, simple design and the like, has parallelism, and is naturally suitable for solving the optimization problem with parallelism such as parallel test task scheduling. However, the traditional genetic algorithm adopts fixed crossover and mutation probability, when crossover and mutation probability is smaller, the evolution speed of the population is lower, iteration times are increased, the convergence speed of the algorithm is reduced, the real-time performance of task scheduling is affected, when crossover and mutation probability is larger, the evolution speed of the population is too high, genes of some dominant individuals can be rapidly diffused in the population, the diversity of the population is lost, the situation of sinking into a local optimal solution easily occurs, the obtained scheduling scheme is not an optimal scheduling scheme, and the aim of optimization cannot be achieved. Aiming at the improvement of a genetic algorithm, srinivas and the like, an adaptive genetic algorithm (ADAPTIVE GENETIC algorithm, AGA) is provided for the first time, the algorithm adjusts the crossover and mutation probability according to the individual fitness value, so that the problem that the genetic algorithm falls into a local optimal solution is solved to a certain extent, but the algorithm can enable the crossover and mutation probability of a dominant individual with a large fitness value to be close to or equal to zero, so that the characteristics of the dominant individual are not inherited and fall into the local optimal solution. Ren Ziwu et al propose an improved adaptive genetic algorithm (improved ADAPTIVE GENETIC algorithm, IAGA) that ensures that all individuals have a minimum probability of crossing and mutation, but that when the fitness value of the individuals is close to the average fitness value and the number of individuals is large at the later stage of algorithm iteration, the probability of crossing and mutation is low for most individuals, reducing the evolution speed of the population. Disclosure of Invention The invention aims to overcome the defects of the prior art and provide a parallel test task scheduling method based on an improved adaptive genetic algorithm, which is used for adaptively taking the value of the crossover and variation probability of the genetic algorithm through population dissimilarity, so that the problem that the genetic algorithm is easy to fall into local optimum is solved, the convergence speed of the genetic algorithm is improved, and the success rate of searching an optimum solution is improved, so that the optimal parallel test task scheduling scheme can be rapidly and accurately solved when the parallel test task scheduling problem is solved. In order to achieve the above object, the parallel test task scheduling method based on the improved adaptive genetic algorithm of the present in