任賀宇，郭 磊，趙開新

（1.河南交通職業(yè)技術(shù)學(xué)院，鄭州 450000；2.河南省民政學(xué)校，鄭州 450002；3.河南工學(xué)院，河南 新鄉(xiāng) 453002）

一種改進(jìn)的粒子群優(yōu)化算法*

任賀宇1，郭 磊2，趙開新3

（1.河南交通職業(yè)技術(shù)學(xué)院，鄭州 450000；2.河南省民政學(xué)校，鄭州 450002；3.河南工學(xué)院，河南 新鄉(xiāng) 453002）

針對基本粒子群算法存在著收斂速度慢、效率低、易陷入局部最優(yōu)等缺陷，為了更好地平衡全局和局部搜索能力，在粒子群算法中引入收縮因子，使算法中粒子不僅向種群最優(yōu)的粒子進(jìn)行學(xué)習(xí)，而且向種群中比自己優(yōu)秀的所有粒子學(xué)習(xí)，增加了粒子的多樣性。實驗結(jié)果證明，與基本蟻群算法相比，改進(jìn)的粒子群算法提高了收斂速度和效率，能一定程度地避免局部最優(yōu)解的產(chǎn)生。

粒子群，全局最優(yōu)，局部最優(yōu)，學(xué)習(xí)規(guī)則

0 引言

粒子群算法［1-2］（Particle swarm optimization algorithm）是由Eberhart和Kennedy在1995年基于鳥群的捕食活動而提出的一種啟發(fā)式的全局優(yōu)化算法。其基本思想是通過群體中個體的合作機(jī)制來迭代尋找最優(yōu)解的。算法中鳥群在捕食時個體的行為與自身的最佳位置信息和整個群體的最佳位置相關(guān)，在捕食初始階段，每只鳥向各個方向的運(yùn)動是隨機(jī)的，隨著時間的推移，所有鳥都趨向于一個中心移動，最終鳥群的運(yùn)動軌跡都趨于一致?；玖Ｗ尤核惴ù嬖谥諗克俣嚷?、局部最優(yōu)等缺陷，為了提高粒子群算法的性能，近些年來國內(nèi)外學(xué)者提出了許多優(yōu)化方案。其中包括動態(tài)修改慣性權(quán)重值、設(shè)置粒子的跳出和牽引機(jī)制、使粒子群算法與其他智能算法相融合等［3-4］。

1 粒子群算法的數(shù)學(xué)模型

圖1 粒子群速度更新圖

式（1）中ω為慣性權(quán)重值，c1和c2為學(xué)習(xí)因子，用于調(diào)節(jié)粒子對自己歷史經(jīng)驗最優(yōu)位置和整個群體最優(yōu)解位置的依賴程度，pkid表示粒子i在d維的個體位置最優(yōu)值，pkgd表示粒子群在d維的最優(yōu)值，r1，r2為（0，1）隨機(jī)數(shù)。為了防止粒子速度太快，還應(yīng)滿足式（3），其中 Vmax表示速度向量的最大值［5-6］。

在粒子群算法中，個體位置最優(yōu)解按式（4）進(jìn)行更新，群體位置最優(yōu)解按式（5）進(jìn)行更新［7-8］。

2 粒子群算法的改進(jìn)

2.1 在粒子群算法中引入收縮因子

為平衡種群局部和全局搜索能力，在基本粒子群算法引入收縮因子后，粒子速度的更新為式（6）。

2.2 改進(jìn)粒子的社會學(xué)習(xí)規(guī)則

式（1）中第3部分社會認(rèn)知選項只考慮了當(dāng)前粒子向群體內(nèi)全局最優(yōu)粒子學(xué)習(xí)，而忽略了向其他次優(yōu)粒子的學(xué)習(xí)，這樣可能會導(dǎo)致局部最優(yōu)解，改進(jìn)的算法中粒子向當(dāng)前群體中比自己優(yōu)秀的所有粒子學(xué)習(xí)，這增加了粒子的多樣性，能一定程度上避免局部最優(yōu)解的產(chǎn)生。改進(jìn)后粒子的速度更新為式（8）。

式（9）中m為粒子群中粒子數(shù)，f（）為粒子適應(yīng)度值的計算函數(shù)，pj表示第j個粒子的最優(yōu)位置，表示粒子群全局最優(yōu)位置，從式中可以看出，f（pj）越大，被學(xué)習(xí)的粒子越優(yōu)秀，ekid的值越大，gp表示當(dāng)前粒子i向粒子j學(xué)習(xí)程度越強(qiáng)。f（pj）的值越大，ekid的值越小，表示當(dāng)前粒子越優(yōu)秀，當(dāng)前粒子i向粒子j學(xué)習(xí)程度越弱。

2.3 改進(jìn)后粒子群算法的實現(xiàn)

用上述兩種方法優(yōu)化后粒子群算法的速度更新為式（10），位置更新仍采用式（1）。

優(yōu)化后粒子群算法的實現(xiàn)步驟。

Step1:初始化粒子群相關(guān)參數(shù)。

Step2:根據(jù)適應(yīng)度函數(shù)f（）求出各粒子的初始適應(yīng)度值。

Step3:根據(jù)優(yōu)化后粒子群算法更新式（10）更新各粒子的速度，根據(jù)位置更新式（2）更新各粒子的位置向量。

Step4:根據(jù)式（4）和式（5）更新最優(yōu)個體位置與最優(yōu)種群全局位置。

Step5:如果達(dá)到優(yōu)化后粒子群算法結(jié)束的條件或設(shè)定的迭代次數(shù)則搜索終止，否則轉(zhuǎn)到Step2繼續(xù)執(zhí)行。

3 仿真測試與分析

3.1 測試函數(shù)

為測試優(yōu)化后粒子群算法的效率，分別用函數(shù)Rosenbrock和Rastrigin來測試優(yōu)化前后的粒子群算法進(jìn)行分析，測試使用的算法有標(biāo)準(zhǔn)粒子群算法（PSO），引入收縮因子和改進(jìn)社會學(xué)習(xí)規(guī)則的粒子群算法（Particle swarm optimization algorithm with shrinkage factor and improved social learning rule，PSO-SFISLR），具體測試參數(shù)見表1。

表1 測試函數(shù)

3.2 測試結(jié)果分析

仿真實驗中設(shè)置種群規(guī)模為20個，每個粒子為30維，最大迭代次數(shù)為200，算法中ω取值為0.5，σ 值取 1，c1=c2=2.05，=0.792。圖2和圖3為用兩個測試函數(shù)對基本粒子群算法和優(yōu)化粒子群算法的測試結(jié)果，其中橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為適應(yīng)度值。

圖2 函數(shù)F1進(jìn)化曲線

圖3 函數(shù)F2進(jìn)化曲線

從圖2和圖3可以看出，通過兩個函數(shù)的測試結(jié)果，PSO-SFISLR比PSO有更快的收斂速度和求解速度，并且PSO-SFISLR能夠邊求解、邊優(yōu)化，而PSO會找到局部最優(yōu)的解而停止優(yōu)化，雖然迭代次數(shù)增加，仍不能跳出局部最優(yōu)解。PSO-SFISLR由于引入收縮因子和向比自己優(yōu)秀的所有粒子學(xué)習(xí)的特性，保持了種群的多樣性，提高了算法的求解性能和效率。

4 結(jié)論

本文提出了改進(jìn)社會學(xué)習(xí)規(guī)則和引入收縮因子的粒子群算法（PSO-SFISLR），該算法較好地平衡了全局和局部搜索能力，在粒子信息更新時不僅向種群最優(yōu)的粒子進(jìn)行學(xué)習(xí)，而且向比自己優(yōu)秀的所有粒子學(xué)習(xí)，通過仿真證明PSO-SFISLR有較高的全局搜索能力、較快的收斂速度和精度較高的尋優(yōu)搜索效率。

［1］袁正午，李君琪.基于改進(jìn)粒子群算法的云資源調(diào)度［J］.計算機(jī)工程與設(shè)計，2016，37（2）:401-404.

［2］趙莉.基于改進(jìn)量子粒子群算法的云計算資源調(diào)度［J］.南京理工大學(xué)學(xué)報，2016，40（2）:223-228.

［3］蔡琪，單冬紅.改進(jìn)粒子群算法的云計算環(huán)境資源優(yōu)化調(diào)度［J］.遼寧工程技術(shù)大學(xué)學(xué)報，2016，35（1）:93-96.

［4］趙志剛，林玉嬌.基于自適應(yīng)慣性權(quán)重的均值粒子群優(yōu)化算法［J］.計算工程與科學(xué)，2016，38（2）:501-505.

［5］彭建新，詹志輝.全局信息引導(dǎo)的改進(jìn)粒子群優(yōu)化算法［J］.小型微型計算機(jī)系統(tǒng)，2016，37（7）:1518-1521.

［6］李桂琴，李劉東.一種結(jié)合自適應(yīng)慣性權(quán)重的混合粒子群算法［J］.哈爾濱理工大學(xué)學(xué)報，2016，21（3）:49-53.

［7］徐從東.一種平衡全局與局部搜索能力的粒子群優(yōu)化算法［J］.微電子學(xué)與計算機(jī)，2016，33（6）:134-138.

［8］王輝，朱龍彪.基于粒子群遺傳算法的泊車系統(tǒng)路徑規(guī)劃研究［J］.工程設(shè)計學(xué)報，2016，23（2）:195-200.

An Improved Particle Swarm Optimization Algorithm

REN He-yu1，GUO Lei2，ZHAO Kai-xin3
（1.Henan Communication Vocational Technology College，Zhengzhou 450000，China；2.Henan Provincial Civil Affairs School,Zhengzhou 450002，China；3.Henan Institute of Technology,Xinxiang 453002，China）

In view of the basic particle swarm optimization algorithm exits the slow speed convergence,low efficiency,and is easy to fall into the local optimum.In order to better balance the global and local search capability,the shrinkage factor is introduced into the particle swarm optimization algorithm.The particle of the population not only learn from the best particle,but also learn from all the particles in the algorithm,the diversity of particles is increased,The experimental results show that the improved particle swarm optimization algorithm can improve convergence speed and efficiency,and avoid the generation of local optimal solution comparing with the basic ant colony algorithm.

particle swarm，global optimum，local optimum，learning rule

TP242

A

10.3969/j.issn.1002-0640.2017.08.027

1002-0640（2017）08-0120-03

2016-06-19修回日期：2016-08-14

國家自然科學(xué)基金（61174085）；河南省高等學(xué)校重點科研基金資助項目（16A520084）

任賀宇（1981- ），男，河南滑縣人，碩士。研究方向：人工智能、計算機(jī)網(wǎng)絡(luò)技術(shù)。