趙曉寒，張 豐，曹 琦，馮 佳

（綏化學(xué)院 電氣工程學(xué)院，黑龍江 綏化 152061）

0 引 言

根據(jù)標(biāo)準(zhǔn)PSO算法的迭代公式可知，產(chǎn)生早熟的原因是標(biāo)準(zhǔn)PSO算法只有向心力卻并沒(méi)有使粒子分離的排斥力。輪換步長(zhǎng)PSO算法在全體粒子上都加入了排斥力，即使將所有粒子人為的早熟于局部最優(yōu)點(diǎn)，粒子也會(huì)因?yàn)椴介L(zhǎng)的不同而分散開(kāi)。可見(jiàn)，引入斥力的輪換步長(zhǎng)PSO算法的全局搜索能力更強(qiáng)，抗早熟能力也更強(qiáng)[1]。

輪換步長(zhǎng)PSO算法同樣存在一些缺陷，如步長(zhǎng)方向隨機(jī)性問(wèn)題；輪換步長(zhǎng)PSO算法在步長(zhǎng)的方向上不具有隨機(jī)性。如果粒子的初始分布過(guò)于密集或者初始于同一個(gè)局部最優(yōu)點(diǎn)，在搜索的初期，粒子只是在解空間的某一局域進(jìn)行搜索，輪換步長(zhǎng)PSO算法不會(huì)像標(biāo)準(zhǔn)PSO算法收斂到零。它的迭代次數(shù)是人為設(shè)定的，若迭代次數(shù)設(shè)置過(guò)少，劣粒子可能還沒(méi)有對(duì)全局進(jìn)行詳細(xì)搜索，計(jì)算就已結(jié)束；若迭代次數(shù)設(shè)置過(guò)多，計(jì)算量及計(jì)算時(shí)間將會(huì)增加。若輪換步長(zhǎng)PSO算法能在步長(zhǎng)的方向上進(jìn)行改進(jìn)，使劣粒子跳出局部點(diǎn)去尋找全局最優(yōu)解時(shí)，能對(duì)新區(qū)域的各個(gè)方向進(jìn)行搜索，其尋優(yōu)速率將會(huì)大大增加，找到全局最優(yōu)解的概率也將提高。

煙花算法在粒子進(jìn)行爆炸時(shí)產(chǎn)生的火花是均勻分布的，其在方向的隨機(jī)性上近乎完美。若將輪換步長(zhǎng)PSO算法的劣粒子視為煙花粒子，在每次迭代時(shí)按照預(yù)先設(shè)定的爆炸強(qiáng)度、爆炸幅度進(jìn)行爆炸，而爆炸后的劣粒子在新的搜索空間產(chǎn)生均勻分布的火花，這些火花會(huì)對(duì)新空間詳細(xì)搜索，尋找更優(yōu)點(diǎn)。

1 輪換步長(zhǎng)PSO算法

1.1 輪換步長(zhǎng)PSO算法概述

輪換步長(zhǎng)PSO算法的步長(zhǎng)不是固定的而是按照函數(shù)值的優(yōu)劣來(lái)動(dòng)態(tài)分配步長(zhǎng)。最優(yōu)粒子分配最小步長(zhǎng)細(xì)致地尋找最優(yōu)解；最劣粒子分配最大步長(zhǎng)，以較大的步長(zhǎng)去尋找真優(yōu)解[2]。

1.2 輪換步長(zhǎng)PSO算法的工作原理

輪換步長(zhǎng)PSO算法的迭代公式為：

若f(xi)＞PibestF，則更新Pibest；

若有PibestF＞GbestF，則更新Gbest；

step0是系數(shù)，決定了尋優(yōu)的精度；a決定了步長(zhǎng)的寬度，范圍1.1～1.5；K代表粒子號(hào)；top( f(xi))為粒子按函數(shù)值從小到大的排序；Pibest為第i個(gè)粒子已走過(guò)的最優(yōu)解；第i個(gè)粒子的當(dāng)前解；Gbest為全局最優(yōu)解。

2 煙花算法

2.1 煙花算法概述

2010年，受煙花爆炸產(chǎn)生火花的啟發(fā)，北京大學(xué)譚營(yíng)教授通過(guò)模擬煙花在空中爆炸的這種行為，提出了一種新的群體智能算法——煙花算法[3]。煙花算法原理簡(jiǎn)單、易操作、空間搜索能力強(qiáng)，一經(jīng)提出就引起了學(xué)者的濃厚熱情。短短幾年間，對(duì)煙花算法的改進(jìn)算法層出不窮，如多目標(biāo)煙花算法、并行計(jì)算煙花算法和混合煙花算法等[4]。

2.2 煙花算法的工作原理

煙花算法來(lái)自于對(duì)煙花爆炸過(guò)程的模擬，其迭代過(guò)程如圖1所示。

圖1 迭代過(guò)程

爆炸算子：爆炸算子是煙花算法的核心，起關(guān)鍵性作用，包括爆炸強(qiáng)度（爆炸火花數(shù)量）、爆炸幅度（爆炸半徑）和位移操作[5]。

煙花在爆炸過(guò)程中會(huì)產(chǎn)生火花，此種現(xiàn)象可用數(shù)學(xué)公式模擬。

爆炸強(qiáng)度。產(chǎn)生火花的數(shù)量為：

Si為第i個(gè)煙花產(chǎn)生的火花個(gè)數(shù)；M為常數(shù)，用來(lái)限制產(chǎn)生的火花總數(shù)；f(xi)為個(gè)體xi的適應(yīng)度值；ε為一個(gè)極小的常數(shù)，用來(lái)避免出現(xiàn)分母為零的情況。

為了限制煙花爆炸產(chǎn)生火花的數(shù)量過(guò)多或過(guò)少，對(duì)每個(gè)煙花設(shè)定如下產(chǎn)生火花數(shù)量的限制公式[6]，即：

S^為第i個(gè)煙花產(chǎn)生的火花數(shù)量；Round(·)為四舍五入取整函數(shù)；a和b是給定的常數(shù)。

爆炸幅度。煙花爆炸幅度范圍的計(jì)算為：

Ai為第i個(gè)煙花的爆炸幅度范圍，即爆炸的火花將在這個(gè)范圍內(nèi)隨機(jī)產(chǎn)生位移，但不能超出這個(gè)范圍[7]；A^為一個(gè)常數(shù)，表示最大的爆炸幅度；Ymin為當(dāng)前種群中適應(yīng)值最好的個(gè)體的適應(yīng)度值；f(xi)和ε的意義同上。

位移操作。位移操作是對(duì)煙花的每一維進(jìn)行位移，即：

其中，rand(0,Ai)表示在幅度Ai內(nèi)生成的均勻隨機(jī)數(shù)。

3 改進(jìn)后的輪換步長(zhǎng)PSO算法

3.1 改進(jìn)后的輪換步長(zhǎng)PSO算法工作原理

輪換步長(zhǎng)PSO算法在標(biāo)準(zhǔn)粒子群算法的基礎(chǔ)上加入了斥力。改進(jìn)后的算法不但具有向心力，最主要是存在排斥力。正是由于這種排斥力的存在，在尋優(yōu)過(guò)程中總有劣粒子擺脫局部最優(yōu)解的束縛去尋找更優(yōu)解。輪換步長(zhǎng)PSO算法具有很好的抗早熟能力，但粒子在移動(dòng)過(guò)程中只是在某單一方向上移動(dòng)。通過(guò)VB仿真圖1可看出，粒子的尋優(yōu)軌跡只是在解空間的某一部分，即使有劣粒子擺脫局部區(qū)域?qū)ふ业叫聟^(qū)域，但劣粒子只是對(duì)新區(qū)域大概地進(jìn)行搜索，尋找到全局最優(yōu)解的概率較小。這就是輪換步長(zhǎng)PSO算法在運(yùn)動(dòng)方向上的缺陷。若在尋優(yōu)過(guò)程中劣粒子可以在每個(gè)維度的各個(gè)方向上尋找更優(yōu)解，找到全局最優(yōu)解的概率將大大增加，也能更有效地抑制早熟現(xiàn)象的產(chǎn)生。

煙花算法中粒子在迭代過(guò)程中每個(gè)粒子都會(huì)按照設(shè)定好的爆炸強(qiáng)度、爆炸幅度、位移操作進(jìn)行爆炸，爆炸產(chǎn)生的火花在爆炸范圍內(nèi)是均勻分布的，包含了粒子的所有方向。這種在方向上的隨機(jī)性正是輪換步長(zhǎng)PSO算法所需要的。本文將輪換步長(zhǎng)PSO算法的劣粒子看作煙花算子，在每次迭代過(guò)程中，劣粒子（適應(yīng)值最差的1/4粒子）按預(yù)先設(shè)定的爆炸強(qiáng)度、爆炸幅度進(jìn)行爆炸。為了防止粒子泛濫，降低計(jì)算量，采用精英策略（隨機(jī)策略）選擇適應(yīng)值最好的火花（精英）作為下一代粒子。改進(jìn)后的輪換步長(zhǎng)PSO算法的全局搜索能力更好，尋找真優(yōu)解的概率更大。

3.2 改進(jìn)后的輪換步長(zhǎng)PSO算法的迭代步驟

步驟0：初始化，設(shè)置參數(shù)，隨機(jī)在解空間設(shè)置N個(gè)粒子；

步驟1：計(jì)算每個(gè)粒子的適應(yīng)值，并對(duì)粒子的適應(yīng)值的優(yōu)劣進(jìn)行評(píng)價(jià)（按粒子適應(yīng)值的優(yōu)劣對(duì)粒子進(jìn)行排序）；

步驟2：找出群體的當(dāng)前全局最優(yōu)解；步驟3：根據(jù)優(yōu)劣度為粒子分配步長(zhǎng)；步驟4：根據(jù)煙花算法的爆炸公式，計(jì)算劣粒子產(chǎn)生的火花數(shù)和煙花的爆炸半徑；

步驟5：在劣粒子（適應(yīng)值最差的1/4粒子）的位置上引爆煙花；

步驟6：采用精英策略（隨機(jī)策略）選擇適應(yīng)值最低的粒子（精英）作為下一代粒子；

步驟7：更新粒子位置和計(jì)算新的函數(shù)值；步驟8：判斷是否結(jié)束。

4 實(shí)驗(yàn)

本文算法是在文獻(xiàn)[1]的基礎(chǔ)上進(jìn)行改進(jìn)。為了測(cè)試改進(jìn)后的輪換步長(zhǎng)PSO算法的有效性，本實(shí)驗(yàn)采用與文獻(xiàn)[1]相同的多維測(cè)試函數(shù)y=sin r/r，其中此函數(shù)的全局最優(yōu)解位于r=0處的圓上。為了體現(xiàn)改進(jìn)后的輪換步長(zhǎng)PSO算法的抗早熟能力，現(xiàn)將所有粒子人為初始于（10,10）處。改進(jìn)前和改進(jìn)后的測(cè)試圖分別如圖2、圖3所示，可以清晰看出，改進(jìn)后的輪換步長(zhǎng)PSO算法的粒子均勻分布在可行區(qū)域內(nèi)，驗(yàn)證了其在步長(zhǎng)方向上的改進(jìn)是有效的，改進(jìn)后的算法具有更好的全局尋優(yōu)能力。

圖2 輪換步長(zhǎng)PSO算法

圖3 改進(jìn)后輪換步長(zhǎng)PSO算法

5 結(jié) 語(yǔ)

由實(shí)驗(yàn)結(jié)果可知，改進(jìn)后的輪換步長(zhǎng)PSO算法在步長(zhǎng)方向上具有很好的隨機(jī)性，在整個(gè)搜索區(qū)域粒子均勻分布，具有更好的全局搜索能力，抗早熟的能力更強(qiáng)。

改進(jìn)后的輪換步長(zhǎng)PSO算法也同樣存在一些缺陷，如步長(zhǎng)的選擇問(wèn)題。步長(zhǎng)過(guò)大或者過(guò)小都會(huì)產(chǎn)生一些不良后果，因?yàn)榱Ｗ拥牟介L(zhǎng)始終不會(huì)像標(biāo)準(zhǔn)粒子群算法那樣收斂至零，這樣即使粒子找到真優(yōu)解，也會(huì)在真優(yōu)解附近震蕩。

參考文獻(xiàn)：

[1] 趙曉寒.輪換步長(zhǎng)PSO算法及SMVSC參數(shù)優(yōu)化[D].沈陽(yáng):沈陽(yáng)理工大學(xué),2015.ZHAO Xiao-han.Rotational Step Size PSO Algorithm and SMVSC Parameter Optimization[D].Shenyang:Shenyang University of Technology,2015.

[2] 黃志鋼,趙曉寒,孫泰.PSO的改進(jìn)——跳蚤算法[J].沈陽(yáng)理工大學(xué)學(xué)報(bào),2015(04):80-83.HUANG Zhi-gang,ZHAO Xiao-han,SUN Tai.Flea Algorithm Based on an Improved Particle Swarm Optimization[J].Journal of Shenyang Ligong University,2015(04):80-83.

[3] 尚亞菲,劉雪英,賈敏南.引入慣性權(quán)重的煙花算法[J].內(nèi)蒙古工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2016(03):168-177.SHANG Ya-fei,LIU Xue-ying,JIA Min-nan.Introducing Inertia Weight Fireworks Algorithm[J].Journal of Inner Mongolia University of Technology(Natural Science Edition),2016(03):168-177.

[4] 陳璇,樊永生,余紅英等.自適應(yīng)煙花算法在重型裝備裝載中的應(yīng)用[J].科學(xué)技術(shù)與工程,2016(25):296-300.CHEN Xuan,FAN Yong-sheng,YU Hong-ying,et al.Application of Adaptive Algorithm of Fireworks in the Heavy Equipment Loading[J].Science Technology and Engineering,2016(25):296-300.

[5] 曹陽(yáng)陽(yáng).綠色蜂窩網(wǎng)中基于煙花算法的無(wú)線資源分配技術(shù)研究[D].西安:西安電子科技大學(xué),2016.CAO Yang-yang.A Research of Radio Resource Allocation Based on Fireworks Algorithm in Green LTE Cellular Systems[D].Xi’an:Xidian University,2016.

[6] 王杰,萇群康,彭金柱.極限學(xué)習(xí)機(jī)優(yōu)化及其擬合性分析[J].鄭州大學(xué)學(xué)報(bào):工學(xué)版,2016(02):20-24.WANG Jie,CHANG Qun-kang,PENG Jin-zhu.The Optimization of the Extreme Learning Machine and Fitting Analysis[J].Journal of Zhengzhou University(Engineering Science),2016(02):20-24.

[7] 韓守飛,李席廣,拱長(zhǎng)青.基于模擬退火與高斯擾動(dòng)的煙花優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2017(05):257-262.HAN Shou-fei,LI Xi-guang,GONG Chang-qing.Fireworks Optimization Algorithm Based on Simulated Annealing and Gaussian Perturbations[J].Computer Science,2017(05):257-262.