混合策略改進鯨魚優化算法

摘 要： 針對標準鯨魚優化算法（whale optimization algorithm，WOA）易陷入局部最優解、收斂精度低、收斂速度慢等問題，提出一種利用混合策略改進的鯨魚優化算法（multi-strategy improved whale optimization algorithm，MSIWOA）。首先采取精英反向策略初始化種群，提高初始種群質量；其次，采取卡方分布的逆累積分布函數更新收斂因子以實現全局探索和局部開發的平衡；然后利用改進氏族拓撲結構強化種群的全局探索能力，并提高算法收斂速度；最后采取circle映射產生混沌解，結合貪婪策略保留較優解，以幫助種群跳出局部最優解。通過對10個基準測試函數以及CEC2019測試函數進行仿真實驗，結果表明，MSIWOA在收斂精度和收斂速度上均有較明顯的提升。

關鍵詞： 精英反向； 收斂因子； 氏族拓撲結構； circle映射； 鯨魚優化算法

中圖分類號： TP301.6"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-021-1415-07

doi：10.19734/j.issn.1001-3695.2021.09.0449

Multi-strategy improved whale optimization algorithm

Li Andong， Liu Sheng

（School of Management， Shanghai University of Engineering Sciences， Shanghai 201620， China）

Abstract： Aiming at the problems of standard whale optimization algorithm（WOA） with low accuracy，slow convergence and easy to fall into local best solutions，this paper proposed a multi-strategy improved whale optimization algorithm（MSIWOA）.Firstly，MSIWOA adopted the elite reverse strategy to initialize the population to improve the quality of the initial population.Secondly，it used the inverse cumulative distribution function of chi-square distribution to update the convergence factor to achieve the balance between global exploration and local development.Then，it used the improved clan topology to strengthen the global exploration ability of the population and improve the convergence speed of the algorithm.Finally，it generated the chaotic solution by circle mapping，and retained the optimal solution by greedy strategy to help the population jump out of the local optimal solution.The simulation results of 10 benchmark test functions and CEC2019 test function show that the convergence accuracy and convergence speed of MSIWOA are significantly improved.

Key words： elite reverse； convergence factor； clan topology； circle mapping； whale optimization algorithm

0 引言

標準鯨魚優化算法（WOA）具有設計參數較少、易于理解等優點，同時也存在易陷入局部最優解、收斂精度低等問題。為此，劉琨等人［1］應用精英反向策略生成初始種群，提高解的質量，為后續進化奠定基礎。Sun等人［2］通過引入二次插值（quadratic interpolation）和萊維飛行策略（Lévy flight）以提高求解精度和跳出局部最優解，并改進非線性遞減收斂因子以更好地適應復雜的非線性問題。De Carvalho等人［3］提出一種融合全互聯拓撲結構和環型鄰域拓撲結構優勢的新型拓撲結構——氏族拓撲，用于平衡探索和開發階段。張達敏等人［4］利用circle混沌序列生成初始化種群，提升種群的均勻分布程度。以上研究成果雖然對WOA進行了一定程度上的改進，但是在收斂精度以及收斂速度方面仍有提升空間，尤其是一些基準測試函數的仿真結果并不十分理想。為此，本文提出一種混合策略改進的鯨魚優化算法（MSIWOA），從初始化種群、拓撲關系、探索和開發的平衡性以及擾動更新四方面進行算法改進。a）利用精英反向策略生成初始化種群，為后續算法進化打下良好的種群基礎；b）就修改收斂因子這一熱門改進策略，引入卡方分布的逆累積分布函數，平衡探索和開發能力；c）改進氏族拓撲關系以更好地與WOA融合，提高算法的全局探索能力；d）將circle混沌序列與動態邊界結合生成擾動解，提高目標區域關注度，提高種群多樣性，并結合貪婪策略，保證種群收斂。通過對10個基準測試函數和CEC2019測試函數進行仿真實驗，結果表明MISWOA在收斂速度和精度方面有著較為明顯的提升。

1 基本鯨魚算法

WOA是在2016年由Mirjalili等人［5］通過觀察座頭鯨群體的捕獵行為后研究提出的，該算法的基本模型描述如下：假設在d維搜索空間中有n只鯨魚個體，則迭代第t次的第i只個體表示為Xti=（xi，1，xi，2，…）（i=1，2，…，n；t=1，2，…，tmax），其中tmax為最大迭代次數。該算法包括三種搜索機制：收縮環繞和螺旋上升機制實現算法的局部搜索，隨機學習機制實現算法的全局搜索。

2.5 CQWOA算法流程

綜上所述，MSIWOA的具體步驟如下：

a）設置種群個體數為N，維數為D，最大迭代tmax次，氏族數量為nc個，則各氏族規模為cp=N/nc。首先利用精英反向學習策略初始化生成種群{Xi，i=1，2，…，N}，進行氏族編號并分配每個氏族中的個體數量。

b）令當前迭代次數為1，計算適應度值{fobj（Xi），i=1，2，…，N}，選出各氏族領導者clan_leader組成領導者會議，并選出全局領導者global_leader。

c）根據式（17）（3）（4）分別更新收斂因子a、參數A和C、更新概率p∈［0，1］。

d）利用式（13）～（16）改進參加領導者會議階段收斂方式。

e）其余個體圍繞本氏族領導者進行位置更新。將X*（t）替換為Xclan_leader（t），根據式（1）（2）進行包圍收縮、隨即學習；依據式（11）（12）進行螺旋更新，將每一維更新后的解利用貪心策略保留較優解。

f）根據式（20）～（24）更新每個個體，待每個個體所有維度更新完成后，與原解進行適應度比較，保留較優解。

g）與循環終止條件比較，判斷是否結束種群進化，否則返回步驟b）。

3 實驗仿真與結果分析

本文實驗是基于IntelCoreTM i5-4258U CPU @ 2.40 GHz 主頻、8 GB內存和Windows 10 64位操作系統進行的，利用MATLAB 2018（a）進行編碼。表1為本文對比分析實驗中各算法的參數設置。

3.1 混合策略的貢獻度分析

為了驗證混合策略改進WOA的合理性和優越性以及分析不同策略對于算法的貢獻程度大小，將WOA與融合精英反向初始化策略的算法定義為模型1（WOA-1）；將WOA與融合精英反向初始化策略和circle動態邊界策略的算法定義為模型2（WOA-2）；將WOA與融合精英反向初始化策略、改進拓撲結構策略和circle動態邊界策略的算法定義為模型3（WOA-3），將上述三個模型與混合策略改進的MSIWOA算法在10個基準測試函數進行仿真實驗對比。為驗證算法的全面性能，基準測試函數包含有單模態和多模態的不同空間特征。測試函數的函數名稱、探索區間、最優值等屬性如表2所示。其中F1～F5測試函數為單模態空間特征，F6～F10測試函數為多模態空間特征。設定種群規模為30，維度為30維，并且為減少隨機誤差，設定最大迭代次數為500，獨立重復30次，取30次實驗結果的平均值和標準差。實驗結果如表3所示。

為比較利用不同策略改進算法之后的收斂快慢情況，上述算法在不同模態測試函數上的收斂曲線如圖6～9所示。

由表3的實驗數據可知，MSIWOA法除了函數F6、F9、F10未達到理論最優值外，其余測試函數均達到了理論最優值，并且與其他模型相比，MSIWOA在這三個測試函數上的實驗結果幾乎為最優值。具體來看，相較于WOA，模型1在函數F3、F5上收斂精度有所提升，這是因為不同的初始化策略提高了種群質量，奠定了后續迭代的基礎；模型2相較于模型1，在F5、F6、F9、F10多模態測試函數上的收斂精度進一步提升，這是因為加入的映射策略有效地提高了算法的全局探索能力；模型3與模型2相比，各測試函數的收斂精度均有大幅的提升，這是因為改進拓撲結構的加入從結構上根本地改進了WOA，但是從F2、F3測試函數結果看，仍存在穩定性差的問題；MSIWAO與模型3相比，解決了F3、F5函數穩定性差的問題，并且函數F10的方差也有所降低。從圖6～9的收斂曲線可以看出，與模型3相比，MSIWOA的收斂速度最快，這是因為改進了非線性收斂因子使得種群在進化的前中期充分地進行空間探索，進而提高了后期開發階段種群對于目標區域的專注度，減少了非目標區域的過多開發，從而提高了算法收斂精度的穩定性。

3.2 與經典智能算法和最近改進智能算法對比

為了驗證MSIWOA的優越性，本文選取10個基準測試函數進行測試，并選取對比算法如下：粒子群算法（PSO）［9］、平衡優化器算法（EO）［10］的經典智能優化算法以及精英反向學習的黃金正弦鯨魚優化算法（elite opposition-based golden-sine whale optimization algorithm，EGolden-SWOA）［9］、融合螺旋策略的分片混沌群粒振蕩搜索算法（DCSOA-S）［11］、混合策略改進的鯨魚優化算法（mix strategy based improved whale optimization algorithm，MSWOA）［12］、一種增強型鯨魚優化算法（enhanced whale optimization algorithm，EWOA）［13］。實驗參數設置如表1所示，維度設定為30，迭代次數設定為500，并進行30次獨立重復實驗。實驗結果如表4所示。

由表4可知，在F1～F5的單模態函數中，MSIWOA均達到了理論最優值，并且標準差也為0，突出表現了MSIWOA較強的局部開發能力、較好的穩定性，證明了綜合改進策略對WOA局部開發能力的顯著提升起到積極的作用；在函數F6、F9、F10的多模態函數測試中，雖然未達到理論最優值，但是相較于其他算法，其收斂精度亦或穩定性均有顯著提升，進一步證實了改進策略的有效性和必要性；在F7、F8的多模態測試函數上，相比于其他智能算法，MSIWOA算法同樣具有一定的優越性和穩定性。

為了探究MSIWOA對收斂速度的影響，圖10～15給出了上述幾種智能算法在不同模態測試函數上的收斂圖。由圖12、15中初始時刻種群適應度值可知，精英反向策略顯著地提高了種群的質量，奠定了后續種群快速迭代的基礎；由圖10～15可知，在迭代中后期，MSIWOA收斂精度的提升明顯比其他算法更快，這是對于空間更全面探索的結果，并且對于多模態測試函數，更是迭代至50次左右便達到極高的收斂精度，證明了MSIWOA較高的全局探索能力。綜上所述，WOA無論在收斂精度、收斂速度還是魯棒性上，均體現出較高的性能。

3.3 Wilcoxon檢驗

上述實驗中，只通過平均值和標準差的結果就判定算法之間有顯著差異是不充分的，為了公平地體現MSIWOA的優越性，本文對實驗數據進行Wilcoxon秩和檢驗。實驗設定顯著性差異為5%，當p值低于該顯著性水平時就判定在該測試函數上兩個算法有顯著差異；而當高于該顯著水平則判斷兩個算法在統計學上無顯著差異，即算法性能差異不大；p為1時兩者無差異。由表5可知，大部分p值小于5%，由此可知，MSIWOA比其他七種優化算法具有更好的優越性。

3.4 CEC2019函數測試

為進一步驗證MSIWOA處理復雜問題時的優越性能，本文選取文獻［14］提及的CEC2019函數測試集，包含10個單目標測試函數，且具有復雜的空間特征。這些測試函數維度數目不等，但是理論最優值均為1。本文選取基本的butterfly optimization algorithm（BOA）［14］、moth-flame optimizationm（MFO）［14］、WOA以及最新提出的一種增強型WOA（WOAmM）［14］和A～C parametric whale optimization algorithm（ACWOA）［15］與MSIWOA進行對比，對比數據來源于文獻［14］。設定算法進化500次，獨立重復尋優30次并記錄各次尋優結果。實驗結果如表6所示。

從表6可知，MSIWOA在F11處達到理論最優值；在函數F14、F19、F20上與其他算法相比，MSIWOA取得了最優的平均值和標準差，體現了改進算法MSIWOA的優越穩定性；在函數F16、F17上，MSIWOA取得最優的最優值和平均值，體現了MSIWOA較強的探索尋優性能；MSIWOA在函數F15變現為實驗最優值最小，同樣體現出該算法的尋優性能較優越。另外，MSIWOA在F12、F13、F18的測試函數上沒有取得測試指標排序的首位，這是因為MSIWOA需進行適應度比較，增加了運算量，導致優化性能下降，但是與WOA相比，部分指標還是有所提升，MSIWOA的性能優越性得到進一步彰顯。

4 結束語

為了提高WOA的尋優性能。提出一種混合策略改進的鯨魚優化算法。首先，為了提高初始種群質量，利用精英策略和反向策略初始化鯨魚種群；然后改進氏族拓撲結構和非線性收斂因子，提高全局探索能力的同時兼顧加速收斂；最后引入circle動態邊界映射，降低對非目標區域探索的概率，同時增加了種群多樣性。為了驗證混合策略改進的可行性及優越性能，與融合單策略改進WOA、經典智能算法以及最新改進智能算法進行比較，通過對10個benchmark測試函數和CEC2019測試函數集進行仿真實驗對比，并對仿真結果進行Wilcoxon統計檢驗。結果驗證了MSIWOA的優越尋優性能。下一步研究重點是應用MSIWOA于多目標的復雜工程問題，如車間調度問題求解和倉庫選址優化等。

參考文獻：

［1］劉琨，趙露露，王輝.一種基于精英反向和縱橫交叉的鯨魚優化算法［J］.小型微型計算機系統，2020，41（10）：2092-2097. （Liu Kun，Zhao Lulu，Wang Hui.Whale optimization algorithm based on elite opposition-based and crisscross optimization［J］.Journal of Chinese Computer Systems，2020，41（10）：2092-2097.）

［2］Sun Yongjun，Wang Xilu，Chen Yahuan，et al.A modified whale optimization algorithm for large-scale global optimization problems［J］.Expert Systems with Applications，2018，114（12）：563-577.

［3］De Carvalho D F，Bastos-Filho C J A.Clan particle swarm optimization［J］.International Journal of Intelligent Computing and Cybernetics，2009，2（2）：197-227.

［4］張達敏，徐航，王依柔，等.嵌入circle映射和逐維小孔成像反向學習的鯨魚優化算法［J］.控制與決策，2021，36（5）：1173-1180. （Zhang Damin，Xu Hang，Wang Yirou，et al.Whale optimization algorithm for embedded circle mapping and one-dimensional oppositional learning based small hole imaging［J］.Control and Decision，2021，36（5）：1173-1180.）

［5］Mirjalili S，Lewis A.The whale optimization algorithm［J］.Advances in Engineering Software，2016，95（5）：51-67.

［6］謝承旺，王志杰，夏學文.應用檔案精英學習和反向學習的多目標進化算法［J］.計算機學報，2017，40（3）：757-772. （Xie Chengwang，Wang Zhijie，Xia Xuewen.Multi-objective evolutionary algorithm based on archive-elite learning and opposition-based learning［J］.Chinese Journal of Computers，2017，40（3）：757-772.）

［7］馮文濤，鄧兵.鯨魚優化算法的全局收斂性分析及參數選擇研究［J］.控制理論與應用，2021，38（5）：641-651. （Feng Wentao，Deng Bing.Global convergence analysis and research on parameter selection of whale optimization algorithm［J］.Control Theory amp; Applications，2021，38（5）：641-651.）

［8］王永貴，李鑫，關連正.求解高維優化問題的改進鯨魚優化算法［J］.計算機科學與探索.（2021-06-03）.

http：//kns.cnki.net/kcms/detail/11.5602.tp.20210603.1301.004.html. （Wang Yonggui，Li Xin，Guan Lianzheng.Improved Whales optimization algorithm for solving high dimensional optimization problems［J］.Journal of Frontiers of Computer Science and Technology（2021-06-03）.http：//kns.cnki.net/kcms/detail/11.5602.tp.20210603.1301.004.html.）

［9］肖子雅，劉升.精英反向黃金正弦鯨魚算法及其工程優化研究［J］.電子學報，2019，47（10）：2177-2186. （Xiao Ziya，Liu Sheng.Study on elite opposition-based golden-sine whale optimization algorithm and its application of project optimization［J］.Acta Electronica Sinica，2019，47（10）：2177-2186.）

［10］Faramarzi A，Heidarinejad M，Stephens B，et al.Equilibrium optimizer：a novel optimization algorithm［J］.Knowledge-Based Systems，2020，191（3）：105190.

［11］林之博，劉媛華.融合螺旋策略的離散混沌群粒振蕩搜索算法［J］.計算機應用研究，2021，38（10）：3060-3066，3071. （Lin Zhibo，Liu Yuanhua.Dispersed chaotic swarm oscillation algorithm merged with spiral strategy［J］.Application Research of Computers，2021，38（10）：3060-3066，3071.）

［12］何慶，魏康園，徐欽帥.基于混合策略改進的鯨魚優化算法［J］.計算機應用研究，2019，36（12）：3647-3651，3665. （He Qing，Wei Kangyuan，Xu Qinshuai.Mixed strategy based improved whale optimization algorithm［J］.Application Research of Computers，2019，36（12）：3647-3651，3665.）

［13］馮文濤，宋科康.一種增強型鯨魚優化算法［J］.計算機仿真，2020，37（11）：275-279，357. （Feng Wentao，Song Kekang.Enhanced whale optimization algorithm［J］.Computer Simulation，2020，37（11）：275-279，357.）

［14］Chakraborty S，Saha A K，Sharma S，et al.A novel enhanced whale optimization algorithm for global optimization［J］.Computers amp; Industrial Engineering，2021，153（3）：107086.

［15］Elhosseini M A，Haikal A Y，Badawy M，et al.Biped robot stability based on an A-C parametric whale optimization algorithm［J］.Journal of Computational Science，2019，31（2）：17-32.