[發明專利]一種基于災變的演化測試的動態優化方法

無效

• 申請號: 201010198471.X
• 申請日: 2010-06-11
• 公開（公告）號: CN101882106A
• 公開（公告）日: 2010-11-10
• 發明（設計）人: 王猛;李必信;王正山;蔣玉婷;張功源;邱棟;吉順慧
• 申請（專利權）人: 東南大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 黃雪蘭

技術領域

本發明是一種基于災變的演化測試的動態優化方法，主要用于處理演化測試在演化過程中出現的種群的早熟退化現象。

背景技術

通常情況下，軟件測試需要耗費整個軟件開發過程50％以上的資源。為了提高測試效率，降低測試成本，研究者們針對自動化測試技術進行了大量研究。其中已被廣泛應用的是隨機測試技術，該技術除了可以實現高度的自動化，還具有簡單、操作性強等優點。但是由于采取了盲目搜索的方法，隨機測試往往會產生龐大低效的測試用例集，從而嚴重降低測試的缺陷檢測能力。因此為了彌補隨機測試中的缺陷，進一步提高自動化測試的效率，需要人們積極研究新的自動化測試方法。其中演化測試作為一種非常有前景的新興方法，受到了越來越多的關注。

演化測試利用某種元啟發式搜索方法(主要使用遺傳算法)來產生測試用例，演化測試將測試用例的生成過程轉化為一個利用遺傳算法進行數值優化的問題。隨著演化測試應用領域的擴大，越來越多的研究者開始關注演化測試性能優化的研究，目前的研究主要集中在解決種群的早熟退化問題與flag變量問題兩大方面。本發明主要針對解決的是種群的早熟退化問題。傳統方法利用靜態優化方法獲得具有合理選擇壓力的演化測試配置，以降低由于收斂速度不合理所造成的種群早熟退化。該方法僅適用于進化停滯問題的預防，但是一旦種群早熟退化，靜態優化方法無法幫助演化測試擺脫局部最優解，從而導致最終無法找到全局最優解。另外一種方法就是動態優化方法，在種群演化的過程中動態處理種群的早熟退化問題。

發明內容

技術問題：本發明的目的是提供一種基于災變的演化測試的動態優化方法，幫助演化測試解決種群的早熟退化問題，從而提高演化測試的性能。與過去使用的方法相比，本發明能夠更好地自動產生測試用例，并提高演化測試的性能。

技術方案：本發明的方法是當演化測試在演化過程中出現種群早熟退化現象時，采用災變操作，幫助演化測試解決種群的早熟退化問題。

本發明提出的基于災變的演化測試的動態優化方法具體步驟如下：

步驟1).分析指定的作為測試對象的程序并構造對應的控制流圖，在測試對象中指定測試目標并根據指定的測試目標構造適應值函數，所述的測試目標是公知的語句覆蓋、分支覆蓋及路徑覆蓋，

步驟2).隨機生成k個數，這k個數組成一個測試用例即每個測試用例包含k個數，然后每個測試用例編碼成種群中的一個個體，重復上述過程直至初始種群有n個個體，其中k和n都是正整數，所述的編碼方法是公知的二進制編碼和格雷碼編碼方法，

步驟3).將種群中的個體解碼為測試用例并將該測試用例作為測試對象的輸入，運行測試對象并根據步驟1)構造的適應值函數計算適應值，適應值的值域為(0，1.0]，當某個體的適應值為1.0時，該個體就是所需的全局最優解，該個體對應的是滿足測試目標的測試用例，所述的解碼是將二進制編碼或者格雷碼編碼的個體轉換為十進制數值的測試用例，

步驟4).將種群中個體的適應值按照設定的劃分標準進行劃分，統計每個劃分區域中的個體數，根據DCP＝-∑Pi*log₁₀Pi度量初始種群的多樣性，所述的DCP為種群的多樣性，Pi表示種群中適應值在第i個劃分區域的個體數占個體總數的比例，且Pi∈[0，1]，i為正整數且為劃分區域的編號，如果初始種群的多樣性DCP高于設定的第一閥值，就重新生成初始種群直到初始種群的多樣性DCP低于第一閥值，第一閥值的值域為(0，1.0]，

步驟5).如果種群中的個體包含所需的全局最優解或者種群演化滿足預設終止條件，則轉至步驟11)，否則，進入步驟6)，所述的全局最優解是種群中適應值為1.0的個體，且該個體對應的是滿足測試目標的測試用例，所述的預設終止條件是種群演化迭代次數達到預設的種群最大迭代次數max，所述的max是正整數，

步驟6).如果種群的多樣性DCP低于設定的第二閥值，第二閥值的值域為(0，1.0]，則進行災變操作，產生一個新種群，并轉入步驟9)，否則，將當前種群作為舊種群，進入步驟7)，

步驟7).對舊種群進行演化操作，并生成臨時種群，

步驟8).按照設定的存活概率Ps對舊種群和臨時種群進行存活操作，形成一個新種群，新種群中的個體為二進制編碼或者格雷碼編碼的個體，所述的存活概率Ps∈(0，1.0)；

步驟9).將新種群作為當前種群，并將當前種群中的個體解碼為測試用例并將該測試用例作為測試對象的輸入，運行測試對象并根據步驟1)構造的適應值函數計算適應值，

步驟10).轉至步驟5)，