7.3.3 基于多种群粒子群算法的多目标测试用例优先级排序
1.算法的基本流程
在基于多种群粒子群算法的多目标测试用例优先级排序算法中,会建立多个副粒子群和1个主粒子群,多个副粒子群独立并行迭代,主粒子群会参照副粒子群的寻优结果进行自身种群的迭代,最后由主粒子群产生全局的测试用例优先级排序Pareto最优解集。算法的基本过程如算法7-3所示。
2.粒子编码方式和种群的初始化
(1)粒子编码方式
每个粒子表示一个测试用例排序序列,采用的编码方式为序列编码,即对于一个包含L个测试用例的测试用例集,每个粒子可以编码为一个长度为L的整数数组,数组中第i项的值表示序列中第i个执行的测试用例序号。
(2)种群初始化
算法需要对N(N＞2)个种群进行初始化,其中包含1个主粒子群,N-1个副粒子群。每个粒子群包含n(n＞2)个粒子。每个粒子随机初始化为L个测试用例编号的一种排列。
3.粒子位置和速度的更新
(1)交叉操作
在测试用例优先级排序问题中,针对粒子按照测试用例编号序列进行编码的方式,标准粒子群算法中的速度和位置更新公式(式(7-23)和式(7-24))不再适用。为此,文献[13]在求解多目标测试用例预优化问题时,已经将遗传算法中的交叉操作引入粒子群算法的粒子速度和位置更新操作中。本书采用了单点交叉操作对粒子的速度和位置进行更新。针对本书测试用例排序采用的粒子编码方式,单点交叉操作的基本流程如算法7-4所示。
(2)副粒子群中粒子位置和速度的更新(https://www.daowen.com)
多个副粒子群独立进化,每个粒子群中粒子的速度和位置按照式(7-27)~式(7-29)进行更新:
其中,k表示迭代次数,⊕表示交叉操作,p i(k)表示该粒子群中第i个粒子前k次迭代后的历史最优值,p g(k)表示该粒子群前k次迭代后的全局最优值,v′i(k+1)可以看作第k+1次迭代时的速度增量。式(7-28)表示将速度增量v′i(k+1)和粒子上一次迭代的速度v i(k)做交叉操作,得到新的速度v i(k+1)。式(7-29)表示将粒子上一次迭代的位置x i(k)和新的速度v i(k+1)做交叉操作,得到粒子新的位置x i(k+1)。
针对⊕交叉操作后会产生两个子代个体,如果两个子代个体不满足非支配关系,则选择较优的子代个体作为交叉结果;如果两个子代个体满足支配关系,则随机选取一个子代个体作为交叉结果。
需要说明的是,在算法7-3中,每一轮迭代,N-1个副粒子群的状态更新是依次进行的。由于N-1个副粒子群之间是独立进化的,所以N-1个副粒子群的状态更新是可以同时并行处理的,有利于提高算法的效率。所以为了陈述方便,算法7-3按照依次处理的方式书写。
(3)主粒子群中粒子位置和速度的更新
主粒子群中的粒子在状态更新时,会基于副粒子群的全局最优解集更新自己的速度和位置。首先,主粒子群中的粒子会根据式(7-30)计算第k+1次迭代的速度增量v′i(k+1):
其中,
(k)表示主种群中第i个粒子前k次迭代后的历史最优值,
(k)表示主种群前k次迭代后的全局最优值,
(k)表示全部副粒子群前k次迭代后的全局最优值。
然后,主粒子群中的粒子会根据式(7-28)和式(7-29)更新自己的速度和位置。需要说明的是,因为主粒子群中粒子需要根据全部副粒子群前k次迭代后的全局最优值p Sg(k)来计算速度增量,所以在一轮迭代中,主粒子群需要在全部副粒子群状态更新完毕后,才能进行状态更新。
4.全局最优解集和历史最优解集更新
在基于多种群协同粒子群算法的测试用例优先级排序算法(算法7-3)中,每个副粒子群需要维护自己种群的全局最优解集,每个粒子需要维护自己的历史最优解集,全部副粒子群需要维护副粒子群的全局最优解集,主粒子群需要维护自己的全局最优解集和每个粒子的历史最优解集。这些最优解集的维护过程大致相似,都可以看作一个新粒子加入时,根据目前最优解集中粒子与新粒子的支配关系,来更新Pareto最优解集。其基本流程如算法7-5所示。
