改進NSGA-Ⅱ算法在水庫流量控制系統中的應用

朱壯華

(1.太原理工大學 財經學院, 太原 030024;2.山西省財政稅務?？茖W校, 太原 030024)

0 引言

多目標優化問題(multi-objective optimization problems,MOPs)廣泛存在于各種工程應用領域, 如電力物資配送[1]、平行束CT系統參數優化[2]、汽車電子電氣架構優化[3]、航空有源AC/DC變換器優化[4]和汽車外形空氣動力學優化[5]等。為有效解決多目標優化問題,學者提出了各種有效解決方法,如NSGA-Ⅱ[6]、MOPSO[7]以及SPEA2[8]等。然而,隨著實際工程應用問題變得越來越復雜,已有方法并不能適用于所有多目標優化問題。因此,許多學者研究進一步改善現有算法性能。

在理論研究方面,針對NSGA-Ⅱ多樣性不足問題,白雪等[9]將精英保留策略和小生境策略引入遺傳算子選擇,并設計新的適應度選擇策略。針對NSGA-Ⅱ的Pareto解局部最優性較差問題,宋健[10]提出迭代式局部搜索算法以使得解更快收斂到Pareto真實前沿面。針對NSGA-Ⅱ全局收斂性差問題,張翔宇等[11]提出利用隨機Halton序列和自適應調整策略改善初始種群多樣性和算法收斂性。針對MOCell在收斂性和多樣性方面的不足,萬興余[12]提出了三維種群拓撲結構,使得種群搜索方向由二維種群結構時的4個增加到了6個。為增強NSGA-Ⅱ的局部搜索能力,姚從潮等[13]將模擬退火算法引入交叉算子。針對NSGA-Ⅱ產生解不均勻的問題,陳銀美等[14]提出一種新的交叉限制機制,使得算法以較大概率得到更加均勻分布的Pareto最優解集。

在應用研究方面,為彌補線性系統MGM模型在非線性動力學系統變形預測分析中的不足,馬龍等[15]建立多目標優化實數編碼遺傳算法,實現背景值最優構造權陣的迭代搜索。為解決混合流水車間調度問題,張志鵬等[16]提出了一種擴展的基于工序的編碼,將NSGA-Ⅱ和粒子群算法結合產生的最優解分別作為彼此的初始因子,有效增強了算法在車間調度問題上的收斂速度。針對NSGA-Ⅱ在求解車間調度問題時收斂速度慢和容易陷入局部最優化的不足,劉婷[17]提出了一種基于點交叉的多目標遺傳算法,即在算法運行初期采用多點交叉以提高收斂速度、在運算后期逐步減少交叉點,直至采用兩點交叉。

從上述分析可以看出,針對不同的應用問題,NSGA-Ⅱ等多目標優化算法仍然存在各種不足,需要進一步改進。因此,本文針對NSGA-Ⅱ中擁擠度距離策略容易選擇收斂性較差個體的不足,提出了改進的NSGA-Ⅱ算法,并將其進一步應用于水庫流量控制系統優化問題。

1 基本概念和NSGA-Ⅱ

1.1 基本概念

多目標優化問題[6]：典型多目標優化問題的數學表達式如下：

minF(X)=(f1(X),f2(X),…,fM(X))

s.t.X∈Ω

(1)

其中：F為目標向量;X為決策向量;M=2或者3,表示目標數量。

Pareto支配 解X1Pareto支配X2當且僅當滿足以下條件：解X1對應目標函數的每一維度均小于等于解X2的每一目標函數維度,且X1至少存在一個目標函數維度小于X2對應目標函數。

Pareto集合 決策空間所有Pareto最優解組成Pareto集合。

Pareto前沿 Pareto最優解集在目標空間對應的集合稱為Pareto前沿。

1.2 NSGA-Ⅱ基本原理以及缺陷分析

NSGA-Ⅱ最初為解決多目標優化問題而設計,其基本過程如算法1所示。首先,輸入種群規模,隨機初始化種群;判斷是否滿足結束條件,若滿足,則輸出種群,否則執行以下操作：對當前種群執行快速非支配排序策略,產生多個Pareto非支配前沿面;然后,計算每個個體擁擠度距離。根據個體所在Pareto前沿面和擁擠度距離采用錦標賽策略選擇較優個體并構建交叉池。對交叉池內個體執行交叉和變異操作,產生后代種群。將后代種群和父代種群合并,執行非支配排序和擁擠度距離,選擇出較優個體作為下一代種群。

算法1：NSGA-Ⅱ基本框架

輸入：種群規模

輸出：種群

1： 隨機初始化種群;

2： while (是否滿足結束條件) do

3：執行非支配排序策略

4：計算每個個體擁擠度

5：執行錦標賽策略構建交叉池

6：執行交叉和變異操作

7：執行環境更新

8： end

如上所述,NSGA-Ⅱ算法主要依據快速非支配排序和擁擠度距離計算個體優劣。擁擠度距離計算方式如下：

(2)

其中：d(Xi)表示個體X1的擁擠度距離;fm(Xi-1)表示前一個個體的第m個目標函數,邊界個體默認擁擠度距離為無窮大。

圖1展示了4個非支配個體,分別為A(1,7),B(2,3)、C(4,2)和D(9,1)。根據式(2),個體B的擁擠度距離為8,而個體C的擁擠度距離為9。顯然,在此情況下,個體C優于個體B。然而,若計算個體B和C對指標HV的貢獻,可以得到個體B對HV的貢獻為28,而個體C對HV的貢獻為25。很明顯可以看出,個體B對整體貢獻更為明顯,而采用擁擠度距離指標則不能有效地選擇合適的個體。

圖1 擁擠度距離分析結果

2 改進NSGA-Ⅱ算法

為彌補擁擠度距離指標的不足,提出改進的NSGA-Ⅱ,其基本框架見算法2。可以看到,改進NSGA-Ⅱ和原始NSGA-Ⅱ的區別之處在于第4—5行的個體評價指標。如算法2第4—5行所示,不同于采用擁擠度距離評價個體,本文中首先計算從最后一層非支配前沿所需選擇的個體數量k;然后采用k-means將最后一層非支配前沿分為k組;接著,計算每個分組內的個體收斂性,并選擇具有最小收斂性的個體進入交叉池。個體收斂性表達式為：

(3)

其中,fm(Xi)表示解Xi的第m個目標函數。

算法2：改進NSGA-Ⅱ基本框架

輸入：種群規模N

輸出：種群

1： 隨機初始化種群;

2： while (是否滿足結束條件) do

3：執行非支配排序策略

5：采用錦標賽策略構建交叉池

6：執行交叉和變異操作

7：執行非支配排序并計算最后一層前沿所需選擇個體數k

8：采用k-means策略將種群分為k個分組,并計算每個組內個體的收斂性

9： end

算法2第7—8行描述了環境更新方式,即對合并后的種群執行非支配排序策略,然后計算從最后一層非支配前沿所需個體數量。采用k-means對最后一層非支配前沿分組,并選擇每個組內具有最小收斂性的個體進入下一代種群。

進一步,利用式(3)分析圖1中個體B和C的收斂性?？梢钥闯?個體B的收斂值為5,而個體C收斂值為6,說明所提改進策略可以有效地提升算法整體性能,也初步說明了改進策略的有效性。

3 實驗分析

3.1 算法在測試函數上的性能分析

為驗證改進NSGA-Ⅱ的性能,采用兩目標的DTLZ1-DTLZ7[18]作為測試用例,其中DTLZ1決策變量維度為6,DTLZ7決策變量維度為21,其他測試用例變量維度為11。對比算法采用NSGA-Ⅱ、BiGE[19]、MOPSO和MOEA/D[20]。所有對比算法參數按照原開發者建議設置。例如,對于MOEA/D,NSGA-Ⅱ以及改進NSGA-Ⅱ,交叉概率設置為1,變異概率為決策變量長度的倒數。對于MOPSO,每個目標維度上分割數設置為10。此外,采用HV[21]和IGD[22]作為算法評價指標,這2個指標均為綜合指標,可以有效衡量算法的收斂性和多樣性。計算指標IGD時采樣點數量設置為8 000,HV計算時參考點設置為(1,1,…,1)。為公平比較,每個算法運行15次,算法計算結果均值如表1和表2所示,其中括號內為相應指標方差,最優結果加粗表示。

表1 算法在DTLZ測試問題上的HV值

表2 算法在DTLZ測試問題上IGD值

如表1所示,本文所提算法在DTLZ2和DTLZ4-DTLZ7問題上表現最好,僅在DTLZ1問題上表現不及MOEA/D,在DTLZ3上表現不及NSGA-Ⅱ。此外,所提算法在DTLZ1測試問題上性能仍然超過算法BiGE和MOPSO。進一步,從表2對比可以看出,所提算法仍在DTLZ2和DTLZ4-DTLZ7上表現最優,僅在DTLZ1上表現不及MOEA/D,在DTLZ3上表現不及NSGA-Ⅱ。綜合實驗結果可看出,所提算法有效改善了標準NSGA-Ⅱ的整體性能,表明了所提策略的有效性。

圖2所示為算法在DTLZ7測試函數上所求Pareto前沿面,為方便對比,DTLZ7真實Pareto前沿面也包含在內。可以看出,改進NSGA-Ⅱ可以完美地接近真實Pareto前沿面,而原始NSGA-Ⅱ所求前沿則未能收斂到真實Pareto前沿。此外,BiGE所求前沿面雖然收斂到真實Pareto前沿,但其均勻性仍然不及改進的NSGA-Ⅱ。MOPSO所求前沿面距離真實Pareto前沿具有較大距離,說明其收斂性最差。MOEA/D雖然在DTLZ7函數Pareto前沿左上部分收斂到最優,但在右下部分表現較差。從以上Pareto前沿面對比可以看出,改進NSGA-Ⅱ綜合性能仍然為最優。

3.2 算法在水庫流量控制系統優化上的分析

進一步將改進NSGA-Ⅱ算法應用于水庫流量控制系統優化問題[23]。水庫流量控制系統管理對于現代工業和農業的發展具有重要意義?？茖W高效地運行水庫管理系統具有挑戰性。

一般水庫流量控制系統模型具有非線性和離散性等特點,其數學模型可表述為：

(4)

表3列出了算法在水庫流量控制系統中所求HV指標均值?？梢钥闯?本文所提算法的結果為最優。圖3所示為算法所求問題Pareto前沿面?？梢钥闯?同NSGA-Ⅱ和BiGE所求結果相比,改進NSGA-Ⅱ算法的結果分布更加均勻,而MOPSO所求個體分布性最差,MOEA/D所求前沿面雖然與改進NSGA-Ⅱ前沿面相似,但整體性能仍然不及NSGA-Ⅱ。從算法在實際水庫優化問題上的表現可以看出,改進NSGA-Ⅱ算法在理論和實際應用方面均展現出較優性能。

表3 算法在水庫流量控制系統問題中的HV指標均值

圖3 算法在水庫問題中所求Pareto前沿面

4 結論

分析了在NSGA-Ⅱ算法中采用擁擠度距離策略解決個體選擇問題的不足,提出利用目標函數和衡量個體收斂性改進NSGA-Ⅱ算法。采用DTLZ測試函數對改進算法進行系統測試。實驗結果表明,改進NSGA-Ⅱ算法能有效地解決多目標優化問題。此外,進一步將改進NSGA-Ⅱ算法應用于水庫流量控制系統優化問題。仿真結果表明,改進NSGA-Ⅱ算法可以有效解決此類實際優化問題。然而,從實驗結果分析可以看出,改進NSGA-Ⅱ算法僅在本文多目標優化問題中表現出優勢,在更多實際工程優化以及高維多目標優化問題中仍需進一步檢驗其性能,這也是下一步的研究內容。