基于代理模型可行規(guī)則法的優(yōu)化算法

張慧晶，張國晨，譚 瑛，孫超利

(太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，太原 030024)

0 引言

在工程應(yīng)用和工業(yè)設(shè)計中存在著許多的約束優(yōu)化問題，例如水資源分布網(wǎng)絡(luò)設(shè)計[1]，資源分配[2]，優(yōu)化控制[3]，DNA序列檢測[4]等。這些不僅是單一目標(biāo)的優(yōu)化問題，同時有其他的附加目標(biāo)約束條件。約束條件的存在將決策空間分成可行空間和不可行空間，所以在解決帶有約束的優(yōu)化問題時通常給帶來很大的挑戰(zhàn)性。

傳統(tǒng)算法在解決約束優(yōu)化問題時需要消耗大量的評價次數(shù)，因此使用傳統(tǒng)優(yōu)化算法解決該問題時，往往會因為實驗代價昂貴而受到限制。進化算法在求解約束優(yōu)化問題的過程中不依賴待優(yōu)化問題的函數(shù)特性，因此得到廣大科研人員的關(guān)注，并且提出了許多優(yōu)秀的用于解決約束優(yōu)化問題的優(yōu)化算法例如jDE-2[5]，MDE[6]，SaDE[7],UDE[8]等。Michalewicz和Schoenauer[9]將目前用于解決約束問題的優(yōu)化算法分為四種類型，具體如下：(1)優(yōu)先尋找可行解類型的算法；(2)基于罰函數(shù)的優(yōu)化算法；(3)將個體分為可行解和不可行解，然后根據(jù)解的類型分別進行優(yōu)化的方法；(4)混合類型的優(yōu)化算法，即同時具有以上兩種或者三種的方法的優(yōu)化算法。其中在以上四種類型的優(yōu)化算法中最常用的是對不可行解添加罰函數(shù)的方法，但由于需要添加過多懲罰因子，該方法在應(yīng)用過程中受到很大的限制。

同時，注意到代理模型廣泛運用在解決代價昂貴的單目標(biāo)優(yōu)化問題(即實驗代價昂貴或?qū)嶒灪臅r較長)[10]，例如藥物實驗設(shè)計[11]，空氣動力學(xué)實驗設(shè)計優(yōu)化[12]等。在將代理模型應(yīng)用到進化算法時，模型管理往往起著至關(guān)重要的作用[13]。

本文所提出的基于代理模型優(yōu)化的進化算法在解決昂貴單目標(biāo)約束問題時，針對評價待優(yōu)化函數(shù)約束條件較為昂貴(約束條件昂貴主要表現(xiàn)在兩個方面：(1)約束條件過多，計算復(fù)雜；(2)單個約束函數(shù)的復(fù)雜度高，評價次數(shù)多)的難題，引入代理模型，主要用于擬合待優(yōu)化函數(shù)的約束函數(shù)。本文的主要貢獻如下：

(1)提出了將代理模型引入到昂貴約束函數(shù)的優(yōu)化問題中的方法，可以有效地減少優(yōu)化過程中的實驗代價。

(2)提出了新的模型管理方法，主要用于解決含有多個約束問題的優(yōu)化問題，既可以有效地減少建模成本，也可以提高模型預(yù)測的精度。

本文的文章結(jié)構(gòu)安排如下：現(xiàn)階段約束處理方式在文章的第一部分；本文所提算法的詳細(xì)描述在第二部分；為了驗證本文所提算法的有效性，采用了CEC2017約束函數(shù)測試集測試其結(jié)果，并且與其他優(yōu)秀的算法對比，其具體描述在本文的第三部分。最后一部分為文章的總結(jié)。

1 相關(guān)工作

1.1 約束優(yōu)化問題

約束優(yōu)化問題的數(shù)學(xué)表達式如下：

(1)

在上述的公式(1)中x具體為：x∈RD且x=(x1,x2,x3,…,xD)，其中D表示待優(yōu)化目標(biāo)函數(shù)的決策空間維度，每個解的取值范圍為[xj,min,xj,max];j=1,2,3,…,D.q表示待優(yōu)化目標(biāo)函數(shù)中不等式約束條件的個數(shù)，m-q表示待優(yōu)化目標(biāo)函數(shù)中含有等式約束條件的個數(shù)。

1.2 代理模型的選取及構(gòu)建

實際的工程中存在很多約束優(yōu)化問題，其約束函數(shù)函數(shù)是昂貴的；同時注意到在解決昂貴單目標(biāo)優(yōu)化問題中，許多學(xué)者將代理模型添加到優(yōu)化算法中[14-20]，因此本文將采用同樣的思想，本文中用到的代理模型為徑向基函數(shù)模型(Radial Basis Function (RBF))。在把RBF模型與眾多代理模型進行比較后，發(fā)現(xiàn)RBF模型擬合函數(shù)的穩(wěn)健性和準(zhǔn)確性更好，故我們采用此模型。RBF的簡要描述如下：

在進行模型訓(xùn)練前，根據(jù)拉丁超立方體采樣在決策空間中選取n個點作為訓(xùn)練模型的樣本數(shù)據(jù)，其在決策空間的表示為u(1),u(2),…u(n)∈Rd，對應(yīng)的函數(shù)值表示為f(u(1)),f(u(2)),…,f(u(n)).下面的公式(2)是基于插值的RBF模型。

(2)

在公式(2)中，‖·‖表示歐氏距離，p(x)是一個線性多項式，φ表示三次多項式具體形式為φ(r)=r3，λi∈R是三次多項式的系數(shù)。

為了求解以上基于三次方插值的RBF模型，我們通過φij=φ(‖u(i)-u(j)‖)i,j=1,2,…,n形成矩陣φ∈Rn×n.定義矩陣p∈Rn×(d+1)其中第i行為[1,(u(i))T].RBF模型可以通過公式(3)得到：

(3)

在此處0(d+1)×(d+1)∈R(d+1)×(d+1)是一個零矩陣，0d+1∈Rd+1是一個零向量，λ=(λ1λ2,…，λn)∈Rn和c=(c1,c2,…，cn)∈Rd+1是線性多項式p(x)的系數(shù)。

我們發(fā)現(xiàn)在進化算法中采用代理模型擬合待優(yōu)化目標(biāo)函數(shù)可以有效地減少進化過程中的評價次數(shù)。在實際應(yīng)用過程中，將該方法與不用代理模型的方式在相同、有限的資源下進行比較，該方法對于優(yōu)化問題可以獲得更好的實驗結(jié)果。因此，為解決優(yōu)化過程中約束條件評價昂貴的問題，本文亦將代理模型添加到種群的進化過程中，同時為了解決在建立多個模型過程中時間復(fù)雜度較高和錯誤率累加的問題，將建立一個代理模型用于擬合從決策空間x到約束條件G(x)的函數(shù)。

為使模型可以更好地引導(dǎo)種群的進化，以及對于模型進行更新，會在種群的每一代個體進化的過程中，選擇一些個體進行真實計算，并且更新代理模型。本文提出用于真實計算的個體的選擇標(biāo)準(zhǔn)為：(1)子代通過模型預(yù)測的值G(x)≤0，說明其通過模型預(yù)測該個體滿足約束解，需要進行真實計算確認(rèn)其是否滿足約束。(2)當(dāng)子代中所有的個體通過模型預(yù)測都不滿足約束的話，則首先根據(jù)所有子代個體的約束違反值G(x)進行升序排列，根據(jù)排序的結(jié)果選擇前NP/10個個體進行真實計算，經(jīng)過計算的個體會用于模型更新。

1.3 約束處理方法詳述

約束優(yōu)化問題廣泛存在于實際的工程中，而且在許多情況下一個優(yōu)化問題中往往存在多個約束條件，這些約束條件可分為不等式約束條件，如公式(4)和等式約束條件，如公式(5).在實際優(yōu)化過程中，往往將等式約束條件轉(zhuǎn)化為不等式約束條件，其轉(zhuǎn)化過程如公式(6)，其中ε表示等式約束條件的容忍度，是一個較小的、接近于0的數(shù)。

gi(x)≤0,i=1,2,…,q

(4)

hj(x)=0,j=q+1,q+2，…,m

(5)

|hj(x)|-ε≤0

(6)

在將等式約束轉(zhuǎn)化為不等式約束之后，待優(yōu)化函數(shù)可表示為：

(7)

在優(yōu)化過程中所有的約束條件都需要被滿足，同時為了避免同時優(yōu)化多個約束條件，因此對每個約束條件做以下處理：

(1)當(dāng)每個約束條件的計算結(jié)果小于0，則表示其滿足該約束條件，故每個約束條件的求解結(jié)果逐個與0作比較，其較大的值為ci(x)的值，如公式(8)，可以發(fā)現(xiàn)當(dāng)ci(x)的值為0則滿足該約束條件。

ci(x)=max(gi(x),0)

(8)

(2)為了避免在種群進化過程中對多個約束條件同時優(yōu)化而導(dǎo)致單目標(biāo)約束問題轉(zhuǎn)化成較為復(fù)雜的多目標(biāo)優(yōu)化問題，我們在經(jīng)過公式(8)的處理之后，將所有的約束條件ci(x)求和，如公式(9)：

(9)

經(jīng)過公式(9)計算之后，待優(yōu)化函數(shù)的多個約束條件轉(zhuǎn)化為一個約束條件G(x)，當(dāng)G(x)=0時，該解滿足所有的約束條件。

1.4 遺傳算法(GA)

遺傳算法(Genetic Algorithm,GA)是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)的全局優(yōu)化搜索算法。它在20世紀(jì)60年代由J.H.Holland教授提出，并且被廣泛用于解決優(yōu)化問題[14]。遺傳算法的主要流程包括：選擇、交叉和變異，在本文中采用了模擬二進制交叉[15]的交叉算子和多項式變異[16]的變異算子，其表示如公式(10)和公式(11).

其中，

(10)

(11)

適當(dāng)?shù)淖儺愃阕幽軌蛟鰪姺N群的多樣性，減少其陷入局部最優(yōu)的概率，同時可以對種群的局部搜索能力進行改進。

在本文中提出的個體選擇策略主要采用的是可行規(guī)則法，可行規(guī)則法具體描述見3.

2 基于代理模型的費時優(yōu)化問題優(yōu)化算法

在解決費時的昂貴約束優(yōu)化問題時，添加代理模型到種群進化過程中能夠有效地降低種群的評價次數(shù)，從而減少實驗代價。在本文提出的基于代理模型的費時昂貴約束優(yōu)化算法中，首先將個體的所有約束違反度進行求和，具體的方法見2.3，然后根據(jù)合并之后的函數(shù)進行建模。通過此方法可以有效的降低由于同時使用多個代理模型而造成的錯誤率累加的問題，并且降低建立代理模型的時間，進而用其在引導(dǎo)種群進化時，減少使得種群向錯誤的方向進化的情況發(fā)生。

本文提出的用于解決昂貴約束問題的基于代理模型輔助的進化算法的算法流程圖，如圖1所示。具體描述如下：

圖1 算法流程圖Fig.1 Flow chart of the algorithm

Step1.依據(jù)拉丁超立方體采樣產(chǎn)生個體，并且進行真實計算，存儲于數(shù)據(jù)庫Data.設(shè)定最大評價次數(shù)ffmax，交叉概率Cr，變異概率Mr，種群數(shù)量Np；

Step2.從數(shù)據(jù)庫中選擇10*D個個體，計算這些個體的約束違反度G(x)，并且建立代理模型M；

Step3.根據(jù)進化算法產(chǎn)生子代個體，計算其適應(yīng)值f(x)，通過模型M預(yù)測其約束違反值G(x).

Step4.根據(jù)可行規(guī)則法對子代和父代進行篩選。可行規(guī)則法具體描述如下：(1)如果兩個個體都滿足約束，則適應(yīng)值較小的個體保留到下一代。(2)如果兩個個體一個滿足約束而一個不滿足約束，那么滿足約束的個體將保留到下一代。(3)如果兩個個體都不滿足約束，則約束違反值較小的個體會保留到下一代；

Step5.選擇ff個體進行真實計算，其選擇標(biāo)準(zhǔn)詳見2.2；

Step6.f=f+ff；

Step7.如果實際評價次數(shù)f小于等于ffmax則進行Step3，否則結(jié)束種群進化，輸出最優(yōu)解。

3 實驗

3.1 實驗函數(shù)選取及參數(shù)設(shè)定

為了驗證本文提出算法的有效性，選取被廣泛采用的CEC2017[19]單目標(biāo)約束測試函數(shù)來進行實驗，同時將本文提出的代理模型的算法框架MGA，與基礎(chǔ)算法GA分別做實驗對比，并進行結(jié)果分析。

實驗過程中用到的參數(shù)有：種群數(shù)量為100，最大評價次數(shù)為1 000次，GA變異概率、交叉概率分別為1/d、1.為了使實驗結(jié)果具有說服力，本文提出的代理模型的算法MGA和原算法GA使用相同的參數(shù)進行實驗對比。同時，為了說明算法在解決昂貴優(yōu)化問題時的有效性，每個測試函數(shù)獨立運行30次，取其均值作為對比結(jié)果。

3.2 結(jié)果及分析

表1展示了添加代理模型的MGA和原算法GA在CEC2017約束測試函數(shù)中的對比實驗結(jié)果。添加代理模型的算法相比原算法在有效次數(shù)評價次數(shù)下，有25個函數(shù)的實驗結(jié)果較好。原函數(shù)GA在1 000次評價次數(shù)下只有5個函數(shù)可以尋找到最優(yōu)解，并且與MGA相比，有三個表現(xiàn)較好。而MGA可以尋找到可行解的函數(shù)有12個，比GA能找到可行解的函數(shù)多7個。另外，在其余的測試函數(shù)中，雖然MGA和GA都未能找到可行解，但是MGA得到的結(jié)果中約束違反值比GA小，所以可以得到使用代理模型能夠有效地解決昂貴約束條件的優(yōu)化問題。

4 結(jié)論與討論

本文提出將代理模型添加到進化算法的框架運用在解決昂貴約束條件的優(yōu)化問題中，通過添加代理模型的MGA與GA在CEC2017約束測試函數(shù)實驗對比顯示： MGA在相同的實驗條件下對比原算法GA可以得到更優(yōu)秀的實驗結(jié)果。這說明本文提出的將代理模型添加到進化算法的框架，來解決昂貴約束條件的優(yōu)化問題是有效的，可以有效降低算法的評價次數(shù)；在實際應(yīng)用過程中，亦可以節(jié)省大量的資源。同時，仍有部分函數(shù)在較少的評價次數(shù)下未能找到可行解，因此在將來，我們將提出更為有效的模型管理方法，使其在更少的資源下可以得到更為優(yōu)秀的結(jié)果。