改進平衡優化器算法在約束優化問題中的應用

李守玉，何慶，陳俊

貴州大學 大數據與信息工程學院，貴陽550025

在實際工程應用領域的優化目標包括從連續到離散、從單目標到多目標、從有約束到無約束，面對這些復雜的優化問題，傳統優化算法僅能求取局部最優值且優化結果嚴重依賴初始值[1]。研究者們從生物和自然物理現象得到啟發，提出的元啟發式算法成為了一種有效且實用的優化方案，并成功應用于NP-Hard[2-3]、圖像分割[4]、PID參數控制[5]等問題。

平衡優化器算法（equilibrium optimizer，EO）是由Faramarzi 等人于2020 年提出的基于物理的元啟發式算法[6]，其原理是將每一個粒子（解）及其濃度（位置）看作獨立個體，然后根據均衡候選解的濃度隨機更新個體，最終達到平衡狀態（最優解）。它具備參數少、耗時少及易于實現等優點，并且尋優能力優于粒子群算法[7]、遺傳算法[8]、差分進化算法[9]、螢火蟲算法[10]。但標準EO 算法與其他智能算法一樣，存在算法容易陷入局部最優、收斂較慢等問題，其尋優能力仍有待提高。眾多學者對其深入研究，提出了一些有效的改進方法。Fan等人[11]通過反向學習和新的濃度更新公式，提高算法尋優精度。Sayed 等人[12]通過引入混沌映射構建穩定的搜索機制，提高算法的特征選擇效率。Dinkar 等人[13]通過拉普拉斯分布的隨機游動更新候選解濃度，然后利用反向學習加速開發，使算法快速收斂。Ahmed等人[14]利用自動學習機尋找合適的參數值，便于解決高維的特征選擇問題。Kardani 等人[15]利用突變機制提高搜索能力，避免陷入局部最優，并與極限學習機和人工神經網結合對致密碳酸鹽巖滲透率進行預測。Shankar等人[16]通過對立學習的更新機制生成最優解來尋找最優空間。雖然上述方法取得不錯的效果，但EO的優化精度仍有待提高。

針對以上問題，提出改進的平衡器優化算法，利用正弦變化規律自適應平衡勘探與開發；引入當前最優粒子信息到粒子種群，促進種群粒子信息交流以及吸引其他粒子快速收斂到最優解，進一步提高和平衡勘探與開發的能力，增強算法逃離局部最優的能力，避免早熟現象。

1 平衡優化器算法

1.1 種群初始化

標準EO 在解空間中隨機初始化粒子的位置。種群初始化公式如下：其中，Ci,k是第k個粒子的初始位置，rk是[0,1]的隨機向量，ub和lb分別是搜索空間的上下界。k的變化范圍為[1,N]，N為種群粒子數量。

1.2 候選解和均衡池

平衡狀態是算法的最終收斂狀態。迭代前期種群沒有達到平衡狀態的依據，只有通過候選解為種群提供依據。種群初始化后，計算每個粒子適應度值，并根據適應度值的大小獲得四個候選解。另外，通過它們得到平均候選解，進而構建均衡池。四個候選解有助于開發，而平均候選解有助于勘探。

每個粒子都以相同的概率在候選粒子中進行隨機選擇來更新其濃度。在優化過程結束之前，每個粒子都將經歷濃度更新過程。

1.3 濃度更新

標準EO為了進一步平衡勘探與開發，利用指數項F進行調整，數學描述如下：

其中，a1和a2均為常數，λ是[0,1]之間的隨機向量，sign(r-0.5)用來控制勘探與開發的方向，m是一個隨著迭代增加而降低的變量。t為當前迭代次數，T為最大迭代次數。另外，利用生成率（G）改進開發階段進而提高提供解的精度。數學表達如下：

其中，GCP為G的控制參數，主要控制粒子是否使用GCP來更新狀態。此外，GCP表達形式又由生成概率（GP）決定。m0是為降低搜索速度的同時提高算法的勘探與開發能力。Ceq是從均衡池隨機選出的一個解，R1和R2是[0,1]的隨機數。標準EO 濃度更新定義如下，其中V表示單位體積。算法1為標準EO算法的偽代碼。

算法1平衡優化器算法

2 改進平衡優化器算法

2.1 正弦池策略

標準EO 指出，當粒子之間距離較遠時，平均候選解有助于迭代初期發現未知的解空間。因此，增強平均候選解的勘探與開發能力將提高種群粒子的尋優能力。

元啟發式算法的核心是迭代初期對解空間內的大部分區域進行勘探，然后勘探階段逐漸轉化為開發階段的尋優過程。因此，為了提高粒子的勘探與開發能力，本文提出正弦池策略。該策略主要根據迭代階段采用不同尋優模式動態協調粒子的全局勘探與局部開發。迭代前期，固定角頻率正弦遞減模式中固定角頻率和正弦遞減特性有助于粒子搜索空間進行大范圍的快速搜索，尋找潛在優質解，同時逐漸向開發階段過渡；迭代后期，變化角頻率正弦遞增模式主要借助柯西分布的“長跳”特性使角頻率發生變化和正弦遞增性質，使粒子的移動步長多變，有助于粒子持續尋優并且在優質解附近空間進行精細的深度開發。正弦池策略數學公式如下：

其中，ω1為固定角頻率設為0.5，ω2是包含種群信息的柯西分布，γ為搜索維度D，φ為種群大小N。式（13）為柯西分布的概率密度函數。另外，式（14）～（16）主要利用正弦池策略對平均候選解作用，得到新的平均候選解Nave。然后將其與Ceq1～Ceq4構成新的均衡池Np，Np從中隨機取出一個候選解得到Ceq。

2.2 自適應優先引力策略

標準EO尋找平衡狀態的過程中，當前粒子僅根據均衡池中隨機選擇的候選解更新濃度，雖然能為當前粒子提供部分信息，但因粒子進化信息不足且有用信息量少，其他粒子無法快速收斂到當前最優粒子和全局最優粒子。本文受萬有引力啟發，提出自適應優先引力策略。簡單來說，自適應優先引力策略是先找到當前最優粒子，將它看成吸引力最大的粒子，它能夠向其他粒子傳遞多且有用的信息吸引其向自身靠近，引導種群進化。另外，當前最優粒子可能處于局部最優，易導致算法早熟。為避免此種情況發生，采用均勻分布U(a,b)對當前最優粒子進行擾動避免陷入局部最優，再用Beta(α,β)分布促進其他粒子與當前最優粒子之間的信息流動，增大彼此之間的引力作用。均勻分布和Beta分布的概率密度函數定義如下：

其中，a,b∈R，α,β>0。由概率密度函數得到兩者的分布函數：

為了充分傳遞粒子之間信息，采用標準均勻分布U(0,1)，B為Beta分布，α設為1，β為式（21）。自適應優先引力策略數學描述，Pb為當前最優粒子的位置：

綜上所述，首先通過正弦池策略提高平均候選解的勘探與開發能力，進一步增強種群粒子尋優能力。然后，自適應優先引力策略添加當前最優粒子的位置信息到種群中豐富其他粒子的進化信息，加強粒子間信息交流，吸引其他粒子向當前最優粒子收斂，進而快速收斂到全局最優解。本文所提的MDSGEO（multi-distribution sinusoidal gravitation equalization optimizer）執行步驟如算法2所示。

算法2改進平衡優化器算法

2.3 時間復雜度分析

假設種群數量為N，目標問題維度為D，最大迭代次數為T，評估目標問題適應度為C。其中“O”常用來表示復雜度。

標準EO的時間復雜度：初始參數定義O(1)，種群初始化O(ND)，計算目標問題適應度O(TCN)，記憶存儲O(TN)，濃度更新O(TND)。因此，根據復雜度計算規則，標準EO總時間復雜度為：

由標準EO的復雜度可知，MDSGEO僅添加正弦池策略O(1+TND)，自適應優先引力策略O(ND+TND)。因此，MDSGEO總時間復雜度為：

綜上分析，MDSGEO復雜度與標準EO的復雜度同一級別，并未增加額外的時間復雜度，說明MDSGEO并未犧牲空間來提升算法性能。

3 仿真實驗與分析

3.1 實驗相關設置

實驗環境為Windows 7，64 位操作系統，CPU 為Intel Core i5-6500H，主頻3.2 GHz，內存8 GB，算法基于MATLAB2020a編寫。

對16 個基準測試函數進行仿真實驗，表1 中測試函數不僅包含測試算法局部開發能力的單峰函數，還包括驗證算法全局勘探能力的多峰函數。具體有單峰可分（US）、單峰不可分（UN）、多峰可分（MS）、多峰不可分（MN）和固定維度（FD）等多類型函數。

表1 基準測試函數Table 1 Benchmark functions

同時，元啟發式算法的參數設置對于算法尋優將產生重要影響。因此，各算法的參數設置如表2所示。

表2 主要參數Table 2 Main parameters

3.2 實驗結果與分析

為了充分驗證MDSGEO尋找平衡狀態的有效性及魯棒性，將MDSGEO 與加入正弦池策略（記為SEO）、加入自適應優先引力策略（記為GEO）、灰狼算法與布谷鳥算法混合（記為GWOCS）、SCA（sine cosine algorithm）[17]、MPA（marine predators algorithm）[18]和TSA（tunicate swarm algorithm）[19]進行對比。同時，為了保證對比的公平性，種群粒子數量N設為30，最大迭代次數設為500，總評估次數15 000。此外，所有算法在16 個基準測試函數上獨立運行30次，并取30 次的平均值和標準差作為最終的評估指標。具體實驗數據如表3～表5所示，其中Ave表示平均最優適應值，Std 表示標準差，最好的結果已加粗表示。

表3 30維實驗結果對比Table 3 Comparison of experimental results in 30 dimensions

表4 100維實驗結果對比Table 4 Comparison of experimental results in 100 dimensions

表5 固定維度實驗結果對比Table 5 Comparison of experimental results in fixed dimensions

由表3～表5 中數據可知：在D=30，D=100 和固定維度的條件下，由于MDSGEO同時具有GEO和SEO的優點，不僅可以更好地平衡勘探與開發關系，還增強種群進化信息加快算法收斂。因此，MDSGEO在F1、F5、F6、F9、F11上全部收斂到理論最優解，剩余函數上收斂精度最高。在F1～F6、F9、F11、F12上，GEO求解精度遠遠高于標準EO，其余函數上也具有明顯優勢，充分說明利用自適應優先引力策略豐富粒子進化信息增加粒子的信息交流，幫助粒子逃離局部最優快速收斂到全局最優的方法效果顯著。在F1～F6上，SEO 相比EO 求解精度呈指數級增長，在F7、F8、F10所得最優值精度更高，甚至在F6、F9、F11上求得理論最優值，這證明根據迭代進行階段采用融合增減機制和柯西分布的正弦池策略能夠實現種群粒子勘探與開發的動態平衡，將有助于粒子向著全局最優方向移動，提高尋得最優解的概率。此外，MDSGEO 可以最大限度減弱維度增加帶來的負面影響，在F1～F13上能取得更高質量的解。然而，TSA、GWOCS、SCA 和MPA 因其搜索模式中種群容易停滯更新出現早熟現象，陷入局部最優仍是它們急需解決的問題。尤其當D=100時，SCA在F3上與理論最優值相差1×105的精度。固定維度上，MDSGEO 求得的平均適應度值與其他算法相似，但其標準差反映出MDSGEO在F14～F15上比其他算法更穩定，GEO在F16上最穩定，其次是MDSGEO。

為進一步評估MDSGEO 的綜合性能，采用非參數估計Friedmam檢驗分析不同維度下各算法的尋優性能，實驗結果如表3～表5所示。其中，Avg.Rank表示Friedman檢驗所得的秩均值，Rank表示排名。秩均值越小說明算法性能越好，排名越靠前。在D=30，D=100 及固定維度的條件下，MDSGEO的秩均值最小且排名第一，從統計學角度證明了MDSGEO 的性能優于其他算法。同時，GEO 和SEO 的秩均值都比EO小，并且排名也在EO之前，再一次證明自適應優先引力策略和正弦池策略的有效性和魯棒性。

新改進算法需要進行顯著性分析，文中利用Wilcoxon 秩和檢驗來判斷MDSGEO 在統計上的顯著性[20]。MDSGEO與對比算法0.05的顯著性水平下進行比較，假設MDSGEO 為最佳算法，在MDSGEO vs GWOCS、MDSGEO vs TSA 等之間進行兩兩成對比較，結果如表6所示。其中，p-value<0.05認為拒絕零假設，表明兩對比算法之間存在顯著差異，符號“+”“-”和“=”分別表示MDSGEO 的性能優于、劣于和相當于對比算法，NA 表示算法獲得相同結果。從表6 最后一行結果可以得出，MDSGEO 與GWOCS、TSA、SCA、MPA、EO、SEO和GEO存在顯著差異，并且MDSGEO 的性能在多個函數上都要優于對比算法。

表6 基準函數Wilcoxon秩和檢驗的實驗結果對比Table 6 Comparison of experimental results of Wilcoxon rank sum test of reference functions

3.3 收斂性分析

圖1（a）～（h）為在D=30，迭代次數為500，評估次數為15 000 的條件下得到的函數平均收斂曲線圖。為了方便觀察算法收斂情況，將縱坐標取以10為底的對數。由圖1（a）～（h）能夠看出，隨著迭代進行，與標準EO相比，MDSGEO和GEO的收斂曲線下降快且收斂到較高精度的解，這說明通過自適應優先引力策略加入當前最優粒子，豐富種群粒子的進化信息，能夠有效幫助粒子增強逃離局部最優的能力，快速收斂到全局最優位置；同時，SEO 的收斂曲線下降速度僅次于GEO和MDSGEO，這證明通過正弦池策略中增減機制和柯西“長跳”特性，能推動粒子由勘探主導的尋優模式向開發模式過渡，動態平衡勘探與開發的關系，進一步幫助粒子向更好的方向收斂。另外，MDSGEO 進入迭代后期仍能持續尋優，未出現停滯現象，收斂速度最快且尋到的解精度遠高于其他算法，這離不開正弦池策略動態調節勘探與開發關系以及自適應優先引力策略豐富種群進化信息的幫助。MDSGEO 和GEO在F1、F5、F9上都尋到最優解，但MDSGEO用到評估次數更少，又一次說明融合正弦池策略和自適應優先引力策略的MDSGEO可以尋到最好的解。然而，標準EO和其他對比算法在迭代前期和后期收斂曲線平緩甚至出現不同程度的停滯狀況，進而導致出現早熟現象和求解精度低等問題。

圖1 平均收斂曲線Fig.1 Average convergence curve

結合表3～表5 和圖1 可以得出，無論是單峰可分、單峰不可分、多峰可分、多峰不可分、高維及固定維度，MDSGEO 在復雜函數上具備強勁的求解能力以及更快的收斂速度，驗證了所提策略的有效性和魯棒性。

3.4 與9種改進算法對比

為了展現MDSGEO 的競爭性，將其與改進的差分算法JADE[21]、jDE[22]、SaDE[23]、改進的人工蜂群算法MPGABC[24]、GABC[25]、MABC[26]、ABVCVSS[27]、DFSABC_elite[28]、改進的樽海鞘算法MSNSSA[29]進行比較。實驗選擇3.1節中的13個典型測試函數，函數維度設置D=30，各算法參數設置參照原文獻并讓每個算法獨立運行50次，所得實驗結果如表7 所示。由于原文獻中沒有對比函數的數據，故用“—”表示。表7中，JADE（adaptive differential evolution with optional external archive）、jDE（self-adapting control parameters in differential evolution）和SaDE（self-adaptive differential evolution algorithm）的數據來源于文獻[21]，MPGABC（modified gbest-guided artificial bee colony）的 數據源自文獻[24]，GABC

表7 與9種改進算法的實驗結果對比Table 7 Comparison of experimental results with 9 improved algorithms

（Gbest-guided artificial bee colony）、MABC（modified artificial bee colony）、ABCVSS（artificial bee colony algorithm with variable search strategy）和DFSABC_elite（novel artificial bee colony algorithm with depthfirst search framework and elite-guided search equation）的數據來自文獻[28]，MSNSSA（multi-subpopulation based symbiosis and non-uniform Gaussian mutation salp swarm algorithm）的數據源于文獻[29]。由表數據可知，MDSGEO在F1、F5、F6、F9、F11共5個函數上尋得最優解且魯棒性最好，相比其他9種改進算法具有顯著優勢。在F7、F10所得解的質量及魯棒性都優于其他改進算法。在剩余函數上，MDSGEO 的總體尋優遠高于其他改進算法。這表明MDSGEO不僅具有強大的尋優能力，也具備出色的競爭力。

3.5 與4種改進算法在CEC2017函數集上對比

為了進一步驗證MDSGEO 的尋優能力，采用更復雜的CEC2017 函數集來測試，其中No.2 的函數在CEC2017 函數集上被移除，即文中所用CEC2017 函數集僅有29 個。同時，將MDSGEO 與標準粒子群PSO（particle swarm optimization）[7]、改進粒子群FFPSO（hybrid firefly and particle swarm optimization）[30]、HPSOFF（hybrid particle swarm optimization algorithm and firefly algorithm）[31]和HFPSO（hybrid firefly and particle swarm optimization）[32]進行比較。為保證公平對比，對比數據和實驗參數設置與文獻[32]一致。函數維度D=10，種群粒子數量與函數維度一致，最大迭代次數為500，獨立運行20次，實驗最終結果記錄在表8中。

表8 CEC2017函數集上實驗結果對比Table 8 Comparison of experimental results on CEC2017

由表8可知，與PSO相比，MDSGEO在24個函數上的收斂精度更高，尤其在No.1函數上遠高于PSO；MDSGEO 在所有函數上獲得的收斂精度都優于FFPSO和HPSOFF；HFPSO僅在6個函數的收斂精度高于MDSGEO；與EO相比，除了No.1函數，MDSGEO的整體收斂精度更高。MDSGEO能夠在眾多先進算法中取得更高的優化精度，正弦池策略和自適應優先引力策略扮演重要角色，前者通過動態平衡算法的勘探與開發能力，提高算法的優化精度；后者豐富種群進化信息，加快算法收斂。另外，MDSGEO在所測29 個函數中，不僅在21 個函數上平均值優勢突出，而且Friedman 檢驗的結果也表明MDSGEO 秩均值最小且排名第一，再一次驗證MDSGEO性能更優。

4 工程優化問題

4.1 約束優化問題

約束優化條件與工程問題結合屬于一類常見的數學優化問題，該類問題通常很難求解，但因其在各科學領域被廣泛應用，所以研究這類問題具有重要的研究價值。約束優化問題定義如下：

其中，f為目標函數，hj(x)=0 是等式約束條件，gi(x)≤0 為不等式約束條件，X是實數Rn的子集且用來約束優化問題的搜索空間，若所求解滿足約束條件，則稱為可行解；反之，稱為不可行解。約束優化問題的難點在于搜索空間可行域的分布受約束影響，而優化過程中不僅需要考慮約束對這些分布影響，還需要考慮如何平衡約束和優化。

許多學者對約束優化問題都有研究，主要分為傳統方法和元啟發式算法兩大類。傳統方法包含文獻[33]提到移動漸進線法（method of moving asymptotes，MMA）、廣義凸近似（generalized convex approximation，GCA），來提高算法的收斂速度，但這類算法結構復雜不易實現；元啟發式算法有布谷鳥算法（cuckoo search algorithm，CS）[34]、礦山爆炸算法（mine blast algorithm，MBA）[35]、具有動態隨機選擇的差分進化（differential evolution with dynamic stochastic selection，DEDS）[36]、人工原子算法（artificial atom algorithm，AAA）[37]等，這類算法雖結構簡單，但算法的收斂精度不高且收斂速度慢。

為了解決上述問題，將MDSGEO 用來求解優化問題，證明其有效性和可行性。選用三桿桁架和懸臂梁設計帶約束的工程問題進行分析。

4.2 三桿桁架設計

三桿桁架，以使其重量最小化[34-35]。目標函數非常簡單，但是這個問題受到了很大的限制。結構設計問題通常具有很多約束。這里的約束是應力、撓曲和屈曲約束。

桁架的整體結構如圖2 所示，圖中L=100 cm、P=2 kN/cm2、σ=2 kN/cm2。選擇進行比較的算法有CS、MBA、Ray and Sain[38]、DEDS 和AAA，比較結果列于表9。

圖2 三桿桁架模型Fig.2 Three bar truss model

表9 三桿桁架實驗結果對比Table 9 Comparison of experimental results of three bar truss

表9中Max.eval.表示最大評估次數，N/A表示原文獻未說明評估次數。由表9 可知，MDSGEO 算法提供了非常有競爭力的結果，其獲得最佳解決方案。MDSGEO 不僅能夠有效解決實際的約束問題，而且相同評估次數下MDSGEO能夠找到最優設計權重263.895 843，這比其他算法要少。

4.3 懸臂梁設計

懸臂梁包括5 個橫截面為正方形的空心元件。如圖3 所示，梁的自由端（節點6）上也施加了垂直載荷，梁的右側（節點1）受到了剛性支撐。其目的是使梁的重量最小。在最終的優化設計中，還存在一個不應違反的縱向位移約束。問題表述如下：

圖3 懸梁臂模型Fig.3 Cantilever model

將MDSGEO 和EO 分別對懸臂梁設計求解最優值，并與m-EO（modified equil optimizer）[11]、SOS（symbiotic organisms search）[34]、CS、MMA、GCA_I[33]進行比較。表10所用符號表示與表9一致。表10的優化結果反映出MDSGEO 優于其他算法。這顯示了MDSGEO在逼近此問題的全局最優值方面擁有出色的性能。

表10 懸梁臂實驗結果對比Table 10 Comparison of experimental results of cantilever

5 結束語

為提高標準平衡優化器算法全局尋優能力，本文提出MDSGEO 算法。在種群粒子初始化后，利用正弦池策略自適應平衡勘探與開發，提高算法尋優精度。此外，通過自適應優先引力策略加速粒子收斂到全局最優。同時將平衡優化器算法應用于多類型基準函數及CEC2017 函數集進行尋優，使用平均值和標準差等指標進行評估以及非參數統計Friedman檢驗、Wilcoxon秩和檢驗進行統計驗證算法的有效性和魯棒性。最后，利用兩個帶約束的工程優化問題測試算法的全局尋優能力。研究結果表明，改進平衡優化器算法不僅能夠自適應平衡勘探與開發，而且尋優能力更強。未來研究方向準備將MDSGEO應用于多目標的工程優化及高維的特征選擇領域。