陳永剛 邱涌 牛丹梅

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

1.引言

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

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

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

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

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

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

PSO算法基本步驟如下：

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

Step2：根據(jù)適應(yīng)度函數(shù)對(duì)粒子種群進(jìn)行評(píng)價(jià)；

Step3：更新粒子的個(gè)體極值；

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

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

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

3.改進(jìn)的粒子群算法（MPSO）

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

3.1 部分粒子的位置隨機(jī)變化

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

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

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

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

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

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

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

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

sphere函數(shù)

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

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

表1 仿真結(jié)果

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

5.結(jié)論

對(duì)標(biāo)準(zhǔn)的PSO算法主要進(jìn)行了3個(gè)方面的改進(jìn)，大大改善了粒子種群的多樣性，增強(qiáng)了優(yōu)化性能的穩(wěn)定性，較好地解決了算法的早熟收斂和后期搜索精度較低的缺點(diǎn)。實(shí)驗(yàn)證明，改進(jìn)后的算法達(dá)到了預(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]基于擴(kuò)展的T-S模型的PSO神經(jīng)網(wǎng)絡(luò)在故障診斷中的應(yīng)用[J].計(jì)算機(jī)科學(xué),2009,36(9)：224-245.

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

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