改進的粒子群算法求解函數極值研究

錢澤鉅

（西藏民族大學 陜西 咸陽 712082）

0 引言

在求解函數極值的問題中，當函數比較簡單時，可以通過直接求解求得極值。但是，大部分函數是無法通過直接求解求得極值。這時就需要用到智能算法，在一個解空間中尋找最優極值解。

傳統的智能算法包括遺傳算法、粒子群、魚群算法等。其中，粒子群算法有簡單易行、收斂速度快、設置參數少等優點。所以，本文采用粒子群算法來解決函數求極值的問題。

1 標準粒子群算法

粒子群算法的思想來源于對鳥類捕食行為的研究，模擬大的鳥群落通過協同合作的捕食行為。行為基礎就是共享自身與種群信息，根據此基礎來判斷食物所在。

1.1 粒子群算法簡介

鳥群中有很多只鳥，而每一只鳥都是一個問題，稱為“粒子”。每個粒子在一個空間內進行搜索。其所在位置的好壞是由適應度函數決定的，也就是fitnessfunction。而且，每個粒子需要有記憶性和速度以決定飛行的位置與方向。這就需要粒子根據自身的經驗與群體的經驗來決定[1-2]。

1.2 粒子群算法的實現步驟

（1）初始化種群。初始化，包括要達到的群體規模N。每一只鳥，也就是每一個粒子隨機初始化位置向量Xi，隨機初始化速度向量Vi。

其中Xi=（xi1，xi2，…，xiD），Vi=（vi1，vi2，…，viD）。

（2）將初始生成的隨機位置向量中每一個xi代入所要求極值的函數f（xi），所求的函數極值就是適應度值Fitness（i）。

（3）計算初始化的粒子的適應度值，將最開始計算的每個初始化粒子的適應度值儲存為個體極值Pbest，將所有初始化粒子的個體極值Pbest進行比較，選擇最優的作為當前全局最優，存入全局極值Gbest。

（4）算法開始迭代，每迭代一次，對于每一個粒子，用其適應度值Fitness（i）和與上一次迭代的個體極值Pbest作對比，如果Fitness（i）優于個體極值Pbest，就用適應度值Fitness（i）替代個體極值Pbest。如果Fitness（i）并不優于個體極值Pbest，則保留個體極值Pbest[3-4]。

（5）對于每一個粒子，用其適應度值Fitness（i）與上一次迭代的全局極值Gbest作對比，如果Fitness（i）優于全局極值Gbest，就用Fitness（i）替代全局極值Gbest。如果Fitness（i）并不優于全局極值Gbest，則保留全局極值Gbest。

（6）更新粒子的位置Xi與速度Vi

其中，ω為慣性因子，較大的ω擁有較強的全局搜索能力，較小的ω擁有較強的局部搜索能力。c1與c2為學習因子，也稱為加速常數，其中c1是個體部分，如果c1過小，則容易陷入局部最優。c2集體部分，如果c2過小，會導致算法收斂速度變慢。r1，r2為[0,1]范圍內的均勻隨機數。為上一次迭代的粒子位置，為上一次迭代的粒子速度。為本次迭代的粒子位置，為本次迭代的粒子速度。

（7）如果滿足最大循環次數的條件，則停止循環，如果不滿足，則返回步驟（4）。

算法框如圖1所示：

圖1 傳統粒子群算法流程

2 改進粒子群算法解決函數求極值問題

2.1 算法的改進

將算法進行分層，分為兩層，第一層負責算法前期，并且混合遺傳算法，用來擴大搜索范圍；第二層負責算法后期，主要用作精準搜索，加速收斂。這樣做，就可以將一個矛盾復雜的要求，分解成兩個小的部分，各司其職，來完成算法的搜索[5]。混合粒子群算法，就是將其他優化算法的一些技術應用到粒子群算法之中，用于提升粒子的多樣性，使其可以跳出局部最優，增強全局尋優的能力，本文采用遺傳算法中的雜交概念，混合入粒子群算法。針對傳統的固定慣性因子ω，無法兼顧算法前期與后期不同的要求，改為線性遞減的慣性因子ω。其公式為：

其中，wmax為慣性因子的最大值，wmin為慣性因子的最小值，t為迭代次數，tmax為最大迭代次數。

2.2 基于雜交的粒子群算法

該算法是借鑒了遺傳算法中的雜交概念[6]，在每次的迭代之中，根據雜交的概率[7-8]，首先選擇一定量的粒子作為父代粒子放入到雜交池子中，讓池子中的粒子進行雜交操作，產生與父代粒子個數相同的子代粒子，并用產生的子代粒子替換父代粒子。

分層混合粒子群算法的實現步驟：

（1）在規定的范圍之內，隨機設置初始化粒子的位置與速度。

（2）計算初始化的粒子的適應度值，將最開始計算的每個初始化粒子的適應度值儲存為個體極值Pbest，將所有初始化粒子的個體極值Pbest進行比較，選擇最優的作為當前全局最優，存入全局極值Gbest。

（3）設置參數T，T小于最大循環次數。當算法循環次數小于T時，進入步驟（4），當算法循環次數大于T時，進入步驟（5）。

（4）對每個粒子的速度與位置進行更新。進入步驟（6）。

（5）對每個粒子的速度與位置進行更新。進入步驟（6）。

（6）計算每一個更新后的粒子的適應度值，將適應度值與粒子最好位置比較。更新全局極值Gbest。

（7）根據一定的雜交概率選取指定數量的粒子，并將選取的指定數量的粒子放入雜交池。將兩個父代個體的部分進行替換重組構成新的個體，并用子代粒子替代父代粒子，子代的位置與速度為：

其中，保持Pbest和Gbest不變。mx（1），mx（2）為兩個不同的父代粒子，nx為交叉操作后的子代粒子的位置，nv為交叉操作后的子代粒子速度，i是0到1之間的隨機數。

（8）當如果滿足結束條件（循環次數滿足最大循環要求），則停止循環，如果不滿足，則返回步驟（3）。

3 算法仿真測試

3.1 測試函數介紹

為了驗證所提出算法是否有效，選取兩個類型不同的函數，作為測試函數進行測試驗證。

其中，Y1是一個多維函數，Y2是一個復雜的多模函數。通過傳統的PSO算法與改進的PSO算法對兩個不同類型函數的對比，來驗證算法是否有效。

3.2 算法仿真

對出傳統的PSO算法，初試種群選擇為50，c1與c2學習因子設置為2，ω慣性權重設置為0.8。改進PSO算法，Y1中設置T為10，Y2中設置T為100，除了w慣性權重設置不同外，其余設置與傳統PSO算法設置相同，其中，慣性權重w設置為區間[0.6,0.8]。在測試函數時，式（1）取最大迭代次數為100，式（2）取最大迭代次數為1 000，對兩個函數各優化10次。算法是否可以快速穩定的收斂，是否可以跳出局部最優得到全局最優，可以衡量一個算法是否優秀。越快收斂，且能跳出局部最優，說明快速有效的求解函數極值。通過對比收斂結果與收斂速度，來展示改進算法的有效性，結論如表1和圖2所示：

圖2 測試函數適應度值變化

表1 測試函數優化結果

通過以表1、圖2可以看出，改進PSO算法對比傳統PSO算法在收斂速度與收斂結果這兩個方面，新算法收斂速度更快。在收斂結果上，新算法也擁有更好的穩定收斂結果。

3.3 仿真結果

從上圖可以看出，改進的粒子群算法與傳統粒子群算法相比，有比較明顯的優勢。對于測試函數Y1改進的算法收斂速度更快，基本在10步左右就可以收斂，收斂速度快，說明算法求解函數極值的速度快。即便算法前期陷入局部最優解，也可以很快地跳出局部最優。而傳統算法側需要35次左右才能收斂，對比改進的算法，收斂速度慢一些，說明算法求解函數極值慢一些，而且，陷入局部最優解時，跳出局部最優比較慢。而收斂結果，改進算法可以穩定收斂到0.3。但傳統算法卻無法穩定收斂，在0.3附近波動。對于測試函數Y2，改進算法在100步左右就可以收斂，收斂速度快，且穩定收斂。而傳統算法則需要250步左右才能收斂，收斂速度不如改進算法，收斂緩慢，且陷入局部最優。

4 結語

本文提出的改進粒子群算法，是先通過對算法進行分層，再局部融合其他智能算法，同時采取自適應權重的方法實現的。在算法前期，擴大搜索范圍，避免陷入局部最優；在算法后期，加速算法的收斂，并用于解決函數求極值的問題。實驗結果表明，改進的粒子群算法整體性能良好，可用于求解其他函數求極值的問題。