申情，蔣云良，沈張果，樓俊鋼

（湖州師范學(xué)院信息工程學(xué)院，浙江 湖州 313000）

基于組合混沌遺傳算法的最小測試用例集生成

申情，蔣云良，沈張果，樓俊鋼

（湖州師范學(xué)院信息工程學(xué)院，浙江 湖州 313000）

最 小 測 試 用 例 集 生 成 是 軟 件 測 試 的 重 要 研 究 領(lǐng) 域 之 一 。 將 具 有 均 勻 分 布 特 性 的 Chebyshev 和 Logistic混沌映射相結(jié)合的混沌序列引入遺傳算法的選擇、交叉和變異操作，并在遺傳測試用例選擇方法中添加混沌擾動，實現(xiàn)全局最優(yōu)，以解決遺傳算法用于測試用例集約簡時局部搜索能力弱、易早熟收斂等問題。 在隨機生成的測試用例需求對應(yīng)關(guān)系及 Siemens 測試套件等實例上進行了實驗研究， 并與現(xiàn)有的經(jīng)典方法在測試用例集生成規(guī)模和算法執(zhí)行時間上進行了比較，實驗結(jié)果表明，在保持算法執(zhí)行時間的基礎(chǔ)上，在遺傳測試用例方法中引入混沌映射有助于生成規(guī)模更小的測試用例集。

軟件測試；測試用例最小化；混沌遺傳算法；測試用例

1 引言

計算機系統(tǒng)已被應(yīng)用到社會生活各方面，軟件形式更加復(fù)雜多樣，規(guī)模越來越大。在這樣的背景下，保證軟件質(zhì)量，使其準(zhǔn)確完成預(yù)期目標(biāo)變得尤為重要。軟件測試是軟件質(zhì)量保證中必不可少的一部分，為滿足一定測試需求覆蓋率，生成的測試用例數(shù)目往往異常龐大；另一方面，軟件系統(tǒng)開發(fā)過程的迭代需要頻繁地進行回歸測試，測試冗余嚴(yán)重。為提高測試效率、降低測試成本，減少測試用例的執(zhí)行、管 理 與 維 護 的開 銷 ，測 試 用 例 集的 約 簡 是 極為 必 要 的［1-3］。

若 用 R=｛r1，r2，…，rk｝表 示 測 試 需 求 集 ，T=｛t1，t2，… ，tn｝表 示測試用例集，（其中，n 代表測試用例數(shù)量，k 代表需求數(shù)量 ）， 可 用 一 個 n×k 矩 陣 g［i］［j］來 表 示 測 試 用 例 ti與 測 試 需 求rj的覆蓋關(guān)系為：

其 中 ，g［i］［j］的 取 值 為 0 或 1，g［i］［j］=1 則 表 示 用 例 ti可 以 覆蓋 需 求 rj，g［i］［j］=0 表 示 用 例 ti不 能 覆 蓋 需 求 rj。測 試 用 例 最 小化生成問題可以描述如下，給出一個測試用例集 T、一個測試用例需求集 R，R 滿足給定程序要求的某種測試覆蓋準(zhǔn)則，T 可以完成對 R 中所有 ri的測試 ，要 求 從 T 中 找 到一個測試用例優(yōu)化集，可以滿足所有 ri的測試，需要 在大量的測試用例中篩選出最優(yōu)的測試用例，即能用最少的 測 試 用 例 覆 蓋 最 多 的 測 試 需 求［1］。

現(xiàn)有的最小測試用例生成方法主要包括啟發(fā)式方法，如 Harrold 和 Gupta 使 用 的 貪 心 算 法 和 啟 發(fā) 式 算 法［4］，Chen提 出 的 GE 和 GRE 算 法［5，6］；智 能 搜 索 方 法 ，如 邢 穎［7］采 用的 分 支 限 界 搜 索 以 及 爬 山 法 ，Windisch［8］、陳 翔 等 人［9］、王 令賽［10］、史 嬌 嬌［11］采 用 的 粒 子 群 優(yōu) 化 算 法 ，Harman、Jones、Lin、Berndt以 及 Michael使 用 的 遺 傳 算 法［12-18］等 ；其 他 方 法 還 包括 整 數(shù) 規(guī) 劃 算 法［19］、擴 張 集 算 法［20，21］、有 限 狀 態(tài) 機［22，23］等 。

其 中 ，遺 傳 算法（genetic algorithm，GA）由 于 其 良 好 的 全局搜索能力，在測試用例最小化生成中取得了較好的應(yīng)用，該算法借鑒達爾文的遺傳選擇和自然淘汰的生物進化理論完成對測試用例集約簡。遺傳算法最早由美國Michigan 大 學(xué)［24］的 Holland J 教 授 提 出 ，是 一 種 概 率 性 全 局優(yōu)化方法，其優(yōu)化對象不需可導(dǎo)或者連續(xù)，有較強的全局和并行性，能自動識別搜索過程中的有益信息以指導(dǎo)優(yōu)化過程，作為一種高效、并行、全局搜索尋優(yōu)的方法，具有很強的頑健性與適應(yīng)性，能解決傳統(tǒng)優(yōu)化方法難以解決的復(fù)雜優(yōu)化問題?；谶z傳算法的測試用例生成主要思想如下：首先對原始測試用例集進行編碼，在此基礎(chǔ)上產(chǎn)生若干個測試用例選擇方案，構(gòu)成初始化種群，種群個體即一種可能的測試用例選擇方案；然后從種群中選出兩個解，使用交叉算子生成新的解，利用測試覆蓋率、測試運行代價等評價個體優(yōu)劣；隨后不斷地用新個體替代種群中適應(yīng)值較差的個體，最后得到最優(yōu)的個體及最優(yōu)的測試用例選擇方案。

在 遺 傳 算 法 應(yīng) 用 于 測 試 用 例 最 小 化 問 題 研 究 上 ，Ma［14］把程序分為若干的塊或者段，用 0-1 關(guān)系表示被測程序塊和測試用例之間的滿足情況，設(shè)計個體編碼，然后利用測試 覆 蓋 率 與 測 試 開 銷 等 信 息 構(gòu) 造 適 應(yīng) 度 函 數(shù) ；Jones［15］用 實驗研究表明，遺傳算法生成的測試數(shù)據(jù)比隨機法小 1～2個數(shù) 量 級 ；Lin［16］使 用 廣 義 海 明 距 離 來 優(yōu) 化 遺 傳 測 試 用 例 方法 中 的 適 應(yīng) 度 函 數(shù) ，進 一 步 提 高 方 法 的 性 能 ；Berndt［17］將輸入空間劃分成多個區(qū)間，根據(jù)待選輸入的多種特性創(chuàng)建最 小 化 函 數(shù) ；Michael［13］結(jié) 合 覆 蓋 表 生 成 一 個 最 小 化 函 數(shù) ，采 用 微 分 遺 傳 算 法 進 行 全 局 尋 優(yōu) ；Khor［18］將 遺 傳 算 法 和 正規(guī) 概 念 分 析（formal concept analysis）相 結(jié) 合 ，進 行 測 試 用 例集 的 生 成 ；Berndt［17］通 過 模 擬 實 驗 等 方 法 分 析 了 各 種 基 于遺傳算法的測試用例生成方法的性能。

然而普通遺傳算法用于測試用例生成也存在局限性，如接近全局最優(yōu)解時搜索速度會變慢，個體多樣性減少較快導(dǎo)致早熟收斂等。針對此，利用混沌理論的遍歷性，提出一種基于組合混沌遺傳算法的最小測試用例集生成方法（minimized testcasegenerationbasedoncombinationchaosgeneticalgorithm，TCGCG）。采用一種結(jié)合 Chebyshev 混沌映射和 Logistic 混沌映 射 的 組 合 混 沌 序 列 產(chǎn) 生 方 法［25］，在 種 群 初 始 化 、 交 叉 和 變異的全過程中使用組合混沌序列，利用混沌序列增加各種運算過程的隨機均勻性，以降低同種群間個體的相似度，從而提升算法全局搜索能力；同時結(jié)合適應(yīng)度水平設(shè)計自適應(yīng)的交叉概率及變異概率選取策略，既保證適應(yīng)度較高的優(yōu)秀個體保留至下一代，保證了種群的多樣性，又提高適應(yīng)度較低個體的變異概率，加快算法收斂速度，降低時間消耗。

2 基于混沌遺傳算法的測試用例集約簡方法

提出的 TCGCG 方法利用組合混沌映射生成初始種群，每個種群個體包括 n 個基因，種群個體即一種可能的測試用例選擇方案，并將具有均勻分布特性的組合混沌序列引入遺傳算法的選擇、交叉和變異操作，有效地避免了未成熟收斂，提升算法的全局搜索能力和計算效率，混沌系統(tǒng)產(chǎn)生初始種群基因，然后對各個混沌變量附加混沌小擾動進行種群優(yōu)化，通過不斷進化收斂到一個最適合的個體上。從而將測試用例最小化轉(zhuǎn)化為在種群中尋找基因個數(shù)最少的個體覆蓋所有測試需求。

基于 TCGCG 的測試用例集最小生成方法的基本步驟如 圖 1 所 示 ，主 要 包 括 采 用 Chebyshev 映 射 和 Logistic 映射相結(jié)合生成混沌序列、利用混沌序列初始化種群、設(shè)定個體適應(yīng)度函數(shù)、計算個體適應(yīng)度、定義遺傳算子（選擇、交叉、變異）、添加混沌擾動等步驟。

圖1 TCGCG 用于測試用例集最小化生成的基本步驟

2.1 產(chǎn)生組合混沌序列

Chebyshev 映 射 ：xi+1=cos（karccosxi），xi∈［-1，1］，當(dāng) 映 射階數(shù) k≥2 時，系統(tǒng)處于混沌狀態(tài)，不同初值產(chǎn)生的序列間具有自相關(guān)性與零值互相關(guān)性。

Logistic 映 射 ：xi+1=μ·xi·（1-xi），對 初 值 敏 感 ，非 周 期 ，不收斂，μ=4 時處于完全混沌狀態(tài)。

采 用 Chebyshev 和 Logistic 混 沌 映 射 結(jié) 合 的 生 成 方 法 ：令 y0=x0為 初 始 值 ，使 用 Chebyshev 映 射 yi+1=cos（karccosyi）得 到 一 個 偽 隨 機 序 列 ｛y0，y1，y2，… ，yl｝，然 后 將 序 列 取 絕 對 值之 后 與 Logistic 映 射 求 和 temp=μxi（1-xi）+|yi+1|，每 次 迭 代 后采用映射 xi+1=mod（temp，1）保 證 混 沌 序 列 取 值 為（0，1），其中，mod（x，1）算子代表取實數(shù) x 的小數(shù)部分。生成混沌序列時，取 μ=4，k=4，可以保證序列完全混沌。該映射將Chebyshev映射和 Logistic 映射中的 兩 個 變 量 聯(lián) 系 起 來 ，以 父 代 混 沌 映射的結(jié)果作為子代混沌序列的種子值，提高了偽隨機數(shù)分布的均勻性，并形成統(tǒng)一的輸出序列。

2.2 利用混沌序列初始化種群

假設(shè)初始種群中個體數(shù)目為 M，未約簡前總測試用例數(shù)量為 n，則初始種群及種群中個體可分別表示為：

其中，P0表示初始種群，W 表示種群中的個體，Wi表示初始種群中的第 i個初始個體，gj表示該個體上的第 j號染色體。采用第 2.1 節(jié)的方法由 M 個不同初值產(chǎn)生 M 個長 度 均 為 n 的 混 沌 序 列 ，對 W1，W2，…，WM上 的 染 色 體 進 行賦值，方法如下：

由此完成初始種群中個體的初始化。gj=1 表示第 j號染色體對應(yīng)的測試用例 被選中，gj=0 表示未被選中 ，一個個體基因編碼可以表示所有測試用例是否被選中。

2.3 個體適應(yīng)度函數(shù)

當(dāng)個體編碼改變時需重新計算其適應(yīng)度，使用傳統(tǒng)適應(yīng)度函數(shù)計算式，針對本文的基因編碼方式將適應(yīng)度計算的對象變?yōu)閷€體 Wi按式（4）進行適應(yīng)度計算：

其 中 ，Coυ（Wi）指 個 體 的 測 試 覆 蓋 度 ，Cost（Wi）是 個 體的 測 試 運 行 代 價 。覆 蓋 程 度 Coυ（Wi）為 計 算 父 體 編 碼 Wi中覆蓋測試需求集的個數(shù)。實驗中暫不考慮不同測試需求的測試代價不同的影響，對所有的測試用例的代價都設(shè)置為 1。

2.4 定義遺傳算子

遺傳算子包括選擇、交叉、變異 3 步，主要對個體進行遺傳變異，對其進行優(yōu)化，最終得到新的個體，新個體的生產(chǎn)可能會增加向最優(yōu)解變異的機會，因此在遺傳算子結(jié)束后需再對新的個體進行適應(yīng)值評價，判斷是否滿足輸出條件。

（1）選擇

采用改進的輪盤賭選擇算法，利用各個體適應(yīng)度的概率 決 定 其 遺 留 可 能 性 。 若 某 個 體 Wi的 適 應(yīng) 度 為 F（Wi），依次計算種群中每個個體的適應(yīng)度，則第 i個個體的適應(yīng)度累計值假 設(shè) 需 要 選 擇 S 個 個 體 直 接 遺 留 到下一代個體，利用第 2.1 節(jié)中的混沌映射產(chǎn)生長度為 S 的序 列 ｛y0，y1，y2，… ，yS｝，由 于 組 合 混 沌 映 射 生 成 的 組 合 混 沌 序列在統(tǒng)計特性上呈現(xiàn)均勻分布，序列值均勻分布在區(qū)間（0，1）上 ，選 擇 所 有 滿 足 Ci≤yj≤Ci+1，j=0，1，2，…，S 的 S 個 個 體Wi，利用該序列可增加選擇運算的隨機均勻性，有效提升算 法 的 全 局 搜 索 能 力 ，另 外 Wi被 選 擇 的 概 率 為 PWi=從 而 可 以 保 證 適 應(yīng) 度 越 大 的 個 體 遺 留 的 可 能 性也越大。

（2）交叉

對 2 個 個 體 W1=｛x1，x2，… ，xn｝，W2=｛y1，y2，… ，yn｝進 行 交 叉操作時，如果交叉點選擇得不適合，則可能出現(xiàn)與父代個體一樣的子代個體，導(dǎo)致交叉操作無效。因此，針對遺傳算法中交叉算子的不足，首先確認(rèn)個體交叉點的有效區(qū)域，然后在該區(qū)域內(nèi)隨機選擇交叉點，確保交叉點操作能生成新的和父代個體不同的子代。交叉點的有效區(qū)域如下：

交 叉 點 有 效 區(qū) 域 為 （Amin，Amax）， 例 如 2 個 個 體 X=（110101），Y=（111010），其 交 叉 點 有 效 區(qū) 域 為（3，6）。

在交叉與變異操作中，交叉概率和變異概率的選取對提高搜索性能尤為重要，交叉概率和變異概率越大，則產(chǎn)生新個體的速度就越快，但若選取過大，可能會影響算法中一些重要的數(shù)學(xué)特性和搜索能力。對于適應(yīng)度較高的個體，為使其順利進入下一代，應(yīng)該給予比較低的概率，而對 于 適 應(yīng) 度 較 低 的 個 體 則 剛 好 相 反 ，因 此 采 用Srinvivas［26］提出的個體適應(yīng)度自適應(yīng)調(diào)整辦法，具體如式（6）、式（7）所示。

式 （6）中 ，Pcross為 參 與 交 叉 運 算 的 兩 個 個 體 的 交 叉 概率 ，F(xiàn)max為 群 體 中 適 應(yīng) 度 的 最 大 值 ，F(xiàn)（Wi）與 F（Wj）分 別 為 待交 叉 的 兩 個 個 體 的 適 應(yīng) 度 值 ，F(xiàn)avg為 群 體 內(nèi) 所 有 個 體 的 適應(yīng) 度 均 值 ；式 （7）中 ，Pmutation為 個 體 的 變 異 概 率 ，F(xiàn) 為 參 加 變異運算個 體 的 適應(yīng)度值 ，k1、k2、k3、k4為常量 系 數(shù)。 采用 自適應(yīng)的交叉概率及變異概率選取策略，既保證了適應(yīng)度較高的優(yōu)秀個體保留至下一代，保證了種群的多樣性，又提高了適應(yīng)度較低個體的變異概率，加快了算法的收斂速度。

2.5 添加混沌擾動

對當(dāng)前種群中適應(yīng)度后 90%的個體，利用混沌系統(tǒng)，對其進行一定程度的微小擾動，從而提高其適應(yīng)度。將選中的個體所指代的二進制的每一位都加一混沌擾動，按式（8）進行添加，然后按式（9）映射為優(yōu)化變量，進行迭代計算。

其中，W*為當(dāng)前最優(yōu)個體，Wk為當(dāng)前個體，k 為迭代次 數(shù) ，在式 （9）中 ，ci、di為變換常數(shù)。 通 過 式（8）可 得 到 一 組新個體：

對于式（8）中 β的取值，按照式（7）進行自適應(yīng)選?。?/p>

在搜索階段的初期，希望 Wk取值變動較大，隨著搜索逐漸接近最優(yōu)點，需將 β逐漸縮小，以保證在小范圍內(nèi)找到搜索最優(yōu)解。

3 實驗分析

為驗證提出的基于混沌遺傳算法測試用例約簡方法的有效性，開發(fā)相關(guān)的測試用例約簡工具進行實驗研究，比較了 TCGCG 方法與一些其他的遺傳算法用于測試用例集約簡方法在隨機生成的測試用例需求對應(yīng)關(guān)系及Siemens 測試套件等實例上的測試用例集規(guī)模和算法執(zhí)行時 間 。實 驗 所 用 計 算 機 處 理 器 配 置為 Intel Core i7-4600U@ 2.10 GHz 2.70 GHz，內(nèi) 存 為 4 GB，操 作 系 統(tǒng) 為 Windows 7旗 艦 版 64 位 。實 驗 中 設(shè) 定 最 大 迭 代 次 數(shù) 為 1 000，若 迭代 10 代后無明顯改進則退出迭代，種群中個體數(shù)目 M=50，k1=k3=1，k2=k4=0.5。

3.1 用于比較的遺傳測試用例生成算法

實驗中用于比較的方法包括：基于一般遺傳算法的測試 用 例 生 成 方 法 （test case generation based on genetic algorithm，TCGG）［17］； 在 TCGG 基 礎(chǔ) 上 的 對 變 異 算 子 進 行 優(yōu)化 后 的 改 進 遺 傳 算 法 測 試 用 例 最 小 生 成 方 法（modified test case generation based on genetic algorithm ，MTCGG），對 變 異算 子 優(yōu) 化 采 用 Srinvivas 提 出 的 個 體 適 應(yīng) 度 自 適 應(yīng) 調(diào) 整 辦法，如式（6）、式（7）所示。

3.2 實驗一

通過隨機函數(shù)生成 0-1 矩陣，表示測試用例與測試需求之間的關(guān)系，矩陣的規(guī)模分 10 組，分別為 20× 20、40×40、60×50、60×60、80×80、90×80、100×100、150× 100、200×150 以 及 300×200，每 組 中 包 含 30 個 矩陣，矩陣 內(nèi) 各 點通 過 隨 機 的 方 式 取 值 為 “1”或 者 “0”，并且確保每個需求至少被 5個測試用例覆蓋，每個矩陣各不相同，從而保證實驗隨機性。對每組對應(yīng)關(guān)系分別運行 TCGG、MTCGG 以及 TCGCG，并 記 錄 每 個 矩 陣約 簡 花 費 時 間（單 位 為 ms）以 及 約 簡 后 的 大 小 ，各 種 情況下每組 30 個矩陣的平均值見表1。表 1 中小括號中的百分比表示總覆蓋率未達到 100%。

表1 中列出了在每組數(shù)據(jù)上使用 TCGG、MTCGG 以及TCGCG 3 種方法約簡后平均最小測試用例數(shù)、平均花費時間。從表 1 中可以看出，除了使用 TCGG 方法的 100×100矩陣，MTCGG 方法的 60×60、100×100 矩陣，TCGCG 方法的 60×60 矩 陣 ，其 余 情 況 下 使 用 3 種 方 法 都 能 得 到100%的覆蓋率，說明遺傳算法具有不錯的搜索能力 。10組實驗中，在平均最小用例數(shù)指標(biāo)上，TCGCG 方法在其中 7組表現(xiàn)最優(yōu)，包括 20×20（并列）、40×40、80×80、90×80、150×100、200×150、300×200；而 MTCGG 方 法 有 3 組 最優(yōu)，分別是 60×50、60×60 和 100×100；而采用 TCGG 方法只 有 在 20×20（并 列）矩 陣 上 表 現(xiàn) 最 優(yōu) 。在 花 費 時 間 指 標(biāo)上，TCGCG 方法在其中 8 組的表現(xiàn)要優(yōu)于 TCGG 方法和MTCGG 方法。

圖2 中列出了在不同矩陣規(guī)模下使用 TCGG、MTCGG以 及 TCGCG 3 種 方 法 約 簡 后 平 均 最 小 測 試 用 例 數(shù) 的 比較 。從 圖 2 中 可 以 看 出 ，大 部 分 情 況 下 使 用 TCGCG、MTCGG 方 法 優(yōu) 化 得 到 的 最 小 測 試 用 例 集 數(shù) 量 要 少 于TCGG。說明通過優(yōu)化變異算子有助于提高遺傳算法的搜索效率，提高尋優(yōu)能力。

圖3 中 列 出 了在不同 矩 陣規(guī)模下 使 用 TCGG、MTCGG以 及 TCGCG 3 種 方 法 約 簡 后 平 均 花 費 時 間 的 比 較 。 從圖3 可 以 看 出 ，矩 陣 規(guī) 模較 小 的 時 候 ，TCGCG 與 MTCGG方法可以得到相近的平均最小測試用例數(shù)量以及平均花費時間，然而隨著矩陣規(guī)模變大，TCGCG 方法的優(yōu)勢越來越明顯。

3.3 實驗二

選 用 space 程 序 以 及 Siemens 提 供 的 5 個 C 程 序 和 相關(guān) 的 測 試 套 件 進 行 約 簡 算 法 的 比 較［27，28］，每 個 程 序 均 設(shè) 計了大量測試用例并保證每個需求至少被 30個測試用例覆蓋 ，表 2 中給出了每個程序的總 需求數(shù)（包 括分支、定義 引用對）以及對應(yīng)的可執(zhí)行測試用例數(shù)。

表1 不同方法所花費時間及平均最優(yōu)用例大小比較

圖2 不同矩陣規(guī)模下3種方法最小測試用例數(shù)比較

圖3 不同矩陣規(guī)模下3種方法平均花費時間比較

表2 實驗評測程序

為確保隨機性，實驗設(shè)計如下：設(shè)待測程序測試用例集為｛t1，t2，…，tN｝，選擇數(shù)量分別為 N1、N2、N3、N4、N5的測試用例進行約簡，在不同的初始值 yj0，j=1，2，…，20 的情況下，采用第 4.1 節(jié)的方法可產(chǎn)生 20 組 不 同 的 混 沌 序 列｛yj0，yj1，yj2，…，yjli｝，j=1，2，…，20表 示 向 上 取 整 運 算 ），其 中 ，li表 示 每 個 序 列 的 長 度 ，計 算方式為，i=1，2，3，4，5，接 著 在 ｛t1，t2，… ，tN｝中 選 取 編號分別為的測 試 用 例 ，剩 余 的 Ni-li個 測 試 用 例 選 取 要 保 證 所 有測試需求能被 100%覆蓋。實驗中各待測程序在分支覆蓋及 定 義 引用對覆蓋時 的 N 值以及 N1、N2、N3、N4、N5值 的選擇見表3。

表3 實驗評測程序選取的測試用例數(shù)量情況

圖4中給出了各待測程序在不同初始測試用例集數(shù)量情況下 20組測試用例集的平均約簡結(jié)果，從圖 4中可以看出，無論是分支覆蓋還是定義—引用覆蓋，在大部分情況下，本文提出的 TCGCG 方法要優(yōu)于 TCGG 方法和MTCGG 方法，可以得到更少的測試用例精簡集合。

3.4 實驗結(jié)果討論

從兩個實驗中可以看出，TCGCG 方法和 MTCGG 方法相比 TCGG 方法，可以在更短時間內(nèi)獲得最好的約簡效果。這主要是因為它們通過采用自適應(yīng)的交叉概率及變異概率選取策略，保證了適應(yīng)度較高的優(yōu)秀個體保留至下一代，從而提高了適應(yīng)度較低個體的變異概率，加快算法的收 斂 速 度 ；另 外 一 方 面 ，通 過 將 Chebyshev 和 Logistic 混 沌映射結(jié)合的混沌序列引入基于遺傳算法的測試用例生成方法的選擇、交叉和變異操作，使得種群構(gòu)造更具均勻分布特性，降低了同種群間個體的相似度，可以提升算法全局搜索能力，因此提出的 TCGCG 方法比 MTCGG 方法以及TCGG 方法在大部分情況下可以得到更好的約簡效果。

圖4 各待測程序不同初始測試用例集數(shù)量情況下的平均約簡結(jié)果

4 結(jié)束語

針對測試用例約簡的特點，介紹了一種基于組合混沌遺傳算法的測試用例約簡方法，它將混沌機制引入遺傳算法中，并且改進了交叉、變異算子，使得最終能快速搜索到全局最優(yōu)解。實驗證明，這種新的方法能夠有效克服遺傳算法的早熟收斂等缺陷，對測試用例生成效率有一定的提高 。主 要 工 作 為 ： 具 有 均 勻 分 布 特 性 的 Chebyshev 和Logistic 混 沌 映 射 結(jié) 合 的 混 沌 序 列 引 入 了 基 于 遺 傳 算 法 的測試用例生成方法的選擇、交叉和變異操作；采用了一種基于個體適應(yīng)度的自適應(yīng)調(diào)整的交叉、變異算子，并設(shè)計了一種混沌擾動設(shè)定的自適應(yīng)方法；與傳統(tǒng)遺傳算法在最小測試用例集生成規(guī)模和算法執(zhí)行時間上進行了比較，以驗證本文提出方法的有效性。

進一步 的 研 究 工 作 包 括：k1、k2、k3、k4等 參 數(shù) 以 及初 始種群規(guī)模 M 取值對算法性能、收斂效率的影響；利用已有的測試數(shù)據(jù)優(yōu)化初始群體以提高算法收斂速度。

［1］ TODD L.An empiricalstudyofregression testselection techniques ［J］.ACM Transactions on Software Engineering and Methodology，2001，10（2）：185-207.

［2］ NIE C，LEUNG H.The minimal failure-causing schema of combinatorialtesting ［J］.ACM Transactions on Software Engineering and Methodology，2011，20（4）：1-38.

［3］ BIBLE J，ROTHERMEL G，ROSENBLUM D.A comparative study of coarse- and fine-grained safe regression test selection techniques ［J］.ACM Transactions on Software Engineering and Methodology，2001，10（2）：149-183.

［4］ HARROLD M，GUPTA R，SOFFA M.A methodology for controlling the size of a test suite ［J］.ACM Transactions on Software Engineering and Methodology，1993，2（3）：270-285.

［5］ CHEN T，LAU M.A new heuristic for test suite reduction ［J］. Information and Software Technology，1998，40（5）：347-354.

［6］ CHEN T，LAU M.On the divide and conquer approach towards test suite reduction ［J］.Information Sciences，2003，152 （1）：89-119.

［7］ 邢穎，宮云戰(zhàn)，王雅文. 基于分支限界搜索框架的測試用例自動 生 成［J］. 中國科 學(xué)：信 息 科 學(xué)，2014，44（10）：1345-1360. XING Y，GONG Y Z，WANG Y W.Based on branch threshold search framework of automatic generation of test cases［J］.China Science：Information Science，2014，44（10）：1345-1360.

［8］ WINDISCH A，WAPPLER S，WEGENER J.Applying particle swarm optimization to software testing ［C］／／The 9th Annual Conference on Genetic and Evolutionary Computation，April 4-8，2007，London，UK.New Jersey：IEEE Press，2007：1121-1128.

［9］ 陳翔，顧慶，王子元.一種基于粒子群優(yōu)化的成對組合測試算法框架［J］. 軟件學(xué)報，2011，22（12）：2879-2893. CHEN X，GU Q，WANG Z Y.A paired combination test algorithm based on particle swarm optimization framework ［J］. Journal of Software，2011，22（12）：2879-2893.

［10］史嬌嬌，姜淑娟，韓寒. 自適應(yīng)粒子群優(yōu)化算法及其在測試數(shù)據(jù)生成中的應(yīng)用研究［J］. 電子學(xué)報，2013，41（8）：1555-1559. SHI J J，JIANG S J，HAN H.Adaptive particle swarm optimization algorithm and its application in test data generation［J］.Electronic Journals，2013，41（8）：1555-1559.

［11］王令賽，姜淑娟，張艷梅.基于正交搜索的粒子群優(yōu)化測試用例生成方法［J］. 電子學(xué)報，2014，42（12）：2345-2351. WANG L S，JIANG S J，ZHANG Y M.Particle swarm optimization based on orthogonal search method for generating test cases［J］.Electronic Journals，2014，42（12）：2345-2351.

［12］YOO S，HARMAN M.Regression testing minimization，selection and prioritization：a survey ［J］.Journal of Software Testing， Verification and Reliability，2012，22（2）：67-120.

［13］MICHAEL C C，MCGRAW G E，SCHATZ M A.Generating software test data by evolution［J］.IEEE Transactions on Software Engineering，2001，27（12）：1085-1110.

［14］MA X Y，SHENG B K，YE C Q.Test-suite reduction using geneticalgorithm ［C］／／The6th InternationalWorkshop on Advanced Parallel Processing Technologies，April 5-10，2005，Hong Kong，China.New Jersey：IEEE Press，2005：253-262.

［15］JONES B，EYRES D.A strategy for using genetic algorithms to automate branch and fault-based testing ［J］.The Computer Journal，1998，41（2）：98-107

［16］LIN J C，YEH P L.Using genetic algorithms for test case generation in path testing ［C］／／The 9th Asian Test Symposium，October 3-5，2000，Washington D C，USA.New Jersey：IEEE Press，2000：241-246

［17］BERNDT D，F(xiàn)ISHER J，JOHNSON L.Breeding software test cases with genetic algorithms ［C］／／The 36th Hawaii International Conference on System Sciences，May 5-8，2003，Hawaii，USA. New Jersey：IEEE Press，2003：17-26

［18］KHOR S，GROGONO P.Using a genetic algorithm and formal conceptanalysis to generate branch coverage testdata automatically ［C］／／The 26th IEEE／ACM International Conference on Automated Software Engineering （ASE 2011），IEEE Computer Society，November 6-10，2004，Lawrence，KS，USA.New Jersey：IEEE Press，2004：346-349.

［19］LEE J，CHUNG C.An optimal representative sets election method ［J］.Information and Software Technology，2000，42 （1）：17-25.

［20］MARRE M，BERTOLINO A.Using spanning sets for coverage testing ［J］.IEEETransactionsonSoftwareEngineering，2003，29（11）：974-984.

［21］JEFFREY D，GUPTA N.Improving fault detection capability by selectively retaining test cases during test suite reduction ［J］. IEEE TransactionsonSoftwareEngineering，2007，33 （2）：108-123.

［22］張涌，錢樂秋，王淵峰.基于擴展有限狀態(tài)機測試中測試輸入數(shù)據(jù)自動選取的研究［J］. 計算機學(xué)報，2003 26（10）：1295-1303. ZHANG Y，QIAN L Q，WANG Y F.Based on extended finite state machine test input data in the automatic selection of research［J］.Journal of Computer，2003，26（10）：1295-1303.

［23］楊瑞，陳振宇，張智軼. 一種基于擴展有限狀態(tài)機的自動化測 試 用 例 生 成 方 法 ［J］. 中 國 科 學(xué) ：信 息 科 學(xué) ，2014，44（5）：588-609. YANG R，CHEN Z Y，ZHANG Z Y.Based on extended finite state machine automation test case generation method ［J］.China Science：Information Science，2014，44（5）：588-609.

［24］HOLLAND J.Adaption in natural and artificial systems ［M］. Boston：MIT Press，2015：126-137.

［25］俎云霄，周杰.基于組合混沌遺傳算法的認(rèn)知無線電資源分配［J］. 物理學(xué)報，2011，60（7）：079501. ZU Y X，ZHOU J.Based on the combination of chaos genetic algorithm in cognitive radio resource allocation ［J］.Journal of Physics，2011，60（7）：079501.

［26］SRINIVASM， PATNAIK L M.Adaptiveprobabilitiesof crossover and mutation in genetic algorithms ［J］.IEEE Transactions on System，Man and Cybern，1994，24（4）：656-667.

［27］HARMAN M.The current state and future of search based software engineering［C］／／The 29th IEEE International Conference on Software Engineering.Minneapolis， May 23-25， 2007，Minneapolis，MN，USA.New Jersey：IEEE Press，2007：342-357.

［28］University of Nebraska-Lincoln.Computer science&engineering［EB／OL］.（2016-02-11）［2016-03-12］.http：／／www.cse.unl.edu.

Test case minimizing based on combination chaos genetic algorithm

SHEN Qing，JIANG Yunliang，SHEN Zhangguo，LOU Jungang
School of Information Engineering，Huzhou University，Huzhou 313000，China

Test case minimizing is one of the most important research fields in software testing.Uniformly distributed Chebyshev and Logistic chaos sequence were introduced in the selection，crossover and mutation of genetic algorithm.Chaos disturbance was also added in genetic testing suite to address the common problems of weak ability in local search and premature convergence，thus to optimize the test result.Experiments were conducted in randomly generated test suites and Siemens test suites.Comparisons were also made with classical methods regard to the scale of production of test suite and the execution time of the algorithms.The results of the experiment indicate that based on the same execution time of the algorithms，a smaller scale test suite can be produced by introducing chaotic sequence in genetic testing suite selection.

software testing，test cases minimizing，chaos genetic algorithm，test case

s：The National Natural Science Foundation of China （No.61103051），Natural Science Foundation of Zhejiang Province（No.LY15F020018），Zhejiang Provincial Science and Technology Plan of China （No.2015C33247），Science and Technology Program of Huzhou City （No.2014GZ02）

TP311

：A

10.11959／j.issn.1000-0801.2016178

申情（1982-），女，湖州師范學(xué)院講師，主要研究方向為軟件測試、人工智能、系統(tǒng)性能評估等。

蔣云良（1967-），男，博士，湖州師范學(xué)院教授，主要研究方向為智能信息處理、GIS 等。

沈張果（1982-），男，湖州師范學(xué)院講師，主要研究方向為大數(shù)據(jù)分析、軟件可靠性建模、智能交通等。

樓俊鋼（1982-），男，博士，湖州師范學(xué)院副教授，主要研究方向為軟件可靠性建模、軟件測試、大數(shù)據(jù)分析等。

2016-02-23；

：2016-06-14

蔣云良，jyl@zjhu.edu.cn

國家自然科學(xué)基金資助項目（No.61103051）；浙江省自然科學(xué)基金資助項目（No.LY15F020018）；浙江省公益性技術(shù)應(yīng)用研 究計 劃 基 金 資 助 項 目（No.2015C33247）；湖州市科技計劃基金資助項目（No.2014GZ02）