基于梦境蚁群算法的车载VOBC测试案例约减策略研究

何涛，王婧

基于梦境蚁群算法的车载VOBC测试案例约减策略研究

何涛1, 2，王婧1

(1. 兰州交通大学 自动化与电气工程学院，甘肃 兰州 730070；2. 甘肃省工业交通自动化工程技术研究中心，甘肃 兰州 730070)

测试案例作为CBTC通用测试平台的基础，研究其约减策略，构建高效完备的测试案例集更加有助于CBTC系统的测试。提出梦境蚁群算法，在传统蚁群算法的信息素更新方式中引入做梦因子，并将其运用在车载VOBC的测试案例约减中，利用CBTC通用测试平台所用的有关测试案例集以matlab作为仿真平台对其进行验证，结果表明梦境蚁群算法能有效地减少测试案例数量，减少测试时间，节约测试成本，且减少比例比使用蚁群算法提高了10%。该算法为测试案例约减研究提供了新的方法，同时该算法扩大了解的搜索空间，能很好改善传统方法易产生局部最优的缺点，而且考虑了需求覆盖度和测试代价两重因素，使最后所得的测试案例集易行全面。

CBTC通用测试平台；车载VOBC；梦境蚁群算法；测试案例；约减

目前，城市轨道交通发展迅速，凭借其载客量大、速度快等优点，己经成为人们出行的优先选 择[1]。CBTC系统目前已广泛运用于城市轨道交通，它与乘客的生命财产安全有密切联系，在实际线试验之前必须经过严格的仿真测试，因此，有必要建立 CBTC 通用测试平台[2]。测试案例是测试平台的指导性文件，处于基础性地位，高效、完备的测试案例集可以更加科学地指导测试工作，节约测试成本[3]。本文以CBTC系统中的关键子系统车载VOBC为例，研究其测试案例约减算法。针对测试案例约减算法，国外提出了贪心算法、HGS算法、GRE算法和整数规划方法等。华丽等[4]提出贪心算法，即不断选取满足测试需求数最多的测试案例，同时划去需求集中相应的需求，直到测试需求集为空集为止；Harrold等[5]提出HGS算法，它依赖于测试案例的重要性来选择测试案例；CHEN等[6]提出GRE 算法，即先挑选必不可少的测试案例再剔除1-1冗余案例，再使用贪心算法直到所有需求都满足为止。有实验研究指出，在求解结果精度方面，以上3种方法各有特点，没有哪一种更优越，且约减后的测试案例集不一定都是优化代表集[7]。Lee等[8]提出整数规划法，但其计算复杂程度较高，运算开销呈指数级增长。聂长海等[9]在利用上述算法精简测试案例集时考虑测试需求之间的相互关系，但是没有考虑测试案例与测试需求之间的覆盖关 系。华丽[10]提出建立基于变异因子的蚁群算法的测试案例约减模型，算法中考虑测试案例的测试代价，有效地减少了测试案例集的数量，然而该算法容易产生早熟现象，所得到的结果质量仍需进一步提高，收敛速度和信息素多样性之间存在矛盾。为解决上述问题，本文提出一种梦境蚁群算法(Dream Ant Colony System, DACS)来约减车载VOBC的测试案例集，此方法可以扩大原有蚁群算法的搜索空间，有效解决算法早熟问题，实验结果表明，DACS能在充分考虑测试需求与测试案例之间的覆盖度的前提下有效减少测试案例集数目，并且能大幅度降低测试代价，节约测试时间。

1 VOBC功能需求分析

1.1 CBTC通用测试平台介绍

CBTC通用测试平台作为第3方全仿真自动化测试平台，可为研发轨道交通控制系统方面的企业提供黑盒测试和检测服务，能带来良好的经济效益与社会效益[2]。其结构如图1所示，由仿真子系统、适配子系统、DCS系统、测试子系统以及真实被测设备组成。由图1可看出测试案例是整个测试平台的基础，因此，研究测试案例的优化方法得到高效完备的测试案例有重要意义，而要想优化测试案例，前提是清楚系统的功能需求以及其与测试案例之间的满足关系。

图1 CBTC通用测试平台结构

图2 车载VOBC功能特征

1.2 VOBC的功能需求分析

车载VOBC是CBTC系统的安全核心子系统之一，是直接实现列车运行控制的关键设备，处于信息交互和命令传达的中枢位置，对保证城市轨道交通安全起着非常大的作用，故本文以车载VOBC为例分析研究其测试案例约减策略[3]。

如图1所示，车载VOBC系统与区域控制器(ZC)无线通信获得移动授权，通过应答器对其测得的位置信息进行校正，根据所获得的移动授权、列车位置以及从线路数据库获得的数据控制并防护列车运行。基于文献[11−13]总结其功能特征如图2所示，每一个2级功能还可以被细化为多个最小需求，任一最小需求都可被测试案例集中的某个测试案例充分测试，不存在多个测试案例测试一个最小需求。本文选取车载VOBC的核心功能超速防护功能来展示其需求细分过程。

超速防护功能是依据MA，障碍物信息，临时限速信息及事先储存的数据综合计算得到列车当前允许的最大速度，将它与车载测速模块实时测得的列车速度相比较以判断列车是否超速及是否要进行紧急制动。列车在CM模式下显示和防护触发速度和推荐速度，在AM和RM模式下只显示和防护触发速度。依据不同模式下超速防护功能的流程对需求进行细化，分别得到AM模式下12条最小需求，CM模式下14条最小需求，RM模式下10条最小需求，其中AM模式下车载超速防护功能的最小测试需求如下：

R_1.6.1 车载ATO设备正常工作；

R_1.6.2 有效列车位置，显示紧急制动速度；

R_1.6.3 列车位置丢失，输出紧急制动；

R_1.6.4 列车正常运行，车载设备未处于紧急制动状态；

R_1.6.5 如果列车处于紧急制动状态，需一直保持直到速度为0；

R_1.6.6 列车可以加速直到超过紧急制动触发速度；

R_1.6.7 如果列车速度没有降至0，需一直保持紧急制动；

R_1.6.8 列车速度能达到或超过紧急制动触发速度；

R_1.6.9 列车速度降至0，列车紧急制动缓解；

R_1.6.10列车超过紧急制动触发速度，输出紧急制动；

R_1.6.11列车紧急制动时，MMI显示红色图标，且速度下降；

R_1.6.12如果收到的MA突然回撤，列车速度超越了触发速度，输出紧急制动。

下文将针对AM模式下车载超速防护功能以及CM模式下退行防护功能的最小需求，选取CBTC通用测试平台所用的对应测试案例利用梦境蚁群算法进行约减研究。CM模式下退行防护功能的需求分析过程与超速防护功能类似，本文不再赘述。

2 梦境蚁群算法

2.1 蚁群算法

蚁群算法(ACS)是一种模拟蚂蚁觅食行为的优化算法，1991年由意大利学者Dorigo M首次提出。ACS的原理是蚂蚁在寻找食物的初期会随机选择路径同时释放浓度与路径长度成反比的信息素，之后的蚂蚁再选择路径时会选择信息素浓度较高的路径，如此循环最优路径上的信息素浓度就会越来越高，最终找到最佳觅食路径[10]。

信息素更新模式分为蚁周、蚁量和蚁密，其中蚁周模型已被证明优于另外2个，蚁周模型是在一次迭代后更新信息素，信息素与路径长度有关，可让长度短的路径上的信息素浓度增大。信息素更新公式为：

蚁群算法由于其正反馈性能使得蚁群最终找到最优解，同时也因为其信息素更新能力有限，使它容易陷入局部最优而过早停滞。针对这一缺点，本文提出梦境蚁群算法。

2.2 梦境蚁群算法

有关研究证明，自然界中的高级生命遵循白天黑夜的活动规律，白天生理活动，夜晚心理活动，Hobson等[14]提出了一种2阶段模型，并且指出人做梦的原因是脑干神经释放信号刺激大脑皮层区域，从而激活了人过去的记忆经验所致。

梦境蚁群算法(DACS)将上述梦境理论中的做梦因子用于蚁群算法的信息素更新中，用以扩大蚁群算法的搜索空间，促进其找到最优解，避免其早熟产生局部最优。假设蚂蚁遵循白天工作，夜晚睡觉的活动规律，每次迭代蚂蚁在分泌信息素时分成2个阶段，即白天和黑夜，白天蚂蚁正常分泌信息素，夜晚蚂蚁受其梦境的影响，扭曲其分泌在不同路径的信息素浓度，而且保证距离越短的路径受梦境扭曲的影响越小，如此使其他路径的信息素浓度与当前最优路径上的差距不大，利于扩大搜索空间，有机会找到更优的解。随着迭代次数的不断增加，受梦境的影响也会逐渐减弱，可以保证算法 收敛。

研究表明由于个体间存在差异，不同个体的睡眠周期不同，大约符合高斯分布[15]。故结合高斯分布和文献[16]中的梦境粒子群算法的做梦因子重新定义本文做梦因子：

其中：是蚂蚁编号；是蚂蚁的数量；是地点的数量。计算公式如下：

梦境蚁群算法的流程图如图3所示。

图3 梦境蚁群算法流程图

3 车载VOBC测试案例约减策略及验证

3.1 车载VOBC测试案例约减策略

d越小，说明测试案例所满足的测试需求数越多或其测试代价越小，由式(1)所算得的转移概率就越大，蚂蚁就会从测试案例转移到测试案例处，如此蚁群便开始在解空间内移动，蚂蚁每到达一个测试案例处就会将其所满足的需求从测试需求集中删除，直到测试需求集为空时，蚂蚁在本次迭代中任务结束，记录此次迭代蚂蚁所到达过的测试案例，且计算蚂蚁所走的路程，当所有蚂蚁都完成任务时，迭代结束，多次迭代之后找到路程最短的测试案例集，即完全覆盖需求且所需测试代价最低的测试案例集′。

表1 测试案例与测试需求关系

表1中需求1，2，3，…，12为AM模式下速度防护功能的需求R_1.6.1至R_1.6.12，案例1，2，3，…，12为CBTC通用测试平台中与其所对应的测试案例TC-Sys-13-001至TC-Sys-13-012，“1”表示对应测试案例满足相应测试需求。

梦境蚁群算法解模型如图4。

图4 梦境蚁群算法解模型

基于以上介绍，现将梦境蚁群算法(DACS)解决车载VOBC速度防护功能的测试案例约减的算法步骤描述如下：

1) 初始化VOBC速度防护功能的需求矩阵、车载VOBC速度防护功能的测试案例坐标矩阵，需求与测试案例满足关系矩阵以及各参数包括：迭代次数，最大迭代次数NC_max，蚂蚁个数，协调因子和，挥发系数，常量，信息素矩阵Tau以及做梦参数；

2) 将只蚂蚁随机放到不同的测试案例上准备出发；

3) 第只蚂蚁由于做梦因子影响根据公式(6)扭曲测试案例到其他测试案例之间的路径上的信息素浓度；

4) 第只蚂蚁从测试案例出发，计算蚂蚁从测试案例到其余各测试案例的转移概率，它将向概率最大的测试案例移动，将它所到达的测试案例所满足的需求从需求矩阵中清零；

5) 若需求矩阵中还有不为0的元素，则返回步骤4)，否则记录第只蚂蚁所经过的测试案例编号和它所走过的路程，，若不大于，返回步骤3)；

5) 比较所有蚂蚁所找到的解，记录当前最优解，利用式(7)进行信息素更新；

6) 若还没到达NC_max，且解还在变化，则+1，=1返回步骤2)，否则输出最优解，程序结束。

7) 步骤2)和3)属于夜晚的梦境信息素更新过程，而步骤4)到6)属于白天蚁群正常工作过程。

3.2 DACS算法的验证与结果分析

在matlab环境下参考中铁检验认证中心城轨事业部开发的CBTC通用测试平台中有关AM模式下，速度防护功能的测试案例集TC-Sys-13-001至TC-Sys-13-012和CM模式下退行防护功能的测试案例集TC-Sys-14-001至TC-Sys-14-013，利用DACS和ACS分别进行多次仿真实验，以验证DACS算法的有效性和可靠性。

图5 速度防护ACS算法测试案例优化结果

图6 速度防护DACS算法测试案例优化结果

图5~6为AM模式下速度防护功能的蚁群算法和梦境蚁群算法的优化结果。共有原始测试案例数12个，由于有2个测试案例4和8坐标相同，所以图中原始测试案例集个数仅显出11个测试案例。由图5可知，用ACS算法约减后速度防护功能的测试案例数减少了5个，约减比例为41.7%，所得到的最短距离为66.25，由图6可知，运用DACS算法约减后测试案例数减少了6个，约减比例为50.0%，所得到的最短距离为56.25。

图7 退行防护ACS算法测试案例优化结果

图7~8为CM模式下退行防护功能的蚁群算法和梦境蚁群算法的优化结果。共有原始测试案例数13个，运用ACS算法约减后测试案例数减少了8个，约减比例为61.5%，所得到的最短距离为39.666 7，运用DACS算法约减后测试案例数减少了9个，约减比例为69.2%，所得到的最短距离为30.5。

图8 退行防护DACS算法测试案例优化结果

根据以上分析可以得出蚁群算法和梦境蚁群算法均能有效减少测试案例数量。虽然对于不同功能的测试案例约减的比例不同，但是运用梦境蚁群算法得到的最短距离均比运用蚁群算法得到的最短距离低，且约减比例均提高了10%左右。由此证明使用引入做梦因子的DACS算法所得到的结果质量更优。

另外本文运用DACS算法分别对2个功能特征的测试案例集进行5次约减，发现每组的约减比例和最短距离都基本一致，速度防护功能约减比例为50%，最短距离为56.25，退行防护功能的约减比例为69.2%，最短距离为30.5，充分证明DACS算法能保证需求的前提条件下有效缩减测试案例数量，且一定程度地反映了其可靠性。

图9为使用ACS算法和DACS算法约减AM模式下速度防护功能测试案例迭代100次每次迭代之后的平均值，可以看出ACS算法每次迭代的平均值大约在132.086上下波动，DACS算法每次迭代的平均值大约在135.138上下波动，据此分析可知ACS算法每次迭代的平均值比DACS算法的低的数量居多，侧面证明由ACS算法所得到的结果有可能由于过早收敛使得其后面的数据都停留在局部最优解上，同时也可以说明DACS算法确实扩大了解的搜索空间。

图9 2种算法平均距离比较结果

图10 2种算法效果对比图

图10为2种算法约减AM模式下速度防护功能测试案例最终结果的效果对比，可以看到迭代100次由ACS算法得到的结果从第10次迭代就已经收敛了，产生过早停滞现象，而DACS算法从75才开始收敛，且得到的最短路径比前者低，因此引入做梦因子使得信息素更新更为随机，一定程度上减少了最优路径上信息素的更新，扩大了搜索空间，改善了算法的早熟缺陷。

3.3 DACS算法参数影响

DACS算法主要是在ACS算法中引入做梦因子使ACS算法的搜索空间增大的改进ACS算法，因此本节仅讨论有关做梦因子的参数影响。当测试案例集给定，蚁群编号给定时权重因子和蚂蚁编号c就确定，而′又受蚁群数量的影响，所以只有蚁群数量和迭代次数NC_max会对优化结果产生影响，表2为不同参数取值利用DACS算法约减CM模式下退行防护功能的测试案例所得到的结果对比。

表2 参数m和NC_max取不同值所获最优解的比较

表2中括号中的数字代表约减后测试案例集个数，如第5行第4列的值为29.8(4)代表迭代120次，蚁群数量为15时得到的最短路径为29.8，约减后的测试案例集数量为4。当迭代次数和蚁群数量都比较小时，得到的结果不是很好，而当蚁群数量m为13，即当蚁群数量等于原始测试案例集数量，且迭代次数为80次时，利用DACS算法所得到的测试案例约减集的数量最小，此时再增加蚁群数量和迭代次数所影响的是最短路径的大小，即约减后的测试案例集的测试代价。由于考虑算法的时间性能，建议m取与原始测试案例集数量相同，迭代次数NC_max取[80,100]即可。

4 结论

1) 介绍CBTC通用测试平台的结构，并且分析了其核心子系统VOBC的功能特征。

2) 改进传统蚁群算法，将做梦因子引入其中，提出梦境蚁群算法(DACS)，将其运用于测试案例的约减方面，并且利用CBTC通用测试平台中的车载VOBC的速度防护功能的测试案例集验证其正确性。结果表明DACS能很好地约减测试案例数量，比传统方法约减效果更好，特别在数据规模较大时更显其优势，而且同时考虑测试代价和需求覆盖程度，使得所得到的最优测试案例集既百分百覆盖需求又没有执行困难的案例。

3) 针对蚁群算法的不足之处，提出引入做梦因子，增加搜索选择，有助于解决蚁群算法过早停滞问题，避免了局部最优。

[1] 刘晓娟, 张雁鹏, 汤自安. 城市轨道交通智能控制系统[M]. 北京: 中国铁道出版社, 2008. LIU Xiaojuan, ZHANG Yanpeng, TANG Zian. Urban rail transit intelligent control system[M]. Beijing: China Railway Press, 2008.

[2] 党佳, 王玮琦. CBTC系统测试平台进入全面调试阶段[J]. 铁道技术监督, 2018, 46(7): 17. DANG Jia, WANG Weiqi. CBTC system test platform enters the full debugging stage[J]. Railway Quality Control, 2018, 46(7): 17.

[3] 胡巍巍. CBTC车载系统测试案例设计及优化方法研究[D]. 北京: 北京交通大学, 2010. HU Weiwei. Research on the method of test cases generation and optimization for CBTC on-board system[D]. Beijing: Beijing Jiaotong University, 2010.

[4] 华丽, 李晓月, 王成勇, 等. 能提高错误检测能力的回归测试用例集约简[J]. 湖南科技大学学报(自然科学版), 2015, 30(2): 99−103. HUA Li, LI Xiaoyue, WANG Chengyong, et al. Regression test suite reduction on improving fault detection capability[J]. Journal of Hunan University of Science &Technology (Natural Science Edition), 2015, 30(2): 99−103.

[5] Harrold M J, Gupta R, Soffa M L. A methodology for controlling the size of a test suite. ACM Trans[J]. Software Engineering and Methodology, 1993, 2(3): 270−285.

[6] CHEN T Y, Lau M F. On the divide-and-conquer approach towards test suite reduction[J]. Information Science, 2003, 42(1): 17−25.

[7] CHEN T Y, Lau M F. A simulation study on some heuristics for test suite reduction[J]. Information and Software Technology, 1998, 40: 777−787.

[8] Lee J G, Chung C G. An optimal representaive set selection method[J]. Information and Software Technology, 2000, 42(1): 17−25.

[9] 聂长海, 徐宝文. 一种最小测试用例集生成方法[J]. 计算机学报, 2003, 26(12): 1690−1695. NIE Changhai, XU Baowen. A minimal test suite generation method[J]. Chinese Journal of Computers, 2003, 26(12): 1690−1695.

[10] 华丽. 基于蚁群算法的测试用例集约简技术研究[D].重庆: 西南大学, 2009. HUA Li. The research of test-suite reduction technology based on ant colony algorithm[D]. Chongqing: Southwest University, 2009.

[11] 中交协10号, 城市轨道交通CBTC信号系统行业技术规范−需求规范[S]. China Transportation Association No.10, Technical specification of communication based train control system for urban rail transit requirements specification[S].

[12] CZJS/T 0028—2015, 城市轨道交通CBTC信号系统-ATP子系统规范[S]. CZIS/T 0028—2015, Technical specification of communication based train control system for urban rail transit-ATP subsystem specification[S].

[13] Fitzmaurice M. Wayside communications: CBTC data communications subsystems[J]. Vehicular Technology Magazine, IEEE, 2013, 8(3): 73−80.

[14] Hobson J A, Pace-schott E F. The cognitive neuroscience of sleep: Neuronal systems, consciousness and learning[J]. Nature Reviews Neuroscience, 2002, 3(9): 579−693.

[15] ErinJ Wamsley, Matthew Tucker, Jessica D Payne, et al. Dreaming of a learning task is associated with enhanced sleep-dependent memory consolidation[J]. Current Biology, 2010, 20(9): 850−855.

[16] 陈漠. 用于最优化问题的改进粒子群优化算法研究[D].吉林: 吉林大学, 2015. CHEN Mo. Research on improved particle swarm optimization algorithms for optimization problems[D]. Jilin: Jinlin University, 2015.

Research on the reduction strategy of vehicle VOBC test cases based on DACS

HE Tao1, 2, WANG Jing1

(1. School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China;2. Gansu Research Center of Automation Engineering Technology for Industry &Transportation, Lanzhou 730070, China)

As the basis of the CBTC Universal Test Platform, test cases were studied to reduce its reduction strategy. It is important to study reduction strategy of test cases and building efficient and complete test cases is more conductive to the testing of the CBTC system. Dream Ant Colony System (DACS) was proposed in this paper, which introduced the dream factor in the pheromone update method of the traditional ant colony algorithm, applied it to reducing test cases of the Vehicle on-board Controller and verified its effectiveness using the matlab platform and the relevant test case set used by the universal test platform of CBTC. The results show that the dream ant colony algorithm can effectively reduce the number of test cases, reduce test time and save test costs and its reduction ratio is 10% higher than the ant colony algorithm. The algorithm expands the search space of the solution, which can effectively improve the shortcomings called local optimum of the traditional method. Moreover, the algorithm considers the two factors of demand coverage and test cost, so that the final test case set has 100% coverage and is easy to execute.

CBTC universal test platform; VOBC; DACS; test case; reduction

TP206

A

1672 − 7029(2020)04 − 0832 − 09

10.19713/j.cnki.43−1423/u.T20190549

2019−06−20

中国国家铁路集团有限公司科技研究开发计划项目(N2019G017)；兰州市人才创新创业项目(2019-RC-107)；甘肃省工业交通自动化工程技术研究中心2019年开放基金项目(GSITA201902)

何涛(1977−)，男，内蒙古商都人，教授，从事轨道交通测试研究；E−mail：34876758@qq.com

(编辑 阳丽霞)