張慧晶，張國(guó)晨，譚 瑛，孫超利

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

0 引言

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

傳統(tǒng)算法在解決約束優(yōu)化問題時(shí)需要消耗大量的評(píng)價(jià)次數(shù)，因此使用傳統(tǒng)優(yōu)化算法解決該問題時(shí)，往往會(huì)因?yàn)閷?shí)驗(yàn)代價(jià)昂貴而受到限制。進(jìn)化算法在求解約束優(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)將個(gè)體分為可行解和不可行解，然后根據(jù)解的類型分別進(jìn)行優(yōu)化的方法；(4)混合類型的優(yōu)化算法，即同時(shí)具有以上兩種或者三種的方法的優(yōu)化算法。其中在以上四種類型的優(yōu)化算法中最常用的是對(duì)不可行解添加罰函數(shù)的方法，但由于需要添加過多懲罰因子，該方法在應(yīng)用過程中受到很大的限制。

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

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

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

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

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

1 相關(guān)工作

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

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

(1)

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

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

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

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

(2)

在公式(2)中，‖·‖表示歐氏距離，p(x)是一個(gè)線性多項(xiàng)式，φ表示三次多項(xiàng)式具體形式為φ(r)=r3，λi∈R是三次多項(xiàng)式的系數(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)是一個(gè)零矩陣，0d+1∈Rd+1是一個(gè)零向量，λ=(λ1λ2,…，λn)∈Rn和c=(c1,c2,…，cn)∈Rd+1是線性多項(xiàng)式p(x)的系數(shù)。

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

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

1.3 約束處理方法詳述

約束優(yōu)化問題廣泛存在于實(shí)際的工程中，而且在許多情況下一個(gè)優(yōu)化問題中往往存在多個(gè)約束條件，這些約束條件可分為不等式約束條件，如公式(4)和等式約束條件，如公式(5).在實(shí)際優(yōu)化過程中，往往將等式約束條件轉(zhuǎn)化為不等式約束條件，其轉(zhuǎn)化過程如公式(6)，其中ε表示等式約束條件的容忍度，是一個(gè)較小的、接近于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)化過程中所有的約束條件都需要被滿足，同時(shí)為了避免同時(shí)優(yōu)化多個(gè)約束條件，因此對(duì)每個(gè)約束條件做以下處理：

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

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

(8)

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

(9)

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

1.4 遺傳算法(GA)

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

其中，

(10)

(11)

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

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

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

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

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

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

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

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

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

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

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

Step6.f=f+ff；

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

3 實(shí)驗(yàn)

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

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

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

3.2 結(jié)果及分析

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

4 結(jié)論與討論

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