融合振蕩禁忌搜索的自適應均衡優化算法

劉成漢，何 慶

1.貴州大學 大數據與信息工程學院，貴陽550025 2.貴州大學 貴州省公共大數據重點實驗室，貴陽 550025

在過去的二十年中，隨著科技的發展和技術的革新，各種復雜優化問題層出不窮，啟發式算法由于其簡單性、靈活性和較高的魯棒性，成為解決復雜優化問題的有力工具。常見的啟發式算法有：粒子群優化（particle swarm optimization，PSO）算法[1]、灰狼優化（grey wolf optimization，GWO）算法[2]、鯨魚優化算法（whale optimization algorithm，WOA）[3]等。

均衡優化（equilibrium optimizer，EO）算法是Faramarzi等人[4]2019年提出的一種新型啟發式算法，其靈感來源于用于估計動態和平衡狀態的控制體積質量平衡物理模型。EO算法具有搜索能力強、參數簡單的優點[4]，已被成功應用到多閾值圖像分割[5]、經濟調度[6]、路徑規劃[7]等多個領域，為解決復雜優化問題提供了新的思路。但是EO算法仍存在著收斂精度不高、收斂速度慢、易受局部最小值影響的問題。針對上述問題，眾多學者對EO算法做出了改進。例如：Fan等人[8]提出了一種基于對立學習和改進位置更新方式的均衡優化算法，利用高斯變異和基于種群劃分和重構概念的探索性搜索機制，提高了算法的收斂速度和跳出局部極值點的能力；Gao等人[9]采用S型和V型傳遞函數將EO算法轉換成二進制離散類型算法，提高了算法搜索能力；Abdel-Basset等人[10]提出了一種具有勘探開發優勢的多目標均衡優化算法，采用存檔策略保存最優解并通過擁擠距離方法來保留非主導解的多樣性，從而提高了算法的搜索和開發能力；Mousa等人[11]將基于混沌理論的局部搜索算法引入到EO算法中，提出了一種基于混沌搜索的均衡優化器算法，提高了算法的局部搜索能力；Wunnava等人[12]提出了一種自適應均衡優化算法，通過對非性能搜索個體施加分散性自適應決策，提高了算法全局搜索能力和多樣性；Too等人[13]提出了一種基于通用學習的均衡優化算法，利用一種通用的學習策略，使個體能夠從不同維度的潛在候選對象中學習，從而幫助算法逃脫局部最優值并探索更多區域。

分析以上學者的研究經驗可知，找到一種簡單有效的策略提升EO算法的性能是必要的，因此，本文針對EO算法存在的上述問題，提出一種融合振蕩禁忌搜索的自適應均衡優化算法。首先，在初始化時結合精英反向學習策略貪婪保留原始種群和精英反向種群中的較好個體，提高種群初始化質量，加快種群收斂；然后，引入自適應調整收斂因子，平衡算法的搜索能力，提高算法的收斂精度；最后，引入融合振蕩算子的禁忌搜索策略，利用禁忌表的記錄功能和振蕩算子削弱局部極值點對算法的影響。通過10個基準測試函數及其Wilcoxon秩和檢測和部分CEC2014測試函數的仿真實驗結果驗證了CfOEO算法的優越性。

1 EO算法介紹

EO算法來源于一個描述容器內進出物質質量平衡的一階常微分方程，方程描述了容器內質量隨時間變化的規律，其數學模型如式（1）所示：

式中，V表示容積；C表示濃度；Q為單位時間內進出的容量流率；Ceq為平衡狀態下的濃度；G表示質量生成速率。分析式（1）可知，平衡體系中質量隨時間的變化等于進入系統的質量加上系統內部產生的質量減去離開系統的質量，當V·dC/dt=0時，系統達到平衡狀態。

求解式（1）所示微分方程，得到結果如式（2）所示：

式中，C0為初始濃度；λ表示流動率；F表示求解微分方程所得的指數項系數，其數學模型描述如式（3）所示：

EO算法采用上述濃度C作為個體的解，主要根據式（2）進行迭代更新，其中濃度C、C0和Ceq分別代表當前解、上一次迭代產生的解和當前最優解。算法具體優化過程起源于一個隨機初始化的濃度集合，數學模型描述如式（4）所示：

式中，UB和LB分別是搜索空間上下限，表示濃度范圍；r i是取值為[0，1]的隨機向量，維度與優化問題維度一致。

平衡池（即最優個體）定義如下：

式中，Ceq1、Ceq2、Ceq3、Ceq4和Ceqa分別表示當前迭代前4個最優個體及其平均值，它們被選中的概率相等。

指數項系數和質量生成速率數學模型描述如式（6）和式（7）所示：

式中，a1為常系數；sign表示符號函數；r和λ表示隨機向量，取值為[0，1]；Gcp為控制參數，數學模型描述如式（8）所示：

式中，r1和r2為取值[0，1]的隨機向量。

綜上所述，EO算法位置更新數學模型如式（9）所示：

2 CfOEO算法原理介紹

在基本EO算法中，種群初始化處理采用隨機分布的方式，這種隨機方式會導致個體前期尋優存在一定的盲目性，使得算法尋優速度慢；其次，算法用來平衡局部搜索和全局搜索能力的指數項系數F采用常系數權重，得到的系數變化趨勢趨于常數，并不符合算法迭代過程中的非線性尋優規律；最后，對于加強算法局部尋優能力的質量生成速率G，其有50%幾率隨機取值為0，具有很大的不穩定性，雖然有一定的幾率帶領個體跳出局部最優值點，但是并沒有考慮尋優過程中個體位置信息的變化。

綜上所述，本文針對上述算法原理上的缺陷，引入相應策略進行改善。具體策略介紹如下。

2.1 精英反向學習初始化

文獻[14]指出，與隨機方法相比，找到具有隨機方向及其相反方向的候選解為尋找未知最優解提供了更高的機會。為了提高算法搜索能力，加快算法前期收斂速度，本文引入精英反向學習策略初始化種群，定義X i=(X i,1,X i,2,…,X i,d)為搜索空間內的一個點，其中d為優化問題的維度，則其反向點X′i定義如式（10）所示：

式中，UB和LB分別為搜索空間的上界和下界。

然而，粒子自身反向解受固定的搜索空間邊界限制，導致反向點較為發散地分布在搜索空間。因此，本文引入精英反向解，通過精英個體構成動態邊界，使反向解分布在空間較優位置，初始個體Xi的精英反向解定義如式（11）所示：

式中，r為取值[0，1]的隨機數；a i和b i分別表示Xi在維度d上的最大值和最小值。當精英反向解超出動態邊界，則重置反向解，如式（12）所示：

最后，通過貪婪策略保留當前個體和精英反向個體中較優的個體組成新的初始化種群。

2.2 自適應調整收斂因子

收斂因子在目標函數優化中起著很重要的作用，合適的收斂因子能夠加快算法收斂，提高算法收斂精度。針對EO算法尋優過程中收斂速度慢、精度不高的問題，引入一種自適應調整的收斂因子，在算法迭代前期，種群全局搜索最優解，此時應該給予足夠的搜索空間發散種群，因此給予一個較大的收斂步長有利于算法的開發；在算法迭代中后期，算法逐漸收斂，個體開始進行局部搜索，此時給予一個較小的收斂步長有利于算法進行局部探索。此外，引入收斂因子速率下降調節算子Q，可自動調節收斂因子下降速率，自適應可調整收斂因子Cf的數學模型描述如式（13）所示：

式中，Tm為最大迭代次數；Cm表示收斂因子的初始值；α為常量系數；Q為控制參數。當Q取值為1.0、2.5和5.0時的收斂因子對比曲線如圖1所示。

圖1 收斂因子曲線圖Fig.1 Feedback factor curve

由圖1可知，改進的收斂因子曲線的下降速率隨著調節因子Q的增大而增大。在具體算法調試中，Q值的選取不宜過大也不能太小。Q值太大可能會導致算法前期收斂過快，算法開發能力減弱從而陷入局部極小值點；而Q值太小則不能體現收斂因子在平衡算法搜索能力上的優勢，算法收斂速度變慢。為了平衡算法的搜索能力，本文經過大量實驗分析，最后選取Q=2.5最為合適。

2.3 振蕩禁忌搜索策略

禁忌搜索（tabu search，TS）開創了搜索過程中存儲功能的系統性探索，是用于全局搜索的一種啟發式過程，為多種類型的組合優化難題提供了有效的解決方案[15]。禁忌搜索思想的核心是禁忌表，禁忌表的存儲功能可以避免算法迂回搜索，提高算法應對復雜優化問題的能力。同時，禁忌搜索策略的赦免機制保證了算法對于優質資源的利用，在提高算法多樣性的同時提高算法的全局搜索能力。禁忌搜索策略源于一個當前解Fp和解的搜索空間N，在當前解的搜索空間內迭代產生多個候選解F={F1,F2,…,F n}（n為優化問題所需迭代次數），當候選解屬性優于當前解，則此候選解為非禁忌對象，用它代替當前解，并加入禁忌表；若候選解存在于禁忌表中或劣于當前解，則保持當前解不變。l決定禁忌表的容量大小，當禁忌對象超過禁忌長度l，則赦免最初的禁忌對象，用新的禁忌對象替代，以此充分利用優質解。

綜上所述，為了提高EO算法的全局搜索能力，改善EO算法易早熟收斂的問題，本文采用禁忌搜索策略更新位置，同時引入振蕩算子，當候選解出現在禁忌表中，說明算法存在迂回搜索，因此對位置更新施加振蕩，以提高算法多樣性。振蕩算子o數學模型描述如式（10）所示：

式中，r1、r2和r3都是取值為[0，1]的隨機數；Tm為最大迭代次數。由式（10）可知，迭代前期，振蕩因子較大，提高了算法搜索范圍，增加了算法多樣性；迭代后期，振蕩因子較小，從而擴大了最優解影響，增加了算法勘探能力。

2.4 CfOEO算法實現過程

綜上改進策略，CfOEO實現流程圖如圖2所示。

圖2 CfOEO實現流程圖Fig.2 CfOEO implementation flowchart

CfOEO算法實現步驟如下所示：

步驟1參數初始化：設置搜索上下界UB、LB，種群規模N，最大迭代次數Tm，維度d，生成速率控制參數Gcp和常系數a1、a2。

步驟2初始化種群：隨機生成種群，計算精英反向種群，貪婪保留較優個體。

步驟3計算個體適應度值，記錄較優個體，生成平衡狀態池Ceq,pool。

步驟4根據式（9）更新候選解位置。

步驟5根據禁忌搜索策略對候選解進行禁忌操作。

步驟6引入振蕩算子對存在于禁忌表中的候選解進行振蕩操作。

步驟7判斷結束條件，若滿足迭代條件則算法終止，否則重復步驟3~步驟6。

步驟8輸出最優值，算法結束。

3 仿真實驗與結果分析

3.1 參數設置說明

仿真實驗采用的計算機配置為Intel Core i5-7500U，32 GB內存，64 bit操作系統，計算環境為Matlab2016（a）。本文選取基本灰狼優化（GWO）算法、蜉蝣算法（mayfly algorithm，MA）、黏菌算法（slime mould algorithm，SMA）以及EO算法與CfOEO算法進行尋優實驗對比，基本參數統一設置為：最大迭代次數Tm=500，低維維度d=30，高維維度d=200，種群規模N=30。各基本算法內部參數設置如表1所示。

表1 算法參數設置Table 1 Algorithm parameter setting

3.2 基準測試函數介紹

本文采用10個基準測試函數對CfOEO算法進行尋優性能測試，其中f1~f5為單峰測試函數，f6~f9為多峰測試函數，f10為固定維度測試函數，基準測試函數相關信息如表2所示。

表2 基準測試函數介紹Table 2 Introduction to benchmark functions

3.3 本文各改進策略仿真分析

本節分別對本文提出的三個策略進行性能分析，其中CEO算法是本文引入精英反向學習初始化的EO算法，CfEO算法是本文引入自適應調整收斂因子的EO算法，OEO算法是本文引入振蕩禁忌搜索策略的EO算法。統一仿真實驗數據為：維度d=30，最大迭代次數Tm=1 000，種群規模N=30，其他固定參數由表1給出，各算法獨立運行30次取平均值和標準差。

3.3.1 CEO算法性能分析

本文在初始化中引入優化問題的適應度評價函數，通過適應度函數評價隨機種群與其精英反向種群的位置，并貪婪保留較優位置，從而加快算法收斂。為了驗證CEO算法的性能，選取單峰測試函數f1和多峰測試函數f8進行仿真實驗，實驗結果如圖3所示。

圖3 CEO算法與EO算法平均收斂曲線圖Fig.3 Convergence curves between CEO and EO

由圖3對比結果可知，CEO算法在單峰測試函數f1和多峰測試函數f8上雖然沒能找到理論最優值，但是CEO算法的收斂速度明顯快于EO算法，說明本文引入精英反向學習初始化策略能有效加快EO算法的收斂速度。

3.3.2 CfEO算法性能分析

為了平衡EO算法的開發和探索能力，引入自適應可調整的收斂因子，平衡算法搜索能力，提高EO算法收斂精度。為了驗證CfEO算法的性能，選取單峰測試函數f2、f5和多峰測試函數f7、f9進行仿真實驗，實驗結果如圖4所示。

圖4 CfEO算法與EO算法平均收斂曲線圖Fig.4 Convergence curves between CfEO and EO

由圖4結果可知，對于單峰測試函數f2和多峰測試函數f7、f9，CfEO算法能夠直接收斂到理論最優值，而對于單峰測試函數f5，CfEO算法的收斂精度優于EO算法，說明收斂因子對于EO算法的搜索能力提升有一定幫助，能提高EO算法收斂精度。

3.3.3 OEO算法性能分析

針對EO算法早熟收斂問題，本文引入禁忌搜索策略并結合振蕩算子對EO算法進行振蕩禁忌操作，以提高算法規避局部極值點的能力。為了驗證OEO算法的性能，選取單峰測試函數f3和多峰測試函數f6、f7以及固定維度測試函數f10進行仿真實驗，實驗結果如圖5所示。

圖5 OEO算法與EO算法平均收斂曲線圖Fig.5 Convergence curves between OEO and EO

由圖5結果可知，對于單峰測試函數f6和固定維度測試函數f10，OEO算法能跳出局部極值點，收斂到最優值，說明振蕩禁忌搜索策略能提高算法跳出局部極值點能力；對于f3函數，OEO算法能找到0，說明禁忌搜索對于優質解的利用以及振蕩算子的動態調整，對于算法搜索能力的提升也有一定的幫助。

3.4 各改進EO算法性能對比

選取基本EO算法、AEO算法[12]、m-EO算法[16]與CfOEO算法進行基準測試函數尋優性能對比，以驗證CfOEO算法的有效性，其中AEO算法是文獻[12]提出的自適應均衡優化算法，m-EO算法是文獻[16]提出的具有突變策略的數值優化均衡優化算法。實驗統一采用維度d=30，最大迭代次數Tm=500，種群規模N=30，各算法獨立運行30次取平均值和標準差，實驗結果如表3所示。

表3 各改進EO算法性能對比Table 3 Performance comparison of improved EO algorithms

由表3結果可知，相比于其他改進的EO算法，本文提出的CfOEO算法在基準測試函數上的表現優秀，10個基準測試函數都取得了最優精度，其中有7個測試函數能夠收斂到全局最優解。對于f5、f6和f8測試函數，雖然CfOEO算法沒能找到最優解，但是其收斂精度在各個EO算法變體中是最高的，說明本文改進策略具有一定優勢。

3.5 CfOEO算法高維尋優性能測試

為了驗證CfOEO算法對于高維度優化問題的處理能力，選取基本灰狼優化（GWO）算法、黏菌算法（SMA）、蜉蝣算法（MA）和EO算法與CfOEO算法進行高維基準函數尋優對比實驗。實驗數據統一為：維度d=200，最大迭代次數Tm=500，種群規模N=30，各算法內部參數由表1給出，測試函數相關信息由表2給出。為了更直觀地分析ISMA處理高維問題的性能，圖6給出了在200維時各算法獨立運行30次后的適應度平均值收斂曲線。

由圖6可知，對于200維度的基準測試函數，CfOEO算法不管是在求解速度和精度，還是對于局部極值點的處理能力上都優于其他基本算法，對于單峰測試函數f1~f4和多峰測試函數f7、f9以及固定維度測試函數f10，CfOEO算法能夠收斂到理論最優值；對于f6和f8測試函數，雖然CfOEO算法的求解精度并不是最高的，但是其求解速度明顯優于其他算法；而f5函數則體現了CfOEO算法對于局部極值點具有一定的規避能力。本文提出的CfOEO算法在高維問題的處理上具有明顯的優勢。

圖6 基準測試函數平均收斂曲線（200維）Fig.6 Function average convergence curves（200D）

3.6 Wilcoxon秩和檢測

Wilcoxon秩和檢測常用來對比兩組數據之間的差異，并分析這些差異，以確定它們是否在統計上存在顯著不同。本文將EO算法、黑猩猩優化算法（chimp optimization algorithm，ChOA）、PSO算法、CEO算法、CfEO算法和OEO算法與CfOEO算法進行12個基準測試函數上的Wilcoxon秩和檢測對比分析，以驗證CfOEO算法尋優結果在統計學上的優勢。其中CEO算法、CfEO算法和OEO算法分別是本文3個單獨改進策略與EO算法形成的變體，當計算結果p＜5%時，可以被認為是拒絕零假設的有力驗證[17]。結果+、-和=分別表示CfOEO算法秩和統計結果優于、差于和等于對比算法，NaN表示沒有數據進行對比，Wilcoxon秩和檢驗結果如表4所示。

由表4結果可知，除了沒有數據對比情況外，CfOEO算法相較于其他算法的Wilcoxon秩和檢測結果p值基本上都小于5%，說明CfOEO算法對于基準測試函數的優化結果在統計學上具有很大的優勢，驗證了CfOEO算法的魯棒性。

表4 Wilcoxon秩和檢驗結果Table 4 Wilcoxon rank sum test results

3.7 CEC2014測試函數尋優對比

為了進一步驗證CfOEO算法處理具有復雜特征問題時的魯棒性，本文選取部分具有復雜特征的CEC2014單目標優化函數進行尋優對比分析，其中包括單峰（UF）、多峰（MF）、混合（HF）和復合（CF）類型函數，函數相關信息如表5所示。本文將CfOEO算法與標準PSO算法、SCA算法、L-SHADE算法和本文引入振蕩禁忌搜索的EO算法（OEO算法）進行對比。其中，L-SHADE算法在CEC2014測試函數中表現卓越，常用來進行對比實驗。實驗參數取種群規模N=50，維度d=30，最大迭代次數Tm=2 000，每個函數獨立運行50次取平均值和標準差。其中L-SHADE算法的數據來源于文獻[18]，CfOEO算法運行結果及與其他算法對比如表6所示。

表5 部分CEC2014函數介紹Table 5 Part of CEC2014 function

表6結果展示了CfOEO算法在CEC2014測試函數上的優秀表現，除了單峰CEC03函數，CfOEO算法在其他7個測試函數上都取得了最優精度。對于CEC05、CEC12和CEC19測試函數，CfOEO算法基本收斂到了理論最優值；對于復合特征CEC28和CEC30函數，CfOEO算法尋優標準差為0，說明其對于復合特征函數尋優穩定性很高。上述CEC2014測試函數尋優結果分析說明，本文提出的CfOEO算法對于具有復雜特征的函數尋優同樣具有很大優勢，驗證了CfOEO算法的魯棒性。

表6 CEC2014函數優化對比Table 6 CEC2014 function optimization comparison

3.8 CfOEO算法時間復雜度分析

CfOEO算法時間復雜度主要由精英反向學習初始化種群、自適應收斂因子和振蕩禁忌搜索策略組成。設基本EO算法的時間復雜度為O(N×d×Tm)，其中N、d和Tm分別表示種群規模、優化問題維度大小和最大迭代次數。

（1）計算精英反向種群時間復雜度為O(N×d×Tm)，因此反向學習初始化種群的時間復雜度為O(2N×d×Tm)；

（2）設計算自適應收斂因子所需時間為t1，則引入自適應收斂因子時間復雜度為O(N×d×T m+t1)；

（3）設計算振蕩算子所需時間為t2，禁忌表長度為l，振蕩禁忌搜索策略時間復雜度為O(N×d×T m+t2+N×d×T m×l)。

綜上所述，雖然CfOEO算法的時間復雜度有所增加，但是與EO算法屬于同一個數量級，這種時間復雜度的增加在可以接受的范圍內，并且通過上面實驗分析可以看出CfOEO算法的性能是卓越的。

4 結束語

為了改善EO算法存在的搜索能力弱、易受局部極值點影響的問題，本文提出一種融合振蕩禁忌搜索的自適應均衡優化算法，通過引入精英反向學習策略初始化種群提高初始化時種群的質量；采用自適應可調整的收斂因子，以平衡算法的搜索能力；考慮到禁忌搜索策略強大的全局管理能力，引入融合振蕩算子的禁忌搜索策略，提高算法跳出局部極值點的能力，也加快了算法收斂。最后，通過10個基準測試函數和部分CEC2014測試函數仿真實驗以及基準測試函數Wilcoxon秩和檢測結果驗證了CfOEO算法的優越性。下一步工作考慮將CfOEO算法應用到實際工程設計問題中，進一步驗證CfOEO算法相對于其他算法的優越性。