王 曄，呂學(xué)偉

(淮陰師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 淮安 223300)

0 引言

近年來(lái)的研究顯示，元啟發(fā)式算法的參數(shù)對(duì)算法的性能有較大影響.參數(shù)決定了算法如何在空間中進(jìn)行搜索，決定了算法的靈活性和效率.理想的參數(shù)可以發(fā)揮算法的最佳性能，不理想的參數(shù)可能會(huì)影響到算法的結(jié)果，甚至造成無(wú)法找到最優(yōu)解.實(shí)踐證明選擇算法最佳性能參數(shù)不僅需要相關(guān)領(lǐng)域知識(shí)，而且需要根據(jù)要解決的問(wèn)題進(jìn)行具體分析和選擇.然而在很多情況下負(fù)責(zé)參數(shù)配置的工作人員不完全是元啟發(fā)式算法方面的專(zhuān)家，而文獻(xiàn)的推薦參數(shù)經(jīng)常發(fā)生相互矛盾，這些矛盾是由于不同的最優(yōu)參數(shù)是針對(duì)不同領(lǐng)域的問(wèn)題而引起的.對(duì)一個(gè)新出現(xiàn)的問(wèn)題，搜索空間是未知的，因此很難有一個(gè)通用的參數(shù)配置來(lái)滿(mǎn)足所有應(yīng)用的需求.在這種情況下，算法參數(shù)的設(shè)置本身就成為了一個(gè)優(yōu)化問(wèn)題.為了節(jié)省時(shí)間，工作人員通常利用一些簡(jiǎn)單的數(shù)據(jù)或者較少的迭代次數(shù)來(lái)運(yùn)行元啟發(fā)式算法，在算法運(yùn)行時(shí)再調(diào)整參數(shù)值，以取得最優(yōu)的參數(shù)值來(lái)解決特定的問(wèn)題.但是利用這種方法，即使在參數(shù)被調(diào)整到最優(yōu)的情況下，也很難保證算法在實(shí)際解決完整問(wèn)題的過(guò)程中參數(shù)是最優(yōu)的.

理論和實(shí)驗(yàn)證明在算法運(yùn)行的不同階段需要的參數(shù)值不同，這意味著事先調(diào)整參數(shù)的做法不能保證元啟發(fā)式算法性能處于最優(yōu).該問(wèn)題已經(jīng)引起重視，一些研究人員提出了適應(yīng)性參數(shù)調(diào)整方法，可以在算法搜索過(guò)程中動(dòng)態(tài)調(diào)整參數(shù)，使算法在每個(gè)運(yùn)行階段具有最優(yōu)的參數(shù)值，以提高算法性能.其中PSO算法因其具有易于理解、全局搜索能力強(qiáng)等特點(diǎn)被廣泛用于測(cè)試數(shù)據(jù)的生成[1-2].由于PSO算法也是元啟發(fā)式算法的一種，因此也會(huì)面臨參數(shù)優(yōu)化問(wèn)題.

近年來(lái)一些學(xué)者通過(guò)動(dòng)態(tài)調(diào)整慣性權(quán)值的方法來(lái)增強(qiáng)PSO算法的性能，以提高測(cè)試數(shù)據(jù)的生成效率.如：Zhu等人[3]提出根據(jù)粒子距離的目標(biāo)距離遠(yuǎn)近來(lái)動(dòng)態(tài)調(diào)整慣性權(quán)值的方法，當(dāng)粒子距離目標(biāo)較遠(yuǎn)的時(shí)候，慣性權(quán)值較大，反之則較小，改變了慣性權(quán)值線(xiàn)性遞減的調(diào)整策略，實(shí)驗(yàn)結(jié)果證實(shí)使用該方法的適應(yīng)性PSO算法的性能優(yōu)于標(biāo)準(zhǔn)PSO算法和免疫遺傳算法；Jiang等人[4]提出了一種約簡(jiǎn)的適應(yīng)性粒子群算法，在該方法中標(biāo)準(zhǔn)PSO算法中的速度分量被移除，基于粒子的適應(yīng)值和粒子的聚集度的關(guān)系來(lái)動(dòng)態(tài)調(diào)整慣性權(quán)值，當(dāng)粒子聚集度越大，粒子越集中，當(dāng)粒子聚集度越小說(shuō)明粒子越分散，設(shè)計(jì)了一種根據(jù)粒子聚集度來(lái)動(dòng)態(tài)調(diào)整慣性權(quán)重的計(jì)算公式用于測(cè)試數(shù)據(jù)的生成，實(shí)驗(yàn)結(jié)果顯示該方法能夠改善PSO算法的收斂速度，進(jìn)而能提高測(cè)試數(shù)據(jù)的生成效率.這些適應(yīng)性參數(shù)調(diào)整方法都是假設(shè)算法結(jié)果的改進(jìn)與特定參數(shù)值直接相關(guān)，但PSO算法的過(guò)程是隨機(jī)的，即使是相同的參數(shù)也可能產(chǎn)生不同的結(jié)果[5].因此,PSO算法得到的最優(yōu)值包含真實(shí)值和不確定的偏差，這種不確定的偏差被稱(chēng)為噪音.在理想情況下，PSO算法的隨機(jī)行為引起的隨機(jī)性應(yīng)該用參數(shù)調(diào)整策略來(lái)應(yīng)對(duì).為了解決此問(wèn)題，本文提出一種適應(yīng)性PSO算法，該算法在進(jìn)化過(guò)程中利用卡爾曼濾波器來(lái)動(dòng)態(tài)的調(diào)整參數(shù)，以期減少PSO算法隨機(jī)特性引起的噪聲影響，從而提高PSO算法的性能.

1 卡爾曼濾波器

本文的適應(yīng)性方法是在算法進(jìn)化過(guò)程中，利用從搜索過(guò)程中得到的反饋信息來(lái)動(dòng)態(tài)調(diào)整參數(shù)值.由于PSO算法的隨機(jī)特性，最優(yōu)解的發(fā)現(xiàn)并不總是與算法的參數(shù)相關(guān)，但是算法的性能對(duì)噪聲和誤差較敏感，這也包括參數(shù)的隨機(jī)性特征.為此，我們使用卡爾曼濾波器以減少因PSO算法隨機(jī)性所造成的噪聲.卡爾曼濾波器使用一列觀(guān)察到包含噪聲的值，并對(duì)未知變量進(jìn)行統(tǒng)計(jì)上的最佳估計(jì).算法包括兩個(gè)階段：使用先前的測(cè)量值來(lái)預(yù)測(cè)參數(shù)值的當(dāng)前表現(xiàn)，以及其所包含的不確定值和噪聲；觀(guān)察到下一次的測(cè)量結(jié)果(通常包含噪聲)時(shí),則使用加權(quán)平均值更新估計(jì)值.卡爾曼濾波器能夠?qū)?shù)值的真實(shí)性能進(jìn)行可靠的評(píng)估.

e(vij)=f(svijk)-f(sk)

(1)

1.1 卡爾曼濾波器模型

卡爾曼濾波器已經(jīng)成功應(yīng)用于追蹤和數(shù)據(jù)預(yù)測(cè)問(wèn)題，并被作為對(duì)預(yù)期數(shù)據(jù)的估計(jì)器來(lái)使用[6].通過(guò)先預(yù)測(cè)再校正的方式來(lái)最小化估計(jì)誤差協(xié)方差.在時(shí)間t時(shí)刻的效果和前一刻t-1時(shí)的效果之間關(guān)系，用一個(gè)n×n的矩陣A來(lái)表示，假設(shè)在整個(gè)算法運(yùn)行過(guò)程中A是一個(gè)常量矩陣,可選擇輸入變量u用n×1的矩陣B來(lái)表示,最后用一個(gè)m×n的矩陣H來(lái)關(guān)聯(lián)參數(shù)的估計(jì)效果e和實(shí)際的參數(shù)效果e′.卡爾曼濾波器通過(guò)一個(gè)線(xiàn)性隨機(jī)差分方程來(lái)控制參數(shù)效果e的評(píng)估過(guò)程，其方程式為：

et=Aet-1+But+wt-1

(2)

在此，由于沒(méi)有控制輸入，因此B是零矩陣.式(2)可簡(jiǎn)化為：

et=Aet-1+wt-1

(3)

而實(shí)際的參數(shù)效果e′的定義為：

e′=Het+vt

(4)

其中隨機(jī)變量wt-1和vt分別代表算法運(yùn)行過(guò)程中和測(cè)量過(guò)程中的噪聲.假設(shè)噪聲呈正態(tài)分布且彼此獨(dú)立，即使噪聲不是正態(tài)分布，卡爾曼濾波器也會(huì)收斂于正確的估計(jì)值.

1.2 卡爾曼濾波器算法

卡爾曼濾波器的反饋控制回路有兩組不同的方程：用于預(yù)測(cè)的時(shí)間更新方程和用于校正的測(cè)試更新方程.時(shí)間更新方程如下：

(5)

(6)

其中P是誤差協(xié)方差，矩陣A的含義和式(2)相同，Q是運(yùn)行噪聲的誤差協(xié)方差矩陣.測(cè)量更新方程式為：

(7)

(8)

(9)

最后，由式(7)計(jì)算卡爾曼增益，R是測(cè)量值的誤差協(xié)方差；由式(8)依據(jù)前一時(shí)刻的測(cè)量值計(jì)算后一時(shí)刻的測(cè)量值；由式(9)估計(jì)后驗(yàn)方差矩陣Pt，當(dāng)前一次的后驗(yàn)方差矩陣Pt被用于預(yù)測(cè)下一個(gè)新的Pt，則重復(fù)執(zhí)行這個(gè)過(guò)程.

2 基于適應(yīng)性PSO算法的測(cè)試數(shù)據(jù)生成方法

利用PSO算法生成路徑覆蓋測(cè)試數(shù)據(jù)，其基本思想是:將測(cè)試數(shù)據(jù)生成問(wèn)題轉(zhuǎn)化為函數(shù)優(yōu)化問(wèn)題.首先對(duì)測(cè)試數(shù)據(jù)進(jìn)行編碼形成粒子，隨機(jī)產(chǎn)生大量粒子作為初始種群，之后以粒子解碼后產(chǎn)生的測(cè)試數(shù)據(jù)作為輸入執(zhí)行被插樁的程序，根據(jù)返回的覆蓋信息計(jì)算粒子的適應(yīng)值，根據(jù)適應(yīng)值對(duì)粒子的運(yùn)動(dòng)軌跡進(jìn)行調(diào)整.重復(fù)該過(guò)程直到滿(mǎn)足結(jié)束條件,最后對(duì)粒子進(jìn)行解碼而產(chǎn)生的測(cè)試數(shù)據(jù)可能覆蓋測(cè)試目標(biāo).由此建立測(cè)試數(shù)據(jù)的生成框架如圖1所示.

2.1 測(cè)試框架的構(gòu)成

測(cè)試框架由3部分構(gòu)成：1)測(cè)試環(huán)境構(gòu)造部分包括對(duì)被測(cè)程序進(jìn)行靜態(tài)分析、構(gòu)造適應(yīng)值函數(shù)、對(duì)程序進(jìn)行插樁、選擇測(cè)試目標(biāo)，這部分是整個(gè)框架的基礎(chǔ)；2)PSO算法執(zhí)行部分把輸入數(shù)據(jù)編碼表示為粒子的位置，同時(shí)對(duì)粒子的速度、個(gè)體最優(yōu)值pbest，種群的全局最優(yōu)值gbest進(jìn)行初始化，然后更新粒子的位置和速度，之后使用適應(yīng)值函數(shù)對(duì)粒子進(jìn)行評(píng)估，如果粒子優(yōu)于個(gè)體最優(yōu)值，則更新個(gè)體最優(yōu)值，如果粒子優(yōu)于全局最優(yōu)值，則更新全局最優(yōu)值，重復(fù)這個(gè)過(guò)程直到滿(mǎn)足算法的結(jié)束條件.這部分是整個(gè)框架的核心部分；3)被測(cè)程序運(yùn)行部分是對(duì)PSO算法中粒子的位置信息進(jìn)行解碼作為程序的輸入來(lái)執(zhí)行插樁后的被測(cè)程序，利用插樁信息來(lái)監(jiān)測(cè)程序的運(yùn)行，并計(jì)算對(duì)應(yīng)的適應(yīng)值.該部分是整個(gè)框架的重要部分，是PSO算法和測(cè)試數(shù)據(jù)生成問(wèn)題之間的橋梁.

圖1 基于適應(yīng)性PSO算法的測(cè)試數(shù)據(jù)生成框架

2.2 基于卡爾曼濾波器的適應(yīng)性PSO算法

基于卡爾曼濾波器的適應(yīng)性PSO算法的實(shí)現(xiàn)過(guò)程如算法1所示.首先，隨機(jī)生成N個(gè)粒子，形成初始化種群，評(píng)估這些粒子的適應(yīng)值，然后利用初始的粒子群參數(shù)進(jìn)化更新粒子的位置，接著使用卡爾曼濾波器估計(jì)參數(shù)值的效果，利用效果值比例選擇策略為下一次迭代選擇適當(dāng)?shù)膮?shù)值，最后用新的參數(shù)來(lái)進(jìn)化種群，重復(fù)這個(gè)過(guò)程直到滿(mǎn)足算法停止條件.

算法1 基于卡爾曼濾波器的適應(yīng)性PSO算法

1 procedure KFPSO

2 輸入：適應(yīng)值函數(shù)(f),種群數(shù)量(N)，算法停止條件(SC)，慣性權(quán)重(ω)，學(xué)習(xí)因子(c1,c2)

3 輸出：最優(yōu)解集合(St)

4S0←GenerateRandomSolution(N) //隨機(jī)生成粒子，構(gòu)成初始粒子群

5t=0

6 while !SCdo

7 Evaluate(f,St) //對(duì)當(dāng)前種群進(jìn)行評(píng)估

8 positiont+1=evolve(positiontω,c1,c2) //進(jìn)化更新種群

9 AdaptiveParameterControl(ω,c1,c2,t) //適應(yīng)性參數(shù)控制

10t=t+1

11 end while

12 returnSt

13 end procedure

14 procedure AdaptiveParameterControl

15 輸入:在t代調(diào)整的參數(shù)的集合(v1,…，vn)

16 for all parametervi,i∈ndo

17 for all parameter valuevij,i∈ndo

18et(vij)=KalmanFilter(vij,t) //卡爾曼濾波器算法

19 end for

20vij=ParameterValueSelection(et(vi1),…,et(vim)) //參數(shù)選擇

21 end for

22 end procedure

23 procedure KALMANFILTER(vij,t)

24 輸入: 參數(shù)值(vij)，進(jìn)化代數(shù)(t)

32 end procedure

2.3 參數(shù)選擇算法

由于參數(shù)在算法進(jìn)化過(guò)程中需要進(jìn)行動(dòng)態(tài)調(diào)整，因此需要在參數(shù)的取值范圍內(nèi)對(duì)參數(shù)進(jìn)行選擇.算法2描述了一種按照參數(shù)效果值所占比例進(jìn)行參數(shù)選擇的策略.算法利用參數(shù)vij的每個(gè)值的選擇概率來(lái)計(jì)算參數(shù)vij在下一次迭代中的具體值.首先對(duì)每個(gè)值的選擇概率進(jìn)行求和，記錄每個(gè)參數(shù)對(duì)應(yīng)的和，然后隨機(jī)生成一個(gè)隨機(jī)數(shù)，判斷該隨機(jī)數(shù)落在哪個(gè)參數(shù)值對(duì)應(yīng)的和區(qū)間中，則該參數(shù)值被選中.如果一個(gè)參數(shù)的選擇概率較大，則其被選中的概率也較大.利用這種策略的優(yōu)點(diǎn)是一些選擇概率低的參數(shù)也有機(jī)會(huì)保留下來(lái)，這些參數(shù)可能會(huì)在后續(xù)的進(jìn)化中發(fā)揮作用.

算法2 參數(shù)值選擇

輸入：每個(gè)參數(shù)值的選擇概率(p(vij),…,p(vm))

輸出：在下一次進(jìn)化中需要使用的參數(shù)值(vij)

1 sum=0;

2 forj→1:mdo

3sum=sum+p(vij)

4 cumulativeSumij=sum

5 end for

6r=RANDOM([0,sum])

7 forj→1:mdo

8 ifr

9 returnvij

10 end if

11 end for

在使用PSO算法生成測(cè)試用例的過(guò)程中，利用算法1和算法2對(duì)參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整，算法執(zhí)行中使用卡爾曼濾波器來(lái)減少算法本身的隨機(jī)性對(duì)參數(shù)效果的影響，這樣有利于提高PSO算法生成測(cè)試用例的效率.

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

為了評(píng)估本文方法的有效性，選擇了8個(gè)程序進(jìn)行實(shí)驗(yàn)，如表1所示.這些程序都是在相關(guān)文獻(xiàn)[7-9]中已使用或者開(kāi)源的程序.將本文方法應(yīng)用于8個(gè)被測(cè)程序，并將所提方法與其他兩種方法作比較，以進(jìn)一步驗(yàn)證本文方法的有效性.運(yùn)行環(huán)境：硬件環(huán)境(CPU：Intel Core P7350 3.2GHZ，內(nèi)存：2GB)；軟件環(huán)境(Windows 7，DEV-C++ 5.11).所有程序均用C語(yǔ)言編寫(xiě).

表1 被測(cè)程序列表

3.1 參數(shù)設(shè)置

為了證明本文方法的有效性，以基本的PSO算法和RAPSO算法[4]作為比較對(duì)象，對(duì)本文方法的適應(yīng)性PSO算法的性能進(jìn)行評(píng)估.

基本PSO算法：所有參數(shù)根據(jù)經(jīng)驗(yàn)被預(yù)先設(shè)置，在進(jìn)化過(guò)程這些參數(shù)不會(huì)改變.參數(shù)設(shè)置如下：粒子群規(guī)模為50；最大生成代數(shù)為200；最大速度為20；學(xué)習(xí)因子c1,c2均為2；慣性權(quán)值ω為0.7.

RAPSO算法：去除了基本粒子群算法中速度分量，使得進(jìn)化過(guò)程不受“最大速度”參數(shù)的影響，同時(shí)根據(jù)粒子的聚集度來(lái)動(dòng)態(tài)調(diào)整慣性權(quán)值ω，當(dāng)粒子比較稀疏的時(shí)候ω比較大，當(dāng)粒子比較密集的時(shí)候ω比較小.本文中，設(shè)置其慣性權(quán)值最大值為0.9，最小值為0.4，其余設(shè)置與基本PSO算法相同.

本文算法(KFPSO算法)對(duì)PSO算法的慣性權(quán)值ω和學(xué)習(xí)因子c1,c2進(jìn)行動(dòng)態(tài)調(diào)整，因此其值在進(jìn)化過(guò)程中不斷改變，設(shè)置ω從[0.4, 0.5],[0.5, 0.6],[0.6, 0.7],[0.7, 0.8],[0.8, 0.9]這5個(gè)區(qū)間中抽樣產(chǎn)生；c1,c2從[1.9, 1.95],[1.95, 2.0],[2.0, 2.05],[2.05 2.1]這4個(gè)區(qū)間中抽樣產(chǎn)生；其余參數(shù)與基本PSO算法相同.

實(shí)驗(yàn)在相同的初始種群下進(jìn)行，所有算法各運(yùn)行100次，比較各種算法需要的評(píng)估次數(shù)和運(yùn)行時(shí)間等指標(biāo).其中，評(píng)估次數(shù)是100次運(yùn)行的平均值，運(yùn)行時(shí)間為100次運(yùn)行的總時(shí)間.

3.2 實(shí)驗(yàn)結(jié)果

PSO算法、RAPSO算法和本文算法(KFPSO算法)運(yùn)行不同被測(cè)程序需要的評(píng)估次數(shù)和運(yùn)行時(shí)間如表2所示.

表2 PSO算法、RAPSO算法和本文算法(KFPSO算法)的測(cè)試情況比較

從表2中可以看出，本文算法所需的評(píng)估次數(shù)和運(yùn)行時(shí)間都明顯低于RAPSO算法和PSO算法.以Barcode程序?yàn)槔瑢?duì)于評(píng)估次數(shù)指標(biāo)，本文算法需要919次評(píng)估，其余兩種算法分別需要2 183次和5 834次，分別是本文算法的2.37和6.34倍.運(yùn)行時(shí)間指標(biāo)，本文算法需要0.387 s，其余兩種算法分別需要0.962 s和3.458 s，分別是本文算法的2.49和8.70倍.實(shí)驗(yàn)表明，RAPSO算法的性能優(yōu)于PSO算法，其所需的評(píng)估次數(shù)和運(yùn)行時(shí)間更少，這與文獻(xiàn)[4]的研究結(jié)果一致.以Bessj程序?yàn)槔?，RAPSO算法需要的評(píng)估次數(shù)和運(yùn)行時(shí)間分別為3 287次和1.684 s，PSO算法分別為6 872次和4.782 s，前者為后者的47.83%和35.16%.實(shí)驗(yàn)結(jié)果表明，本文提出的適應(yīng)性PSO算法在生成測(cè)試數(shù)據(jù)方面具有更高的效率.

4 結(jié)論

參數(shù)的設(shè)置對(duì)PSO算法的性能有重要的影響.目前的參數(shù)設(shè)置主要依靠測(cè)試人員的經(jīng)驗(yàn)，當(dāng)面對(duì)不同規(guī)模、不同結(jié)構(gòu)的被測(cè)程序時(shí)，原有的參數(shù)往往不能完全發(fā)揮出PSO算法的性能.此外,由于PSO算法本身具有的隨機(jī)特性，使得算法性能對(duì)噪聲的影響較敏感.本文提出的適應(yīng)性參數(shù)設(shè)置方法可以在進(jìn)化過(guò)程中，利用卡爾曼濾波器對(duì)當(dāng)前參數(shù)的效果值進(jìn)行隨機(jī)性估計(jì)，依據(jù)效果值對(duì)下次迭代使用的參數(shù)進(jìn)行調(diào)整，從而提高PSO算法的效率.實(shí)驗(yàn)證明了該方法比基本PSO算法和相關(guān)文獻(xiàn)算法性能更優(yōu).