帶過濾機(jī)制非線性慣性權(quán)重粒子群算法

秦毅，彭力

江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫 214122

帶過濾機(jī)制非線性慣性權(quán)重粒子群算法

秦毅，彭力

江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫 214122

為改進(jìn)非線性慣性權(quán)重粒子群算法，提出了一種帶過濾機(jī)制的非線性慣性權(quán)重粒子群算法。由于原算法存在粒子易陷入局部最優(yōu)解與搜索效率較低的缺點(diǎn)，將適應(yīng)度縮放函數(shù)引入到非線性慣性動(dòng)態(tài)調(diào)整的粒子群算法中，剔除適應(yīng)度過高與過低的粒子，再對剩余種群部分優(yōu)良個(gè)體進(jìn)行復(fù)制，并隨機(jī)產(chǎn)生一些新粒子，然后進(jìn)行交叉操作，種群數(shù)量保持不變，減少了粒子陷入局部極值的概率，使結(jié)果收斂于全局最優(yōu)解。通過低維度與高維度函數(shù)的對比測試，表明新算法具有較為理想的效果。

過濾機(jī)制；適應(yīng)度縮放；慣性權(quán)重；非線性粒子群算法

1 引言

很多學(xué)者針對標(biāo)準(zhǔn)粒子群算法易陷于早熟收斂，局部最優(yōu)，提出了改進(jìn)的粒子群算法[1-5]。針對其收斂速度的情況，有學(xué)者提出了慣性權(quán)重遞增的算法[6]，也有學(xué)者提出了慣性權(quán)重遞減的方法[7]，這些算法在一定程度上都改善了算法的收斂速度及算法得到最優(yōu)解的特性。通過實(shí)驗(yàn)發(fā)現(xiàn)，具有遞增慣性權(quán)重的粒子群算法前期收斂速度較快，但是容易陷入局部最優(yōu)解，具有遞減慣性權(quán)重的粒子群算法前期具有較強(qiáng)的局部搜索能力，但是后期收斂速度較差。

本文提出了一種帶過濾機(jī)制的交叉粒子非線性慣性權(quán)重動(dòng)態(tài)調(diào)整的PSO算法，首先對位置和速度進(jìn)行非線性自適應(yīng)調(diào)整，然后通過適應(yīng)度縮放函數(shù)將適應(yīng)度很好以及很不好的粒子剔除，再對進(jìn)化過程中部分不良適應(yīng)值的粒子用優(yōu)良的粒子進(jìn)行復(fù)制交叉，減少不良適應(yīng)值粒子出現(xiàn)的概率，從而使得算法在初期就過濾掉了一些不良粒子，加快了算法的收斂速度，減小了粒子陷于早熟收斂的概率，更加快速地得到最優(yōu)解。

2 算法模型

粒子群優(yōu)化算法（PSO）和其他進(jìn)化類算法類似，是一種迭代的優(yōu)化算法。PSO算法最初是Kennedy博士和Eberhart教授于1995年提出的，該算法模仿鳥群等群體動(dòng)物尋找食物的社會(huì)性行為來建立的，具有算法簡單及容易實(shí)現(xiàn)的優(yōu)點(diǎn)[8]。在PSO算法中，每個(gè)粒子都代表著搜索空間中的一個(gè)可行解，所有粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值，粒子的速度和位置決定了它飛翔的距離和方向，粒子通過跟蹤兩個(gè)極值來更新自己，一個(gè)是粒子本身所經(jīng)歷的最優(yōu)解，稱為個(gè)體極值Pi；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，稱為全局極值Pj。假設(shè)在一個(gè)m維搜索空間中，有n個(gè)粒子組成一粒子群，其中第i個(gè)粒子的空間位置為Xi=(Xi1，Xi2，…，Xim)其飛行速度Vi=(Vi1，Vi2，…，Vim)，i=1，2，…，n。Xi是優(yōu)化問題的一個(gè)潛在解，將它代入優(yōu)化目標(biāo)函數(shù)可以計(jì)算出相應(yīng)的適應(yīng)值，根據(jù)適應(yīng)值可衡量Xi的優(yōu)劣。對每一代粒子，其速度及位置的更新公式如下：

其中，ω為慣性權(quán)值，它使粒子保持運(yùn)動(dòng)慣性。c1和c2都為正常數(shù)，稱為加速系；R1和R2是兩個(gè)在[0，1]范圍內(nèi)變化的隨機(jī)數(shù)，用以保證粒子群體的多樣性和搜索的隨機(jī)性。

Vi+1是Vi、Pj-Xi和Pg-Xi的矢量和，如圖1所示。粒子速度的每一維都會(huì)被限制在一個(gè)最大速度Vmax(Vmax＞0)，若某一維更新后的速度超過用戶設(shè)定的Vmax。

圖1 粒子可能移動(dòng)方向圖

為了保證粒子在優(yōu)化前期的快速性，以及保證粒子在優(yōu)化后期不發(fā)散，對標(biāo)準(zhǔn)粒子群算法的公式進(jìn)行調(diào)整，加入一個(gè)自適應(yīng)參數(shù)來保證上述要求。

3 穩(wěn)定性分析

為方便推導(dǎo)，現(xiàn)將式（1）和（2）簡記成式（4）和（5），其中C1=c1r1，C2=c2r2，Pg，Pb為外部輸入[9]。

把式（4）和（5）中的時(shí)間項(xiàng)向后推一步，得：

假設(shè)Pg和Pb在粒子運(yùn)動(dòng)過程中保持不變，由式（4）、（5）、（6）和（7）得：

若將粒子的速度變化過程看作一個(gè)時(shí)間連續(xù)過程，則式（9）可對應(yīng)一個(gè)典型的二階齊次線性微分方程：

其中e1，e2為方程（*）的根。

如果將位置變化看作一個(gè)時(shí)間連續(xù)過程，則式（12）可對應(yīng)一個(gè)二階微分方程，其對應(yīng)的一般解的形式為：

其中k1，k2，k3是與粒子初始狀態(tài)相關(guān)的常數(shù)，記粒子第0、1、2步的位置為xi(0)，xi(1)，xi(2)，由式（13）有

當(dāng)粒子位置趨向無窮大時(shí)，粒子的運(yùn)動(dòng)軌跡將是發(fā)散的，多個(gè)粒子運(yùn)動(dòng)軌跡發(fā)散也將導(dǎo)致粒子群的發(fā)散。下面對粒子位置變化過程的穩(wěn)定性進(jìn)行分析。

對式（14）取Z變換，得：其中，?=C1+C2-1-w。為便于分析，假設(shè)C1，C2為某一常數(shù)使得式（19）成為一個(gè)線性系統(tǒng)，其特征方程為：

整理后得：

粒子的位置變化過程穩(wěn)定的條件為：

當(dāng)滿足條件式（24）時(shí)，由Z變換的終值定理可得：

4 算法改進(jìn)

本文提出了一種帶過濾機(jī)制的粒子交叉復(fù)制與慣性權(quán)重相結(jié)合、慣性權(quán)重沿正弦曲線先增后減的改進(jìn)粒子群算法，并且對速度進(jìn)行參數(shù)自適應(yīng)調(diào)整，這樣算法在保證前期階段具有較快的收斂速度的同時(shí)，對種群進(jìn)行過濾，減小了不良粒子出現(xiàn)的概率。算法首先計(jì)算出種群中每一個(gè)粒子所對應(yīng)的適應(yīng)值，剔除適應(yīng)值不良的部分個(gè)體，再從剩余的個(gè)體中選出一些適應(yīng)值優(yōu)良的個(gè)體，使這些個(gè)體在種群中復(fù)制一次，另外隨機(jī)產(chǎn)生一新個(gè)體，這兩個(gè)群體之間在進(jìn)行交叉，復(fù)制及新產(chǎn)生的個(gè)體數(shù)量之和等于過濾掉粒子的數(shù)量，以保持種群大小不變。這樣優(yōu)良適應(yīng)值的粒子取代部分適應(yīng)值不良的個(gè)體，使得優(yōu)秀適應(yīng)值個(gè)體在種群中所占比例增大。保證收斂速度的同時(shí)避免搜索過程中過早地陷于局部最優(yōu)解，適當(dāng)補(bǔ)充新個(gè)體，增強(qiáng)種群活力，提高搜索到最優(yōu)解的可能性。這樣既保留了原來算法收斂速度快，又克服了原算法易陷入局部最優(yōu)解的缺點(diǎn)，取得了比較好的實(shí)驗(yàn)效果。

對ω，η參數(shù)進(jìn)行自適應(yīng)動(dòng)態(tài)調(diào)整。參數(shù)的調(diào)整規(guī)律[10]為：

式（25）中，ηmax，ηmin是η變化的最大值與最小值，一般取ηmax∈[1.0，1.8]，ηmin∈[0.4，0.8]，t為粒子群進(jìn)化代數(shù)，maxnumber為最大迭代次數(shù)，一半取α∈[0.005，0.015]。

5 仿真研究

為了驗(yàn)證上文中提出算法的性能，采用Shaffer’sF6、LevyNo.5、4Generalized Schwefel’s Problem 2.26、以及Generalized Griewank Function四個(gè)函數(shù)，對其加以測試，并對結(jié)果進(jìn)行分析。函數(shù)特性如表1所示。

表1 函數(shù)特性表

上述函數(shù)中，前兩個(gè)是二維的函數(shù)，后兩個(gè)是多維的函數(shù)，分別用以上四個(gè)函數(shù)做測試，測試過程中，種群數(shù)設(shè)置為50，最大迭代數(shù)為2 000，迭代結(jié)束的條件為最優(yōu)解與最優(yōu)適應(yīng)值差小于0.000 01。仿真實(shí)驗(yàn)共做3次，每次實(shí)驗(yàn)中共進(jìn)行100次優(yōu)化過程。陷入局部極值的實(shí)驗(yàn)結(jié)果如表1。

表2中1表示本文提出的例子群算法，2表示基本粒子群算法，3表示非線性慣性權(quán)重的粒子群算法。從表2中可以看出，采用本文提出的PSO算法，能有效地避免粒子陷入局部最優(yōu)解，同時(shí)還能保證算法的快速性。算法的性能優(yōu)于其他的兩種。

表2 三種方法的陷入局部極值次數(shù)對比

為了更進(jìn)一步地表現(xiàn)本文提出的算法的有效性，用基本粒子群算法，非線性慣性權(quán)重粒子群算法，以及本文提出的改進(jìn)算法對上文中提出的四個(gè)測試函數(shù)進(jìn)行優(yōu)化，對結(jié)果做了對比，對比圖形如圖2～圖5所示。

圖2 Shaffer’s F6函數(shù)的對比測試圖

圖3 LevyNo.5函數(shù)的對比測試圖

圖4 Generalized Schwefel’s Problem 2.26函數(shù)的對比測試圖

圖5 Generalized Griewank Function：函數(shù)的對比測試圖

從圖2～圖5可以看出，在算法的初期，本文提出的算法在保證了收斂速度的同時(shí)，也避免了算法陷入局部最優(yōu)解，而在算法的后期收斂速度有所降低，能夠保證尋優(yōu)的過程能逐漸接近最優(yōu)解，避免了粒子震蕩的發(fā)生。而對于維度較低的測試函數(shù)，本文改進(jìn)的粒子群算法相對于其他兩種算法的優(yōu)勢不是特別明顯，而對于高維度的函數(shù)，即圖4、5可以看出，本文改進(jìn)的算法在保證收斂速度的同時(shí)也很好地克服了算法在尋優(yōu)的過程中陷入早熟收斂。

6 結(jié)論

本文提出了一種帶過濾機(jī)制的交叉粒子非線性慣性權(quán)重動(dòng)態(tài)調(diào)整的PSO算法在保證了算法前期的搜索速度的同時(shí)，避免了粒子陷入局部最優(yōu)解，而在算法的后期，避免了無效粒子過多而出現(xiàn)粒子震蕩，對于高維度的函數(shù)來說，本文提出的算法在尋優(yōu)過程中明顯優(yōu)于其他兩種算法，實(shí)驗(yàn)取得了比較理想的效果。

[1]Shi Y，Eberhart R.Fuzzy adaptive particle swarm optimization[C]//Proceedings of Congress on Evolutionary Computation，2001，3（27）：101-106.

[2]Angeline P J.Using selection to improve particle swarm optimization[C]//Proceedings of the Congress on Evolutionary Computation，1998，3（4）：84-89.

[3]崔志華，曾建潮.一種動(dòng)態(tài)調(diào)整的改進(jìn)微粒群算法[J].系統(tǒng)工程學(xué)報(bào)，2005，20（6）：657-660.

[4]夏桂梅，曾建潮.雙群體隨機(jī)微粒群算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（24）：46-48.

[5]王麗芳，曾建潮.基于微粒群算法與模擬退火算法的協(xié)同進(jìn)化方法[J].自動(dòng)化學(xué)報(bào)，2006，32（4）：630-635.

[6]Shi Y，Eberhart R C.Comparing inertia weights and constriction factors in particle swarm optimization[C]//Proceedings of the 2000 Congress on Evolutionary Computation.Conference Publications，2000（1）：84-88.

[7]Shi Y，Eberhart R.C.Recent advances in particle swarm[C]// Congress on Evolutionary Computation，2004（1）：90-97.

[8]Kennedy J，Eberhart R C.Particle Swarm Optimization[C]// IEEE International Conference on Neural Networks.Piscataway，NJ：IEEE Service Center，1995：1942-1948.

[9]李寧.粒子群優(yōu)化算法的理論分析與應(yīng)用研究[D].武漢：華中科技大學(xué)，2006.

[10]溫黎茗，彭力.用正弦函數(shù)描述非線性慣性權(quán)重的微粒群算法[J].計(jì)算機(jī)仿真，2012，29（5）：235-238.

QIN Yi,PENG Li

School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China

This paper proposes nonlinear inertia weight particle swarm optimization with a filtering mechanism to improve the non-linear inertia weight particle swarm algorithm.Due to the original algorithm exsists two shortcomings of particles falling into the local optimal solution and lower search efficiency,introduces fitness scaling function to the nonlinear inertia dynamically for the particle swarm optimization,fitness of excellent and poor particle are removed,then copy some excellent individual of remaining population,meanwhile randomly generated new particles,and crossover operation to them,populations remain unchanged,the methed reduces the opportunity that particulates fall into the localmaximum and make the results converge to the global optimum.In order to verify the effectiveness of the algorithm.In this paper,low dimensions and high dimensional function are compared with each other.The result show s that this method achieves good effects.

filtering mechanism;fitness scaling;inertia weight;nonlinear particle swarm algorithm

A

TP39

10.3778/j.issn.1002-8331.1208-0478

QIN Yi,PENG Li.Non linear inertia weigh t particle swarm optimization with filtering mechanism.Computer Engineering and Applications,2014,50（16）：35-38.

秦毅（1987—），男，研究生，主要研究方向?yàn)橹悄軟Q策系統(tǒng)與仿真；彭力（1967—），男，博士，博導(dǎo)，主要研究方向視覺傳感器網(wǎng)絡(luò)，人工智能，計(jì)算機(jī)仿真。E-mail：qinyidee@163.com

2012-09-04

2012-10-11

1002-8331（2014）16-0035-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-11-28,http://www.cnki.net/kcm s/detail/11.2127.TP.20121128.1453.006.htm l