一種變異的改進粒子群優(yōu)化算法

陳永剛 邱 涌 肖春寶

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

1.引言

粒子群優(yōu)化算法（PSO）是由Kennedy和Eberhart等于1995年發(fā)明的一種基于群智能的進化計算技術(shù)[1，2]，來源于對鳥群捕食的行為研究。后來shi等人[3]引入慣性權(quán)重，形成了當(dāng)前的標(biāo)準版本。PSO的優(yōu)勢在于概念簡單，容易實現(xiàn)并且沒有許多參數(shù)需要調(diào)整，目前已經(jīng)成功應(yīng)用于結(jié)構(gòu)設(shè)計、神經(jīng)網(wǎng)絡(luò)[4]、多目標(biāo)優(yōu)化[5]等工程優(yōu)化中。

PSO算法收斂速度較快，但會出現(xiàn)早熟收斂，甚至不收斂的情況，尤其對于多峰函數(shù)而言不能令人滿意，對高維函數(shù)優(yōu)化在求解質(zhì)量上和速度上有些缺點。對PSO算法進行改進提高優(yōu)化性能為該領(lǐng)域的一個研究熱點。相繼出現(xiàn)了一些改進的算法，然而這些算法在一定程度上改善了算法的優(yōu)化性能，但很難在搜索精度和早熟收斂之間達到平衡。針對上述缺點，本文提出了一種改進的粒子群算法，該算法引入了合作算子[6]，在迭代優(yōu)化過程中對粒子進行兩種合作策略的變異，使粒子群體保持多樣性。本文分析了粒子速度更新公式的基礎(chǔ)上，提出了動態(tài)改變粒子的粒子分享個體最優(yōu)和群體最優(yōu)的信息比例的方法，使算法初期具有全局搜索能力，后期具有較好的搜索精度。實驗結(jié)果表明，該算法具有較好的優(yōu)化效率。

2.粒子群算法介紹

2.1 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是非負常數(shù)并且通常取值為2，稱為學(xué)習(xí)因子。r1和r2是介于[0，1]之間的隨機數(shù)。每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新后的速度超過用戶設(shè)定的Vmax，那么這一維的速度就被設(shè)定為Vmax，即 vid∈[-Vmax，Vmax]。

2.2 算法流程

標(biāo)準PSO的算法流程如下：

Step1：初始化所有粒子，包括隨機位置和速度；

Step2：評價每個粒子的適應(yīng)值；

Step3：對每個粒子，將其適應(yīng)值與其經(jīng)歷過的最好位置Pi作比較，如果較好，則將其作為當(dāng)前的最好位置Pi；

Step4：對每個粒子，將其Pi與全局所經(jīng)歷的最好位置pg作比較，如果較好，則重新設(shè)置pg；

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

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

3.改進的粒子群優(yōu)化算法(IPSO)

標(biāo)準的PSO算法中，若粒子找到一個最優(yōu)位置，則其他粒子會迅速向其靠攏，此時若最優(yōu)位置為局部最優(yōu)，則粒子就可能陷入早熟收斂。這樣就導(dǎo)致了粒子群體不能在優(yōu)化空間重新搜索和運動。為了使粒子能進一步進化和繼續(xù)優(yōu)化，本文采用了合作算子對歷史最優(yōu)粒子進行變異的方法。這樣不僅使變異后歷史最優(yōu)粒子更好地引導(dǎo)粒子的運動，使粒子擺脫局部收斂。還可以進化整個種群的最優(yōu)粒子，更好地搜索最優(yōu)解，提高搜索精度。同時對最優(yōu)粒子采取保序策略，確保群體最優(yōu)解向好的方向進化。

3.1 合作算子

設(shè)兩個個體粒子為 p1=(x1，x2，…xD)和 p2=(y1，y2，…yD)。如果∈(0，1)

合作策略1中，q和r由式（3）產(chǎn)生：

其中，βk為0和1之間的隨機數(shù)。

合作策略2中，由式（4）產(chǎn)生：

其中，1

3.2 對運動公式進行動態(tài)調(diào)整

由于算法的優(yōu)化效果取決于粒子運動的兩個公式，所以改動公式，就相當(dāng)于是粒子的運動發(fā)生了變化，進而產(chǎn)生不同的優(yōu)化效果。

從公式(1)可見，粒子速度更新由三部分完成。第一部分反應(yīng)粒子當(dāng)前速度的影響，聯(lián)系粒子當(dāng)前的狀態(tài)，起到了平衡全局和局部搜索的能力；第二部分反應(yīng)認知模式的影響，即粒子本身記憶的影響，使粒子具有全局搜索能力，避免陷入局部極??；第三部分反應(yīng)社會模式的影響，即群體信息的影響，體現(xiàn)粒子間的信息共享。令φ1=c1r1，φ2=c2r2，顯然φ1和φ2是介于0和2之間的隨機數(shù)。顯然在算法初期應(yīng)該增加粒子的群體搜索能力，這樣必須加強粒子本身記憶的影響，削弱群體最優(yōu)粒子的影響。這時，令φ1=1+φ1/2，φ2=φ2/2，這樣就有，φ1∈(1，2)，φ2∈(0，1)，較好地增加了個體經(jīng)驗對粒子速度的影響，提高群體多樣性，從而增加算法的全局搜索能力，有效增強避免早熟收斂能力。算法后期，由于大部分粒子都聚集在最優(yōu)粒子周圍，為了找到更好的結(jié)果，需要增加最優(yōu)解附近的搜索，需要最優(yōu)粒子分享更多的信息給整個種群。這時，令 φ1=φ1/2，φ2=1+φ2/2。這樣粒子局部搜索能力得到了加強，提高了優(yōu)化精度。

4.仿真實驗和結(jié)果分析

本文采用了標(biāo)準PSO算法和改進算法進行實驗，并將結(jié)果進行對比。兩種算法采用相同的參數(shù)設(shè)置。線性下降的慣性權(quán)重的變化范圍是[0.3，0.9]。實驗中的種群規(guī)模設(shè)置為30，粒子的維數(shù)為30，最大的迭代次數(shù)為1000次。CS設(shè)置為0.5，保證粒子的兩種變異方式都能平均地采用。兩個測試函數(shù)如下：

Rastrigin函數(shù)

Griewank函數(shù)

算法迭代次數(shù)為1000次。算法對每個函數(shù)獨立運行30次，取最優(yōu)值和平均最優(yōu)值作對比。結(jié)果如表1。

表1 仿真結(jié)果

從表中的測試結(jié)果中，可以看出本文IPSO算法的最優(yōu)收斂值和平均收斂值要優(yōu)于標(biāo)準PSO，這充分說明了IPSO算法具有更好的搜索精度，較強的抗早熟能力和較快的收斂速度，并且算法也具有較好的穩(wěn)定性。

5.結(jié)論

本文提出的改進PSO算法，對于每次迭代，粒子群體之間采用合作算子進行變異進化，合作算子通過粒子之間相互作用來增加彼此的適應(yīng)度，提高了算法的收斂速度和精度。對于算法不同階段粒子運動公式的改變，可以較好地平衡粒子的全局搜索和局部搜索的能力，避免算法陷入早熟收斂。通過對2個基準測試函數(shù)的仿真，證明了本文的IPSO算法對于高維、多極值點的函數(shù)有較好的效果。

[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 Congress on Computational Intelligence，1998：69-73.

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

[5]劉衍民，牛奔，趙慶禎.基于交叉和變異的多目標(biāo)粒子群算法[J].計算機應(yīng)用，2011，31(1)：82-84.

[6]焦李成，劉靜，鐘偉才.協(xié)同進化計算與多智能體系統(tǒng)[M].北京：科學(xué)出版社，2006.