改進(jìn)的粒子群算法求解函數(shù)極值研究

錢澤鉅

（西藏民族大學(xué) 陜西 咸陽(yáng) 712082）

0 引言

在求解函數(shù)極值的問題中，當(dāng)函數(shù)比較簡(jiǎn)單時(shí)，可以通過直接求解求得極值。但是，大部分函數(shù)是無(wú)法通過直接求解求得極值。這時(shí)就需要用到智能算法，在一個(gè)解空間中尋找最優(yōu)極值解。

傳統(tǒng)的智能算法包括遺傳算法、粒子群、魚群算法等。其中，粒子群算法有簡(jiǎn)單易行、收斂速度快、設(shè)置參數(shù)少等優(yōu)點(diǎn)。所以，本文采用粒子群算法來解決函數(shù)求極值的問題。

1 標(biāo)準(zhǔn)粒子群算法

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

1.1 粒子群算法簡(jiǎn)介

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

1.2 粒子群算法的實(shí)現(xiàn)步驟

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

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

（2）將初始生成的隨機(jī)位置向量中每一個(gè)xi代入所要求極值的函數(shù)f（xi），所求的函數(shù)極值就是適應(yīng)度值Fitness（i）。

（3）計(jì)算初始化的粒子的適應(yīng)度值，將最開始計(jì)算的每個(gè)初始化粒子的適應(yīng)度值儲(chǔ)存為個(gè)體極值Pbest，將所有初始化粒子的個(gè)體極值Pbest進(jìn)行比較，選擇最優(yōu)的作為當(dāng)前全局最優(yōu)，存入全局極值Gbest。

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

（5）對(duì)于每一個(gè)粒子，用其適應(yīng)度值Fitness（i）與上一次迭代的全局極值Gbest作對(duì)比，如果Fitness（i）優(yōu)于全局極值Gbest，就用Fitness（i）替代全局極值Gbest。如果Fitness（i）并不優(yōu)于全局極值Gbest，則保留全局極值Gbest。

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

其中，ω為慣性因子，較大的ω?fù)碛休^強(qiáng)的全局搜索能力，較小的ω?fù)碛休^強(qiáng)的局部搜索能力。c1與c2為學(xué)習(xí)因子，也稱為加速常數(shù)，其中c1是個(gè)體部分，如果c1過小，則容易陷入局部最優(yōu)。c2集體部分，如果c2過小，會(huì)導(dǎo)致算法收斂速度變慢。r1，r2為[0,1]范圍內(nèi)的均勻隨機(jī)數(shù)。為上一次迭代的粒子位置，為上一次迭代的粒子速度。為本次迭代的粒子位置，為本次迭代的粒子速度。

（7）如果滿足最大循環(huán)次數(shù)的條件，則停止循環(huán)，如果不滿足，則返回步驟（4）。

算法框如圖1所示：

圖1 傳統(tǒng)粒子群算法流程

2 改進(jìn)粒子群算法解決函數(shù)求極值問題

2.1 算法的改進(jìn)

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

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

2.2 基于雜交的粒子群算法

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

分層混合粒子群算法的實(shí)現(xiàn)步驟：

（1）在規(guī)定的范圍之內(nèi)，隨機(jī)設(shè)置初始化粒子的位置與速度。

（2）計(jì)算初始化的粒子的適應(yīng)度值，將最開始計(jì)算的每個(gè)初始化粒子的適應(yīng)度值儲(chǔ)存為個(gè)體極值Pbest，將所有初始化粒子的個(gè)體極值Pbest進(jìn)行比較，選擇最優(yōu)的作為當(dāng)前全局最優(yōu)，存入全局極值Gbest。

（3）設(shè)置參數(shù)T，T小于最大循環(huán)次數(shù)。當(dāng)算法循環(huán)次數(shù)小于T時(shí)，進(jìn)入步驟（4），當(dāng)算法循環(huán)次數(shù)大于T時(shí)，進(jìn)入步驟（5）。

（4）對(duì)每個(gè)粒子的速度與位置進(jìn)行更新。進(jìn)入步驟（6）。

（5）對(duì)每個(gè)粒子的速度與位置進(jìn)行更新。進(jìn)入步驟（6）。

（6）計(jì)算每一個(gè)更新后的粒子的適應(yīng)度值，將適應(yīng)度值與粒子最好位置比較。更新全局極值Gbest。

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

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

（8）當(dāng)如果滿足結(jié)束條件（循環(huán)次數(shù)滿足最大循環(huán)要求），則停止循環(huán)，如果不滿足，則返回步驟（3）。

3 算法仿真測(cè)試

3.1 測(cè)試函數(shù)介紹

為了驗(yàn)證所提出算法是否有效，選取兩個(gè)類型不同的函數(shù)，作為測(cè)試函數(shù)進(jìn)行測(cè)試驗(yàn)證。

其中，Y1是一個(gè)多維函數(shù)，Y2是一個(gè)復(fù)雜的多模函數(shù)。通過傳統(tǒng)的PSO算法與改進(jìn)的PSO算法對(duì)兩個(gè)不同類型函數(shù)的對(duì)比，來驗(yàn)證算法是否有效。

3.2 算法仿真

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

圖2 測(cè)試函數(shù)適應(yīng)度值變化

表1 測(cè)試函數(shù)優(yōu)化結(jié)果

通過以表1、圖2可以看出，改進(jìn)PSO算法對(duì)比傳統(tǒng)PSO算法在收斂速度與收斂結(jié)果這兩個(gè)方面，新算法收斂速度更快。在收斂結(jié)果上，新算法也擁有更好的穩(wěn)定收斂結(jié)果。

3.3 仿真結(jié)果

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

4 結(jié)語(yǔ)

本文提出的改進(jìn)粒子群算法，是先通過對(duì)算法進(jìn)行分層，再局部融合其他智能算法，同時(shí)采取自適應(yīng)權(quán)重的方法實(shí)現(xiàn)的。在算法前期，擴(kuò)大搜索范圍，避免陷入局部最優(yōu)；在算法后期，加速算法的收斂，并用于解決函數(shù)求極值的問題。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的粒子群算法整體性能良好，可用于求解其他函數(shù)求極值的問題。