依概率收斂的改進粒子群優(yōu)化算法

錢偉懿，李明

(渤海大學(xué) 數(shù)理學(xué)院，遼寧 錦州 121013)

依概率收斂的改進粒子群優(yōu)化算法

錢偉懿，李明

(渤海大學(xué) 數(shù)理學(xué)院，遼寧 錦州 121013)

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

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

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

1 標(biāo)準(zhǔn)PSO算法

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

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

2 改進的PSO算法

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

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

位置與速度越界處理：

改進PSO算法的流程如下：

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

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

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

7)令

；

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

3 收斂性分析

本文考慮如下全局優(yōu)化問題：

minimizef(x)

subject tox∈S

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

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

f(x*)≤f(x)

則稱x*為S的全局最優(yōu)解。

定義2 對任意ε>0，設(shè)

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

則稱Bε為ε最優(yōu)解集，x∈Bε被稱為ε-最優(yōu)解。

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

由定義1和2得:

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

式中pr表示概率測度。

于是

由引理2有

于是

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

令

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

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

4 數(shù)值實驗

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

表1 高維單峰函數(shù)的實驗結(jié)果

表2 高維多峰函數(shù)的實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[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]郭建濤,劉瑞杰,陳新武. 用于跳頻分量選取的修正適應(yīng)度距離比粒子群算法[J]. 重慶郵電大學(xué)學(xué)報：自然科學(xué)版, 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]姜建國，田旻，王向前，等. 采用擾動加速因子的自適應(yīng)粒子群優(yōu)化算法[J]. 西安電子科技大學(xué)學(xué)報， 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算法中學(xué)習(xí)因子(c1,c2)取值的實驗與分析[J]. 廣東工業(yè)大學(xué)學(xué)報， 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]. 計算機工程與應(yīng)用， 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]王麗芳，曾建潮. 基于微粒群算法與模擬退火算法的協(xié)同進化方法 [J]. 自動化學(xué)報， 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]艾兵，董明剛. 基于高斯擾動和自然選擇的改進粒子群優(yōu)化算法[J]. 計算機應(yīng)用， 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]. 智能系統(tǒng)學(xué)報，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]戴月明,朱達祥,吳定會. 核矩陣協(xié)同進化的震蕩搜索粒子群優(yōu)化算法[J]. 重慶郵電大學(xué)學(xué)報：自然科學(xué)版, 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.網(wǎng)絡(luò)出版日期2017-04-07.

國家自然科學(xué)基金項目(11371071);遼寧省教育廳科學(xué)研究項目(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

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

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

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

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