基于慣性因子動(dòng)態(tài)化的一種改進(jìn)型粒子群算法

【摘 要】由于PSO算法采用了隨機(jī)集群的理念，與其他智能算法類似，會(huì)出現(xiàn)“早熟”或收斂速度慢的問(wèn)題。全面學(xué)習(xí)粒子群算法（CLPSO）是模擬鳥(niǎo)群的隨機(jī)搜索行為的一種應(yīng)用于連續(xù)空間的群體智能優(yōu)化算法，其主旨是對(duì)每個(gè)粒子的歷史最優(yōu)值一種概率的形式出現(xiàn)進(jìn)行更新。受全面學(xué)習(xí)粒子群算法啟發(fā)，結(jié)合基于慣性因子的PSO改進(jìn)算法，對(duì)慣性因子動(dòng)態(tài)化，得到一種改進(jìn)型粒子群算法。改進(jìn)算法可以較好地拓展粒子的學(xué)習(xí)對(duì)象和搜索范圍，避免“早熟”現(xiàn)象；能夠較好地跳出求解聚類中心過(guò)程中易陷入某一局部的極小值的情況，從而得到全局最優(yōu)解。

【關(guān)鍵詞】全面學(xué)習(xí)粒子群算法（CLPSO） 慣性因子動(dòng)態(tài)化 改進(jìn)算法

【中圖分類號(hào)】G642 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-4810（2013）15-0054-02

自粒子群算法提出至今，由于該算法本身所具有的易于實(shí)現(xiàn)、計(jì)算快速等優(yōu)越性能，使得它受到很多學(xué)者的青睞。目前，對(duì)于PSO算法的理論研究和實(shí)際應(yīng)用都取得了非常大的發(fā)展，但是該算法仍然有一些缺點(diǎn)，如易陷入局部最優(yōu)點(diǎn)、后期收斂速度較慢等。針對(duì)上述的情況，本文提出了一種改進(jìn)型的粒子群算法，然后用多種權(quán)威標(biāo)準(zhǔn)的測(cè)試函數(shù)測(cè)試改進(jìn)了的算法。與標(biāo)準(zhǔn)算法比較分析其結(jié)果，得出將粒子群優(yōu)化算法進(jìn)行改進(jìn)后，在加速后期的收斂性、防止得到的結(jié)果是局部最優(yōu)解，改善收斂穩(wěn)定性方面顯示了良好的潛能。

一 基本粒子群算法

1.粒子群算法簡(jiǎn)介

1995年，在受到鳥(niǎo)群覓食的啟發(fā)之后，Kennedy和Eberhart提出了粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）。PSO算法是一種群體智能優(yōu)化方法，和其他群體智能優(yōu)化算法相比，它具有易于實(shí)現(xiàn)和優(yōu)化過(guò)程簡(jiǎn)單的優(yōu)點(diǎn)。PSO算法通過(guò)微粒群初始化來(lái)隨機(jī)初始化微粒群，組成隨機(jī)種群，每個(gè)粒子被抽象成為沒(méi)有體積和質(zhì)量，最優(yōu)解也在其中，而單個(gè)微粒除了有一個(gè)適應(yīng)度值（即目標(biāo)函數(shù)的優(yōu)化值）以外，還有兩個(gè)矢量，分別代表飛行速度和位置。在整個(gè)全局尋優(yōu)的過(guò)程中，算法模擬具有智能的群體，利用粒子間的合作與競(jìng)爭(zhēng)，讓每個(gè)粒子在限定的搜索范圍內(nèi)以限定的速度進(jìn)行搜索，這樣從整體上看對(duì)每一個(gè)粒子通過(guò)不斷迭代更新自身的速度和位置，搜索全局最優(yōu)位置。

2.基本粒子群算法簡(jiǎn)介

假定存在n維的搜索空間，在算法開(kāi)始的時(shí)候，取定粒子數(shù)為m來(lái)建立微粒群，通過(guò)每次迭代來(lái)更新粒子信息，這個(gè)過(guò)程中，粒子需要不斷地對(duì)兩個(gè)極值進(jìn)行跟蹤以達(dá)到更新自己的目的。首先，第一個(gè)是粒子在附近找出個(gè)體的最優(yōu)的值Pbest，將其看作是粒子的個(gè)體飛行經(jīng)驗(yàn)解；另一個(gè)極值Gbest是全局最優(yōu)解（不是所有的粒子都能尋到），并將其看作是群體的飛行經(jīng)驗(yàn)。

設(shè)：粒子i的當(dāng)前位置：xi=（xi1，xi2，…，xin）；粒子i的前飛行速度：vi=（vi1，vi2，…，vin）；粒子的最佳適應(yīng)值（即Pbest）：Pi=（Pi1，Pi2，…，Pid）；粒子群的全局適應(yīng)值（即Gbest）：Pg=（Pg1，Pg2，…，Pgd）。

在每次迭代中，單個(gè)粒子根據(jù)如下公式來(lái)更新速度和位置的值：

（ ） （ ） （1）

（2）

其中，i=1，2，…，m，m表示群體中的粒子個(gè)數(shù)；k=1，2，…，l，l是迭代最大次數(shù)；d=1，2，…，n，n是自變量的個(gè)數(shù)； 、 分別表示在第k次迭代，第i個(gè)粒子位置矢量、速度矢量的第d維的分量； 表示第k次迭代，第i個(gè)粒子在局部最優(yōu)位置pb的第d維的分量； 表示第k次迭代，全部粒子在最優(yōu)位置gb的第d維的分量；c1、c2是學(xué)習(xí)因子，取值范圍大于或等于0，分別用于調(diào)節(jié)微粒向本身最好、向群體最好的位置飛行，是用于調(diào)節(jié)微粒的位置飛行。二者一般在[0，2]內(nèi)取值，通常令c1=c2，適合的學(xué)習(xí)因子可以加快收斂且不易陷入局部最優(yōu)。rand1和rand2是兩個(gè)介于[0，1]之間的服從均勻分布的隨機(jī)數(shù)。為了盡量避免在迭代過(guò)程中發(fā)生粒子離開(kāi)搜索空間，通常給粒子的速度限定一個(gè)范圍，即vid∈[-vmax，vmax]。若問(wèn)題的搜索空間限定在[-xmax，xmax]，則可設(shè)定vmax=k*xmax，其中k∈[0.1，1]。由更新公式很容易得到粒子更新的速度計(jì)算主要由三個(gè)部分決定，即粒子i更新前的 ，粒子i的當(dāng)前位置與粒子最優(yōu)位置之間的距離（ - ），（ - ）表示粒子i所在位置距離粒子群中最優(yōu)位置的大小。該粒子新位置的確定可通過(guò)（1）、（2）兩個(gè)式子判斷。

二 基于慣性因子的PSO改進(jìn)算法

粒子群算法不要求目標(biāo)函數(shù)具有很好的數(shù)學(xué)性質(zhì)，如有偏導(dǎo)和連續(xù)等特點(diǎn)，并且它是一種隨機(jī)并行的易于實(shí)現(xiàn)的優(yōu)化算法。但是，目前PSO仍然面臨著一些比較困難的問(wèn)題，針對(duì)不同的問(wèn)題，研究者做了不同的改進(jìn)。算法是否成功，其中一個(gè)很重要的因素是對(duì)于性質(zhì)相異的問(wèn)題，如何處理好在搜索過(guò)程中出現(xiàn)的全局與局部的搜索能力的比例關(guān)系。對(duì)此，Yuhui Shi改進(jìn)了PSO算法，在算法中增加了慣性變量的權(quán)重，其迭代的公式如下：

ω （ ） （ ） （3）

式中ω>0，稱為慣性因子。

三 一種改進(jìn)型粒子群算法

1.改進(jìn)思路

由于PSO算法采用了隨機(jī)集群的理念，與其他智能算法如遺傳算法等類似，會(huì)出現(xiàn)“早熟”或收斂速度慢的問(wèn)題。引人關(guān)注的一種方法是全面學(xué)習(xí)粒子群算法（Comprehensive Learning Particle Swarm Optimization algorithm，CLPSO），其主旨是對(duì)每個(gè)粒子的歷史最優(yōu)值一種概率的形式出現(xiàn)進(jìn)行更新，受之啟發(fā)，我們對(duì)式（3）進(jìn)行如下修正：

vid=wvid+c1rand1（pf（i）d-xid）+c2rand2（gid-xid） （4）

xid=xid+vid （5）

式中f（i）表示從所有粒子的歷史最優(yōu)值中依照一定的概率選中某個(gè)粒子的歷史最優(yōu)值。可以推想，這樣拓展了學(xué)習(xí)對(duì)象和搜索范圍，可以避免“早熟”現(xiàn)象。改進(jìn)算法的具體步驟如下：

步驟一：隨機(jī)設(shè)置粒子群的位置 ，1≤i≤N，速度 ，1≤i≤N，微粒i當(dāng)前最優(yōu)適應(yīng)度值所在位置 與全體粒子群最優(yōu)適應(yīng)度值所在位置 ，其中，N為粒子群所含粒子個(gè)數(shù)，d為粒子維度， （ … ）， （ … ），

（ … ）， （ … ），1≤i≤N。

步驟二：根據(jù)構(gòu)造的適應(yīng)度函數(shù)F（.）計(jì)算各粒子當(dāng)前位置的適應(yīng)度值F（ ）以及全局最優(yōu)位置適應(yīng)度值 （ ），1≤i≤N，k為迭代次數(shù)。

步驟三：在當(dāng)前迭代步驟對(duì)于每個(gè)粒子計(jì)算個(gè)體最優(yōu)位置 { F（ ），F(xiàn)（ ），… ，F(xiàn)（ ）}。

步驟四：計(jì)算整個(gè)粒子群在當(dāng)前迭代步驟下的全局最優(yōu)位置 { F（ ），F(xiàn)（ ），… ，F(xiàn)（ ）}和全局最優(yōu)值F（g（k））。

步驟五：對(duì)所有粒子進(jìn)行如下計(jì)算：

對(duì)i粒子隨機(jī)產(chǎn)生兩個(gè)服從0到1均勻分布的隨機(jī)數(shù)rand1和rand2；更新每個(gè)粒子的速度和位置，生成下一代粒子群， c1rand1·（ ）+c2rand2·（ ）

其中1≤i≤N，w為慣性權(quán)重，f（i）表示從所有粒子的歷史最優(yōu)值中依照一定的概率選中某個(gè)粒子的歷史最優(yōu)值。

步驟六：如果當(dāng)前迭代滿足終止條件，則終止迭代。否則轉(zhuǎn)到步驟二。

2.改進(jìn)粒子群算法的測(cè)試

在對(duì)粒子群算法進(jìn)行一定目的的改進(jìn)后，后面將對(duì)其改進(jìn)后的性能進(jìn)行測(cè)試。為了分析改進(jìn)后的粒子群算法的性能，本論文引入了較權(quán)威的測(cè)試函數(shù)，即Sphere函數(shù)和Rosenbrock

函數(shù)，Schaffer函數(shù)。Sphere函數(shù)： ；Rosenbrock

函數(shù)： ；Schaffer函數(shù)：

；Becker and Lago Problem（BL函數(shù)）：

f4=（|x1|-5）2+（|x2|-5）2。

以上四個(gè)測(cè)試函數(shù)，用傳統(tǒng)的優(yōu)化算法即使在二維情況下也很難優(yōu)化，且優(yōu)化難度隨著維數(shù)的增加而急劇增加。對(duì)于低維問(wèn)題的優(yōu)化，使用標(biāo)準(zhǔn)粒子群算法非常容易得到滿意的優(yōu)化結(jié)果。但對(duì)于高維問(wèn)題，標(biāo)準(zhǔn)粒子群算法的優(yōu)化結(jié)果可能會(huì)不令人滿意。為此，本文對(duì)四個(gè)函數(shù)的測(cè)試均在40維下進(jìn)行，以便更加清楚地對(duì)改進(jìn)以后的算法性能進(jìn)行檢驗(yàn)比較。

3.算法的參數(shù)比較分析

算法的優(yōu)化結(jié)果如下：

（a）f1測(cè)試結(jié)果 （b）f2測(cè)試結(jié)果

（c）f3測(cè)試結(jié)果 （d）f4測(cè)試結(jié)果

測(cè)試函數(shù)的迭代收斂曲線圖

其中數(shù)據(jù)測(cè)試結(jié)果見(jiàn)下表，記錄了基本粒子群算法和改進(jìn)粒子群算法尋得的最優(yōu)值，經(jīng)比較易得出改進(jìn)算法的收斂效果比較好，尋得了較好的極值點(diǎn)。

測(cè)試函數(shù)尋優(yōu)結(jié)果

測(cè)試函數(shù)基本粒子群改進(jìn)粒子群

最優(yōu)數(shù)值Std最優(yōu)數(shù)值Std

f13.2382634047E-100.019715843511E-10

f20.0046895723E-100.003995408077E-10

f30.0024589880E-70.0024558581714E-7

f40.059703704403E-120.004976223677E-12

新算法通過(guò)動(dòng)態(tài)地使慣性系數(shù)與最大迭代次數(shù)得到疊加，加強(qiáng)了粒子的全局搜尋能力，同時(shí)較好地提高收斂速度。從上表可以發(fā)現(xiàn)，對(duì)這些測(cè)試函數(shù)求解要求在相同的精度情況以及基本參數(shù)設(shè)置相同的條件下，改進(jìn)后的PSO的求解精度優(yōu)于傳統(tǒng)的PSO算法。通過(guò)若干標(biāo)準(zhǔn)測(cè)試函數(shù)仿真實(shí)驗(yàn)之后，進(jìn)行數(shù)據(jù)比對(duì)和分析，實(shí)驗(yàn)結(jié)果表明了該改進(jìn)的粒子群算法可以較好地預(yù)防陷入局部最優(yōu)解，盡可能達(dá)到全局最優(yōu)解。

優(yōu)化結(jié)果分析：由上述測(cè)試算法的收斂曲線的快速收斂，并在優(yōu)化后期平穩(wěn)收斂表明改進(jìn)后的粒子群算法具有有效性。

參考文獻(xiàn)

[1]Kennedy J、Eberhart R.C.Particle swarm optimization[C]. Proceedings of the IEEE international conference on neural networks，Perth，Australia，1995：1942～1948

[2]閆允一.粒子群優(yōu)化及其在圖像處理中的應(yīng)用研究[D].西安電子科技大學(xué)，2008

[3]Shi Y、Eberhart R C.A modified particle swarm optimizer[A]. In： Proceedings of the IEEE International Conference on Evolutionary Computation[C]. IEEE Press，Piscataway，NJ，1998：69～73

〔責(zé)任編輯：龐遠(yuǎn)燕〕