基于DNA算法的硬实时系统预调度的研究

Research on Pre-run-time Scheduling of Hard Real-time System Based on DNA Algorithm

针对传统遗传算法在解决硬实时系统任务预调度问题时,存在早熟收敛现象,提出了一种基于DNA遗传算法的任务预调度序列搜索方法。该方法将复杂的任务调度问题转化为解决离散优化问题,利用任务的时间延迟作为目标函数,通过改进DNA遗传算法的变异算子对任务调度序列进行求解,并最终找到了具有可行性调度的最优解。仿真结果表明,所给出的搜索方法同传统遗传算法相比,具有更快的收敛速度。在初始群体规模相同的条件下,该方法的迭代次数仅为遗传算法的21.5%。

In the light of the drawbacks that conventional genetic algorithm converged at local optimum when applied in pre-runtime scheduling of hard real-time system, a search approach based on DNA Genetic algorithm was proposed. The approach selected the task delay as the objective function and improved the mutation operator of DNA genetic algorithm： The optimization solution of scheduling sequence of task was found. The results of simulation indicate that compared with the conventional algorithm, the proposed approach has better convergence rate. In the same size of initialize population, the iterative number of the proposed approach is only 21.5 percent of the conventional algorithm.