基于搜索策略的煙花算法研究

趙偉 郭乙江

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

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

中圖分類號： TN911?34; TP18 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 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ā)展，在圖像識別、安防、交通駕駛、社會行為預(yù)測等眾多領(lǐng)域得到廣泛應(yīng)用[1]。

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

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

1 ?煙花算法

1.1 ?最小爆炸半徑檢測

設(shè)定煙花群體規(guī)模為[N]，維數(shù)為[d]，種群中第[i]個煙花爆炸生成的火花個數(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)爆炸生成的火花個數(shù)的參數(shù);[A]表示可調(diào)爆炸半徑范圍的參數(shù);[f（xi）]表示煙花個體[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ù)量和爆炸半徑，煙花個體[i]爆炸生成[Si]個火花，爆炸過程隨機選取[k]個維度，對隨機選擇的維度[k∈{1，2，…，d}]，利用式（2）進行位置偏移構(gòu)成新的爆炸火花[7]。

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

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

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

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

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

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

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

2.1 ?動態(tài)隨機搜索策略

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

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

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

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

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

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

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

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

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

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

2.2 ?佳點集技術(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）]表示最佳點集合。

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

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

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

設(shè)定不同算法種群規(guī)模一致，為25，迭代次數(shù)均為500次，對比不同算法求解結(jié)果的均值及方差。表1給出文獻[4]算法、文獻[5]算法以及本文算法求解結(jié)果的均值及方差，測試所用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可知，本文算法對于所有Benchmark函數(shù)的求解精度明顯高于文獻[4]算法和文獻[5]算法。當文獻[4]算法、文獻[5]算法取得最優(yōu)解的同時本文算法也能夠獲取到最優(yōu)解;在部分Benchmark函數(shù)無法獲取最優(yōu)解時，本文算法同樣取得了最優(yōu)解;當其他兩種算法無法獲取最優(yōu)解時，本文算法所得結(jié)果更逼近于最優(yōu)解。通過求解結(jié)果可知，本文算法方差更小，說明本文提出的基于搜索策略的煙花算法運行過程中更為穩(wěn)定、可靠。表2給出這三種算法對于Benchmark函數(shù)最優(yōu)解獲取的成功次數(shù)以及獲取最優(yōu)解收斂代數(shù)對比結(jié)果。

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

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

4 ?結(jié) ?語

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

參考文獻

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

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

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

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

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

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

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

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

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

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

作者簡介：趙 ?偉（1985—），女，河北邢臺人，碩士，講師，研究方向為計算機應(yīng)用、應(yīng)用數(shù)學、課程與教學論。

郭乙江（1984—），男，陜西扶風人，碩士，講師，研究方向為數(shù)據(jù)挖掘、自然算法、人工智能。