基于鄰居適應值的改進粒子群算法研究

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

（1.五邑大學數學與計算科學學院，廣東江門529020；2.遵義師范學院數學學院，貴州遵義563006）

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

由于前面提到的改進算法存在一定的不足，本文提出了一種新的改進算法（NFPSO），該算法將種群分成三個子群，提取每個子群中最優個體，采用加權法構建具有全局代表性的最優個體。在檢測函數的測試中，實驗結果表明，相比基本粒子群算法NFPSO具有較好的性能，是對基本粒子群算法的一種有效改進。

1 基本粒子群算法

粒子群算法因其具有結構簡單、操作方便的特點，在智能優化計算、圖像識別與工程應用等領域得到廣泛應用。

算法的進化方式如下：

其中為i粒子的歷史最

種群在進化過程中，粒子i的當前最好位置更新規則如下：

2 基于鄰居適應值的改進算法

種群個體學習樣本的選取是決定算法運行效率的主要因素之一[4]，而種群的拓撲結構（個體的鄰居集合）決定了學習樣本的選取。針對標準粒子群算法，根據種群鄰居個體的不同，把標準粒子群算法分為全局版本（GPSO）和局部版本（LPSO），本文在LPSO基礎上，采用把種群中每個個體的鄰居平均分成三個子群，然后提取每個子群中運行最優的個體，對提取的個體按照適應值優劣進行排序，并按照個體的貢獻比例，運用加權法來確定個體的學習樣本。

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

根據種群進化方程（5）和（6），NFPSO算法流程如下：

第二步：對于每個粒子，將當前的適應值與該粒子經歷過的最好適應值進行比較，如果優于后者，則被當前的適應值替代；否則不變；

第四步：隨機把種群鄰居平均分成三個子群，確定每個子群中運行最優的個體，并將其按適應值從優到差進行排序；

第五步：根據式（5）（6）重新計算出每個粒子的速度和位置；

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

3 實驗結果和討論

4.1 測試函數的選取

為測試算法的性能，選取國際上公認的六個測試函數來測試算法的運行效果，檢測函數表達式如下：

（1）Sphere函數

（2）Rosenbrock函數

（3）Ackley函數

（4）Griewanks函數

（5）Rastrigin函數

（6）Schewfel函數

表1給出了六個檢測函數的全局最優解、對應的全局最優值以及測試函數的搜索范圍。

表1 測試函數的全局最優值和搜索范圍

4.2 實驗結果和討論

實驗設置如下：算法的種群規模為30，檢測函數為30維，各種算法獨立運行10次，計算次數均為3×104次，其它參數與算法提出時一致。選取國際上公認的經典改進算法CF-LPSO[2]、CF-GPSO[3]、FIPS[4]和CPSO[5]算法與本文提出的NFPSO算法進行比較。

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

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

圖1 檢測函數的收斂特征圖

表2 單峰函數在五個算法下運行10次的平均值及方差

表3 多峰函數在五個算法下運行10次的平均值及方差

5 結論

本文提出了鄰居適應值粒子群算法（NFPSO），借鑒了個體在集體中的作用發揮與其所處環境直接相關的社會學原理。以鄰居適應值為依據，動態地構建種群最優粒子的拓撲結構，進而提升粒子之間的信息交流能力，增加種群多樣性，此策略提高了算法的尋優能力。仿真實驗表明，NFPSO不論是在單峰函數還是多峰函數上相比其它改進算法都表現了較優的結果。然而，粒子鄰域的隨機性對算法的穩定性有一定的影響，在今后的研究中將進行進一步的改進。

[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.