基于深度卷積神經網絡的復雜多目標規劃問題機器學習方法

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

長江大學信息與數學學院，湖北 荊州 434023

多目標規劃問題是指同時優化多個相互沖突目標的優化問題，由于其可以全面體現決策者的意愿，從而廣泛應用于工程實踐中，如跨流域調水問題[1]、土地資源使用問題[2]、工程設計問題[3]、綠色煤炭生產問題[4]等。但由于多目標問題的復雜性，其有效的算法設計一直是優化領域的研究熱點。

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

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

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

1 模型與基本概念

假設x∈Rn，f：Rn→Rm，g：Rn→Rq，以最小化問題為例，多目標規劃問題的數學模型可表述為：

(1)

多目標規劃問題的概念圖如圖1，相關定義如下：

圖1 多目標規劃概念圖

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

定義2(Pareto最優解)對可行解x*，若不存在x∈S，使得xx*，則x*為問題(1)的一個Pareto最優解。

定義3(Pareto最優解集)給定問題的所有Pareto最優解構成Pareto最優解集(Pareto-optimal set，PS)，記作：

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

定義4(Pareto前沿)對于給定問題的所有Pareto最優解所對應的目標向量構成問題(1)的Pareto前沿(Pareto Front，PF)，記作：

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

s.t.x∈Ω

2 算法

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

2.1 算法總體流程

算法流程如下所述：

Step 1 在決策空間中隨機初始化一組解X，設置循環次數N；

Step 2 將X帶入問題模型得到Y；

Step 3 利用深度卷積神經網絡從Y構成的圖像中提取Pareto最優前沿Z；

Step 4 得到Pareto前沿Z對應的決策變量集合S；

Step 5 由S根據智能采樣算法產生新的決策變量集合X；

Step 6 從Step 2開始循環N-1次。

2.2 智能采樣算法流程

智能采樣算法流程如下：

Step 1 得到當前最優解集S；

Step 2 以S中每個向量為中心，進行Gauss采樣得到集合P；

Step 3 生成一組隨機數組成集合R；

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

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

2.3 基于深度卷積神經網絡的Pareto前沿提取算法

基于深度卷積神經網絡的Pareto前沿提取算法流程如下：

步驟1 將目標空間圖像轉換成二值數字圖像；

步驟2 根據圖像大小，設置相應的卷積核，建立深度卷積神經網絡模型，其中卷積核設置如下：

網絡所需層數由卷積核大小和輸入圖像大小計算后設置；

步驟3 將數字圖像輸入神經網絡模型得到對應的Pareto前沿圖像；

步驟4 將Pareto前沿圖像轉換成對應的Pareto解集。

3 數值試驗與結果分析

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

3.1 測試模型

改進后的測試模型R-ZDT1～R-ZDT5分別如下：

R-ZDT1：

R-ZDT2：

R-ZDT3：

R-ZDT4：

R-ZDT5：

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

3.2 算法性能評價指標

算法的性能評價主要分為2個方面：一是衡量算法收斂性能的指標，刻畫利用算法所得最優解和理論Pareto最優前沿的逼近程度，如世代距離指標GD；二是衡量算法多樣性的指標，主要衡量解集在PF上分布的均勻程度，如空間指標SP。

世代距離指標GD計算公式如下：

(2)

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

空間指標SP計算公式如下：

(3)

3.3 試驗結果

改進測試模型R-ZDT1～R-ZDT5的求解結果分別如圖2～圖11所示。圖2、4、6、8、10中，各分圖的左圖展示問題的理論Pareto最優前沿與利用筆者算法求解得到的Pareto最優前沿，右圖展示理論Pareto最優解集與利用筆者算法求解得到的Pareto最優解集。

圖11 R-ZDT5的GD和SP指標箱線圖及變化曲線

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

圖2 R-ZDT1的Pareto最優前沿和Pareto最優解集

圖3 R-ZDT1的GD和SP指標箱線圖及變化曲線

圖4 R-ZDT2的Pareto最優前沿和Pareto最優解集

圖5 R-ZDT2的GD和SP指標箱線圖及變化曲線

圖6 R-ZDT3的Pareto最優前沿和Pareto最優解集

圖7 R-ZDT3的GD和SP指標箱線圖及變化曲線

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

圖8 R-ZDT4的Pareto最優前沿和Pareto最優解集

圖9 R-ZDT4的GD和SP指標箱線圖及變化曲線

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

圖10 R-ZDT5的Pareto最優前沿和Pareto最優解集

4 結語

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