旅行商問題求解程序的蛻變測試研究

劉艷平

摘要：隨著計算機硬件運算性能的不斷提升和分布式算法的應(yīng)用，通過計算機進行求解復(fù)雜的數(shù)學(xué)問題變得可能。近些年，大數(shù)據(jù)、智能算法的興起，計算機求解復(fù)雜的數(shù)學(xué)問題的速度和效果越來越成熟，相關(guān)的算法也成為一些軟件的核心部分，測試實現(xiàn)這些算法的復(fù)雜程序的實現(xiàn)是否正確成為一個難點，也是當(dāng)前的研究熱點。以旅行商問題為例，構(gòu)建了問題模型的蛻變關(guān)系，研究了蛻變測試的邏輯和實現(xiàn)，并通過變異分析測試蛻變關(guān)系的有效性，最后分析了不同蛻變關(guān)系檢錯的效能。

關(guān)鍵詞：旅行商問題；黑盒測試；蛻變測試；變異算子

中圖分類號 TP391 文獻標(biāo)識碼 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）是指這樣一個問題：一個旅行商推銷員要去給定的若干城市去推銷產(chǎn)品，每個城市只去一次，城市名稱和城市之間的距離是已知量，推銷員的行走路線和行走距離是未知量，現(xiàn)需要求解未知量的最小值，即求解旅行商推銷員從某座城市出發(fā)，訪問每一座城市一次并回到起始城市的最短距離。旅行商問題是一個典型的組合優(yōu)化的完全NP問題，求解最短路徑的算法復(fù)雜度為O（[n！]），隨著頂點的增加，計算量爆炸式增長。旅行商問題經(jīng)數(shù)學(xué)抽象建模再具體應(yīng)用到入線路設(shè)計、物流配送路線規(guī)劃、交通運輸?shù)慕７矫?，了眾多的解法被研究和?yīng)用，例如動態(tài)規(guī)劃法和分支界限法等傳統(tǒng)方法，還有遺傳算法、模擬退火算法等智能算法。在對基于某種算法的旅行商問題求解程序執(zhí)行基于黑盒測試的功能測試時，由于枚舉法等算法的計算量太大，人工無法手動求得期望解，不能對算法的解算結(jié)果進行評估，屬于不可測程序。

為了解決這類測試判定的問題，Chen等提出了蛻變測試（ Metamorphic Testing，MT） 方法。這種測試方法的思路是，通過一般方法生成一組測試用例，然后研究問題模型，構(gòu)造一種關(guān)系，在原來測試用例的基礎(chǔ)上生成一組新的用例，用例之間的關(guān)系確定了程序輸出之間的理論關(guān)系，通過驗證程序輸出組之間的實際關(guān)系和理論關(guān)系來判斷程序是否正確，這種關(guān)系稱為蛻變關(guān)系。

定義 1 蛻變關(guān)系。假設(shè)程序 P 是用于計算函數(shù)[f]的。[x1，x2，…，xnn>1]，是[f的n組]輸入變量，這[n組]輸入變量對應(yīng)的函數(shù)輸出結(jié)果為[fx1，fx2，…，f（xn）]。 若 [x1，x2…xn]滿足關(guān)系[r]時，可以推出[fx1，fx2，…，f（xn）]之間滿足關(guān)系[rf]，即：

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

那么就稱 [（r，rf]）是 P 的蛻變關(guān)系。

所以，如果程序 P 是正確的，那么它一定滿足推導(dǎo)式（ 2）：

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

式中： [I1，I2，…，In] 是程序 P 對應(yīng)于 [x1，x2，…，xn]的實際輸入，[PI1，PI2，…，PIn] 則是對應(yīng)的輸出結(jié)果。在測試具體程序時，通過檢查表達式（ 2） 成立與否來驗證程序 P 是否正確。由定義一可知，蛻變關(guān)系的核心是構(gòu)造蛻變關(guān)系，蛻變關(guān)系構(gòu)造的好壞基于對具體模型和問題的理解是否深入。endprint

定義2 原始 /衍生測試用例?；谕懽冴P(guān)系[（r，rf）]對程序P進行測試時，需要若干組原始測試用例，這些用例可以由任意其他的用例生成的方法或算法獲得，原始測試用例結(jié)合關(guān)系 r形成的一組新用例稱為衍生測試用例。

現(xiàn)有的相關(guān)研究和實踐表明，蛻變測試在黑盒測試的功能測試中能夠有效解決測試判定問題的。張晶等研究了蛻變測試在聚類程序測試的應(yīng)用，邱淑婷等研究了蛻變測試在求解常微分方程程序的應(yīng)用。

1 旅行商問題建模

假設(shè)[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序列中順時針出發(fā)的位置。

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

2 構(gòu)造蛻變關(guān)系

2.1 蛻變關(guān)系MR1

對所有位置點的坐標(biāo)進行同等比例改變構(gòu)建MR1。

根據(jù)公式（1）的定義，設(shè)原點為[P（x，y）]，坐標(biāo)改變后的點為[P'（x'，y'）]，坐標(biāo)改變?yōu)閚倍，則[（x，y）和（x'，y'）]存在以下關(guān)系： [ x'，y'=（nx，xy）] （5）

點[C'i、C'j]之間的距離[d'（C'i，C'j）]和[點Cixi，yi、Cj（xj，yj）]之間[d（Ci，Cj）]的距離的關(guān)系為：

[ 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）]，設(shè)執(zhí)行MR1后的路徑長度為[R1l，則Rl=nR1l]。

2.2 蛻變關(guān)系MR2

根據(jù)三角形任意兩邊之和大于第三邊的原理構(gòu)造蛻變關(guān)系MR2。

假設(shè)圖1為某旅行商問題的路線規(guī)劃圖，A、B、C為相鄰的三點，那么根據(jù)三角形三邊關(guān)系，則存在以下關(guān)系：

[ AB+BC>AC ] （7）

設(shè)[R2l]為圖2對應(yīng)的路徑長度，可以得出：

[ Rl>R2l ] （8）

2.3 蛻變關(guān)系MR3

增加位置C的影子地點[C']構(gòu)造蛻變關(guān)系MR3，[dC，C'=0]。

[C']為點[C]的影子點（[C'和C]具有相同的位置坐標(biāo)，實際是重合的），設(shè)執(zhí)行MR3后的路徑長度為[R3l]，則可以得出：[Rl=R3l]。

2.4 蛻變關(guān)系MR4

根據(jù)使用貪婪算法求解旅行商問題并不能得到最優(yōu)解構(gòu)建MR4。

貪婪算法是這樣一種算法，下一步的解是當(dāng)前狀態(tài)最優(yōu)的選擇，不考慮下一步之后的情況。貪婪算法并不從整體最優(yōu)上加以考慮。貪婪算法求解旅行商問題的簡要步驟如下：

Step1 選擇任一個點為開始點和當(dāng)前點，加入旅行路徑；

Step2 選擇和當(dāng)前點相通的、距離最短、不在旅行路徑的點作為下一點；

Step3 重復(fù)Step2，直到所有點都加入旅行路徑；

Step4 把開始點，加入路徑，完成路徑選擇；

Step5 從開始點開始，計算路徑上相鄰點之間的距離并求和，完成貪婪算法下的最短路徑長度。

設(shè)貪婪算法求解旅行商問題得到的最短路徑長度為[Rgl]，則存在[Rl≤Rgl]。

3 實例驗證

通過變異測試的方法評估本文提出的蛻變關(guān)系的有效性。變異測試是一項通過對程序進行變異形成新的程序，在新的程序上執(zhí)行測試用例，通過檢測出變異體數(shù)量來衡量用例設(shè)計是否充分的測試技術(shù)。變異測試中，選擇算子生成變異體是關(guān)鍵部分。

該算法基于遺傳算法，并用C++開發(fā)。對遺傳算法的求解TSP問題的基本原理進行分析后，判斷程序中的循環(huán)、條件判定出現(xiàn)較多，是容易出現(xiàn)缺陷的地方。因此在程序中植入以下4種類型的變異算子：

M1： if條件變異（STRI），針對利用隨機算法隨機選擇if語句條件，變異運算符；

M2： continue和break互換變異（SBRC，SCRB），針對continue和break語句進行替換操作，使用隨機算法進行模擬程序員少量的continue和break使用錯誤；

M3：數(shù)組下標(biāo)擺動變異（VTWD），模擬程序員可能存在的數(shù)據(jù)下標(biāo)的[±1]的偏差。

M4：上/下移括號（SMVB），C++中的“}”意味著一個符合語句的結(jié)束，程序員可能把緊隨循環(huán)體的一條語句“推入”循環(huán)體，也可能把循環(huán)體內(nèi)的語句推出循環(huán)體。

M5： 算術(shù)運算符變異（OAAN），對程序中的+、-、*、/、+=、-=、*=、/=等運算符進行變異。

對源程序進行M1、M2、M3、M4、M5，采用TSPLIB的數(shù)據(jù)作為測試用例輸入。分別用蛻變關(guān)系MR1、MR2、MR3、MR4執(zhí)行5個變異體并進行測試，測試結(jié)果如表1所示。

表1中括號外的數(shù)字表示該列變異算子產(chǎn)生的變異體括號內(nèi)的數(shù)字表示蛻變關(guān)系檢測出的變異錯誤，針對每一個蛻變關(guān)系，都執(zhí)行一遍變異算子，括號內(nèi)的數(shù)字表示該行變異算子檢測出的變異體數(shù)量，全部是指綜合使用MR1、MR2、MR3、MR4四種蛻變關(guān)系生成蛻變用例，圖4是蛻變關(guān)系檢錯能力統(tǒng)計表。endprint

從圖4可以得出，不同的蛻變關(guān)系檢測不同的變異算子的能力不同，MR1檢錯M4變異型的錯誤的能力最強，MR3檢錯M1、M2、M3變異型的錯誤的能力最強，MR4檢錯M5變異型的錯誤能力最強，MR3的綜合檢錯能力最強，試驗結(jié)果顯示，將MR1、MR2、MR3、MR4綜合應(yīng)用會有較滿意的檢錯效果。

4 結(jié)束語

傳統(tǒng)的測試方法在算法程序測試中存在判定問題，尤其是在黑盒測試中，無法查看算法實現(xiàn)過程，不能測試算法的實現(xiàn)是否正確，現(xiàn)有的研究表明蛻變測試可以在一定程度上解決判定問題。本文提出將蛻變測試應(yīng)用到旅行商求解程序的測試上，對問題模型進行深入研究后，構(gòu)造了四個蛻變關(guān)系，通過構(gòu)造變異算子測試，驗證了蛻變關(guān)系是有效的，為該類程序的測試提供了思路和方法。蛻變關(guān)系的構(gòu)造依賴具體的問題模型，變異算子的構(gòu)造和開發(fā)語言密切相關(guān)，蛻變關(guān)系在神經(jīng)網(wǎng)絡(luò)、支持向量機等模型上的應(yīng)用和面向?qū)ο笳Z言的變異算子的構(gòu)建，將是下一步研究內(nèi)容。

參考文獻：

[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] 張晶，胡學(xué)鋼，張斌. 基于蛻變關(guān)系的聚類程序測試方法[J]. 電子測量與儀器學(xué)報，2011（8）：688-694.

[3] 黃松，丁瑞浩，李輝，等. 坡度坡向量算程序蛻變測試方法[J]. 計算機應(yīng)用， 2013（6）：1657-1661，1745.

[4] 饒衛(wèi)振，金淳. 基于求解TSP問題的改進貪婪算法[J]. 運籌與管理，2012（6）：1-9.

[5] 陳翔，顧慶. 變異測試：原理、優(yōu)化和應(yīng)用[J]. 計算機科學(xué)與探索，2012（12）：1057-1075.

[6] 杜元柱，黃松，惠戰(zhàn)偉，等. 基于變異分析的蛻變測試充分性條件[J]. 計算機應(yīng)用，2014，34（S1）：280-283.

[7] 謝曉東，彭聲明，劉艷，等. 蛻變關(guān)系敏感度及其聚類分析[J]. 電子學(xué)報，2016，44（5）：1196-1201.

[8] Aditya Mathura.軟件測試基礎(chǔ)教程[M].王峰，譯.北京：機械工業(yè)出版社，2011：232-252.

[9] 王雪華. 基于變異測試的錯誤修正系統(tǒng)的設(shè)計與實現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2016.

[10] 中國電子信息產(chǎn)業(yè)發(fā)展研究院. 工業(yè)大數(shù)據(jù)測試與評價技術(shù)[M].北京：人民郵電出版社，2015：103-202.

[11] 侯淑靜. 求解TSP問題的幾種算法比較[J]. 黃岡職業(yè)技術(shù)學(xué)院學(xué)報，2015，17（1）：99-102.

[12] 秦備. 基于重要語句選擇的變異測試數(shù)據(jù)生成[D].徐州：中國礦業(yè)大學(xué)，2016.

[13] 程勇，秦丹，楊光. 針對JavaScript瀏覽器兼容性的變異測試方法[J]. 計算機應(yīng)用，2017，37（4）：1143-1148，1173.

[14] 鞏敦衛(wèi)，秦備，田甜. 基于語句重要度的變異測試對象選擇方法[J]. 電子學(xué)報，2017，45（6）：1518-1522.endprint