基于黃金萊維引導機制的阿基米德優化算法

陳 俊，何慶，李守玉

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

0 引言

近年來隨著科學技術，特別是電子信息技術的飛速發展，全局優化方法在電力調度［1］、控制工程［2］、圖像處理［3］、生物醫學信號處理［4］等眾多領域的應用越來越廣泛；然而對于非線性以及目標函數不可導的全局優化問題，傳統的優化方法很難在合理時間內解決。利用類似仿生學原理，將自然、動物的一些現象抽象成的算法——元啟發算法［5-13］為解決復雜全局優化問題提供了一種新途徑。該類方法對目標函數性質要求低、容易實現、穩定性好，受到國內外學者的關注。

阿基米德優化算法（Archimedes Optimization Algorithm，AOA）是2020 年由Hashim 等［14］提出的一種新型啟發式智能優化算法。該算法靈感來源于浸入流體中的物體與物體所受浮力的關系，個體通過不斷調整自身密度和體積，使物體達到平衡狀態，其中調整的過程即是種群尋優過程，達到平衡狀態的個體即是全局最優解。相較于其他算法，AOA 局部搜索能力強、收斂速度快，但是仍存在很多不足：首先在迭代中后期算法不斷圍繞著全局最優位置的尋優方式，導致算法容易陷入局部最優，且全局搜索能力差；其次在搜索過程中，算法很難從個體信息上獲取收益。

針對上述存在問題，本文提出了一種多策略阿基米德優化算法（Multi-Strategy improved AOA，MSAOA）。首先，利用變區間初始化策略來過濾搜索空間中冗余信息，以保證初始解的質量；其次，提出黃金萊維引導機制，擴大個體在迭代后期的搜索范圍，以提高算法跳出局部最優的能力；最后，根據個體自身適應度值動態調整搜尋半徑，在密度下降因子中引入自適應波長算子，提高AOA 的收斂速度。20 個經典測試函數和Wilcoxon 秩和檢驗測試的實驗結果表明，所提算法性能優于原始算法，并通過4 個機械設計實例證實了所提算法可行性和有效性。

本文主要工作包括以下3 點：

1）提出了變區間初始化策略，提取和過濾搜索空間中的有用信息以保證初始種群向全局最優解靠近。

2）提出了黃金萊維引導機制，有效提高了種群多樣性，增強了算法跳出局部的能力。

3）提出了自適應波長算子，并將其融入密度因子中，有效增強了個體的學習效率，以提高算法的尋優精度。

1 阿基米德優化算法

阿基米德優化算法（AOA）是一種基于種群的優化算法，設計靈感來自阿基米德定理。該原理指出，當物體完全或部分浸入流體中時，流體給物體施加的浮力大小與排出液體的質量（體積）成正比［15］：若物體受到的浮力等于排出液體質量時，視為該物體處于平衡狀態，如式（1）所示。假設許多物體浸沒在同一種流體中。每個物體都試圖達到平衡狀態。浸沒的物體有不同的密度p和體積v，從而導致不同的加速度a。

其中：b 表示為流體，o 表示為物體個體。根據式（1）可將物體的加速度公式表示為式（2）：

假如物體o 與另一個鄰近物體r 的碰撞，導致當前物體的平衡狀態將受到鄰近物體的影響，則當前物體的平衡狀態將為：

與其他的元啟發式算法一樣，AOA 以隨機初始化物體的密度、體積和加速度開始搜索。在評估了初始種群的適應度后，AOA 進行迭代更新，直到終止條件滿足。在每次迭代中，AOA 會根據個體與其他鄰近個體是否發生碰撞選擇位置方式，并更新個體自身屬性。更新后的密度、體積、加速度決定了下一代個體的新位置。以下是AOA 步驟的詳細數學表達式。

在初始化階段，AOA 會隨機初始化每個對象的體積（vol）、密度（den）、加速度（acc）。在此過程中，AOA 將評估初始種群，選取當前最優個體（xbest）、最優個體的密度（denbest）、體積（volbest）、加速度（accbest），用于其他個體密度、體積和加速度的更新。

式中：和為在t代中第i個和i+1 個體的密度和為在第t代中第i個和i+1 個個體的體積；rand∈(0，1)的隨機數。

根據浸透在液體中的物體是否發生碰撞，AOA 將其分為全局探索和局部搜索階段。若未發生碰撞，AOA 進行全局探索階段；反之，進行局部開發階段。通過設置遷移算子（Transfer Factor，TF），用于對兩個階段的切換，其定義如下：

式中：t和tmax分別表示當前迭代次數和最大迭代次數。

不同階段對應不同加速度更新公式。當TF≤0.5，AOA進行全局搜索，個體的加速度進行更新方式為式（6）：

當TF＞0.5，AOA 進行局部開發。個體的加速度進行更新方式為式（7）：

為了規范個體的更新步長范圍，AOA 將對個體的加速度進行歸一化操作，如式（8）所示：

在全局搜索階段，個體位置根據式（9）進行位置更新：

在局部開發階段，個體位置根據式（11）進行位置更新：

式中：C2為固定常數；F為方向因子，用于決定迭代的位置更新方向，其定義為：

其 中：P=2rand-C4，C4為固定常 數；T=C3×TF，且T∈［0.3C3，1］，C3為固定常數。

2 多策略阿基米德優化算法

2.1 變區間初始化策略

初始化種群的好壞一定程度上決定了算法的性能，初始種群在解空間中的細微不同，都可能影響算法進化方向。AOA 的初始種群在搜索空間中隨機產生，導致初始種群分布不均勻，搜索范圍有限。為了解決以上問題，獲得好的初始種群，本文利用變區間初始化策略來提取搜索空間中有用信息以保證種群向全局最優解靠近。

對于優化問題：

式中：LB（Lower Bound）表示搜索空間中的搜索下限；UB（Upper Bound）表示搜索空間中的搜索上限。變區間初始化策略對就是通過不斷縮短[LB，UB]，將初始種群逼近到式（13）中近似最優解的附近。

首先在中間取一個中點l。

生成兩個個體：

式中a和b分別為：

計算f（x1）和f（x2）并比較它們大小，若f（x1）＞f（x2），則有x*∈［l，UB］，從而將潛在的最優解位置收縮到［l，UB］內；然后依次迭代，不斷縮短搜索區間，并將搜索空間［LB，UB］分割成n-1 個子區間，把初始種群聚集到問題（13）的最優解附近。具體步驟參見算法1。

算法1 變區間初始化策略偽代碼。

2.2 黃金萊維引導機制

在AOA 中，當遷移算子TF＜0.5 時，AOA 進入全局開發階段。由遷移算子定義可知TF∈(0.36，1]，并且遷移算子會隨迭代次數線性增長。該現象導致絕大部分迭代圍繞著最優個體進行位置更新，引導個體朝向最優個體方向移動；然而當最優個體陷入局部最優時，很容易導致算法出現搜索停止的現象。為了加強AOA 跳出局部最優的能力，本文提出黃金萊維引導機制。

在凸優化理論中，AOA 收斂的關鍵之一是其步長應當滿足適定性［16］，即：步長較大會使得算法搜索精度低且收斂后期出現震蕩現象；步長較小會導致搜索速度低，且不易跳出局部最優。萊維步長［17］是一種服從萊維分布的隨機游動，其短距離與較長距離步長相間的特性，使得在未知范圍內搜索時，能夠達到更大范圍，從而有助于算法跳出局部最優。步長s的計算公式為：

其中μ和ν服從正態分布：μ～N(0，σ2μ)，ν～N(0，σ2ν)。

式中：σν通常取1；Γ（β）是Gamma 函數。根據文獻［18］可知，β取值影響萊維飛行步長軌跡，β取值越大，局部開發能力越強。

其次，本文引入正弦函數與單位圓之間的關系［19］，使得種群能遍歷正弦函數上的所有點，即單位圓上的所有點。個體位置更新公式為：

式中：R1∈［0，2π］的隨機數，R1和萊維步長s共同決定搜索半徑；R2∈［0，π］的隨機數，決定個體的位置更新方向；θ1和θ2是引入的黃金分割系數τ，其目的是縮小搜索空間，使得算法在每次迭代都會對能產生優秀解的區域進行充分搜索，從而加快了算法收斂速度。公式中具體參數表達式如下所示：

最后，雖然對目標個體使用黃金萊維引導機制，能讓算法跳出局部最優，但并不能保證新的個體位置優于原目標個體位置，因此在引導機制后加入貪婪機制，通過比較個體位置更新前后個體適應度后再決定是否更新目標位置，以保留適應度較好的個體。貪婪機制具體操作表達式如下：

2.3 自適應波長算子

受到浸泡在液體中運動物體會導致水平面發生波動現象啟發，本文提出了自適應波長算子：達到自身平衡（適應度較好）的個體，引起波動較小，從而具有較長的波長；還遠未達到自身平衡（適應度較差）的個體運動會引起的較大波動，從而具有較短的波長。

在AOA 中，由于缺乏多樣性的操作，當AOA 進化到一定的程度時，導致AOA 很難從自身適應度獲取收益。因此結合浸泡在液體中運動物體的物理現象，本文提出自適應波長算子增強個體學習效率，提高算法尋優精度。

式中：λi表示第i個體運動引起的波長系數；f（Xi）表示當前迭代中第i個個體的適應度值；fmin和fmax分別表示當前迭代中最優適應度值和最差適應度值；α為衰減因子，ε為一個非常小的有理數，以防止分母為0 的情況。最后將自適應波長系數融合到密度因子，得到新密度因子更新公式為：

式中表示在t+1 代中第i個個體的密度因子。新的密度因子的大小會根據個體自身適應度動態變化：適應度接近最優適應度的個體，AOA 保持原來的密度因子的性質；而適應度較差的個體，密度因子接近最大值，使當前個體擁有較長的步長，快速向最優解靠近。

2.4 MSAOA時間復雜度

時間復雜度從理論上反映算法的收斂速度，在AOA 中，假設參數初始化（最大迭代次數為M，種群規模為n，空間維度d等參數），求解目標的適應度函數時間為f（d），由文獻［14］可知，AOA 時間復雜度為O（M（n×f（d））），MSAOA 的時間復雜度與AOA 相同，分析如下。

初始化階段 假設種群初始化參數比之前多x1，且變區間初始化策略時間復雜度O（n×f（d）），則MSAOA 種群初始階段的時間復雜度為：

黃金萊維引導機制階段 假設每一維度計算levy（λ）需要的時間為x2；生成隨機數需要的時間為x3；根據式（19）需要的時間復雜度為O（2f（d）），則該策略需要的時間復雜度為：

引入自適應波長算子后的時間復雜度與AOA 基本相同。綜上MSAOA 的時間復雜度為：

2.5 AOA的實現流程

本文所提算法MSAOA 的流程如圖1 所示。

圖1 MSAOA流程Fig.1 Flowchart of MSAOA

3 數值實驗與結果分析

為了全面驗證本文改進策略的有效性和魯棒性，以及改進后算法的性能。本文驗證實驗分為3 個部分進行。

1）將MSAOA 與不同改進策略進行對比，驗證改進策略的有效性；

2）將MSAOA 與其他群智能算法進行對比實驗，再次驗證MSAOA 的有效性；

3）通過Wilcoxon 秩和檢驗驗證本文算法與其他對比算法之間的差異顯著性。

實驗引入20 個基準函數，分為3 類：第1 類為單峰基準測試函數，表1 中F1～F7 所示；第2 類為多峰基準測試函數，如表1 中的F8～F14 所示；第3 類為固定維度的多峰基準測試函數，如表1 中的F15～F20 所示。

表1 基準測試函數Tab.1 Benchmark test functions

算法的基本參數：種群規模為30，最大迭代次數為1 000，算法內參數如表2 所示。

表2 算法內參數Tab.2 Parameters in algorithms

3.1 與不同的改進策略對比

為了驗證本文所提算法和每個改進點的效果，將多策略阿基米德優化算法（MSAOA）與阿基米德優化算法（AOA）、僅加入變區間初始化策略的阿基米德優化算法（AOA1）、僅加入自適應波長算子的阿基米德優化算法（AOA2）以及僅加入黃金萊維飛行引導機制的阿基米德優化算法（AOA3），同時在20 個經典基準測試函數下對比實驗，進而客觀地反映算法改進的有效性。

首先，為了體現實驗的準確性能，圖2 所示的6 個測試函數運行30 次的平均收斂曲線，其中縱坐標取10 為底的對數。通常采用單峰值函數（F1、F3、F6）來評價算法的開發能力，多峰值函數（F8、F10、F11）來評價算法的全局探索能力。由于加入黃金萊維引導機制，AOA 更容易跳出局部最優，所以MSAOA 的收斂速度和收斂精度上都優于其他算法，進而驗證了改進策略的有效性。

圖2 基準函數的平均收斂曲線Fig.2 Average convergence curves of benchmark functions

其次，表3 中最優值和標準差分別反映算法的尋優能力以及穩定性和魯棒性。

表3 基準測試函數上的測試結果Tab.3 Test results on benchmark test functions

從表3 縱向來看，在除去F12 外的單峰值函數，MSAOA均能找到理論最優值，且標準差最小。對于函數F7，MSAOA雖然沒有達到理論最優值，但是MSAOA 的性能指標均優于其他算法。對于7 個多峰值函數，算法的求解精度相較于單峰值函數有所下降。MSAOA 在求解多峰值函數時，其中F8、F10、F11 達到理論最優值，且穩定性最好。對于其余多峰值函數，MSAOA 尋優精度以及穩定性上都優于AOA，客觀說明MSAOA 能有效幫助算法跳出局部最優，擁有更強的全局搜索能力。對于固定維度函數，MSAOA 的平均值更接近理論最優值，同時MSAOA 的標準差明顯優于AOA。縱向來說，3個改進策略對算法性能都有一定程度上的提升，其中僅加入黃金萊維飛行策略的阿基米德優化算法（AOA3）表現最為突出，引入自適應波長算子的阿基米德優化算法（AOA2）其次，結合變區間初始化策略的阿基米德優化算法（AOA1）次之。綜合MSAOA 在表3、4 以及圖2 上的表現，證明MSAOA 在多種基準函數上的求解效果，具有較強的尋優能力。

3.2 與其他群智能算法進行比較

將MSAOA 與粒子群優化（Particle Swarm Optimization，PSO）算法、灰狼優化算法（Grey Wolf Optimizer，GWO）、正余弦算法（Sine Cosine Algorithm，SCA）和均衡器算法（Equilibrium Optimizer，EO）進行性能比較，結果如表4 所示。對該五種算法在最大迭代次數為500、空間維度為100、種群規模為30 條件下進行仿真實驗。由表4 可知，MSAOA在單峰基準函數的表現均優于其他算法，達到了顯著的優化效果。在多峰函數中，對于尋優難度較大的F12，MSAOA 穩定性不如最新的均衡器算法（EO）；然而，對于具有許多局部極小值點的F10 以及多模態函數F13，均達到了一定數量級的優化效果，并且在具有強烈震蕩的復雜多模態函數F9 和F11 中，均取得理論最優值。最后在固定維度函數中，F17～F19 優化效果稍遜于均衡器算法（EO）。MSAOA 對于其他的固定維度測試函數上的優化效果仍然相對較好。

表4 所提算法與四種群智能算法結果比較Tab.4 Comparison of results of the proposed algorithm and four swarm intelligence algorithms

綜上所述，本文提出多策略改進的阿基米德優化算法求解精度高、魯棒性強和收斂較快，取得了相對較好的優化效果，提高了原始阿基米德優化算法的優化效率。

3.3 Wilcoxon秩和檢驗

本文采用Wilcoxon 秩和檢驗驗證MSAOA 與其他算法的顯著性差異。每次運行結果在p=5%的顯著性水平下，當p值小于5%時，拒絕H0 假設，說明兩種算法的差異性顯著，否則就是接受H0 假設，說明兩種算法在整體上是相同的。由于算法不能和自身比較，所以表5 中的標記為“NaN”表不適用，無法進行顯著判斷；“R”為顯著性判斷結果；“+”“-”“=”分別表示MSAOA 的性能優于、劣于和相當于對比算法的次數。從表5 中可以觀察到大部分的p值是小于5%，因此表明該算法的性能在統計上是顯著的，從而表明MSAOA 比其他算法擁有更好的優越性。

表5 基準函數上Wilcoxon 秩和檢驗p值Tab.5 p-values for Wilcoxon rank-sum test on benchmark functions

4 機械優化實例及結果分析

優化設計是20世紀60年代發展起來的一門新學科與設計方法。在實際機械設計中，某一類具體的實際問題都有其特定應用場合，表現出其特點以及復雜性。絕大多數機械問題與數學模型有著緊密聯系，其中設計變量的選擇、目標函數以及約束條件的確定是構造優化設計數學模型的主要步驟。該類問題的數學模型一般可以描述為如下帶約束優化問題［20］：

在機械優化設計中，常常會遇到這一類數值優化問題。因此本文將提出的MSAOA 用于求解機械優化設計問題上，以驗證MSAOA 在工程應用中的有效性和可行性。選取焊接梁的設計問題［21］、壓縮彈簧的設計問題［22］、壓力管道設計問題［23］和懸臂梁設計問題［24］作為工程算例進行分析。

為了體現比較的公平性，MSAOA 與粒子群優化（PSO）算法、引力搜索算法（Gravitational Search Algorithm，GSA）、生物地理學優化（Biogeography-Based Optimization，BBO）算法、差分進化（Differential Evolutionary，DE）算法、蟻群優化（Ant Colony Optimization，ACO）算法、樽海鞘群算法（Salp Swarm Algorithm，SSA）、正余弦優化算法（SCA）、AOA 進行對比實驗時，各算法外基本參數設置相同，種群的規模N=30 和最大迭代次數M=1 000，獨立運行30 次。

4.1 焊接梁設計問題

該問題以如圖3 所示的焊接梁為研究對象，優化目標是使制造總成本最低。

圖3 焊接梁設計問題Fig.3 Welded beam design problem

該問題共包含4個決策變量：焊縫寬度h、長度l、橫梁寬度d、厚度b，分別表示為x1、x2、x3、x4；包含7 個約束條件如式（30）所示：剪切應力τ、橫梁彎曲應力σ、屈曲載荷Pc、橫梁撓度δ以及各設計變量之間尺寸約束，具體數學約束方程表示如下：

MSAOA 與其他算法的實驗結果如表6 所示。從表6 中可知，MSAOA 對該問題的優化效果要優于其他的8種算法。

表6 九種不同算法求解焊接梁設計問題的對比Tab.6 Comparison of 9 different algorithms for solving welded beam design problem

4.2 壓縮彈簧設計問題

該問題以如圖4 所示的壓縮彈簧為研究對象，優化目標是在受到最小偏差（g1）、剪切應力（g2）、沖擊頻率（g3）、外徑限制（g4）和設計變量的條件下，盡可能減少彈簧重量。

圖4 壓縮彈簧設計問題Fig.4 Compression spring design problem

該問題共包含3個決策變量，分別是線徑d（x1）、平均線圈直徑D（x2）及有效線圈數P（x3）。式（36）為不等式約束條件：

其中：0.05 ≤x1≤2.00，0.25 ≤x2≤1.30，2.00 ≤x3≤15.0。

MSAOA 與其他算法的實驗結果如表7 所示。從表7 中可知，MSAOA 對該問題的平均值和標準差最小，優化效果優于其他8 種算法。

表7 九種算法求解壓縮彈簧設計問題的對比Tab.7 Comparison of 9 algorithms for solving compression spring design problem

4.3 壓力管道設計問題

根據壓力管道平面結構圖5，該問題設計目標為最小化費用總成本。

圖5 壓力管道設計問題Fig.5 Pressure piping design problem

式中：x1（殼體厚度Ts）、x2（頭部厚度Th）、x3（內半徑R）、x4（圓柱體長度L）。該問題的約束方程如下所示：

對獲取最佳解決方案的不同算法進行比較，從表8 可知，MSAOA 與其他算法相比，平均值優于其他8 種算法，其次標準差遠小于其他8 種算法，表現出極強的穩定性。

表8 九種算法求解壓力管道設計問題的對比Tab.8 Comparison of 9 algorithms for solving pressure piping design problem

4.4 懸臂梁設計問題

根據懸臂梁平面結構（圖6），該問題受到不同單元梁高度或寬度的約束，設計目標為盡可能減小懸臂梁矩形截面的重量。其數學模型如下：

圖6 懸臂梁設計問題Fig.6 Cantilever beam design problem

式中：f（x）為最小化懸臂梁矩形截面的重量，設計變量xi表示5 個不同單元梁的高度或寬度。

表9 是MSAOA 與其他算法獲取最優解的對比實驗結果。

表9 九種算法求解懸臂梁設計問題的對比Tab.9 Comparison of 9 algorithms for cantilever beam design problem

從表9 中可以明顯地看出，MSAOA 獲取的平均值和標準差都小于對比算法，具有較高的收斂精度和較強的魯棒性。

5 結語

為了解決AOA 存在的問題，本文提出了一種多策略阿基米德優化算法（MSAOA）。首先，提出了變區間初始化策略，為算法的迭代奠定良好基礎；其次，提出了黃金萊維引導機制，加強了AOA 跳出局部最優的能力；最后，提出自適應波長算子，提高個體學習效率。將本文算法與主流算法在20 個基準測試函數以及部分CEC2014 函數上進行比較，使用數值分析、收斂性分析、Wilcoxon 秩和檢驗對實驗結果進行評估。評估結果表明，本文算法有效，具有更高的尋優精度和收斂速度，與對比算法差異性顯著；將本文算法應用于4 個機械設計實例中，再次驗證了MSAOA 的有效性和優越性。下一步工作可圍繞著兩個方面進行：將本文算法改進思想應用在其他元啟發式算法中，驗證本文改進策略的泛化能力以及有效性；將MSAOA 應用在機器學習參數優化和智能電網參數優化當中，為解決參數優化問題提供一個新途徑。