張建俠，宋明順，方興華，鄧鈺佳

(中國計(jì)量大學(xué) 經(jīng)濟(jì)與管理學(xué)院，浙江 杭州 310018)

0 引言

實(shí)踐中的優(yōu)化設(shè)計(jì)問題通常是多目標(biāo)優(yōu)化問題(Multiobjective Optimization Problem, MOP)。由于優(yōu)化目標(biāo)之間的沖突性，MOP一般不存在單個(gè)絕對的最優(yōu)解，其目標(biāo)是尋求一組Pareto最優(yōu)意義下的折衷解[1](Pareto Set, PS)。智能優(yōu)化算法(如多目標(biāo)進(jìn)化算法)是求解MOP的有效方法，但由于在優(yōu)化進(jìn)程中需要大量調(diào)用函數(shù)，不能滿足昂貴仿真情形下的優(yōu)化設(shè)計(jì)需求[2]。為提高復(fù)雜系統(tǒng)的優(yōu)化設(shè)計(jì)效率，基于近似模型的代理優(yōu)化方法應(yīng)運(yùn)而生[3-4]。

Kriging模型可以同時(shí)提供任意試驗(yàn)點(diǎn)上的預(yù)測值及預(yù)測誤差，易于構(gòu)造引導(dǎo)優(yōu)化過程快速收斂的自適應(yīng)優(yōu)化策略[5]。以有效全局優(yōu)化(Efficient Global Optimization, EGO)算法[6]為代表的自適應(yīng)代理優(yōu)化算法，合理利用設(shè)計(jì)的加點(diǎn)準(zhǔn)則序貫選取能收斂到全局最優(yōu)解的新試驗(yàn)點(diǎn)，優(yōu)化效率比傳統(tǒng)進(jìn)化類方法高出1～2個(gè)數(shù)量級[7]。近年來，自適應(yīng)優(yōu)化思想逐漸推廣至MOP。由于容易理解和執(zhí)行，學(xué)者們常采用直接優(yōu)化Pareto解集質(zhì)量指標(biāo)(performance indicator)的方式優(yōu)化原MOP[8]。

文獻(xiàn)[9]基于超體積(HyperVolume, HV)質(zhì)量指標(biāo)，提出了期望超體積改進(jìn)(Expected Hypervolume Improvement, EHVI)準(zhǔn)則及其精確計(jì)算方法，并證明了EHVI準(zhǔn)則的單調(diào)性質(zhì);文獻(xiàn)[10]對ParEGO等4種多目標(biāo)代理優(yōu)化算法進(jìn)行了比較，指出基于EHVI準(zhǔn)則的代理優(yōu)化算法是唯一一種在求解人工構(gòu)造問題和實(shí)際工程問題時(shí)，都表現(xiàn)優(yōu)異的算法?？尚行愿怕?Probability of Feasibility, PoF)準(zhǔn)則能估計(jì)試驗(yàn)點(diǎn)落入可行域的概率，在代理優(yōu)化研究中常被用于設(shè)計(jì)黑箱約束的應(yīng)對策略[11]。文獻(xiàn)[12]進(jìn)一步指出，基于PoF準(zhǔn)則的約束應(yīng)對策略不需要擬合拉格朗日乘子函數(shù)和選擇罰因子，與基于增廣拉格朗日乘子法的約束優(yōu)化策略[13]相比，更易于執(zhí)行且優(yōu)化效果好;文獻(xiàn)[14]將PoF準(zhǔn)則分別與Kriging模型預(yù)測標(biāo)準(zhǔn)差和EHVI準(zhǔn)則結(jié)合，提出了探索MOP可行域和改進(jìn)PS質(zhì)量的加點(diǎn)策略。當(dāng)優(yōu)化問題包含多個(gè)非連通可行子區(qū)域時(shí)，其可行域探索準(zhǔn)則不能確保找出所有子區(qū)域，且近似PS改進(jìn)準(zhǔn)則逼近可行域邊界上最優(yōu)解的效率不高[15]。

評估算法的收斂性是代理優(yōu)化研究的另一課題。文獻(xiàn)[16]歸類分析了多目標(biāo)進(jìn)化算法研究中的收斂準(zhǔn)則，并強(qiáng)調(diào)了綜合應(yīng)用多個(gè)評估指標(biāo)(如Epsilon、R2等)的重要性。對多目標(biāo)代理優(yōu)化算法，代理模型的近似誤差將會(huì)影響求得的近似PS，因此PS的不確定性反映了算法的收斂性。條件模擬(conditional simulation)與Kriging模型有相同理論基礎(chǔ)，但更側(cè)重于對區(qū)域變量空間分布的隨機(jī)模擬，被廣泛應(yīng)用于地質(zhì)、土壤、水文、生態(tài)等領(lǐng)域的不確定性評價(jià)[17]。針對固定翼飛機(jī)采集地面火災(zāi)數(shù)據(jù)存在采樣不足的問題，文獻(xiàn)[18]提出了利用Kriging模型和條件模擬擬合火輻射能量密度的方法;文獻(xiàn)[19]針對不考慮約束影響的優(yōu)化問題，分析了條件模擬方法評估算法收斂性的可能性。

為提高黑箱系統(tǒng)多目標(biāo)優(yōu)化設(shè)計(jì)的效率，綜合考慮Kriging模型的預(yù)測不確定性、試驗(yàn)點(diǎn)的PoF和EHVI、試驗(yàn)點(diǎn)之間的距離，并利用隨機(jī)集理論，提出一種改進(jìn)的多目標(biāo)代理優(yōu)化算法及收斂性分析方法。該算法對可行域非連通的問題也有效；近似PS改進(jìn)準(zhǔn)則兼具刻畫可行域邊界的能力；收斂性評估從分析近似PS不確定性的角度評估算法的收斂性。通過兩個(gè)算例與已有算法作比較，計(jì)算結(jié)果驗(yàn)證了所提算法的高效性。

1 多目標(biāo)優(yōu)化和Kriging模型

1.1 問題描述

一個(gè)典型的包含m個(gè)目標(biāo)函數(shù)和r個(gè)約束條件的MOP可以表示為

s.t.

gi(x)≤0,i=1,…,r;

x∈X?d。

(1)

其中：m>1;x為d維設(shè)計(jì)變量;y(x)為目標(biāo)函數(shù)向量;gi(x)為第i個(gè)約束條件。由于優(yōu)化目標(biāo)之間的沖突性，MOP通常不存在絕對的最優(yōu)解，而是尋求一組Pareto意義下的折衷解[1]。設(shè)G為問題(1)的可行域，x,x′∈G是兩個(gè)可行解，稱x支配x′(記作xx′)當(dāng)且僅當(dāng)：?i∈{1,…,m},yi(x)≤yi(x′)∧y(x)≠y(x′)。Pareto最優(yōu)解集(PS)是所有Pareto最優(yōu)解構(gòu)成的集合：PS={x∈G|x*∈G:x*x}。PS在目標(biāo)空間上的投影稱為Pareto最優(yōu)前沿(Pareto Front, PF)：PF={y(x)|x∈PS}。

1.2 Kriging模型

Kriging模型將仿真模型的響應(yīng)y(x)看作是隨機(jī)過程的實(shí)現(xiàn)，即

(2)

(3)

1.3 其他相關(guān)概念

辨識優(yōu)化問題可行域、改進(jìn)PS質(zhì)量是多目標(biāo)代理優(yōu)化算法的基本功能。為此，首先介紹以下概念。

(1)期望超體積改進(jìn)[9]

超體積指的是被PF支配的空間的體積，其取值越大越好。超體積改進(jìn)(HV Improvement，HVI)則被用來度量新試驗(yàn)數(shù)據(jù)(x,y(x))帶來的超體積的增量。

HVI(x)=HVI(y(x),PF,r)=

(4)

(5)

(2)可行性概率[11]

考慮約束條件的影響，令G={x∈X|g(x)≤0}表示可行域，則新試驗(yàn)點(diǎn)x帶來的可行超體積改進(jìn)為

I(x)=I(y(x),PF,r)=1g(x)≤0·

HVI(y(x),PF,r)

(6)

其中1g(x)≤0為示性函數(shù)。若目標(biāo)函數(shù)y獨(dú)立于約束條件g，則新試驗(yàn)點(diǎn)x帶來的期望的可行超體積改進(jìn)可表示為

HVI(y(x),PF,r))

(7)

(3)條件模擬

(8)

2 基于Kriging模型的多目標(biāo)代理優(yōu)化算法

本文提出的多目標(biāo)代理優(yōu)化算法(Surrogate-based Multiobjective Optimization Algorithm, SMOA)的基本流程如圖1所示,包括辨識可行域、改進(jìn)解集質(zhì)量及評估解集不確定性3個(gè)主要部分。

2.1 辨識可行域和改進(jìn)近似PF

(1)辨識可行域

若MOP的約束條件較難滿足(如可行域較小)，初始樣本點(diǎn)集不含可行試驗(yàn)點(diǎn)，則先用以下加點(diǎn)準(zhǔn)則選取一個(gè)可行試驗(yàn)點(diǎn)：

(9)

(10)

(2)改進(jìn)近似PF

約束優(yōu)化問題的最優(yōu)解通常位于可行域邊界上。為此，提出如下兼顧目標(biāo)改進(jìn)和可行域邊界刻畫的近似PF改進(jìn)準(zhǔn)則：

Cpf(x)=maxx∈Ppf(EHVI(x)·PoF(x))。

(11)

式中Ppf表示備選樣本集(同時(shí)優(yōu)化EHVI和PoF時(shí)求得的Pareto集),

Ppf=maxx∈X(EHVI(x),PoF(x))。

(12)

式中EHVI(x)=EHVI(x,PF,r)表示試驗(yàn)點(diǎn)x的期望超體積改進(jìn)。從具有Pareto最優(yōu)性的備選樣本集中選取新試驗(yàn)點(diǎn)，不僅縮小了新試驗(yàn)點(diǎn)選擇范圍、避免在無效區(qū)域選取新試驗(yàn)點(diǎn)，還使新試驗(yàn)點(diǎn)兼具了刻畫可行域邊界的能力，進(jìn)而提高Cpf(x)準(zhǔn)則選取新試驗(yàn)點(diǎn)和改進(jìn)近似PF的針對性，提高優(yōu)化效率和穩(wěn)健性。

2.2 度量近似PF的不確定性

工程實(shí)踐中MOP的真實(shí)PF是未知的，使優(yōu)化算法的收斂性評估遇到困難(Epsilon、世代距離等解集質(zhì)量指標(biāo)需要用到真實(shí)PF)。為此，提出一種利用條件模擬度量近似PF不確定性，并將其作為算法收斂性評價(jià)依據(jù)的間接方法。

(1)條件Pareto前沿(Conditional Pareto Fronts，CPFs)

條件模擬方法生成N個(gè)CPFs的步驟見算法1，這些CPFs反映了近似PF的不確定。

算法1生成N個(gè)CPFs。

步驟1選取模擬點(diǎn)。

(1)隨機(jī)生成n個(gè)模擬點(diǎn){e1,…,en}?X?d。

(2)利用約束條件的Kriging模型，選出“可行”的模擬點(diǎn){e1′,…,en′}。

步驟2利用條件模擬方法預(yù)測目標(biāo)函數(shù)響應(yīng)值：

步驟3利用“可行”的模擬點(diǎn)及響應(yīng)數(shù)據(jù)，生成一個(gè)條件PF及條件PS。

步驟4重復(fù)以上步驟N次，得到N個(gè)CPFs。

文獻(xiàn)[22]證明了CPFs在分布上與被其支配的隨機(jī)集等價(jià)。因此，CPFs的不確定性又可借助Vorob’ev期望和方差的概念加以描述[23]。

(2)Vorob’ev期望和方差

定義1收斂函數(shù)和上水平集[22-23]。設(shè)Y是拓?fù)淇臻gB?m中的隨機(jī)閉集，定義Y的收斂函數(shù)(coverage function)為pY:y∈BP(y∈Y)。利用收斂函數(shù)，定義Y的上水平集(upper level set)為Qβ={z∈B,pY(z)≥β}，并稱β為分位數(shù)。

定義2Vorob’ev期望和方差[22-23]。令m表示m上的勒貝格測度且E(m(Y))≤+∞，若存在β*滿足E(m(Y))=m(Qβ*),則定義Y的Vorob’ev期望為其上水平集Qβ*;否則，先用式子{m(Qβ)≤E(m(Y))≤m(Qβ*),?β>β*}求分位數(shù)β*,再令對應(yīng)的水平集Qβ*為Y的Vorob’ev期望。定義Y與其Vorob’ev期望Qβ*的對稱差的期望E(μ(Qβ*ΔY))為Y的Vorob’ev方差。

(3)近似PF的不確定性

算法2評估近似PF的不確定性(求Vorob’ev期望和方差)。

步驟1利用算法1生成近似PF的CPFs。

步驟4二分法求Vorob’ev期望的β*分位數(shù)

(1)取a=0,b=1。

步驟5利用收斂函數(shù)和β*，確定Y的Vorob’ev期望Qβ*(上水平集)。

3 算例與結(jié)果分析

本章通過兩個(gè)典型算例，將提出的SMOA算法與文獻(xiàn)[14]的KEMOCO代理優(yōu)化算法及U-NSGA-Ⅲ[24]進(jìn)化算法作比較，以驗(yàn)證SMOA算法的有效性、高效性及條件模擬方法評估算法收斂性的可行性。

3.1 數(shù)值算例

算例1

f1(x)=(x1-10)2+(x2-15)2+10,

(13)

其中x=(x1,x2)∈[-5,10]×[0,15]。算例1為自構(gòu)造函數(shù)。

算例2[25]

f1(x)=-(25(x1-2)2+(x2-2)2+

(x3-1)2+(x4-4)2+(x5-1)2),

g1=2-x1-x2≤0,

g2=x1+x2-6≤0,

g3=x2-x1-2≤0,

g4=x1-3x2-2≤0

g5=(x3-3)2+x4-4≤0,

g6=4-(x5-3)2-x6≤0。

(14)

其中：x1,x2,x6∈[0,10],x3,x5∈[1,5],x4∈[0,6]。

算例1的可行域由3個(gè)非連通子區(qū)域組成且可行域占設(shè)計(jì)變量空間的比例小，可用于驗(yàn)證SMOA算法可行域探索準(zhǔn)則的有效性。算例2包含6個(gè)變量和6個(gè)約束條件，可用于驗(yàn)證SMOA算法在求解較復(fù)雜MOP時(shí)的高效性和通用性。

3.2 試驗(yàn)設(shè)定

為方便分析，首先對算例的變量作歸一化處理，使x∈[0,1]d。其次，假定算例的目標(biāo)和約束條件相互獨(dú)立，并分別構(gòu)建他們的Kriging模型(取初始設(shè)計(jì)的樣本容量為k=5×d，其中d為設(shè)計(jì)變量的維數(shù))。這是由于：優(yōu)化問題函數(shù)之間的相關(guān)性信息通常是未知的，且構(gòu)建多函數(shù)聯(lián)合Kriging模型的過程復(fù)雜、易出現(xiàn)數(shù)值不穩(wěn)定，在實(shí)踐中并未表現(xiàn)出更好的預(yù)測精度[26]。

SMOA算法包含兩個(gè)需要預(yù)先設(shè)定的參數(shù)q和tfea。其中，距離項(xiàng)(D(x))q中的參數(shù)q對可行域探索準(zhǔn)則Cfea(x)的探索能力有很大影響，經(jīng)過反復(fù)測試，建議對有多個(gè)非連通可行子區(qū)域的優(yōu)化問題(如算例1)取q=2，對可行域單連通的優(yōu)化問題(如算例2)取q=1。鑒于Cfea(x)準(zhǔn)則中的距離項(xiàng)能迫使新試驗(yàn)點(diǎn)彼此遠(yuǎn)離，進(jìn)而在可行域中分布均勻，此處將用于辨識可行域的可行試驗(yàn)點(diǎn)的數(shù)量設(shè)定為tfea=10(足以刻畫出可行域的輪廓)。此外，本文選取有20個(gè)隨機(jī)初始點(diǎn)的擬牛頓法BFGS算法優(yōu)化Cfea(x)準(zhǔn)則，以保證新試驗(yàn)點(diǎn)選取的準(zhǔn)確性；在改進(jìn)近似PF時(shí)，選取種群大小為100、進(jìn)化代數(shù)為200的U-NSGA-Ⅲ算法生成Cpf(x)準(zhǔn)則的備選試驗(yàn)點(diǎn)集。

在比較SMOA、KEMOCO以及U-NSGA-Ⅲ算法的優(yōu)化性能時(shí)，本文以試驗(yàn)的總次數(shù)T作為SMOA和KEMOCO算法的終止條件，取U-NSGA-Ⅲ算法的種群大小為100、進(jìn)化代數(shù)為200，并選取相對超體積(Relative HV，RHV)、Epsilon和R2指標(biāo)評估算法的優(yōu)化性能，用這些指標(biāo)分別描述近似PF與真實(shí)PF之間的相對誤差、最大最小距離和平均距離[27]。

3.3 優(yōu)化結(jié)果分析

KEMOCO算法直接以EHVI與PoF的乘積作為近似PF的改進(jìn)準(zhǔn)則。本文SMOA算法首先以同時(shí)最大化EHVI和PoF為目標(biāo)生成具有Pareto最優(yōu)性的備選點(diǎn)集Ppf，再從中選取新試驗(yàn)點(diǎn)，不僅提高了新試驗(yàn)點(diǎn)選取的目的性，還使其兼具了改進(jìn)最優(yōu)解和刻畫可行域邊界的能力，保證了算法的優(yōu)化效率和精度。通過兩個(gè)數(shù)值算例，在45組隨機(jī)初始試驗(yàn)設(shè)計(jì)下，用SMOA和KEMOCO算法的PF改進(jìn)準(zhǔn)則改進(jìn)可行域探索階段得到的近似PF，并與U-NSGA-Ⅲ算法的優(yōu)化結(jié)果作比較，得到的解集質(zhì)量指標(biāo)數(shù)據(jù)如表1所示。表中，算例1的真實(shí)PF是通過比較細(xì)密網(wǎng)格點(diǎn)上目標(biāo)和約束函數(shù)的取值得到的；算例2的自變量維度高，難以用網(wǎng)格點(diǎn)法確定其真實(shí)PF，為此將由U-NSGA-Ⅲ算法(種群大小取200，進(jìn)化代數(shù)取500)求得的“高精度”PF當(dāng)作真實(shí)的PF。

表1 不同優(yōu)化算法求得的近似PF的質(zhì)量指標(biāo)數(shù)據(jù)(45組)

由表1的指標(biāo)數(shù)據(jù)可以看出：用SMOA算法求解算例1和算例2，得到的解集質(zhì)量指標(biāo)數(shù)據(jù)明顯優(yōu)于KEMOCO算法的相應(yīng)數(shù)據(jù)(差異性檢驗(yàn)結(jié)果如表2)，且SMOA算法優(yōu)化結(jié)果的標(biāo)準(zhǔn)差更小。說明本文所提近似PF改進(jìn)準(zhǔn)則(式(11))，兼具了改進(jìn)目標(biāo)函數(shù)和刻畫可行域邊界的功能，具有更高的優(yōu)化精確和穩(wěn)定性。算例1的優(yōu)化結(jié)果數(shù)據(jù)還顯示SMOA算法和U-NSGA-Ⅲ算法的優(yōu)化精度在同一數(shù)量級，證明SMOA算法具有類似于多目標(biāo)進(jìn)化算法的優(yōu)化能力但優(yōu)化效率更高(SMOA算法的試驗(yàn)次數(shù)是T=80，遠(yuǎn)小于U-NSGA-Ⅲ算法的試驗(yàn)次數(shù)T=20 000)。

表2 SMOA算法與KEMOCO算法優(yōu)化效果差異性檢驗(yàn)(配對t檢驗(yàn)，差異性水平0.05)

3.4 算法收斂性評估

當(dāng)真實(shí)PF未知時(shí)，解集質(zhì)量指標(biāo)難以評價(jià)代理優(yōu)化算法的收斂性。本文用條件模擬方法分析近似PF的不確定性，并將此不確定性作為算法收斂性的評價(jià)依據(jù)。用SMOA算法求解算例1，并用條件模擬方法度量近似PF的不確定性，結(jié)果如圖3～圖5所示。圖5中圓點(diǎn)對應(yīng)真實(shí)的PF，菱形表示隨機(jī)集Vorob’ev期望的PF，上三角形表示SMOA算法在優(yōu)化過程中添加的可行試驗(yàn)數(shù)據(jù)(它們的連線對應(yīng)于求得的近似PF)；陰影區(qū)域則反映了CPFs的不確定性(y屬于對稱差Qβ*ΔY的概率)。

由圖3可知：在可行域探索階段選取的前10個(gè)試驗(yàn)點(diǎn)中，有4個(gè)是可行的且它們成功地找到了算例1的全部3個(gè)可行子區(qū)域；但此時(shí)CPFs的不確定程度高(圖中陰影區(qū)域大)、SMOA算法求得的近似PF與隨機(jī)集Vorob’ev期望的PF相差大，算法未收斂。用加點(diǎn)準(zhǔn)則Cfea(x)繼續(xù)選取10個(gè)新試驗(yàn)點(diǎn)(如圖4)，此時(shí)CPFs的不確定性已較小(圖中陰影區(qū)域較小)，Vorob’ev期望的PF接近于真實(shí)的PF，說明當(dāng)前試驗(yàn)數(shù)據(jù)包含了PF的較多信息；但SMOA算法求得的近似PF與Vorob’ev期望的PF差異仍然較大，算法尚未收斂。用SMOA算法繼續(xù)添加新試驗(yàn)點(diǎn)直到總試驗(yàn)次數(shù)T=80(如圖5)，這時(shí)圖中的陰影區(qū)域已經(jīng)非常小，且真實(shí)的PF、Vorob’ev期望的PF、近似PF三者幾乎重合，SMOA算法收斂。

表征近似PF不確定性的Vorob’ev期望和方差的超體積(分別記為VE和VD)，也可由條件模擬方法(算法2)得到。受變異系數(shù)概念的啟發(fā)，在此用VD/VE作為定量分析近似PF不確定性的指標(biāo)，并與RHV、Epsilon、R2等作比較，結(jié)果如圖6所示?？芍孩賄D/VE與RHV、Epsilon、R2等解集質(zhì)量指標(biāo)的總體變化趨勢一致，表明近似PF的不確定性確實(shí)反映了代理優(yōu)化算法的收斂性；②VD/VE指標(biāo)的靈敏度略有不足：VE和VD數(shù)據(jù)的獲取涉及隨機(jī)抽樣(用以生成CPFs)，由此產(chǎn)生的隨機(jī)誤差導(dǎo)致VD/VE指標(biāo)在優(yōu)化進(jìn)程的后期不能迅速趨于零；③用條件模擬方法間接分析代理優(yōu)化算法的收斂性，即便真實(shí)PF未知，也能從定性、定量兩方面評估優(yōu)化進(jìn)程，是一種新穎、可行的算法收斂性評估方法。

4 結(jié)束語

針對包含黑箱約束的多目標(biāo)優(yōu)化設(shè)計(jì)問題，本文提出一種有效辨識可行域和提高優(yōu)化效率的SMOA算法。該算法的可行域探索準(zhǔn)則包含了考慮試驗(yàn)點(diǎn)之間距離的項(xiàng)，辨識可行域的能力強(qiáng)；近似PF改進(jìn)準(zhǔn)則從具有Pareto最優(yōu)性的點(diǎn)集中選取新試驗(yàn)點(diǎn)，選點(diǎn)目的性強(qiáng)且兼具刻畫可行域邊界，保證了算法的優(yōu)化效率和精度；此外，用隨機(jī)模擬方法間接評估算法的收斂性，避免了真實(shí)PF未知情況下解集質(zhì)量指標(biāo)難以評估算法收斂性的問題。最后，通過與KEMOCO及U-NSGA-Ⅲ算法作比較，驗(yàn)證了SMOA算法的有效性和高效性。由于條件模擬涉及大量模擬點(diǎn)的選取與比較，其計(jì)算量較大。如何進(jìn)一步提高算法收斂性評估中條件模擬的效率以使其適用于高維問題，以及如何在算法的優(yōu)化迭代中同時(shí)選取多個(gè)新試驗(yàn)點(diǎn)以充分利用仿真模型的并行計(jì)算能力，是需要進(jìn)一步研究的問題。