大規模黑箱優化問題元啟發式求解方法研究進展

江璞玉，劉均，周奇，程遠勝*

1 華中科技大學 船舶與海洋工程學院，湖北 武漢 430074

2 華中科技大學 航空航天學院，湖北 武漢 430074

0 引 言

船舶優化設計是業界十分關注的問題之一，例如船舶水動力性能的優化[1-2]、艙段結構優化[3-4]、聲性能優化[5]等。船舶優化設計的目標函數或約束條件通常是由數值仿真方法（例如計算流體動力學（CFD）方法、有限元方法（FEM）、邊界元方法（BEM）等）計算得到，一般具有如下顯著特點：一是無法采用顯式解析式得到；二是計算時間較長。學界將具有前者特點的優化問題稱為黑箱（black-box）優化問題，后者稱為昂貴優化問題。通常，將單一目標約束優化問題定義如下：

式中，y=f(x)為 目標函數，x=(x1,···,xd)為設計變量，下標d表示設計變量的維度；gi(x)，hj(x)分別為第i個不等式約束和第j個等式約束；n，m分別表示不等式約束和等式約束的個數。

由于約束優化問題可以通過懲罰函數法（penalty function method, PFM）、拉格朗 日 乘子(Lagrange multiplier)法等轉化成無約束優化問題，故不失一般性，本文主要討論單一目標無約束優化問題。

對于黑箱優化問題，式（1）中的目標函數或約束函數解析式與梯度無法獲得，傳統的基于梯度的優化方法不再適用于黑箱優化問題的直接求解。而元啟發式算法（meta-heuristic algorithm）通過對決策空間的部分子集進行采樣來搜索優化解，具有不需要目標函數的梯度信息和適用性廣等特點[6]，故成為了解決黑箱優化問題的有效途徑。其中，代表性的元啟發式算法有遺傳算法（genetic algorithm, GA）[7]、差分進化（differential evolution, DE) 算法[8]、粒子群算法(particle swarm optimization, PSO)[9]、進化策略（evolutionary strategies,ES）[10]等。圖1 所示為元啟發式算法的流程圖。

圖1 元啟發式算法流程圖Fig. 1 Flowchart of meta-heuristic algorithm

如果黑箱優化問題設計變量的維度很高，則稱之為大規模黑箱優化問題（large-scale black-box optimization problem, LBOP），例如，大型船舶的中剖面優化、艙段結構優化。對于求解LBOP 問題，若以各板列板的厚度、骨材間距和骨材型號作為設計變量，可能會有成百上千的設計變量，就目前而言，求解包括了如此多設計變量的優化問題將非常具有挑戰性。鑒于黑箱優化問題的特性，元啟發式算法仍然是優秀的求解算法之一。然而，對于求解LBOP 問題，在低維優化問題上表現優異的大部分算法的性能下降十分嚴重。其原因是，隨著維度的增加，設計空間體積也隨之呈指數增長。若設計方案的目標函數評價沒有達到足夠的次數，現有優化算法就很難對如此巨大的空間進行充分探索。關于設計變量的維度達到多少可定義為大規模優化問題，目前尚無定論。但對于進化計算，一般認為設計變量的維度達到1 000～5 000 即可定為LBOP 問題[11]。

可見，提出高效求解LBOP 問題的元啟發式算法，對于提高船舶優化設計效率、縮減設計周期以及提升設計質量都具有重大意義。本文擬對目前處理LBOP 問題的元啟發式算法進行總結分析，提出未來可能的研究方向或重點，以便為相關領域感興趣的學者提供參考。

1 處理大規模優化問題的方法

一般地，根據是否基于分解策略方法來處理LBOP 問題，可以將元啟發式算法分為兩個大類，表1 列出了歸納匯總的相關文獻，下文將分別對這兩個大類算法中的代表性算法進行綜述。

表1 大規模黑箱優化問題元啟發式算法研究文獻匯總Table 1 Summary of research advances using meta-heuristic algorithms for LBOPs

1.1 不使用分解策略的方法

此類方法中將LBOP 問題作為一個整體來處理，通常是結合局部搜索、縮減搜索空間、改進進化算子等途徑來克服LBOP 問題引起的各種困難。具有代表性的是MA-SW-Chains 算法[40]，該算法曾在IEEE CEC 2010 年年會LBOP 問題競賽中獲獎，性能十分優秀。MA-SW-Chains 算法也是對MA-CMA-Chains 算法[41]的改進，屬于文化基因算法（memetic algorithm，MA），通常是指進化算法(evolutionary algorithm，EA) 和 局 部 搜 索 的 混 合體。MA-SW-Chains 算法在GA 中使用了SW (Solis-Wets)算法[119]作為局部搜索方法，通過建立不同的局部搜索鏈，給種群中每個個體分配一個取決于其特征的局部搜索強度，以此提高算法對LBOP問題的優化性能。而不使用分解策略的元啟發式算法又主要分為EA 算法和群智能算法(swarm intelligence algorithm，SIA) 兩類，其中又以DE 和PSO 為兩個代表性算法。下文將主要介紹基于DE 和PSO 算法的元啟發式算法。

1.1.1 基于DE 的改進算法

DE 算法是EA 算法中的典型算法之一，其一般流程如圖2 所示。

圖2 差分進化算法流程圖Fig. 2 Flowchart of differential evolution algorithm

DE 算法因其良好的全局搜索能力和易于使用的特點，成為了被研究的熱門算法。事實上，圖1所示流程也是絕大多數EA 算法的流程，只需要將DE 算子變為其他的進化算子來產生后代即可。DE 算法的核心操作在于交叉和變異算子(crossover and mutation operator)，大 部 分 對DE 的改進都著重改進交叉和變異算子，以此增強處理LBOP 的能力。例如，擁有可選外部庫的自適應差分進化（adaptive differential evolution with optional external archive，Jade）算法就是對DE 算法的改進[12]，其框架與基本DE 框架大體相同。與后者相比，Jade 算法增加了額外的樣本庫A，用以存儲進化過程中被淘汰的個體。Jade 算法改進了基本DE 的變異算子，將其改為如下形式：

Takahama 等[13]提出了一種函數模態檢測方法，通過在種群中心點和最佳個體形成的直線上進行采樣，以此來判斷該直線上的目標函數是單峰還是多峰，并根據判斷結果自適應地調整DE變異算子中縮放因子的值。Brest 等[14]提出的自適應差分進化算法（self-adaptive differential evolution algorithm, SaDE）使用種群規模縮減技術，根據隨機選取的向量適應度值，可以以一定概率改變縮放因子的符號。Wang 等[15]提出的量化正交交叉DE 算法首先量化兩個父代個體的搜索范圍，再根據量化結果調整交叉和變異算子中各參數因子的值。Zamuda 等[16]還提出了一種使用對數正態自適應控制參數的合作協同差分進化（differential evolution combined with cooperative coevolution）算法。Yang 等[17]則在研究分析以往的自適應方法，并結合其他方法優點的基礎上，提出了一種通用的差分進化參數自適應框架。徐廣治[18]提出了多級擾動的DE 算法，該算法利用隨機正態分布對個體最優解進行擾動，以此來增加種群多樣性。關于改進DE 算法進化算子的研究還有文獻[19-21, 28]等，限于篇幅，這里不再贅述。

除上述著重于改進DE 算子的研究外，其他研究還包括注重DE 算法與其他算法混合使用[42-43]，以及改變原有的單一種群進化機制[22-23]等。

1.1.2 基于PSO 的改進算法

SIA 算法是與EA 算法類似的另一種元啟發式算法，其中PSO 算法是SIA 算法的代表性算法。圖3 所示為經典的PSO 算法流程圖。

圖3 粒子群算法流程Fig. 3 Flowchart of particle swarm optimization

在PSO 算法中，粒子的位置和速度更新手段是該算法的核心。改進方向也都集中于此。Yang等[29]還提出了一種PSO 算法的變體——基于層次的學習粒子群算法（level-based learning swarm optimizer, LLSO），該算法中種群按照其適應度值的大小進行排序，并分成多個層級，其中，除最好一層的粒子直接進入下一代之外，其他粒子的位置和速度按式（3）更新。

此外，LLSO 算法還包括一種自適應調整層數和控制參數 φ的可動態變化的基于層次學習粒子 群 算 法（dynamic level-based learning swarm optimizer，DLLSO）[29]。Hsieh 等[30]提出基于高效種群利 用 策 略 的 粒 子 群 (efficient population utilization strategy for particle swarm optimization, EPUS-PSO)算法，定義了種群管理器和解共享策略。其中，種群管理器能夠自適應地根據當前優化情況去除種群中的冗余粒子或增加新粒子，而在解共享策略中，將標準PSO 算法速度更新方程的第3 項——個體歷史最優位置（pbest），按一定的概率改變為另一個粒子的個體歷史最優位置。同時，作者還提出了一種搜索范圍的共享策略，用于跳出局部最優解。

García-Nieto 等[31]提出了采用速度調整和重啟策略的PSO 算法，該算法中的速度調整策略用于控制粒子在有限區域內定向運動，而重啟策略用于防止出現早熟問題，若整個種群中粒子適應度標準差或目標函數值總體變化非常低，則執行重啟策略。Cheng 等[32]使用基于成對的隨機競爭機制的競爭粒子群算法(competitive particle swarm optimizer，CSO)來求解LBOP 問題。在算法的每輪優化中，從當前種群中隨機選擇粒子開展競爭，獲勝粒子被傳遞到下一種群中，通過向獲勝粒子學習，更新失敗粒子的下一個位置及其速度。

周建宏[33]提出了通過對搜索的子空間進行疊加來覆蓋整個搜索空間的頻繁覆蓋策略，并將該策略與隨機漂移粒子群優化算法和具有量子行為的PSO 算法的變體相結合。Chu 等[34]對高維復雜優化問題中的隨機、吸收和反射3 種邊界處理方法進行了分析比較。Tian 等[36]基于CSO 算法提出了一種新的兩階段粒子位置的更新策略，用于處理大規模多目標優化問題，其效率優于基于問題 的 轉 換 算 法（problem-based transformation algorithm）、基于決策變量聚類的算法（decision variable clustering-based algorithm）、PSO 算法和分布式 估 計 算 法（estimation of distribution algorithm,EDA）等。

Deng 等[39]根據學習者與榜樣間適配度差最大化的原理，提出了一種改進PSO 算法，即RBLSO（ranking-based biased learning swarm optimizer)算法，該算法含排名配對學習（ranking paired learning，RPL）和偏心學習（biased center learning，BCL）兩種學習策略。其中：RPL 策略是讓較差粒子根據其排名從較好粒子中對等學習，以加快收斂速度；BCL 策略是讓每個粒子都向整個種群的適應度加權中心（偏置中心）學習，以加強算法的探索能力。

Huang 等[37]提出了用于控制PSO 算法收斂速度的策略，當檢測到算法收斂速度過快或過慢時，自適應地調整算法的收斂速度。計算結果表明，該策略可以幫助PSO 算法在收斂速度與種群多樣性間保持平衡。Wang 等[38]提出的DGLDPSO(dynamic group learning distributed particle swarm optimization) 算法是將整個種群分為若干組，通過“主-從”分布式模型共同進化，該算法采用動態組學習策略（dynamic group learning，DGL）平衡多樣性和收斂性。此外，DGLDPSO 算法被應用到了大規模云的工作流調度優化中，作者結合資源特性還進一步提出了自適應重編號策略（adaptive renumber strategy，ARS）。

總之，相比于基于DE 的方法，基于PSO 的方法收斂速度通常更快，但更易陷入局部最優。

1.1.3 其他算法

除了DE 和PSO 分別作為EA 及SIA 算法的典型算法得到了大量研究外，還有研究將其他算法改進后用于提升所研算法求解LBOP 問題時的性能。例如，協方差矩陣自適應進化策略（covariance matrix adaptation evolution strategy，CMA-ES）[120]在處理中、低維問題時有著卓越的性能，但在處理LBOP 問題時，隨著維度的增加，協方差矩陣計算復雜度也隨之迅速增加。因此，Ros 和Hansen[44]提出了sep-CMA-ES 算法，該算法只計算協方差矩陣的對角元素，以降低計算復雜度，即計算復雜度僅隨問題的維度線性增加，從而解決了CMAES 算法在處理高維問題時的可用性。但是，Omidvar 等[121]將sep-CMA-ES 算法與幾種CCEA 算法進行比較后，發現當LBOP 問題的維度增加時，sep-CMA-ES 算法的性能明顯下降。為此，Li 等[49]提出了一種CMA-ES 算法的快速變體，通過使用一個低階矩陣與幾個向量逼近協方差矩陣，并使用其中2 個向量生成新解，實現了計算復雜度隨問題的維度線性增加，試驗結果表明其優于其他CMA-ES 優化算法的變體。

除了上述文獻研究總結得到的方法外，還有大量未使用分解策略的元啟發式算法。例如，多重 軌 跡 搜 索（multiple trajectory search，MTS）[46]、LSEDA-gl （EDA for large scalar global optimization）[47]、基于對立的差分進化（opposition-based differential evolution，ODE）[24]、SOUPDE （shuffle or update parallel differential evolution）[25]、改進社會 蜘蛛算法(improved social spider algorithm, ISSA)[48]等。關于不使用分解策略的方法更為詳盡的總結可見文獻[122-123]。

總體上，未使用分解策略的方法可以通過以下途徑提高對LBOP 問題的搜索性能：1）加入局部搜索策略，例如MA-SSW-Chains[45], μDSDE （micro differential evolution with a directional local search）[26]，jDEsps （self-adaptive differential evolution algorithm with a small and varying population size）[27]等；2）改進交叉、變異、選擇等進化算子，例如融合了反向學習的PSO算法（GOPSO）[35]，GaDE （generalized adaptive differential evolution）[17]等；3）混合不同算法，以取長補短，例如MOS-CEC 2013[42]。

1.2 使用分解策略的方法

基于分解策略求解LBOP 問題的算法采用了“分而治之”（divide-and-conquer）的思想。首先，將LBOP 問題分解為一系列較低維的子問題，然后，分別對子問題進行優化，最終，迭代逼近真實的最優解。這里，以最小化問題為例，若函數f(x1,···,xd)滿足以下條件：則稱函數f(x1,···,xd)是可分的[124-125]，亦即若一個函數單獨優化各維度的變量得到的最優解與其他變量的取值無關，且等于該函數全局最優解在該維度上的取值，則認為該函數是可分的。根據函數可分的定義，可以得到加法可分的定義。加法可分的函數可以方便地表示許多具有模塊化性質的實際工程問題[126]，其數學形式簡單，有利于理論推導。

若函數f(x1,···,xd)可以寫為如式（5）所示的形式，則稱之為部分加法可分的函數。

式中：xi為函數fi的 決策向量，且xi之間無相互重疊的決策變量，即xi互斥；x=〈x1,···,xd〉，為全局決策變量；s為獨立子問題的個數。若所有獨立的子問題都是一維的，則將函數f(x)稱為完全加法可分的。若獨立的子問題的個數只有一個，則稱f(x)為完全不可分的。

1.2.1 合作協同進化算法

合作協同進化算法（cooperative co-evolutionary algorithm，CCEA）運用生物協同演化的思想將問題分解為一系列子問題（即子種群），此方法在解決LBOP 問題時表現出了高效性，是解決LBOP問題的主要和熱門方法之一。文獻[127]對2018年以前提出的CCEA 算法進行了較為詳細和全面的總結。在此基礎上，本節對2018 年至今在求解LBOP 問題方面采用CCEA 算法所取得的研究進展進行總結補充，如表2 所示。

表2 合作協同進化算法研究文獻匯總Table 2 Summary of research advances of CCEA

圖4 所示為典型的CCEA 算法的框架[129]。

圖4 合作協同進化算法框架Fig. 4 Framework of cooperative co-evolutionary algorithm

如圖4 所示，CCEA 算法將一個高維問題分解為s個低維子問題，并為每個子問題建立一個用于進化的對應子種群，以串行或并行方式，利用EA 算法對每個子種群單獨優化（稱為一輪優化）。由于每個子問題的決策變量僅是全部決策變量的一部分，所以在優化子問題評價某個體的適應度值時，需要從對應的合作者庫中選擇合作者（圖中淺藍色的個體部分），補齊剩余的設計變量，使其形成一個完整的解以評價其適應度值。合作者庫是根據合作者信息池構建，而后者又是由各子問題中選出的代表解（圖中深藍色的個體部分）組成的，二者在優化過程中不斷更新，不同子種群之間就可以以此方式實現信息交換。值得指出的是，每個子種群可選擇多個代表解，并將其納入合作者信息池。評價子種群個體適應度值時，也可以與多個合作者形成多個完整的解，來綜合評價其適應度值。總之，通過不斷重復上述一輪優化過程，直至獲得最終的優化解。對于CCEA的研究方向主要有分組策略、合作者選擇策略等，下文將分別介紹此方面的研究工作。

1） 分組策略研究。

很顯然，如何分組及分組的正確與否對于算法性能有著重大的影響。若本來彼此之間無相互影響（可分）的變量被分到同一個子問題內，將無法體現“分而治之”方法的優勢。若本來彼此之間存在相互影響（不可分）的變量被分到不同的子問題內，將會丟失子問題的適應度函數特性，使得合作者的改變引起子問題適應度函數特性的大幅度改變，并且算法也將收斂到納什均衡（Nash equilibrium），而非全局最優解[51]。第1 個合作協同進化算法CCGA 由Potter 和De Jong[50]提出，該算法是將一個d維問題分解為d個一維子問題，并使用GA 算法輪流對子問題進行優化。這種最原始的分組方法在處理不可分問題（例如Rosenbrock 和Griewank 函數[11]）時的性能非常差。

關于分組策略的研究內容大致可分為動態和靜態分組方法兩類。其中，動態分組方法指的是原問題的分組在協同進化優化過程中會發生變化的方法。

（1） 動態分組方法。

隨機分組（random grouping）是這類分解方法的代表。Yang 等[51]結合隨機分組和CCEA 算法提出了DECC-G 算法，該算法將一個n維LBOP問題隨機分為k組，每個子問題包含n/k維度的變量。具體而言，每個協同進化框架在循環開始前（即下一輪子問題開始優化前），將再次將包含n維的問題重新隨機分成k組，以開始下一輪優化。通過每輪優化之間不斷改變分組方案，以此提高不可分變量被分到同一組中的概率。此外，DECC-G 算法還在每輪優化結束后，為各子問題分配一個權重，然后，分別對整個大種群的最優、最差、隨機的個體優化該權重值，以得到更好的全局最優解。

學者們基于DECC-G 算法提出了許多提高DECC-G 性能的算法。例如，多層合作協同進化（multilevel cooperative coevolution，MLCC）[52]使用分組方案庫來代替DECC-G 算法中每輪優化都重新分組的策略。該算法中，分組方案庫中每個方案的概率選擇取決于此方案的歷史性能表現，即歷史性能表現好的方案具有更大的被選中的概率。然而，Omidvar 等[53]指出，MLCC 算法繼承自DECC-G 算法的自適應優化權重部分，對算法性能幾乎無提升，而將已使用的函數計算次數用于更頻繁的重新隨機分組將更有效。最后，還有不少基于隨機分組或改進DECC-G 算法的研究[54-56]，但限于篇幅，不再贅述。

除了隨機分組外，還有Ray 和Yao[57]提出的一種基于相關矩陣的分組方法。此方法在最開始的幾輪優化中未使用分解方法，而是直接采用EA 算法對原問題整體優化，然后計算種群中前50%個體的相關矩陣，并根據相關矩陣分組。對于相關系數大于某個閾值的設計變量，可將其分配到同一組，分組完成后，再采用正常的CCEA算法進行優化。自適應可變分區的協同進化算法（CCEA with adaptive partitioning, CCEA-AVP）[58]是對Ray 和Yao 所提方法的改進，二者的區別在于，前者在協同進化的每一輪優化開始前都會利用已經計算過的個體來更新相關矩陣，并根據更新后的相關矩陣重新分組。但是，有研究也指出基于相關矩陣的方法計算資源消耗太大，且無法識別非線性相關的不可分變量[121,130]。

（2） 靜態分組方法。

靜態分組方法指的是一旦分組方案確定，例如將n維的問題分解為n個一維的子問題，或者將n維的問題分解為k個n/k維的問題，則在后續優化過程中分組方案不再發生變化的分組方法。很顯然，靜態分組這種先入為主的分解方法效果并不理想，故許多研究者提出了不少自動分辨可分與不可分變量的算法。例如，Weicker 等[131]提出了一種判斷相互影響變量的簡單方法，其假設best為當前已知最優解，new為協同進化的優化器對第i維變量優化后的個體，rand為種群中隨機選擇的個體。通過式（6），可以生成兩個新的個體x′和x，其第j維的值由下式給出：

若x′的 目標 函 數 值f(x′)優 于x的目 標 函數值f(x)，則可認為第j個變量和第k個變量相互影響的概率增加了。

基于上述思想，Chen 等[59]提出了基于變量交互學習的合作協同進化（cooperative co-evolution with variable interaction learning，CCVIL）算法。該算法分為學習階段和優化階段，其中，在學習階段利用與文獻[131] 中類似方法識別不可分變量并分組。Omidvar 等[60]則提出了Delta 分組方法與基于Delta 值的合作協同進化框架，其中，Delta 值由連續兩輪優化中的每個維度的絕對變化量計算得到，基于此，再根據對應的Delta 值對決策變量進行排序，最終，按排序后的delta 值對變量進行分組。然而，Omidvar 等[61]的研究也表明，若存在多個不可分離的子問題，Delta 分組的性能會下降。因此，作者又提出采用差分分組(differential grouping，DG)方法從數學上推導出如下定理。

則xp和xq是不可分的，p和q為被選擇用于判斷的兩個維度下標。其中：

上述推導的定理非常重要，因為它是DG 方法的核心理論，Omidvar 等[61]證明了由該定理可以推導出使用非線性檢測用于實數編碼遺傳算法的聯動 識 別（linkage identification by nonlinearity check for real-coded genetic algorithms，LINC-R）算 法[128]。

雖然DG 方法可大幅度提高分組的正確率，但也有不足之處：1）處理完全可分的問題時的計算資源消耗太大；2）無法對有重疊變量的子問題進行檢測；3）對數值計算的舍入誤差非常敏感；4）需要使用者事先定義一個閾值。

為了解決上述缺陷，許多學者開展了提高DG方法的效率和性能的研究。例如，提出了DG 方法的兩種變體形式-全局差分分組(globaldif-ferential grouping, GDG)[62]和擴展差分分組(extended differential grouping, XDG)[63]。XDG 方 法 是 通過確定變量間的間接相互作用來處理Rosenbrock函數，但缺點是它繼承了DG 的敏感性特點，且其判斷變量交互作用的方法可能會將可分離的變量視為不可分離的變量。

GDG 方法是通過考慮計算誤差來解決DG存在的敏感性問題，但該方法使用某個全局參數來檢測所有的交互作用，使其不適合于不平衡的函數。不僅如此，GDG 方法還需要通過檢查所有變量對的交互作用，來解決識別子問題間存在重疊變量的函數。為此，Omidvar 等[64]又提出了DG方法的升級版DG2，在方法中引入了一個“原始交互結構矩陣”。首先，其自適應尋找閾值；然后，將原始交互結構矩陣轉換為設計交互矩陣；最后，通過設計交互矩陣決定最終的分組方案。結果顯示，DG2 方法可以有效緩解原有方法存在的上述4 個缺點。

在其他分組策略方面，劉禮文[65]提出了一種再分組策略的算法，即將原問題分解為一系列子問題后，對維度仍較高的子問題再分組。此外，有學者還另外提出了一系列DG 類型的算法（詳見文獻[66-69]），以進一步降低DG 算法計算資源的消耗。而且，還有學者將設計變量和目標變量視為隨機變量，首先利用統計模型統計分析變量和/或目標函數，再根據不同統計值對變量進行分組，這些統計值包括Pearson 相關系數[70]、互信息（mutual information）[71]、最大信息系數（maximum information coefficient, MIC）[72]、Kullback-Leibler 散度[73]等。

2） 合作者選擇策略研究。

除了研究分組策略外，還有大量學者專注于合作者選擇策略的研究。如上所述，在對原問題進行分解后，使用CCEA 算法優化每個子問題時需要從其他子問題中選擇合作者湊成一個完整的解來評估適應度。因此，如何從子問題中選擇合適的合作者對于算法性能有著重要的影響。

第1 種策略也是最簡單直觀的，其選擇每個子問題中的最優個體作為合作者，將子問題個體與剩余子問題中的最優個體湊成完整的解來評價該個體的適應度（詳見文獻[50-51, 61, 74])。從研究結果來看，采用此策略處理完全可分的問題時非常有效，但對于不可分問題可能會導致算法陷入納什均衡或局部最優[75-76]。

第2 種策略是隨機選擇每個子問題中的個體作為合作者，將該個體與剩余子問題中隨機選擇的個體湊成完整的解來評價子問題個體的適應度。采用該策略能有效保持種群的多樣性且可防止算法早熟的問題，具體可見文獻[77-80]。從研究結果來看，采用此策略處理外部環境改變很快的動態優化問題時的表現好于選擇最優個體的策略，但隨機選擇合作者會降低算法的收斂速度[81]。

第3 種策略即所謂精英選擇策略，其也被視為第1 和第2 種策略的結合體。該策略首先從每個子問題中挑選前K個最優個體形成合作者池，然后從合作者池中隨機選取個體形成完整的解[82]。值得指出的是，當K=1 時，此策略退化為第1 種策略；當K等于子種群個體數時，則退化為第2 種策略。其次，K值不一定保持不變，例如，在算法初始階段可以選取較大的K值以保證多樣性，而后期階段可以選取較小的K值以提高收斂速度。另外，對于選擇單一合作者的策略，還包括類 似 于GA 算 法 中 的 輪 盤 賭/錦 標 賽 選 擇 策 略[78,83]、固定選擇合作者策略[84-85]、鄰域選擇策略[85]等，限于篇幅，不再贅述。

除了選擇單一合作者外，也可選擇多個合作者，與當前個體形成多個完整的解來對個體進行評估。為此，一種策略是選出剩余子問題中的所有個體作為合作者，具體詳見文獻[76, 86-87]。在子種群個體數足夠大時，此策略的優點是可保證收斂到全局最優[87]，但缺點是計算資源消耗巨大。例如，假設有s個子問題，每個子種群個體數為Np，則在優化某一個子問題的過程中，僅僅評價一個個體的適應度就需要Nps-1次的真實函數計算。另一種策略是構建合作者庫，例如基于帕累托支配的合作協同進化算法（pCCEA）[88]是以非支配者庫為基礎選擇合作者。在每代種群中，pCCEA算法用非支配者庫中的所有個體來評估子種群中的每個個體，即生成Na個完整解（其中，Na是子種群非支配者庫中的個體數）。然而，pCCEA 算法的缺點是，隨著算法的推進，Na趨于無窮大。而改進后的合作協同進化算法（iCCEA）[79]通過記錄“信息量大 ”的合作者，即記錄能夠改變另一個子種群中兩個個體的相對等級的個體解決了合作者數量趨于無窮大的問題。為此，文獻[89-91]提出了大小固定的共享參考庫，所有子種群從庫中選擇合作者。

3） 其他策略研究。

除了研究分組策略和合作者選擇策略外，關于合作協同進化策略的研究還包括但不限于如下內容：

（1） 適應度評價策略。如上所述，選擇單一合作者策略基本上都是選擇與單一合作者湊成完整解的目標函數值作為適應度值，但是，當有多個合作者時，就會有多種評價適應度的方法。例如，若有多個合作者形成多個完整的解時，可選取多個完整解目標函數之中的最優值[89]、平均值[92]、最差值[93]作為其適應度值，或基于帕累托支配的概 念 分 配 適 應 度 值[88-89,94-95]。常 規 進 化 算 法 中 使 用的適應度評價技術（例如，適應度繼承[96-97]、小生境技術[98-100]等）也可應用于CCEA 算法。

（2） 計算資源分配策略。即給每個單獨優化的子問題分配計算資源，包括均勻分配[50]、隨機分配[101]、基于對原問題貢獻程度的分配[102-105]等。

1.2.2 其他算法

CCEA 算法是基于分解思想的最典型、研究最多的算法之一。此外，仍有部分同樣利用了分解思想不屬于CCEA 的算法，例如代表性的EDA算法[106]。EDA 算法通過概率模型描述候選解的空間分布，利用有希望的解集來估計變量分布和變量相互作用，然后，根據學習到的變量分布及變量之間的相互作用，生成新候選解[107]。最簡單的EDA 算法（例如緊致遺傳算法（compact genetic algorithm, cGA）[108]、基于種群的增量學習（population-based incremental learning，PBIL）[109]等）中每個變量都是獨立的，不過，這些算法不適合處理不可分的問題。

Dong 等[110]提出的采用模型復雜度控制技術的EDA 算法（EDA-MCC）首先根據線性相關系數來識別交互作用較弱的變量，然后將剩余的交互作用較強的變量強行劃分為若干個不重疊的子集，以減小搜索空間。EDA-MCC 算法還可對所有的變量子集進行不同概率模型的演化。結果表明，在一批基準測試函數上，EDA-MCC 算法的性能優于傳統的EDA 算法和其他一些高效的算法。Xu 等[111]進一步對EDA-MCC 算法進行了改進，其采用互信息代替線性相關系數來識別交互作用較弱的變量，這樣可以檢測到變量間的非線性依賴關系。

Yang 等[112]結合分解策略與代理模型技術，提出了一種自我評價進化（self-evaluation evolution，SEE）算法, 即將多維度問題相應地劃分為一維多個子問題，通過局部搜索算子分別對每個子問題進行演化，通過訓練每對子代和父代的一部分得到簡單的代理模型，從而高效地實現子代解的適應度評價。最近，Yang 等[113]還采用并行計算技術以增強SEE 算法，進一步發展出一種高效算法-自然并行的分而治之算法（naturally paralleled divide-and-conquer, NPDC）。

在基于原問題分解的條件分布來處理不可分問題的算法中，因子化分布算法（factorized distribution algorithm，FDA）[114-115]在加法可分問題上表現較好，但需要問題架構的先驗知識，計算成本極高。

此外，還有一部分研究是利用專門設計的進化運算符、表征和機制，將變量分成若干組。例如，Schaffer 和Morishima[116]在個體染色體的每個基因上附加一個標志位，用以指示交叉點，相鄰的兩個交叉點間的基因被合并為同一組。在此基礎上，Levenick[117]擴展了上述方法，引入額外的標志位以表示選擇一個位置作為交叉點的概率。

Smith 和Fogarty[118]提出采用聯動進化遺傳算子（linkage evolving genetic operator，LEGO）自適應調整變量的分組。該方法通過為每個基因施加兩個布爾標志來表示其在染色體上與哪一個鄰居（左鄰或右鄰）相互作用，而相互作用的鄰接基因被認為是同一組的一部分。

Wu 等[132]提出的新混合算法則是采用現有分組算法將LBOP 問題劃分為若干個小規模問題，采用設計的改進自適應離散掃描方法對全部搜索空間進行粗略掃描，且著重搜索存在希望的區域。該混合搜索方法可自適應選擇一維搜索方案或協方差矩陣自適應進化策略，以分別解決可分離問題、部分（加法）可分問題或不可分問題的子問題。

2 代理模型輔助的大規模優化算法

在實際工程應用中，計算目標函數通常非常耗時。例如，對船舶沖擊動力響應的仿真計算，一次計算可能需要數小時到幾十小時不等，故也將這種目標函數計算非常耗時的優化問題稱為昂貴的優化問題。目前，LBOP 問題相關算法所需目標函數計算次數仍高達106數量級，這種計算成本是不可接受的。因此，有學者引入代理模型來有效解決時間成本高昂的問題。對于元啟發式算法而言，代理模型幾乎可以在元啟發式算法的所有階段使用，如圖5 所示。圖中，灰色框表示代理模型與元啟發式算法交互的階段。

圖5 代理模型與元啟發式算法交互示意圖Fig. 5 Diagram of interaction between surrogate modle and metaheuristic algorithm

代理模型可用于指導初始解的生成、輔助評價解的目標函數值、指導新生成解的采樣策略等。對于昂貴的優化問題，最常用方法是采用代理模型替代昂貴的耗時計算。對于低維昂貴的優化問題，目前的研究已相當成熟，典型方法可分為代理模型輔助的進化算法（surrogate-assisted evolutionary algorithm）[133]和貝葉斯優化框架（Bayesian optimization framework）[134-135]。有關這兩類算法可詳見文獻[136-137]。但是，傳統上適用于低維昂貴的優化問題的方法卻不能用于求解昂貴的LBOP 問題，其原因主要在于如下困難：1）隨著求解問題的維度增加，優化算法的搜索能力大幅降低，即使采用本文所述大規模優化算法可提高算法在高維的搜索能力，但仍難以找到真實的全局最優解；2）隨著求解問題的維度增加，代理模型的精度會迅速下降，構建代理模型所需樣本點數也會迅速增加。不僅如此，代理模型本身的計算復雜度也會隨著維度的增加而增加。

目前，關于代理模型輔助LBOP 問題的研究并不多見[138-140]。與上文類似，這些研究同樣可以分為使用和不使用分解策略兩大類，表3 按此分類給出了求解LBOP 問題時使用代理模型輔助元啟發式算法的典型文獻。表中，RBF（radial basis function）為徑向基模型, GP（Gaussian process）為高斯過程模型。

表3 代理模型輔助元啟發式算法的文獻分類Table 3 Summary of surrogate model assisted meta-heuristic algorithms

2.1 不使用分解策略的方法

原則上，對于不使用分解策略的方法求解低維的昂貴優化問題，直接使用代理模型擬合目標函數值（也稱適應度近似）的方法仍可以使用。然而，由于代理模型在高維空間中的精度會迅速下降，以及建模成本顯著上升，采用適應度近似的方法求解LBOP 問題的效果會嚴重下降，此時，可以考慮使用其他代理模型。

例如，根據父代適應度擬合子代的適應度值（也稱適應度繼承）和利用不同精度代理模型遷移個體間的適應度（也稱適應度遷移）；或使用代理模型指導交叉變異操作、初始種群生成等。另外，還可以采取降維的方式，結合整體與局部代理模型等各種途徑來緩解“維數災難”的問題。其中，部分研究采用的是基于高維空間到低維空間映射的降維方法（例如文獻[138,140]中使用的Sammon 映射方法)。然而，降維也意味著會丟失一定數量的設計變量對目標函數的影響，研究證明此方法僅適用于中等規模的優化問題(50～100個變量)[138-140]。

為了獲取全局最優解，Sun 等[141]提出了代理模型輔助合作的粒子群優化（surrogate-assisted cooperative swarm optimization, SA-COSO）算法，即通過代理模型輔助的PSO 算法與代理模型輔助社會學習的粒子群優化算法（social learning-based PSO, SL-PSO）合作來搜索全局最優解。PSO 與SL-PSO 之間的合作包含兩個方面：一是其共享由真實函數評估過的有希望的解；二是SL-PSO 算法側重于全局搜索，PSO 算法側重于局部搜索。Yu 等[142]提出一種類似于SA-COSO 的算法以提高SA-COSO 算法的性能，Sun 等[139]使用基于適應度近似的競爭群優化算法(competitive swarm optimizer, CSO)處理500 個決策變量的問題，算法采用適應度繼承策略[55]替代部分昂貴的適應度評估，該適應度繼承的方法也可以被視為局部代理模型。研究表明，相比未采用任何適應度近似策略的CSO 算法，采用代理模型輔助的CSO 算法對500 個變量的基準測試函數計算得到的結果更好，或者至少有競爭力。

Werth 等[147]提出的窗口式優化方法是根據變量相互作用關系對問題進行初步分組，算法每次迭代都在一個滑動窗口（該窗口僅包含所有設計變量的一個子集）內完成。初步研究結果表明，運用這種窗口式優化方法優化5 個高達1 000 維度的問題是有效的。Fu 等[143]提出的采用隨機特征選擇技術的代理模型輔助進化算法（surrogateassisted evolutionary algorithm with random feature selection，SAEA-RFS）則是利用隨機特征選擇技術形成的若干子問題進行序貫優化，來優化LBOP問題。

在降低代理模型建模成本方面，陳祺東[144]提出的代理模型輔助量子粒子群算法（surrogate-assisted quantum-behaved particle swarm optimization，SAQPSO），也稱SAQPSO-WS 算法，其基于曼哈頓距離（Manhattan distance）方法在優化過程中逐漸丟棄目標函數值不佳的樣本點，以此降低代理模型的建模成本。

Wang 等[145]提出的全局和局部代理模型輔助差分進化算法（evolutionary sampling assisted optimization，ESAO）可以交替進行全局和局部搜索，將RBF 模型作為全局代理模型，而將RBF 模型與Kriging 模型作為局部搜索模型。數值實驗表明，RBF 比Kriging 更適合作為局部代理模型。

Dong 等[146]提出的代理模型輔助灰狼優化(surrogate-assisted grey wolf optimization，SAGWO)算法在初始階段基于樣本識別出原始狼群和狼首，用于擬合高維空間，在搜索階段則利用灰狼優化全局搜索，結合多起點局部搜索策略在重點區域局部搜索。SAGWO 算法根據從RBF 模型中獲取的知識在每次循環內輔助生成新的狼首，并根據狼首所在位置改變狼群位置，從而達到平衡開發和探索的目的。

綜上所述，目前采用不使用分解策略的算法的研究一般都僅局限于約200 維度的高維優化問題，而對于上千維度的LBOP 問題則幾乎沒有涉及。

2.2 使用分解策略的方法

對于使用分解策略的方法，很自然地會想到能夠緩解所謂“維數災難”問題的代理模型與CCEA 算法結合的算法。CCEA 算法的特點是，首先將LBOP 問題分解為一系列低維子問題，有效降低訓練代理模型時的維度（也即避免代理模型直接擬合原有高維問題），然后再擬合低維子問題的適應度函數。盡管針對LBOP 問題的算法研究促進發展出了一些有效的CCEA 算法，但卻鮮有關于CCEA 算法與代理模型結合的研究，特別是涉及LBOP 問題時。目前，兩者相結合的算法研究仍處于比較初級的階段，也就是直接在子問題優化過程中使用代理模型來替代原有的適應度函數計算。

Ren 等[148]提出的RBF 模型、基于成功歷史的自適應差分進化算法（success-history based adaptive differential evolution，SHADE)和代理模型輔助的合作協同進化算法（surrogate model assisted cooperative coevolution，SACC）三者結合的混合算法（RBF-SHADE-SACC）中，RBF 模型作為各子問題的代理模型，SHADE 算法則為各子問題的優化器。對子問題優化過程中，只有代理模型預測值較優的個體才會被用于真實目標函數的計算，其他個體則直接使用RBF 模型進行適應度計算。值得指出的是，RBF-SHADE-SACC 算法默認原問題的理想分組情況已知，但這在實際應用中很難實現。

在Blanchard 等[149]提出的SACC-EAM（surrogate-assisted cooperative co-evolutionary algorithm of Minamo）算法中，將RBF 作為代理模型，Jade 算法作為子問題的優化器，使用隨機分組策略。該算法在使用Jade 算法優化子問題的過程中，RBF 被用于替代耗時的真實函數計算，最優解的評估采用的是真實函數，并將其加入到代理模型樣本點庫。其后，Blanchard 等[150]又提出了改進SACCEAM 的SACC-EAM-II 算法，通過使用遞歸差分分組 (recursive differential grouping，RDG) 策 略代替原有的分組策略，以達到提高算法性能的目的。

De Falcon 等[151]提出的基于隨機分組策略的SACC 算法框架將Jade 算法作為優化器，在優化子問題的過程中可以使用全局代理模型或局部代理模型。其研究主要在于各參數對SACC 框架的影響，結果表明：在大多數問題中，降低子問題的維度（2～4 維）能夠顯著提升收斂性，每個子問題的最佳進化代數會隨著目標函數的不同而不同；其次，若由GP、RBF、支持向量機回歸(support vector regression, SVR)作為全局代理模型，而二次多項式近似(quadratic polynomial approximation, QPA)作為局部代理模型時，總體上性能表現最好的代理模型是GP 和RBF；在大多數情況下，SVR 模型早期收斂速度更快，并且對于多模態函數，SACC算法性能提升不大。

綜上所述，對于不使用分解策略的算法，由于“維數災難”問題不能再像低維問題一樣采用代理模型直接替換適應度評估，而是需要采取降維、局部搜索等特殊的改進方法。由結果可見，這種方法在應用于解決中高維問題（500 維以下）時的效果較好，超過500 維度的LBOP 問題得到的優化解仍不夠理想；采用使用分解策略的算法由于分解機制可以在分解后的低維子問題中直接采用代理模型替換子問題的適應度計算，因此其研究一般都涉及到了約1 000 維度的LBOP 問題。然而，這種算法只是在子問題中機械地套用了低維問題的方法，而未考慮分解策略的特點。雖然相比于不使用代理模型的算法這種方法可節省計算資源，但是針對LBOP 問題獲得的優化解與真實的優化解仍然存在較大差距。

鑒此，代理模型輔助大規模元啟發式算法仍然具有很大的改進空間，故有比較大的研究價值。

3 結論與展望

近年來，LBOP 問題引起了各領域研究者的廣泛興趣，本文總結了目前有關LBOP 問題的元啟發式算法的研究進展。總體上，用于求解LBOP問題的元啟發式算法可以按照是否使用了分解策略進行分類。不使用分解策略的算法需要通過添加局部搜索、混合不同算法等策略來提高算法在求解LBOP 問題時的性能；而使用分解策略的算法則主要考慮分解策略帶給算法的新特性，從這些新特性著手提高算法效率，例如，提出高效的分組策略、資源分配策略等。在算法性能方面，這兩類算法無明顯的優劣之分。

對于昂貴的LBOP 問題，使用代理模型仍然是絕大部分研究的首選方案。由于LBOP 問題本身的復雜度，無論算法是否使用了分解策略，運用代理模型輔助元啟發式算法來求解LBOP 問題仍比較困難，故有較大的提升空間。總之，元啟發式算法在求解LBOP 問題時還將面臨如下主要挑戰：

1） 設計空間體積隨著維度的增加呈現指數增加的趨勢。

2） 高維空間中目標函數的特性變得復雜，例如從單模態函數變為多模態函數。

3） 優化算法的搜索能力在高維空間中被削弱。

4） 優化成本高昂。

通過大量的文獻分析和歸納總結，以及基于對實際工程應用的需求思考，本文認為LBOP 問題的未來研究方向可以概括為：

1） 進一步提升解決LBOP 問題的算法性能。目前，對于LBOP 問題現有算法仍需要大量的函數計算次數，并且得到的優化解與真實的優化解之間仍存在較大差距。

2） 求解大規模多目標優化及大規模約束優化問題。目前，對于無約束單一目標的LBOP 問題仍不能得到理想的解決方案，因此解決復雜的大規模約束優化問題更加困難。

3） 昂貴的LBOP 問題的研究。與目前研究主要使用廉價的測試函數不同，實際工程應用中的LBOP 問題通常昂貴，現有算法所需要的目標函數計算次數仍然巨大。代理模型輔助的元啟發式算法似乎是比較有希望的解決方案。

4） 大規模優化算法在實際工程問題中的應用研究。在開展研究時，可以結合設計對象的專業先驗知識指導變量分組，以提高優化效率。例如：對于大型船舶復雜橫剖面優化設計問題，可以將上層建筑的設計變量分為一組，主船體設計變量根據垂向高度分成若干個組；對于船舶艙段優化設計問題，可以根據板架分組（例如甲板、舷側、船底，平臺，縱艙壁等）；對于船舶的艏部型線的優化問題，可以按照附體型線（例如球鼻艏型線、艏部主船體型線）分組。