依概率收斂的改進粒子群優化算法

錢偉懿，李明

(渤海大學 數理學院，遼寧 錦州 121013)

依概率收斂的改進粒子群優化算法

錢偉懿，李明

(渤海大學 數理學院，遼寧 錦州 121013)

粒子群優化算法是一種隨機優化算法，但它不依概率1收斂到全局最優解。 因此提出一種新的依概率收斂的粒子群優化算法。 在該算法中，首先引入了具有探索和開發能力的兩個變異算子，并依一定概率對粒子當前最好位置應用這兩個算子，然后證明了該算法是依概率1收斂到ε-最優解。 最后，把該算法應用到13個典型的測試函數中，并與其他粒子群優化算法比較，數值結果表明所給出的算法能夠提高求解精度和收斂速度。

粒子群優化算法；隨機優化算法；變異算子；依概率收斂；全局優化；進化計算；啟發式算法；高斯分布

粒子群優化算法是Kennedy等[1]在1995年提出的一種群體搜索的隨機優化算法。由于PSO算法的參數少而且易操作，所以在實際問題中得到了廣泛的應用。對PSO算法的研究主要有以下幾個方面：1)對PSO算法自身參數的改進，這方面的工作主要關于慣性權重的自適應改進[2-9]和對學習因子的改進[9-11]；2)將其他進化算法與PSO相結合，比如，遺傳算法與PSO算法結合[12-13]，差分進化算法與PSO算法結合[14]，模擬退火算法與PSO算法結合[15]；3)在PSO算法引入一些改進PSO算法性能的其他算子，比如，把高斯擾動策略加入粒子群優化算法中[16]，把均勻設計方法引入到粒子群優化算法中[17]，把變異策略[18]、精英策略[19]、局部搜索策略[20]及鄰域搜索策略[21]引入到粒子群優化算法中；4)PSO算法的理論分析，比如，基于線性系統理論研究PSO收斂性[22-25]，基于隨機過程研究PSO收斂性[26]，但是粒子群算法不依概率收斂[26]。本文給出了一種依概率1收斂的PSO算法，該算法在標準粒子群優化算法實施位置更新后按一定概率對較好的粒子實施具有開發能力的變異操作，對較差的粒子實施具有探索能力的變異操作，從而平衡了算法的全局搜索能力和局部搜索能力，提高了算法的效率，另外，證明了該算法依概率1收斂到ε-最優解。實驗結果表明，提出的算法能夠提高全局搜索能力，算法的收斂速度明顯加快。

1 標準PSO算法

標準粒子群算法中，粒子群由Np個粒子組成，在時刻k，第i個粒子在d維空間中速度和位置的更新公式為

式中：ωstart、ωend分別為最初和最終的慣性權重，Kmax是最大迭代步。

2 改進的PSO算法

提高PSO算法性能的有效方法之一就是平衡算法的探索能力和開發能力。我們的目的是對粒子所經歷的最好位置進行操作，一方面能夠使其跳出局部最優；另一方面使其具有一定的局部搜索能力。為此，給出兩個變異算子：

式中：ρ1>1和ρ2>1是常數，N(0,σ2)是具有時變標準差σ的高斯分布的隨機變量，σ表示為

位置與速度越界處理：

改進PSO算法的流程如下：

1)設置參數，隨機初始化粒子的位置和速度，計算各粒子的適應度，確定每個粒子的經歷過的最優位置及全局最優位置，令k=1；

2)按式(3)計算慣性權重，并按式(1)和式(2)進行速度與位置更新；

3) 按式(10)和式(11)進行越界處理；

7)令

；

9) 判斷是否滿足終止條件(本文采用最大迭代步)，若滿足則輸出結果，否則令k=k+1，轉2)。

3 收斂性分析

本文考慮如下全局優化問題：

minimizef(x)

subject tox∈S

式中：f:S→R是實值函數,S={xmin≤x≤xmax}，xmin=(l1,l2,…,lD)，xmax=(u1,u2,…,uD)。

定義1 設f(x)是實值函數，x*∈S，若對任意x∈S，

f(x*)≤f(x)

則稱x*為S的全局最優解。

定義2 對任意ε>0，設

Bε=x∈Sf(x)-f(x*)<ε

則稱Bε為ε最優解集，x∈Bε被稱為ε-最優解。

本文假設μ(Bε)>0, 其中μ為勒貝格測度。

由定義1和2得:

定義3 設ΦNp={Φ丨Φ=(φ1，…，φNp),φi∈Γ,i=1,…,Np}，則稱ΦNp為狀態空間，Φ∈ΦNp稱為狀態。

式中pr表示概率測度。

于是

由引理2有

于是

證明由算法可知，Φk+1只與Φk有關，所以Φ1,Φ2,Φ3,…是馬爾可夫過程，由馬爾可夫過程性質及引理1可知

令

Δ={ΦPg?Bε}?ΦNp

則?Φ∈ΦNp，由引理3有

4 數值實驗

為了評價改進算法(簡稱，IPSO)的性能，我們選取文獻[24]中的13個測試函數進行實驗研究。前7個函數為高維單峰函數，后6個函數是高維多峰函數。在本文中13個問題的維數都取30。IPSO算法的實驗結果與LDIWPSO[2]、CDIWPSO[3]、DAPSO[4]、和SSRDIWPSO[5]實驗結果進行比較。所有算法的共同參數設置如下：ωstart=0.9，ωend=0.4，Np=30，c1=c2=2，vmin=0.5xmin，vmax=0.5xmax，Kmax=3 000，IPSO算法的其他參數設置如下：ρ1=2,ρ2=0.1,σmax=1,σmin=0.2。所有算法的程序都是由MATLAB2007實現，且每個實驗獨立運行30次，實驗結果見表1和表2。

表1 高維單峰函數的實驗結果

表2 高維多峰函數的實驗結果

從表1可以看出，除了測試函數F1、F5和F6外,IPSO算法與其他4種算法相比，在尋優能力和穩定性方面明顯優于其他4種算法，特別是測試函數F3和F4，其他4種算法不能獲得到最優解，而IPSO算法能夠得到較理想的最優解，且穩定性也非常好。對于測試函數F1來說，IPSO算法不如SSRDIWPSO算法，但是優于其他3種算法。對于測試函數F5來說，IPSO算法的最好收斂值不如其他4種算法，但是對于平均收斂值和方差來說，IPSO算法優于其他4種算法。對于測試函數F6，IPSO算法與其他4種算法獲得相同的結果。總之，對于高維單峰函數來說IPSO算法有一定優勢，其原因如下：函數F1～F7都單峰函數，由于IPSO算法有較好的局部搜索能力，所以IPSO算法對于單峰函數具有一定優勢。函數F1是非線性簡單的單峰函數，所以大多數算法都能夠找到最優解；函數F5是很難極小化的典型病態二次函數，由于其全局最優解與可達到的局部最優之間有一道狹窄的山谷，所以算法很難辨別搜索方向，找到全局最優解的機會很小，因此5種算法都沒有找到全局最優解，而函數F7是含有隨機變量的函數，由于目標函數不確定，找到非常理想的全局最優解也是較困難的。

從表2可以看出，除了測試函數F12和F13外IPSO算法與其他4種算法相比，在尋優能力和穩定性方面明顯優于其他4種算法，特別是測試函數F9和F11，其他4種算法不能獲得較好最優解，而IPSO算法能夠得到非常理想的最優解，且穩定性也非常好。對于測試函數F12來說，關于最好收斂值，IPSO算法不如SSRDIWPSO和CDIWPSO算法，但是優于其他兩種算法，而關于最差收斂值、平均收斂值和方差，IPSO算法遠好于其他4種算法。對于測試函數F13來說，對于最好收斂值IPSO算法不如SSRDIWPSO和CDIWPSO算法，對于平均收斂值，IPSO算法與SSRDIWPSO算法一樣優于其他3種算法。總之，除了函數F8～F13外，對于其他函數IPSO算法都能夠得到滿意結果，其原因如下：函數F8～F13都是多峰函數且有較多局部最優解，由于IPSO算法按一定概率對適應值較差的粒子實行全局搜索，對于適應值較好的粒子實行局部搜索，所以IPSO算法對于解決多峰函數有一定優勢。但是由于函數F8的全局最優解與局部最優相距較遠，且有一定的欺騙性，導致算法朝著錯誤方向搜索，因此不易找到滿意的全局最優解；函數F13含有大量深度不同的“坑”，導致算法陷入第一個坑后不易跳出來，因此也不易找到滿意的全局最優解。

為了更清楚且直觀地比較各種算法的收斂性，我們分別從高維單峰函數和高維多峰函數中選取3個函數進行收斂曲線分析，圖1～圖3分別表示測試函數F1、F4、和F6的收斂曲線，其中用100-100代替0。圖4～圖6分別表示測試函數F8、F10和F12的收斂曲線。

圖1 函數F1的收斂曲線Fig.1 Convergence curve of function F1

圖2 函數F4的收斂曲線Fig.2 Convergence curve of function F4

圖3 函數F6的收斂曲線Fig.3 Convergence curve of function F6

從圖1～6中可以看出，對于函數F4、F10和F12，IPSO算法的收斂速度及求解精度明顯優于其他4種算法，對于函數F6，雖然求解精度一樣，但是IPSO算法的收斂速度明顯比其他4種算法收斂快，對于函數F1，雖然收斂精度IPSO算法不如SSRDIWPSO算法，但是他較快收斂到人們比較滿意精度，對于函數F8，IPSO算法的求解精度略優于其他4種算法。總之，IPSO算法有較好的收斂速度和求解精度。

圖4 函數F8的收斂曲線Fig.4 Convergence curve of function F8

圖5 函數F10的收斂曲線Fig.5 Convergence curve of function F10

圖6 函數F12的收斂曲線Fig.6 Convergence curve of function F12

5 結束語

針對標準PSO算法不依概率收斂和易出現早熟收斂等缺點，提出了標準粒子群優化算法中增加了具有開發能力和探索能力兩個變異算子，其目的是平衡算法的全局探索能力和局部搜索能力。并且從理論上證明所提出算法依概率1收斂到ε-最優解。數值結果表明，所提出的算法較大提高了全局尋優能力且具有較好的魯棒性。在未來的工作中，將對變異算子中的參數設置進一步研究，以便提高算法收斂精度與收斂速度。

[1]KENNEDY J, EBERHART R C. Particle swarm optimization[C]//IEEE International Conference on Neural Networks. Perth, Australia, 1995: 1942-1948.

[2]SHI Y H, EBERHART R C. Empirical study of particle swarm optimization[C]//IEEE International Conference on Evolutionary Computation. Washington, USA, 1999: 1945-1950.

[3]FENG Y, TENG G F A X， WANG Y， et al. Chaotic inertia weight in particle swarm optimization[C]//Proceedings of the 2nd international conference on innovative computing, information and control. Kumamoto, Japan, 2007: 475.

[4]SHEN X， CHI Z Y, CHEN J C. et al. Particle swarm optimization with dynamic adaptive inertia weight[C]//International conference on challenges in environmental science and computer engineering. Wuhan, China, 2010: 287-290.

[5]ADEWUMI A O, ARASOMWAN A M. An improved particle swarm optimizer based on swarm success rate for global optimization problems[J]. Journal of experimental and theoretical artificial intelligence, 2016, 28(3): 441-483.

[6]PLUHACEK M, SENKERIK R, DAVENDRA D, et al.On the behavior and performance of chaos driven PSO algorithm with inertia weight[J]. Computers and mathematics with applications, 2013, 66: 122-134.

[7]YANG C, GAO W, LIU N, et al. Low-discrepancy sequence initialized particle swarm optimization algorithm with high-order nonlinear time-varying inertia weight[J]. Applied soft computing, 2015, 29: 386-394.

[8]郭建濤,劉瑞杰,陳新武. 用于跳頻分量選取的修正適應度距離比粒子群算法[J]. 重慶郵電大學學報：自然科學版, 2015, 27(1): 26-30.

GUO Jiantao， LIU Ruijie， CHEN Xinwu. Modified fitness-distance ratio based particle swarm optimizer for selection of frequency hopping components[J]. Journal of chongqing university of posts and telecommunications： natural science edition， 2015, 27(1): 26-30.

[9]ARDIZZON G, CAVAZZINI G, PAVESI G. Adaptive acceleration coefficients for a new search diversification strategy in particle swarm optimization algorithms[J]. Information sciences, 2015, 299: 337-378.

[10]姜建國，田旻，王向前，等. 采用擾動加速因子的自適應粒子群優化算法[J]. 西安電子科技大學學報， 2012， 39(4)： 74-79.

JIANG Jianguo, TIAN Min, WANG Xiangqian, et al. Adaptive particle swarm optimization via disturbing acceleration coefficients[J]. Journal of xidian university, 2012， 39(4)： 74-79.

[11]任鳳鳴，李麗娟. 改進的PSO算法中學習因子(c1,c2)取值的實驗與分析[J]. 廣東工業大學學報， 2008， 25(1)： 86-89.

REN Fengming, LI Lijuan. Experiment and analysis of the value selection of acceleration coefficients (c1,c2) in IPSO method [J]. Journal of Guangdong university of technology, 2008， 25(1)： 86-89.

[12]GRIMACCIA F, MUSSETTA M， ZICH R. Genetical swarm optimization: self-adaptive hybrid evolutionary algorithm for electromagnetics[J]. IEEE transactions on antennas and propagation, 2007, 55(3): 781-785.

[13]熊偉麗，徐保國，吳曉鵬，等. 帶變異算子的改進粒子群算法研究[J]. 計算機工程與應用， 2006， 42(26)： 1-3.

XIONG Weili, XU Baoguo, WU Xiaopeng， et al. Study on the particle swarm optimization with mutation operator [J]. Computer engineering and applications, 2006， 42(26)： 1-3.

[14]段玉紅，高岳林. 基于差分演化的粒子群算法 [J]. 計算機仿真， 2009, 26(6): 212-215.

DUAN Yuhong, GAO Yuelin. A particle swarm optimization algorithm based on differential evolution[J]. Computer simulation, 2009, 26(6): 212-215.

[15]王麗芳，曾建潮. 基于微粒群算法與模擬退火算法的協同進化方法 [J]. 自動化學報， 2006， 32(4)： 630-635.

WANG Lifang， ZENG JianChao. A cooperative evolutionary algorithm based on particle swarm optimization and simulated annealing algorithm[J]. Acta automatica sinica, 2006, 32(4): 630-635.

[16]艾兵，董明剛. 基于高斯擾動和自然選擇的改進粒子群優化算法[J]. 計算機應用， 2016， 36(3): 687-691.

AI Bing, DONG Minggang. Improved particle swarm optimization algorithm based on Gaussian disturbance and natural selection[J]. Journal of computer applications, 2016, 36(3): 687-691.

[17]劉宏達，馬忠麗. 均勻粒子群算法 [J]. 智能系統學報，2010， 5(4)： 336-341.

LIU Hongda, MA Zhongli. A particle swarm optimization algorithm based on uniform design[J]. CAAI transactions on intelligent systems, 2010， 5(4)： 336-341.

[18]PEHLIVANOGLU Y V. A new particle swarm optimization method enhanced with a periodic mutation strategy and neural networks[J]. IEEE transactions on evolutionary computation, 2013, 17: 436-452.

[19]LIM W H, MATISA N A. An adaptive two-layer particle swarm optimization with elitist learning strategy[J]. Information sciences, 2014, 273: 49-72.

[20]WU G, QIU D, YU Y, et al. Superior solution guided particle swarm optimization combined with local search techniques[J]. Expert systems with applications, 2014, 41: 7536-7548.

[21]WANG H, SUN H, LI C， et al. Diversity enhanced particle swarm optimization with neighborhood search[J]. Information sciences, 2013, 223: 119-135.

[22]TIAN D P. A review of convergence analysis of particle swarm optimization[J]. international journal of grid and distributed computing, 2013, 6: 117-128.

[23]LIU Q. Order-2 stability analysis of particle swarm optimization[J]. Evolutionary computation, 2014, 23: 187-216.

[24] PAN F, LI X T, ZHOU Q， et al. Analysis of standard particle swarm optimization algorithm based on Markov chain[J]. Acta automatica sinica, 2013, 39(4): 81-289.

[25]戴月明,朱達祥,吳定會. 核矩陣協同進化的震蕩搜索粒子群優化算法[J]. 重慶郵電大學學報：自然科學版, 2016, 28(2): 247-253.

DAI Yueming， ZHU Daxiang， WU Dinghui. Shock search particle swarm optimization algorithm based on kernel matrix synergistic evolution[J]. Journal of chongqing university of posts and telecommunications： natural science edition， 2016, 28(2): 247-253.

[26]YAO X , LIU Y， LIN G. Evolutionary programming made faster[J]. IEEE transactions on evolutionary computation, 1999, 3(2): 81-102.

Improvedparticleswarmoptimizationalgorithmwithprobabilityconvergence

QIAN Weiyi， LI Ming

(College of Mathematics and Physics, Bohai University, Jinzhou 121013, China)

The particle swarm optimization (PSO) algorithm is a stochastic optimization algorithm that does not converge to a global optimal solution on the basis of probability 1. In this paper, we present a new probability-based convergent PSO algorithm that introduces two mutation operators with exploration and exploitation abilities, which are applied to the previous best position of a particle with a certain probability. This algorithm converges to the-optimum solution on the basis of probability 1.We applied the proposed algorithm in 13 typical test functions and compared its performance with that of other PSO algorithms. Our numerical results show that the proposed algorithm can improve solution precision and convergence speed.

particle swarm optimization; stochastic optimization algorithm; mutation operator; probability convergence; global optimization; evolutionary computation; heuristic algorithm; Gaussian distribution

2016-10-05.網絡出版日期2017-04-07.

國家自然科學基金項目(11371071);遼寧省教育廳科學研究項目(L2013426).

錢偉懿. E-mail：qianweiyi2008@163.com.

10.11992/tis.201610004

http://kns.cnki.net/kcms/detail/23.1538.tp.20170407.1744.008.html

TP301.6

A

1673-4785(2017)04-0511-08

中文引用格式：錢偉懿，李明.依概率收斂的改進粒子群優化算法J.智能系統學報， 2017, 12(4): 511-518.

英文引用格式：QIANWeiyi，LIMing.ImprovedparticleswarmoptimizationalgorithmwithprobabilityconvergenceJ.CAAItransactionsonintelligentsystems, 2017, 12(4): 511-518.

錢偉懿，男，1963年生，教授，博士，主要研究方向為智能計算、優化理論與方法，主持國家自然科學基金項目1項。發表學術論文60余篇，出版專著3部。

李明，男，1991年生，碩士研究生，主要研究方向為智能計算。