基于智能優(yōu)化算法的測試數(shù)據(jù)生成研究綜述

摘要：軟件測試數(shù)據(jù)的自動生成是提高測試效率和降低測試成本的關(guān)鍵策略之一。近年來，基于智能優(yōu)化算法的測試數(shù)據(jù)生成方法逐漸成為學(xué)術(shù)界關(guān)注的熱點問題。文章對該領(lǐng)域的研究成果進(jìn)行了系統(tǒng)梳理與綜合評述。文章分析了進(jìn)化算法、群智能算法及模擬單個事物運行的智能算法在軟件測試數(shù)據(jù)生成中的應(yīng)用效果及優(yōu)化能力，展望了軟件測試數(shù)據(jù)自動生成技術(shù)未來可能的發(fā)展方向，提出了進(jìn)一步的研究建議與思考。

關(guān)鍵詞：智能優(yōu)化算法；軟件測試；測試數(shù)據(jù)生成；遺傳算法；粒子群算法；蟻群算法；模擬退火算法

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

文章編號：1009-3044（2025）06-0049-04開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

0 引言

軟件測試在軟件開發(fā)過程中扮演著不可或缺的角色。據(jù)統(tǒng)計，在軟件開發(fā)的整個生命周期中，軟件測試的成本通常占據(jù)了開發(fā)總成本的一半甚至更高[1]。傳統(tǒng)的人工測試數(shù)據(jù)生成方法已顯現(xiàn)出耗時費力且效率低下的局限性。因此，自動化生成測試數(shù)據(jù)的方法因其高效性的特點成為了解決該問題的重要途徑之一。

在軟件測試領(lǐng)域，基于智能優(yōu)化算法的測試數(shù)據(jù)生成方法因提升效率而被廣泛研究與應(yīng)用，從而為軟件測試工作提供了有力支持。

1 智能優(yōu)化算法概述

智能優(yōu)化算法是一類基于仿生學(xué)原理和數(shù)學(xué)模型的優(yōu)化方法，被廣泛應(yīng)用于工程設(shè)計、機器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域，用于解決復(fù)雜的優(yōu)化問題。這些算法通過模擬生物進(jìn)化、群體行為或其他智能策略來搜索問題的最優(yōu)解或近似最優(yōu)解，具有全局搜索能力強、通用性高、參數(shù)敏感性高等特點，在生成軟件測試數(shù)據(jù)方面也發(fā)揮著重要作用。以遺傳算法（Genetic Al?gorithm， GA）為代表的進(jìn)化類算法，以及優(yōu)化粒子群（Particle Swarm Optimization， PSO）、蟻群算法（AntColony Optimization， ACO）等群體智能算法，結(jié)合模擬退火算法（Simulated" Annealing）、差分進(jìn)化算法（Dif?ferential Evolution，DE）、灰狼優(yōu)化算法（Grey Wolf Op?timizer， GWO）、蝙蝠算法（Bat Algorithm， BA）、多目標(biāo)優(yōu)化算法（Multi-objective Optimization Algorithm，MOA）、協(xié)同進(jìn)化算法（Co-evolutionary Algorithm，CEA）、強化學(xué)習(xí)優(yōu)化（Reinforcement Learning Optimi?zation）、元學(xué)習(xí)優(yōu)化（Meta-learning Optimization）等其他優(yōu)化方法，常用于生成軟件測試數(shù)據(jù)。本文將探討這些算法及其改進(jìn)算法在自動生成測試數(shù)據(jù)中的實踐，并對智能優(yōu)化算法的未來研究趨勢進(jìn)行歸納與預(yù)測。

2 基于進(jìn)化類算法的測試數(shù)據(jù)生成

進(jìn)化類算法是一種源自自然進(jìn)化過程的智能優(yōu)化方法，借助遺傳變異和“適者生存”的自然規(guī)則逐步優(yōu)化的智能算法。這些算法模仿了生物進(jìn)化的機制[2]，最具代表性的有學(xué)者Holland[3]在1975年基于自然選擇理論提出的遺傳算法（Genetic Algorithm，GA）和美國學(xué)者Storn 等[4]1995 年創(chuàng)立的差分進(jìn)化算法（Differential Evolution，DE）。它們在求解復(fù)雜優(yōu)化問題時展現(xiàn)出了強大的搜索能力和適應(yīng)性。最常見的遺傳算法的流程圖如圖1所示。

遺傳算法生成測試數(shù)據(jù)的核心原理在于，設(shè)計并定義適應(yīng)度函數(shù)，將其函數(shù)值作為衡量標(biāo)準(zhǔn)，借助算法反復(fù)對編碼后的參數(shù)進(jìn)行迭代優(yōu)化，直至獲取最優(yōu)解或達(dá)到最大進(jìn)化代數(shù)。相較于人工生成，能以更高效率生成更高質(zhì)量的測試數(shù)據(jù)。但劣勢十分顯著，如出現(xiàn)過早收斂陷入局部最優(yōu)和生成的測試數(shù)據(jù)路徑覆蓋率低的問題。為此，許多學(xué)者提出了各自的改進(jìn)方案。

為應(yīng)對遺傳算法容易陷入局部最優(yōu)的狀況，程孟飛[5]所提出的多路徑覆蓋測試用例使用改進(jìn)的佳點集遺傳算法，通過混沌學(xué)習(xí)初始化，優(yōu)化交叉算子，綜合路徑相似性與分支距離，該文章所提出的改進(jìn)算法在迭代次數(shù)方面的波動相對較小，有效減緩了過早收斂的現(xiàn)象；楊現(xiàn)瑋[6]提出的算法能夠基于個體適應(yīng)度的分布情況，決定交叉操作與變異操作的執(zhí)行順序，以提升種群中個體的多樣性，為后續(xù)的遺傳操作奠定基礎(chǔ)，通過遷移子種群的個體，使得交叉和變異后的種群個體更加豐富，利于全局尋優(yōu)，該算法在運行效率和生成覆蓋所有路徑的測試用例數(shù)量方面表現(xiàn)出顯著的優(yōu)勢；黃陳輝[7]提出了基于反向?qū)W習(xí)的初始種群生成策略，以優(yōu)化初始種群，使其更接近最優(yōu)解，設(shè)計適應(yīng)度函數(shù)，考慮算法的并行能力，采用了針對所有目標(biāo)路徑的個體評價函數(shù)，在交叉和變異過程中使用了混沌序列操作，增強全局尋優(yōu)能力，避免“早熟”，提高了算法的性能，使遺傳算法的效率提升了10.8%，自適應(yīng)遺傳算法提升了8.49%；文獻(xiàn)[8]結(jié)合鯨魚算法提出混合算法，采用精英保留策略，在交叉、變異操作中分別采用自適應(yīng)的交叉、變異概率，增強了其全局搜索能力。這些方法的核心理念是通過打破種群的局部收斂狀態(tài)，增強對解空間的探索能力，從而提高遺傳算法找到全局最優(yōu)解的可能性。

針對遺傳算法生成測試數(shù)據(jù)效率不高和路徑覆蓋率低的問題，黃川沂[9]優(yōu)化了算法流程，在每次生成子代時，會根據(jù)覆蓋情況更新目標(biāo)集和存檔集，新設(shè)計的適應(yīng)度函數(shù)綜合考慮層相似度、分支偏差和個性化因子，能夠自定義個性化因子并設(shè)置其影響權(quán)重，針對初代種群生成設(shè)計了自定義用例集，將隨機生成的種群與自定義用例集結(jié)合，提升了初代種群的多樣性，有助于算法更快收斂，并設(shè)計了多組對照實驗，結(jié)果表明在測試用例生成問題上有更加優(yōu)異的表現(xiàn)；文獻(xiàn)[10]構(gòu)建了適應(yīng)度函數(shù)，擴(kuò)大不匹配路徑之間的差異，迅速生成滿足條件的測試數(shù)據(jù)，降低冗余測試數(shù)據(jù)的產(chǎn)生，并提升覆蓋率；虞飛等人[11]融合退火算法到遺傳算法中，在交叉和變異產(chǎn)生新一代種群時，以退火算法的概率接受比父輩差的個體，能覆蓋更多的路徑，實驗證明此算法的最優(yōu)迭代次數(shù)為標(biāo)準(zhǔn)遺傳算法的42.1%，是自適應(yīng)遺傳算法的85.4%；林亞娜[12]改進(jìn)的算法通過路徑構(gòu)建方法生成目標(biāo)路徑矩陣集合和實際路徑矩陣，設(shè)計適應(yīng)度函數(shù)，比較目標(biāo)路徑矩陣和實際路徑矩陣的差異，經(jīng)歸一化處理得到適應(yīng)度值，根據(jù)適應(yīng)度值調(diào)節(jié)遺傳算子，得到問題的最優(yōu)解集合和全部測試數(shù)據(jù)；文獻(xiàn)[13]提出了一種基于佳點集的遺傳算法，該算法根據(jù)問題特征采用不同種類的編碼方式。對于基于二進(jìn)制進(jìn)行編碼的個體，生成子代個體時利用了佳點集交叉算子；對于基于實數(shù)進(jìn)行編碼的個體，生成子代個體時則利用混沌交叉方法。此外，設(shè)計適應(yīng)度函數(shù)時對分支距離和個體穿越路徑與目標(biāo)路徑矩陣相似度的結(jié)合進(jìn)行了嘗試，該方法在覆蓋率以及測試時間方面均具有優(yōu)勢；姚婷[14]提出基于多路徑覆蓋的遺傳算法，計算個體針對每一條目標(biāo)路徑的適應(yīng)值，保存符合條件的測試用例及其覆蓋的目標(biāo)路徑，若無期望的測試用例，則評價進(jìn)化個體性能，然后，進(jìn)行選擇、交叉、變異操作，構(gòu)成新一代種群，迭代至生成覆蓋所有目標(biāo)路徑的測試用例，效率明顯提高；Suresh Y等[15]提出一種基于基路徑集的遺傳算法自動生成測試數(shù)據(jù)的軟計算方法，將遺傳算法的特征與測試數(shù)據(jù)相結(jié)合，充分利用測試數(shù)據(jù)生成能力的全局和局部優(yōu)化能力的優(yōu)點。這些方法的核心理念是提升搜索效率、增強全局探索能力并優(yōu)化局部精度，從而更有效地解決遺傳算法生成測試數(shù)據(jù)時效率低和路徑覆蓋率低的問題。

差分進(jìn)化算法因其結(jié)構(gòu)簡潔、收斂速度快、魯棒性強且實現(xiàn)便捷等特點，廣泛應(yīng)用于軟件測試數(shù)據(jù)生成。韋婧[16]提出了一種基于多因素排序的參數(shù)自適應(yīng)差分進(jìn)化算法，該算法由兩大部分組成，分別為參數(shù)存儲和分配機制，參數(shù)存儲通過加權(quán)排名擇優(yōu)存儲，為下一代提供參考；分層分配依據(jù)適應(yīng)度差值分類優(yōu)化，增強局部搜索。實驗表明，該機制有效提升差分進(jìn)化算法性能，自適應(yīng)策略池進(jìn)一步優(yōu)化。此外，自適應(yīng)選擇策略池差分進(jìn)化算法結(jié)合了改進(jìn)的DE/current-to-rand/1變異策略，并設(shè)計了兩種不同類型的策略池。這些策略能夠增強種群的局部搜索能力，平衡探索與開發(fā)的能力。實驗結(jié)果顯示，所提算法具有競爭力。

3 基于群智能算法的測試數(shù)據(jù)生成

自20世紀(jì)90年代以來，自然界生物和物理現(xiàn)象進(jìn)入專家學(xué)者的視線，影響其提出了一系列群體智能算法，旨在通過模擬這些現(xiàn)象來解決復(fù)雜的優(yōu)化問題。蟻群覓食啟發(fā)了Colorni A[17]等人提出蟻群算法（Ant Colony Optimization，ACO），鳥群捕食啟發(fā)Kenne?dy J[18]等人提出了粒子群優(yōu)化算法（Particle Swarm Op?timization，PSO）。此外，對自然界物理現(xiàn)象的觀察也是部分群體智能算法的起點。Reynolds R G[19]模擬人類社會發(fā)展提出文化算法，煙花爆炸啟發(fā)Zhu Y等[20]提出了演化算法等。在軟件測試數(shù)據(jù)生成領(lǐng)域，粒子群優(yōu)化算法已成為學(xué)者們研究的重點，其流程圖如圖2所示。

與大多數(shù)優(yōu)化算法一樣，粒子群優(yōu)化算法同樣有著后期容易陷入局部最優(yōu)和生成測試數(shù)據(jù)效率不高的問題。文獻(xiàn)[21]通過引入自適應(yīng)隨機測試，提出了一種基于自適應(yīng)隨機測試的粒子群優(yōu)化算法，當(dāng)種群陷入局部最優(yōu)解時，通過生成跳出局部最優(yōu)的粒子提升全局搜索概率，實驗顯示算法精度與探索能力優(yōu)異。提出代理模型優(yōu)化，通過樣本訓(xùn)練、適應(yīng)度預(yù)測、篩選與更新降低計算成本，動態(tài)調(diào)整代理模型，顯著提升了測試用例生成效率，同時有效降低了時間和計算成本。孫毅剛等人[22]為了應(yīng)對測試用例冗余的問題提出一種由天牛須算法改進(jìn)的粒子群算法，將粒子群算法與改進(jìn)后的天牛須搜索算法結(jié)合來生成測試用例，有效減少測試用例集的大小，提高生成的效率；王杰等人[23]提出了基于實例群優(yōu)化算法的軟件測試數(shù)據(jù)生成方法，優(yōu)化了各個環(huán)節(jié)的參數(shù)；滕賽娜[24]提出了兩種方法改進(jìn)陷入局部最優(yōu)問題，其一采用梯度下降法對最優(yōu)解與次優(yōu)解進(jìn)行再次搜索，并設(shè)定禁忌區(qū)域以保證快速找到最優(yōu)解并提高收斂精度，其二引入混沌搜索進(jìn)行優(yōu)化，對當(dāng)前種群中的最優(yōu)粒子進(jìn)行混沌優(yōu)化以跳出局部最優(yōu)，并對部分較差粒子進(jìn)行混沌優(yōu)化以改善種群多樣性；王曙燕等人[25]利用大數(shù)據(jù)平臺Spark將所有需要被覆蓋的兩兩組合分組并下發(fā)到集群中各個節(jié)點上進(jìn)行尋優(yōu)操作，采用一次只測試一個用例的策略，并結(jié)合自適應(yīng)粒子群算法進(jìn)行尋優(yōu)，當(dāng)各個節(jié)點完成尋優(yōu)后，利用Spark進(jìn)行結(jié)果收集，并對收集后的用例集進(jìn)行約簡操作；李晨晨[26]采用約簡粒子群優(yōu)化算法（RAPSO）生成組合測試用例集，對進(jìn)化方程中的速度項進(jìn)行約簡，僅依靠位置的更新來實現(xiàn)算法的迭代，避免了粒子速度帶來的誤差，提高了粒子群優(yōu)化算法的收斂速度，在RAPSO算法的進(jìn)化過程中，采用根據(jù)粒子當(dāng)前適應(yīng)度值與聚集度動態(tài)調(diào)整慣性權(quán)重的策略，有效避免算法過早收斂于局部最值，該算法相比其他3種算法分別提高了61.71%、46.82%、48.09%的執(zhí)行效率。其核心理念與解決方法的關(guān)鍵在于平衡全局探索與局部開發(fā)，確保搜索多樣性與效率。

群智能算法中其他受啟發(fā)于鳥群、蟲群和獸群的算法在軟件測試數(shù)據(jù)生成上也被廣泛應(yīng)用。李清霞[27]提出了一種采用柯西變異算子來自動生成具有較高變異的測試數(shù)據(jù)集的改進(jìn)烏鴉搜索算法，利用相對誤差作為適應(yīng)度函數(shù)來選擇較好的測試用例，引入柯西變異算子以防止陷入局部最優(yōu)；劉汀[28]引進(jìn)改進(jìn)蟻群算法控制測試用例集合的冗余數(shù)據(jù)量，建立測試用例集覆蓋模型，掌握測試用例集數(shù)據(jù)信息的覆蓋情況，根據(jù)事件發(fā)生概率模型，以測試用例集的用例個數(shù)最小為優(yōu)化目標(biāo)，建立用例集優(yōu)化目標(biāo)函數(shù)，在保證用例集滿足要求的條件下，逐步縮小用例集信息的覆蓋度；Lakshminarayana P等人[29]提出了一種混合了杜鵑搜索算法和蜂群算法的算法，將算法與現(xiàn)有的粒子群優(yōu)化、布谷鳥搜索、蜂群算法和螢火蟲算法進(jìn)行了性能比較，所提算法生成的測試數(shù)據(jù)中有65%達(dá)到了較高的適應(yīng)度函數(shù)值。

4 基于模擬單個事物運行的智能算法測試數(shù)據(jù)生成

有別于進(jìn)化類算法和群智能算法的模擬群體行為，模擬退火算法、神經(jīng)網(wǎng)絡(luò)和禁忌搜索算法等傾向于模擬單個事物的運行邏輯來進(jìn)行優(yōu)化。劉思凝[30]提出一種改進(jìn)的模擬退火遺傳算法生成測試數(shù)據(jù)，提出新的路徑相似度計算，并納入適應(yīng)度函數(shù)中，提高個體評價精度；圍繞多點交叉算法和自適應(yīng)變異，采用精英保留策略，保護(hù)最優(yōu)個體，再結(jié)合模擬退火算法，應(yīng)用Boltzmann機制，加速收斂并避免早熟和局部最優(yōu)；文獻(xiàn)[6]使用RBF神經(jīng)網(wǎng)絡(luò)模擬適應(yīng)度函數(shù)，代替插值法計算個體適應(yīng)度值，大幅提高了分支覆蓋測試用例生成算法的效率，縮短了生成時間；劉本和[31]以禁忌搜索算法作為主要工具，結(jié)合遺傳算法輔助提出改進(jìn)的禁忌搜索算法，通過優(yōu)化初始解的選擇，解決了禁忌搜索算法對初始解的依賴問題，并對返回值進(jìn)行了調(diào)整，從而在效率和解質(zhì)量方面取得了顯著改善；仲曉敏等人[32]對禁忌搜索算法的評價函數(shù)、鄰域移動和禁忌表進(jìn)行改進(jìn)，并設(shè)計了合理的赦免準(zhǔn)則和終止準(zhǔn)則。在此基礎(chǔ)上構(gòu)建了測試用例生成模型，利用禁忌搜索算法產(chǎn)生測試用例來驅(qū)動插樁程序運行并求取其評價值，通過實驗驗證了該方法的準(zhǔn)確性和有效性。

5 結(jié)論與展望

在軟件測試領(lǐng)域，自動生成測試數(shù)據(jù)已成為解決測試效率和成本問題的重要途徑之一。本文綜述了基于智能優(yōu)化算法的軟件測試數(shù)據(jù)自動生成方法。首先闡述了軟件測試的重要性以及傳統(tǒng)方法的局限性，從而引發(fā)了自動生成測試數(shù)據(jù)的需求。隨后，概述了智能優(yōu)化算法，涵蓋了進(jìn)化類算法和群體智能算法等。最后針對這些算法，詳細(xì)介紹了它們在測試數(shù)據(jù)生成領(lǐng)域的應(yīng)用以及改進(jìn)成果。未來，基于智能優(yōu)化算法的測試數(shù)據(jù)生成方法仍具有廣闊的研究前景，在跨領(lǐng)域測試數(shù)據(jù)生成、動態(tài)適應(yīng)性優(yōu)化算法、多目標(biāo)優(yōu)化與約束處理和大規(guī)模軟件系統(tǒng)測試數(shù)據(jù)生成方面，可以進(jìn)一步提高測試數(shù)據(jù)生成的效率和質(zhì)量，結(jié)合多種算法和技術(shù)以提高智能化水平，追求人機協(xié)同化、軟硬件協(xié)同測試數(shù)據(jù)生成、自動化與持續(xù)集成中的測試數(shù)據(jù)生成，并設(shè)計定制化方案以滿足不同應(yīng)用需求。