基于鄰居適應(yīng)值的改進(jìn)粒子群算法研究

李承啟，龍圣杰，劉衍民*

（1.五邑大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣東江門529020；2.遵義師范學(xué)院數(shù)學(xué)學(xué)院，貴州遵義563006）

粒子群算法（PSO）[1]是Eberhart和Kennedy在1995年提出的，它是源于對(duì)鳥類覓食行為的模擬，具有操作簡(jiǎn)單、求解速度快等優(yōu)點(diǎn)。與其它進(jìn)化算法一樣，PSO也存在容易早熟、局部尋優(yōu)能力差等缺點(diǎn)。因此，為了提升算法的運(yùn)行效率，許多學(xué)者提出了各種不同的改進(jìn)策略，以克服算法存在的不足。例如，在種群拓?fù)浣Y(jié)構(gòu)改進(jìn)領(lǐng)域，文獻(xiàn)[2，3]提出了帶收斂因子的局部版本的粒子群算法（CF-LPSO）和帶收斂因子的全局版本的粒子群算法（CF-GPSO），文獻(xiàn)[4]提出了局部版本的PSO（FIPS）。還有一些研究者對(duì)粒子的學(xué)習(xí)對(duì)象進(jìn)行改進(jìn)，如文獻(xiàn)[5]提出了合作粒子群算法(CPSO)，文獻(xiàn)[6]提出了全面學(xué)習(xí)粒子群算法（CLPSO），文獻(xiàn)[7]提出了適應(yīng)距離比例的粒子群算法（FDR-PSO）等，這些改進(jìn)策略對(duì)于粒子跳出局部最優(yōu)都有一定的效果，但是在求解精度和實(shí)現(xiàn)上仍有很大改進(jìn)空間。

由于前面提到的改進(jìn)算法存在一定的不足，本文提出了一種新的改進(jìn)算法（NFPSO），該算法將種群分成三個(gè)子群，提取每個(gè)子群中最優(yōu)個(gè)體，采用加權(quán)法構(gòu)建具有全局代表性的最優(yōu)個(gè)體。在檢測(cè)函數(shù)的測(cè)試中，實(shí)驗(yàn)結(jié)果表明，相比基本粒子群算法NFPSO具有較好的性能，是對(duì)基本粒子群算法的一種有效改進(jìn)。

1 基本粒子群算法

粒子群算法因其具有結(jié)構(gòu)簡(jiǎn)單、操作方便的特點(diǎn)，在智能優(yōu)化計(jì)算、圖像識(shí)別與工程應(yīng)用等領(lǐng)域得到廣泛應(yīng)用。

算法的進(jìn)化方式如下：

其中為i粒子的歷史最

種群在進(jìn)化過程中，粒子i的當(dāng)前最好位置更新規(guī)則如下：

2 基于鄰居適應(yīng)值的改進(jìn)算法

種群個(gè)體學(xué)習(xí)樣本的選取是決定算法運(yùn)行效率的主要因素之一[4]，而種群的拓?fù)浣Y(jié)構(gòu)（個(gè)體的鄰居集合）決定了學(xué)習(xí)樣本的選取。針對(duì)標(biāo)準(zhǔn)粒子群算法，根據(jù)種群鄰居個(gè)體的不同，把標(biāo)準(zhǔn)粒子群算法分為全局版本（GPSO）和局部版本（LPSO），本文在LPSO基礎(chǔ)上，采用把種群中每個(gè)個(gè)體的鄰居平均分成三個(gè)子群，然后提取每個(gè)子群中運(yùn)行最優(yōu)的個(gè)體，對(duì)提取的個(gè)體按照適應(yīng)值優(yōu)劣進(jìn)行排序，并按照個(gè)體的貢獻(xiàn)比例，運(yùn)用加權(quán)法來確定個(gè)體的學(xué)習(xí)樣本。

在本文提出的改進(jìn)策略中，對(duì)每個(gè)子群中對(duì)應(yīng)的個(gè)體以適應(yīng)值作為評(píng)價(jià)標(biāo)準(zhǔn)由優(yōu)到劣進(jìn)行排序。把適應(yīng)值最優(yōu)的個(gè)體所在的部分定義為最優(yōu)俱樂部（最優(yōu)運(yùn)行個(gè)體用表示），適應(yīng)值居中的定義為標(biāo)準(zhǔn)俱樂部（最優(yōu)運(yùn)行個(gè)體用表示），適應(yīng)值最差的定義為最差俱樂部（最優(yōu)運(yùn)行個(gè)體用表示）。根據(jù)社會(huì)學(xué)理論所述：一個(gè)個(gè)體在社會(huì)中的地位和作用會(huì)隨著他所處的集體不同而改變，例如：一個(gè)綜合實(shí)力表現(xiàn)一般的人如果處在社會(huì)精英云集的集體里，他的表現(xiàn)可能會(huì)最差；在同類人構(gòu)成的集體里，他的表現(xiàn)可能會(huì)較優(yōu)；但在一個(gè)平庸的集體里，他的表現(xiàn)可能會(huì)最優(yōu)。基于這一理論，將種群分成的三個(gè)子群分別類比于個(gè)體在不同環(huán)境中的表現(xiàn)，分別給予不同的子群不同的權(quán)重，多次仿真結(jié)果表明：三個(gè)子群的加權(quán)系數(shù)分別取0.7、0.2和0.1為最優(yōu)的表現(xiàn)形式。綜上，本文提出的速度更新公式為

根據(jù)種群進(jìn)化方程（5）和（6），NFPSO算法流程如下：

第二步：對(duì)于每個(gè)粒子，將當(dāng)前的適應(yīng)值與該粒子經(jīng)歷過的最好適應(yīng)值進(jìn)行比較，如果優(yōu)于后者，則被當(dāng)前的適應(yīng)值替代；否則不變；

第四步：隨機(jī)把種群鄰居平均分成三個(gè)子群，確定每個(gè)子群中運(yùn)行最優(yōu)的個(gè)體，并將其按適應(yīng)值從優(yōu)到差進(jìn)行排序；

第五步：根據(jù)式（5）（6）重新計(jì)算出每個(gè)粒子的速度和位置；

第六步：判斷是否滿足終止條件，若滿足，輸出最后的全局最優(yōu)解和全局最優(yōu)值，算法結(jié)束；若不滿足，返回第二步。

3 實(shí)驗(yàn)結(jié)果和討論

4.1 測(cè)試函數(shù)的選取

為測(cè)試算法的性能，選取國(guó)際上公認(rèn)的六個(gè)測(cè)試函數(shù)來測(cè)試算法的運(yùn)行效果，檢測(cè)函數(shù)表達(dá)式如下：

（1）Sphere函數(shù)

（2）Rosenbrock函數(shù)

（3）Ackley函數(shù)

（4）Griewanks函數(shù)

（5）Rastrigin函數(shù)

（6）Schewfel函數(shù)

表1給出了六個(gè)檢測(cè)函數(shù)的全局最優(yōu)解、對(duì)應(yīng)的全局最優(yōu)值以及測(cè)試函數(shù)的搜索范圍。

表1 測(cè)試函數(shù)的全局最優(yōu)值和搜索范圍

4.2 實(shí)驗(yàn)結(jié)果和討論

實(shí)驗(yàn)設(shè)置如下：算法的種群規(guī)模為30，檢測(cè)函數(shù)為30維，各種算法獨(dú)立運(yùn)行10次，計(jì)算次數(shù)均為3×104次，其它參數(shù)與算法提出時(shí)一致。選取國(guó)際上公認(rèn)的經(jīng)典改進(jìn)算法CF-LPSO[2]、CF-GPSO[3]、FIPS[4]和CPSO[5]算法與本文提出的NFPSO算法進(jìn)行比較。

圖1給出了6個(gè)檢測(cè)函數(shù)的收斂特征圖，可以看出對(duì)于兩個(gè)單峰函數(shù)而言，NFPSO收斂速度非?？?，尤其是Sphere函數(shù)，NFPSO顯著改善了運(yùn)行結(jié)果，其它4種算法都陷入了局部最優(yōu)。對(duì)于多峰函數(shù)而言，NFPSO算法不論在收斂速度和精度上相比其它算法也都表現(xiàn)出較好的運(yùn)行結(jié)果。對(duì)于Rastrigin復(fù)雜多峰函數(shù)，NFPSO算法相比CF-LPSO、CFGPSO、FIPS算法表現(xiàn)出了極大的優(yōu)勢(shì)，它能有效地跳出局部最優(yōu)解，預(yù)防早熟現(xiàn)象。

表2和表3分別給出算法在單峰和多峰檢測(cè)函數(shù)下獨(dú)立運(yùn)行10次所得出的平均值和方差，最好結(jié)果用粗體表示。從表中可以看出，NFPSO所獲結(jié)果都優(yōu)于其它算法，與圖1所得結(jié)論一致。這主要由于NFPSO算法采用了個(gè)體在群體中作用發(fā)揮機(jī)理，將種群中個(gè)體的信息充分利用，有效地提升了種群多樣性。

圖1 檢測(cè)函數(shù)的收斂特征圖

表2 單峰函數(shù)在五個(gè)算法下運(yùn)行10次的平均值及方差

表3 多峰函數(shù)在五個(gè)算法下運(yùn)行10次的平均值及方差

5 結(jié)論

本文提出了鄰居適應(yīng)值粒子群算法（NFPSO），借鑒了個(gè)體在集體中的作用發(fā)揮與其所處環(huán)境直接相關(guān)的社會(huì)學(xué)原理。以鄰居適應(yīng)值為依據(jù)，動(dòng)態(tài)地構(gòu)建種群最優(yōu)粒子的拓?fù)浣Y(jié)構(gòu)，進(jìn)而提升粒子之間的信息交流能力，增加種群多樣性，此策略提高了算法的尋優(yōu)能力。仿真實(shí)驗(yàn)表明，NFPSO不論是在單峰函數(shù)還是多峰函數(shù)上相比其它改進(jìn)算法都表現(xiàn)了較優(yōu)的結(jié)果。然而，粒子鄰域的隨機(jī)性對(duì)算法的穩(wěn)定性有一定的影響，在今后的研究中將進(jìn)行進(jìn)一步的改進(jìn)。

[1]Kennedy J,Eberhart R.Particle swarm optimization[C].IEEE International Conference on Neural Networks,Piscataway,1995.1942-1948.

[2]Kennedy J,Eberhart R.Population structure and particle swarm performance[C].Congress on Evolutionary Computation,Honolulu,2002.1671-1676.

[3]Clerc M,Kennedy J.The particle swarm-explosion,stability,and convergence in a multidimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.

[4]Mendes R,kennedy J.The fully informed particle swarm:Simple,maybe better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.

[5]Van dBF,Engelbrecht AP.A cooperative approach to particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):225-239.

[6]Peram T,Veeramachaneni K,Mohan CK.Fitness-distance-ratio based particle swarm optimization[J].Swarm Intelligence Symposium,2003,1019(1):174-181.

[7]Liang JJ,Qin AK,Suganthan PN,et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation,2006,10(3):281-295.