旅行商问题求解程序的蜕变测试研究

刘艳平

摘要：随着计算机硬件运算性能的不断提升和分布式算法的应用，通过计算机进行求解复杂的数学问题变得可能。近些年，大数据、智能算法的兴起，计算机求解复杂的数学问题的速度和效果越来越成熟，相关的算法也成为一些软件的核心部分，测试实现这些算法的复杂程序的实现是否正确成为一个难点，也是当前的研究热点。以旅行商问题为例，构建了问题模型的蜕变关系，研究了蜕变测试的逻辑和实现，并通过变异分析测试蜕变关系的有效性，最后分析了不同蜕变关系检错的效能。

关键词：旅行商问题；黑盒测试；蜕变测试；变异算子

中图分类号 TP391 文献标识码 A 文章编号：1009-3044（2017）32-0080-03

Research on the Application of Metamorphic Testing to Tsp Solver Program

LIU Yan-ping

（PLA 91404 Unit， Qinhuangdao 066000， China）

Abstract： With the continuous improvement of computer performance and the application of distributed algorithm， complex mathematical problems solved by computer is feasible. In recent years， for the spring up of big data and intelligent algorithm， the speed and effect solving complex mathematical problems automatically are more satisfied， and related algorithms have become a core part of the software， to test such software correct or not is a difficulty， so how to test these software which integrate some complex algorithms also is research hotspots. Taking the traveling salesman problem as an example， this paper constructs the model transformation， makes a study on the implementation of metamorphic testing， and the effectiveness of metamorphic relation has been tested through mutation testing. Finally， capability of detecting faults with metamorphic relations are tested and analyzed.

Key words：TSP； metamorphic testing； mutation testing

旅行商问题（Travelling salesman problem， TSP）是指这样一个问题：一个旅行商推销员要去给定的若干城市去推销产品，每个城市只去一次，城市名称和城市之间的距离是已知量，推销员的行走路线和行走距离是未知量，现需要求解未知量的最小值，即求解旅行商推销员从某座城市出发，访问每一座城市一次并回到起始城市的最短距离。旅行商问题是一个典型的组合优化的完全NP问题，求解最短路径的算法复杂度为O（[n！]），随着顶点的增加，计算量爆炸式增长。旅行商问题经数学抽象建模再具体应用到入线路设计、物流配送路线规划、交通运输的建模方面，了众多的解法被研究和应用，例如动态规划法和分支界限法等传统方法，还有遗传算法、模拟退火算法等智能算法。在对基于某种算法的旅行商问题求解程序执行基于黑盒测试的功能测试时，由于枚举法等算法的计算量太大，人工无法手动求得期望解，不能对算法的解算结果进行评估，属于不可测程序。

为了解决这类测试判定的问题，Chen等提出了蜕变测试（ Metamorphic Testing，MT） 方法。这种测试方法的思路是，通过一般方法生成一组测试用例，然后研究问题模型，构造一种关系，在原来测试用例的基础上生成一组新的用例，用例之间的关系确定了程序输出之间的理论关系，通过验证程序输出组之间的实际关系和理论关系来判断程序是否正确，这种关系称为蜕变关系。

定義 1 蜕变关系。假设程序 P 是用于计算函数[f]的。[x1，x2，…，xnn>1]，是[f的n组]输入变量，这[n组]输入变量对应的函数输出结果为[fx1，fx2，…，f（xn）]。 若 [x1，x2…xn]满足关系[r]时，可以推出[fx1，fx2，…，f（xn）]之间满足关系[rf]，即：

[rx1，x2，…，xnrffx1，fx2，…，fxn] （1）

那么就称 [（r，rf]）是 P 的蜕变关系。

所以，如果程序 P 是正确的，那么它一定满足推导式（ 2）：

[rI1，I2，…，InrfPI1，PI2，…，PIn] （2）

式中： [I1，I2，…，In] 是程序 P 对应于 [x1，x2，…，xn]的实际输入，[PI1，PI2，…，PIn] 则是对应的输出结果。在测试具体程序时，通过检查表达式（ 2） 成立与否来验证程序 P 是否正确。由定义一可知，蜕变关系的核心是构造蜕变关系，蜕变关系构造的好坏基于对具体模型和问题的理解是否深入。endprint

定义2 原始 /衍生测试用例。基于蜕变关系[（r，rf）]对程序P进行测试时，需要若干组原始测试用例，这些用例可以由任意其他的用例生成的方法或算法获得，原始测试用例结合关系 r形成的一组新用例称为衍生测试用例。

现有的相关研究和实践表明，蜕变测试在黑盒测试的功能测试中能够有效解决测试判定问题的。张晶等研究了蜕变测试在聚类程序测试的应用，邱淑婷等研究了蜕变测试在求解常微分方程程序的应用。

1 旅行商问题建模

假设[C1x1，y1，C2x2，y2，…，Cnxn，yn]

[n>1]是地图上的n个点，任意两个点[Cixi，yi，Cj（xj，yj）]之间的距离[d（Ci，Cj）]计算方式为：

[d（Ci，Cj）=xi-xj2+yi-yj2 ] [（3）]

可以得到城市之间的距离方阵：

[D=0?d（C1，Cj）?d（C1，Cn）…?…?…d（Ci，C1）?0?dCi，Cn………?…d（Cn，C1）d（Cn，Cj）0] （4）

路径[R=c1…ci…cnr1…ri…ln]，[ri]为地点[ci]在路径R序列中顺时针出发的位置。

[路径的长度Rl]=[i=1n-1d（Ci，Ci+1）]。

2 构造蜕变关系

2.1 蜕变关系MR1

对所有位置点的坐标进行同等比例改变构建MR1。

根据公式（1）的定义，设原点为[P（x，y）]，坐标改变后的点为[P'（x'，y'）]，坐标改变为n倍，则[（x，y）和（x'，y'）]存在以下关系： [ x'，y'=（nx，xy）] （5）

点[C'i、C'j]之间的距离[d'（C'i，C'j）]和[点Cixi，yi、Cj（xj，yj）]之间[d（Ci，Cj）]的距离的关系为：

[ d'C'i，C'j=x'i2-x'j2+y'i2-y'j2=n（xi-xj）2+yi-yj2 ] （6）

所以[d'C'i，C'j=n d（Ci，Cj）]，设执行MR1后的路径长度为[R1l，则Rl=nR1l]。

2.2 蜕变关系MR2

根据三角形任意两边之和大于第三边的原理构造蜕变关系MR2。

假设图1为某旅行商问题的路线规划图，A、B、C为相邻的三点，那么根据三角形三边关系，则存在以下关系：

[ AB+BC>AC ] （7）

设[R2l]为图2对应的路径长度，可以得出：

[ Rl>R2l ] （8）

2.3 蜕变关系MR3

增加位置C的影子地点[C']构造蜕变关系MR3，[dC，C'=0]。

[C']为点[C]的影子点（[C'和C]具有相同的位置坐标，实际是重合的），设执行MR3后的路径长度为[R3l]，则可以得出：[Rl=R3l]。

2.4 蜕变关系MR4

根据使用贪婪算法求解旅行商问题并不能得到最优解构建MR4。

贪婪算法是这样一种算法，下一步的解是当前状态最优的选择，不考虑下一步之后的情况。贪婪算法并不从整体最优上加以考虑。贪婪算法求解旅行商问题的简要步骤如下：

Step1 选择任一个点为开始点和当前点，加入旅行路径；

Step2 选择和当前点相通的、距离最短、不在旅行路径的点作为下一点；

Step3 重复Step2，直到所有点都加入旅行路径；

Step4 把开始点，加入路径，完成路径选择；

Step5 从开始点开始，计算路径上相邻点之间的距离并求和，完成贪婪算法下的最短路径长度。

设贪婪算法求解旅行商问题得到的最短路径长度为[Rgl]，则存在[Rl≤Rgl]。

3 实例验证

通过变异测试的方法评估本文提出的蜕变关系的有效性。变异测试是一项通过对程序进行变异形成新的程序，在新的程序上执行测试用例，通过检测出变异体数量来衡量用例设计是否充分的测试技术。变异测试中，选择算子生成变异体是关键部分。

该算法基于遗传算法，并用C++开发。对遗传算法的求解TSP问题的基本原理进行分析后，判断程序中的循环、条件判定出现较多，是容易出现缺陷的地方。因此在程序中植入以下4种类型的变异算子：

M1： if条件变异（STRI），针对利用随机算法随机选择if语句条件，变异运算符；

M2： continue和break互换变异（SBRC，SCRB），针对continue和break语句进行替换操作，使用随机算法进行模拟程序员少量的continue和break使用错误；

M3：数组下标摆动变异（VTWD），模拟程序员可能存在的数据下标的[±1]的偏差。

M4：上/下移括号（SMVB），C++中的“}”意味着一个符合语句的结束，程序员可能把紧随循环体的一条语句“推入”循环体，也可能把循环体内的语句推出循环体。

M5： 算术运算符变异（OAAN），对程序中的+、-、*、/、+=、-=、*=、/=等运算符进行变异。

对源程序进行M1、M2、M3、M4、M5，采用TSPLIB的数据作为测试用例输入。分别用蜕变关系MR1、MR2、MR3、MR4执行5个变异体并进行测试，测试结果如表1所示。

表1中括号外的数字表示该列变异算子产生的变异体括号内的数字表示蜕变关系检测出的变异错误，针对每一个蜕变关系，都执行一遍变异算子，括号内的数字表示该行变异算子检测出的变异体数量，全部是指综合使用MR1、MR2、MR3、MR4四种蜕变关系生成蜕变用例，图4是蜕变关系检错能力统计表。endprint

从图4可以得出，不同的蜕变关系检测不同的变异算子的能力不同，MR1检错M4变异型的错误的能力最强，MR3检错M1、M2、M3变异型的错误的能力最强，MR4检错M5变异型的错误能力最强，MR3的综合检错能力最强，试验结果显示，将MR1、MR2、MR3、MR4综合应用会有较满意的检错效果。

4 结束语

传统的测试方法在算法程序测试中存在判定问题，尤其是在黑盒测试中，无法查看算法实现过程，不能测试算法的实现是否正确，现有的研究表明蜕变测试可以在一定程度上解决判定问题。本文提出将蜕变测试应用到旅行商求解程序的测试上，对问题模型进行深入研究后，构造了四个蜕变关系，通过构造变异算子测试，验证了蜕变关系是有效的，为该类程序的测试提供了思路和方法。蜕变关系的构造依赖具体的问题模型，变异算子的构造和开发语言密切相关，蜕变关系在神经网络、支持向量机等模型上的应用和面向对象语言的变异算子的构建，将是下一步研究内容。

参考文献：

[1] CHEN T Y，CHEUNG S C，YIU S M.Metamorphic testing： a new approach for generating next test cases[R].Hong Kong： Hong Kong University of Science and Technology，1998.

[2] 張晶，胡学钢，张斌. 基于蜕变关系的聚类程序测试方法[J]. 电子测量与仪器学报，2011（8）：688-694.

[3] 黄松，丁瑞浩，李辉，等. 坡度坡向量算程序蜕变测试方法[J]. 计算机应用， 2013（6）：1657-1661，1745.

[4] 饶卫振，金淳. 基于求解TSP问题的改进贪婪算法[J]. 运筹与管理，2012（6）：1-9.

[5] 陈翔，顾庆. 变异测试：原理、优化和应用[J]. 计算机科学与探索，2012（12）：1057-1075.

[6] 杜元柱，黄松，惠战伟，等. 基于变异分析的蜕变测试充分性条件[J]. 计算机应用，2014，34（S1）：280-283.

[7] 谢晓东，彭声明，刘艳，等. 蜕变关系敏感度及其聚类分析[J]. 电子学报，2016，44（5）：1196-1201.

[8] Aditya Mathura.软件测试基础教程[M].王峰，译.北京：机械工业出版社，2011：232-252.

[9] 王雪华. 基于变异测试的错误修正系统的设计与实现[D]. 哈尔滨：哈尔滨工业大学，2016.

[10] 中国电子信息产业发展研究院. 工业大数据测试与评价技术[M].北京：人民邮电出版社，2015：103-202.

[11] 侯淑静. 求解TSP问题的几种算法比较[J]. 黄冈职业技术学院学报，2015，17（1）：99-102.

[12] 秦备. 基于重要语句选择的变异测试数据生成[D].徐州：中国矿业大学，2016.

[13] 程勇，秦丹，杨光. 针对JavaScript浏览器兼容性的变异测试方法[J]. 计算机应用，2017，37（4）：1143-1148，1173.

[14] 巩敦卫，秦备，田甜. 基于语句重要度的变异测试对象选择方法[J]. 电子学报，2017，45（6）：1518-1522.endprint