基于区域迁移策略的测试任务调度问题多目标多模优化

路 辉,王诗琪,申泽鹏

(北京航空航天大学 电子信息工程学院，北京 100191)

自动测试系统因具有高速度、高精度、多功能、多参数和宽测量范围的优点在航空航天、汽车、移动通信等领域发挥着越来越重要的作用[1]。测试任务调度问题(test task scheduling problem，TTSP)是自动测试系统的关键技术之一，主要解决如何合理安排测试任务顺序和测试资源分配，以达到测试系统效率最大化、测试平均负荷最小等目标[2-3]的问题。TTSP问题是典型的多目标组合优化问题，真实前沿点较少且比较分散，存在多个决策空间的解集对应同一个目标空间的帕累托前沿(Pareto front，PF)，具有多模问题的特性[4]。本文通过对TTSP多目标多模特性的分析，研究相应的求解方法，为测试任务调度问题的研究提供补充。

2016年，Liang等将有多个决策空间中的解对应于目标空间同一个帕累托前沿的多目标问题称为多目标多模优化问题[5]。在现实生活中，路径规划问题、背包问题和调度问题等都可以抽象为多目标多模优化问题[6-8]。对于不同领域的实际问题，首先需要从问题特性的角度出发，从理论层面分析问题是否具有多模特性，设计与问题耦合程度最高的算法进而解决问题。目前在多模特性的理论分析方面，尚没有一套有效证明问题多模特性的方法。本文从时间序列相似性分析的角度出发，通过动态时间弯曲算法(dynamic time warping，DTW)，计算不同决策空间中的解(Pareto-optimal set，PS)对应目标空间中PF之间的相似性，相似性越高，问题的多模特性就越强。

在明确问题多模特性之后，需要根据问题特性，提出相应的多目标多模优化方法。……