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

【摘 要】由于PSO算法采用了隨機(jī)集群的理念，與其他智能算法類似，會(huì)出現(xiàn)“早熟”或收斂速度慢的問題。全面學(xué)習(xí)粒子群算法（CLPSO）是模擬鳥群的隨機(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)象；能夠較好地跳出求解聚類中心過程中易陷入某一局部的極小值的情況，從而得到全局最優(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.粒子群算法簡介

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

2.基本粒子群算法簡介

假定存在n維的搜索空間，在算法開始的時(shí)候，取定粒子數(shù)為m來建立微粒群，通過每次迭代來更新粒子信息，這個(gè)過程中，粒子需要不斷地對(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ù)如下公式來更新速度和位置的值：

（ ） （ ） （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ù)。為了盡量避免在迭代過程中發(fā)生粒子離開搜索空間，通常給粒子的速度限定一個(gè)范圍，即vid∈[-vmax，vmax]。若問題的搜索空間限定在[-xmax，xmax]，則可設(shè)定vmax=k*xmax，其中k∈[0.1，1]。由更新公式很容易得到粒子更新的速度計(jì)算主要由三個(gè)部分決定，即粒子i更新前的 ，粒子i的當(dāng)前位置與粒子最優(yōu)位置之間的距離（ - ），（ - ）表示粒子i所在位置距離粒子群中最優(yōu)位置的大小。該粒子新位置的確定可通過（1）、（2）兩個(gè)式子判斷。

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

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

ω （ ） （ ） （3）

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

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

1.改進(jìn)思路

由于PSO算法采用了隨機(jī)集群的理念，與其他智能算法如遺傳算法等類似，會(huì)出現(xià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ì)于低維問題的優(yōu)化，使用標(biāo)準(zhǔn)粒子群算法非常容易得到滿意的優(yōu)化結(jié)果。但對(duì)于高維問題，標(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é)果見下表，記錄了基本粒子群算法和改進(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

新算法通過動(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算法。通過若干標(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)燕〕