陳永剛 邱 涌 肖春寶

(河南科技大學(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)整，目前已經(jīng)成功應(yīng)用于結(jié)構(gòu)設(shè)計(jì)、神經(jīng)網(wǎng)絡(luò)[4]、多目標(biāo)優(yōu)化[5]等工程優(yōu)化中。

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

2.粒子群算法介紹

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

2.2 算法流程

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

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

Step2：評(píng)價(jià)每個(gè)粒子的適應(yīng)值；

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

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

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

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

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

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

3.1 合作算子

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

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

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

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

其中，1

3.2 對(duì)運(yùn)動(dòng)公式進(jìn)行動(dòng)態(tài)調(diào)整

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

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

4.仿真實(shí)驗(yàn)和結(jié)果分析

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

Rastrigin函數(shù)

Griewank函數(shù)

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

表1 仿真結(jié)果

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

5.結(jié)論

本文提出的改進(jìn)PSO算法，對(duì)于每次迭代，粒子群體之間采用合作算子進(jìn)行變異進(jìn)化，合作算子通過(guò)粒子之間相互作用來(lái)增加彼此的適應(yīng)度，提高了算法的收斂速度和精度。對(duì)于算法不同階段粒子運(yùn)動(dòng)公式的改變，可以較好地平衡粒子的全局搜索和局部搜索的能力，避免算法陷入早熟收斂。通過(guò)對(duì)2個(gè)基準(zhǔn)測(cè)試函數(shù)的仿真，證明了本文的IPSO算法對(duì)于高維、多極值點(diǎn)的函數(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]王建芳，李偉華.基于擴(kuò)展的T-S模型的PSO神經(jīng)網(wǎng)絡(luò)在故障診斷中的應(yīng)用[J].計(jì)算機(jī)科學(xué)，2009，36(9)：224-245.

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

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