一種新改進的粒子群優化算法

時貴英，吳雅娟，倪紅梅

(東北石油大學 計算機與信息技術學院，大慶 163318)

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

1 基本粒子群算法

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

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

2 改進的PSO算法

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

這里q0是一個給定的參數入局部最優的可能性。

2.1 適應值函數的構造

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

2.2 改進的PSO算法的實現描述

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

步驟2：粒子達到迭代次數或滿足精度要求后退出迭代，轉步驟6；

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

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

步驟5：迭代次數加1，然后轉步驟2；

步驟6：輸出每個粒子當前的局部最優解。

3 仿真實驗

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

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

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

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

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

4 結束語

本文提出一種改進的粒子群算法，算法融合蟻群算法和粒子群算法的優缺點，在搜索算法早期用粒子群算法生成初步測試結果，然后引入蟻群算法的信息素機制來加強粒子的區域搜索能力，克服了使用單一粒子群算法容易陷入局部最優的問題。實驗結果表明改進后粒子群算法實現簡單方便，用于測試用例自動生成，效果好于單獨的粒子群算法。

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

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

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

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

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

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

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

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