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

路 辉,王诗琪,申泽鹏

(北京航空航天大学 电子信息工程学院，北京 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之间的相似性，相似性越高，问题的多模特性就越强。

在明确问题多模特性之后，需要根据问题特性，提出相应的多目标多模优化方法。多目标问题的特点在于解在目标空间和决策空间中的分布是不同的。目标空间中距离相近的解在决策空间中可能并不相近。在现存大多数多目标优化算法中，只考虑了目标空间解的分布，在目标空间进行拥挤距离排序时，会淘汰距离相近的、被支配的解，即使这些解在决策空间中可能并不相近。这就让决策空间解多样性的保持非常困难[5]。若要使算法可以解决多目标多模优化问题，找到多个对应于目标空间的同一个帕累托前沿的决策空间中的解[9],保证解在决策空间的多样性，就需要添加一定的策略。

现有算法大多数采取以下3种策略：(1)引入小生境策略以保证决策空间与目标空间解的多样性。如Yue等在MOPSO基础上引入环形拓扑策略，以形成稳定的小生境[10]。Liang等将小生境策略引入NSGA-Ⅱ算法中以保证决策空间中解的多样性，提出DN-NSGAⅡ算法[5]。Liang等利用自组织地图网络聚类相似的解，在决策空间产生小生境[11]。李国森等引入参考点策略，利用佳点集原理[12]产生均匀分布的参考点，每个参考点与其附近的粒子构成小生境[13]。Liu等利用收敛性和多样性双档案集，在多样性档案集中采取聚类策略以保证算法多样性[14]。(2)加入指标控制决策空间中解的分布。不再将目标空间中解的拥挤度作为淘汰解的唯一评价。如Deb等提出的Omni-optimizer算法将目标空间用于拥挤距离排序的指标CD(crowding distance)引入决策空间中[15]，用以保持决策空间的多样性。Liang等将先对决策空间中的解进行非支配排序，然后进行拥挤距离排序[5]。Yue等在决策空间拥挤度距离排序的基础上提出特殊拥挤度距离这一概念(special crowding distance，SCD)，综合考虑决策空间和目标空间解的拥挤度排序[10]。(3)加入变异操作，防止粒子早熟，增加算法多样性。如文献[13]所提出的RPMOPSO算法，当过多粒子集中于某一个参考点附近时，加入变异策略让粒子飞出所在区域。Dong等在粒子群算法中加入全局自适应突变选择算子(AMS)，以提高粒子的搜索能力[16]。这些算法在目标空间表现相似，因为在进行非支配排序时都考虑了目标空间中解的分布，但在决策空间表现各有差别，且这些算法没有进行实际大规模问题的测试。

综上，目前研究在理论层面缺少对于问题是否具有多模特性的证明，从而无法针对问题的特性选择合适的优化算法。在算法层面，目前存在的多目标多模优化算法有几个缺点：一是对于小生境策略，一般需要很多复杂的参数(如小生境半径)，而算法结果对于这些参数的设置非常敏感，在对问题无先验知识的情况下对参数进行合适的设置比较困难；二是很多算法无法做到同时考虑决策空间的拥挤距离和目标空间的拥挤距离，因此无法同时保持在决策空间以及目标空间的多样性，并且针对维度更大、PS更多的大规模的问题表现不佳；三是现存的算法缺少对于维度大、离散程度大、真实前沿少的实际问题的测试。

本文主要包含以下两方面工作。第一，提出分析问题多模特性的方法，突破实际问题多模特性的分析和证明，形成多模特性的证明方法。其主要思路是直接利用多目标多模的概念，即证明决策空间中不同的PS对应的PF之间的相似性，由于动态时间弯曲可以不受两个被比较序列点数必须一致的限制，能有效处理两个序列某一维度上发生平移、伸缩后相似性比较的问题，因此将其引入多模特性分析领域，用于比较不同PF之间的相似性，从而证明问题的多模特性。第二，提出基于区域迁移的多目标粒子群优化算法(RMMOPSO)，引入多种群策略、区域迁移策略、精英池策略和淘汰策略。多个子种群在决策空间中并行搜索，将迭代过程分为搜索阶段和转移阶段。在搜索阶段时子种群中粒子向本种群全局最优点收敛；在转移阶段，按顺序交换各子种群全局最优点，使子种群搜索区域发生转移，从而每个子种群都可以搜索到完整决策空间。算法兼具多样性与收敛性，并且可以得到多个对应于同一个PF的不同PS。算法的优势在于不需要复杂的参数设置，不需要问题的先验知识，并且可以兼顾决策空间和目标空间的多样性，对于大规模问题和实际问题也具有较好的效果。

1 测试任务调度问题

1.1 测试任务调度问题的描述

对于测试任务调度问题来说，测试过程可能有多个测试任务，这些测试任务可能有先后要求，一个测试任务可能存在多种测试方案，每一种测试方案所占用的测试资源也不同。TTSP所要解决的，是合理安排n个测试任务到m个测试资源上，确定测试任务的测试顺序和每个测试任务的测试方案，以达到一定的设计目标[17]。这些目标可能是测试时间最短、资源利用率最大、负载耗能最少等，一般选择的两个目标是f1(测试时间最小)以及f2(各步平均负荷最小)[1]。

1.2 编码方法

编码是将问题转化为数学模型，并进行求解的基础。染色体编码是将所研究的问题的解用染色体的形式来表达，利用染色体可以进行变异交叉等操作。本文采用文献[18]所提出的IES(integrated encoding scheme)编码方式，将测试任务排序和测试方案的选择体现在同一条染色体上，提高编码效率，降低复杂性。

基本思想是利用决策变量不同维度之间的大小关系表示测试任务顺序，用决策变量的值来表示所采用的测试方案。一个n×mTTSP实例的决策空间有n维，每一维都是[0,1]之间的一个数。n维决策空间中的一个解表示为：(x1,x2,…,xn),xl∈[0,1]，将x1,x2,…,xn从小到大进行排序，xl的排序序号就是其所对应的测试任务号。接下来，根据决策变量xl的值和其所对应的测试任务ti，依据式(1)计算出ti所采用的测试方案：

(1)

其中ki是测试任务ti所对应的测试方案总数。表1给出了一个4×4 TTSP实例的编码过程。

表1 4×4 TTSP实例编码

1.3 TTSP的多模特性

在之前的研究工作中，课题组成员提出利用空间适应度地形对不同规模TTSP实例的多模特性进行分析的方法，对于较小规模TTSP实例(如4×5、6×8)，采取遍历的方法，对于遍历得到的数据进行统计分析，并给出空间适应度地形，来分析问题的多模特性[4]。表2给出了4×5与6×8 TTSP实例解空间的统计结果,其中:NsoluD表示决策空间中解的数量;NsoluO表示目标空间中解的数量;RD/O=NsoluD/NsoluO，表示平均每个目标空间中的解会对应多少个决策空间中的解;NpareO表示目标空间中帕累托前沿中解的数量;NpareD表示每个帕累托前沿在决策空间对应解的数量。4×5与6×8 TTSP实例所对应的RD/O值均大于1，即平均每个目标空间中的解会对应多个决策空间中的解。且NpareD比NpareO大很多，也说明目标空间中帕累托前沿对应着多个决策空间中的解。

表2 小规模TTSP实例解空间统计结果

图1给出了4×5与6×8 TTSP实例的空间适应度地形，可以看出两者的空间适应度地形存在很多平坦区域，即有很多不同的任务排序和方案选择对应于同一个适应度值，这也反映出TTSP问题的多模特性。

图1 小规模TTSP实例空间适应度地形

对于大规模TTSP问题，因其解空间巨大，无法进行遍历，因此采用随机区域采样的方法获得采样点，对采样点进行空间适应度地形分析，结果如图2所示(以20×8规模为例)。

图2 20×8 TTSP实例随即区域采样空间适应度地形

从图2可以看出，对于大规模TTSP问题，不同区域内适应度地形可能是不一样的，但同样表现出不同任务排序和方案选择对应于同一个适应度值的情况，因此大规模TTSP问题也具有很强的多模特性。

2 TTSP多目标多模特性分析

从空间适应度地形可以对TTSP问题是否具有多模特性进行分析，但如何有效证明问题特性是需要解决的问题。只有明确问题的多模特性，才能更好根据问题特性选择合适的算法或参数，达到效率高、鲁棒性好的目标，做到问题与算法的高度耦合[4]。本文针对这一问题，提出利用动态时间弯曲来计算不同PS对应的PF之间的相似性，用于证明问题的多模特性。

2.1 多目标多模特性描述

不失一般性，将多目标问题描述如下：

(2)

多目标多模优化问题可能存在两个或更多PS对应于同一个PF，如图3所示(以目标空间和决策空间为二维为例)。

图3 多目标问题多模特性示意图

可见，多目标优化问题多模特性证明的要点，就是证明决策空间存在多个不同的PS，对应于目标空间同一个PF。本文提出利用动态时间弯曲算法来证明问题的多模特性。

2.2 基于动态时间弯曲算法的多模特性分析方法

2.2.1 动态时间弯曲 动态时间弯曲[19]是在时间序列数据挖掘领域，利用距离比较时间序列相似性的算法[20]。相对于传统计算两个时间序列欧氏距离的方法，DTW可以有效处理时间序列沿时间轴伸缩、平移等变形的问题，找到两个时间序列之间最相近的点进行匹配，能更好反映两个时间序列之间的相似性，并且不需要两个时间序列的长度完全相等，具有较高的鲁棒性[21]。

如图4所示，单纯的欧式距离是将两个时间序列点与点之间的欧式距离进行累加，根据得到的距离和的大小来判断两个时间序列的相似性。显然这样的方法在时间序列沿时间轴发生平移或伸缩时是不准确的。

图4 欧式距离求时间序列相似性

DTW利用动态规划的思想，构造两个序列之间的距离阵，在距离矩阵中找到一个最佳匹配路径进行匹配，这个最佳匹配路径通过的距离矩阵中的元素累加和一定是最少的[22]。

假设时间序列P={p1,p2,…,pm}和Q={q1,q2,…,qn}，构造一个m×n的矩阵D(如图5a所示)。矩阵D中元素d(pi,qj)代表pi和qj间的距离

图5 时间序列DTW匹配路径与匹配结果

(3)

N为决策空间维度。

弯曲路径W需要满足:(1) 边界约束。弯曲路径W必须起始于(1,1)，终止于(m,n)，即P的第一个点必须和Q的第一个点匹配，P的最后一个点必须和Q的最后一个点匹配。(2) 单调性约束。弯曲路径元素wk(i,j)和其相邻元素wk+1(i′,j′)必须满足i

(4)

K为弯曲路径中元素个数。DTW的求解采用了动态规划的回溯思想：

DTW(i,j)=d(pi,qj)+

(5)

DTW得到两个序列间的匹配结果如图5b所示。

两个时间序列的DTW值越小，说明两个时间序列越相似。DTW因为其动态匹配特性，可以将两个具有不同长度的时间序列进行匹配，较好排除伸缩平移等操作的影响。

对于多目标多模特性证明问题，要比较不同PS对应的PF之间的相似性，PF的点数不同，但形状可能是相似的，因此将DTW用于比较PF的相似性从而证明多目标问题的多模特性。大多数多目标问题的目标空间都是二维的，将其视为时间序列的时间轴与幅度轴，就可计算两个PF之间的DTW值。

2.2.2 多目标多模特性分析方法 利用DTW来证明问题的多模特性的主要思路是：将求解问题在决策空间进行分组，求出每一组的PF后，利用DTW计算出不同组PF与标准PF的DTW距离(适用于标准PF已知的标准测试函数问题)或组与组PF之间的DTW距离(适用于标准PF未知的实际问题)，通过比较PF的相似性来证明算法的多模特性。DTW值越小，问题的多模特性越强。图6给出了多目标多模分析的流程图。

图6 多目标多模特性证明流程

2.3 多目标多模特性分析

求解每一组的PF时可采取任意多目标优化算法，本文采取MO_Ring_PSO_SCD来进行求解，并将分组数设为4组，算法进行30次取平均值，下面给出对于标准测试函数以及TTSP问题多模特性的证明结果。

2.3.1 标准测试函数 表3展示了在将决策空间分为4组的前提下，标准测试函数多模特性证明结果。从每一组PF与标准PF的DTW值和平均DTW值来看，标准测试函数都有比较强的多模特性。

表3 标准测试函数多模特性分析结果

图7和图8展示了MMF1的标准PF与标准PS，以及4组PF与PS，不同颜色代表不同组别。在决策空间中，4组PS没有交叠，但在目标空间中，4组PF均分布在(1,0)—(0,1)的一条弧线上，与标准PF具有很强的相似性。其他测试函数与MMF1同理。

图7 MMF1多模特性证明结果图(PF)

图8 MMF1多模特性证明结果图(PS)

DTW值越小，说明不同PS对应的PF的相似性越高，说明问题的多模特性越强。从表3结果可以看出，MMF1-MMF7的DTW值较小，多模特性相对较强，SYM-PRAT simple与SYM-PART rotated的DTW值相对较大。这可能有两种原因：该问题的多模特性比较弱;求解出的每一组的前沿质量不高。多模特性的证明结果与所选择的求解每一组前沿的算法有很大的关系，当问题规模比较大时，如果算法的收敛性或多样性不足，会影响每一组前沿的求解质量，从而影响到DTW值的计算和问题多模特性的证明。比如对SYM-PRAT simple与SYM-PART rotated，当前沿求解质量不好时，DTW值会偏大。

2.3.2 TTSP 表4给出了TTSP不同规模实例多模特性证明结果。可以看到对于规模较小的问题如4×8和5×8，每一组PS之间的DTW值都为0，即所有组找到的前沿完全一样，显然4×8与5×8规模的TTSP问题是具有多模特性的。对于更大规模的问题如20×8、30×12、40×8,DTW值稍大。但从上面对于TTSP进行空间适应度地形分析来看，高维度的TTSP实例依然具有很强的多模特性。通过对找到的采样解进行分析，发现DTW值大的原因是：当问题规模较大、寻找采样解的方法收敛性不够好时，影响每一组找到前沿的质量，影响到分析结果。

表4 TTSP不同规模实例多模特性证明结果

3 多目标多模优化算法

3.1 算法框架

本文提出基于区域迁移策略的多目标粒子群优化算法(multi-objective particle swarm optimizer based on regional migration strategy，RMMOPSO)，以适用于解决多目标多模问题，即找到多个不同的PS对应于同一个PF。该算法的主要思想是令多个种群在决策空间并行独立搜索，种群之间进行信息交互，使得每个种群都可以找到一个良好的PF，且在决策空间各PS并不相同。算法针对TTSP的多目标多模特性主要采取以下4个策略:(1)多种群策略。将决策空间分为N组，每组中有一个子种群并行独立搜索，以通过子种群数量来增加算法在决策空间的多样性。(2)区域迁移策略。种群之间利用全局最优解进行信息交互，引导每个子种群的搜索区域不断发生转移，使所有子种群可以搜索到完整搜索空间，从而找到多个不同的PS对应于同一个前沿，使算法具有多模特性。(3)精英池策略。将每个阶段每个子种群搜索到的精英解都保存在精英池中。(4)淘汰策略。将精英池中的粒子进行非支配排序，淘汰排序靠后的粒子。

图9给出了RMMOPSO的算法框图(以4个子种群为例)。

图9 RMMOPSO算法框图

下面将主要介绍本算法两个核心策略：多种群策略与区域迁移策略。

3.2 多种群策略

多种群策略将决策空间分为互不相交的N个区域，作为N个子种群的初始搜索区域。N个子种群在各自的搜索区域内并行独立搜索，产生种群内部的全局最优解gbest，进行精英解的保存。

子种群的个数可以根据问题的维度和每一维度的长度进行调整。当某一维度范围很广或有较多维度时，可以适当增加子种群个数。算法采用网格状将决策空间分组。例如，当子种群数为N=2m时，可以利用决策空间的前m维进行分组。当分为4组时，用前两维进行分组，其他维度各组保持一致，如图10a所示；当子种群数为8时，用前决策空间前3维进行分组，其他维度各组保持一致，如图10b所示。

图10 将决策空间分组示意图

子种群采用基于特殊拥挤距离排序的MOPSO算法进行迭代。

策略伪代码如表5所示。其中:N代表子种群个数;i表示子种群的序号;range_ui表示子种群i的初始搜索范围上界;range_li表示子种群i的初始搜索范围下界;gbesti表示子种群i产生的种群内部的全局最优解;n_var表示决策空间维度;Global_range_u(1,n_var)表示全局搜索范围上界;Global_range_l(1,n_var)表示全局搜索范围下界;skip1与skip2分别表示维度1与维度2上子种群的搜索范围;archivei表示子种群i的精英池;Iteration表示当前迭代次数;MAXIteration表示该子种群总迭代次数。

表5 多种群策略伪代码

3.3 区域迁移策略

为了能使N个子种群可以在全局范围内都进行搜索，并且利用好其他种群的经验，使每个种群都能找到对应于较好前沿的不同PS，引入区域迁移策略，顺时针轮流交换子种群的gbesti，使得各个种群可以在决策空间内轮转起来。将整个算法分为搜索阶段和转移阶段。

在搜索阶段，子种群i粒子的速度按式(6)来更新：

vikt=wvik(t-1)+c1(pbestik(t-1))+c2gbesti(t-1)。

(6)

式中：vikt表示子种群i中，第k个粒子第t次迭代的速度；pbestik(t-1)为子种群i中，第k个粒子第(t-1)次迭代后个体历史最优解的坐标;gbesti(t-1)表示子种群i中第(t-1)次迭代后本种群全局最优解坐标;c1与c2分别为个体和全局学习因子。此时，粒子在gbesti引导下，会不断向本种群全局最优解收敛，故本文称为搜索阶段。

在转移阶段，N个子种群的全局最优解进行交换，交换顺序为[gbestN→gbest1→gbest2→…→gbestN-2→gbestN-1]，即交换后，子种群1用于更新粒子速度的全局最优解为上一搜索阶段子种群N迭代得到的gbestN；同理，子种群2用于更新粒子速度的全局最优解为上一搜索阶段子种群1迭代得到的gbest1，子种群i粒子的速度和位置按式(7)来更新：

vikt=wvik(t-1)+c1(pbestik(t-1))+c2gbestj。

(7)

式中gbestj指子种群j上个搜索阶段迭代产生的全局最优解。子种群i在gbestj的引导下，会向gbestj所在区域不断收敛，即向子种群j上个搜索阶段所在区域转移，故本文称为转移阶段。转移阶段不仅可以起到让子种群进行转移，尽可能搜索到完整的决策空间，还可以起到交流种群间经验的作用。gbestj为子种群j上个搜索阶段所产生的种群经验，用此来引导子种群i转移，可以增加算法收敛性。

表6给出了区域迁移策略的伪代码(以子种群个数为4为例)。其中N代表子种群个数，i表示子种群序号；Gbest=[gbest4;gbest1;gbest2;gbest3]是子种群gbest的和矩阵，完成子种群间gbest交换的功能；Loop表示(搜索过程+转移过程)执行次数，为了让所有子种群搜索到完整决策空间，Loop与子种群数相同；Iteralion表示当前迭代次数；MAXIterationsearch表示子种群每次搜索阶段的总迭代次数;MAXIterationtrans表示子种群每次转移阶段的总迭代次数。

表6 区域迁移策略伪代码

MAXIterationsearch、Loop、MAXIterationtrans之间满足如下关系：在有4个子种群的情况下，一般让子种群可以完整循环一圈，即一般令Loop=4,MAXIteration为算法的总迭代次数，那么有式(8)：

MAXIteration=Loop×(MAXIterationsearch+

MAXIterationtrans)。

(8)

4 仿真与性能分析

本文选择了11个标准测试函数与不同规模的TTSP实例来测试算法表现，将RMMOPSO与MO_Ring_PSO_SCD算法进行对比，选择指标Hv、PSP及SP来衡量算法表现，并给出对于RMMOPSO所具有的多模特性的分析。下面主要介绍实验的测试函数、参数设置和说明、评价指标、实验结果以及对实验结果的分析。

4.1 测试函数

对于标准测试函数，本文选择了文献[10]所设计的11个经典多目标多模测试函数：MMF1—MMF8，以及SYM-PART simple、SYM-PART rotated和Omni-test。这些函数都具有多模特性，但决策空间的维度以及同一个PF对应的PS的个数不同。其中MMF1—MMF8、SYM-PART simple、SYM-PART rotated决策空间为2维；SYM-PART simple、SYM-PART rotated较复杂，有9个PS对应于同一个PF，SYM-PART rotated的PS相对于SYM-PART simple发生了旋转，求解更加困难；Omni-test决策空间为3维，有27个PS对应于同一个PF，是最复杂的一个测试函数。

对于测试任务调度问题，本文选择4×8、5×8、6×8、30×12和40×12实例作为测试函数，据上文分析可知，它们具有多模特性、真实前沿少、离散程度大的特征，且决策空间规模维度不断增大，适合于检验算法的收敛性与多样性。

4.2 评价指标

为了衡量算法在目标空间和决策空间的多样性和收敛性，采取超体积指标(hypervolume, Hv)、SP来衡量目标空间算法性能，采取PSP[10]来衡量决策空间算法性能。其中PSP包含了解集覆盖率(cover rate, CR)[23]和决策空间的反向世代距离(inverse generation distance，IGDX)[24]，可以综合衡量算法在决策空间的收敛性与多样性。表7给出了这些指标的适用范围和条件。

表7 评价指标及它们的适用范围和条件

4.3 参数设置

目前多目标多模优化的主流算法有MO_Ring_PSO_SCD[10]、DN-NSGAⅡ[15]、Omni-optimizer[15]。文献[10]对MO_Ring_PSO_SCD算法与Omni-optimizer、DN-NSGAⅡ、NSGAⅡ、MOEAD、SPEA2进行了对比，在目标空间内，几个算法表现相差不大，在决策空间内，除了MMF7外，MO_Ring_PSO_SCD在所有算法中表现最好，所以本算法主要与MO_Ring_PSO_SCD算法进行比较。比较表7中的11个测试函数和不同规模TTSP实例，以分析算法在目标空间和决策空间的综合性能，并着重关注算法的多模性能，即能否找到多个PS对应于目标空间同一个PS。

为保证公平性，算法的所有参数设置同对比算法MO_Ring_PSO_SCD完全一致，采用文献[10]中推荐的参数：粒子总数设置为800，最大迭代次数为100。式(4)和(5)中的学习因子c1和c2都设置为2.05，惯性权重w设置为0.729 8。所有算法运行20次，对指标计算结果取平均值与方差。

对于RMMOPSO来说，当粒子总数为800，设置4个子种群并行搜索时，每个子种群的粒子数为200。根据式(8)，设置Loop=4，当MAXIteration=100时，我们选择MAXIterationsearch=12，MAXIterationtrans=13，以满足式(8)。

4.4 结果分析

本节主要给出RMMOPSO算法与MO_Ring_PSO_SCD算法在11个标准测试函数和不同规模TTSP问题对比的实验结果，并给出结果分析。

对于11个标准测试函数，选择指标Hv来衡量算法在目标空间的综合性能，选择PSP来衡量算法在决策空间的综合性能。Hv和PSP的值越大说明算法综合性能越优秀。对于TTSP实例，因为没有标准前沿，选择不需要标准前沿的Hv和SP来衡量算法性能。对于复杂的TTSP实例，目标空间解的综合性能可以反映出决策空间的多样性和收敛性。Hv越大、SP越小，说明算法的综合性能越好。

为了进一步说明算法的多样性，分别给出RMMOPSO每个子种群找到的前沿的指标。

4.4.1 标准测试函数实验结果 表8和表9给出了11个标准测试函数的实验结果，图11给出了11个测试函数PSP盒图。其中，RMMOPSO序号为1，MO_Ring_PSO_SCD序号为2。在目标空间内，RMMOPSO在MMF4和SYM-PART simple表现明显优于MO_Ring_PSO_SCD。对于其他测试函数，二者表现差距不大，这是因为二者在目标空间的排序、淘汰方式差别不大。RMMOPSO在目标空间中解的分布略优于MO_Ring_PSO_SCD。

图11 标准测试函数PSP盒图

表8 标准测试函数算法对比结果(Hv)

表9 标准测试函数算法对比结果(PSP)

在决策空间中，从PSP平均值来看，除了Omni-test函数RMMOPSO表现均优于MO_Ring_PSO_SCD。这说明RMMOPSO在决策空间中的解分布更均匀、覆盖率也更高，反映出RMMOPSO在低纬度测试函数中在决策空间表现良好，有很好的多样性。

图12以标准测试函数SYM-PART simple为例给出了RMMOPSO和MO_Ring_PSO_SCD所求得的PS与PF。可以明显看出，RMMOPSO在目标空间和决策空间中解的分布都要更均匀、更能覆盖标准前沿上的点。

图12 两种算法在SYM-PART simple下解得PS与PF对比

在更高维函数如Omni-test中，RMMOPSO在决策空间的表现不如MO_Ring_PSO_SCD。图13给出了两个算法对于Omni-test的求解结果。可以看到，在目标空间RMMOPSO求得解更均匀，覆盖率更好。但是在决策空间，绝大多数解聚集在几个区域，而其他区域解比较少。相反，MO_Ring_PSO_SCD在决策空间中的解分布更均匀，PSP指标表现更好。这是因为Omni-test函数有27个PS对应于同一个PF，且维度更高。如果我们仍然将决策空间分为4组，每组内将存在不止一个PS。而在算法迭代中的转移阶段，用于引导子种群i向目标区域发生转移的是之前在此目标区域搜索的子种群j的全局最优点gbestj，所以子种群i在转移时会不断收敛于gbestj；如果gbestj已经固定，这会使粒子群趋于早熟，且子种群i在本目标区域收敛得到的全局最优点gbesti还会引导下一个子种群向本区域收敛，因此会造成大多数种群集中在少数几个PS上。此时，应当根据问题规模增加子种群数量，从而达到更好的效果。后面4.4.3节将改变子种群个数，以标准测试函数Omni-test为例给出改变子种群数后的实验结果和分析。

图13 两种算法在Omni-test下解得PS与PF对比

从方差来看，RMMOPSO方差较大，鲁棒性不够高。这也是区域迁移策略带来的弊端。与上述对Omni-test函数实验结果分析一致，因为引导子种群搜素区域发生转移的是其他子种群的gbest，当第一个在目标区域搜索的粒子群早熟时，会造成算法迭代结束后整个解的质量变差，因此造成算法鲁棒性不高，方差较大。

4.4.2 TTSP实例实验结果 下面对不同规模TTSP实例进行实验分析。表10与表11给出了在不同规模TTSP实例下，RMMOPSO与MO_Ring_PSO_SCD对比的结果。

表10 不同规模TTSP实例算法对比结果(Hv)

表11 不同规模TTSP实例算法对比SP结果

在对RMMOPSO纵向比较来看，通过比较不同规模的TTSP实例可以发现，在4×8、5×8、6×8规模下，问题规模较小，目标空间前沿只有2个点，算法每次找到的点是一样的，因此方差为0。当问题规模逐渐增大时，指标Hv不断减小，指标SP不断增大，说明随着问题的增大，算法收敛性与多样性降低，此时需要增加迭代次数或者增加粒子数来增加算法的收敛性。RMMOPSO与MO_Ring_PSO_SCD比较，因为问题规模比较大，Hv值也比较大，所以两者算法性能相差不大。

4.4.3 区域迁移策略效果分析 本节主要对RMMOPSO算法提出的区域迁移策略的效果进行分析。

在区域转移策略的搜索阶段中，每个区域向着各自区域的全局最优点收敛，在本次搜索阶段结束，每个区域内的PF与PS都会被保存至精英池中，用以指导转移阶段子种群的转移，并且在下一个搜索阶段，该区域新的子种群会在上一个在此区域的子种群的搜索经验上继续搜索。

区域转移策略与精英池策略的结合可以使得每个子种群在每个区域的搜索经验都被保存下来并不断进行利用。因为有了这种经验的传递和指导，在完整算法迭代过程中，对于每一个区域来说，随着迭代次数的增加，该区域所搜索到的PF与PS是在不断收敛的，避免了区域迁移对于已找到前沿面的破坏。图14给出了对于MMF1，在分为4个子种群的情况下，对于区域1，在4次搜索阶段中分别获得的前沿面。

图14 MMF1测试函数区域1中4次搜索阶段获得的前沿面

可以看出，在4次搜索阶段不同子种群对于区域1的搜索后，获得的前沿面互相补充并不断向里推进。迭代完成后，经过去重、淘汰，最终获得完整的前沿面。由此也可以证明，RMMOPSO可以兼顾决策空间与目标空间的多样性和分布性。

4.4.4 子种群个数对算法的影响 下面以标准测试函数Omni-test和30×12 TTSP实例为例，改变子种群个数，将决策空间分为8组进行实验，分析子种群个数对于算法结果的影响。

决策空间分组方法参照3.2节。在区域迁移策略中，Loop、转移阶段和搜索阶段的迭代次数依然要满足式(8)。将总迭代次数增加一倍，变成200次，令MAXIterationsearch=25，MAXIterationtrans=25，其他参数保持不变。为了对比，将决策空间分为4组的情况也增加迭代次数至200次进行实验。表12和表13分别展示了对于Omni-test和30×12 TTSP实例的实验结果。 图15展示了不同子种群数量找到的PS的对比。

表12 Omni-test不同子种群数实验结果

表13 30×12 TTSP实例不同子种群数实验结果

图15 标准测试函数Omni-test下不同子种群数量找到的PS

从图15和表12可以看出，对于Omni-test函数，当增加子种群个数时，找到的PS明显更多，决策空间指标表现也更好。并且通过8个子种群200次迭代结果和4个子种群200次迭代结果对比可以看出，性能的提升并不是因为迭代次数的增加。但仍然存在决策空间中粒子都集中于部分区域的现象。

对于30×12 TTSP实例，增加子种群个数对算法收敛性改善并不明显，因为问题规模很大，即使增加分组个数，也无法搜索到更大范围的空间，因此对效果改善不明显，但此时增加迭代次数可以有效增加算法收敛性。

通过以上分析，在问题规模较大、维度较高时，适当增加迭代次数和粒子群个数有利于避免所有粒子收敛于少数几个PS上，从而得到更均匀、覆盖率更高的PS，提升算法性能。

4.4.5 算法多模特性分析 下面以标准测试函数SYM-PART simple与20×8 TTSP实例为例分析算法的多模特性。

图16展示了RMMOPSO在标准测试函数SYM-PART simple下4个子种群产生的PS与PF。

图16 RMMOPSO在SYM-PART simple 上各子种群求解结果

图17与表15展示了RMMOPSO在20×8 TTSP实例下4个子种群分别找到的前沿和这些前沿的Hv和SP指标。

表15 20×8 TTSP实例各子种群Hv、SP指标结果

图17 RMMOPSO在20×8 TTSP实例上各子种群求解结果

表14展示了4个子种群所得前沿的Hv指标。

表14 SYM-PART simple函数各子种群Hv指标结果

可以看出，对于标准测试函数，无论从PF的分布还是指标来看，4个子种群均能得到质量好的PF，且与之对应的PS并不相同，说明算法可以找到4个不完全相同的PS对应于目标空间同一个PF，算法具有较好的多样性。对于TTSP实例，可以看到，4个子种群分别找到的PF在目标空间找到的PF不能相互支配，且对应指标相似，这说明TTSP实例具有多模特性。子种群的指标相较于所有子种群汇总结果的指标略差，因为算法迭代总结果是所有子种群迭代得到的解中非支配排序靠前的粒子组成的，因此表现更好。

综上，通过对于低维度标准测试函数和小规模TTSP实例的测试，RMMOPSO在决策空间和目标空间的综合性能较好，但鲁棒性较差；对于大规模、高维度问题，可以适当增加子种群个数或者迭代次数。RMMOPSO还具有可以同时找到对应于目标空间同一个PF的不同PS的优点，具有求解多模问题的能力。

5 总结

本文针对测试任务调度问题的多模特性提出了基于动态时间弯曲的证明方法，通过比较决策空间不同区域对应的PF的相似性来判断问题的多模特性，通过对11个标准测试函数及不同规模TTSP实例的测试，发现该方法能很好反映问题的多模特性；但对于更复杂的问题，当求解算法的收敛性不够、求得前沿质量不高时，会影响到DTW计算结果。基于多模特性分析结果，本文提出基于区域迁移的粒子群多目标多模优化算法(RMMOPSO)，其中主要采用了多种群策略以及区域迁移策略。多种群策略可增加决策空间多样性，区域迁移策略可以使每个子种群都能找到对应于同一个PF的不同PS，以提升算法的多模特性。通过对11个标准测试函数和不同规模TTSP问题的测试，发现RMMOPSO在目标空间和决策空间都有较好的收敛性和多样性，并且能同时得到多个对应于目标空间同一个PF的不同PS。但算法容易造成误差累积，鲁棒性较差，且对于高维、大规模问题，需要适当增加子种群个数，以得到更好的结果。

下一步工作将从进一步提高算法鲁棒性的角度出发，将RMMOPSO算法与其他算法进行融合；从提升多样性和收敛性的角度，提升搜索区域的覆盖性以及解集的均匀性，从而更好地解决多目标多模测试任务调度问题，并可应用于其他领域中的调度问题。