基于強(qiáng)化學(xué)習(xí)選擇策略的路徑覆蓋測試數(shù)據(jù)生成算法

摘 要：面向路徑覆蓋的測試是軟件測試的重要方法之一。如何快速生成高質(zhì)量測試數(shù)據(jù)使其滿足路徑覆蓋要求，一直是研究熱點問題。為解決現(xiàn)有智能優(yōu)化方法運(yùn)行時間長、探索過程不穩(wěn)定以及生成測試用例冗余的問題，提出一種基于強(qiáng)化學(xué)習(xí)思想的選擇策略，用于以路徑覆蓋為準(zhǔn)則的測試數(shù)據(jù)生成中。通過將可執(zhí)行路徑定義為智能體狀態(tài)，算法每一輪迭代更新后的數(shù)據(jù)選擇定義為智能體動作，并將獎勵函數(shù)與狀態(tài)變化關(guān)聯(lián)，在狀態(tài)更新過程中使用貪心策略來引導(dǎo)輸入數(shù)據(jù)不斷向未獲取狀態(tài)變異更新，以此不斷選擇能夠覆蓋新可執(zhí)行路徑的數(shù)據(jù)，從而實現(xiàn)對待測程序所有執(zhí)行路徑覆蓋的目標(biāo)。實驗結(jié)果表明，與其他算法相比，所提策略的運(yùn)行時間和迭代次數(shù)明顯降低，同時覆蓋率快速提高。結(jié)合理論分析可以得出結(jié)論：所提策略在實際運(yùn)用中能夠有效實現(xiàn)路徑覆蓋并提高測試數(shù)據(jù)生成效率。

關(guān)鍵詞：測試數(shù)據(jù)生成； 路徑覆蓋； 強(qiáng)化學(xué)習(xí)； 選擇策略

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2024）08-031-2467-07

doi：10.19734/j.issn.1001-3695.2023.11.0592

Algorithm for path coverage test data generation based onreinforcement learning selection strategy

Liu Chaoa， Ding Ruib， Zhu Yuhana

（a.School of Mathematics & Science， b.School of Computing & Information Technology，Mudanjiang Normal University， Mudanjiang Heilongjiang 157000， China）

Abstract：Path-coverage oriented testing is a crucial method in software testing， and the rapid generation of high-quality test data to satisfy path coverage requirements has been a persistent research challenge. To address issues such as long running times， unstable exploration processes， and the generation of redundant test cases in existing intelligent optimization methods， this paper proposed a selection strategy based on the reinforcement learning paradigm applied to test data generation with path coverage as the criterion. By defining executable paths as the state of the intelligent agent， it defined the data selection after each iteration update as the agent’s action. It associated the reward function with state changes， and employed a greedy strategy during the state update process to guide input data towards continuous variations in unexplored states. This iterative selection process aimed to continuously choose data that covered new executable paths， thereby achieving the goal of covering all execution paths of the target program. Experimental results demonstrate that compared to other algorithms， the proposed strategy significantly reduces running times and iteration counts while achieving notable improvements in coverage. Theoretical ana-lysis supports the conclusion that the proposed strategy effectively realizes path coverage and enhances the efficiency of test data generation in practical applications.

Key words：test data generation; path coverage; reinforcement learning; selection strategy

0 引言

軟件測試是保障軟件質(zhì)量的重要方法。其對軟件進(jìn)行大量的測試，用來發(fā)現(xiàn)軟件中可能存在的缺陷和錯誤［1］。當(dāng)下對軟件行業(yè)的統(tǒng)計結(jié)果顯示，關(guān)乎軟件測試的花費(fèi)成本很高，往往能占整個項目開發(fā)的一半［2］。而軟件測試的核心在于生成有效的測試數(shù)據(jù)，用來滿足規(guī)定的測試充分性準(zhǔn)則。因此，如何高效地生成測試數(shù)據(jù)，就具有重要的現(xiàn)實意義和經(jīng)濟(jì)價值［3］。

面向覆蓋的測試數(shù)據(jù)生成方法通過覆蓋待測軟件的需要滿足測試要求，是經(jīng)典的測試數(shù)據(jù)生成方法。路徑覆蓋作為面向覆蓋的最基本充分性準(zhǔn)則之一，其要求選取足夠多的測試數(shù)據(jù)，使待測程序的每條可達(dá)路徑都至少執(zhí)行一次。可以將問題描述為：對于給定程序的目標(biāo)路徑，需要在程序的輸入空間里尋找或生成能夠覆蓋目標(biāo)路徑的測試數(shù)據(jù)［4］。

對于測試數(shù)據(jù)生成，傳統(tǒng)優(yōu)化算法方面，Goschen等人［5］利用遺傳規(guī)劃方法來進(jìn)行自動化軟件測試，動態(tài)地生成輸入值來探索給定軟件的輸入域，從而實現(xiàn)更好的路徑覆蓋。Sun等人［6］將分布式代理引導(dǎo)進(jìn)化優(yōu)化與測試用例生成相結(jié)合，以提高程序中路徑覆蓋測試的測試用例生成效率。Zhang等人［7］提出覆蓋引導(dǎo)的模糊測試生成測試數(shù)據(jù)，以此來檢測軟件運(yùn)行中的缺陷和故障。Potluri等人［8］提出了一種混合群智能方法，將粒子群、蜜蜂群和螢火蟲、布谷鳥算法結(jié)合，以優(yōu)化測試覆蓋率，從而高效地生成測試數(shù)據(jù)。Damia等人［9］提出基于群的遺傳算法，采用全新的適應(yīng)度函數(shù)來更新種群，實現(xiàn)測試數(shù)據(jù)的生成。丁蕊等人［10］提出關(guān)鍵點路徑表示法來計算理論路徑的數(shù)目，從覆蓋難易程度上對路徑進(jìn)行分類，并使用遺傳算法來生成難覆蓋路徑的測試數(shù)據(jù)。錢忠勝等人［11］提出一種結(jié)合關(guān)鍵點與路徑相似度的多種群多覆蓋策略，來提高測試數(shù)據(jù)生成效率。Kumar等人［12］針對測試數(shù)據(jù)自動生成問題，提出了一種蟻群優(yōu)化負(fù)選擇算法，對生成的數(shù)據(jù)進(jìn)行細(xì)化，以此來提高測試數(shù)據(jù)質(zhì)量。雖然傳統(tǒng)的優(yōu)化算法能夠有效地生成測試數(shù)據(jù)，但是其受搜索能力以及更新速度等因素限制，容易陷入過早收斂，并且由于其缺乏并行性，在大規(guī)模路徑覆蓋或者復(fù)雜程序的測試數(shù)據(jù)生成問題中，存在計算時間過長、生成測試數(shù)據(jù)效率不高的問題。

在測試數(shù)據(jù)生成問題中，執(zhí)行路徑受到輸入數(shù)據(jù)、內(nèi)部結(jié)構(gòu)變化等因素影響，構(gòu)成了一個動態(tài)的環(huán)境。同時，路徑覆蓋問題中需要探索全局最優(yōu)解，測試數(shù)據(jù)的生成要考慮長期目標(biāo)，而不是局部最優(yōu)解，這些都需要在高維度的決策空間中進(jìn)行搜索。強(qiáng)化學(xué)習(xí)［24］作為利用智能體與環(huán)境的交互進(jìn)行學(xué)習(xí)以達(dá)成回報最大化或?qū)崿F(xiàn)特定目標(biāo)的方法，在面向復(fù)雜程序的測試時，以動態(tài)環(huán)境為基礎(chǔ)，通過獎勵函數(shù)，在動態(tài)環(huán)境中展現(xiàn)出比其他智能優(yōu)化算法更好的環(huán)境適應(yīng)性和靈活性。同時，強(qiáng)化學(xué)習(xí)具有一個長期的獎勵導(dǎo)向功能，能夠高效地處理高維度的決策問題，與其他智能優(yōu)化算法相比，能夠更好地探索全局最優(yōu)解，不易陷入局部最優(yōu)。

在強(qiáng)化學(xué)習(xí)方面，曹靜［13］提出一種基于強(qiáng)化學(xué)習(xí)的智能化測試用例生成方法，通過強(qiáng)化學(xué)習(xí)模型建立測試智能體Xbot，將測試用例生成問題轉(zhuǎn)換為多步?jīng)Q策優(yōu)化問題，以此來快速生成測試用例。Spieker等人［14］使用一種基于強(qiáng)化學(xué)習(xí)的方法Retecs，其根據(jù)數(shù)據(jù)持續(xù)時間、上次執(zhí)行時間和失敗歷史來選擇測試用例，提供了一種更輕量級的學(xué)習(xí)方法，證明了強(qiáng)化學(xué)習(xí)能夠在持續(xù)集成和回歸測試中進(jìn)行有效的自動化自適應(yīng)測試用例選擇。Esnaashari等人［15］提出一種模因算法，將強(qiáng)化學(xué)習(xí)作為遺傳算法中的一種局部搜索方法，以此來提高測試數(shù)據(jù)生成速度。Reddy等人［16］提出一種基于表格策略的強(qiáng)化學(xué)習(xí)方法RLCheck，將隨機(jī)選擇問題形式化成多樣化引導(dǎo)問題，通過RLCheck方法生成有效的測試數(shù)據(jù)。Cˇegiň等人［17］提出一種基于強(qiáng)化學(xué)習(xí)的測試數(shù)據(jù)生成方法，通過獎賞函數(shù)對每一組測試數(shù)據(jù)形成的覆蓋率提供一個獎勵，同時將測試函數(shù)主體添加到強(qiáng)化學(xué)習(xí)算法中，根據(jù)被測函數(shù)的復(fù)雜度推斷個體嘗試次數(shù)，再利用神經(jīng)網(wǎng)絡(luò)對獎勵進(jìn)行訓(xùn)練，以此達(dá)到路徑的完全覆蓋或滿足給定的嘗試次數(shù)。Kim等人［18］使用強(qiáng)化學(xué)習(xí)取代元啟發(fā)式算法，將被測軟件重構(gòu)為強(qiáng)化學(xué)習(xí)環(huán)境，構(gòu)建了GunPowder框架，利用深度神經(jīng)網(wǎng)絡(luò)訓(xùn)練一個雙深度Q-Networks智能體，通過實驗驗證了其在分支路徑覆蓋上的可行性。Harries等人［19］提出一種用于功能軟件測試的強(qiáng)化學(xué)習(xí)（RL）框架DRIVE，并提出Batch-RL方法進(jìn)行Q學(xué)習(xí)，用圖神經(jīng)網(wǎng)絡(luò)對狀態(tài)-動作值函數(shù)進(jìn)行建模，證明此框架可以用自動化的方式觸發(fā)所需的軟件功能，能夠高效地測試具有大范圍測試目標(biāo)的軟件。Tsai等人［20］提出了DeepRNG框架，其主要通過在框架里增加深度強(qiáng)化學(xué)習(xí)代理來提高軟件的測試數(shù)據(jù)生成效率。王立歆［21］提出了一種基于分層強(qiáng)化學(xué)習(xí)的混合測試算法LCCT，采用馬爾可夫決策過程作為上層控制，模糊測試方法作為決策補(bǔ)充來測試數(shù)據(jù)。Pan等人［22］提出了一種基于強(qiáng)化學(xué)習(xí)方法的Q-Testing，使用一種好奇心驅(qū)動的策略來探索被測程序，該策略利用已訪問過的部分狀態(tài)來引導(dǎo)測試轉(zhuǎn)向不熟悉的程序區(qū)域。Pan等人［23］提出一種將可測性分析與強(qiáng)化學(xué)習(xí)相結(jié)合的方法，利用強(qiáng)化學(xué)習(xí)方法來大大縮減測試數(shù)據(jù)生成的時間，并提高代碼覆蓋率。綜上，強(qiáng)化學(xué)習(xí)算法通過將數(shù)據(jù)生成過程轉(zhuǎn)換成與環(huán)境的交互學(xué)習(xí)過程，能夠避免算法陷入過早收斂。同時，智能體通過自主探索解空間，充分利用計算資源，能夠提高測試數(shù)據(jù)生成的效率。但現(xiàn)有的強(qiáng)化學(xué)習(xí)算法在面對路徑覆蓋的測試數(shù)據(jù)生成研究中仍面臨一些挑戰(zhàn)，如探索過程不穩(wěn)定、測試用例贅余等問題。

為了應(yīng)對上述挑戰(zhàn)，本文研究基于強(qiáng)化學(xué)習(xí)算法的路徑覆蓋測試數(shù)據(jù)生成方法，提出強(qiáng)化學(xué)習(xí)選擇算法（reinforcement learning selection algorithm，RLSA），將強(qiáng)化學(xué)習(xí)思想融入面向路徑覆蓋的測試數(shù)據(jù)生成中。在測試數(shù)據(jù)生成問題中，首先以待測程序的動態(tài)環(huán)境為基礎(chǔ)，定義智能體的狀態(tài)及動作，將待測程序的可執(zhí)行路徑定義為狀態(tài)，將每一輪更新的數(shù)據(jù)選擇定義為動作，通過這種定義方式，極大地減少了無效數(shù)據(jù)的產(chǎn)生，降低了生成冗余測試數(shù)據(jù)的可能性；然后，將貪心策略與Q學(xué)習(xí)方法相結(jié)合，設(shè)計基于環(huán)境反饋Q值學(xué)習(xí)的貪心選擇策略，用確定性的動作選擇來提高智能體學(xué)習(xí)的穩(wěn)定性和效率，以此避免隨機(jī)性探索時可能造成的探索過程不穩(wěn)定問題，實現(xiàn)測試數(shù)據(jù)生成的全局性；最后，利用獎勵函數(shù)引導(dǎo)智能體在高維度的決策空間選擇最優(yōu)決策，使得智能體能夠快速地生成覆蓋所有可執(zhí)行路徑的數(shù)據(jù)，以此來提高算法的效率。

1 相關(guān)知識及定義

強(qiáng)化學(xué)習(xí)［24］是利用智能體與周圍環(huán)境的感知來獲取最大獎勵值，并基于此來尋找最優(yōu)化策略的方法過程。本文將強(qiáng)化學(xué)習(xí)的尋優(yōu)過程應(yīng)用到程序結(jié)構(gòu)上，先將程序結(jié)構(gòu)抽象成控制流圖，再利用智能體對環(huán)境的感知交互來作出決策，最后根據(jù)決策方法不斷迭代，從而實現(xiàn)目標(biāo)。對應(yīng)于軟件測試數(shù)據(jù)生成問題，下面定義在強(qiáng)化學(xué)習(xí)中智能體學(xué)習(xí)時涉及的相關(guān)概念及條件。

1.1 控制流圖

在待測程序中，控制流圖是一個表示程序執(zhí)行流程的有向圖G=〈V，W，s，e〉，也對應(yīng)著強(qiáng)化學(xué)習(xí)中智能體的整體學(xué)習(xí)環(huán)境。如圖1所示，其中節(jié)點表示程序的基本塊，邊表示基本塊之間的跳轉(zhuǎn)關(guān)系。記V={V1，V2，…，Vn}為有向圖的節(jié)點集，W={W1，W2，…，Wn}為有向圖的邊集，有Wjk=〈Vj，Vk〉，s和e分別為程序輸入的入口和出口。以圖1為例，有V={s，1，2，3，4，5，6，7，e}，Ws1=〈s，1〉。

1.2 執(zhí)行路徑及其數(shù)目計算

執(zhí)行路徑是程序入口節(jié)點開始到出口節(jié)點的一條路徑，其通過節(jié)點的序列進(jìn)行表示，如圖1中“〈s，1，3，7，e〉”就是一條由節(jié)點序列組成的執(zhí)行路徑。對于可執(zhí)行路徑的數(shù)量，利用節(jié)點、兄弟節(jié)點以及分支節(jié)點數(shù)目計算，以圖1為例，其計算方式如下所示：路徑數(shù)目=兄弟節(jié)點+節(jié)點×［分支節(jié)點×（分支子節(jié)點+分支子節(jié)點）+兄弟節(jié)點］，M=②+③×［④×（⑤+⑥）+⑦］，將所有節(jié)點代入數(shù)值1，得路徑數(shù)目為4。

1.3 狀態(tài)空間

對于狀態(tài)空間X={x0，…，xi，…}，其中每一個狀態(tài)點xi都是對待測程序的一條可執(zhí)行路徑的描述，狀態(tài)空間為所有可執(zhí)行路徑的集合。以圖1為例，其狀態(tài)空間為X={〈s，1，2，e〉，〈s，1，3，4，5，e〉，〈s，1，3，4，6，e〉，〈s，1，3，7，e〉}。

1.4 動作空間

對于動作空間A={a0，a1，a2，…，ai，…}，每一個動作ai都是對新一輪更新后的數(shù)據(jù)進(jìn)行選擇行為的刻畫。以圖1程序為例，初始輸入的數(shù)據(jù)為t，新一輪對輸入數(shù)據(jù)t進(jìn)行更新操作后產(chǎn)生的數(shù)據(jù)為t1，t2，t3，…，動作a0=〈t，t1〉，a1=〈t1，t2〉。例如圖1中，若輸入數(shù)據(jù)為（a，b，c），進(jìn)行更新后產(chǎn)生的數(shù)據(jù)為（a1，b1，c1），（a2，b2，c2），動作a0=〈（a，b，c），（a1，b1，c1）〉，a1=〈（a，b，c），（a2，b2，c2）〉。

1.5 獎勵函數(shù)

獎勵函數(shù)R與測試數(shù)據(jù)所要達(dá)成的目標(biāo)相關(guān)。對面向路徑覆蓋的測試數(shù)據(jù)來說，獎勵函數(shù)影響著智能體的決策。因此需要對智能體的不同動作賦予不同的獎勵值，在每一輪更新的數(shù)據(jù)中，若這些數(shù)據(jù)中能夠執(zhí)行之前未通過的新路徑，那么給智能體一個正向獎勵，否則沒有獎勵。具體如式（1）表示。

R=iR if data have new iR path（s）

R=0else（1）

以圖1為例，若初始數(shù)據(jù)集（a，b，c）更新后的數(shù)據(jù)為（a1，b1，c1），相較初始數(shù)據(jù)集多執(zhí)行了一條新路徑，則更新后的數(shù)據(jù)（a1，b1，c1）獲得獎勵R=1。

2 基于強(qiáng)化學(xué)習(xí)的測試數(shù)據(jù)生成方法

本文研究利用強(qiáng)化學(xué)習(xí)思想提高測試數(shù)據(jù)生成效率的方法，從而快速實現(xiàn)待測程序的路徑覆蓋目標(biāo)。在強(qiáng)化學(xué)習(xí)中，智能體是在與環(huán)境的交互中獲得信息的，在基于強(qiáng)化學(xué)習(xí)的路徑覆蓋測試數(shù)據(jù)生成中，智能體需要使用策略來進(jìn)行狀態(tài)-動作的選擇，從而生成覆蓋路徑的測試數(shù)據(jù)。為此，提出了一種學(xué)習(xí)策略來進(jìn)行智能體的模型訓(xùn)練，利用確定性的狀態(tài)-動作選擇來加速智能體的學(xué)習(xí)過程，同時簡化計算過程。

2.1 建立基于強(qiáng)化學(xué)習(xí)的測試數(shù)據(jù)生成模型

在本文提出的基于強(qiáng)化學(xué)習(xí)的測試數(shù)據(jù)生成模型中，首先對初始數(shù)據(jù)集中覆蓋的路徑進(jìn)行覆蓋率計算。若滿足覆蓋率要求，初始數(shù)據(jù)集即為滿足要求的測試數(shù)據(jù)；若不滿足覆蓋要求，則利用強(qiáng)化學(xué)習(xí)方法更新數(shù)據(jù)，生成新的初始數(shù)據(jù)集。循環(huán)迭代，直到滿足覆蓋率要求輸出數(shù)據(jù)。其具體的模型運(yùn)行過程如圖2所示。

本文目標(biāo)是生成覆蓋所有路徑的數(shù)據(jù)，即生成的測試數(shù)據(jù)能覆蓋待測程序的所有可執(zhí)行路徑。本文策略將貪心算法與Q學(xué)習(xí)算法相結(jié)合，用貪心選擇替換原本探索過程中的概率選擇。通過貪心算法，使得強(qiáng)化學(xué)習(xí)智能體更傾向于選擇當(dāng)前Q值最高的動作，通過累積的Q值來引導(dǎo)智能體決策，促使算法能夠更快地收斂，并得到一組優(yōu)質(zhì)的測試數(shù)據(jù)。同時，貪心算法和Q學(xué)習(xí)的結(jié)合能夠減少很多在概率探索過程中的不必要嘗試，更有針對性地選擇未覆蓋的可執(zhí)行路徑，使得生成的測試數(shù)據(jù)更有可能覆蓋未被探索的可執(zhí)行路徑，從而提高測試數(shù)據(jù)的質(zhì)量，提高算法的運(yùn)行效率，讓智能體能夠快速選擇出優(yōu)質(zhì)數(shù)據(jù)，實現(xiàn)待測程序可執(zhí)行路徑的全覆蓋。

具體實現(xiàn)思路如下：首先，通過控制流圖，得到所有可執(zhí)行路徑的數(shù)目，同時將每一條可執(zhí)行路徑都定義為智能體的一種狀態(tài)；然后，根據(jù)隨機(jī)方法生成初始輸入數(shù)據(jù)，利用智能體轉(zhuǎn)換獲得初始狀態(tài)集合，當(dāng)這個初始狀態(tài)集合為狀態(tài)空間X的真子集時，說明有可執(zhí)行路徑未被覆蓋，通過變異、隨機(jī)擾動等方式更新初始輸入數(shù)據(jù)，并生成多組更新后的數(shù)據(jù)，以此來增加未覆蓋的可執(zhí)行路徑選擇概率；接著進(jìn)行更新數(shù)據(jù)的獎勵函數(shù)值設(shè)定，在這些新生成的數(shù)據(jù)中，若有數(shù)據(jù)發(fā)現(xiàn)了初始數(shù)據(jù)集未覆蓋的執(zhí)行路徑，則智能體對這組數(shù)據(jù)選擇賦予正向獎勵值，反之無獎勵值；最終，智能體將獎勵值最大的數(shù)據(jù)替換為新的初始數(shù)據(jù)集，繼續(xù)迭代，直到智能體的狀態(tài)覆蓋整個狀態(tài)空間，即覆蓋了待測程序的所有可執(zhí)行路徑。其更新以及動作選擇的模型如圖3所示。

2.2 基于強(qiáng)化學(xué)習(xí)的測試數(shù)據(jù)生成模型實現(xiàn)

強(qiáng)化學(xué)習(xí)選擇策略的具體行為如下。在整個策略的具體行為上，首先通過分析待測程序控制流圖結(jié)構(gòu)，計算出待測程序所有的可執(zhí)行路徑集合P以及對應(yīng)的完整狀態(tài)空間X。隨機(jī)生成初始數(shù)據(jù)集t0后，通過智能體轉(zhuǎn)換環(huán)境信息，獲得初始數(shù)據(jù)集t0當(dāng)前覆蓋的可執(zhí)行路徑p0，并得到初始狀態(tài)空間X0、初始動作空間A0，并設(shè)置初始Q0值為0。接下來，對X0與X進(jìn)行比較。若X0X，則說明初始數(shù)據(jù)集t0未能完全覆蓋待測程序執(zhí)行路徑；若X0=X，則說明初始數(shù)據(jù)集t0已經(jīng)完全覆蓋待測程序執(zhí)行路徑，此時t0即為符合條件的測試用例。

下面說明在更新過程中，強(qiáng)化學(xué)習(xí)選擇策略的具體實現(xiàn)：當(dāng)初始數(shù)據(jù)集未能完全覆蓋待測程序可執(zhí)行路徑時，強(qiáng)化學(xué)習(xí)選擇策略將Q學(xué)習(xí)與貪心方法相結(jié)合來指導(dǎo)智能體進(jìn)一步探索學(xué)習(xí)，通過對數(shù)據(jù)集ti中各重復(fù)覆蓋可執(zhí)行路徑的數(shù)據(jù)ti，j進(jìn)行m次變異、擾動操作δ，使得智能體向下探索生成新數(shù)據(jù)集為ti，jδ={ti，j1，ti，j2，…，ti，jm}，由智能體動作空間A的定義，此時智能體的動作集為{ai，jk=〈ti，j，ti，jδ〉|k=1，2，…，m}，同時動作空間更新為Ai+1=Ai∪{ai，jk}。再根據(jù)上述獎勵函數(shù)R的定義，給予新數(shù)據(jù)集中不同數(shù)據(jù)對應(yīng)的獎勵值iR，通過貪心策略選擇新數(shù)據(jù)集ti，jδ中具有最大獎勵值的數(shù)據(jù)ti，jk，即有R（ti，j，ti，jk）=max R（ti，j，ti，jδ），同時更新狀態(tài)空間Xi+1以及數(shù)據(jù)集ti+1，并生成對應(yīng)的執(zhí)行路徑pi+1。在更新好數(shù)據(jù)集及狀態(tài)空間后，再通過強(qiáng)化學(xué)習(xí)選擇策略來更新Q值，使其不斷地引導(dǎo)智能體決策，更新公式如下：

Qi+1=（1－α）Qi+α（iRi+γ×max Q（x，a））（2）

其中：Qi+1為新數(shù)據(jù)集ti+1的Q值；α為智能體學(xué)習(xí)效率；Qi為當(dāng)前數(shù)據(jù)的Q值；iRi為所做動作的獎勵；γ為折扣因子；max Q（x，a）為新狀態(tài)下能獲取的最大動作獎勵。最后將更新后的數(shù)據(jù)ti+1作為新的數(shù)據(jù)集，重復(fù)上述過程，不斷向下進(jìn)行探索迭代，直到生成覆蓋所有執(zhí)行路徑的數(shù)據(jù)并輸出結(jié)果。

2.3 算法偽代碼分析

算法1 強(qiáng)化學(xué)習(xí)選擇策略

輸入：隨機(jī)生成的被測程序的一組測試數(shù)據(jù)。

輸出：一組能夠覆蓋所有路徑的測試數(shù)據(jù)及各測試數(shù)據(jù)對應(yīng)的路徑。

1 function R（olddata，newdata）

2 if newdata have new iR path（s）

3 return iR //返回獎勵值

4 end if

5 return 0

6 end function

7 main RLSA（X，P）

8 t0=random（data），t0，j∈t0 //數(shù)據(jù)域中隨機(jī)生成數(shù)據(jù)集

9 t0→p0 //由數(shù)據(jù)生成對應(yīng)路徑

10X0=Xt0，A0=At0，Q0=0

11for i=0 to N do

12 if XiX then

13 T=ti，jδ //變異、擾動生成下一代數(shù)據(jù)集

14 ai，jk=〈ti，j，T〉

15 Ai+1=Ai∪{ai，jk}

16 iRi=max R（ti，T）

17 ai，jk→ti，jk∈T|iRi //選擇獎勵最大的數(shù)據(jù)

18 （ai，jk，ti，jk）→xi，jk

19 Xi+1=Xi∪{xi，jk} //更新狀態(tài)空間

20 ti+1=（ti＼{ti，j}）∪{ti，jk}

21 ti+1→pi+1

22 Qi+1=（1-α）Qi+α（iRi+γ×max Q（x，a））

23 end if

24 return datas=models（ti+1）

25 return paths=models（pi+1）

26?; if Xi==X then

27 break

28 end if

29 end for

在上述代碼中，首先定義算法的獎勵函數(shù)（第1行），通過判斷新數(shù)據(jù)是否涵蓋新的可執(zhí)行路徑，以此來賦予不同的獎勵值（第2～5行）。接下來，指定算法策略（第7行），隨機(jī)生成初始數(shù)據(jù)集（第8行），由初始數(shù)據(jù)得到已覆蓋的路徑情況（第9行）、初始狀態(tài)空間、動作空間以及Q值（第10行）。然后執(zhí)行本文算法的循環(huán)更新過程（第12～29行）。通過比較初始數(shù)據(jù)集狀態(tài)空間與整個待測程序狀態(tài)空間的包含關(guān)系來判定是否生成新數(shù)據(jù)，若此時初始狀態(tài)集合為待測程序狀態(tài)空間集合真子集（第12行），則通過變異、擾動等方式對重復(fù)覆蓋路徑的數(shù)據(jù)進(jìn)行更新（第13行），然后更新動作集（第14行）以及動作空間（第15行），再通過最大獎勵值（第16行）進(jìn)行動作選擇更新數(shù)據(jù)（第17行），以及更新數(shù)據(jù)對應(yīng)的狀態(tài)集（第18行）和狀態(tài)空間（第19行），之后更新數(shù)據(jù)集（第20行）、對應(yīng)的路徑（第21行）以及Q值（第22行）。最后，重復(fù)迭代上述過程，直到更新后數(shù)據(jù)集的狀態(tài)空間等于待測程序狀態(tài)空間或滿足迭代終止條件，輸出此時的測試數(shù)據(jù)（第24行）以及其對應(yīng)的可執(zhí)行路徑（第25行）。

2.4 時間復(fù)雜度分析

本文算法每次更新Q值表時需要進(jìn)行的計算量與狀態(tài)數(shù)目及動作數(shù)目相關(guān)。具體來說，對于一個有n條可執(zhí)行路徑的程序，其狀態(tài)數(shù)為n，記每一次動作選擇的數(shù)目為m，其中m不超過算法設(shè)定的最大變異數(shù)。在每次更新Q值表時，需要計算所有狀態(tài)下可能的動作獎勵，每個動作的獎勵需要進(jìn)行m次計算。又由于每次訓(xùn)練都需要進(jìn)行狀態(tài)的更新，所以總的計算量為O（N（nm）），其中N表示迭代次數(shù)。

3 實驗分析

為驗證本文方法在路徑覆蓋率方面的性能和可靠性，選擇隨機(jī)方法（RA）、傳統(tǒng)優(yōu)化算法中的遺傳算法（GA）、改進(jìn)的粒子群算法（PSO）［25］、TOGA算法［26］、GPSGA算法［27］和（RLSA），以及在不同的探索率下的強(qiáng)化學(xué)習(xí)Q-learning算法在兩個基準(zhǔn)程序以及兩個工業(yè)程序上進(jìn)行實驗對比，以檢驗本文算法是否具有更高的測試數(shù)據(jù)生成效率。本文所對比的幾種算法進(jìn)行測試數(shù)據(jù)生成時，在全局搜索以及在處理復(fù)雜結(jié)構(gòu)方面都有較好的表現(xiàn)，具有較好的尋優(yōu)能力。所有的程序在Python 3.8軟件環(huán)境下運(yùn)行，Windows 10操作系統(tǒng)，機(jī)器主頻是2.80 GHz，內(nèi)存為16 GB。通過對比實驗旨在回答下面幾個問題：

問題1 本文方法的數(shù)據(jù)生成效率是否優(yōu)于一些現(xiàn)有的優(yōu)化方法？

問題2 本文方法在覆蓋率方面是否優(yōu)于一些現(xiàn)有的優(yōu)化方法？

問題3 貪心探索策略在本文方法中是否優(yōu)于其他探索策略？

3.1 測試程序以及參數(shù)

本文使用的測試程序基本信息以及相關(guān)的實驗參數(shù)如表1和2所示。其中：triangle classification和password strength程序都是傳統(tǒng)軟件測試中常用的基準(zhǔn)程序，其程序邏輯簡單，可以適應(yīng)多種不同的測試環(huán)境，以滿足不同條件下的測試；text sentiment和decision-making support都是在現(xiàn)實生活中被廣泛應(yīng)用的工業(yè)程序，具有一定的現(xiàn)實場景，能夠證明所提的測試策略在實際應(yīng)用中的性能和可靠性。

3.2 實驗結(jié)果與分析

為了降低單次實驗造成的結(jié)果誤差，將6種算法在測試程序上運(yùn)行20次，取其平均值作為對比數(shù)據(jù)。表3為6種算法在兩個基準(zhǔn)測試程序中的運(yùn)行時間、迭代次數(shù)以及多次運(yùn)行后平均覆蓋率的結(jié)果比較。

從表3中可以看出，在基準(zhǔn)程序1中，RA的隨機(jī)選擇導(dǎo)致其運(yùn)行時間最長，改進(jìn)后的PSO算法憑借其較快的收斂速度使其運(yùn)行時間相對較少，而RLSA運(yùn)行時間少于其他所有算法，這是因為RLSA通過貪心策略進(jìn)行選擇，提高算法計算速度的同時，一定程度上和其他算法相比減少了選擇范圍；在迭代次數(shù)方面，在這兩個基準(zhǔn)程序中，RLSA算法也都遠(yuǎn)少于其他的優(yōu)化算法以及隨機(jī)方法，這是因為強(qiáng)化學(xué)習(xí)策略有較強(qiáng)的適應(yīng)性，能夠快速適應(yīng)問題及環(huán)境找到最優(yōu)解；在覆蓋率方面，在基準(zhǔn)程序1中，RLSA策略以及改進(jìn)后的PSO、TOGA算法都能夠成功找到覆蓋所有可執(zhí)行路徑的測試數(shù)據(jù)，并且在一定程度上優(yōu)于GA、GPSGA以及隨機(jī)方法。這是因為它們在全局搜索方面都進(jìn)行了相應(yīng)的優(yōu)化，都能夠跳出局部最優(yōu)。與此同時，RLSA策略在兩個基準(zhǔn)程序上都可以使用較少的運(yùn)行時間來覆蓋待測程序的可執(zhí)行路徑，且都具有較好的覆蓋率。這是因為RLSA策略是通過將待測程序的可執(zhí)行路徑作為狀態(tài)空間中的元素，這樣能夠更快地通過獎勵函數(shù)的引導(dǎo)提高路徑的覆蓋率。圖4表示算法在各程序中隨時間變化的覆蓋率。圖4（a）為程序1的運(yùn)行時間與覆蓋率變化關(guān)系，其中RLSA策略可以最早達(dá)到100%覆蓋；圖（b）為程序2的運(yùn)行時間與覆蓋率變化關(guān)系，其中RLSA策略同樣可以最早達(dá)到100%覆蓋，RLSA策略相對于其余策略可以達(dá)到100%覆蓋，并且運(yùn)行時間最短、效率更高。

表4為6種算法在兩個工業(yè)測試程序中的運(yùn)行時間、迭代次數(shù)以及多次運(yùn)行后平均覆蓋率的結(jié)果比較。

從表4中可以看出，在text sentiment（程序3）程序的實驗中，RLSA策略在運(yùn)行時間上優(yōu)于RA、GA和PSO算法，進(jìn)一步說明強(qiáng)化學(xué)習(xí)選擇策略在智能程序上的適用性；在迭代次數(shù)方面，RLSA也有著較好的性能，說明在數(shù)據(jù)生成方面強(qiáng)化學(xué)習(xí)選擇策略也有較好的收斂速度；在覆蓋率方面，RLSA能夠成功找到覆蓋所有可執(zhí)行路徑的測試數(shù)據(jù)，高于TOGA以及PSO算法。在decision-making support程序（程序4）實驗中，在運(yùn)行時間方面，RLSA遠(yuǎn)低于RA、TOGA以及GPSGA，這是因為RLSA在面對復(fù)雜結(jié)構(gòu)時，能夠高效地在高維度決策空間中選擇最優(yōu)策略；迭代次數(shù)方面，RLSA依然具有優(yōu)勢；在覆蓋率方面，RLSA覆蓋率為100%，TOGA和GPSGA也有較高的覆蓋率，而其他算法覆蓋率則較低，這是因為在面對復(fù)雜的程序時，其他算法在高維度空間決策方面能力較差，而TOGA策略使用反向?qū)W習(xí)提高未覆蓋路徑的搜索效率，GPSAG通過保留佳點集中的優(yōu)秀個體來提高搜索精度，RLSA策略利用獎勵函數(shù)不斷引導(dǎo)智能體自主學(xué)習(xí)探索未知狀態(tài)，增加智能體在復(fù)雜程序中的探索范圍和搜索效率，以此來實現(xiàn)更好的路徑覆蓋。因此，對于工業(yè)程序，RLSA算法在覆蓋率方面仍然保持著較好的性能。圖4（c）為程序3的運(yùn)行時間與覆蓋率變化關(guān)系，其中只有RLSA策略達(dá)到100%覆蓋；圖（d）為程序4的運(yùn)行時間與覆蓋率變化關(guān)系，同樣只有RLSA策略可以達(dá)到100%覆蓋，其余算法都未達(dá)到100%的覆蓋，說明RLSA策略在覆蓋率方面顯著優(yōu)于其他方法。

本文所提策略中使用貪心策略，相比于強(qiáng)化學(xué)習(xí)方法中原本的概率選擇方法，生成的測試數(shù)據(jù)能夠更好地覆蓋此前未覆蓋的可執(zhí)行路徑，較好地提高測試數(shù)據(jù)的生成效率。表5為強(qiáng)化學(xué)習(xí)選擇策略和其他使用不同探索率的強(qiáng)化學(xué)習(xí)Q-learning算法在運(yùn)行4種待測程序后的運(yùn)行時間比較。

從表5中可以看出，對于面向路徑覆蓋的測試數(shù)據(jù)生成問題，強(qiáng)化學(xué)習(xí)算法探索率ε和被測程序的運(yùn)行時間呈正相關(guān)。而本文貪心策略能夠?qū)崿F(xiàn)最高的探索率，使得強(qiáng)化學(xué)習(xí)選擇策略能夠?qū)崿F(xiàn)最短的運(yùn)行時間。這是由于可執(zhí)行路徑的確定，在RLSA中，將可執(zhí)行路徑作為動作的選擇，每一次動作更新都是對未被覆蓋路徑的選擇，每一次智能體向前探索時，都會優(yōu)先選擇未被探索的可執(zhí)行路徑，以此來極大地縮短運(yùn)行時間，而概率選擇方法缺少搜索精度，效率會明顯低于貪心策略。圖5是在不同探索率下的強(qiáng)化學(xué)習(xí)Q-learning算法和本文算法在待測程序上的運(yùn)行時間比較。

3.3 算法穩(wěn)定性分析

通過分析RLSA對以上效率、覆蓋率、迭代次數(shù)影響的實驗，得出RLSA算法在性能方面有較好的優(yōu)勢。為進(jìn)一步分析RLSA策略的穩(wěn)定性，將RLSA與TOGA、GPSGA等算法進(jìn)行穩(wěn)定性對比。由于RLSA的最大迭代次數(shù)為50，所以僅選擇上述實驗分析中迭代次數(shù)少于50次的算法進(jìn)行穩(wěn)定性對比。

下面重點分析RLSA、GPSGA、TOGA算法的穩(wěn)定性。對各算法種群迭代次數(shù)進(jìn)行統(tǒng)計分析，選取基準(zhǔn)測試程序和工業(yè)測試程序分別對比被測程序在各算法上種群迭代次數(shù)，為避免結(jié)果的隨機(jī)性，使用各算法在被測程序上執(zhí)行5 000次的迭代次數(shù)數(shù)值來分析算法穩(wěn)定性。迭代次數(shù)統(tǒng)計結(jié)果使用帶有正態(tài)曲線的箱線圖進(jìn)行展示，箱線圖用來表現(xiàn)一組種群迭代次數(shù)數(shù)據(jù)的離散程度，正態(tài)曲線可以展示數(shù)據(jù)的分布情況。箱線圖由上至下依次表示異常值、上限、上四分位數(shù)（Q3）、中位數(shù)、下四分位數(shù)（Q1）、下限。采用上四分位數(shù)和下四分位數(shù)之差（IOR=Q3-Q4）表示統(tǒng)計數(shù)據(jù)的穩(wěn)定性，即箱線圖中箱子的高度，箱子高度越高說明數(shù)據(jù)離散程度越大，反之離散程度越小。

如圖6所示，RLSA與GPSA、TOGA算法對應(yīng)箱線圖的中位數(shù)值明顯低于其余算法的中位數(shù)值。在程序2中，RLSA策略的中位數(shù)值略低于TOGA和GPSGA，是因為強(qiáng)化學(xué)習(xí)思想需要有強(qiáng)化和學(xué)習(xí)的過程，所以RLSA策略會存在少量的迭代學(xué)習(xí)過程，而在測試程序1、3、4中，RLSA策略優(yōu)勢明顯，均小于其余算法。從4個被測程序整體看，RLSA策略的迭代次數(shù)均保持在10代左右。

從箱線圖中的IQR值來看，RLSA策略在4個測試程序中的IQR值均小于其余算法的IQR值，這說明RLSA策略的穩(wěn)定性優(yōu)于GPSGA和TOGA。

對比箱線圖中的上四分位線，4個被測程序中，除被測程序2以外，RLSA策略均明顯低于其余算法，其中被測程序4的優(yōu)勢不明顯，其余被測程序中，RLSA策略均明顯優(yōu)于其余算法。從正態(tài)曲線看出，RLSA的數(shù)據(jù)分布離散程度最小，異常值較少，數(shù)據(jù)分布情況相比于其余算法較密集。總體來說，RLSA策略比傳統(tǒng)算法和GPSGA、TOGA算法優(yōu)勢明顯，RLSA的覆蓋率、效率、穩(wěn)定程度均高于其余算法。

綜上，通過已得到的實驗結(jié)果以及相關(guān)分析，逐一回答了之前的問題：

對于問題1：基于強(qiáng)化學(xué)習(xí)選擇算法的測試數(shù)據(jù)生成方法能夠更好地提高測試數(shù)據(jù)生成效率，因其通過合理的狀態(tài)定義以及高效的選擇策略，使得本文方法的測試數(shù)據(jù)生成效率優(yōu)于傳統(tǒng)的優(yōu)化算法。

對于問題2：與傳統(tǒng)的優(yōu)化方法相比，基于強(qiáng)化學(xué)習(xí)選擇算法的測試數(shù)據(jù)生成方法提高了路徑覆蓋率，并具有更好的穩(wěn)定性。

對于問題3：與其他探索策略相比，基于貪心的探索策略在本文方法中具有更好的性能。

4 結(jié)束語

本文提出了一種基于強(qiáng)化學(xué)習(xí)的測試數(shù)據(jù)生成方法RLSA，通過貪心策略的強(qiáng)化學(xué)習(xí)方法來實現(xiàn)高效率的測試數(shù)據(jù)生成。同時，提出一種新的狀態(tài)表示方式，并設(shè)計新的動作選擇方式為強(qiáng)化學(xué)習(xí)策略提供指導(dǎo)，避免了使用強(qiáng)化學(xué)習(xí)方法生成測試數(shù)據(jù)時造成的大量贅余，提高了生成的測試數(shù)據(jù)的質(zhì)量。實驗表明，RLSA在迭代次數(shù)、運(yùn)行時間以及路徑覆蓋率上優(yōu)于現(xiàn)有的一些方法。

未來，將通過優(yōu)化數(shù)據(jù)更新方式來進(jìn)一步改善狀態(tài)空間遍歷情況，以期能夠進(jìn)一步減少智能體訓(xùn)練時間。同時，對于貪心策略在一些程序中可能產(chǎn)生的測試數(shù)據(jù)生成效率不高的問題，將繼續(xù)優(yōu)化智能體在探索和利用方面的性能，以此增強(qiáng)算法的普適性，進(jìn)一步提高測試數(shù)據(jù)生的成效率。

參考文獻(xiàn)：

［1］喬夢晴， 李琳， 王頡， 等. 基于遺傳規(guī)劃和集成學(xué)習(xí)的惡意軟件檢測［J］. 計算機(jī)應(yīng)用研究， 2023， 40（3）： 898-904. （Qiao Mengqing， Li Lin， Wang Jie， et al. Malware detection based on genetic programming and ensemble learning［J］. Application Research of Computers， 2023， 40（3）： 898-904.）

［2］張威楠， 孟昭逸， 熊焰， 等. 基于異質(zhì)信息網(wǎng)絡(luò)的安卓虛擬化程序檢測方法［J］. 計算機(jī)應(yīng)用研究， 2023， 40（6）： 1764-1770. （Zhang Weinan， Meng Zhaoyi， Xiong Yan， et al. Detection method of Android virtualization program based on heterogeneous information network［J］. Application Research of Computers， 2023， 40（6）： 1764-1770.）

［3］Anand S， Burke E K， Chen T Y， et al. An orchestrated survey of methodologies for automated software test case generation［J］. Journal of Systems & Software， 2013， 86（8）： 1978-2001.

［4］單錦輝， 姜瑛， 孫萍， 等. 軟件測試研究進(jìn)展［J］. 北京大學(xué)學(xué)報： 自然科學(xué)版， 2005， 41（1）： 134-145. （Shan Jinhui， Jiang Ying， Sun Ping， et al. Research advances in software testing［J］. Journal of Peking University： Natural Science Edition， 2005， 41（1）： 134-145.）

［5］Goschen J， Bosman A S， Gruner S， et al. Genetic Micro-programs for automated software testing with large path coverage［C］//Proc of IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE Press， 2022： 1-8.

［6］Sun Baicai， Gong Dunwei， Yao Xiangjuan， et al. Integrating DSGEO into test case generation for path coverage of MPI programs［J］. Information and Software Technology， 2023， 153： 107068.

［7］Zhang Wenxi， Sakamoto K， Washizaki H， et al. Improving fuzzing coverage with execution path length selection［C］//Proc of IEEE International Symposium on Software Reliability Engineering Workshops. Piscataway， NJ： IEEE Press， 2022： 132-133.

［8］Potluri S， Ravindra J， Mohammad G B， et al. Optimized test cove-rage with hybrid particle swarm bee colony and firefly cuckoo search algorithms in model based software testing［C］//Proc of the 1st International Conference on Artificial Intelligence Trends and Pattern Recognition. Piscataway， NJ： IEEE Press，2022： 1-9.

［9］Damia A， Esnaashari M， Parvizimosaed M. Automatic test data ge-neration based on the prime path coverage criterion： a grouping-based GA approach［EB/OL］. （2023-04-12）. https：//doi.org/10.21203/rs.3.rs-2796131/v1.

［10］丁蕊， 董紅斌， 張巖， 等. 基于關(guān)鍵點路徑的快速測試用例自動生成方法［J］. 軟件學(xué)報， 2016， 27（4）： 814-827. （Ding Rui， Dong Hongbin， Zhang Yan， et al. Rapid test case generation method based on critical path［J］. Journal of Software， 2016， 27（4）： 814-827.）

［11］錢忠勝， 祝潔， 朱懿敏. 結(jié)合關(guān)鍵點概率與路徑相似度的多路徑覆蓋策略［J］.軟件學(xué)報，2022， 33（2）： 434-454.（Qian Zhong-sheng， Zhu Jie， Zhu Yimin. Multi-path coverage strategy combining key point probability and path similarity［J］. Journal of Software， 2022， 33（2）： 434-454.）

［12］Kumar G， Chopra V. Automatic test data generation for basis path testing［J］. Indian Journal of Science and Technology， 2022， 15（41）： 2151-2161.

［13］曹靜. 基于強(qiáng)化學(xué)習(xí)的Web API功能測試用例生成研究［D］. 上海：東華大學(xué)， 2021. （Cao Jing. Research on Web API functional test case generation based on reinforcement learning［D］. Shanghai： Donghua University， 2021.）

［14］Spieker H， Gotlieb A， Marijan D， et al. Reinforcement learning for automatic test case prioritization and selection in continuous integration［C］//Proc of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis. New York：ACM Press， 2017： 12-22.

［15］Esnaashari M， Damia A H. Automation of software test data generation using genetic algorithm and reinforcement learning［J］. Expert Systems with Applications， 2021， 183： 115446.

［16］Reddy S， Lemieux C， Padhye R， et al. Quickly generating diverse valid test inputs with reinforcement learning［C］//Proc of the 42nd ACM/IEEE International Conference on Software Engineering. Pisca-taway， NJ： IEEE Press， 2020： 1410-1421.

［17］Cˇegiň J， Rástocˇny K. Test data generation for MC/DC criterion using reinforcement learning［C］//Proc of IEEE International Conference on Software Testing， Verification and Validation Workshops. Pisca-taway， NJ： IEEE Press， 2020： 354-357.

［18］Kim J， Kwon M， Yoo S， et al. Generating test input with deep reinforcement learning［C］//Proc of the 11th International Workshop on Search-Based Software Testing. Piscataway， NJ： IEEE Press， 2018： 51-58.

［19］Harries L， Clarke R S， Chapman T， et al. Drift： deep reinforcement learning for functional software testing［EB/OL］. （2020-07-16）. https：//arxiv.org/abs/2007.08220.

［20］Tsai C Y， Taylor G W. DeepRNG： towards deep reinforcement learning-assisted generative testing of software［EB/OL］. （2022-01-29）. https：//arxiv.org/abs/2201.12602.

［21］王立歆. 基于分層強(qiáng)化學(xué)習(xí)的自動化軟件測試技術(shù)研究［D］. 沈陽：遼寧大學(xué)， 2022. （Wang Lixin. Research on automated software testing technology based on hierarchical reinforcement learning［D］.Shenyang： Liaoning University， 2022.）

［22］Pan Minxue， Huang An， Wang Guoxin， et al. Reinforcement lear-ning based curiosity-driven testing of Android applications［C］//Proc of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis. New York：ACM Press， 2020： 153-164.

［23］Pan Zhixin， Mishra P. Automated test generation for hardware trojan detection using reinforcement learning［C］//Proc of the 26th Asia and South Pacific Design Automation Conference. Piscataway， NJ： IEEE Press， 2021： 408-413.

［24］張汝波， 顧國昌， 劉照德， 等. 強(qiáng)化學(xué)習(xí)理論， 算法及應(yīng)用［J］. 控制理論與應(yīng)用， 2000， 17（5）： 637-642. （Zhang Rubo， Gu Guochang， Liu Zhaode， et al. Reinforcement learning： theory， algorithms， and applications［J］. Control Theory & Applications， 2000， 17（5）： 637-642.）

［25］Jaiswal U， Prajapati A. Optimized test case generation for basis path testing using improved fitness function with PSO［C］//Proc of the 13th International Conference on Contemporary Computing. New York：ACM Press， 2021： 475-483.

［26］Cheng Mengfei， Ding Rui， Huo Tingting， et al. A hyper-heuristic algorithm for test data generation［C］//Proc of the 6th International Conference on Big Data Research. New York：ACM Press， 2022： 26-31.

［27］程孟飛， 丁蕊. 基于佳點集遺傳算法的多路徑覆蓋測試用例生成［J］. 計算機(jī)與數(shù)字工程， 2022， 50（9）： 1940-1944. （Cheng Mengfei， Ding Rui. Multi-path coverage test case generation based on optimal point set genetic algorithm［J］. Computer and Digital Engineering， 2022， 50（9）： 1940-1944.）