基于改進粒子群算法的函數(shù)優(yōu)化

陳永剛 邱涌 牛丹梅

(河南科技大學(xué)電子信息工程學(xué)院,河南 洛陽 471003)

1.引言

粒子群優(yōu)化算法（PSO）是由Kennedy和Eberhart等于1995年發(fā)明的一種基于群智能的進化計算技術(shù)[1，2]，來源于對鳥群捕食的行為研究。后來shi等人[3]引入慣性權(quán)重，形成了當(dāng)前的標(biāo)準(zhǔn)版本。PSO的優(yōu)勢在于概念簡單，容易實現(xiàn)并且沒有許多參數(shù)需要調(diào)整。因此，該算法很快應(yīng)用于神經(jīng)網(wǎng)絡(luò)[4]、多目標(biāo)優(yōu)化[5]、函數(shù)優(yōu)化[6]等問題。作為一種高效的全局優(yōu)化算法，PSO可用于求解大量非線性、不可微和多峰值的復(fù)雜函數(shù)優(yōu)化問題。為了提高算法的優(yōu)化效率，近幾年出現(xiàn)了很多改進的PSO算法,并且已經(jīng)應(yīng)用于許多科學(xué)和工程領(lǐng)域。然而，當(dāng)遇到某些具有較多局部極值點的搜索空間時，PSO算法的搜索效率可能會突然大大降低并且在最優(yōu)點附近的搜索效率也不高。

對于這些問題，許多人做了大量的工作來改進算法的性質(zhì)，比如從參數(shù)的控制角度出發(fā)，可以結(jié)合其它算法來增強算法的效率。本文提出了一種改進的粒子群算法，通過不斷隨機初始化部分適應(yīng)值較差的粒子的位置，個體歷史最優(yōu)粒子做相互交叉變異和群體最優(yōu)粒子在最優(yōu)值空間附近的變異搜索，有效地克服了算法的早熟收斂，搜索效率和速度都有較大的提高。

2.粒子群優(yōu)化算法介紹（PSO）

PSO初始化為一群隨機粒子（隨機解），然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優(yōu)解。這個叫做個體極值，記為Pi。另一個極值是整個種群目前找到的最優(yōu)解。這個極值是全局極值，記為Pg。

設(shè)搜索空間為D維，總粒子數(shù)為n，第i個粒子表示為Xi=(xi1，xi2，…，xiD)；第 i個粒子的歷史最優(yōu)位置記為 Pi=(pi1，pi2，…，piD);整個群體經(jīng)歷過的最好位置記為 Pg=(pg1，pg2，…，pgD);粒子速度記為Vi=(vi1，vi2，…，viD)。則對于每一代，每個粒子的位置根據(jù)如下方程變化：

其中c1和c2是非負(fù)常數(shù)，稱為學(xué)習(xí)因子。r1和r2是介于[0，1]之間的隨機數(shù)。w稱為慣性因子，w較大適用于對解空間進行大范圍探查，w較小適用于進行小范圍搜索。每一維粒子的速度都會被限制在一個最大速度Vmax,如果某一維更新后的速度超過用戶設(shè)定的Vmax，那么這一維的速度就被設(shè)定為Vmax，即 Vid∈[-Vmax,Vmax]。

PSO算法基本步驟如下：

Step1：隨機初始化粒子種群，即初始化種群中所有粒子的速度和位置(可行解)；

Step2：根據(jù)適應(yīng)度函數(shù)對粒子種群進行評價；

Step3：更新粒子的個體極值；

Step4：更新粒子的群體極值；

Step5：根據(jù)式(1)和(2)進行速度和位置的迭代；

Step6：重復(fù)Step2～Step5,直到滿足算法停止迭代的條件。

3.改進的粒子群算法（MPSO）

本文提出的改進算法中，位置和速度更新公式仍然與PSO相同。

3.1 部分粒子的位置隨機變化

由于粒子群算法對于多峰值函數(shù)空間的優(yōu)化容易早熟收斂，每次迭代搜索時，使適應(yīng)值最差的部分粒子的位置在搜索空間中重新隨機分布，這樣就改善了部分粒子的位置值，保持了粒子的多樣性，使部分粒子進行算法發(fā)散的搜索。這里取全部粒子的30%進行隨機初始化。

3.2 歷史個體最優(yōu)粒子之間進行交叉變異

對歷史個體最優(yōu)粒子之間進行兩兩雜交，這個雜交概率由一個隨機數(shù)確定，與粒子的適應(yīng)度沒有關(guān)系。在每次迭代中，所有的個體最優(yōu)粒子進行隨機的兩兩雜交，產(chǎn)生同樣數(shù)目的孩子粒子，并用孩子粒子代替父母粒子作為個體最優(yōu)粒子來引導(dǎo)粒子的運動。孩子粒子的位置由父母粒子的位置的算術(shù)加權(quán)計算。公式如下：

3.3 對群體最優(yōu)粒子進行小范圍位置變異

PSO算法的一個不足之處在于在算法運行的后期，受到速度等因素影響，粒子會在全局最優(yōu)點附近擺動，卻不能到達到全局最優(yōu)點?？紤]到此時粒子距離最優(yōu)點已經(jīng)很近了，因此應(yīng)該進行小步長的變異。使最優(yōu)粒子位置做出變異，除了能做進一步搜索之外，還可以引導(dǎo)其它粒子作搜索。位置變異公式如下：

其中Pi的適應(yīng)值比較接近Pg，可在個體歷史最優(yōu)群體中前10%的個體中隨機選取一個。r3為隨機整數(shù)，r4是介于[0，1]之間的隨機數(shù)。算法中Pg對采取保序策略，用一個變量保存最優(yōu)的Pg，保證算法得到的最優(yōu)解。

4.仿真結(jié)果及其分析

（1）為了驗證本文改進算法的有效性，本文以求解兩個基準(zhǔn)測試函數(shù)的最小值為例，通過計算機仿真比較本文算法和標(biāo)準(zhǔn)PSO算法的性能。選擇以下2個典型函數(shù)進行測試：

sphere函數(shù)

實驗中兩種算法的群體規(guī)模為30，慣性權(quán)重w的值從1.1線性遞減到0.3，c1=c2=2，第一個函數(shù)為10維，第二個函數(shù)為2維。

算法迭代次數(shù)為1000次，取平均適應(yīng)值和平均迭代次數(shù)。結(jié)果如表1：

表1 仿真結(jié)果

從表中的指標(biāo)上看，改進的算法MPSO都優(yōu)于標(biāo)準(zhǔn)的PSO，且求解精度優(yōu)勢明顯優(yōu)于標(biāo)準(zhǔn)PSO，說明了改進算法的有效性。

5.結(jié)論

對標(biāo)準(zhǔn)的PSO算法主要進行了3個方面的改進，大大改善了粒子種群的多樣性，增強了優(yōu)化性能的穩(wěn)定性，較好地解決了算法的早熟收斂和后期搜索精度較低的缺點。實驗證明，改進后的算法達到了預(yù)期的目的。

[1]Kennedy J,Eberhart R.Particle swarm optimization[A].Proc IEEE Int Conf on Neural Networks[C].Perth,1995.1942-1948.

[2]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[A].Proc 6th Int Symposium on Micro Machine and Human Science[C].Nagoya,1995.39-43.

[3]Shi Y,Eberhart R.A modified particle swarm optimizer[C].In：IEEE World Congresson Computational Intelligence,1998：69-73.

[4]基于擴展的T-S模型的PSO神經(jīng)網(wǎng)絡(luò)在故障診斷中的應(yīng)用[J].計算機科學(xué),2009,36(9)：224-245.

[5]基于小生境的極性PSO多目標(biāo)優(yōu)化及應(yīng)用 [J].自動化與儀表,2011,08：45-48.

[6]一種基于量子行為的改進粒子群算法 [J].計算機工程與應(yīng)用,2007,43(36)：89-91.