适应度地形机理驱动的动态测试任务调度理论研究

Dynamic test task scheduling problem is one kind of time-varying discrete optimization problem. The design of the scheduling theory is dependent on the specific intelligent optimization algorithm. The analysis of correlation between the problem and the theory is weak, and the prior knowledge of the solution space is insufficient. For quantification of the problem and using the solution space, this project focuses on dynamic fitness landscape analysis and research the influence of topological structure and features of solution space on the solving algorithm, and forms the scheduling theory related to the prior knowledge. Firstly, we propose the sampling theory based on the hybrid of linear feedback shift register and the preference choices considering the uniformity and coverage of landscape undulation area. Secondly, we investigate features of similarity, chaos and severity of landscape changes. We use the dynamic time warping, maximum Lyapunov exponent and the number of high frequency side-lobe to create the parameter system of the prior knowledge and the theory related the problem and theory based on fitness landscape. In addition, we propose the neighborhood and global forecast theory of solution space. We focus on the mapping mechanism from code space to problem space, and extend the scheduling theory from the aspect of prediction. Finally, we carry out the software and semi-physical simulation. The similar scheduling problems are used to compare with test task scheduling problem for the analysis of similarity of fitness landscape, and to explore the inherent relation among different scheduling problems. The research not only can perfect the dynamic scheduling theory, but also can provide technical support to the industrial test system.

动态测试任务调度是一种时变离散优化问题。目前类似问题求解依赖于智能优化框架，算法和问题缺少关联性分析，解空间先验知识利用不足。为定量待求解问题，充分利用解空间，本项目从动态适应度地形分析入手，研究解空间地形结构和特征对求解算法的影响，形成先验知识关联的调度问题求解理论。首先，综合解集均匀性与地形突变区域覆盖性，提出线性移位寄存器与偏好性选择结合的解空间采样理论；然后，提出动态适应度地形变化相似性、混沌性和尖锐性等特征，利用动态时间弯曲、最大Lyapunov 指数、高频旁瓣数等参数建立先验知识参数体系，形成基于适应度地形的问题和算法关联理论；再之，提出解空间邻域与全局预测思想，重点研究编码空间同解空间的映射方法，从预测的视角拓展问题求解理论；最后，利用软件与半实物仿真，分析动态测试任务调度和类似问题地形相似性，探讨此类问题的内在联系。本项目既能完善动态调度理论，又能为工业系统测试提供技术支持。

动态测试任务调度是一类时变组合优化问题，目前的求解理论依赖于智能优化算法框架、缺乏解空间先验知识，与问题特性耦合性不强，无法有效求解。本项目从动态适应度地形角度出发，研究测试任务调度问题的解空间拓扑结构以及特性，形成解空间的先验知识，并据此研究动态测试任务调度方法，形成基于适应度地形的问题和算法关联理论，最终形成融合问题特性分析、算法设计和参数调整的闭环研究体系。首先，从时域、频域和空域三个角度对解空间适应度地形特征进行分析。将采样解的适应度值看作时间序列，利用动态弯曲距离、有向图衡量适应度地形的时域相似性程度与尖锐性程度；基于傅里叶变换给出尖锐性等频域评价指标；基于字典排序法完成高维到低维的映射和可视化，提出坡度和中性比例的空域指标。最终，形成以尖锐性、相似性、中性为主要指标，振幅平稳性、周期性等为辅助指标的解空间适应度地形评价体系。其次，充分利用适应度地形分析得出的结论，设计了基于多中心多策略的单目标和多目标调度算法，并从前沿预测等角度针对动态调度过程给出解决方案。然后，针对调度算法存在的参数敏感性问题，以调度问题的解空间适应度地形特征参数为调整依据，在迭代过程中利用中性比例等特征指标作为反馈量，在算法执行过程中自适应调整参数的取值，有效解决了参数的选取问题，也进一步提升了算法的搜索能力。最后，搭建了从问题建模、解空间特性求解、调度方法设计与调度结果分析的一体化平台，建立了适应度地形驱动的调度问题求解框架和求解系统，为动态优化问题的研究提供了一种新颖的解决思路。本项目相关研究成果不但可以应用于航空、航天等领域的调度问题，提升装备性能和维修保障能力，也可以用于解决柔性车间调度等工业领域问题，目前已推广应用于船舶资源调度问题和综合模块化航空电子系统分区调度演示系统。本项目共发表学术论文19篇，其中SCI检索论文11篇，EI检索论文8篇，申请发明专利6项，培养研究生14人。