王曙燕 王瑞 孫家澤

摘 要：針對(duì)測(cè)試用例自動(dòng)化生成技術(shù)中效率較低的問(wèn)題，嘗試引入新的細(xì)菌覓食算法，并結(jié)合測(cè)試用例生成問(wèn)題提出了一種基于細(xì)菌覓食算法的改進(jìn)算法（IM-BFOA）。IM-BFOA首先采用Kent映射來(lái)增加細(xì)菌的初始種群和全局搜索的多樣性，其次針對(duì)算法中趨化階段的步長(zhǎng)進(jìn)行自適應(yīng)設(shè)計(jì)，使其在細(xì)菌趨化過(guò)程中更加合理化，并通過(guò)實(shí)驗(yàn)仿真驗(yàn)證其合理性，最后根據(jù)被測(cè)程序構(gòu)造適應(yīng)度函數(shù)來(lái)加速測(cè)試數(shù)據(jù)的優(yōu)化。實(shí)驗(yàn)結(jié)果表明，與遺傳算法（GA）、粒子群優(yōu)化（PSO）算法和標(biāo)準(zhǔn)細(xì)菌覓食優(yōu)化算法（BFOA）相比，該算法在保證覆蓋率的前提下，在迭代次數(shù)和運(yùn)行時(shí)間方面都是較優(yōu)的，可有效提高生成測(cè)試用例的效率。

關(guān)鍵詞：測(cè)試用例生成;細(xì)菌覓食算法;Kent映射;自適應(yīng)步長(zhǎng);適應(yīng)度函數(shù)

中圖分類號(hào)： TP311.5

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）03-0845-06

Abstract： Aiming at the low efficiency of test case automatic generation technology， an IMproved Bacterial Foraging Optimization Algorithm （IM-BFOA） was proposed with introduction of Knet map. Firstly， Kent map was used to increase the diversity of the initial population and global search of bacteria. Secondly， the step size of chemotaxis stage in the algorithm was adaptively designed to make it more rational in the process of bacterial chemotaxis. Finally， a fitness function was constructed according to the program under test to accelerate the optimization of test data. The experimental results show that compared with Genetic Algorithm （GA）， Particle Swarm Optimization （PSO） algorithm and standard Bacterial Foraging Optimization Algorithm （BFOA）， the proposed algorithm is the best in terms of iterations number and running time with the guarantee of coverage and has high efficiency of test case generation.

Key words： test case generation; Bacterial Foraging Optimization Algorithm （BFOA）; Kent map; adaptive step size; fitness function

0 引言

軟件設(shè)計(jì)上的缺陷和代碼錯(cuò)誤嚴(yán)重影響了軟件的可靠性和可用性，軟件測(cè)試作為發(fā)現(xiàn)軟件問(wèn)題的一種方法受到了廣泛關(guān)注[1]。軟件測(cè)試是軟件開(kāi)發(fā)整個(gè)流程中必不可少的一環(huán)，也是保障軟件可靠性的重要手段。軟件測(cè)試可以檢測(cè)軟件中的bug，但軟件測(cè)試耗時(shí)費(fèi)力，它消耗了幾乎50%的軟件系統(tǒng)開(kāi)發(fā)資源[2]。其中，測(cè)試用例生成是關(guān)鍵性步驟，其生成的效率決定了軟件測(cè)試的整體效率，對(duì)整個(gè)軟件測(cè)試工程的發(fā)展具有重要的影響。

在測(cè)試用例生成的發(fā)展過(guò)程中，根據(jù)不同的測(cè)試準(zhǔn)則和粒度，產(chǎn)生了很多研究方法，主要有：數(shù)據(jù)流準(zhǔn)則法[3]、需求分析法[4]、基于搜索的優(yōu)化方法等。其中基于搜索的優(yōu)化方法因其尋優(yōu)能力較強(qiáng)而受到很多研究者的青睞，它的核心是啟發(fā)式搜索算法，通過(guò)將尋找最優(yōu)的測(cè)試用例問(wèn)題轉(zhuǎn)換為函數(shù)的最優(yōu)化問(wèn)題，結(jié)合生成測(cè)試用例的具體方法設(shè)計(jì)適應(yīng)度函數(shù)，來(lái)實(shí)現(xiàn)測(cè)試用例的自動(dòng)生成。Khan等[5]將遺傳算法（Genetic Algorithm， GA）和變異分析方法融合來(lái)生成測(cè)試用例，該方法通過(guò)變異評(píng)分來(lái)優(yōu)化測(cè)試用例，但這需要運(yùn)行變異體得到變異評(píng)分，增加了運(yùn)行時(shí)間。Andalib等[6]利用粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法生成測(cè)試用例，并將其與遺傳算法進(jìn)行比較，得到了更高的效率，但該方法適用于不具有數(shù)據(jù)依賴性的程序。郭后錢(qián)等[7]利用動(dòng)態(tài)集合進(jìn)化算法覆蓋弱變異分支生成測(cè)試用例，降低減小了時(shí)間開(kāi)銷和測(cè)試用例規(guī)模。戚榮志等[8]利用Spark將遺傳算法進(jìn)行并行化，以此降低生成組合測(cè)試用例的計(jì)算成本，該方法相比串行的遺傳算法得到了較高的效率。劉淵等[9]利用遺傳算法生成Fuzzing測(cè)試用例，在效率和覆蓋率方面得到了顯著提高。夏春艷等[10]利用節(jié)點(diǎn)概率設(shè)計(jì)遺傳算法的自適應(yīng)函數(shù)來(lái)提高測(cè)試用例的生成效率。李龍澍等[11]將果蠅算法應(yīng)用到測(cè)試用例領(lǐng)域，提高了生成測(cè)試用例的效率。這些算法都從不同的角度對(duì)測(cè)試用例生成提供了思路。

細(xì)菌覓食算法（Bacteria Foraging Optimization Algorithm，BFOA）[12]是受生物醫(yī)學(xué)領(lǐng)域?qū)Υ竽c桿菌的群體覓食行為啟發(fā)而總結(jié)出來(lái)的。由于BFOA群體智能算法可并行搜索、易于跳出局部極小值的優(yōu)點(diǎn)已經(jīng)吸引了不同理論研究者的注意，在電氣工程與控制、調(diào)度問(wèn)題、模式識(shí)別等領(lǐng)域得到了有效應(yīng)用[13]，但該算法尚未在測(cè)試用例生成領(lǐng)域中實(shí)踐，且該算法在尋優(yōu)過(guò)程中存在收斂速度慢、精度不高的問(wèn)題[14]。針對(duì)這些問(wèn)題，本文引入了Kent映射[15]來(lái)增加種群多樣性，并且設(shè)計(jì)自適應(yīng)步長(zhǎng)，以此來(lái)提高搜索的精度和效率。

1 測(cè)試用例生成方法

1.1 問(wèn)題的編碼

測(cè)試用例生成模型主要包括三部分：靜態(tài)分析模塊、測(cè)試驅(qū)動(dòng)模塊、算法生成測(cè)試用例模塊。

靜態(tài)分析模塊 通過(guò)分析被測(cè)程序得到控制流圖，選擇被測(cè)程序的目標(biāo)路徑得到算法的部分參數(shù)，同時(shí)結(jié)合控制流圖得到測(cè)試驅(qū)動(dòng)模塊的插樁程序。

測(cè)試驅(qū)動(dòng)模塊 測(cè)試驅(qū)動(dòng)模塊的輸入為算法生成的測(cè)試用例，通過(guò)執(zhí)行插樁的被測(cè)程序得到該測(cè)試用例的適應(yīng)度值并傳回給算法。

算法生成測(cè)試用例模塊 該模塊主要根據(jù)適應(yīng)度值來(lái)進(jìn)行判斷迭代。由靜態(tài)分析模塊得到的參數(shù)開(kāi)始執(zhí)行改進(jìn)的細(xì)菌覓食算法（IMproved Bacterial Foraging Optimization Algorithm， IM-BFOA），將生成的測(cè)試用例交付給測(cè)試驅(qū)動(dòng)模塊得到適應(yīng)度值后利用IM-BFOA來(lái)迭代找到最優(yōu)的測(cè)試用例。

因而，針對(duì)測(cè)試用例生成問(wèn)題，首先，分析被測(cè)程序的控制流圖，得到目標(biāo)路徑并對(duì)其進(jìn)行插樁;其次，結(jié)合IM-BFOA生成初始種群，即初始的測(cè)試用例，運(yùn)行插樁程序得到適應(yīng)度值;最后，利用IM-BFOA迭代優(yōu)化適應(yīng)度值，得到更優(yōu)的測(cè)試用例。

1.2 插樁方式與適應(yīng)度函數(shù)的設(shè)定

用算法解決具體的實(shí)際問(wèn)題，是通過(guò)適應(yīng)度函數(shù)來(lái)進(jìn)行銜接，設(shè)計(jì)合理的適應(yīng)度函數(shù)是更好解決問(wèn)題的前提。在利用IM-BFOA解決測(cè)試用例生成問(wèn)題中，適應(yīng)度函數(shù)貫穿整個(gè)流程，無(wú)論是利用Kent映射產(chǎn)生初始種群，還是算法的趨化和復(fù)制操作，都是根據(jù)適應(yīng)度值的高低決定操作步驟，而適應(yīng)度值需要通過(guò)程序插樁來(lái)得到。針對(duì)不同的分支情況具體的插樁方式及分支距離如表1所示。

本文采用分支距離法[16]來(lái)評(píng)價(jià)測(cè)試用例的優(yōu)劣。該方法首先需要針對(duì)分支進(jìn)行插樁得到分支函數(shù)信息，現(xiàn)針對(duì)被測(cè)程序目標(biāo)路徑上的m個(gè)分支進(jìn)行插樁，插樁函數(shù)如式（1）所示：

其中： f（i）表示第i個(gè)分支的插樁函數(shù);Xi表示測(cè)試用例在第i個(gè)分支的數(shù)據(jù);x表示分支的值。若f（i）小于等于零表示該測(cè)試用例可覆蓋到該分支，則令f（i）=0;若f（i）大于零，則得到的值就是測(cè)試用例與該分支的距離，值越大代表測(cè)試用例越遠(yuǎn)離該分支。

最終計(jì)算適應(yīng)度函數(shù)式如（2）所示：

式（2）使得值的范圍在（0，1]區(qū)間，值越大表示測(cè)試用例越好。當(dāng)適應(yīng)度值為1時(shí)，表明該測(cè)試用例可完全覆蓋該目標(biāo)路徑。

1.3 IM-BFOA生成測(cè)試用例

利用IM-BFOA生成測(cè)試用例的流程如圖1所示。其中：p為測(cè)試用例問(wèn)題的維度，根據(jù)被測(cè)程序?qū)С?S是細(xì)菌初始種群;Ns是趨向操作中可前進(jìn)的最大步數(shù);C（i）是趨化操作中的游動(dòng)步長(zhǎng);Nc是趨化操作的次數(shù);Nre是復(fù)制操作的次數(shù);Ned是遷徙操作的次數(shù);Ped是細(xì)菌遷徙概率。

此流程圖說(shuō)明了IM-BFOA如何解決測(cè)試用例生成問(wèn)題：在完成對(duì)被測(cè)程序的插樁后，利用IM-BFOA生成初始的測(cè)試用例，運(yùn)行程序得到適應(yīng)度值，然后經(jīng)過(guò)算法的迭代優(yōu)化，使適應(yīng)度值達(dá)到最大值，完成基于搜索的測(cè)試用例生成。

2 細(xì)菌覓食算法

細(xì)菌覓食算法是一種新型的群體智能優(yōu)化搜索算法，它模擬細(xì)菌在覓食過(guò)程中的趨化（chemotaxis）、復(fù)制（reproduction）、遷移（elimination-dispersa）三種行為。其優(yōu)化搜索的操作方法如下：針對(duì)某個(gè)問(wèn)題進(jìn)行優(yōu)化，將問(wèn)題的可行域確定為其細(xì)菌的覓食區(qū)域，將問(wèn)題的可行解抽象為細(xì)菌在可行域中的位置，將細(xì)菌個(gè)體的適應(yīng)度轉(zhuǎn)化為某個(gè)可行解針對(duì)問(wèn)題是否優(yōu)化的判斷依據(jù)。

2.1 趨化行為

趨化行為主要靠翻轉(zhuǎn)和游動(dòng)兩種操作來(lái)完成。翻轉(zhuǎn)指的是細(xì)菌向任意方向移動(dòng)單位步長(zhǎng)的行為。游動(dòng)指的是若翻轉(zhuǎn)后的適應(yīng)度值變高，那么將繼續(xù)在同一方向進(jìn)行移動(dòng)，直至達(dá)到最大的游動(dòng)步長(zhǎng)或者適應(yīng)度值不再得到改善;若翻轉(zhuǎn)后適應(yīng)度值下降，那么會(huì)繼續(xù)向另一個(gè)隨機(jī)的方向進(jìn)行翻轉(zhuǎn)。細(xì)菌的趨化行動(dòng)可以用式（3）表示：

其中：θ（i， j，k，l）表示細(xì)菌i在第j次趨化、第k次復(fù)制、第l次遷移后所在的位置函數(shù);C（i）是細(xì)菌i的趨化行動(dòng)中的游動(dòng)步長(zhǎng);Δ（i）是細(xì)菌i的趨化行動(dòng)中翻轉(zhuǎn)操作的單位隨機(jī)方向向量。

2.2 復(fù)制行為

復(fù)制行為遵循適者生存的規(guī)律。在細(xì)菌復(fù)制前，根據(jù)適應(yīng)度值降序排序，選取總細(xì)菌個(gè)數(shù)一半且適應(yīng)度值高的細(xì)菌分裂成兩個(gè)細(xì)菌，適應(yīng)度值較低的一半細(xì)菌則被淘汰。復(fù)制行為確保了細(xì)菌種群的數(shù)量保持不變，這樣可以大大提高搜索的速度。

2.3 遷移行為

遷移行為是為了防止細(xì)菌陷入局部最優(yōu)點(diǎn)，一些細(xì)菌被隨機(jī)地以小概率清除，當(dāng)某個(gè)細(xì)菌滿足遷移發(fā)生的概率時(shí)，該細(xì)菌就會(huì)被新的細(xì)菌所替代，新細(xì)菌是在解空間內(nèi)隨機(jī)初始化來(lái)的個(gè)體。遷移操作增加了細(xì)菌跳出局部最優(yōu)的可能性。

3 改進(jìn)的細(xì)菌覓食算法

為了解決細(xì)菌覓食算法搜索效率和精度不高的問(wèn)題，引入了混沌序列，并設(shè)計(jì)了自適應(yīng)步長(zhǎng)。

3.1 Kent映射

在基本的細(xì)菌覓食算法當(dāng)中，采用隨機(jī)的方式來(lái)產(chǎn)生初細(xì)菌初始種群，這種隨機(jī)性會(huì)使細(xì)菌分布不均勻，這會(huì)降低搜索的效率;因而可利用混沌序列來(lái)進(jìn)行初始化，增加種群的多樣性。

混沌指的是一種非線性的狀態(tài)，在一定的范圍內(nèi)混沌變量具有隨機(jī)性和遍歷性。因此本文將混沌映射加入到細(xì)菌覓食算法的初始化階段，利用混沌映射產(chǎn)生混沌序列?；煦缧蛄袝?huì)使得數(shù)據(jù)在某個(gè)范圍內(nèi)均勻分布，提高了解的質(zhì)量，使得某個(gè)解盡可能地靠近最優(yōu)解，從而提高算法搜索的效率。在眾多的混沌映射模型當(dāng)中，最基礎(chǔ)且使用率最高的就是logistic映射，但該映射模型在遍歷均勻性方面不如Kent映射[17]，因而，本文使用Kent映射來(lái)產(chǎn)生初始化種群，其具體計(jì)算如式（4）所示：

改進(jìn)后的細(xì)菌覓食算法的初始化步驟如下。

步驟1 設(shè)置最大的迭代次數(shù)為M，種群的規(guī)模為S。

步驟4 將得到的混沌向量Y通過(guò)式（5）映射到細(xì)菌覓食算法的初始解空間：

其中：p為搜索空間的最小值，q為最大值。

步驟5 計(jì)算適應(yīng)度值，選取S個(gè)最高的適應(yīng)度值作為細(xì)菌覓食算法的初始種群。

3.2 自適應(yīng)步長(zhǎng)的設(shè)計(jì)

在基本的細(xì)菌覓食算法當(dāng)中，不同的細(xì)菌采用的是固定的步長(zhǎng)來(lái)進(jìn)行趨化行為，而步長(zhǎng)的大小會(huì)直接影響到細(xì)菌覓食的尋優(yōu)速度和精度。如果步長(zhǎng)較大，會(huì)使得解的精度不高;如果步長(zhǎng)較小，算法可能會(huì)陷入局部最優(yōu)，不利于算法的收斂。因而，選擇合適的步長(zhǎng)對(duì)算法而言尤為重要。

3.2.1 趨化次數(shù)的影響

對(duì)細(xì)菌覓食算法的趨化步長(zhǎng)進(jìn)行分析如下：算法初期，要求步長(zhǎng)較大，以便盡快地搜索到最優(yōu)解;隨著趨化次數(shù)的增加，細(xì)菌逐步靠近最優(yōu)解，需要使得搜尋的步伐減小，進(jìn)行精細(xì)搜尋得到最優(yōu)解，以防止步長(zhǎng)過(guò)大而造成解震蕩情況，從而提高算法的尋優(yōu)速率。

根據(jù)步長(zhǎng)隨趨化次數(shù)的增加而減小的特性，利用神經(jīng)網(wǎng)絡(luò)當(dāng)中的激活函數(shù)Gaussian，添加非線性因素來(lái)解決線性模型的表達(dá)能力較弱的問(wèn)題，以此來(lái)解決較為復(fù)雜的問(wèn)題。Gaussian激活函數(shù)原型如式（6）所示：

結(jié)合細(xì)菌覓食算法得到步長(zhǎng)趨化次數(shù)學(xué)習(xí)因子如式（7）所示：

3.2.2 適應(yīng)度值的影響

步長(zhǎng)與細(xì)菌的適應(yīng)度值有關(guān)，當(dāng)細(xì)菌適應(yīng)度值較小時(shí)，步長(zhǎng)應(yīng)該較大，從而使得該細(xì)菌以較大的步長(zhǎng)進(jìn)行搜尋。因而設(shè)計(jì)適應(yīng)度學(xué)習(xí)因子如式（8）所示：

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

為了對(duì)比分析4種方法，本實(shí)驗(yàn)基于eclipse平臺(tái)，利用Java語(yǔ)言實(shí)現(xiàn)4種算法，并對(duì)被測(cè)程序的目標(biāo)路徑進(jìn)行分析插樁，然后利用算法對(duì)每個(gè)被測(cè)程序獨(dú)立運(yùn)行多次后，統(tǒng)計(jì)數(shù)據(jù)得到平均值來(lái)進(jìn)行實(shí)驗(yàn)分析。

本文實(shí)驗(yàn)以5個(gè)開(kāi)源程序?yàn)楸粶y(cè)對(duì)象，其詳細(xì)信息見(jiàn)表2，從多個(gè)角度評(píng)估IM-BFOA生成測(cè)試用例的有效性。并通過(guò)與遺傳算法（Genetic Algorithm， GA）、粒子群優(yōu)化（Particle Swarm Optimization Algorithm， PSO）算法、基本細(xì)菌覓食算法（BFOA）、文獻(xiàn)[10]中改進(jìn)的遺傳算法、文獻(xiàn)[11]中果蠅算法的部分實(shí)驗(yàn)研究成果進(jìn)行對(duì)比分析。

程序1的目標(biāo)路徑選擇較為復(fù)雜的等邊三角形判定;程序2的目標(biāo)路徑為兩個(gè)數(shù)組是否相等，這里設(shè)置數(shù)組長(zhǎng)度是4;程序3的目標(biāo)路徑為檢驗(yàn)銀行卡是否有效，將其長(zhǎng)度設(shè)定為10，且選擇每個(gè)代碼在0～9之間，并且符合LuhnCheck算法合法的路徑。程序4和程序5是兩個(gè)工業(yè)用例，Sed目標(biāo)路徑為覆蓋長(zhǎng)選項(xiàng)命令行解析函數(shù)getopt_long（）的路徑，F(xiàn)lex目標(biāo)路徑為計(jì)算輸入的字符個(gè)數(shù)和行數(shù)。

為了保證在公平的實(shí)驗(yàn)環(huán)境下進(jìn)行對(duì)比分析，4種方法在某些相同參數(shù)上設(shè)置一致，例如初始種群規(guī)模、最大迭代次數(shù)、獨(dú)立運(yùn)行次數(shù)，其他不同的參數(shù)均參考其他文獻(xiàn)[18-20]進(jìn)行設(shè)置。本文選用平均迭代次數(shù)和平均運(yùn)行時(shí)間作為評(píng)判標(biāo)準(zhǔn)。具體的實(shí)驗(yàn)參數(shù)如表3所示。

4.2 實(shí)驗(yàn)分析

為了驗(yàn)證IM-BFOA算法中自適應(yīng)步長(zhǎng)的合理性，實(shí)驗(yàn)首先利用Matlab工具進(jìn)行驗(yàn)證。設(shè)置式（9）中的參數(shù)NC=10，a=1，b=0，c=1/2π，F(xiàn)max=1，F(xiàn)min=0，C（i）=0.05，F(xiàn)i分別取最大適應(yīng)度值Fmax的0.25倍，0.5倍，0.75倍，得到趨化次數(shù)與步長(zhǎng)關(guān)系如圖2所示。由圖可知，該自適應(yīng)趨化步長(zhǎng)在算法初期較大，有利于較快靠近最優(yōu)解，隨著趨化次數(shù)的增加，步長(zhǎng)逐漸減小，可利于精細(xì)搜索，符合細(xì)菌覓食算法的要求規(guī)律，初步驗(yàn)證了該自適應(yīng)步長(zhǎng)設(shè)計(jì)的合理性。

同時(shí)，為了結(jié)合測(cè)試用例生成問(wèn)題進(jìn)行實(shí)證研究，本文通過(guò)三個(gè)對(duì)比實(shí)驗(yàn)來(lái)進(jìn)行分析，其中在前兩個(gè)實(shí)驗(yàn)中所有統(tǒng)計(jì)對(duì)比的前提條件是被測(cè)程序目標(biāo)路徑的覆蓋率為100%。

實(shí)驗(yàn)一 對(duì)三角形判定程序在搜索范圍為[0，5]的條件下，記錄細(xì)菌的種群規(guī)模分別為10，20，30，40，50時(shí)，BFOA、IM-BFOA分別獨(dú)立運(yùn)行20次后的平均迭代次數(shù)和平均運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果如表4所示。從表4中可以看出，隨著種群規(guī)模的增加， BFOA算法與IM-BFOA算法的平均迭代次數(shù)和平均運(yùn)行時(shí)間都呈現(xiàn)下降趨勢(shì)，且IM-BFOA比基本的BFOA的平均迭代次數(shù)與平均運(yùn)行時(shí)間都要少，可以看出IM-BFOA的效率更高。

實(shí)驗(yàn)二 在表2所示的搜索范圍下，針對(duì)3個(gè)源程序，分別統(tǒng)計(jì)在GA、PSOA、BFOA、IM-BFOA下獨(dú)立運(yùn)行20次的迭代次數(shù)，得到的實(shí)驗(yàn)結(jié)果如圖3所示。從3個(gè)程序下在不同算法的迭代情況來(lái)看，IM-BFOA所需要的迭代次數(shù)更少，尋優(yōu)速度更快，能夠在較少的迭代次數(shù)內(nèi)找到覆蓋目標(biāo)路徑的測(cè)試用例。

實(shí)驗(yàn)三 利用IM-BFOA針對(duì)表2中編號(hào)1、4、5的3個(gè)被測(cè)程序進(jìn)行實(shí)驗(yàn)。其中，編號(hào)1的搜索范圍變?yōu)閇0，127]，與文獻(xiàn)[11]保持一致，編號(hào)4、5的實(shí)驗(yàn)參數(shù)參考文獻(xiàn)[10]進(jìn)行設(shè)置，得到的實(shí)驗(yàn)結(jié)果如表5所示。與文獻(xiàn)[11]相比，IM-BFOA在平均迭代次數(shù)和平均運(yùn)行時(shí)間上均較少。與文獻(xiàn)[10]相比，雖然本文方法的成功率較低，且在編號(hào)5中本方法的運(yùn)行時(shí)間略高于文獻(xiàn)[10]，但在其他情況下，尤其是在平均迭代次數(shù)上IM-BFOA遠(yuǎn)少于文獻(xiàn)[10]，這是因?yàn)槲墨I(xiàn)[10]在針對(duì)不可達(dá)路徑的處理需要以迭代次數(shù)為代價(jià)，而本文方法針對(duì)目標(biāo)路徑進(jìn)行處理沒(méi)有檢測(cè)不可達(dá)路徑，這同時(shí)也導(dǎo)致了成功率的降低。因此，本文方法可有效生成滿足覆蓋目標(biāo)路徑的測(cè)試用例，但仍需進(jìn)一步改進(jìn)。

綜上所述，IM-BFOA在保證被測(cè)程序目標(biāo)覆蓋率的前提下，生成測(cè)試用例的平均迭代次數(shù)和平均運(yùn)行時(shí)間均優(yōu)于GA、PSOA和BFOA，算法從整體上加快了種群的進(jìn)化過(guò)程，彌補(bǔ)克服了算法收斂速度慢、精度不高的缺點(diǎn)，使得改進(jìn)后算法能夠快速地找到覆蓋源程序目標(biāo)路徑的最優(yōu)測(cè)試數(shù)據(jù)，有效地提高了測(cè)試用例的生成效率。

5 結(jié)語(yǔ)

軟件自動(dòng)化測(cè)試的效率主要取決于生成測(cè)試用例的效率，在利用智能群體優(yōu)化算法進(jìn)行搜索生成測(cè)試用例技術(shù)中，主要取決于算法的效率。本文將細(xì)菌覓食算法應(yīng)用于測(cè)試用例的自動(dòng)生成，并且針對(duì)基本的細(xì)菌覓食算法存在的問(wèn)題，提出了一些改進(jìn)措施并證明了其合理性。本文引入Kent混沌映射對(duì)細(xì)菌的初始位置進(jìn)行均勻性分布，增加了種群的多樣性，并且對(duì)趨化操作中的步長(zhǎng)進(jìn)行自適應(yīng)設(shè)計(jì)，提高了收斂速度。同時(shí)，針對(duì)測(cè)試用例的具體問(wèn)題，對(duì)算法的適應(yīng)度函數(shù)進(jìn)行了有效的設(shè)計(jì)，用測(cè)試用例的分支覆蓋率表示適應(yīng)度值，以加快測(cè)試用例的優(yōu)化過(guò)程。本文利用三角形程序、判斷數(shù)組相等程序和檢測(cè)銀行卡有效性的LuhnCheck算法程序，將遺傳算法、粒子群算法、基本細(xì)菌覓食算法、改進(jìn)后的細(xì)菌覓食算法進(jìn)行了對(duì)比分析，實(shí)驗(yàn)結(jié)果表明了算法的可靠性和高效性，可以應(yīng)用到測(cè)試環(huán)節(jié)中的測(cè)試用例生成問(wèn)題當(dāng)中。但是，相對(duì)于復(fù)雜的大規(guī)模的程序而言，其時(shí)間效率依然沒(méi)有得到較大的提高，因而在后續(xù)工作中，可以利用細(xì)菌覓食算法的并行搜索能力，研究如何并行地生成測(cè)試用例，以期得到更高的效率來(lái)生成測(cè)試用例。

參考文獻(xiàn) （References）

[1] WU W. Research of automatic test case generation algorithm based on improved particle swarm optimization [C]// ICMMCT 2016： Proceedings of the 4th International Conference on Machinery， Materials and Computing Technology. Paris： Atlantis Press， 2016： 1558-1562.

[2] SHARMA C， SABHARWAL S， SIBAL R. A survey on software testing techniques using genetic algorithm [J]. International Journal of Computer Science Issues， 2013， 10（1）： 381-393.

[3] DENARO G， PEZZE M， VIVANTI M. Quantifying the complexity of dataflow testing [C]// Proceedings of the 8th International Workshop on Automation of Software Test. Piscataway， NJ： IEEE， 2013： 132-138.

[4] ELGHONDAKLY R， MOUSSA S， BADR N. Waterfall and agile requirements-based model for automated test cases generation [C]// Proceedings of the 2015 IEEE 7th International Conference on Intelligent Computing and Information Systems. Piscataway， NJ： IEEE， 2016： 607-612.

[5] KHAN R， AMJAD M. Automatic test case generation for unit software testing using genetic algorithm and mutation analysis [C]// Proceedings of the 2015 IEEE UP Section Conference on Electrical Computer and Electronics. Piscataway， NJ： IEEE， 2015： 1-5.

[6] ANDALIB A， BABAMIR S M. A new approach for test case generation by discrete particle swarm optimization algorithm [C]// Proceedings of the 2014 22nd Iranian Conference on Electrical Engineering. Piscataway， NJ： IEEE， 2015： 1180-1185.

[7] 郭后錢(qián)，王微微，尚穎，等.基于動(dòng)態(tài)集合進(jìn)化算法的弱變異測(cè)試用例集生成[J].計(jì)算機(jī)應(yīng)用，2017，37（9）：2659-2664.（GUO H Q， WANG W W， SHANG Y， et al. Weak mutation test case set generation based on dynamic set evolutionary algorithm [J]. Journal of Computer Applications， 2017， 37（9）： 2659-2664.）

[8] 戚榮志，王志堅(jiān)，黃宜華，等.基于Spark的并行化組合測(cè)試用例集生成方法[J].計(jì)算機(jī)學(xué)報(bào)，2018，41（6）：1064-1079.（QI R Z， WANG Z J， HUANG Y H， et al. Generating combinatorial test suite with spark based parallel approach [J]. Chinese Journal of Computers， 2018， 41（6）： 1064-1079.）

[9] 劉淵，楊永輝，張春瑞，等.一種基于遺傳算法的Fuzzing測(cè)試用例生成新方法[J].電子學(xué)報(bào)，2017，45（3）：552-556.（LIU Y， YANG Y H， ZHANG C R， et al. A novel method for fuzzing test cases generating based on genetic algorithm[J]. Acta Electronica Sinica， 2017， 45（3）： 552-556.）

[10] 夏春艷，張巖，宋麗.基于節(jié)點(diǎn)概率的路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成[J].軟件學(xué)報(bào)，2016，27（4）：802-813.（XIA C Y， ZHANG Y， SONG L. Evolutionary generation of test data for paths coverage based on node probability[J]. Journal of Software， 2016， 27（4）： 802-813.）

[11] 李龍澍，郭紫夢(mèng).應(yīng)用混沌果蠅算法的路徑覆蓋測(cè)試用例優(yōu)化技術(shù)研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2018，39（2）：362-366.（LI L S， GUO Z M. Optimization techniques research on testing data through path coverage with chaotic fruit fly algorithm [J]. Journal of Chinese Computer Systems， 2018， 39（2）： 362-366.）

[12] PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control [J]. IEEE Control Systems， 2002， 22（3）： 52-67.

[13] 周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（20）：16-21.（ZHOU Y L. Research and application on bacteria foraging optimization algorithm [J]. Computer Engineering and Applications， 2010， 46（20）： 16-21.）

[14] SADEGHIRAM S. Bacterial foraging optimisation algorithm， particle swarm optimisation and genetic algorithm： a comparative study [J]. International Journal of Bio-Inspired Computation， 2017， 10（4）： 275-282.

[15] CHEN Z， ZHOU Q. Kent chaos mapping application in the digital fountain codes [C] // Proceedings of the 30th Chinese Control Conference. Piscataway， NJ： IEEE， 2011： 4371-4376.

[16] 王令賽，姜淑娟，張艷梅，等.基于正交搜索的粒子群優(yōu)化測(cè)試用例生成方法[J].電子學(xué)報(bào)， 2014， 42（12）： 2345-2351.（WANG L S， JIANG S J， ZHANG Y M， et al. Test case generation based on orthogonal exploration and particle swarm optimization [J]. Acta Electronica Sinica， 2014， 42（12）： 2345-2351.）

[17] 劉建軍，石定元，武國(guó)寧.基于Kent映射的混合混沌優(yōu)化算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2015， 36（6）： 1498-1503.（LIU J J， SHI D Y， WU G N. Hybrid chaotic optimization algorithm based on Kent map [J]. Computer Engineering and Design， 2015， 36（6）： 1498-1503.）

[18] 姜淑娟，王令賽，薛猛，等.基于模式組合的粒子群優(yōu)化測(cè)試用例生成方法[J].軟件學(xué)報(bào)，2016，27（4）：785-801.（JIANG S J， WANG L S， XUE M， et al. Test case generation based on combination of schema using particle swarm optimization [J]. Journal of Software， 2016， 27（4）： 785-801.）

[19] 高雪笛，周麗娟，張樹(shù)東，等.基于改進(jìn)遺傳算法的測(cè)試數(shù)據(jù)自動(dòng)生成的研究[J].計(jì)算機(jī)科學(xué)，2017， 44（3）： 209-214.（GAO X D， ZHOU L J， ZHANG S D， et al. Research on test data automatic generation based on improved genetic algorithm [J]. Compter Science， 2017， 44（3）： 209-214.）

[20] 張翼鵬，葛麗娜，王紅，等.基于改進(jìn)細(xì)菌覓食算法的輿情熱點(diǎn)話題發(fā)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2017， 38（10）： 2832-2837.（ZHANG Y P， GE L N， WANG H， et al. Cluster of people opinion analysis based on improved bacterial foraging optimization [J]. Computer Engineering and Design， 2017， 38（10）： 2832-2837.）