趙偉 郭乙江

摘 ?要： 為了克服煙花算法容易早熟，提高其尋優(yōu)精度，提出一種基于搜索策略的煙花算法。首先，通過最小爆炸半徑檢測(cè)，得到種群適應(yīng)度值。其次，在煙花種群多次迭代過程中對(duì)當(dāng)前最佳煙花個(gè)體進(jìn)行動(dòng)態(tài)隨機(jī)搜索，增強(qiáng)對(duì)當(dāng)前階段最佳個(gè)體鄰域范圍內(nèi)的搜索。最后，根據(jù)當(dāng)前最佳個(gè)體之間的擁擠程度，存留10%的最佳個(gè)體，對(duì)剩余煙花個(gè)體采用佳點(diǎn)集策略進(jìn)行初始化操作，輔助種群個(gè)體逃離局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，所提算法相比同類煙花算法有效提高了求解精度，且收斂速度較快。

關(guān)鍵詞： 搜索策略; 煙花算法; 動(dòng)態(tài)隨機(jī)搜索; 佳點(diǎn)集策略; Benchmark函數(shù); 個(gè)體逃離

中圖分類號(hào)： TN911?34; TP18 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2020）02?0074?03

Research on fireworks algorithm based on search strategy

ZHAO Wei， GUO Yijiang

Abstract： A fireworks algorithm based on search strategy is proposed to overcome the premature explosion of the fireworks algorithm and improve its optimization accuracy. The fitness value of the population is obtained by detecting the minimum explosion radius. In the course of the multiple iterations of the fireworks population， the dynamic random search for the current best fireworks individuals is carried out to enhance the search within the neighborhood scope of the optimal individuals at the current stage. The 10% best fireworks individuals are retained according to the current crowdedness degree among them， and the rest is initialized by means of the good?point set strategy to assist the individuals to escape from the local optimum. The experimental results show that in comparison with similar fireworks algorithms， the proposed algorithm can more effectively improve the solution accuracy， and has faster convergence speed.

Keywords： search strategy; fireworks algorithm; dynamic random search; good point set strategy; Benchmark function;individual escape

0 ?引 ?言

煙花算法作為一種求解眾多優(yōu)化問題的智能優(yōu)化算法，近年來得到了快速發(fā)展，在圖像識(shí)別、安防、交通駕駛、社會(huì)行為預(yù)測(cè)等眾多領(lǐng)域得到廣泛應(yīng)用[1]。

通過引入歷史成功信息構(gòu)造學(xué)習(xí)因子，文獻(xiàn)[2]提出動(dòng)態(tài)搜索煙花算法。學(xué)習(xí)因子可使用搜索階段種群各代最佳煙花個(gè)體，使個(gè)體具備向種群內(nèi)部最佳搜索信息學(xué)習(xí)能力。該算法涉及的計(jì)算參數(shù)較少，求解速度較快。與傳統(tǒng)的智能優(yōu)化算法雷同，對(duì)高維函數(shù)的處理，在收斂速度以及優(yōu)化方面存在明顯不足。為了改善煙花算法的收斂能力，文獻(xiàn)[3]提出具有反向?qū)W習(xí)能力與記憶功能反饋的煙花算法。利用反向?qū)W習(xí)機(jī)制，構(gòu)造合理的種群規(guī)模，并保證煙花種群多樣性。文獻(xiàn)[4]針對(duì)煙花算法求解精度低的問題，提出具有灰色關(guān)聯(lián)算子的煙花算法。該算法在粒子群算法尋優(yōu)階段，采用灰色關(guān)聯(lián)算子為種群所有個(gè)體配備一個(gè)引導(dǎo)粒子，通過引導(dǎo)粒子對(duì)種群個(gè)體維度信息進(jìn)行動(dòng)態(tài)更新。該算法與原煙花算法相比，求解能力更佳。文獻(xiàn)[5]針對(duì)標(biāo)準(zhǔn)煙花算法粒子之間信息交流缺陷，提出差分進(jìn)化算法引導(dǎo)趨化算子的改進(jìn)煙花算法。結(jié)合差分進(jìn)化以及趨化算子的綜合優(yōu)勢(shì)搜索種群迭代過程中的最佳個(gè)體，根據(jù)最佳個(gè)體信息對(duì)煙花算法粒子維度信息進(jìn)行修正，加強(qiáng)粒子之間的信息交流。

本文提出基于搜索策略的煙花算法。在種群迭代過程中，采用動(dòng)態(tài)隨機(jī)搜索機(jī)制對(duì)種群內(nèi)部當(dāng)前階段的最佳煙花個(gè)體進(jìn)行動(dòng)態(tài)隨機(jī)搜索，增強(qiáng)最佳個(gè)體鄰近區(qū)域的搜索。同時(shí)為了保證種群多樣性，在后期引入佳點(diǎn)集技術(shù)，根據(jù)煙花種群當(dāng)前階段最佳個(gè)體聚集程度，對(duì)剩余個(gè)體在解空間內(nèi)進(jìn)行初始化操作。實(shí)驗(yàn)結(jié)果表明，該算法相比同類煙花算法有效提高了求解精度，且收斂速度較快。

1 ?煙花算法

1.1 ?最小爆炸半徑檢測(cè)

設(shè)定煙花群體規(guī)模為[N]，維數(shù)為[d]，種群中第[i]個(gè)煙花爆炸生成的火花個(gè)數(shù)為[si]，爆炸半徑為[Ai]，公式如下：

[si=M·fmax-f（xi）+θi=1N（fmax-f（xi））+θ] ? （1）

[Ai=A·f（xi）-fmin+θi=1N（f（xi）-fmin）+θ] （2）

式中：[M]表示可調(diào)爆炸生成的火花個(gè)數(shù)的參數(shù);[A]表示可調(diào)爆炸半徑范圍的參數(shù);[f（xi）]表示煙花個(gè)體[xi]的種群適應(yīng)度值;[fmax=max（f（xi））]表示種群中最劣煙花相應(yīng)的適應(yīng)度值[6];[fmin=min（f（xi））]表示種群中最優(yōu)煙花相應(yīng)的適應(yīng)度值;[θ]為常數(shù)。

1.2 ?煙花的爆炸方式

根據(jù)上述所得爆炸火花數(shù)量和爆炸半徑，煙花個(gè)體[i]爆炸生成[Si]個(gè)火花，爆炸過程隨機(jī)選取[k]個(gè)維度，對(duì)隨機(jī)選擇的維度[k∈{1，2，…，d}]，利用式（2）進(jìn)行位置偏移構(gòu)成新的爆炸火花[7]。

[Δxki=xki+rand（0，Ai）] ? ? ? ? ? ? （3）

式中，[rand（0，Ai）]為爆炸范圍[Ai]內(nèi)的隨機(jī)數(shù)。

設(shè)定煙花個(gè)體[i]，[t]時(shí)段的當(dāng)前位置為[Xit=（xi1t，xi2t，…，xint）]，此時(shí)種群全局最優(yōu)位置可描述為[X?t=（x?1t，x?2t，…，x?nt）]。設(shè)煙花個(gè)體[i]按照以下方式爆炸，則：

[Xt+1i=Xti+rand（0，Ai）] ? ? ? ? ? ?（4）

式中，[Ai]為煙花個(gè)體[i]的爆炸影響范圍，即爆炸產(chǎn)生的火花在此區(qū)間內(nèi)隨機(jī)發(fā)生位置變化[8?9]，但無法超出此區(qū)間。

2 ?基于搜索策略的煙花算法

種群迭代過程中所生成的最佳爆炸點(diǎn)，含有相比其他煙花個(gè)體更為優(yōu)秀的進(jìn)化信息，更能引導(dǎo)煙花算法的收斂方向。因此，加強(qiáng)種群最佳個(gè)體鄰近區(qū)域的搜索，有助于快速搜索到最佳解[10]，提高種群求解精度。故在煙花算法中引入動(dòng)態(tài)搜索機(jī)制，種群迭代后針對(duì)當(dāng)代最佳個(gè)體進(jìn)行動(dòng)態(tài)隨機(jī)搜索。

2.1 ?動(dòng)態(tài)隨機(jī)搜索策略

考慮到煙花算法當(dāng)前最佳個(gè)體[Xg（t）]鄰近范圍內(nèi)可能存在更為優(yōu)異的煙花個(gè)體，故種群迭代后針對(duì)種群煙花個(gè)體[Xc：Xb=Xc+Xr]，進(jìn)行一次動(dòng)態(tài)隨機(jī)搜索，觀測(cè)是否存在更為優(yōu)異的煙花個(gè)體。具體步驟如下：

1） 種群參數(shù)初始化。設(shè)定煙花算法的最大迭代次數(shù)為[Max]，滿足[Xc=Xb];

2） 設(shè)定煙花算法的初始搜索步長[stepk];

3） 煙花算法的所有維度[m]，進(jìn)行如下步驟。

① 在區(qū)間[[-stepk，stepk]]內(nèi)生成隨機(jī)向量[Xr];

② 構(gòu)造新的煙花個(gè)體[Xn：Xn=Xc+Xr]，[X′n：X′n=Xc-Xr];

③ 將[Xn]分別與[Xc]和[Xb]進(jìn)行優(yōu)劣對(duì)比，假設(shè)[Xn]比[Xc]和[Xb]更佳，則替換掉[Xc]和[Xb];

④ 調(diào)整搜索步長[stepk];

⑤ 循環(huán)迭代步驟①～步驟④，[k]次，即完成對(duì)算法不同空間維度的搜索;

⑥ 算法迭代是否滿足結(jié)束條件，假設(shè)滿足則輸出結(jié)果，煙花算法結(jié)束，相反則返回步驟②。

2.2 ?佳點(diǎn)集技術(shù)

設(shè)定[s]維空間內(nèi)包含某種形式為[Pn（k）=（{r（n）1·k}，}，…，{r（n）s·k}）]的立方體[Vs]。假設(shè)偏差[φ（n）=C（r，ε）n-1+ε]存在，[ε]表示常數(shù)，[C（r，ε）]表示與[r]，[ε]相關(guān)的參數(shù)，[Pn（k）]表示最佳點(diǎn)集合。

煙花種群內(nèi)每個(gè)煙花相應(yīng)的適應(yīng)度值應(yīng)當(dāng)與種群內(nèi)部的平均適應(yīng)度值相接近。為了提高種群多樣性，在煙花算法中加入一個(gè)參數(shù)[α=-j=1mfi-faf2]來描述煙花算法局部最優(yōu)解的獲取是否受限，[fj]表示煙花個(gè)體當(dāng)前階段的適應(yīng)度值，[fa]表示煙花種群當(dāng)前階段的平均適應(yīng)度值，該值越小，說明煙花個(gè)體聚集程度越高。設(shè)定一閾值[λ]，當(dāng)滿足[α≤λ]時(shí)，說明煙花算法種群多樣性降低，此時(shí)使用佳點(diǎn)集技術(shù)進(jìn)行初始化操作。

3 ?測(cè)試結(jié)果與分析

為了驗(yàn)證本文提出的基于搜索策略的煙花算法的求解能力，在硬件環(huán)境為Matlab 7.9（R2009b），Intel[?]CoreTMDuo CPU 2.1 GHz，Windows 7 Flagship下與其他兩種算法進(jìn)行對(duì)比。

設(shè)定不同算法種群規(guī)模一致，為25，迭代次數(shù)均為500次，對(duì)比不同算法求解結(jié)果的均值及方差。表1給出文獻(xiàn)[4]算法、文獻(xiàn)[5]算法以及本文算法求解結(jié)果的均值及方差，測(cè)試所用Benchmark函數(shù)如下：

[f（x）=i=130x2i， ?xi≤100] ? ? ? ?（5）

[f（x）=i=111ai-x1（b2i+bix2）b2i+bix3+x42] ? ?（6）

[f（x）=4x21-2.1x41+x613+x1x2-4x22+4x42] ? （7）

[f（x）=-i=14ciexp-i=13aij（xi-pij）2] （8）

分析表1可知，本文算法對(duì)于所有Benchmark函數(shù)的求解精度明顯高于文獻(xiàn)[4]算法和文獻(xiàn)[5]算法。當(dāng)文獻(xiàn)[4]算法、文獻(xiàn)[5]算法取得最優(yōu)解的同時(shí)本文算法也能夠獲取到最優(yōu)解;在部分Benchmark函數(shù)無法獲取最優(yōu)解時(shí)，本文算法同樣取得了最優(yōu)解;當(dāng)其他兩種算法無法獲取最優(yōu)解時(shí)，本文算法所得結(jié)果更逼近于最優(yōu)解。通過求解結(jié)果可知，本文算法方差更小，說明本文提出的基于搜索策略的煙花算法運(yùn)行過程中更為穩(wěn)定、可靠。表2給出這三種算法對(duì)于Benchmark函數(shù)最優(yōu)解獲取的成功次數(shù)以及獲取最優(yōu)解收斂代數(shù)對(duì)比結(jié)果。

分析表2可知，本文算法搜索到Benchmark函數(shù)最優(yōu)解的成功次數(shù)明顯高于文獻(xiàn)[4]算法以及文獻(xiàn)[5]算法。這說明本文通過引入動(dòng)態(tài)隨機(jī)搜索策略，能夠使煙花算法跳出局部最優(yōu)，有效提高了算法對(duì)Benchmark函數(shù)進(jìn)行求解的精度。同時(shí)迭代次數(shù)相比其他兩種算法更少，說明在算法后將佳點(diǎn)集技術(shù)的引入是非常有效的。選取兩個(gè)Benchmark函數(shù)，對(duì)比函數(shù)f1，f5在仿真過程中最優(yōu)值的變化曲線，如圖1、圖2所示。

從圖1和圖2給出變化曲線可看出，本文算法的收斂速度相比文獻(xiàn)[4]算法和文獻(xiàn)[5]算法更快一些。

4 ?結(jié) ?語

本文提出基于搜索策略的煙花算法。該算法采用動(dòng)態(tài)隨機(jī)搜索機(jī)制加強(qiáng)對(duì)最佳爆炸點(diǎn)鄰近區(qū)域的搜索，有效提高算法求解精度。為了避免基礎(chǔ)煙花算法在后期陷入局部最優(yōu)，采用佳點(diǎn)集技術(shù)重新設(shè)定部分爆炸點(diǎn)，以保證煙花算法的種群多樣性。實(shí)驗(yàn)結(jié)果表明，該算法相比同類煙花算法有效提高了求解精度，值得推廣。

參考文獻(xiàn)

[1] 杜振鑫.采用多精英指導(dǎo)的煙花算法[J].蘭州理工大學(xué)學(xué)報(bào)，2017，43（5）：100?104.

[2] 李席廣，韓守飛，劉曉靜，等.基于反向?qū)W習(xí)與動(dòng)態(tài)記憶反饋的煙花算法[J].計(jì)算機(jī)工程，2017，43（12）：203?210.

[3] 包曉曉，葉春明，黃霞.煙花算法求解JSP問題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（3）：247?252.

[4] 汪菊琴，史熒中，彭力，等.帶有灰色關(guān)聯(lián)算子的煙花算法[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（20）：150?156.

[5] 劉茜，毛力，楊弘.差分進(jìn)化引導(dǎo)趨化算子的煙花優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（3）：145?151.

[6] 謝承旺，許雷，汪慎文，等.一種增強(qiáng)型多目標(biāo)煙花爆炸優(yōu)化算法[J].電子學(xué)報(bào)，2017，45（10）：2323?2331.

[7] 薛俊杰，王瑛，孟祥飛，等.二進(jìn)制反向?qū)W習(xí)煙花算法求解多維背包問題[J].系統(tǒng)工程與電子技術(shù)，2017，39（2）：451?458.

[8] 韓守飛，李席廣，拱長青.基于模擬退火與高斯擾動(dòng)的煙花優(yōu)化算法[J].計(jì)算機(jī)科學(xué)，2017，44（5）：257?262.

[9] 王曉楠，巨永鋒，高婷.緊急狀態(tài)下候選通信網(wǎng)絡(luò)信息實(shí)時(shí)生成仿真[J].計(jì)算機(jī)仿真，2017，34（12）：165?168.

[10] 謝承旺，許雷，汪慎文，等.一種增強(qiáng)型多目標(biāo)煙花爆炸優(yōu)化算法[J].電子學(xué)報(bào)，2017，45（10）：2323?2331.

作者簡(jiǎn)介：趙 ?偉（1985—），女，河北邢臺(tái)人，碩士，講師，研究方向?yàn)橛?jì)算機(jī)應(yīng)用、應(yīng)用數(shù)學(xué)、課程與教學(xué)論。

郭乙江（1984—），男，陜西扶風(fēng)人，碩士，講師，研究方向?yàn)閿?shù)據(jù)挖掘、自然算法、人工智能。