代理模型輔助的初始可行解產(chǎn)生方法

朱 珂，張國晨，譚 瑛，孫超利

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

尋優(yōu)問題普遍存在于生產(chǎn)、生活中，如房屋設(shè)計、車間流水作業(yè)問題、車輛調(diào)度問題、城市交通管理問題等。這類優(yōu)化問題都要求在滿足主目標(biāo)函數(shù)的同時，滿足其他的約束條件[1-2]。在這類問題中，單目標(biāo)約束優(yōu)化問題(Single Objective Constraints Optimization Problem，簡稱SOCOP)是指包含一個目標(biāo)函數(shù)和多種約束的問題，其中，約束函數(shù)十分復(fù)雜、計算非常昂貴(對于計算電磁學(xué)的一次模擬實驗可能需要20 min[3-4])的問題又被稱為昂貴的單目標(biāo)約束優(yōu)化問題(Expensive Single Objective Constraint Optimization Problem，簡稱ESOCOP).

對于求解ESOCOP，傳統(tǒng)的確定性優(yōu)化算法，主要有梯度投影法、可行方向法、梯度下降法等[5-6]。由于傳統(tǒng)算法的優(yōu)化結(jié)果依賴于初始點的選取，且要求目標(biāo)函數(shù)或約束函數(shù)具有連續(xù)可微的性質(zhì)，所以應(yīng)用范圍有限。進(jìn)化算法因其對函數(shù)性質(zhì)的要求較低，且具有智能性、自適應(yīng)性和自組織性等優(yōu)點而受到了的重視[7]。

粒子群算法(Particle Swarm Optimization，PSO)是由Kennedy和Eberhart于1995年開發(fā)的一種隨機(jī)搜索算法，該算法對所優(yōu)化的目標(biāo)函數(shù)無任何連續(xù)可微的要求，且能在較短的時間內(nèi)求得高質(zhì)量的解，因此得到了廣泛的應(yīng)用。其中，PSO算法解決ESOCOP主要利用其較好的全局搜索能力用于粒子的迭代更新，從而加快優(yōu)化過程[8-9]。但在現(xiàn)實生活中大部分工程問題的目標(biāo)變量取值常包含各種各樣的限制條件，因此如何合理地處理約束成為隨機(jī)優(yōu)化算法在工程應(yīng)用中的核心問題之一[10]。目前針對此問題的技術(shù)主要有罰函數(shù)法、約束保持法以及可行規(guī)則法[11-12]。這三種方法在一定程度上可以降低問題求解的復(fù)雜度，但是它們都存在初始解產(chǎn)生困難導(dǎo)致的計算費時問題。

其中，在采用約束保持法求解SOCOP時，由于其只允許在可行域中的粒子進(jìn)入下一次迭代，因此需要對產(chǎn)生的試驗粒子約束違反度進(jìn)行反復(fù)評價。若要獲得較好的結(jié)果可能需要幾千次、幾萬次甚至幾十萬次的評價，這無疑帶來巨大的資源浪費，所付出的時間和費用以及人力資源代價很難讓人接受。目前很多的算法研究在優(yōu)化階段使用代理模型(Surrogate Model，簡稱SM)預(yù)估目標(biāo)值用以提高算法效率。但尚未有算法研究在生成初始解的階段引入代理模型[13]。

因此，本文提出了基于代理模型輔助的初始可行解產(chǎn)生方法。通過在初始化階段引入代理模型[14]估計約束沖突值的策略，著重考慮減少對試驗粒子的評價次數(shù)，以緩解初始可行解產(chǎn)生費時問題。算法在給定邊界約束范圍內(nèi)隨機(jī)產(chǎn)生初始解后，再由PSO產(chǎn)生試驗種群，此時不對試驗粒子直接進(jìn)行約束沖突值的計算，而是進(jìn)入預(yù)判斷階段，采用初始種群中真實評價過的粒子構(gòu)建模型，此模型用來對試驗粒子約束違反度進(jìn)行預(yù)判，若在可行域中，則進(jìn)行真實約束沖突值的計算。本文通過對CEC2017的28個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行測試，驗證了所提算法可大大減少評價次數(shù)，解決計算昂貴問題。

1 相關(guān)知識

單目標(biāo)約束優(yōu)化問題的數(shù)學(xué)模型可定義為如下所示：

miny=f(x)

s.t.gi(x)≤0;1

hj(x);a+1

x=(x1,x2，…，xn)∈Rn

(1)

在式(1)中，xmin

E=|x|gi(x)≤0，hi(x)=0，

|1

(2)

1.1 約束保持法

約束保持法是目前求解帶有約束的問題時處理約束的主要方法之一。該方法的主要思想是確保進(jìn)化過程中所有粒子始終在可行域范圍內(nèi)，并且該方法要求初始解都必須在可行域中。約束保持法對初始種群的要求較高，故存在初始種群產(chǎn)生困難的問題，本文針對約束保持法初始解產(chǎn)生困難問題展開研究。

對于約束保持法解決約束優(yōu)化費時問題，當(dāng)前研究主要采用：在初始化粒子時，直接在給定約束范圍內(nèi)隨機(jī)產(chǎn)生點，并對這些點的約束沖突值進(jìn)行評估，若粒子違反其中任一約束條件，則重新產(chǎn)生點，重復(fù)上述過程，直到找到所需初始可行解的個數(shù)。

約束保持法尋找可行初始解的過程中，其產(chǎn)生可行解沒有規(guī)律性，因此很長一段時間內(nèi)都無法產(chǎn)生滿足約束條件的可行初始解。而本文針對上述所提問題展開研究，所提算法很大程度上提高了初始可行解的產(chǎn)生效率。

1.2 拉丁超立方體抽樣

傳統(tǒng)隨機(jī)抽樣方法，總體樣本不進(jìn)行分類、分組等，每個樣本被抽中的概率都相等。樣本中的個體完全獨立，彼此間無關(guān)聯(lián)性和排斥性，這種采樣方式僅適用于總體樣本之間差異程度較小和樣本數(shù)目較少的情況。但是樣本數(shù)較大或樣本差異較大時容易出現(xiàn)數(shù)據(jù)過度聚集的問題。

本文采用的拉丁超立方體采樣[15]先將樣本按其差異程度或某一特征進(jìn)行分類、分層，然后在各類或每層中再隨機(jī)抽取樣本單位。這種采樣方式考慮了樣本本身的特性，使得每類或每個分組都可以等概率的被采樣點覆蓋，抽取的樣本分布比較均勻，保持了樣本的多樣性。采樣過程如算法1所示：

算法1:超立方體采樣過程假設(shè):D向量空間,搜索范圍[xmin,xmax]里抽取模NP個樣本;Step1:在D維搜索空間中,每一維的搜索范圍[xmin,xmax]分為模NP等份,每個小區(qū)間內(nèi)[i(xmax-xmin)/NP,(i+1)(xmax-xmin)/NP] 根據(jù)均勻分布隨機(jī)產(chǎn)生一個數(shù);Step2:將這NP個隨機(jī)數(shù)的順序打亂;Step3:這NP個數(shù)即為:每個隨機(jī)樣本的概率,按照概率分布函數(shù)的反函數(shù)生成隨機(jī)分布的值。

1.3 粒子群優(yōu)化算法(PSO)

粒子群算法[8-9]是由Kennedy博士和Eberhart博士等于1995年提出來的智能優(yōu)化算法，其算法思想來源于對鳥群和魚群覓食行為的模擬。PSO依據(jù)對環(huán)境的適應(yīng)度來引導(dǎo)種群中的個體向好的區(qū)域移動。該算法中粒子在搜索空間中以一定的速度飛行，忽略其質(zhì)量和體積。該速度根據(jù)粒子自身及種群中其他個體的飛行位置動態(tài)調(diào)整。第t+1代每個微粒在第d維上的速度和位置更新方程如下：

vid(t+1)=wvid(t)+c1r1(pid(t)-

xid(t))+c2r2(pgd(t)-xid(t))

(3)

xid(t+1)=xid(t)+vid(t+1)

(4)

其中，慣性權(quán)重w使粒子保持運(yùn)動慣性，使其有能力探索新的區(qū)域，c1調(diào)節(jié)粒子飛向自身最好位置方向的步長，c2調(diào)節(jié)粒子向全局最好位置飛行的步長。式(3)等號右側(cè)分三部分，第一部分為粒子原先的速度，記錄粒子的運(yùn)動方向；第二部分為粒子的“認(rèn)知”部分，表示對粒子對自身最優(yōu)位置的記憶；第三部分為粒子的“社會”部分，表示粒子之間的信息共享和合作，代表了粒子有向群體最佳位置靠近的趨勢。式(3)和式(4)可用于進(jìn)化算法中對粒子位置的更新。

2 代理模型輔助的粒子群算法初始可行解生成方法

2.1 模型選擇

本文采用徑向基函數(shù)RBF[16-17](Radial-based Function)來構(gòu)建模型。RBF是一種插值模型，已廣泛應(yīng)用于各種科學(xué)和工程領(lǐng)域[18]。同時利用該模型求解復(fù)雜優(yōu)化問題的有效性已經(jīng)得到的了證明[19]。RBF使用簡單基函數(shù)的加權(quán)和來內(nèi)插散點。給定數(shù)據(jù)點x1，x2……xn∈RD和函數(shù)值f(x1)，f(x2)，…，f(xn)，RBF的插值模型為：

(5)

其中：φi(·)是第i個基函數(shù)，‖·‖代表歐氏距離，λi表示第i個基函數(shù)的權(quán)重。

徑向基函數(shù)的未知參數(shù)(λ1，λ2，…λn∈RD)可以作為線性方程的解獲得：

(6)

其中：φ是一個n×n的矩陣，φij=φ(‖xi-xj‖)

(7)

(8)

因此，由式(5)-式(8)可以構(gòu)建徑向基模型用于進(jìn)化算法中對目標(biāo)值的預(yù)測，從而減少真實評價次數(shù)。

2.2 約束沖突值計算方式

測試函數(shù)中包含的等式約束首先需將等式約束轉(zhuǎn)化成不等式約束，再進(jìn)行優(yōu)化。其中：ε=0.000 1，如果|hj(x)|-ε≤0，j=p+1，…，m那么認(rèn)為粒子在該約束條件下可行。轉(zhuǎn)換方式如式(9)所示，算法約束處理步驟如算法2所示。

Hj(x)=|hj(x)|-ε，j=p+1，…，m (9)

由于每個單目標(biāo)約束優(yōu)化問題都在對應(yīng)一個目標(biāo)函數(shù)的同時，對應(yīng)著一個或多個約束函數(shù)。相應(yīng)地，每個粒子對應(yīng)一個目標(biāo)函數(shù)值的同時也對應(yīng)一個或多個約束函數(shù)值，因此本文中所提到的約束沖突值即為將每個粒子對應(yīng)的一個或多個約束函數(shù)值按算法2整合成的一個sum值。

2.3 模型評價方式

研究中首先根據(jù)隨機(jī)搜索建立初始樣本庫，采用初始樣本庫中的樣本構(gòu)建RBF模型，在算法執(zhí)行過程中根據(jù)實驗粒子的信息在線更新RBF模型，以使得該模型的估計精度越來越高。

2.3.1 樣本庫構(gòu)建

1)初始樣本庫

隨機(jī)產(chǎn)生NP個在給定邊界約束范圍內(nèi)的粒子，并對每一個當(dāng)前粒子q(i)進(jìn)行約束沖突值的真實評價。建模訓(xùn)練樣本數(shù)據(jù)集的輸入為粒子的位置信息xi=(xi1，xi2，…，xid)，i=1，2，…，NP，輸出為約束沖突函數(shù)值。其中d表示問題維度，NP為樣本個數(shù)。同時文獻(xiàn)[20]對不同RBF的應(yīng)用進(jìn)行了分析和總結(jié)，認(rèn)為高斯函數(shù)適用于隨機(jī)數(shù)的模擬，因此本文采用高斯函數(shù)為基函數(shù)，從而構(gòu)建式(5)所示的RBF插值模型，模型參數(shù)可通過求解式(6)的線性方程獲得。

2)樣本庫更新

使用上述所構(gòu)建的RBF模型，將試驗粒子q(i)的位置信息作為輸入，模型的輸出即為該試驗粒子的約束沖突值。若當(dāng)前代預(yù)估出滿足可行域的試驗粒子s(i)，則真實評價s(i)后放入模型庫中用來更新模型；若沒有預(yù)估出滿足可行域的粒子，則選擇當(dāng)前代預(yù)估約束沖突值最小的粒子smin(i)強(qiáng)行真實評價，評價后smin(i)的位置及約束沖突值用來更新模型。

2.3.2 粒子更新準(zhǔn)則

產(chǎn)生試驗粒子s(i)后，若模型估計其滿足約束，則進(jìn)行真實計算。真實計算后，若滿足約束則比較s(i)和當(dāng)前粒子q(i)的約束沖突值，約束沖突值小的更新為個體最優(yōu)pbest；若不滿足約束，則個體最優(yōu)pbest不更新。若模型估計其不滿足約束，則個體最優(yōu)pbest不更新。C庫中有可行解，則每次隨機(jī)選擇一個可行粒子更新全局最優(yōu)gbest；若C中無可行粒子，則選擇當(dāng)前種群最小約束沖突值的粒子更新gbest.

2.4 本文所提算法的具體步驟

本文所提代理模型輔助的初始可行解產(chǎn)生方法，主要是采用徑向基函數(shù)構(gòu)建代理模型，并使用代理模型估計試驗粒子的約束沖突值。具體步驟如算法3所示。

算法3:具體步驟Step1:參數(shù)設(shè)置:群體規(guī)模NP,慣性權(quán)重ω,加速權(quán)重c1和c2,最大速度vmax最小速度vmin,真實評價庫Archive,可行解庫C;Step2:拉丁超立方體采樣,產(chǎn)生微粒的初始位置及初始速度;Step3:對每個微粒i進(jìn)行真實約束沖突值計算,真實計算后的粒子i的位置信息及約束沖突值存放在Archive中;Step4:在可行域中的粒子放入C庫中;

Step5:產(chǎn)生個體最優(yōu)pbest以及全局最優(yōu)gbest;Step6:使用粒子群算法速度更新公式(3)(4)更新粒子的位置信息,并產(chǎn)生實驗個體s(i);Step7:采用Archive中的粒子建立模型,該模型估計試驗個體s(i)約束沖突值;Step8:若預(yù)估s(i)在可行域中,則對s(i)的約束沖突值進(jìn)行真實計算,并將該粒子s(i)的位置信息放入Archive中,否則轉(zhuǎn)Step10;Step9:真實計算后滿足約束條件的試驗粒子s(i)的位置信息放入C中,否則轉(zhuǎn)到Step10;Step10:若當(dāng)前代沒有粒子被預(yù)估在可行域中,則選擇預(yù)估值最小的粒子進(jìn)行真實評價,評價后的粒子信息放入Archive中,否則轉(zhuǎn)到Step11;Step11:根據(jù)更新準(zhǔn)則更新個體最優(yōu)pbest以及全局最優(yōu)gbest;Step12:若未達(dá)到結(jié)束條件(設(shè)置為產(chǎn)生滿足要求的初始解的個數(shù)),則返回Step 6.

3 實驗結(jié)果及分析

3.1 采樣方式

對于樣本庫中的粒子，本文算法分別將樣本數(shù)設(shè)為10D、20D、50D(D代表維度)以及樣本庫中所有粒子來更新模型。其中，若模型庫中的粒子數(shù)不足所要求的建模數(shù)量時，則將樣本庫中的粒子全部用于構(gòu)建模型。本文經(jīng)過對10D、20D、50D以及全部樣本建模的實驗結(jié)果表明，在低維問題中，樣本數(shù)越多構(gòu)建的模型可以找到更多的解，因此最終采用Archive中全部粒子來構(gòu)建模型時。

3.2 結(jié)果及分析

為驗證方法的有效性，本文針對cec2017[21]中的28個標(biāo)準(zhǔn)單目標(biāo)約束函數(shù)進(jìn)行測試，具體實驗結(jié)果如表1所示。并與傳統(tǒng)粒子群算法的可行初始解產(chǎn)生方法進(jìn)行比較，以下簡稱其為傳統(tǒng)方法。在表1中給出種群大小NP=100，維度D=10，獨立運(yùn)行30次的運(yùn)行結(jié)果。

表1 傳統(tǒng)算法與本文所提算法實驗結(jié)果

表1中對比實驗1是約束值評價1 000次，兩種算法所找可行解個數(shù)，找到可行解個數(shù)多的方法即為好方法。對比實驗1中：在C01-C05、C20測試函數(shù)上傳統(tǒng)及所提方法均能找到可行解，且所提方法找到可行解個數(shù)大于傳統(tǒng)方法，其中C02、C05效果尤為明顯；在C06-C10、C12-C14、C21-C25測試函數(shù)中，傳統(tǒng)方法無法找到可行解，而所提方法可以找到可行解；C15、C16函數(shù)中，傳統(tǒng)方法找到可行解的實驗次數(shù)分別為8次和5次，而所提方法30次獨立實驗均可找到可行解，且找到可行解個數(shù)遠(yuǎn)大于傳統(tǒng)方法。因此，在試驗1中本文所提算法在相同評價次數(shù)條件下，能找到更多的可行解，效果明顯好于傳統(tǒng)算法。

表1中對比試驗2是設(shè)置找到100個可行解時，兩種算法所需的評價次數(shù)對比，評價次數(shù)少的方法較好。該實驗僅針對可以找到可行解的測試函數(shù)做對比。對比實驗2中：在C01-C05、C12、C14-C16、C20-C21、C23-C25測試函數(shù)上，所提方法的評價次數(shù)均小于傳統(tǒng)方法。其中在C02、C05、C12、C14-C16、C21、C23-C25測試函數(shù)上所提算法評價次數(shù)遠(yuǎn)小于傳統(tǒng)方法；在C06-C10、C13、C22測試函數(shù)上，傳統(tǒng)方法均無法找到可行解，而所提算法可以找到可行解。因此，對比實驗2中，在產(chǎn)生初始可行解效率方面，本文所提算法同樣優(yōu)于傳統(tǒng)算法，能在找到相同數(shù)量可行解的情況下大大減少評價次數(shù)，提高生成初始解的效率。

4 總結(jié)

針對采用約束保持法的粒子群算法在產(chǎn)生初始可行解時存在評價次數(shù)過高、計算昂貴的問題，本文將代理模型預(yù)估約束沖突值的策略引入算法產(chǎn)生初始可行解的過程中。在初始種群更新位置信息后，首先進(jìn)行約束沖突值預(yù)判斷，預(yù)判可行的粒子才進(jìn)行真實評價，用以減少浪費資源評價不可行粒子的次數(shù)。實驗結(jié)果證明本文所提算法能解決產(chǎn)生初始可行解困難的問題。未來將進(jìn)一步豐富和完善初始可行解產(chǎn)生機(jī)制，提高策略的穩(wěn)定性，獲得更精確的粒子評估資源。在此基礎(chǔ)上，將本文所提算法運(yùn)用到的智能優(yōu)化算法中，提高算法優(yōu)化效率。