基于代理模型的差分進化約束優化

薛 鋒，史旭華，史非凡

（寧波大學信息科學與工程學院，浙江寧波315211）

（?通信作者電子郵箱520286179@qq.com）

0 引言

系統優化包括無約束優化和約束優化，在科研、管理、工業等方面都發揮著重要作用?，F實世界中的許多問題本質上都是優化問題。最開始，研究者使用各種傳統優化算法來解決優化問題，傳統優化算法一般針對的是結構化的問題，其問題與條件的描述都較為明確，可以在特定條件下產生全局最優解。對于解決單極值問題，傳統的優化算法已足夠好，然而，對于解決多變量、高復雜度的多極值優化問題，使用傳統優化方法效率不高，容易陷入局部最優。為了解決這一問題，有研究者提出了進化算法（Evolutionary Algorithm，EA），如遺傳算法、差分進化、粒子群優化等。這些算法在解決復雜優化問題時表現出了更好的性能。

相較于無約束的優化問題，約束優化問題中多了各種約束條件。約束條件通常包含等式約束、不等式約束以及變量的上下界約束。在進化計算領域，越來越多的研究者使用進化算法來解決約束優化問題。對約束的處理，提出了多種約束優化進化算法（Constrained Evolutionary Optimization Algorithm，COEA）［1］，如變量約簡策略［2］、簡單多種群進化策略［3］、混合約束優化進化算法［4］等。

約束優化問題通?？擅枋鰹?

對約束的處理主要以下6 種方法［5］:罰函數法［6］、可行性規則［7］、多目標優化法［8］、隨機排序法［9］、ε 約束處理法［10］、混合法［11］。

實際上，約束處理技術是為了確定一個標準，以此來比較親本和后代的優劣。罰函數法的主要思想是根據種群中個體的約束違反度來構造懲罰項，然后將懲罰項與目標函數相結合來構造出一個懲罰適應度函數，從而將帶有約束的優化問題轉換成無約束的優化問題來處理；但罰函數法存在著參數設置困難、實際使用效果不佳的問題［6］。多目標優化法是將約束優化問題轉換為多目標優化問題，然后運用多目標優化方法來解決轉換后的問題，該方法具有較好的收斂結果和性能；但是其消耗的計算資源也是巨大的［8］。隨機排序法采用一個概率參數來決定是根據個體的約束違反程度還是根據其目標函數來評判兩個個體的優劣；但也存在著相關參數設置困難的問題［9］。ε 約束處理法是通過預先設定ε 值，然后基于個體的約束違反度將決策域分為不同的區域，在不同的區域，對可行解和不可行解采用不同的方法進行比較，其缺點是比較耗時［10］。

可行性法則是Deb 于2000 年提出的一種約束處理方法，該方法通過一定的準則對兩個候選解進行比較，從而選擇出其中較優的一個。相對于其他方法，可行性法則能夠更快地找到可行解，且該方法容易實現，不需要設置額外參數，可以適用于各種場景。

一般來說，進化約束優化算法有兩個主要目標:1）快速進入可行域；2）找到最優解。大多數進化約束優化算法為了盡快進入可行域而依賴約束條件對個體進行比較，從而忽略了目標函數的影響。這樣不利于算法的快速收斂。對此，本文提出了基于代理模型的差分進化約束優化算法（Surrogatebased Differential Evolution Constrained Optimization Algorithm，SDECOA）。SDECOA 將目標函數的信息和約束條件作為個體選擇的評價，運用到算法中，并且結合了代理模型來提高解決耗時計算問題的計算效率。

SDECOA 使用差分進化算法來進行搜索，并運用可行性規則來對個體進行比較。在進化過程中，如果差分進化產生的后代根據可行性規則進行比較比父代差，但是其目標函數值比父代更優，則將該子代存入備用種群存檔中，然后通過一種替換機制來用存檔中的個體替換種群中的某些個體。此外還提出了一種突變策略來防止種群陷入不可行區域。在計算出第一代個體的目標函數值后，使用這些數據來建立目標函數的代理模型，在之后對子代的評估都通過代理模型來進行，這樣就可以大幅減少目標函數的調用次數，從而提高算法效率。

1 背景知識

1.1 代理模型

對目標函數構建代理模型已經成為一種用來優化現實世界中復雜問題的實用方法。因為使用代理模型能有效地降低計算成本，從而實現更低的預算。代理模型的思想是對耗時計算的目標函數建立一個近似的替代模型，用這個模型來替代進化計算過程中對目標函數的調用，從而減少耗時計算的次數。

在解決復雜優化問題上，可供選擇的代理模型［11］有許多:克里金（Kriging，KRG）模型、高斯過程（Gaussian Process，GP）模型、多項式響應面（Polynomial Regression Surface，PRS）模型、徑向基函數（Radial Basis Function，RBF）模型、后向傳播神經網絡（Back Propagation Neural Network，BPNN）模型、支持向量回歸（Support Vector Regression，SVR）模型等。

以上這些代理模型的理論基礎和適用范圍均不相同，本文主要使用克里金模型、多項式響應面模型和后向傳播神經網絡模型來對目標函數進行擬合。

1.2 可行性規則

由Deb提出的可行性法則是當前應用最受歡迎和最有效的約束處理技術之一，在可行性法則中，當需要對兩個解xi和xj進行比較時，在滿足以下條件之一時，xi比xj更優:

1）xi是可行解而xj是不可行解；

2）xi和xj都是可行解，但xi的目標函數值更??；

3）xi和xj都是不可行解，但xi的約束違反度值更小。

2 基于代理模型的差分進化約束優化算法

2.1 算法整體框架

約束優化進化算法主要包括兩個部分:約束處理技術和搜索算法。因為差分進化算法具有簡單、高效、易于使用等優點，所以本文使用它作為搜索算法。

針對可行性規則處理約束速度快但是可靠性較差的特點，本文使用了一種利用目標函數提供的信息來提高其魯棒性的方法。通過將目標函數的信息與可行性規則相結合，可以使得算法在約束條件和目標函數之間達到平衡。

如算法1 所示，首先初始化種群Pt，計算出當前種群中每個個體的目標函數值和約束違反度值，并使用這些數據建立目標函數的代理模型。其次對種群中的每個個體xi，t通過差分進化產生一個試驗個體vi，t，使用代理模型計算試驗個體的近似目標函數值，然后根據可行性規則對xi，t與vi，t進行比較，將更優的一個加入下一代種群。如果vi，t能加入下一代則用真實目標函數計算出其真實的目標函數值。如果vi，t不能進入下一代但是卻有更小的目標函數值，則將其加入備用存檔中。

2.2 差分進化算法的改進

差分進化算法［12］是一種啟發式隨機搜索算法，該算法的主要特點是利用種群中的個體間的差異向量來對個體進行變異操作，其交叉與選擇操作與遺傳算法大致相同。該算法原理簡單、魯棒性強、受控參數少，求解質量高且收斂速度優于其他一些進化算法。

本文使用一種改進的差分進化算法來對最優解進行搜索。針對原始的差分進化算法容易陷入局部最優的問題，本文對差分進化算法進行了改進，與原來的差分進化算法不同的是，改進后的差分進化算法中的個體不僅僅向種群中隨機的其他個體獲取信息，而且還有相同的可能向種群中的最優個體獲取信息。

如算法2 所述，其中k1、k2、k3 是［1，NP］中互不相同的整數，F 是縮放比例因子。首先取一個［0，1］的隨機數rand，若rand＜0.5，則只從種群中的其他隨機個體獲取信息；反之則額外從最優個體獲取信息。

2.3 替換機制

替換機制的目的是通過將當前種群中的一些個體用備用存檔中的個體來替換從而避免可行性規則過于貪心的問題。

如算法3 所示，為了避免只在可行域的局部區域實行替換機制，該算法先將種群中的個體按照目標函數值的大小降序排列，再將其分為相同尺寸的N 個部分。然后選擇種群的第一部分中約束違反度最大的個體xa和備用存檔中約束違反度最小的個體xb，如果xb的目標函數值小于xa的目標函數值，則用xb替換xa。再對接下來的每一個部分進行同樣的處理。

2.4 變異策略

由于在求解約束優化問題時，種群很容易陷入不可行區域的局部最優，這樣就會導致在迭代結束時無法找到最優解。出于這方面的考慮本文使用了一種種群變異策略，該策略僅在種群中的所有個體全部為不可行解時才會用到。

失業后的程曉只得開著凱迪拉克去機場和火車站的路口攬客。一天，他送一個齒輪廠的小老板去一家大公司談業務，那位小老板要程曉在那家公司的大樓下等著把他送回去，來回僅40公里路程，對方竟開出了400元的高價。

如算法4 所示，如果當前種群中的所有個體都是不可行解，則從種群中隨機選擇一個個體進行變異操作，生成新的個體來替代當前個體，從而避免無法進入可行區域的情況發生。

3 仿真

3.1 與其他約束優化算法的比較

為了測試本文所提出的算法的有效性，選取CEC2006 中比較典型的測試函數來對算法進行測試。初始種群數設置為80，對于不同復雜度的目標函數設置不同的最大適應度評估次數。使用軟件為Matlab r2018a，對于每一個測試函數都在相同的條件下運行20次。

將 本 文 算 法 與 FROFI（Feasibility Rule with the incorporation of Objective Function Information）算法［13］和內部罰函數進化策略（Interior Penalty based Evolution Strategy，IPES）算法［14］進行比較。對于每一種算法都設置相同的最大適應度評估次數，然后分別從三個方面比較:最優值、平均值和方差。從表1 中可以看出，本文提出的SDECOA 能夠在較少的適應度評估次數下得到更優的結果，而且方差最小，說明SDECOA 的效果最穩定；而FROFI 算法和IPES 算法在同樣的適應度評估次數下的結果不如SDECOA。對于g05、g10、g14、g15這四個函數，FROFI算法無法在較少的適應度評估次數下求出結果；對于g04、g05、g12，IPES 算法也無法在給定的適應度評估次數的限制下求得結果；但SDECOA 卻能在同樣的適應度評估次數限制下求出較好的結果。FROFI算法雖然能直接得到最優的結果，但需要的適應度評估次數也相應地大幅提高［13］。同樣，IPES 算法也可以對大多數函數求取出最優值，但其所需的適應度評估次數也不少［14］。這對于目標函數較為復雜的情況來說會極大地增加計算成本。由此可見，本文所提出的SDECOA 能夠在更少的適應度評估次數下求取較為精確的結果，極大減少了計算成本。

圖1和圖2分別給出了SDECOA、FROFI和IPES三種算法對于g04、g16 兩個函數的收斂曲線。種群數設置為80，最大適應度評估次數設置為50 000。從圖1～2 可看出，FROFI 和IPES 兩種算法都在數千次以后才開始快速向最優值收斂，而SDECOA 則在千次以前就快速地向最優值收斂了。因此，SDECOA 在前期具有更快的收斂能力，具有較好的尋優效果。

表1 三種優化算法在10個測試函數上的結果比較Tab. 1 Result comparison of three optimization algorithms on 10 test functions

圖1 對函數g04尋優過程中SDECOA、FROFI、IPES的收斂曲線Fig.1 Convergence curves of SDECOA，FROFI and IPES in the optimization process of function g04

圖2 對函數g16尋優過程中，SDECOA、FROFI、IPES的收斂曲線Fig.2 Convergence curves of SDECOA，FROFI and IPES in the optimization process of function g16

3.2 不同代理模型的效果比較

現有的代理模型多種多樣，本文將三種代理模型分別與算法相結合，通過比較運行20 次的結果及其方差來分析各個代理模型的優劣。本文所用的三種代理模型為:克里金模型（KRG）、多項式回歸模型（PRS）、后向傳播神經網絡模型（BPNN）。實驗結果如表2所示。

表2 三種代理模型的效果比較Tab. 2 Effect comparison of three surrogate models

從表2 中可以看出，三種代理模型對于不同的函數有著不同的效果:對于PRS 來說，它在g04、g05、g10、g11、g12、g15的表現最好，最為接近真實最優值且方差最?。粚τ贙RG 來說，其僅在g06、g11、g12 的表現較好；對于BPNN 而言，它在g08、g14、g15、g16 等部分函數上有較好的表現。綜上所述，PRS 對于在大部分測試函數都有著更好的表現，其次是BPNN，效果相對較差的則是KRG。

3.3 工字梁設計優化實例

工字梁設計優化問題［15］是如今比較典型的實際工程設計問題。

圖3 工字梁設計問題Fig.3 I-beam design problem

本文通過對該問題的優化來體現SDECOA 的優化能力和效率。工字梁設計優化問題的目標是:給定荷載條件，使得在同時滿足橫截面和應力約束的條件下形變量最小。該問題的各項參數如下。

楊氏彈性模量:E = 2 × 104kΝ/cm2；

最大彎曲力:P = 600 kΝ，Q = 50 kΝ；

工字梁長度:L = 200 cm。

優化目標為最小化形變量:

約束條件:

1）橫截面積小于300 cm2。

2）工字梁容許彎曲應力小于6 kΝ/cm2。

3）初始設計空間:10 ≤x1≤80，10 ≤x2≤50，0.9 ≤x3≤5，0.9 ≤x4≤5。

首先，采用拉丁超立方采樣方法生成40 個初始設計變量，對每一個初始設計變量進行適應度評估并計算出對應的約束違反度值。再用后向傳播神經網絡模型（BPNN）對目標函數建立代理模型。最后程序運行結束得到的結果如表3所示。

表3 SDECOA應用效果Tab. 3 Application effect of SDECOA

從表3 中可以看出，使用本文提出的SDECOA 比優化前以及采用FROFI 算法的模型調用次數都要少，而且優化精度也比優化前更高，但是略低于FROFI 算法。SDECOA 能在大幅減少模型調用次數的情況下獲得較為精確的結果。所以，本文所提出的SDECOA 在解決復雜的約束優化問題時在優化效率方面具有一定的優勢，能夠有效提升優化的質量和效率。

4 結語

本文針對復雜約束優化問題提出了基于代理模型的差分進化約束優化算法，并且還將可行性法則與目標函數的信息相結合。該算法利用父代來建立真實目標函數的代理模型，在之后父代與子代的比較中，對于子代個體的評估通過代理模型來完成，當確定某一子代進入父代時，再對該子代使用真實目標函數進行評估。通過實驗可以看出，SDECOA 能夠在較少的適應度評估次數下獲得更優的結果。使用不同的代理模型效果也不盡相同?？偟膩碚f，使用PRS 作為代理模型對于大多數測試函數都能取得最優的效果，而且，在對于10 個測試函數的實驗中，相對于不使用代理模型的FROFI 和IPES這兩種方法，SDECOA 能夠更快地收斂向最優值，同時取得較好的結果。

但是，現有的代理模型是靜態的代理模型，第一次建立后就不可更改。這可能不利于對原函數的擬合，從而影響優化效果，所以可以采用在優化過程中不斷加入采樣點的動態代理模型，進一步細化代理模型，可能會取得更好的優化效果。