基于啟發(fā)式遺傳算法的模糊測試樣本集優(yōu)化方案

王志華，王浩帆，程漫漫

（鄭州大學 網絡空間安全學院，鄭州 450002）

隨著信息與通信技術的快速發(fā)展，信息技術改變了人們的生活方式。然而，伴隨而來的網絡與信息安全問題也逐漸引起了社會各個領域的廣泛關注。

軟件漏洞挖掘技術［1］在信息安全領域中占據(jù)了重要地位。模糊測試［2］則是漏洞挖掘中較為有效的方法之一，其是一種基于缺陷注入的自動化軟件測試技術，主要依賴于不斷輸入非預期的數(shù)據(jù)并對數(shù)據(jù)進行監(jiān)控和觀測的方式發(fā)現(xiàn)軟件是否會存在異常。傳統(tǒng)的模糊測試技術并沒有對初始樣本集進行處理，而是直接進行變異分析。樣本的重復性會產生大量代碼率低且無用的測試用例，從而降低了模糊測試的效率。如何改進模糊測試的缺陷已經成為當前研究熱點。考慮模糊測試樣本集的特點，可以對其進行優(yōu)化，從而精簡樣本集的數(shù)量，提高樣本集的質量，進而提升模糊測試的效率。因此，研究模糊測試樣本集的高質量性精簡問題，具有很大的理論意義和工程應用價值。本文對模糊測試樣本集精簡進行了研究，借助0-1矩陣，在遺傳算法的基礎上進行改進，將貪心逼近算法與遺傳算法結合，提出了基于啟發(fā)式遺傳算法的樣本集精簡解決方案。實驗結果表明，本文方法是有效的。

1 相關工作

近年來，眾多學者從集合覆蓋、機器學習、遺傳算法等角度圍繞模糊測試樣本集的精簡問題開展了大量的研究工作。馬金鑫等［3］設計了一種貪心逼近的求解算法來優(yōu)化模糊測試的輸入樣本集，在樣本集覆蓋率不變的前提下求解獲取最小樣本集合；Bhme等［4］把模糊測試問題建模為Markov模型，并采用特定的策略引導AFL優(yōu)先選擇低頻路徑和變異頻率低的文件作為文件進行變異；隨后Bhme等［5］提出采用模擬退火算法對能逼近特定目標位置的測試輸入分配更高的能量，并優(yōu)先選取高能量種子文件進行變異；Wang等［6］提出了一種質量感知的測試用例優(yōu)先級技術，優(yōu)先輸入高質量的種子，直接定義獲取高質量的種子；唐梟［7］利用污點分析和其他技術來獲取數(shù)據(jù)的執(zhí)行路徑，對代碼覆蓋率相關字段進行基因編碼，并執(zhí)行遺傳算法的選擇變異過程，對危險操作相關字段執(zhí)行邊界值賦值，產生新的測試用例。

在實際處理過程中，采用集合覆蓋技術解決樣本集的精簡或篩選時，精確算法能夠找到集合覆蓋問題的最優(yōu)解，近似算法能夠取得有質量保證的解，但其求解速度較慢，只能求解較小規(guī)模的實例。采用機器學習方法時，需要對數(shù)據(jù)進行大量的訓練并分類，但由于模糊測試樣本集的整體性特點，需要人工干預設定指標，反而降低了模糊測試的效率。使用傳統(tǒng)的逼近算法可以實現(xiàn)對樣本集的縮減，但是沒有考慮樣本在實際問題中的適用性。

2 基礎理論和評價指標

2.1 基礎理論

2.1.1 貪心逼近算法

貪心逼近算法［3］是指利用有關算法解決一些實際問題的場景或精確度，且給出的解決方法是理論上的最優(yōu)解。在樣本集的精簡中，貪心逼近算法指的是盡可能精確地給出樣本的最小樣本集，獲取優(yōu)質樣本是貪心逼近算法的唯一標準。

2.1.2 遺傳算法

遺傳算法［8］是一種基于生物進化原理構想出來的搜索最優(yōu)解的仿生算法。其模擬基因重組與進化的自然過程，把待解決的問題的參數(shù)編程成二進制碼或十進制碼（也可編成其他進制碼），即基因，若干基因組成一個染色體（個體）。對染色體進行類似于自然選擇、配對交叉和變異運算，經過多次重復迭代（世代遺傳）直至得到最后的優(yōu)化結果。

遺傳算法的步驟如下：

步驟1 初始化第0代種群P0。

步驟2 對第i代種群Pi迭代執(zhí)行步驟2.1～步驟2.5，直到滿足停止準則：

2.1 計算Pi中每個個體的適應值，并按照適應值的大小對所有個體進行排序。

2.2 將Pi中適應值最佳的個體加入Pi＋1。

2.3 按照適應值的大小排序在Pi中選擇2個父體。

2.4 按概率選擇雜交算子或者變異算子對兩父體進行遺傳操作，將生成的個體加入Pi＋1。

2.5 如果Pi＋1的規(guī)模已經與Pi持平，則i←i＋1并轉步驟2，否則轉步驟2.3。

步驟3 將最終種群中適應度最好的個體作為遺傳算法的結果。

2.1.3 集合覆蓋問題

集合覆蓋問題（SCP）［9］：在模糊測試中，任何樣本集都可以轉化為最小集合覆蓋問題，而最小覆蓋集為經典的NP-hard問題［10］，難以計算最優(yōu)解。集合覆蓋問題形式上可以描述如下：令A＝（aij）為一個m行、n列的0-1矩陣。C＝（cj）為一個n維整數(shù)向量。令M ＝｛1，2，…，m｝，N ＝｛1，2，…，n｝表示矩陣A的行向量和列向量維數(shù)。值cj（j∈N）表示某一列的代價。不失一般性，假定cj＞0，j∈N。如果aij＝1，則認為列j∈N覆蓋了行i∈M。集合覆蓋問題要求一個最小代價的子集合S?N，這樣每一行i?M 至少被一列j?S覆蓋。集合覆蓋問題的一個自然的數(shù)學模型可以描述為：v（SCP）＝m incjxj，服從于aijx˙j≥1，i∈M，xj∈（0，1）（j∈N）；如果xj＝1（j∈S），則xj＝0。

2.2 評價指標

1）壓縮率。對比樣本精簡前和樣本精簡后的測試樣本數(shù)量，并計算壓縮率來表示算法對樣本集的優(yōu)化程度。

2）執(zhí)行模糊測試所需要的時間。假設模糊測試初始樣本集數(shù)量為n，模糊測試時間函數(shù)為f（n），隨著模糊測試數(shù)量n的增加，模糊測試執(zhí)行時間的增長率與f（n）的增長率正相關。

3）樣本質量。主要由代碼覆蓋率為判斷依據(jù)；代碼覆蓋率為測試的代碼行數(shù)占總代碼行數(shù)的比例。

3 基于啟發(fā)式遺傳算法的樣本集優(yōu)化

樣本集的精簡是將數(shù)量龐大的數(shù)據(jù)集進行縮減的過程。從本文所解決的問題出發(fā)，對于模糊測試集中的樣本，樣本的重復不僅表現(xiàn)在完全相同的樣本，而且從變異的根源來說，樣本間基本塊的相互覆蓋是導致變異產生大量重復測試用例的問題所在。因此，本文在進行樣本選取時，規(guī)定優(yōu)先選取包含代碼基本塊數(shù)最多的樣本（代碼塊數(shù)多的樣本在進行變異時可以得到更多測試用例），再按照樣本性能依次選擇，直到新樣本集基本代碼塊可以覆蓋原始樣本集的基本代碼塊為止。本文要定義的啟發(fā)式算法是對染色體選擇的算法，最終獲取所求染色體集合。

3.1 染色體的表示

為了保證在樣本集數(shù)量最少的基礎上得到更優(yōu)質的樣本（基本代碼塊數(shù)多且變異能力好），在實現(xiàn)過程中，引入0-1矩陣［11］，向量x的元素是0或者1，用一個n位的二進制串作為染色體結構，n是矩陣A的列數(shù)，第i位上的值“1”意味著第i列被選擇。

進行模糊測試時，每個程序都有自己所包含的基本代碼塊，根據(jù)基本塊地址找到的內容就是對應的代碼塊?；緣K地址信息的獲取是比較方便的，故將基本塊地址作為研究對象（每個基本地址塊相當于遺傳算法中的基因）。每個樣本看作一個以基本代碼塊地址為元素的集合（樣本相對于遺傳算法中的染色體）。樣本中如果存在某個基本地址塊就用“1”表示，否則用“0”表示，所有的樣本構成一個以0或1為元素的0-1矩陣。矩陣中的“1”即表示染色體的基因，每一列基因的集合相當于一個染色體。

3.2 啟發(fā)式遺傳算法改進染色體

選擇的染色體都會有自己獨特的基因存在，交叉重疊的基因也不計其數(shù)。在進行集合覆蓋時，需要確定最小覆蓋集合并保證該集合冗余最小。

在實際的遺傳過程中，由于變異操作產生的染色體并不適合問題集合，本文不再對新個體的變異基因進行修復，而是將變異產生的新個體直接舍棄（由于原始數(shù)據(jù)較相似，出現(xiàn)新的基因的概率很小）。遺傳算法執(zhí)行后會保留所有產生的染色體，該啟發(fā)式算法的作用包括以下2點：①消除因為基因重復產生的冗余；②選擇更優(yōu)質的染色體（包含的基因多且基因組合更豐富）。

啟發(fā)式算法闡述如下：

1）矩陣中的染色體和基因表示。

在0-1矩陣中，一列表示一個染色體，矩陣中的“1”表示某個染色體包含這個基因，“0”表示該染色體不包含該基因。算法使用性能代價比的優(yōu)先思想：性能指的是染色體中某位基因所對應集合中的列包含“1”的個數(shù)，個數(shù)越多，則該列覆蓋的行數(shù)就越多，說明該染色體的性能比較高。假設一組染色體使用遺傳算法時產生的所有染色體集合為：Sall＝｛s1，s2，s3，s4，s5｝，s1＝｛2，4，6｝，s2＝｛1，6｝，s3＝｛3，5｝，s4＝｛2，3，7｝，s5＝｛1，7｝（本文采用數(shù)字來表示其包含的基因及位置）。

2）染色體的基因交換。

假設A1和A2是父代的2個染色體，B1和B2是染色體交換之后所得的孩子染色體?？梢愿采w矩陣A的集合，借助集合C1和C2，用其來存放基因沒有覆蓋的行號；集合D1和D2用來存放B1和B2包含的全部基因。例如，A1＝｛s1，s5｝，A2＝｛s2，s3，s4｝集合，B1、B2、C1和C2均為空集，D1＝｛1，2，3，4，5，6，7｝，D2＝｛1，2，3，4，5，6，7｝。

①計算集合A1和A2中每個基因體的性能η，即每列所包含的“1”的個數(shù)，“1”越多，表示該染色體能覆蓋行越多，其包含的基因就越多，其性能就越高。此時各個基因的性能為：ηs1＝ηs4＝3，ηs2＝ηs3＝ηs5＝2。

②A1和A2中性能最高的染色體放入集合B1，統(tǒng)計該染色體包含的基因，并在集合D1中將其刪除，計算其未包含的基因，將這些基因的行號存入集合C1，再按照相同方法排列A1和A2剩下的基因到B1，最后將其他的基因放入B2。

③在進行基因選擇時，可能會出現(xiàn)一些基因性能一樣的情況，因此在性能相同的基因中選取最優(yōu)質的基因是算法設計的關鍵。例如，假設集合父輩A1中有2個性能一樣的基因：s1＝｛2，4，6｝，s2＝｛1，4，6｝，當前集合B1中包含一個基因s3＝｛2，3，5，6｝，s1、s2作為被選擇對象，s2和s3中相同的代碼塊要多于s1和s3的代碼塊，因此選擇s2比s1更合適。除此之外，模糊測試樣本在進行變異時，會根據(jù)自己的代碼塊隨機變異生成測試用例。例如，s1＝｛2，4，6｝，s2＝｛1，4，6｝，當前集合B1中包含一個染色體s3＝｛2，3，5，6｝。在染色體s1中，2號和6號代碼塊在B1中已經出現(xiàn)，代碼塊進行變異后，相當于產生了一個新的基因組合。s3中，當3號和5號基因不變異時，剩下的2號和6號的基因組合與染色體s1在4號基因不產生變異的基礎上是一樣的效果。相比較，染色體s2除了4號基因，1號和6號基因在進行變異時會產生新的組合，進而產生新的測試用例。在實現(xiàn)消除冗余的基礎上，在進行下一個染色體選擇時，會出現(xiàn)性能相同的染色體，但其所包含的基因是不同的；在進行選擇前，將等待選擇的性能相同的染色體與集合B1中已選的染色體做“差”，記錄“差”集的元素個數(shù)，按照上述規(guī)則，元素個數(shù)多的“差”集與已選染色體不相同的個數(shù)就越多，那么對應的染色體即為下個候選染色體。

啟發(fā)式遺傳算法在原始種群的基礎上借助于0-1矩陣獲取所需染色體；在不需要改變遺傳算法工作過程的前提下優(yōu)化搜索條件，提升模糊測試的效率。

3.3 啟發(fā)式遺傳算法實現(xiàn)

啟發(fā)式遺傳算法的實現(xiàn)過程在理論意義上與傳統(tǒng)的遺傳算法是沒有區(qū)別的，同樣需要重點考慮以下幾個方面：①種群大小和種群初始化。種群樣本集的大小可以人為控制，而不隨機選擇。②父代選擇。在千萬樣本集中選擇2個樣本集作為父代，這是遺傳算法仿生物的表現(xiàn)。③交叉率。確定父代在染色體的某個點進行交叉繁殖產生來后代。④變異率。產生后代的方法不僅依靠交叉，變異也是新物種最重要的來源。⑤精英比率。直接進入下一代而不參與基因交換的優(yōu)秀個體的比例。⑥停止準則。傳統(tǒng)的遺傳算法需設定界限；樣本集合覆蓋問題需要設定其遺傳的代數(shù)，或者某一個子代覆蓋了所有測試路徑時停止。

1）種群大小和種群初始化。

使用遺傳算法解決實際問題時，種群的大小對遺傳算法所求得的解的質量有很大影響。適當?shù)姆N群數(shù)量可以提高算法的性能。種群數(shù)量過大，影響算法的效率；種群數(shù)量過小，整個算法過程起到的作用不大，反而將集合問題復雜化。在樣本集精簡問題中，本文算法沒有對種群的大小進行太多的限制，數(shù)量根據(jù)實際情況自行定義，但是也會對不同種群數(shù)量進行不同的測試，以便粗略地獲取較好的種群數(shù)量范圍。

2）父代的選擇。

父代的選擇是對種群中每個個體賦予的產生后代的機會。一般選擇方法包括隨機選擇法、錦標賽選擇法和輪盤賭注法。本文采用輪盤賭注法，其基本思想是：個體被選擇的概率與其適應度大小成正比。具體實現(xiàn)操作如下：

①計算出種群每個個體的適應度fi（i＝1，2，…，M，M為種群大?。?。

④在［0，1］區(qū)間內產生一個均勻分布的偽隨機數(shù)r。

⑤若r＜q1，則選擇個體1，否則，選擇個體k，使得：qk－1＜r≤qk成立。

⑥重復④、⑤共M次。

3）交叉率［12］的選擇。

交叉是產生新個體的主要方法，在被選中的父代中確定一個交叉點，使雙親在交叉點進行基因的重組。交叉率是用來設定交叉池中參與交叉的染色體的個數(shù)，合理的交叉率可以保證交叉池中不斷產生新個體，且不會產生過多的新個體，導致遺傳秩序破壞。不同的交叉方法對應著不同的交叉率，當前主流的方案是采用自適應方法。

4）變異率［13］的選擇。

變異率指的是一個種群中發(fā)生變異的基因數(shù)目與全體基因數(shù)目的比例。變異是產生新個體的另一種方式，可以通過設定隨機變異的基因數(shù)也可以設定變異率來控制變異情況。在本文所研究的樣本集精簡中，變異可以將包含獨特基因的染色體提前納入到所設定的搜索規(guī)則中，以便于保證遺傳算法的全局性。為此本文采用實驗來設定合適的變異率，將最后一條含有獨特基因的染色體混入其他染色體，并使用本文提出的啟發(fā)式遺傳算法來進行選擇。

圖1給出了變異率在0.5、0.6和0.7時待選基因隨著初始染色體數(shù)量的增加被啟發(fā)式遺傳算法選入的時間變化。由圖1可以得出，變異率為0.6時，花費時間最少。變異率過小會導致參與變異的染色體過少，并不能將含有獨特基因的染色體提前錄入集合；變異率過高將會使得參與變異的染色體過多，更容易產生一些非法的數(shù)據(jù)并且增大時間開銷。因此，綜合考慮后，本文啟發(fā)式遺傳算法選取的變異率為0.6。

圖1 不同變異率選取染色體時間折線圖Fig.1 Broken line graph of chromosome selection time with differentmutation rates

5）精英比率。

當前種群中適應度最高的個體不參與交叉運算和變異運算，而是用來替換掉本代群體中經過交叉、變異等遺傳操作后所產生的適應度最低的個體，本例中設置精英比率為0.08。

6）停止準則。

遺傳算法在實際操作中都要經過多代進化，直到適應值趨于穩(wěn)定，或者找到最優(yōu)解或者達到規(guī)定的遺傳代數(shù)，進化過程結束。本文的樣本集精簡目標是在不降低代碼覆蓋的前提下盡可能降低測試用例的數(shù)量。當算法執(zhí)行到特定迭代次數(shù)或選擇出的測試用例不再發(fā)生變化時，算法停止。

4 實驗設置與評估

4.1 實驗準備

1）實驗環(huán)境。實驗在W indows 10系統(tǒng)下，配置為Intel Core i7-4790 CPU 3.6 GHz，8 GB內存，使用peach等工具采用啟發(fā)式遺傳算法對模糊測試樣本集進行精簡優(yōu)化。

2）測試環(huán)境與目標程序。在模糊測試實驗中，本文選取peach［14］作為模糊測試工具：①安裝方便；②有開放的使用說明；③不同的命令可實現(xiàn)多種操作，在獲取樣本的執(zhí)行路徑時無需再借助于其他工具。同時選取 mspaint、pdfium、VLC Player作為目標程序。

3）數(shù)據(jù)來源。本文實驗所需的jpg、PDF、AVI類型數(shù)據(jù)來源于互聯(lián)網開源數(shù)據(jù)集。此數(shù)據(jù)集中包括很多重復數(shù)據(jù)，并且不同數(shù)據(jù)之間存在交叉；其將增加模糊測試樣本集錄入的時間，并使peach在變異時產生更多重復甚至沒有任何利用價值的測試用例。

4.2 實驗方法與分析

3.3節(jié)闡述了本文方案的算法評價指標，通過時間復雜函數(shù)來展現(xiàn)算法隨著初始數(shù)據(jù)的變化而變化的程度，而這些表現(xiàn)可以多種角度來展示。為了更直觀地展現(xiàn)算法的有效性，設計了以下實驗，并以jpg類型數(shù)據(jù)實驗過程進行分析。

1）樣本集數(shù)量。

啟發(fā)式遺傳算法在0-1矩陣的基礎上操作，將矩陣中的元素“1”看作是遺傳算法中的染色體。在遺傳算法過程中，通過父代染色體的變異和交叉產生新的染色體，父代的選擇也是樣本精簡的一個過程，只選擇性能好的染色體作為父代，直至進化到停止準則要求時間。實驗中，對初始樣本集做了定向的選擇。jpg1：隨機選擇；jpg2：3組jpg1；jpg3：隨機選擇，jpg4：隨機選擇。精簡樣本集的數(shù)量與初始樣本集的數(shù)量關系在表1中給出。由前2組數(shù)據(jù)可以看出，第2組數(shù)據(jù)在啟發(fā)式遺傳算法后數(shù)量明顯減少，jpg2包含3組jpg1，jpg2的精簡樣本集數(shù)量與第1組一樣，啟發(fā)式遺傳算法在某種程上可以對樣本進行精簡，但是jpg2是特殊的數(shù)據(jù)組，不能體現(xiàn)算法的實用性。jpg3隨機選取的2 000個樣本集和jpg4隨機選擇的4 000個樣本集，其經過啟發(fā)式遺傳算法優(yōu)化后獲得相應精簡樣本集，即啟發(fā)式遺傳算法并不會受選取樣本的影響。從jpg2和jpg3兩組數(shù)據(jù)可以看出，該啟發(fā)式遺傳算法可以減少樣本集的數(shù)量；從jpg1、jpg3和jpg4的初始樣本集數(shù)量和精簡樣本集的數(shù)量進行觀察，假設存在精簡比例，那么jpg3的精簡樣本集數(shù)量應該是818，jpg4的精簡樣本集數(shù)量應該是1 636，而實際精簡樣本集數(shù)量卻比期望低。這是因為：選取樣本集數(shù)越大，該樣本集所包含“基因”越多，其可覆蓋“染色體”就越多，剩余不能覆蓋的“染色體”就越少，那么精簡樣本集數(shù)量就越少。

表1 樣本集數(shù)量Tab le 1 Num ber of sam p le sets

2）模糊測試時間。

為了驗證本文啟發(fā)式遺傳算法的有效性及能否提升模糊測試效率，對整體模糊測試時間進行統(tǒng)計。將表1中所采用的4組數(shù)據(jù)進行啟發(fā)式遺傳算法優(yōu)化后進行模糊測試，其花費的時間如表2所示，通過模糊測試時間的變化來說明該啟發(fā)式遺傳算法是否可以提升模糊測試效率。樣本數(shù)量與測試用例個數(shù)的對比情況如圖2所示。在一定程度上，測試用例的產生主要取決于原始樣本的最小樣本集合。模糊測試時間與樣本數(shù)量情況如圖3所示。精簡后的樣本模糊測試時間低于未精簡樣本的模糊測試時間；樣本集精簡后模糊測試的時間比精簡前降低了22%。本質上，模糊測試用例的數(shù)量由輸入樣本集的數(shù)量來決定，而模糊測試用例通過啟發(fā)式遺傳算法去除冗余可以提升模糊測試的效率。

圖2 測試用例個數(shù)與樣本數(shù)量Fig.2 Number of test cases and number of samp les

圖3 模糊測試時間與樣本數(shù)量Fig.3 Fuzzy testing time and sample size

表2 模糊測試時間Tab le 2 Fuzzy testing tim e

3）樣本質量。

每個樣本都有對應的代碼塊，根據(jù)不同的代碼塊變異而產生測試用例。在未精簡時，重復樣本產生無用測試用例。在時間一定的前提下，輸入同一組初始種群，對產生的測試用例進行標記以保證獲取的測試用例的不重復性，統(tǒng)計精簡前后變異產生的測試用例的數(shù)量。本文從jpg3和jpg4中各取一個子集，名為Test1和Test2。實驗測試用例數(shù)據(jù)情況如表3所示。測試時間一定時，未精簡的樣本集短時間內產生的測試用例大于精簡后的樣本集所產生的測試用例，但其標記后的測試用例個數(shù)小于精簡后的標記個數(shù)。樣本集在經過啟發(fā)式遺傳算法后，其樣本的質量有所提升；在相同的時間內，其產生的測試用例存在的重復性小，同時精簡前后的代碼覆蓋率沒有發(fā)生變化，算法兼顧了樣本質量。

表3 測試用例數(shù)據(jù)Tab le 3 Test case data

4）對比實驗。

通過比較文獻［3，15］提出的算法，觀察不同模糊測試樣本集優(yōu)化方案的處理效果。文獻［3，15］對比實驗按照文獻原文中設定參數(shù)進行精簡優(yōu)化，對千兆級樣本數(shù)據(jù)進行處理，實驗數(shù)據(jù)如表4所示。通過表4可以觀察出，使用文獻［3，15］和本文所述樣本集精簡方案對初始樣本集進行優(yōu)化后，樣本集中數(shù)量有一定下降，且代碼覆蓋率都維持在初始樣本水平，保證了樣本質量。但進一步觀察，結合圖4所示，貪心逼近算法運算速度較快，但需多次迭代方能達到和其他算法相同的精簡數(shù)量，因此其速度卻遠遠要慢于啟發(fā)式遺傳算法的速度；并且如表4所示，本文所述方案處理過的樣本集中數(shù)量少于文獻［3，15］提出的方案，說明經過本文所述方案優(yōu)化后的樣本集更加有效。

圖4 不同算法產生相同精簡樣本集所需時間對比Fig.4 Comparison of time required for different algorithms to produce the same simplified sample set

表4 多種方案測試樣本數(shù)量和覆蓋率Table 4 Test sam p le size and coverage rate for m ultip le schem es

5 結 論

1）啟發(fā)式遺傳算法在遺傳算法上進行改進并且應用到集合覆蓋問題中，通過染色體來表示集合中的覆蓋情況，以高質量的染色體為背景，對染色體進行啟發(fā)式改進，使之在種群中隨時進化，從而精簡優(yōu)化樣本集。該方案比傳統(tǒng)方案壓縮率提升約40%，展示了該算法的有效性。

2）本文在進行優(yōu)質染色體選擇過程中使用0-1矩陣與集合覆蓋的方式來完成優(yōu)質染色體的選取工作，并且改進了基因交叉的規(guī)則，加快模糊測試速度，同時能夠兼顧樣本質量和處理時間，測試時間降低了約22%，比傳統(tǒng)方式更加高效。