帶有自適應差分進化的混合煙花算法

汪菊琴，史熒中

（無錫職業技術學院物聯網技術學院，江蘇無錫 214121）

0 引言

近年來，元啟發式優化算法在工程優化領域得到越來越多的應用，主要是其概念簡單，容易實現，能夠在可接受的花費（指計算時間和空間）內給出問題的一個可行解。已廣泛應用于各領域的元啟發式算法有遺傳算法［1］、粒子群算法［2］、蟻群算法［3］、人工蜂群算法［4］。

煙花算法是Tan 等［5］受到煙花爆炸過程中炸點擴散的規律性啟發而提出的一種元啟發式算法。自煙花算法提出之后，學界對煙花算法的研究逐步深入，并針對原始煙花算法的不足，提出了大量的改進方法，并據此提出了各種改進算法。如Gao 等［6］利用文化進化機制更新煙花粒子的位置進而提出文化煙花算法；Wang 等［7］提出一種增強型煙花算法，用于提高能源管理策略的性能；Zhang 等［8］提出3 種通過加強煙花粒子間的信息交流機制以改善煙花算法的策略，該策略在數值實驗和列車調度問題中表現出良好的性能；周迅等［9］提出解決開放式選址路徑問題的離散煙花算法。這些改進算法在一定程度上增強了煙花算法的尋優能力，提高了算法的搜索效率，但在處理一些多峰函數時，仍有陷入局部最優的問題。單一的智能算法在處理優化問題時或多或少都會存在一些問題，許多學者還將不同的算法加入到煙花算法中，其中差分算法特別受學者青睞。如朱曉東等［10］在煙花算法爆炸產生新粒子之后利用差分算法進一步優化模型；Zheng 等［11］采用差分算法中變異、交叉綜合變異方式增強粒子間信息交流及導向策略的適用性，并將改進后的算法成功應用于模擬集成電路設計。然而，正如文獻［12］所述，差分算法有兩個非常敏感的參數，即差分收縮因子F 和交叉率CR（Crossover Rate），在已經提出的混合算法中都沒有對其進行很好的處理。

為了解決上述問題，本文提出了帶有自適應差分進化的混合煙花算法（Adaptive Differential Evolution Fireworks Algorithm，ADEFA）。首先動態增加利用差分算子處理煙花粒子的個數，再調整變異操作中變異向量的生成機制，且對于差分算子中的兩個參數F 和CR，會根據已有的成功經驗利用高斯分布進行動態調整。這樣，ADEFA 對差分算子中的參數不會那么敏感，可以充分發揮變異和交叉機制的優勢以提高煙花算法性能，避免陷入局部最優，提高算法全局搜索能力。

1 煙花算法

煙花算法是通過模擬煙花爆炸過程而產生的優化算法，對于一個d維優化問題，假設初始時有N個煙花粒子，=1,2,…,N表示問題的一個解，X(t)=[X1,X2,…,XN]為第t次迭代的煙花粒子集合。煙花算法的尋優過程跟其他智能算法尋優過程類似。首先，初始化N個煙花粒子，初始化的過程是隨機產生的，然后通過爆炸算子和高斯變異算子生成新的火花粒子，對于新的火花粒子做邊界映射檢查，對于超出可行域邊界的粒子通過映射規則將其映射到可行域內。最后，通過選擇策略選取進入下一次迭代的煙花粒子，在選擇時保證最優粒子進入下一次迭代。具體步驟如下：

步驟1：初始化N 個煙花粒子，記為Xi，其中i=1,2,…,N，并計算其適應度值f(Xi)。

步驟2：對于每一個煙花粒子Xi，通過爆炸算子產生si個火花粒子，每一個火花粒子記為Yi,j，則Yi,j可表示為：

其中，Ai表示煙花粒子Xi的爆炸半徑，且有：

為控制爆炸半徑的常量，fmin為當前迭代中適應度值的最小值，ε為一個極小值，避免出現零的情況。每個煙花粒子Xi產生的火花個數si表示為：

其中，m為控制火花數量的常數，fmax為當前迭代中適應度值的最大值，ε為一個極小值，避免出現零的情況。為了控制總體火花的數量，使適應度值好的煙花粒子不會產生過多的粒子，適應度值差的煙花粒子不會產生過少的粒子，通常對si作如下限制：

m為控制火花數量的常數，a和b也為常數，round（）為四舍五入取整函數。

步驟3：為了增加種群的多樣性，選取一部分煙花粒子通過高斯變異算子產生新的火花粒子，假設選擇h個粒子（1≤h≤N），對于煙花粒子Xk（1≤k≤h）經過高斯變異之后記為Ck，則有：

Xk表示在煙花粒子集合中隨機選擇的粒子，Gaussian(1,1)表示服從均值為1、方差為1 的高斯分布隨機數。

步驟4：對于爆炸算子和高斯變異算子處理后得到的新的火花粒子進行邊界映射檢查，對于超出可行域的粒子，作如下映射處理：

其中，表示第i個煙花粒子在第j維的值，和表示第j維的上界和下界。

步驟5：從煙花粒子、爆炸算子產生的火花粒子和高斯變異算子產生的火花粒子中選取N個粒子作為下一次迭代的初始煙花粒子。粒子種群中最優粒子會被保留下來，剩余N-1 個粒子采用輪盤賭的方式進行選擇。通過這種方式不斷迭代更新，直到達到條件迭代后終止，產生最優解。

2 自適應差分進化的混合煙花算法

根據NFL（No Free Lunch）定理［13］，在不考慮具體問題的情況下，沒有任何一個算法比另一個算法更優，甚至不會比胡亂猜測更好。即對于某一個算法，如果在某類問題上表現很好，則其對剩余其他類型的問題表現就會很差。基于該事實可以得到，對于A 和B 兩種算法，通過某種形式組合成一個混合算法，可能會克服原始算法的缺陷，進而得到一個更優秀的算法。

對于標準煙花算法，主要通過煙花粒子爆炸產生新的火花粒子進行粒子更新。對于單峰函數，可能會取得較優的結果，而對于多峰函數，則有較大的可能陷入局部最優。差分算法通過自身變異和交叉機制，可以使得解保持多樣性，容易跳出局部最優。同時，差分算法還可以通過收縮因子F控制其局部搜索能力。本文結合差分算法，在煙花算法中引入自適應差分算子，提出自適應差分進化的混合煙花算法。在標準煙花算法中選取一定數量的煙花粒子，利用自適應差分算子進行粒子更新。同時，為了克服差分算法中參數的敏感性，采用高斯分布動態調整和更新參數的值。這樣可以充分發揮變異和交叉機制的優勢以提高煙花算法性能，避免陷入局部最優，提高算法的全局搜索能力。

2.1 差分算子

差分算法（DE）是Storn 等［14］于1995 年提出，與其他演化算法一樣，DE 是一種模擬生物進化的隨機模型，通過不斷迭代，使得那些適應環境的個體被保存下來。DE 主要用來求解連續變量的優化問題，算法主要包括變異和交叉操作。

2.1.1 變異

在差分算法中，從種群中隨機選出3 個個體xr1、xr2和xr3，令第g 次迭代個體xi生成的變異向量為vi，則有：

其中，r1、r2、r3?[1,SN]，且r1≠r2 ≠r3≠i，SN表示種群個數，F是收縮因子，主要用來控制算法的局部搜索能力。

2.1.2 交叉

在變異之后，差分算法會進行交叉操作，每個變異個體vi與目標個體xi進行交叉產生新的個體ui=(ui1,ui2,…,uiD)，則有：

其中，i=1,2,…,SN，j=1,2,…,D，D表示維度，rand 表示（0，1）之間的隨機數，jrand為區間［1，D］中的一個整數，CR為交叉率，且CR∈[0,1]。

2.2 自適應差分算子

差分算法中主要有兩個參數，即收縮因子F和交叉率CR。F用來控制算法的局部搜索能力和全局搜索能力。當F值較大時，可以保持種群的多樣性，算法具有較強的全局搜索能力，當F值較小時，有利于算法的局部搜索。CR用來控制算法的收斂速率，當CR值較小時，算法所需評價次數較多，算法收斂速率慢，但精度較高，當CR值較大時，算法所需評價次數少、收斂速率快、精度較低。因此，F和CR對算法的性能和收斂速率有較大影響。如果直接在煙花算法中引入差分算子，不對F和CR作任何調整，算法容易陷入局部最優，對煙花算法性能提升會比較有限。特別對于多峰適應度函數，當算法陷入局部最優時，甚至會出現不提升或降低原有算法性能的情況。為了提高煙花算法的收斂精度和收斂速率，本文采用自適應差分算子。

首先，對原差分算法進行改進，即在變異操作中，選擇當前迭代中的最優解、次優解和最差解生成變異向量為vi，以此提升算子的變異效率。最優解、次優解、最差解通過函數的適應度值確定，適應度值最好的為最優解，適應度值次好的為次優解，適應度值最差的為最差解。因此，對式（7）作一些調整，具體為：

其中，xs1、xs2和xs3為當前迭代中選擇的最優解、次優解和最差解，sig是符號函數，用來控制差分向量的方向。

其次，由概率論中的中心極限定理可知，若影響某一數量指標的隨機因素很多，且每個因素都有一定的作用，則這個指標一般服從正態分布，即高斯分布，因此本文利用高斯分布設計一種自適應機制來調整F和CR，從而提升差分算子的性能，具體為：

當Fi>1 或者Fi≤0 時，Fi取［0，1］之間的隨機數。CRi也采用相同的方法進行處理。在文獻［15］中，Fu和CRu的初始值設定為0.5，Fδ和CRδ的初始值設定為0.3，本文與文獻［15］保持相同的設定。

在每一次迭代中，當一個新解比原來的解有所提高時，記錄下F 和CR 的值，分別存儲在SF和SCR中，通過SF和SCR更新Fu、Fδ、CRu和CRδ的值，具體為：

式（14）—式（17）中,c1和c2為常數，c1和c2可以動態調整F 和CR 的值，一般通過經驗或者實驗獲取。可以看出，Fδ和CRδ的值被限定在［0.1，0.3］區間。

2.3 ADEFA 算法流程

在算法迭代后期，FA 算法可能會出現爆炸粒子的來源過于單一甚至來源于同一粒子的情況。ADEFA 算法為了避免這種情況發生，會對這些適應度值較好的粒子采用自適應差分算子進行處理。首先，從FA 算法中的煙花粒子、爆炸算子產生的火花粒子和高斯變異算子產生的火花粒子中選取k個較優粒子作為更新集，則有k=ceil(t×W)，其中t∈(0,1)，W為煙花粒子、爆炸算子產生的火花粒子和高斯變異算子產生的火花粒子總數。然后利用自適應差分算子更新這k個較優粒子，從而增加解的多樣性，使算法跳出局部最優。具體算法步驟為：

步驟1：設置算法參數iter_max、N、、m、a、b、h、t，其中iter_max為最大迭代次數，N為初始煙花粒子個數，為爆炸半徑常量，m、a、b為給定的常數，用來控制生成煙花粒子個數，h為高斯變異粒子個數，t為控制自適應差分算子更新粒子個數的參數。在n維搜索空間內初始化N個煙花粒子。

步驟2：利用式（1）—式（5）產生火花粒子和高斯變異火花粒子，對于超出可行域的粒子采用式（6）將其映射到可行域內。

步驟3：將煙花粒子和步驟2 產生的火花粒子根據適應度值進行排序，選取k個較優的粒子組成較優粒子更新集合S。

步驟4：利用式（12）和式（13）計算得到F和CR，利用式（9）和式（8）更新集合S中的粒子，得到自適應差分火花粒子，對超出可行域的粒子采用式（6）將其映射到可行域內。

步驟5：將所有煙花粒子、爆炸火花粒子、高斯變異火花粒子、自適應差分火花粒子按照適應度值進行排序，選取前N個較優粒子作為下一次迭代的煙花粒子。

步驟6：判斷是否達到迭代停止條件，如果達到，則停止迭代，輸出最優值，如果沒有，則返回步驟2。

2.4 算法收斂性分析

文獻［16］的研究結果證明了隨機優化算法以概率1 收斂于全局最優解的條件，主要結論如下：

假設1 若f(D(z,ξ) ≤fz)，并且如果ξ∈S，則有：f(D(z,ξ) ≤fξ)，其中f為目標函數，D為產生問題解的函數，z為S中尋找的一個點，其能使函數f的值最小化或者至少能夠生成一個可接受的下確界，ξ為從概率空間(Rn,B,uk)產生的隨機向量，S為Rn的子集，表示問題的約束空間。uk為B上的概率變量，B為子集的σ域。

假設2S的任意Borel 子集A，若其測度v(A) >0，則有：，其中，v(A)>0 為子集A的n維閉 包，uk(A)為由測度uk產生A的概率。

定理1 設f為一可測函數，S為Rn的一可測子集，為隨機算法產生的解序列，則當滿足假設1 和假設2 時，有：，其中Rε為全局最優點集合。

即對一個隨機優化算法，只要能夠滿足假設1 與假設2，就可以保證以概率1 收斂于全局最優解。

下面進行ADEFA 算法的全局收斂性證明。

引理1 ADEFA 算法滿足假設1。

證明 在ADEFA 算法中，函數D可以描述為：

其中，xg,t為t次迭代時當前粒子的最優解，pg,t為t次迭代時種群的最優解。因為ADEFA 算法利用種群最優資源檔案池保留種群最優解，即采用適應度值非遞增的精英保留策略，因此算法滿足假設1。

引理2 ADEFA 算法滿足假設2。

證明 設規模為N的煙花粒子樣本空間的并必須包含S，即。其中，Mi,t為第t代粒子i的樣本空間的支撐集。

對標準的FA 算法，文獻［17］證明存在整數t'，使得當t>t'，存在集合A?S，使得。即=1，因此不滿足假設2。

ADEFA 算法是在FA 算法的基礎上，運用自適應差分算子產生新的粒子。因此，對于正常進化的粒子，設其支撐集為α；利用自適應差分算子產生的粒子，設其支撐集的并集為β。

由于自適應差分算子的隨機性，必然存在整數t1，使得當t>t1時，β?S。因此對于ADEFA 算法，存在整數t2，使得當t>t2時，。

定義S的任意Borel 子集A=Mi,t，則有v(A)>0，ut(A)=，因此ADEFA 算法滿足假設2。

結論1 ADEFA 算法是全局收斂算法。

3 實驗分析

為了測試ADEFA 算法的性能，本文使用12 個多維度可擴展基準測試函數，詳見文獻［18］。實驗在Matlab2019a下實現，運行環境為：主頻2.60 GHz，內存8.00 GB，Win?dows 10 操作系統。

3.1 實驗參數

將本文所提ADEFA 算法與FA 算法及改進的帶有引力搜索算子的煙花算法［18］（FAGSO）、帶有信息交換功能的煙花算法［19］（IFWA）進行對比。各算法的參數設置如表1 所示，其中h為高斯變異粒子個數，m、a和b為控制煙花粒子個數的常數，為爆炸半徑常量。表1 中FAGSO 和IFWA 參數分別來自文獻［18］和文獻［19］，ADEFA 中的c1和c2參數來自文獻［20］。

為使對比結果更公平，實驗中煙花粒子個數和最大迭代次數都保持一致。4 個算法的煙花粒子個數都設置為10個，最大迭代次數設置為300 000 次。不同的初始化值會產生不同的優化結果，為了減小這種影響，所有的算法都獨立運行15 次。

Table 1 Parameter setting表1 參數設置

3.2 實驗結果分析

3.2.1 解的質量分析

不同算法在各測試函數上的實驗結果如表2 和表3 所示，其中表2 表示函數維數等于30 的情況，表3 表示函數維數為50 的情況。表中Mean 和Std 分別表示均值和適應度值方差。為了更直觀地看出差別，4 個算法中最好的結果用粗體標出。

從表2 可以看出，對于30 維的基準測試函數，ADEFA除在f9和f10上沒有取得最優值外，在其他測試函數上都取得了最優值，而且ADEFA 在6 個測試函數（f1-f3，f5，f7，f11）上取得了全局最優值，在其他幾個函數（f4，f6，f8，f12）雖然沒有取得全局最優值，但也非常接近，相比其他幾個函數，已經極大提高了解的質量。

傳統的煙花算法中，由于其爆炸粒子產生機制的缺陷，在算法迭代后期很容易陷入局部最優，自適應差分算子利用其交叉變異機制，在算法的迭代中增加了粒子信息的多樣性，使其跳出了局部最優，因此ADEFA 算法在單峰和多峰函數上都能取得較優的結果。ADEFA 在對解進行更新時，動態增加利用差分算子處理煙花粒子的個數。同時，調整變異操作中變異向量的生成機制，且對于差分算子中的兩個參數F和CR，會根據已有的成功經驗利用高斯分布進行動態調整。這樣，ADEFA 對差分算子中的參數不會那么敏感，可以充分發揮變異和交叉機制的優勢提高煙花算法的性能，避免陷入局部最優，提高算法的全局搜索能力。因此，ADEFA 算法無論在前期的收斂速度還是在后期的求精能力都比其他幾種算法表現要好。ADEFA、FA、FAGSO 和IFWA 算法在部分基準測試函數上的收斂曲線如圖1—圖4 所示，更直觀地驗證了本文的推論。

Table 2 Average optimal value and standard deviation of four algorithms on the benchmark functions（n=30）表2 4 種算法對測試函數的平均最優值及標準差（n=30）

Table 3 Average optimal value and standard deviation of four algorithms on the benchmark functions（n=50）表3 4 種算法對測試函數的平均最優值及標準差（n=50）

Fig.1 Convergence of Sphere function圖1 Sphere 函數的收斂

Fig.2 Convergence of Rotated Rastrigin function圖2 Rotated Rastrigin 函數的收斂

Fig.3 Convergence of Quadric function圖3 Quadric 函數的收斂

3.2.2 維數變化分析

表3 表示在50 維基準測試函數上各算法的測試結果。可以看到，隨著維度的增加，ADEFA 算法的尋優精度有所下降，但差別不是特別大，其他算法尋優精度下降明顯，證明ADEFA 算法具有較強的穩定性。

3.3 參數t 的分析

ADEFA 算法中引入了一個新的參數t，主要用來控制自適應差分算子處理煙花粒子的個數。為了確定t 的值，本文選取部分函數（f3、f4、f6、f8）進行測試，t 的值設定為0.1、0.2、0.3、0.4、0.5、0.8、0.9、1，其余參數不變。實驗結果如表4 所示。

Fig.4 Convergence of Rotated Ackley function圖4 Rotated Ackley 函數的收斂

由表4 可見，t 設置為0.4 時，算法性能達到最優，當t<0.4 時，算法性能隨著t 的增加而提高，當t>0.4 時，算法性能隨著t 的增加而降低。原因分析如下：當t 較小時，自適應差分算子處理的粒子個數很少，對結果的影響有限，因此隨著t 值的增加，算法的性能提高；當t 值較大時，較多的粒子都得到了處理，包含那些效果很差的煙花粒子，這些粒子處理后可能會進入下一次迭代，影響算法的收斂性能，因此當t 值較大時，算法性能隨著t 的增大而降低。

Table 4 Experimental results of different t表4 不同t 的實驗結果

4 結語

本文提出了一種改進型的煙花算法（ADEFA），該算法在標準煙花算法中選取一定數量的煙花粒子，利用自適應差分算子進行粒子更新，即調整變異操作中變異向量的生成機制。同時，為了克服差分算法中參數的敏感性，采用高斯分布動態調整和更新參數的值，充分發揮變異和交叉機制的優勢提高煙花算法性能，避免了陷入局部最優，提高了算法的全局搜索能力。實驗結果表明，本文所提算法具有較高的收斂性能。在未來工作中，可以考慮將更有效的差分算子加入到煙花算法中，并且將ADEFA 用于更復雜的優化問題處理和實際應用。