帶過濾機制非線性慣性權重粒子群算法

秦毅，彭力

江南大學物聯網工程學院，江蘇無錫 214122

帶過濾機制非線性慣性權重粒子群算法

秦毅，彭力

江南大學物聯網工程學院，江蘇無錫 214122

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

過濾機制；適應度縮放；慣性權重；非線性粒子群算法

1 引言

很多學者針對標準粒子群算法易陷于早熟收斂，局部最優，提出了改進的粒子群算法[1-5]。針對其收斂速度的情況，有學者提出了慣性權重遞增的算法[6]，也有學者提出了慣性權重遞減的方法[7]，這些算法在一定程度上都改善了算法的收斂速度及算法得到最優解的特性。通過實驗發現，具有遞增慣性權重的粒子群算法前期收斂速度較快，但是容易陷入局部最優解，具有遞減慣性權重的粒子群算法前期具有較強的局部搜索能力，但是后期收斂速度較差。

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

2 算法模型

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

其中，ω為慣性權值，它使粒子保持運動慣性。c1和c2都為正常數，稱為加速系；R1和R2是兩個在[0，1]范圍內變化的隨機數，用以保證粒子群體的多樣性和搜索的隨機性。

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

圖1 粒子可能移動方向圖

為了保證粒子在優化前期的快速性，以及保證粒子在優化后期不發散，對標準粒子群算法的公式進行調整，加入一個自適應參數來保證上述要求。

3 穩定性分析

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

把式（4）和（5）中的時間項向后推一步，得：

假設Pg和Pb在粒子運動過程中保持不變，由式（4）、（5）、（6）和（7）得：

若將粒子的速度變化過程看作一個時間連續過程，則式（9）可對應一個典型的二階齊次線性微分方程：

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

如果將位置變化看作一個時間連續過程，則式（12）可對應一個二階微分方程，其對應的一般解的形式為：

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

當粒子位置趨向無窮大時，粒子的運動軌跡將是發散的，多個粒子運動軌跡發散也將導致粒子群的發散。下面對粒子位置變化過程的穩定性進行分析。

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

整理后得：

粒子的位置變化過程穩定的條件為：

當滿足條件式（24）時，由Z變換的終值定理可得：

4 算法改進

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

對ω，η參數進行自適應動態調整。參數的調整規律[10]為：

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

5 仿真研究

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

表1 函數特性表

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

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

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

為了更進一步地表現本文提出的算法的有效性，用基本粒子群算法，非線性慣性權重粒子群算法，以及本文提出的改進算法對上文中提出的四個測試函數進行優化，對結果做了對比，對比圖形如圖2～圖5所示。

圖2 Shaffer’s F6函數的對比測試圖

圖3 LevyNo.5函數的對比測試圖

圖4 Generalized Schwefel’s Problem 2.26函數的對比測試圖

圖5 Generalized Griewank Function：函數的對比測試圖

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

6 結論

本文提出了一種帶過濾機制的交叉粒子非線性慣性權重動態調整的PSO算法在保證了算法前期的搜索速度的同時，避免了粒子陷入局部最優解，而在算法的后期，避免了無效粒子過多而出現粒子震蕩，對于高維度的函數來說，本文提出的算法在尋優過程中明顯優于其他兩種算法，實驗取得了比較理想的效果。

[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]崔志華，曾建潮.一種動態調整的改進微粒群算法[J].系統工程學報，2005，20（6）：657-660.

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

[5]王麗芳，曾建潮.基于微粒群算法與模擬退火算法的協同進化方法[J].自動化學報，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]李寧.粒子群優化算法的理論分析與應用研究[D].武漢：華中科技大學，2006.

[10]溫黎茗，彭力.用正弦函數描述非線性慣性權重的微粒群算法[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—），男，研究生，主要研究方向為智能決策系統與仿真；彭力（1967—），男，博士，博導，主要研究方向視覺傳感器網絡，人工智能，計算機仿真。E-mail：qinyidee@163.com

2012-09-04

2012-10-11

1002-8331（2014）16-0035-04

CNKI網絡優先出版：2012-11-28,http://www.cnki.net/kcm s/detail/11.2127.TP.20121128.1453.006.htm l