基于深度卷積神經(jīng)網(wǎng)絡(luò)的復(fù)雜多目標(biāo)規(guī)劃問(wèn)題機(jī)器學(xué)習(xí)方法

張濤，陳薇，周俊，劉瑞林，陳芳

長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023

多目標(biāo)規(guī)劃問(wèn)題是指同時(shí)優(yōu)化多個(gè)相互沖突目標(biāo)的優(yōu)化問(wèn)題，由于其可以全面體現(xiàn)決策者的意愿，從而廣泛應(yīng)用于工程實(shí)踐中，如跨流域調(diào)水問(wèn)題[1]、土地資源使用問(wèn)題[2]、工程設(shè)計(jì)問(wèn)題[3]、綠色煤炭生產(chǎn)問(wèn)題[4]等。但由于多目標(biāo)問(wèn)題的復(fù)雜性，其有效的算法設(shè)計(jì)一直是優(yōu)化領(lǐng)域的研究熱點(diǎn)。

智能算法的發(fā)展促進(jìn)了最優(yōu)化方法從“方法定向”到“問(wèn)題定向”的轉(zhuǎn)變。相對(duì)于傳統(tǒng)算法，智能優(yōu)化算法具有以下優(yōu)點(diǎn)：對(duì)目標(biāo)函數(shù)和約束函數(shù)的性能要求更為寬松；計(jì)算效率比理論上的最優(yōu)性更為重要；多數(shù)算法有一個(gè)多個(gè)體的種群，尋優(yōu)過(guò)程實(shí)際上就是一個(gè)種群進(jìn)化的過(guò)程。結(jié)合多目標(biāo)規(guī)劃問(wèn)題的結(jié)構(gòu)特征，智能算法已成為求解多目標(biāo)規(guī)劃問(wèn)題的重要手段。SCHAFFER設(shè)計(jì)了求解多目標(biāo)規(guī)劃問(wèn)題的向量評(píng)價(jià)遺傳算法(VEGA)[5]；FONSECA和FLEMING提出了求解多目標(biāo)規(guī)劃問(wèn)題的遺傳算法MOGA[6]，該算法易于操作且計(jì)算效率較高，但該算法過(guò)于依賴(lài)共享參數(shù)，極易陷入局優(yōu)；SRINIVAS和DEB提出了求解多目標(biāo)規(guī)劃問(wèn)題的非受控排序遺傳算法(NSGA)，該算法具有較好的收斂性且Pareto最優(yōu)解分布均勻，但算法計(jì)算量大，計(jì)算復(fù)雜度高[7]；HORN等提出了基于小生境技術(shù)的多目標(biāo)規(guī)劃問(wèn)題的遺傳算法(NPGA)，該算法計(jì)算效率較高且能獲得較好的Pareto最優(yōu)解集，但難以選擇和調(diào)整小生境半徑和比較集的規(guī)模[8]；KNOWLES等提出了基于外部存檔的多目標(biāo)進(jìn)化算法(PAES)，該算法利用外部存檔技術(shù)保留非支配個(gè)體，并采用一種自適應(yīng)的網(wǎng)格保持種群的多樣性[9]；CORNE等利用擠壓系數(shù)保持種群的多樣性，提出了Paeto包絡(luò)的多目標(biāo)優(yōu)化選擇算法(PESA)[10]；后續(xù)又對(duì)PESA 算法進(jìn)行改進(jìn)，提出了求解多目標(biāo)規(guī)劃問(wèn)題的PESA-Ⅱ算法，該算法采用網(wǎng)格選擇，與基于個(gè)體選擇的PESA算法相比，在一定程度上提高了算法的運(yùn)行效率[11]；基于外部精英集存檔技術(shù)和保持種群多樣性的聚類(lèi)技術(shù)，結(jié)合基于個(gè)體強(qiáng)度的適應(yīng)度賦值方法，ZITZLER等提出了求解多目標(biāo)規(guī)劃問(wèn)題的強(qiáng)度Pareto進(jìn)化算法(SPEA)，該算法為多目標(biāo)進(jìn)化算法的設(shè)計(jì)提供了一種新的思想，但該算法在選擇壓力較小時(shí)，幾乎等效于隨機(jī)搜索[12]；他們后續(xù)又對(duì)SPEA算法的適應(yīng)度分配策略、個(gè)體分布性評(píng)估方法以及非支配解集的更新策略進(jìn)行了改進(jìn)，提出了第二代求解多目標(biāo)規(guī)劃問(wèn)題的強(qiáng)度Pareto進(jìn)化算法(NSGA-Ⅱ)，該算法雖然與SPEA算法的計(jì)算復(fù)雜度相同，但SPEA-Ⅱ的Pareto最優(yōu)解的分布均勻性得到了極大的提高[13]；基于快速非受控技術(shù)，DEB等提出了求解多目標(biāo)規(guī)劃問(wèn)題的快速非受控排序遺傳算法(NSGA-Ⅱ)，該算法具有良好的收斂性與Pareto最優(yōu)解具有較好的分布均勻性且計(jì)算效率較高，但難以找到孤立點(diǎn)[14]。

自2003年開(kāi)始，由于粒子群優(yōu)化算法以及人工免疫系統(tǒng)優(yōu)化算法等新的進(jìn)化思想被引入多目標(biāo)優(yōu)化的領(lǐng)域，多目標(biāo)進(jìn)化算法的研究又得到了進(jìn)一步的發(fā)展。2004年，COELLO等提出了多目標(biāo)規(guī)劃問(wèn)題的粒子群算法(MOPSO)，該方法簡(jiǎn)單易行且具有較高的計(jì)算效率[15]；2008年，基于人工免疫系統(tǒng)模擬抗體的優(yōu)化過(guò)程，JIAO等提出了經(jīng)典的求解多目標(biāo)規(guī)劃問(wèn)題的非支配鄰域免疫算法(NNIA)，該算法收斂速度較快，在求解高維多目標(biāo)優(yōu)化問(wèn)題時(shí)具有一定的優(yōu)勢(shì)[16]。

近年來(lái)，國(guó)內(nèi)外學(xué)者以多目標(biāo)進(jìn)化算法為主要手段，設(shè)計(jì)了一系列的多目標(biāo)規(guī)劃問(wèn)題求解算法，并取得了一定的成果。然而，多目標(biāo)規(guī)劃問(wèn)題進(jìn)化算法中仍存在一些共性問(wèn)題：測(cè)試函數(shù)的Pareto最優(yōu)解集模式單一；種群多樣性與算法收斂速度相互牽制，且隨著問(wèn)題維度的增加，求解難度急劇上升。最近，深度卷積神經(jīng)網(wǎng)絡(luò)因在圖像邊緣提取中的高效性備受矚目，該方法幾乎可以“瞬時(shí)”完成圖像邊緣提取。事實(shí)上，將多目標(biāo)規(guī)劃問(wèn)題的像空間進(jìn)行圖像表征，則Pareto最優(yōu)前沿通常映射為圖像邊緣的特定部分?；诖?，筆者設(shè)計(jì)了一種基于深度卷積神經(jīng)網(wǎng)絡(luò)的復(fù)雜多目標(biāo)規(guī)劃問(wèn)題的機(jī)器學(xué)習(xí)方法。

1 模型與基本概念

假設(shè)x∈Rn，f：Rn→Rm，g：Rn→Rq，以最小化問(wèn)題為例，多目標(biāo)規(guī)劃問(wèn)題的數(shù)學(xué)模型可表述為：

(1)

多目標(biāo)規(guī)劃問(wèn)題的概念圖如圖1，相關(guān)定義如下：

圖1 多目標(biāo)規(guī)劃概念圖

定義1(Pareto支配)對(duì)任意2個(gè)可行解x和y，若對(duì)?i∈{1,2,…,m}滿(mǎn)足fi(x)≤fi(y)，且?i∈{1,2,…,m}，使fi(x)

定義2(Pareto最優(yōu)解)對(duì)可行解x*，若不存在x∈S，使得xx*，則x*為問(wèn)題(1)的一個(gè)Pareto最優(yōu)解。

定義3(Pareto最優(yōu)解集)給定問(wèn)題的所有Pareto最優(yōu)解構(gòu)成Pareto最優(yōu)解集(Pareto-optimal set，PS)，記作：

P*={x*∈S|?x∈S,x*x}

定義4(Pareto前沿)對(duì)于給定問(wèn)題的所有Pareto最優(yōu)解所對(duì)應(yīng)的目標(biāo)向量構(gòu)成問(wèn)題(1)的Pareto前沿(Pareto Front，PF)，記作：

PF*={f(x)=(f1(x),f2(x),…,fm(x))|x∈P}

s.t.x∈Ω

2 算法

首先，在原像空間中，提出“部分精英集的Gauss采樣+部分拉丁超立方采樣”的混合采樣新方法，其中部分樣本以精英集中的Pareto最優(yōu)解為中心進(jìn)行Gauss采樣以保證所獲Pareto前沿不差于上一代，部分樣本利用拉丁超立方采樣以保證樣本的多樣性。接著，在像空間中，利用基于深度卷積神經(jīng)網(wǎng)絡(luò)圖像特定邊緣提取直接獲取Pareto最優(yōu)前沿。反復(fù)迭代上述過(guò)程，直到滿(mǎn)足精度要求。

2.1 算法總體流程

算法流程如下所述：

Step 1 在決策空間中隨機(jī)初始化一組解X，設(shè)置循環(huán)次數(shù)N；

Step 2 將X帶入問(wèn)題模型得到Y(jié)；

Step 3 利用深度卷積神經(jīng)網(wǎng)絡(luò)從Y構(gòu)成的圖像中提取Pareto最優(yōu)前沿Z；

Step 4 得到Pareto前沿Z對(duì)應(yīng)的決策變量集合S；

Step 5 由S根據(jù)智能采樣算法產(chǎn)生新的決策變量集合X；

Step 6 從Step 2開(kāi)始循環(huán)N-1次。

2.2 智能采樣算法流程

智能采樣算法流程如下：

Step 1 得到當(dāng)前最優(yōu)解集S；

Step 2 以S中每個(gè)向量為中心，進(jìn)行Gauss采樣得到集合P；

Step 3 生成一組隨機(jī)數(shù)組成集合R；

Step 4 將S、P和R合并后進(jìn)行拉丁超立方采樣，得到集合Q；

Step 5 將S、P和Q合并，得到新的樣本集合X。

2.3 基于深度卷積神經(jīng)網(wǎng)絡(luò)的Pareto前沿提取算法

基于深度卷積神經(jīng)網(wǎng)絡(luò)的Pareto前沿提取算法流程如下：

步驟1 將目標(biāo)空間圖像轉(zhuǎn)換成二值數(shù)字圖像；

步驟2 根據(jù)圖像大小，設(shè)置相應(yīng)的卷積核，建立深度卷積神經(jīng)網(wǎng)絡(luò)模型，其中卷積核設(shè)置如下：

網(wǎng)絡(luò)所需層數(shù)由卷積核大小和輸入圖像大小計(jì)算后設(shè)置；

步驟3 將數(shù)字圖像輸入神經(jīng)網(wǎng)絡(luò)模型得到對(duì)應(yīng)的Pareto前沿圖像；

步驟4 將Pareto前沿圖像轉(zhuǎn)換成對(duì)應(yīng)的Pareto解集。

3 數(shù)值試驗(yàn)與結(jié)果分析

為了測(cè)試算法求解復(fù)雜多目標(biāo)規(guī)劃問(wèn)題的效率和普適性，基于文獻(xiàn)[14]，將5個(gè)經(jīng)典多目標(biāo)規(guī)劃問(wèn)題進(jìn)行了如下改進(jìn)：①重新構(gòu)造測(cè)試模型，測(cè)試模型的最優(yōu)Pareto解集具有隨機(jī)性；②增加測(cè)試模型維度。改進(jìn)后的測(cè)試模型稱(chēng)為R-ZDT。所有試驗(yàn)均在Dell Precision 7530移動(dòng)工作站上運(yùn)行，工作站主要配置如下：Nvidia Quadro P3200M(6GB RAM，1792 CUDA core)的GPU、Intel i7-8750H CPU以及16GB RAM。

3.1 測(cè)試模型

改進(jìn)后的測(cè)試模型R-ZDT1～R-ZDT5分別如下：

R-ZDT1：

R-ZDT2：

R-ZDT3：

R-ZDT4：

R-ZDT5：

其中：xi∈[0,1]；εi～U([0,1])。

3.2 算法性能評(píng)價(jià)指標(biāo)

算法的性能評(píng)價(jià)主要分為2個(gè)方面：一是衡量算法收斂性能的指標(biāo)，刻畫(huà)利用算法所得最優(yōu)解和理論P(yáng)areto最優(yōu)前沿的逼近程度，如世代距離指標(biāo)GD；二是衡量算法多樣性的指標(biāo)，主要衡量解集在PF上分布的均勻程度，如空間指標(biāo)SP。

世代距離指標(biāo)GD計(jì)算公式如下：

(2)

式中：np=|P|；m為目標(biāo)個(gè)數(shù)；di表示為P中第i個(gè)解到P*上離其最近的解的歐式距離。GD的值越小，算法的收斂性能越好。一般地，P*由問(wèn)題的真實(shí)PF上均勻采樣的點(diǎn)集構(gòu)成。

空間指標(biāo)SP計(jì)算公式如下：

(3)

3.3 試驗(yàn)結(jié)果

改進(jìn)測(cè)試模型R-ZDT1～R-ZDT5的求解結(jié)果分別如圖2～圖11所示。圖2、4、6、8、10中，各分圖的左圖展示問(wèn)題的理論P(yáng)areto最優(yōu)前沿與利用筆者算法求解得到的Pareto最優(yōu)前沿，右圖展示理論P(yáng)areto最優(yōu)解集與利用筆者算法求解得到的Pareto最優(yōu)解集。

圖11 R-ZDT5的GD和SP指標(biāo)箱線(xiàn)圖及變化曲線(xiàn)

值得注意的是，所有測(cè)試函數(shù)的最優(yōu)前沿均與模型中的f2(x)函數(shù)密切相關(guān)。其中，測(cè)試函數(shù)R-ZDT1～R-ZDT3中的f2(x)函數(shù)為單調(diào)函數(shù)，測(cè)試函數(shù)R-ZDT4和R-ZDT5中的f2(x)函數(shù)具有多模態(tài)性。對(duì)于測(cè)試模型R-ZDT1～R-ZDT3，從圖2、圖4以及圖6可以看出，利用筆者算法所獲得最優(yōu)Pareto前沿面能很好地收斂到理論最優(yōu)Pareto前沿面且分布均勻；從圖3、圖5以及圖7可以看出，算法在保證收斂的前提下具有較快的收斂速度。

圖2 R-ZDT1的Pareto最優(yōu)前沿和Pareto最優(yōu)解集

圖3 R-ZDT1的GD和SP指標(biāo)箱線(xiàn)圖及變化曲線(xiàn)

圖4 R-ZDT2的Pareto最優(yōu)前沿和Pareto最優(yōu)解集

圖5 R-ZDT2的GD和SP指標(biāo)箱線(xiàn)圖及變化曲線(xiàn)

圖6 R-ZDT3的Pareto最優(yōu)前沿和Pareto最優(yōu)解集

圖7 R-ZDT3的GD和SP指標(biāo)箱線(xiàn)圖及變化曲線(xiàn)

對(duì)于測(cè)試函數(shù)R-ZDT4，由于f2(x)函數(shù)的多模態(tài)性，導(dǎo)致原問(wèn)題具有多個(gè)局部Pareto最優(yōu)前沿，算法極易陷入局優(yōu)。從圖8可以看出，當(dāng)決策變量維數(shù)小于70時(shí)，利用筆者算法所獲得最優(yōu)Pareto前沿面能很好地收斂到理論最優(yōu)Pareto前沿面且分布均勻；從圖9可以看出，該算法具有較快的收斂速度。

圖8 R-ZDT4的Pareto最優(yōu)前沿和Pareto最優(yōu)解集

圖9 R-ZDT4的GD和SP指標(biāo)箱線(xiàn)圖及變化曲線(xiàn)

對(duì)于測(cè)試函數(shù)R-ZDT5，從圖10和圖11可以看出，算法雖然具有較快的收斂速度但全局收斂性較欠缺。

圖10 R-ZDT5的Pareto最優(yōu)前沿和Pareto最優(yōu)解集

4 結(jié)語(yǔ)

針對(duì)多目標(biāo)規(guī)劃進(jìn)化算法中測(cè)試函數(shù)的Pareto最優(yōu)解集模式單一、種群多樣性與算法收斂速度相互牽制的問(wèn)題，提出了一種基于智能采樣和特定邊緣提取的多目標(biāo)規(guī)劃問(wèn)題算法。其中，智能采樣中的高斯采樣用于局部搜索，超立方拉丁采樣用于全局搜索，利用卷積神經(jīng)網(wǎng)絡(luò)特定邊緣提取實(shí)現(xiàn)最優(yōu)Pareto最優(yōu)前沿的“瞬間”提取。最后，對(duì)5個(gè)復(fù)雜多目標(biāo)規(guī)劃問(wèn)題進(jìn)行仿真試驗(yàn)，結(jié)果表明，該算法對(duì)求解復(fù)雜多目標(biāo)規(guī)劃問(wèn)題的具有可行性且具有較高的計(jì)算效率。未來(lái)，還需要深入挖掘該算法的采樣機(jī)理，對(duì)算法進(jìn)行改進(jìn)，并從理論上明確該算法的最佳應(yīng)用范圍；對(duì)于具體的邊緣提取，根據(jù)其原理，進(jìn)一步簡(jiǎn)化網(wǎng)絡(luò)架構(gòu)。