改進(jìn)NSGA-Ⅱ算法在水庫(kù)流量控制系統(tǒng)中的應(yīng)用

朱壯華

(1.太原理工大學(xué) 財(cái)經(jīng)學(xué)院, 太原 030024;2.山西省財(cái)政稅務(wù)?？茖W(xué)校, 太原 030024)

0 引言

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

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

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

從上述分析可以看出,針對(duì)不同的應(yīng)用問(wèn)題,NSGA-Ⅱ等多目標(biāo)優(yōu)化算法仍然存在各種不足,需要進(jìn)一步改進(jìn)。因此,本文針對(duì)NSGA-Ⅱ中擁擠度距離策略容易選擇收斂性較差個(gè)體的不足,提出了改進(jìn)的NSGA-Ⅱ算法,并將其進(jìn)一步應(yīng)用于水庫(kù)流量控制系統(tǒng)優(yōu)化問(wèn)題。

1 基本概念和NSGA-Ⅱ

1.1 基本概念

多目標(biāo)優(yōu)化問(wèn)題[6]：典型多目標(biāo)優(yōu)化問(wèn)題的數(shù)學(xué)表達(dá)式如下：

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

s.t.X∈Ω

(1)

其中：F為目標(biāo)向量;X為決策向量;M=2或者3,表示目標(biāo)數(shù)量。

Pareto支配 解X1Pareto支配X2當(dāng)且僅當(dāng)滿足以下條件：解X1對(duì)應(yīng)目標(biāo)函數(shù)的每一維度均小于等于解X2的每一目標(biāo)函數(shù)維度,且X1至少存在一個(gè)目標(biāo)函數(shù)維度小于X2對(duì)應(yīng)目標(biāo)函數(shù)。

Pareto集合 決策空間所有Pareto最優(yōu)解組成Pareto集合。

Pareto前沿 Pareto最優(yōu)解集在目標(biāo)空間對(duì)應(yīng)的集合稱為Pareto前沿。

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

NSGA-Ⅱ最初為解決多目標(biāo)優(yōu)化問(wèn)題而設(shè)計(jì),其基本過(guò)程如算法1所示。首先,輸入種群規(guī)模,隨機(jī)初始化種群;判斷是否滿足結(jié)束條件,若滿足,則輸出種群,否則執(zhí)行以下操作：對(duì)當(dāng)前種群執(zhí)行快速非支配排序策略,產(chǎn)生多個(gè)Pareto非支配前沿面;然后,計(jì)算每個(gè)個(gè)體擁擠度距離。根據(jù)個(gè)體所在Pareto前沿面和擁擠度距離采用錦標(biāo)賽策略選擇較優(yōu)個(gè)體并構(gòu)建交叉池。對(duì)交叉池內(nèi)個(gè)體執(zhí)行交叉和變異操作,產(chǎn)生后代種群。將后代種群和父代種群合并,執(zhí)行非支配排序和擁擠度距離,選擇出較優(yōu)個(gè)體作為下一代種群。

算法1：NSGA-Ⅱ基本框架

輸入：種群規(guī)模

輸出：種群

1： 隨機(jī)初始化種群;

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

3：執(zhí)行非支配排序策略

4：計(jì)算每個(gè)個(gè)體擁擠度

5：執(zhí)行錦標(biāo)賽策略構(gòu)建交叉池

6：執(zhí)行交叉和變異操作

7：執(zhí)行環(huán)境更新

8： end

如上所述,NSGA-Ⅱ算法主要依據(jù)快速非支配排序和擁擠度距離計(jì)算個(gè)體優(yōu)劣。擁擠度距離計(jì)算方式如下：

(2)

其中：d(Xi)表示個(gè)體X1的擁擠度距離;fm(Xi-1)表示前一個(gè)個(gè)體的第m個(gè)目標(biāo)函數(shù),邊界個(gè)體默認(rèn)擁擠度距離為無(wú)窮大。

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

圖1 擁擠度距離分析結(jié)果

2 改進(jìn)NSGA-Ⅱ算法

為彌補(bǔ)擁擠度距離指標(biāo)的不足,提出改進(jìn)的NSGA-Ⅱ,其基本框架見(jiàn)算法2?？梢钥吹?改進(jìn)NSGA-Ⅱ和原始NSGA-Ⅱ的區(qū)別之處在于第4—5行的個(gè)體評(píng)價(jià)指標(biāo)。如算法2第4—5行所示,不同于采用擁擠度距離評(píng)價(jià)個(gè)體,本文中首先計(jì)算從最后一層非支配前沿所需選擇的個(gè)體數(shù)量k;然后采用k-means將最后一層非支配前沿分為k組;接著,計(jì)算每個(gè)分組內(nèi)的個(gè)體收斂性,并選擇具有最小收斂性的個(gè)體進(jìn)入交叉池。個(gè)體收斂性表達(dá)式為：

(3)

其中,fm(Xi)表示解Xi的第m個(gè)目標(biāo)函數(shù)。

算法2：改進(jìn)NSGA-Ⅱ基本框架

輸入：種群規(guī)模N

輸出：種群

1： 隨機(jī)初始化種群;

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

3：執(zhí)行非支配排序策略

5：采用錦標(biāo)賽策略構(gòu)建交叉池

6：執(zhí)行交叉和變異操作

7：執(zhí)行非支配排序并計(jì)算最后一層前沿所需選擇個(gè)體數(shù)k

8：采用k-means策略將種群分為k個(gè)分組,并計(jì)算每個(gè)組內(nèi)個(gè)體的收斂性

9： end

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

進(jìn)一步,利用式(3)分析圖1中個(gè)體B和C的收斂性。可以看出,個(gè)體B的收斂值為5,而個(gè)體C收斂值為6,說(shuō)明所提改進(jìn)策略可以有效地提升算法整體性能,也初步說(shuō)明了改進(jìn)策略的有效性。

3 實(shí)驗(yàn)分析

3.1 算法在測(cè)試函數(shù)上的性能分析

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

表1 算法在DTLZ測(cè)試問(wèn)題上的HV值

表2 算法在DTLZ測(cè)試問(wèn)題上IGD值

如表1所示,本文所提算法在DTLZ2和DTLZ4-DTLZ7問(wèn)題上表現(xiàn)最好,僅在DTLZ1問(wèn)題上表現(xiàn)不及MOEA/D,在DTLZ3上表現(xiàn)不及NSGA-Ⅱ。此外,所提算法在DTLZ1測(cè)試問(wèn)題上性能仍然超過(guò)算法BiGE和MOPSO。進(jìn)一步,從表2對(duì)比可以看出,所提算法仍在DTLZ2和DTLZ4-DTLZ7上表現(xiàn)最優(yōu),僅在DTLZ1上表現(xiàn)不及MOEA/D,在DTLZ3上表現(xiàn)不及NSGA-Ⅱ。綜合實(shí)驗(yàn)結(jié)果可看出,所提算法有效改善了標(biāo)準(zhǔn)NSGA-Ⅱ的整體性能,表明了所提策略的有效性。

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

3.2 算法在水庫(kù)流量控制系統(tǒng)優(yōu)化上的分析

進(jìn)一步將改進(jìn)NSGA-Ⅱ算法應(yīng)用于水庫(kù)流量控制系統(tǒng)優(yōu)化問(wèn)題[23]。水庫(kù)流量控制系統(tǒng)管理對(duì)于現(xiàn)代工業(yè)和農(nóng)業(yè)的發(fā)展具有重要意義?？茖W(xué)高效地運(yùn)行水庫(kù)管理系統(tǒng)具有挑戰(zhàn)性。

一般水庫(kù)流量控制系統(tǒng)模型具有非線性和離散性等特點(diǎn),其數(shù)學(xué)模型可表述為：

(4)

表3列出了算法在水庫(kù)流量控制系統(tǒng)中所求HV指標(biāo)均值?？梢钥闯?本文所提算法的結(jié)果為最優(yōu)。圖3所示為算法所求問(wèn)題Pareto前沿面?？梢钥闯?同NSGA-Ⅱ和BiGE所求結(jié)果相比,改進(jìn)NSGA-Ⅱ算法的結(jié)果分布更加均勻,而MOPSO所求個(gè)體分布性最差,MOEA/D所求前沿面雖然與改進(jìn)NSGA-Ⅱ前沿面相似,但整體性能仍然不及NSGA-Ⅱ。從算法在實(shí)際水庫(kù)優(yōu)化問(wèn)題上的表現(xiàn)可以看出,改進(jìn)NSGA-Ⅱ算法在理論和實(shí)際應(yīng)用方面均展現(xiàn)出較優(yōu)性能。

表3 算法在水庫(kù)流量控制系統(tǒng)問(wèn)題中的HV指標(biāo)均值

圖3 算法在水庫(kù)問(wèn)題中所求Pareto前沿面

4 結(jié)論

分析了在NSGA-Ⅱ算法中采用擁擠度距離策略解決個(gè)體選擇問(wèn)題的不足,提出利用目標(biāo)函數(shù)和衡量個(gè)體收斂性改進(jìn)NSGA-Ⅱ算法。采用DTLZ測(cè)試函數(shù)對(duì)改進(jìn)算法進(jìn)行系統(tǒng)測(cè)試。實(shí)驗(yàn)結(jié)果表明,改進(jìn)NSGA-Ⅱ算法能有效地解決多目標(biāo)優(yōu)化問(wèn)題。此外,進(jìn)一步將改進(jìn)NSGA-Ⅱ算法應(yīng)用于水庫(kù)流量控制系統(tǒng)優(yōu)化問(wèn)題。仿真結(jié)果表明,改進(jìn)NSGA-Ⅱ算法可以有效解決此類實(shí)際優(yōu)化問(wèn)題。然而,從實(shí)驗(yàn)結(jié)果分析可以看出,改進(jìn)NSGA-Ⅱ算法僅在本文多目標(biāo)優(yōu)化問(wèn)題中表現(xiàn)出優(yōu)勢(shì),在更多實(shí)際工程優(yōu)化以及高維多目標(biāo)優(yōu)化問(wèn)題中仍需進(jìn)一步檢驗(yàn)其性能,這也是下一步的研究?jī)?nèi)容。