時貴英，吳雅娟，倪紅梅

(東北石油大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，大慶 163318)

粒子群優(yōu)化(Particle SwarmOptimization，簡稱PSO)算法是1995年berhart博士和kennedy博士提出的一種新的進(jìn)化算法[1]。這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實際問題中顯示了其優(yōu)越性。但是任何方法都有其缺陷或不足，比如遺傳算法[2-4]雖然具有良好的全局搜索能力，但是實現(xiàn)復(fù)雜，且局部搜索能力差容易發(fā)生早熟現(xiàn)象；同遺傳算法比較，粒子群算法[5]容易實現(xiàn)并且沒有太多參數(shù)需要調(diào)整，但是在算法后期局部搜索能力較差，反饋信息利用不充分，容易陷入局部最優(yōu)，導(dǎo)致算法出現(xiàn)停滯，破壞了粒子間的多樣性，導(dǎo)致算法不再繼續(xù)搜索解空間，從而發(fā)生早熟；蟻群算法[6]具有正反饋性、并行性、強(qiáng)收斂性以及魯棒性，但是由于搜索初期信息素相對匱乏，導(dǎo)致算法的搜索效率降低，容易產(chǎn)生停滯早熟現(xiàn)象。一種有效的方法是將粒子群算法和蟻群算法有機(jī)地結(jié)合起來，在傳統(tǒng)的粒子群優(yōu)化算法基礎(chǔ)上引入蟻群思想，運(yùn)用類似于蟻群算法中信息素的選擇機(jī)制，在每個粒子的當(dāng)前最好位置附近通過局部搜索產(chǎn)生若干個位置，它利用粒子群算法的較強(qiáng)的全局搜索能力生成信息素分布，再利用蟻群算法的正反饋機(jī)制求問題的精確解。該算法實現(xiàn)簡單，且有效地避免了蟻群算法和粒子群算法的缺陷，達(dá)到了優(yōu)勢互補(bǔ)的效果。

1 基本粒子群算法

基本粒子群算法和遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解。粒子群的每個粒子代表問題的一個可能解，每個粒子具有位置和速度兩個特征，并通過適應(yīng)度來衡量粒子的優(yōu)劣。算法首先初始化n個隨機(jī)粒子，在m維空間中，記第i個粒子的當(dāng)前位置為，當(dāng)前速度為 =1，2，…， ，然后每個粒子在搜索時需要考慮兩個因素：一個是粒子本身所找到的歷史最優(yōu)解，即個體極值；另一個是全部粒子群目前找到的最優(yōu)解，即全局極值 pg=，并通過這兩個極值根據(jù)下面的兩個公式(1)和(2)來更新自己的速度和位置。

其中 i∈(1，2，…，n)，j∈(1，2，…，m)，表示迭代次數(shù)， 是保持原來速度的系數(shù)，即慣性權(quán)重，一般在0.1至0.9之間取值，慣性權(quán)重的大小決定了對粒子當(dāng)前速度繼承的多少，研究發(fā)現(xiàn)在算法的迭代過程中動態(tài)的減少慣性權(quán)重，可以使算法才更加穩(wěn)定，效果比較好；c1和c2被稱作學(xué)習(xí)因子，通常c1=c2=2，c1是調(diào)節(jié)粒子飛向自身最好位置方向的步長，c2是調(diào)節(jié)粒子飛向全局最好位置方向的步長；r1和 r2是在[0，1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)；r是對位置更新的時候，在速度前面加的一個系數(shù)，這個系數(shù)叫做約束因子，通常設(shè)置為1。

2 改進(jìn)的PSO算法

在粒子群算法中由于單個粒子僅僅保留其搜索過程中遇到的最優(yōu)解pi的信息，在整個進(jìn)化過程中如果粒子群的全局最優(yōu)解pg與局部最優(yōu)解pi接近，粒子將可能陷入局部最優(yōu)，無法繼續(xù)在解空間內(nèi)進(jìn)行進(jìn)一步搜索。而蟻群算法是依據(jù)螞蟻路線上的信息素濃度進(jìn)行分析，按照一定概率選擇信息素濃度較高的一條作為前進(jìn)方向，從而達(dá)到求取優(yōu)化解的目的。受蟻群算法啟發(fā)，在粒子群算法中引入信息素機(jī)制[8]，在每個粒子當(dāng)前局部最優(yōu)解的鄰域內(nèi)進(jìn)行局部搜索產(chǎn)生k個點(diǎn)，連同當(dāng)前局部最優(yōu)解在內(nèi)，生成一個包含k+1個點(diǎn)的新序列pp，然后根據(jù)概率公式在該序列中選擇相應(yīng)的點(diǎn)，作為新的粒子。本文構(gòu)造的新序列pp中第個點(diǎn)被選中的概率為：，函數(shù) fitness(j)為點(diǎn)j的適應(yīng)度。由選擇概率可知，在pp序列中適應(yīng)度較高的點(diǎn)被選中的可能性較大。通過鄰域搜索機(jī)制使粒子群進(jìn)化方向有了多種選擇，加大了粒子間的多樣性差異，從而降低了粒子群算法陷

這里q0是一個給定的參數(shù)入局部最優(yōu)的可能性。

2.1 適應(yīng)值函數(shù)的構(gòu)造

如何定義適應(yīng)值函數(shù)，是優(yōu)化算法解決問題的關(guān)鍵。因為適應(yīng)值函數(shù)的優(yōu)劣將直接影響到算法解決問題的效率。本文采用“分支函數(shù)疊加法[3]”構(gòu)造適應(yīng)值函數(shù)，分支函數(shù)是一個實值函數(shù)，它是分支謂詞到實值的一個映射，可以量化地描述在測試數(shù)據(jù)的驅(qū)動下，被測單元的實際執(zhí)行路徑對選定路徑的覆蓋程度。設(shè)選定路徑上有個分支點(diǎn)，個參數(shù)，則每個分支點(diǎn)前需插入相應(yīng)的分支函數(shù)可定義為：，；則該路徑的的適應(yīng)度函數(shù)，其中：

2.2 改進(jìn)的PSO算法的實現(xiàn)描述

步驟1：在算法的初期用粒子群算法，初始化粒子群并計算粒子適應(yīng)度，初始化粒子的個體最優(yōu)值和全局最優(yōu)值，使達(dá)到精度要求的粒子退出迭代；

步驟2：粒子達(dá)到迭代次數(shù)或滿足精度要求后退出迭代，轉(zhuǎn)步驟6；

步驟3：根據(jù)公式(1)和(2)更新剩余粒子的速度和位置，重新計算粒子適應(yīng)度，更新粒子的個體最優(yōu)值和全局最優(yōu)值，同樣達(dá)到精度要求的粒子也要退出迭代，轉(zhuǎn)步驟6；

步驟4：在最后剩余粒子的當(dāng)前局部最優(yōu)解 pi的鄰域內(nèi)進(jìn)行局部搜索產(chǎn)生k個點(diǎn)，然后根據(jù)概率公式(3)在該序列中選擇相應(yīng)的點(diǎn)，作為新的粒子，并重新計算粒子適應(yīng)度，更新粒子的個體最優(yōu)值和全局最優(yōu)值；

步驟5：迭代次數(shù)加1，然后轉(zhuǎn)步驟2；

步驟6：輸出每個粒子當(dāng)前的局部最優(yōu)解。

3 仿真實驗

三角形分類問題包含了清晰而又復(fù)雜的邏輯，下面以三角形分類程序為例，來驗證本文算法在求解面向路徑的測試數(shù)據(jù)問題的性能。三角形分類問題描述為：輸入3個整數(shù)A、B和C，作為三角形的邊，根據(jù)邊的關(guān)系輸出三角形類型。例如以1到10的整數(shù)作為輸入，在1000組可能的組合中，只有10組能滿足判定為等邊三角形的分支。在本文算法的實現(xiàn)過程中，采用整數(shù)編碼方式，隨機(jī)產(chǎn)生1到100之間的整數(shù)，生成初始種群，設(shè)置種群初始規(guī)模為100，取粒子群算法的參數(shù)隨迭代次數(shù)由0.7線性地減小到0.4，最大迭代次數(shù)是20，取k=10。使用本文算法生成的路徑測試數(shù)據(jù)實驗結(jié)果如圖1所示。

圖1 本文算法的實驗結(jié)果Fig.1 The experiment result of the improved PSO algorithm

為了驗證本文算法的有效性，本文同時使用在相同條件下沒有引入信息素機(jī)制的粒子群算法(暫時稱作基本的粒子群算法)來生成測試數(shù)據(jù)，以便于與使用本文算法生成的數(shù)據(jù)進(jìn)行對比。為了更好地進(jìn)行比較，系統(tǒng)將使用本文算法生成的初始粒子群數(shù)據(jù)保留在外部文件中，作為沒有改進(jìn)的粒子群算法的初始種群，生成的三角形路徑測試實驗結(jié)果如圖2所示。

圖2 基本粒子群算法的實驗結(jié)果Fig.2 The experiment result of PSO algorithm

根據(jù)以上兩組數(shù)據(jù)的對比，可以很清楚地看到，在改進(jìn)粒子群算法中由于引入了信息素的調(diào)解作用，從而有效地保證了個體的多樣性，不至于在很短的時間內(nèi)使適應(yīng)度高的少數(shù)個體占據(jù)群體總數(shù)的大部分，更好地避免了早熟和局部最優(yōu)等不足，使得路徑覆蓋更全面，更合理，測試數(shù)據(jù)生成更可靠，更具有實用價值。

4 結(jié)束語

本文提出一種改進(jìn)的粒子群算法，算法融合蟻群算法和粒子群算法的優(yōu)缺點(diǎn)，在搜索算法早期用粒子群算法生成初步測試結(jié)果，然后引入蟻群算法的信息素機(jī)制來加強(qiáng)粒子的區(qū)域搜索能力，克服了使用單一粒子群算法容易陷入局部最優(yōu)的問題。實驗結(jié)果表明改進(jìn)后粒子群算法實現(xiàn)簡單方便，用于測試用例自動生成，效果好于單獨(dú)的粒子群算法。

[1]Kennedy J，Eberhert R.Particle swarm optimization[J].IEEE International Conferenceon Neural Networks，1995：1942-1948.

[2]夏蕓，劉鋒.基于免疫遺傳算法的軟件測試數(shù)據(jù)自動生成[J].計算機(jī)應(yīng)用，2008，8(3)：723-725.

[3]汪浩，謝軍凱，高仲儀.遺傳算法及其在軟件測試數(shù)據(jù)生成中的應(yīng)用研究[J].計算機(jī)工程與應(yīng)用，2001，37(12)：64-68．

[4]許秀梅.基于退火免疫遺傳算法的測試數(shù)據(jù)生成方法研究[D].北京：北京交通大學(xué)，2007.

[5]尉小環(huán)，高慧敏，李峰.微粒群算法在軟件測試數(shù)據(jù)生成中的應(yīng)用[J].太原科技大學(xué)學(xué)報，2009.8，30(4)：294-296.

[6]傅博.基于蟻群算法的軟件測試數(shù)據(jù)自動生成[J].計算機(jī)工程與應(yīng)用，2007，43(12)：97-99.

[7]段玉紅，高岳林.基于蟻群信息機(jī)制的粒子群算法[J].計算機(jī)工程與應(yīng)用，2008，44(31)：81-83.

[8]史海軍，王志剛，郭廣寒.引入變異算子的粒子群優(yōu)化算法[J].長春理工大學(xué)學(xué)報：自然科學(xué)版，2007，30(3)：81-83.