利用NSGA-II算法求解多元多目标函數優化問題

一、問題描述

利用進化多目标優化算法NSGA-II求解多目标函數優化問題，選擇三個多目标優化問題（包括函數表達式、決策變量取值範圍）進行求解。本文選取兩目标優化ZDT問題集中的三個問題，ZDT問題集均基于以下f1和f2的優化，其表達式如下，其中g(x)一般是收斂的。

min ⁡ f 1 ( x ) \min f _ { 1 } ( x ) minf1​(x)

min ⁡ f 2 ( x ) = g ( x ) h ( f 1 ( x ) , g ( x ) ) \min f _ { 2 } ( x ) = g ( x ) h \left( f _ { 1 } ( x ) , g ( x ) \right) minf2​(x)=g(x)h(f1​(x),g(x))

選取的三個函數分别為：

ZDT1： f 1 ( x ) = x 1 g ( x ) = 1 + 9 n − 1 ∑ i = 2 n x i h ( f 1 , g ) = 1 − f 1 / g 0 ≤ x i ≤ 1 i = 1 , … , n \begin{aligned} f _ { 1 } ( x ) & = x _ { 1 } \\ g ( x ) & = 1 + \frac { 9 } { n - 1 } \sum _ { i = 2 } ^ { n } x _ { i } \\ h \left( f _ { 1 } , g \right) & = 1 - \sqrt { f _ { 1 } / g } \\ 0 \leq x _ { i } & \leq 1 \quad i = 1 , \ldots , n \end{aligned} f1​(x)g(x)h(f1​,g)0≤xi​​=x1​=1+n−19​i=2∑n​xi​=1−f1​/g

​≤1i=1,…,n​

ZDT2： f 1 ( x ) = x 1 g ( x ) = 1 + 9 n − 1 ∑ i = 2 n x i h ( f 1 , g ) = 1 − ( f 1 / g ) 2 0 ≤ x i ≤ 1 i = 1 , … , n \begin{aligned} f _ { 1 } ( x ) & = x _ { 1 } \\ g ( x ) & = 1 + \frac { 9 } { n - 1 } \sum _ { i = 2 } ^ { n } x _ { i } \\ h \left( f _ { 1 } , g \right) & = 1 - \left( f _ { 1 } / g \right) ^ { 2 } \\ 0 \leq x _ { i } & \leq 1 \quad i = 1 , \ldots , n \end{aligned} f1​(x)g(x)h(f1​,g)0≤xi​​=x1​=1+n−19​i=2∑n​xi​=1−(f1​/g)2≤1i=1,…,n​

ZDT4： f 1 ( x ) = x 1 g ( x ) = 1 + 10 ( n − 1 ) + ∑ i = 2 n ( x i 2 − 10 cos ⁡ ( 4 π x i ) ) h ( f 1 , g ) = 1 − f 1 / g 0 ≤ x 1 ≤ 1 − 10 ≤ x i ≤ 10 i = 2 , … , n \begin{array} { r l } { f _ { 1 } ( x ) = } & { x _ { 1 } } \\ { g ( x ) = } & { 1 + 10 ( n - 1 ) + \sum _ { i = 2 } ^ { n } \left( x _ { i } ^ { 2 } - 10 \cos \left( 4 \pi x _ { i } \right) \right) } \\ { h \left( f _ { 1 } , g \right) = 1 - \sqrt { f _ { 1 } / g } } & { } \\ { } & { 0 \leq x _ { 1 } \leq 1 } \\ { - 10 \leq x _ { i } \leq 10 } & { i = 2 , \ldots , n } \end{array} f1​(x)=g(x)=h(f1​,g)=1−f1​/g

​−10≤xi​≤10​x1​1+10(n−1)+∑i=2n​(xi2​−10cos(4πxi​))0≤x1​≤1i=2,…,n​

二、解決思路和方案

NSGA-II算法适合應用于複雜的、多目标優化問題，其解決了NSGA的主要缺陷，實作快速、準确的搜尋性能。NSGA的非支配排序的時間複雜度很大，在種群規模較大時排序的速度會很慢，而NSGA-II使用帶精英政策的快速非支配排序，減小了時間複雜度，排序速度有大幅的提升。同時，精英政策保證找到的最優解不會被抛棄，提高了搜尋性能。另一方面NSGA使用共享函數來使解分布均勻，共享函數方法在保持多樣性的性能很大程度上依賴于所選擇的共享參數；種群中的每個個體都要與其餘的個體相比較，共享函數的複雜度很高，NSGA-II重新定義了擁擠距離來代替共享參數。NSGA-II算法步驟如下：

（1）首先，采用實數編碼方法随機産生規模為50的初始種群pop，利用二進制錦标賽方法（對pop中個體進行快速非支配排序和擁擠距離比較）産生父代種群P。

快速非支配排序結果的排序值越小，說明被被其餘個體支配的次數越小，有着越大的機率被選擇。擁擠距離的計算方法為該個體與相鄰的兩個個體組成的矩形的長寬和。在排序值相同的情況下，保留擁擠距離更大的個體。

（2）通過交叉、變異操作得到子代種群Q，将父代種群P與子代種群Q合并為R。

交叉采用模拟二進制交叉方法（SBX）,交叉分布指數設定為1。變異采用單點變異，變異算子設定為0.1。

（3）利用精英政策産生下一代種群，即對R中個體進行快速非支配排序，同時對每個非支配層中的個體進行擁擠度計算，根據非支配關系以及個體的擁擠度選取合适的個體組成下一代種群。設定疊代次數為500。

本文使用python語言進行仿真實作，求解每個最優化函數的最優前端，将其可視化。

三、仿真結果及分析

（1）ZDT1 仿真結果

ZDT1經過500次疊代，最優前端由藍點繪制而成，綠色的為理論參考集，可以看到求解結果和理論值基本吻合，且前端的分布比較均勻。其他函數同，其他函數便不進行解釋，隻進行結果展示。

圖3.1 ZDT1最優前端

（2）ZDT2仿真結果

圖3.2 ZDT2最優前端

（3）ZDT4 仿真結果

圖3.3 ZDT4最優前端