大規(guī)模黑箱優(yōu)化問題元啟發(fā)式求解方法研究進(jìn)展

江璞玉，劉均，周奇，程遠(yuǎn)勝*

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

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

0 引 言

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

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

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

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

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

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

可見，提出高效求解LBOP 問題的元啟發(fā)式算法，對(duì)于提高船舶優(yōu)化設(shè)計(jì)效率、縮減設(shè)計(jì)周期以及提升設(shè)計(jì)質(zhì)量都具有重大意義。本文擬對(duì)目前處理LBOP 問題的元啟發(fā)式算法進(jìn)行總結(jié)分析，提出未來可能的研究方向或重點(diǎn)，以便為相關(guān)領(lǐng)域感興趣的學(xué)者提供參考。

1 處理大規(guī)模優(yōu)化問題的方法

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

表1 大規(guī)模黑箱優(yōu)化問題元啟發(fā)式算法研究文獻(xiàn)匯總Table 1 Summary of research advances using meta-heuristic algorithms for LBOPs

1.1 不使用分解策略的方法

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

1.1.1 基于DE 的改進(jìn)算法

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

圖2 差分進(jìn)化算法流程圖Fig. 2 Flowchart of differential evolution algorithm

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

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

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

1.1.2 基于PSO 的改進(jìn)算法

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

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

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

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

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

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

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

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

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

1.1.3 其他算法

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

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

總體上，未使用分解策略的方法可以通過以下途徑提高對(duì)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）改進(jìn)交叉、變異、選擇等進(jìn)化算子，例如融合了反向?qū)W習(xí)的PSO算法（GOPSO）[35]，GaDE （generalized adaptive differential evolution）[17]等；3）混合不同算法，以取長補(bǔ)短，例如MOS-CEC 2013[42]。

1.2 使用分解策略的方法

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

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

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

1.2.1 合作協(xié)同進(jìn)化算法

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

表2 合作協(xié)同進(jìn)化算法研究文獻(xiàn)匯總Table 2 Summary of research advances of CCEA

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

圖4 合作協(xié)同進(jìn)化算法框架Fig. 4 Framework of cooperative co-evolutionary algorithm

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

1） 分組策略研究。

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

關(guān)于分組策略的研究內(nèi)容大致可分為動(dòng)態(tài)和靜態(tài)分組方法兩類。其中，動(dòng)態(tài)分組方法指的是原問題的分組在協(xié)同進(jìn)化優(yōu)化過程中會(huì)發(fā)生變化的方法。

（1） 動(dòng)態(tài)分組方法。

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

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

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

（2） 靜態(tài)分組方法。

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

若x′的 目標(biāo) 函 數(shù) 值f(x′)優(yōu) 于x的目 標(biāo) 函數(shù)值f(x)，則可認(rèn)為第j個(gè)變量和第k個(gè)變量相互影響的概率增加了。

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

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

上述推導(dǎo)的定理非常重要，因?yàn)樗荄G 方法的核心理論，Omidvar 等[61]證明了由該定理可以推導(dǎo)出使用非線性檢測用于實(shí)數(shù)編碼遺傳算法的聯(lián)動(dòng) 識(shí) 別（linkage identification by nonlinearity check for real-coded genetic algorithms，LINC-R）算 法[128]。

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

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

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

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

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

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

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

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

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

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

3） 其他策略研究。

除了研究分組策略和合作者選擇策略外，關(guān)于合作協(xié)同進(jìn)化策略的研究還包括但不限于如下內(nèi)容：

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

（2） 計(jì)算資源分配策略。即給每個(gè)單獨(dú)優(yōu)化的子問題分配計(jì)算資源，包括均勻分配[50]、隨機(jī)分配[101]、基于對(duì)原問題貢獻(xiàn)程度的分配[102-105]等。

1.2.2 其他算法

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

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

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

在基于原問題分解的條件分布來處理不可分問題的算法中，因子化分布算法（factorized distribution algorithm，F(xiàn)DA）[114-115]在加法可分問題上表現(xiàn)較好，但需要問題架構(gòu)的先驗(yàn)知識(shí)，計(jì)算成本極高。

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

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

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

2 代理模型輔助的大規(guī)模優(yōu)化算法

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

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

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

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

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

2.1 不使用分解策略的方法

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

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

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

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

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

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

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

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

2.2 使用分解策略的方法

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

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

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

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

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

鑒此，代理模型輔助大規(guī)模元啟發(fā)式算法仍然具有很大的改進(jìn)空間，故有比較大的研究價(jià)值。

3 結(jié)論與展望

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

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

1） 設(shè)計(jì)空間體積隨著維度的增加呈現(xiàn)指數(shù)增加的趨勢。

2） 高維空間中目標(biāo)函數(shù)的特性變得復(fù)雜，例如從單模態(tài)函數(shù)變?yōu)槎嗄B(tài)函數(shù)。

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

4） 優(yōu)化成本高昂。

通過大量的文獻(xiàn)分析和歸納總結(jié)，以及基于對(duì)實(shí)際工程應(yīng)用的需求思考，本文認(rèn)為LBOP 問題的未來研究方向可以概括為：

1） 進(jìn)一步提升解決LBOP 問題的算法性能。目前，對(duì)于LBOP 問題現(xiàn)有算法仍需要大量的函數(shù)計(jì)算次數(shù)，并且得到的優(yōu)化解與真實(shí)的優(yōu)化解之間仍存在較大差距。

2） 求解大規(guī)模多目標(biāo)優(yōu)化及大規(guī)模約束優(yōu)化問題。目前，對(duì)于無約束單一目標(biāo)的LBOP 問題仍不能得到理想的解決方案，因此解決復(fù)雜的大規(guī)模約束優(yōu)化問題更加困難。

3） 昂貴的LBOP 問題的研究。與目前研究主要使用廉價(jià)的測試函數(shù)不同，實(shí)際工程應(yīng)用中的LBOP 問題通常昂貴，現(xiàn)有算法所需要的目標(biāo)函數(shù)計(jì)算次數(shù)仍然巨大。代理模型輔助的元啟發(fā)式算法似乎是比較有希望的解決方案。

4） 大規(guī)模優(yōu)化算法在實(shí)際工程問題中的應(yīng)用研究。在開展研究時(shí)，可以結(jié)合設(shè)計(jì)對(duì)象的專業(yè)先驗(yàn)知識(shí)指導(dǎo)變量分組，以提高優(yōu)化效率。例如：對(duì)于大型船舶復(fù)雜橫剖面優(yōu)化設(shè)計(jì)問題，可以將上層建筑的設(shè)計(jì)變量分為一組，主船體設(shè)計(jì)變量根據(jù)垂向高度分成若干個(gè)組；對(duì)于船舶艙段優(yōu)化設(shè)計(jì)問題，可以根據(jù)板架分組（例如甲板、舷側(cè)、船底，平臺(tái)，縱艙壁等）；對(duì)于船舶的艏部型線的優(yōu)化問題，可以按照附體型線（例如球鼻艏型線、艏部主船體型線）分組。