基于μ律爆炸算子和信息交流映射策略的煙花改進(jìn)算法

滕志軍, 李 哲, 王幸幸, 皇甫澤南, 申博冉

(1.東北電力大學(xué) 現(xiàn)代電力系統(tǒng)仿真控制與綠色電能新技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室， 吉林 吉林 132012； 2.東北電力大學(xué) 電氣工程學(xué)院, 吉林 吉林 132012; 3.吉林大學(xué) 數(shù)學(xué)學(xué)院, 吉林 長(zhǎng)春 130022)

0 引言

近年來，針對(duì)復(fù)雜的優(yōu)化問題，群智能算法憑借其簡(jiǎn)單、靈活、尋優(yōu)速度快的優(yōu)點(diǎn)成為解決這類問題的強(qiáng)有力工具[1].目前，群智能算法有粒子群算法[2,3]、遺傳算法[4]、灰狼算法[5]、螢火蟲算法[6]、煙花算法[7]等.煙花算法(Fireworks algorithm，縮寫為FWA)由北大教授譚營(yíng)于2010年受煙花在夜空中爆炸產(chǎn)生火花的自然現(xiàn)象啟發(fā)而提出，其優(yōu)越的特性受到不同領(lǐng)域科研工作者的關(guān)注，對(duì)FWA進(jìn)行改進(jìn)提高算法性能也成為了研究的主要方向.

針對(duì)原始煙花算法的不足和缺陷，Gong等[8]提出了具有自適應(yīng)參數(shù)的動(dòng)態(tài)搜索煙花算法(dynFWA)，通過引入自適應(yīng)系數(shù)調(diào)整爆炸半徑放縮系數(shù)和新的選擇策略加快算法收斂，增強(qiáng)了算法的求解性能.Zhao等[9]提出了一種核心煙花信息引導(dǎo)的自適應(yīng)煙花算法(AFWA)，該算法通過CF煙花位置信息來擴(kuò)展最佳煙花的爆炸幅度和更新方向，在該方向上產(chǎn)生更多的爆炸火花來增強(qiáng)搜索能力，加快算法收斂.Zheng等[10]提出了一種增強(qiáng)型煙花算法(EFWA)通過通過引入新的最小半徑幅度檢查策略和精英選擇策略，減少了算法運(yùn)行時(shí)間.Krouska A等[11]在增強(qiáng)型煙花算法(EFWA)的基礎(chǔ)上對(duì)最小半徑策略進(jìn)行修改提出新的爆炸方案，引入信息交換策略，平衡了煙花算法的局部與全局搜索能力.Luo等[12]將混沌映射策略與自適應(yīng)煙花算法相結(jié)合，保證了煙花算法局部搜索的精度，滿足了全局搜索的多樣性.

此外，Yu等[13]受各種爆炸方式和形狀的啟發(fā)提出了基于多層爆炸策略的煙花算法，使用目標(biāo)函數(shù)來評(píng)估前一層爆炸產(chǎn)生的火花個(gè)體以此來確定下一層的爆炸形狀和火花分配，提高了爆炸性能.Cheng等[14]提出一種混合混沌機(jī)制與levy變異的改進(jìn)煙花算法，利用混沌機(jī)制使初始種群分布均勻，引入levy變異算子增強(qiáng)煙花的全局搜索能力.朱啟兵等[15]結(jié)合引力搜索算法的思想提出了一種帶有引力搜索算子的煙花算法，增強(qiáng)了優(yōu)質(zhì)火花與其它火花之間的信息交互，增加了煙花種群的多樣性，提高了算法尋優(yōu)性能.Yue等[16]通過引入自適應(yīng)平衡系數(shù)將灰狼算法的全局尋優(yōu)與煙花算法強(qiáng)大的局部搜索相結(jié)合提出對(duì)多維復(fù)雜空間進(jìn)行優(yōu)化.Zhang等[17]提出了蜂群-煙花混合算法來求解多目標(biāo)優(yōu)化問題，首先使用蜂群算法(ABC)進(jìn)行全局搜索，當(dāng)尋找到更好蜜源時(shí)，引入動(dòng)態(tài)煙花算法(dynFWA)快速執(zhí)行局部搜索增強(qiáng)算法的性能.

為進(jìn)一步提升煙花算法后期的尋優(yōu)速度、平衡局部和全局的尋優(yōu)能力，本文提出一種基于μ律爆炸算子和信息交流映射策略的煙花算法(Firework algorithm based onμ-law explosion operator and information exchange mapping strategy，縮寫為μFWA).該算法采用適應(yīng)度等級(jí)代替適應(yīng)度并將非均勻量化的μ率特性曲線函數(shù)作為一個(gè)轉(zhuǎn)移函數(shù)構(gòu)建新的煙花爆炸公式，改善了后期最優(yōu)煙花與其它煙花差異不明顯造成的收斂速度減慢的問題.引入縮放因子動(dòng)態(tài)調(diào)整變異范圍和隨著迭代次數(shù)動(dòng)態(tài)調(diào)整μ率特性曲線的形狀參數(shù)μ值，均衡局部和全局的搜索能力.最后提出了基于信息交流的映射策略，充分考慮了超出邊界火花的位置信息，更有針對(duì)性的對(duì)超出邊界的火花進(jìn)行映射.

1 煙花算法簡(jiǎn)介

1.1 爆炸算子

爆炸算子是煙花算法核心，煙花爆炸時(shí)根據(jù)適應(yīng)度值自適應(yīng)的控制爆炸的范圍和爆炸火花數(shù)目，爆炸強(qiáng)度公式如下：

(1)

式(1)中：Si表示第i個(gè)煙花產(chǎn)生的爆炸火花數(shù)目，M是火花總數(shù)目，f(Xi)表示當(dāng)前煙花Xi的適應(yīng)度值，Ymax表示當(dāng)前種群中適應(yīng)度值最差的個(gè)體的適應(yīng)度值，ε是極小數(shù).

(2)

式(2)中：Si表示第i個(gè)煙花產(chǎn)生的火花數(shù);a，b為常數(shù);round()表示四舍五入取整.保證通過爆炸算子計(jì)算得到爆炸火花數(shù)目為整數(shù).

(3)

式(3)中：Ai表示第i個(gè)煙花的爆炸范圍;A是煙花爆炸總幅度;f(Xi)表示當(dāng)前煙花Xi的適應(yīng)度值;Ymin表示當(dāng)前種群中適應(yīng)度值最優(yōu)個(gè)體的適應(yīng)度值;ε是極小數(shù).

1.2 變異算子

(4)

g=N(1,1)

(5)

式(5)中：g是服從均值為1方差為1的高斯變異.

1.3 映射策略

煙花算法在執(zhí)行爆炸時(shí)，難以避免會(huì)產(chǎn)生超出邊界區(qū)域之外的火花，然而這些火花會(huì)降低算法的尋優(yōu)能力，因此采用映射策略將經(jīng)爆炸導(dǎo)致的越界火花重新映射回可行域內(nèi).

(6)

1.4 選擇策略

FWA采用基于距離的輪盤賭選擇策略，公式如下：

(7)

式(7)中：‖xl-xj‖ 表示火花xl，xj之間的歐氏距離;R(xl)為第l個(gè)火花到所有火花的距離.

(8)

式(8)中：p(xl)為爆炸火花xl被選擇為下一代煙花的概率，由式(8)知，據(jù)其它爆炸火花距離更遠(yuǎn)的火花更容易成為下一代煙花，保證了種群的多樣性.

2 改進(jìn)煙花算法

2.1 新的爆炸算子

煙花算法的爆炸算子產(chǎn)生的爆炸火花數(shù)目在不同的情況下是不穩(wěn)定的.適應(yīng)度值隨著目標(biāo)函數(shù)的不同和搜索空間中位置的不同而劇烈波動(dòng).爆炸火花的數(shù)量沒有規(guī)律，相應(yīng)地，最佳煙花產(chǎn)生的爆炸火花的數(shù)量無法控制.最佳煙花的適應(yīng)度如果很小時(shí)，可能會(huì)占用幾乎所有資源，相反劣質(zhì)煙花爆炸產(chǎn)生的火花數(shù)目會(huì)很少，導(dǎo)致算法易陷入局部最優(yōu).當(dāng)算法進(jìn)入迭代后期時(shí)，由于所有煙花都集中在最優(yōu)值附近進(jìn)行探索，各個(gè)煙花的適應(yīng)度值差別不大導(dǎo)致最優(yōu)煙花分配的爆炸火花數(shù)目和爆炸范圍與其它普通煙花區(qū)別很小，體現(xiàn)不出最優(yōu)煙花優(yōu)勢(shì)，使算法在后期收斂速度減緩.因此，本文用適應(yīng)度等級(jí)代替適應(yīng)度值來計(jì)算煙花的爆炸火花數(shù)目和爆炸幅度，引入非均勻量化的μ率特性曲線函數(shù)作為傳遞函數(shù)Ta(n)將煙花序號(hào)映射為函數(shù)值構(gòu)建新的煙花強(qiáng)度算子.適應(yīng)度值轉(zhuǎn)化適應(yīng)度等級(jí)量化值的傳遞函數(shù)Ta(n)計(jì)算如下：

(9)

式(9)中：n是煙花序號(hào)，μ是傳遞函數(shù)形狀的參數(shù).由圖1知，傳遞函數(shù)隨著μ的減小會(huì)變得更加均勻.μ隨迭代次數(shù)的改變能動(dòng)態(tài)的調(diào)整煙花爆炸火花的數(shù)目和幅度，且隨著迭代次數(shù)增加而減小，適應(yīng)度較差的煙花隨著迭代次數(shù)的增加火花越來越少，爆炸半徑越來越大，適應(yīng)度較優(yōu)的煙花隨著迭代次數(shù)的增加火花越來越多，爆炸半徑越來越小.讓全局搜索在早期完成，加強(qiáng)算法后期的局部搜索，更好的平衡了算法的局部和全局尋優(yōu)能力.

圖1 μ率曲線

爆炸火花數(shù)目和范圍計(jì)算公式如下：

(10)

(11)

式(10)、(11)中：N是煙花總數(shù)，n是煙花序號(hào)，Sn是適應(yīng)度排名為n的煙花的爆炸火花數(shù)目，An是適應(yīng)度排名為n的煙花的爆炸范圍.基于μ律爆炸算子的偽代碼如下：

2.2 改進(jìn)的變異算子

煙花算法中的變異算子可以增強(qiáng)種群的多樣性，使算法跳出局部最優(yōu)而找到全局最優(yōu)解.但傳統(tǒng)煙花算法采用的高斯變異對(duì)于原點(diǎn)附近的變異火花很難通過變異跳出原點(diǎn)附近的位置，隨機(jī)變異又缺乏與最優(yōu)火花個(gè)體之間的信息交流，因此本文提出一種新的變異策略，引入縮放因子來動(dòng)態(tài)的控制變異范圍，算法前期增大變異范圍，增加了找到最優(yōu)值的可能性，后期減小變異范圍，與爆炸火花一起進(jìn)行局部搜索，一定程度上提高了算法的收斂能力.改進(jìn)變異算子的公式為：

(12)

(13)

Algorithm 2:變異火花產(chǎn)生方式Input:最優(yōu)煙花位置xkbest,火花總數(shù)M,縮放因子F.Output:變異火花位置1.for l=1 to variationNum2.i=ceil(rand*M);k=round(rand*dim) //隨機(jī)選擇第k維第i個(gè)火花作為變異火花3.計(jì)算縮放因子F4.根據(jù)公式(12)產(chǎn)生變異火花5.if xki,b超出邊界;Then6.根據(jù)映射策略將其映射到可行域內(nèi)7. end if8.end for

2.3 基于信息交流的映射策略

煙花算法的映射策略主要是將利用爆炸算子和變異算子產(chǎn)生的超出可行域的火花映射回可行域內(nèi)，保證種群的完整性.煙花算法的映射策略主要分為取余映射和隨機(jī)映射，取余映射易將超出可行域的火花映射回原點(diǎn)附近，浪費(fèi)大量的搜索機(jī)會(huì)，而提出的均勻隨機(jī)映射雖然避免了取余映射的缺陷，但是忽略了生成火花的位置信息，具有較大的隨機(jī)性.因此本文提出了一種基于信息交流的映射策略，首先通過c來決定進(jìn)行局部映射還是全局映射.

(14)

c為一條前期驟減后期緩慢變化的曲線，保證算法局部和全局映射的平衡性.如果c≥0.5，利用式(15)將超出可行域的火花映射到爆炸煙花或者變異火花的附近.如果c<0.5，利用式(16)將超出可行域的火花映射到最優(yōu)火花附近.

(15)

(16)

本文提出的映射規(guī)則既充分考慮了爆炸火花的位置信息，將其映射到爆炸煙花與邊界的區(qū)間內(nèi)，比隨機(jī)映射增強(qiáng)了位置的針對(duì)性，在一定程度上保留了超出可行域火花的位置特征.同時(shí)通過一定概率的全局最優(yōu)映射，加快了算法的搜索效率和收斂速度，比傳統(tǒng)的取余映射增加了種群的多樣性.基于信息交流生成爆炸火花的偽代碼如下：

Algorithm 3:映射策略Input:最優(yōu)煙花k維的位置信息xkbest,爆炸火花xki,煙花k維的位置信息xkm,當(dāng)前迭代次數(shù)evaTimeOutput:映射后的火花在k維的位置xki,p '1.if xki>UB或xki

2.4 算法流程

本文提出改進(jìn)之后的煙花算法的具體實(shí)現(xiàn)步驟如下：

Step1設(shè)置煙花種群的數(shù)目，維數(shù).設(shè)置爆炸火花數(shù)目M和爆炸幅度A；

Step2在搜索區(qū)間內(nèi)初始化產(chǎn)生N個(gè)煙花，并計(jì)算每個(gè)煙花的適應(yīng)度值；

Step3根據(jù)適應(yīng)度值對(duì)煙花進(jìn)行排序，利用式(9)將煙花的序號(hào)值轉(zhuǎn)換為函數(shù)值，然后根據(jù)式(10)、(11)分別計(jì)算每個(gè)煙花進(jìn)行爆炸時(shí)產(chǎn)生的火花數(shù)目和爆炸幅度；

Step4產(chǎn)生爆炸火花，將超出可行域的爆炸火花通過式(15)或式(16)映射回可行域內(nèi)；

Step5隨機(jī)選取某個(gè)火花通過式(12)產(chǎn)生variationNum個(gè)變異火花，并將超出可行域的變異火花通過式(15)或式(16)映射回可行域內(nèi)；

Step6計(jì)算爆炸火花和變異火花的適應(yīng)度值，然后通過精英選擇策略選擇N個(gè)煙花做為下一代煙花；

Step7判斷evaTime是否達(dá)到evaTmax值，如果達(dá)到則輸出最優(yōu)解和最佳適應(yīng)度值，否則返回Step3繼續(xù)執(zhí)行.

3 仿真分析

為驗(yàn)證本文所提算法的有效性，本文選擇12個(gè)國(guó)際通用的基準(zhǔn)測(cè)試函數(shù)(基準(zhǔn)測(cè)試函數(shù)的具體信息如表1所示，實(shí)驗(yàn)時(shí)測(cè)試函數(shù)維數(shù)設(shè)為20維)進(jìn)行仿真實(shí)驗(yàn)，F(xiàn)1～F6為單峰測(cè)試函數(shù)，含有一個(gè)全局最優(yōu)解，以測(cè)試算法的開發(fā)能力.F7～F12為多峰測(cè)試函數(shù)，其含有多個(gè)局部極值，測(cè)試算法的全局探索能力.通過與FWA、EFWA、dynFWA、AFWA等改進(jìn)煙花算法進(jìn)行對(duì)比來分析本文算法的性能.為了保證尋優(yōu)結(jié)果的穩(wěn)定性，五種算法在每個(gè)函數(shù)上獨(dú)立運(yùn)行30次.

表1 12個(gè)基準(zhǔn)測(cè)試函數(shù)

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

通過MATLAB對(duì)上述的基準(zhǔn)函數(shù)進(jìn)行仿真對(duì)比，實(shí)驗(yàn)初始數(shù)據(jù)為煙花種群數(shù)目為5，爆炸火花數(shù)目為50，初始爆炸幅度為40，變異火花數(shù)目為5，迭代次數(shù)為105，形狀參數(shù)μini=0.1，μfin=500.

3.2 仿真分析

3.2.1 尋優(yōu)結(jié)果對(duì)比

由于基本煙花算法在爆炸過程中，爆炸火花數(shù)目和爆炸幅度僅由適應(yīng)度值得到，導(dǎo)致后期最優(yōu)煙花與普通煙花區(qū)別不明顯，造成尋優(yōu)速度減緩，所以本文將適應(yīng)度值進(jìn)行排序，引入非均勻量化中的μ率特性曲線將序號(hào)值映射為函數(shù)值，重新構(gòu)建爆炸算子.通過表2數(shù)據(jù)可知，本文所提算法在12個(gè)測(cè)試函數(shù)上都能表現(xiàn)出比較優(yōu)秀的性能，相對(duì)于其它4種算法，通過μFWA得到的平均適應(yīng)度值在7個(gè)函數(shù)上獲得領(lǐng)先，特別是在F1、F2、F4、F5優(yōu)勢(shì)更加明顯，反映了μFWA收斂精度更高.此外，μFWA算法的標(biāo)準(zhǔn)差相較于其它4種算法更小，說明該算法的穩(wěn)定性較好.

表2 本文算法與改進(jìn)型煙花算法平均值、標(biāo)準(zhǔn)差比較

3.2.2 收斂曲線對(duì)比

為比較5種算法的求解性能，本文對(duì)5種算法在12個(gè)測(cè)試函數(shù)上的收斂曲線進(jìn)行對(duì)比，其結(jié)果如圖2和圖3所示.

圖2所示的是5種算法在單峰基準(zhǔn)函數(shù)(F1-F6)的性能對(duì)比.可以看出，在搜索初期本文μFWA算法收斂速度略慢于其它對(duì)比算法，主要原因是本文采用適應(yīng)度值等級(jí)替代適應(yīng)度值進(jìn)行爆炸火花數(shù)目和爆炸幅度的計(jì)算，隨機(jī)產(chǎn)生的煙花差異性比較大，基于適應(yīng)度值的爆炸算子性能優(yōu)于基于適應(yīng)度值等級(jí)的爆炸算子，隨著算法運(yùn)行一段時(shí)間后，各個(gè)煙花集中在較小范圍進(jìn)行尋優(yōu)，基于適應(yīng)度值等級(jí)的爆炸算子體現(xiàn)出了更大的優(yōu)勢(shì)，從而收斂速度明顯優(yōu)于其它算法.

(a)F1

(b)F2

(c)F3

(d)F4

(e)F5

(f)F6圖2 FWA、EFWA、dynFWA、AFWA和μFWA在單峰函數(shù)上的收斂曲線

(a)F7

(b)F8

(c)F9

(d)F10

(e)F11

(f)F12圖3 FWA、EFWA、dynFWA、AFWA和μFWA在多峰函數(shù)上的收斂曲線

圖3所示的是5種算法在多峰基準(zhǔn)函數(shù)上的收斂曲線.μFWA算法通過動(dòng)態(tài)改變傳遞函數(shù)μ的值，增強(qiáng)各等級(jí)煙花的差異性，使得各等級(jí)煙花的爆炸數(shù)目和幅度隨迭代時(shí)間動(dòng)態(tài)調(diào)整，優(yōu)秀煙花小范圍大量搜索，劣質(zhì)煙花大范圍少量搜索，更好的平衡了算法的局部開采和全局探索能力.從圖3可以看出，本文所提算法出現(xiàn)停滯的次數(shù)和時(shí)間明顯少于其它對(duì)比算法，反映了本文算法跳出局部最優(yōu)的能力強(qiáng)，不易陷入局部最優(yōu)，能夠較快的找到全局最優(yōu)解.

4 結(jié)論

為了進(jìn)一步提高算法的尋優(yōu)性能，本文提出一種改進(jìn)的煙花算法，將適應(yīng)度值等級(jí)替代適應(yīng)度值構(gòu)建新的爆炸算子，通過動(dòng)態(tài)調(diào)整傳遞函數(shù)μ值，更好的平衡了算法的局部及全局搜索能力.引入縮放因子F，在前期增強(qiáng)種群多樣性，后期可加強(qiáng)算法的收斂能力.同時(shí)基于信息交流的映射策略，既考慮了最優(yōu)火花的位置信息，又通過一定概率的全局映射，提升映射火花的多樣性，提高了火花的搜索效率，進(jìn)而提高了算法的收斂速度.為驗(yàn)證本文提出算法的有效性，對(duì)12個(gè)測(cè)試函數(shù)進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明，μFWA比其它對(duì)比算法能更快的搜索到全局最優(yōu)解，且穩(wěn)定性好.下一步將把本文算法應(yīng)用于WSN節(jié)點(diǎn)部署優(yōu)化問題以進(jìn)一步驗(yàn)證算法的有效性.