基于組合變異的平衡灰狼優(yōu)化算法

戈陽 胡創(chuàng)業(yè)

摘? 要：針對狼群算法在迭代過程中逐漸失去多樣性及分布性的問題，提出一種基于組合變異的平衡灰狼優(yōu)化算法BGWO。通過融入metropolis準則的等溫過程，有效加快算法的收斂速度。通過引入轉(zhuǎn)換概率組合兩種變異策略對alpha狼進行變異，來控制種群聚散的特征，使算法具備跳出局部極值的能力。最后，將所提算法BGWO與EOGWO、EGWO、CGWO在IEEE CEC2013基準函數(shù)集上相比，所提算法的求解效率顯著提升。實驗結(jié)果表明，所提算法具有良好的收斂性，算法收斂精度更高，尋優(yōu)能力更強。

關鍵詞：群智能;灰狼優(yōu)化;模擬退火;組合變異;metropolis準則;等溫過程

中圖分類號：TP301.6? ? ? ? ?文獻標識碼：A? 文章編號：2096-4706（2021）18-0106-05

Abstract： Aiming at the problem that the wolf swarm algorithm gradually loses its diversity and distribution in the iterative process， a balanced gray wolf optimization algorithm based on combinatorial variation （BGWO） is proposed. By incorporating the isothermal process of metropolis criterion， the convergence speed of the algorithm is effectively accelerated. Through introducing transformation probability to combine two mutation strategies for alpha volf mutation， so as to control the characteristics of population aggregation and dispersion， making the algorithm has the ability to jump out of local extremum. Finally， the proposed algorithm BGWO is compared with EOGWO， EGWO and CGWO in IEEE CEC2013 benchmark function set. The efficiency of the proposed algorithm is significantly improved. Experimental results show that the proposed algorithm has good convergence， higher convergence accuracy and stronger optimization ability.

Keywords： swarm intelligence; gray wolf? optimization; simulated annealing; combinatorial variation; metropolis criterion; isothermal process

0? 引? 言

灰狼優(yōu)化算法（Grey Wolf Optimizer，GWO）是通過模擬自然界中灰狼群的社會等級和捕獵行為來實現(xiàn)搜索的新型群智能優(yōu)化算法，該算法由Mirjalili等人于2014年第一次提出。因其卓越的搜索性能，近幾年越來越吸引到研究者的關注。目前，GWO算法已被應用于解決經(jīng)濟調(diào)度、飛行器的控制設計、參數(shù)估計等非常廣泛的實際問題。

為了改進GWO算法易陷入局部極值的問題，由于SA算法的Metropolis準則可以以一定的概率接受劣質(zhì)解，因此通過引入metropolis準則，可以使融合后算法具有跳出局部極值的能力。在算法迭代的過程中，種群的聚集、分散趨勢在發(fā)生變化，為了進一步提升算法的求解性能，如何平衡算法探索（即分散）和開發(fā)（即聚集）的關系是關鍵。因此，如果通過控制種群的這種聚集、分散的變化特點來達到更好地為尋找全局最優(yōu)解服務，那么對提升算法的性能提供可能。

根據(jù)上述分析，提出了基于組合變異平衡灰狼優(yōu)化算法BGWO。該算法在GWO算法的基礎上混合模擬退火，應用組合變異策略，即通過引入轉(zhuǎn)換概率w來組合聚集和發(fā)散兩種策略，來控制種群的聚集、分散的變化特點來進一步提升算法性能。實驗結(jié)果表明，該算法在IEEE CEC2013函數(shù)集與EOGWO、EGWO、CGWO，所提算法性能顯著提升。

1? 基于組合變異的平衡灰狼優(yōu)化算法

為了解決灰狼優(yōu)化算法存在的問題，在灰狼優(yōu)化算法的基礎上融入模擬退火操作，即按照metropolis接受準則進行等溫過程和降溫過程。通過引入轉(zhuǎn)換概率w來組合兩種變異策略，即發(fā)散變異、聚集變異，來控制種群聚散的特征。

1.1? 組合變異策略

組合變異策略包括一種發(fā)散策略，用于全局探索，另一種是聚集策略，用于局部開發(fā)。通過組合兩種變異算子，在適應性轉(zhuǎn)換概率w的指導下，改變兩種變異算子的執(zhí)行。轉(zhuǎn)換概率w是基于當前迭代次數(shù)可以適應性調(diào)節(jié)兩種變異算子的轉(zhuǎn)換概率。組合變異偽代碼如以下所示：

一般地，在搜索開始時應以較大概率進行全局探索，即每個個體根據(jù)發(fā)散變異算子，比如rand/2/bin計算出一個相應的變異個體。隨著迭代的進行，轉(zhuǎn)換概率w隨之變化，搜索逐漸轉(zhuǎn)向局部開發(fā)算子，如current-to-best/1。在搜索的收尾階段，種群已經(jīng)從全局范圍聚焦到在當前的區(qū)域中，應已經(jīng)大致找到可能出現(xiàn)最優(yōu)解的區(qū)域。因此，在收尾階段應對該區(qū)域進行局部開發(fā)，從而期望在當前最優(yōu)解附近發(fā)現(xiàn)全局最優(yōu)解。

1.2? 適應性轉(zhuǎn)換概率w

組合變異策略使用適應性轉(zhuǎn)換概率w進行轉(zhuǎn)換，來決定執(zhí)行哪個變異算子。w是在[0，1]范圍內(nèi)變化的概率，w根據(jù)當前迭代的次數(shù)與迭代的總次數(shù)來決定，基本形式如公式1所示：

其中，G為當前迭代次數(shù)，Gmax為最大迭代次數(shù)，該式表明w隨著迭代的進行，在[0，1]范圍內(nèi)線性變化。在應用時w在迭代的初期會比較小，但種群在初期應全局搜索。因此當概率滿足1-w時進行發(fā)散變異操作;隨著迭代的進行，w逐漸變大，此時應該進行聚集變異。根據(jù)基本形式提出公式2的變化形式：

其中，G、Gmax與上式相同，參數(shù)freq為公式2的周期控制參數(shù)，freq∈（0，+∞），用來控制w的周期變化。該式是周期函數(shù)，意味著w以一定的規(guī)律變化，變化周期為π2·freq/Gmax。

如圖1所示，當freq為0時，隨著迭代的進行，轉(zhuǎn)換概率w始終為0，即組合變異始終只進行某一種聚集變異，算法退化為GWO算法。當freq為0.5時，w從0以sin型增長到1，整個搜索過程，種群的聚集趨勢簡單地經(jīng)歷一次轉(zhuǎn)變。當freq為1時，w經(jīng)歷了一個完整周期。反映到搜索策略上是經(jīng)歷了兩次轉(zhuǎn)變，即初始時全局搜索，隨著迭代進行到四分之一時翻轉(zhuǎn)，轉(zhuǎn)而進行局部搜索，到四分之三時再翻轉(zhuǎn)，進行全局發(fā)散搜索。當freq為1.5、2…時以此類推。因此，通過freq可以有效地控制種群的聚散特點。

BGWO算法流程如圖2所示。

步驟1：初始化種群。隨機初始化種群，計算種群每個個體適應度值，根據(jù)公式10計算初始溫度t0，設置迭代次數(shù)gen=1;

步驟2：迭代開始。根據(jù)公式9計算轉(zhuǎn)換概率w;

步驟3：等溫過程開始。應用組合變異策略，根據(jù)轉(zhuǎn)換概率w來決定使用發(fā)散算子公式2或者聚集算子公式3;

步驟4：metropolis準則。對變異后的新狀態(tài)xnew應用metropolis準則，來判斷是否接受新狀態(tài);

步驟5：判斷等溫過程是否結(jié)束。如果沒有結(jié)束。轉(zhuǎn)向步驟3;如果結(jié)束，轉(zhuǎn)向步驟6;

步驟6：對種群進行交叉操作;

步驟7：對種群進行選擇操作;

步驟8：溫度衰減t=k×t，記錄當前種群最優(yōu)適應度個體xbest;

步驟9：判斷是否迭代結(jié)束。如果沒有，轉(zhuǎn)向步驟2;如果結(jié)束，轉(zhuǎn)向步驟10;

步驟10：算法結(jié)束，輸出當前最優(yōu)適應度個體xbest。

2? 實驗結(jié)果及分析

2.1? 基準測試函數(shù)

為了評估BGWO算法的性能，將使用IEEE CEC2013作為基準函數(shù)集。根據(jù)基準函數(shù)的特點，可以被分為3類，即No.1—5為單峰函數(shù)，No.6—20為多峰函數(shù)，No.21—28為組合函數(shù)。實驗中將選擇最具代表性的15個函數(shù)（即No.1—10，No.21—25），編號為F1—F15，進行實驗。值得一提的是，該函數(shù)集已統(tǒng)一所有函數(shù)的搜索范圍，均為[-100，100]。

2.2? 參數(shù)設置和性能指標

當融合不同算法時會引入新的參數(shù)，增加算法對初始值依賴。比如引入模擬退火操作時，會引入溫度衰減系數(shù)K，馬氏鏈長度L。由于組合變異策略，又引入了參數(shù)freq。在沒有特殊說明的情況下，BGWO的F設為0.2，BGWO算法其他的參數(shù)，均設置為文獻[8，9]中經(jīng)過實驗后的最優(yōu)值，即種群大小NP設為30，維度D設為30，馬氏鏈長度L設為20，溫度衰減系數(shù)K設為0.98，CR為0.1，最大迭代次數(shù)為600進行實驗。實驗中選用Mean、Std兩個對比指標，其中Mean為算法的適應度誤差的平均最優(yōu)適應度值，以客觀衡量算法的性能水平;Std為適應度誤差的標準差值，以衡量算法的魯棒性。適應度誤差，由實際求解最優(yōu)適應度值f（xbest）與理論最優(yōu)適應度值f（x*）的差值表示。同時，Wilcoxon秩和檢驗（顯著水平5%）被用于比較算法之間性能的差異。用“+”“-”“=”，分別表示被比較算法優(yōu)于、劣于、等于所提BGWO算法。

2.3? 與其他算法的性能對比

為了進一步驗證所提算法的性能，BGWO與EOGWO、EGWO和CGWO，進行性能比較。這些最先進的算法不只是性能卓越，并且與所提改進算法在某些方面具有相似性，使對比更具參考價值。實驗將以適應度誤差平均值Mean及其標準差Std作為算法性能評價指標。根據(jù)上述實驗結(jié)論，設置BGWO參數(shù)值F=0.2，CR=0.1，freq=0.5，其他參數(shù)不再贅述。最后，實驗以30維為例，結(jié)果整理在表3，最好的結(jié)果已用粗體標出。

從表3中可以明顯地看出，所提算法BGWO的性能顯著優(yōu)于其他四個算法。當函數(shù)為單峰函數(shù)時，除了F2、F4外，所提算法均為最優(yōu);在解決多峰函數(shù)時，所提算法性能一般，只有F8、F10上優(yōu)于其他算法，F(xiàn)6為EGWO最優(yōu)，F(xiàn)7、F9則EOGWO最優(yōu);對于組合函數(shù)，所提算法的優(yōu)越性明顯。在F11、F13、F14、F15函數(shù)上，所提算法均最優(yōu)于其他算法，只有F12函數(shù)，EOGWO求解結(jié)果最優(yōu)。經(jīng)過分析，BGWO算法由于引入組合變異策略，通過種群的聚散特征靈活地平衡了開發(fā)和探索過程，因此該算法更適合解決存在復雜的局部極值的問題，比同樣是算法融合的CGWO性能更高。由于等溫過程使所提算法比其他參數(shù)調(diào)整的EOGWO求解精度更高。EOGWO由于沒有過多的改進，只進行簡單的自適應參數(shù)策略，具有良好的時間復雜度，因此在求解簡單在單峰函數(shù)上表現(xiàn)良好。

為了更直觀地觀察BGWO算法的收斂特性，選擇F1、F3、F11、F18、F21和F23共六個函數(shù)，繪制了BGWO與其他對比算法在D=30時的適應度誤差收斂曲線。

從圖3適應度誤差收斂圖中可以看出，BGWO在F1、F3、F11、F18函數(shù)上收斂速度和收斂精度顯著優(yōu)于對比算法。在單峰函數(shù)F3和在組合函數(shù)F15上，BGWO較EOGWO有些許劣勢。通過曲線圖也能看出隨著問題復雜程度的增大，各算法之間的差距在逐漸增大。通過之前的分析，BGWO算法更擅長求解復雜的多局部極值的問題，但在F23函數(shù)上，EOGWO逐漸以明顯的優(yōu)勢超過其他所有算法。針對該函數(shù)，是未來需要進一步解決的問題。

3? 結(jié)? 論

針對灰狼優(yōu)化算法易陷入局部極值，求解效率低的問題，提出基于組合變異的模擬退火混合灰狼優(yōu)化算法BGWO。實驗中，使用IEEE CEC2013函數(shù)集中單峰、多峰和組合這三類函數(shù)進行測試，在與算法BGWO與EOGWO、EGWO、CGWO的性能比較時，所提算法BGWO均顯著優(yōu)于對比算法，更適合于求解復雜的多局部極值的問題。通過觀察適應度誤差收斂曲線，所提算法收斂速度、收斂精度均明顯優(yōu)于對比算法，但F15函數(shù)上所提算法的效果略差。下一步將應用BGWO求解高維問題，并進一步將研究成果應用于實際工程問題。

參考文獻：

[1] STORN R，PRICE K. Differential Evolution—A Simple and Efficient Heuristic for global Optimization over Continuous Spaces [J].Journal of Global Optimization，1997，11：341-359.

[2] 黃戈文，蔡延光，戚遠航，等.自適應遺傳灰狼優(yōu)化算法求解帶容量約束的車輛路徑問題 [J].電子學報，2019，47（12）：2602-2610.

[3] 晏福，徐建中，李奉書.混沌灰狼優(yōu)化算法訓練多層感知器 [J].電子與信息學報，2019，41（4）：872-879.

[4] 胡小平，曹敬.改進灰狼優(yōu)化算法在WSN節(jié)點部署中的應用 [J].傳感技術學報，2018，31（5）：753-758.

[5] DRAA A，BOUZOUBIA S，BOUKHALFA I. A sinusoidal differential evolution algorithm for numerical optimization [J].Applied Soft Computing，2015，27：99-126.

[6] LI X T，YIN M H. Modified differential evolution with self-adaptive parameters method [J].Journal of Combinatorial Optimization，2016，31：546–576.

[7] ZENG Y R，PENG L，ZHANG J，et al. An Effective Hybrid Differential Evolution Algorithm Incorporating Simulated Annealing for Joint Replenishment and GWOlivery Problem with TraGWO Credit [J].International Journal of Computational Intelligence Systems，2016，9（6）：1001-1015.

[8] ZHENG Y J，XU X L，LING H F，et al. A hybrid fireworks optimization method with differential evolution operators [J].Neurocomputing，2015，148：75-82.

[9] CHEN B，ZENG W，LIN Y，et al. An Enhanced Differential Evolution Based Algorithm with Simulated Annealing for Solving Multiobjective Optimization Problems [J/OL].Journal of Applied Mathematics，2014，2014[2021-06-31].https：//www.hindawi.com/journals/jam/2014/931630/.

[10] JADON S S，TIWARI R，SHARMA H，et al. Hybrid Artificial Bee Colony algorithm with Differential Evolution [J].Applied Soft Computing，2017，58：11-24.

[11] ZORARPACI E，?ZEL S A. A hybrid approach of differential evolution and artificial bee colony for feature selection [J].Expert Systems with Applications，2016，62：91-103.

[12] 劉愛軍，楊育，李斐等.混沌模擬退火粒子群優(yōu)化算法研究及應用 [J].浙江大學學報（工學版），2013，47（10）：1722-1730.

[13] TAN Y，ZHU Y. Fireworks Algorithm for Optimization [C]//Proceedings of the First international conference on Advances in Swarm Intelligence. Berlin：Springer，2010：355-364.

[14] ELSAYED S M，SARKER R A，RAY T. Differential evolution with automatic parameter configuration for solving the CEC2013 competition on Real-Parameter Optimization [C]//2013 IEEE Congress on Evolutionary Computation.Cancun，Mexico：IEEE，2013：1932-1937.

[15] 黃晨晨，魏霞，黃德啟，等.求解高維復雜函數(shù)的混合蛙跳-灰狼優(yōu)化算法 [J].控制理論與應用，2020，37（7）：1655-1666.

作者簡介：戈陽（1992.05—），男，漢族，江蘇泗陽人，助教，碩士研究生，研究方向：群智能優(yōu)化算法的研究與應用。