王 曄，呂學偉

(淮陰師范學院 計算機科學與技術學院，江蘇 淮安 223300)

0 引言

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

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

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

1 卡爾曼濾波器

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

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

(1)

1.1 卡爾曼濾波器模型

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

et=Aet-1+But+wt-1

(2)

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

et=Aet-1+wt-1

(3)

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

e′=Het+vt

(4)

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

1.2 卡爾曼濾波器算法

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

(5)

(6)

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

(7)

(8)

(9)

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

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

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

2.1 測試框架的構成

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

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

2.2 基于卡爾曼濾波器的適應性PSO算法

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

算法1 基于卡爾曼濾波器的適應性PSO算法

1 procedure KFPSO

2 輸入：適應值函數(shù)(f),種群數(shù)量(N)，算法停止條件(SC)，慣性權重(ω)，學習因子(c1,c2)

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

4S0←GenerateRandomSolution(N) //隨機生成粒子，構成初始粒子群

5t=0

6 while !SCdo

7 Evaluate(f,St) //對當前種群進行評估

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

9 AdaptiveParameterControl(ω,c1,c2,t) //適應性參數(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)，進化代數(shù)(t)

32 end procedure

2.3 參數(shù)選擇算法

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

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

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

輸出：在下一次進化中需要使用的參數(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算法生成測試用例的過程中，利用算法1和算法2對參數(shù)進行動態(tài)調(diào)整，算法執(zhí)行中使用卡爾曼濾波器來減少算法本身的隨機性對參數(shù)效果的影響，這樣有利于提高PSO算法生成測試用例的效率.

3 實驗與分析

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

表1 被測程序列表

3.1 參數(shù)設置

為了證明本文方法的有效性，以基本的PSO算法和RAPSO算法[4]作為比較對象，對本文方法的適應性PSO算法的性能進行評估.

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

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

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

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

3.2 實驗結果

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

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

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

4 結論

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