基于代理模型的差分進化約束優(yōu)化

薛 鋒，史旭華，史非凡

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

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

0 引言

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

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

約束優(yōu)化問題通?？擅枋鰹?

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

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

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

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

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

1 背景知識

1.1 代理模型

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

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

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

1.2 可行性規(guī)則

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

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

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

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

2 基于代理模型的差分進化約束優(yōu)化算法

2.1 算法整體框架

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

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

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

2.2 差分進化算法的改進

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

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

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

2.3 替換機制

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

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

2.4 變異策略

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

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

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

3 仿真

3.1 與其他約束優(yōu)化算法的比較

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

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

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

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

圖1 對函數(shù)g04尋優(yōu)過程中SDECOA、FROFI、IPES的收斂曲線Fig.1 Convergence curves of SDECOA，F(xiàn)ROFI and IPES in the optimization process of function g04

圖2 對函數(shù)g16尋優(yōu)過程中，SDECOA、FROFI、IPES的收斂曲線Fig.2 Convergence curves of SDECOA，F(xiàn)ROFI and IPES in the optimization process of function g16

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

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

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

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

3.3 工字梁設計優(yōu)化實例

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

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

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

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

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

工字梁長度:L = 200 cm。

優(yōu)化目標為最小化形變量:

約束條件:

1）橫截面積小于300 cm2。

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

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

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

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

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

4 結語

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

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