基于徑向空間劃分的昂貴多目標(biāo)進(jìn)化算法

顧清華 周煜豐 李學(xué)現(xiàn) 阮順領(lǐng)

高維多目標(biāo)優(yōu)化問題在現(xiàn)實(shí)世界很常見,這類問題是具有3 個以上目標(biāo)的多目標(biāo)優(yōu)化問題.由于多個目標(biāo)之間往往是相互沖突的,通常不存在唯一的最優(yōu)解,而是由多個最優(yōu)解組成帕累托前沿面.進(jìn)化算法由于其群體的特性,能夠在1 次運(yùn)行中獲得1 組解,適用于多目標(biāo)優(yōu)化問題[1].但是,對于高維多目標(biāo)優(yōu)化問題,由于帕累托選擇壓力的喪失,大部分進(jìn)化算法都需要上萬次的函數(shù)評價(jià)才能獲得一些滿意的解.這使得傳統(tǒng)的多目標(biāo)進(jìn)化算法在實(shí)際應(yīng)用中遇到了巨大的挑戰(zhàn).許多現(xiàn)實(shí)問題單一的適應(yīng)度評估(Function evaluation,FE)在計(jì)算或經(jīng)濟(jì)上都需要昂貴的資源.以翼型結(jié)構(gòu)優(yōu)化設(shè)計(jì)[2]為例,如果使用10 000 個FEs,那么傳統(tǒng)的多目標(biāo)進(jìn)化算法大概需要188 天的時間,這是難以接受的.為了解決昂貴的多目標(biāo)優(yōu)化問題,基于代理模型的昂貴多目標(biāo)進(jìn)化算法被廣泛采用[3?5].即用計(jì)算量小的代理模型去替代部分計(jì)算昂貴的真實(shí)函數(shù)評價(jià)或?qū)Υ罅總€體進(jìn)行預(yù)篩選,以達(dá)到減少計(jì)算量的目的.常用的代理模型包括支持向量機(jī)、多項(xiàng)式響應(yīng)面法、徑向基函數(shù)、人工神經(jīng)網(wǎng)絡(luò)及高斯模型(也稱為Kriging 模型).其中,高斯模型不僅提供了預(yù)測值,還給出了預(yù)測值的置信度,這對于避免代理模型陷入局部最優(yōu)有重要意義.因此,高斯模型被廣泛作為代理模型應(yīng)用于工程優(yōu)化設(shè)計(jì)領(lǐng)域[6].

目前,代理輔助進(jìn)化算法可以分為兩類.第1類是利用代理模型去逼近候選個體的適應(yīng)度值.具體而言,使用歷史數(shù)據(jù)或部分真實(shí)數(shù)據(jù)構(gòu)建高效的代理模型,然后用代理模型近似候選解的適應(yīng)度值.在帕累托優(yōu)化的高效全局優(yōu)化(Pareto optimization efficient global optimization,ParEGO)算法[7]中,建立了單一的代理模型來逼近候選個體的聚集函數(shù),其中聚集函數(shù)是由1 組均勻的權(quán)重向量中隨機(jī)選擇的權(quán)重向量構(gòu)成的.在基于S度量選擇的高效全局優(yōu)化[8]中,個體的適應(yīng)度被定義為個體對群體的超體積分?jǐn)?shù)貢獻(xiàn),代理模型近似逼近超體積指標(biāo)函數(shù).但是由于超體積指標(biāo)函數(shù)的復(fù)雜性,其計(jì)算復(fù)雜度較高.在高斯隨機(jī)過程輔助的基于分解多目標(biāo)進(jìn)化(Multi-objective evolutionary algorithm based on decomposition with the Gaussian stochastic process model,MOEA/D-EGO)[9]算法中,針對每個目標(biāo)函數(shù)建立多個局部代理模型,每次迭代時,候選個體基于距離它最近的聚類中心的局部代理模型進(jìn)行真實(shí)評估.在Kriging 模型輔助的參考向量進(jìn)化(Kriging-assisted reference vector guided evolutionary algorithm,K-RVEA)[10]算法中,同時用m個代理模型逼近m個目標(biāo)函數(shù),另外,采用了1種新的管理代理模型的策略,限制了代理模型的訓(xùn)練樣本量,降低了代理建模的成本.第2 類是將代理模型視作分類器,利用代理模型過濾較差的候選解以達(dá)到減少計(jì)算量的目的.在基于帕累托支配的分類預(yù)選進(jìn)化算法框架[11](Pareto domination based evolutionary algorithm framework with a classification based preselection,CPSMOEA)中,根據(jù)非支配排序?qū)⒎N群分為兩個相等的集合,兩個集合分別存儲好解和壞解,然后訓(xùn)練分類器對新生成的后代進(jìn)行分類,以減少昂貴評估的數(shù)量.在基于分類的代理輔助進(jìn)化(Classification based surrogated-assisted evolutionary algorithm,CSEA)算法[12]中,使用人工神經(jīng)網(wǎng)絡(luò)來預(yù)測候選解和預(yù)先生成的參考解之間的優(yōu)勢關(guān)系,利用預(yù)測中的不確定性信息,結(jié)合優(yōu)勢關(guān)系,選擇有前途的解.

徑向空間劃分是將高維目標(biāo)空間的個體投影到徑向空間,并利用二維網(wǎng)格進(jìn)行劃分的一種技術(shù),可以很好的反映個體的鄰域關(guān)系.這有利于尋找保持種群收斂性和多樣性的解.在這項(xiàng)技術(shù)的基礎(chǔ)上,本文提出了利用Kriging 模型輔助徑向空間劃分的昂貴多目標(biāo)進(jìn)化算法(Kriging model assisted radial space division evolutionary algorithm,K-RSEA),算法主要創(chuàng)新總結(jié)如下:

1)利用徑向空間中解的位置分布衡量種群的擁擠程度.當(dāng)徑向空間中的個體稀疏時,綜合考慮目標(biāo)空間和徑向空間的個體信息,選擇有利于平衡種群的收斂性和多樣性的候選個體真實(shí)評估;當(dāng)徑向空間中的個體擁擠時,代理模型的質(zhì)量被考慮,利用其提供的不確定信息選擇有利于目標(biāo)空間探索的候選個體真實(shí)評估.

2)采用雙檔案管理策略.1 個固定檔案存儲建立代理模型的個體,在徑向空間中利用鄰域關(guān)系對其進(jìn)行維護(hù);1 個可變檔案存儲所有真實(shí)評估得到的非支配解.

本文后續(xù)安排如下.第1 節(jié)介紹算法使用到的相關(guān)技術(shù);第2 節(jié)詳細(xì)介紹基于徑向空間劃分的昂貴多目標(biāo)算法;第3 節(jié)進(jìn)行數(shù)值實(shí)驗(yàn);第4 節(jié)在1個汽車優(yōu)化設(shè)計(jì)的現(xiàn)實(shí)問題上驗(yàn)證了算法性能;第5 節(jié)是總結(jié)和展望.

1 相關(guān)技術(shù)

本節(jié)介紹本文算法使用的高斯過程和徑向空間劃分技術(shù).

1.1 高斯過程

高斯過程又稱作Kriging 模型[13].Kriging 模型被頻繁地用于代理模型的構(gòu)建[5],因?yàn)樗粌H能給出預(yù)測值,還能給出預(yù)測值的不確定信息即置信度.這對于代理的管理而言是極其有用的.Kriging 模型假設(shè)多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)為:

式中,μ(x)是Kriging 模型的預(yù)測值;ε(x) 是均值為0,方差為σ2的統(tǒng)計(jì)過程,表示全局近似的局部偏差即ε(x) ～N(0,σ2);y(x) 的先驗(yàn)分布是1 個均值為μ,方差為σ2的高斯分布.

如圖1 所示的Kriging 模型由3 個訓(xùn)練數(shù)據(jù)(x1,y1)、(x2,y2)和(x3,y3) 建立.實(shí)線表示Kriging 模型估計(jì)的平均值μ,填充部分表示預(yù)測值的置信度σ.每個新的測試向量得到的預(yù)測值分布都是以y(x) 為期望,s(x) 為均方差的正態(tài)分布.圖1中測試向量x′和x′′,其預(yù)測值分別為y′和y′′,該點(diǎn)的置信度分別為s′和s′′.當(dāng)s′

圖1 高斯過程(Kriging 模型)圖解Fig.1 Gaussian process (Kriging model) description

1.2 徑向空間劃分技術(shù)

徑向空間劃分技術(shù)包括兩方面.一方面是將目標(biāo)空間個體投影到徑向空間,另一方面是對徑向空間進(jìn)行網(wǎng)格劃分.

1)徑向投影.徑向投影首先被使用在生物信息學(xué)領(lǐng)域,被用作DNA 序列分類,后被引入多目標(biāo)優(yōu)化領(lǐng)域[15?18].徑向投影過程,首先是將候選解歸一化,歸一化如式(2)所示;然后將歸一化后目標(biāo)空間個體投影到徑向空間.高維空間中個體的鄰域關(guān)系是難以判斷的,而在徑向二維空間中則變得十分直觀.投影過程如式(3)～(6)所示.

式中,Fi、Fmin、Fmax分別表示種群中第i個個體,種群個體的目標(biāo)函數(shù)形成的最小值向量和最大值向量.W1和W2表示權(quán)重向量,表示第i維的角度,I表示m×1 的全為數(shù)字1 的向量.Yi表示最終得到的徑向空間坐標(biāo).

為了說明徑向投影如何反映高維點(diǎn)在二維空間中的分布.假設(shè)兩個點(diǎn)F1,F2∈?m,其中 ?m是m維目標(biāo)空間,在徑向空間中的坐標(biāo)為Y1和Y2.在目標(biāo)空間中F1和F2兩點(diǎn)的歐氏距離為EF=||F1?F2||,對應(yīng)的徑向空間中Y1和Y2兩點(diǎn)的歐氏距離為EY=||Y1?Y2||.因此有如下推導(dǎo):

EY第1 部分的結(jié)果與目標(biāo)空間歐氏距離計(jì)算公式EF是線性近似的;剩下的第2 部分的結(jié)果是F1?F2兩點(diǎn)中不同目標(biāo)的加權(quán)和,當(dāng)ij時,cos(θi ?θj)<1,對EY的影響小于第1 部分,可以被忽略.因此可以得到結(jié)論,任意兩點(diǎn)在高維目標(biāo)空間的歐氏距離類似于徑向空間中的歐氏距離,說明徑向投影之后的個體位置分布能夠反映個體在原目標(biāo)空間中的位置分布.布能夠反映個體在原目標(biāo)空間中的位置分布.

2)網(wǎng)格劃分.徑向空間可以被視作1 個二維平面,容易被劃分為不同的小網(wǎng)格.為了充分衡量個體的鄰域關(guān)系,網(wǎng)格的劃分是自適應(yīng)的.首先根據(jù)投影后解的上界和下界確定徑向空間的個體所占面積的矩形;然后將矩形劃分為個等距的網(wǎng)格;最后計(jì)算各解在徑向網(wǎng)格中的標(biāo)號:

式中,Bl和Bu是徑向坐標(biāo)的下界和上界.d是間距,由種群數(shù)量N確定.

值得注意的是,利用徑向空間劃分輔助代理模型進(jìn)行優(yōu)化的動機(jī)是這一技術(shù)可以直觀的判斷種群的稀疏性.種群稀疏性信息與高斯模型提供的不確定信息相結(jié)合,為選擇哪些個體真實(shí)評估提供了依據(jù),這對于保證代理模型的質(zhì)量十分關(guān)鍵.

2 基于徑向空間劃分的昂貴多目標(biāo)進(jìn)化算法

本文提出一種基于徑向空間劃分的昂貴多目標(biāo)進(jìn)化算法,稱作K-RSEA.算法主要由匹配選擇、環(huán)境選擇、真實(shí)評估解選擇和檔案維護(hù)4 部分組成,算法1 介紹了算法的主流程.

算法 1.K-RSEA 算法流程

算法1 中,首先使用拉丁超立方采樣[19]生成分布均勻的初始種群并利用被真實(shí)評估的個體對每個目標(biāo)建立1 個Kriging 模型逼近昂貴的真實(shí)函數(shù).然后使用匹配選擇和環(huán)境選擇探索目標(biāo)空間,迭代過程中生成的新后代都使用代理模型進(jìn)行評估,如步驟6)～8)所示.在一定迭代次數(shù)后,需要選擇一定數(shù)量解真實(shí)評估以保證代理模型的質(zhì)量,具體細(xì)節(jié)見算法4.最后利用算法5 的策略,使用固定檔案維護(hù)策略刪除劣解,降低建立代理計(jì)算成本的同時避免代理模型被劣解誤導(dǎo).

2.1 匹配選擇

匹配選擇采用兩個二元競標(biāo)賽選擇策略,即徑向空間網(wǎng)格擁擠度和目標(biāo)空間收斂度分布描述種群的多樣性和收斂性.網(wǎng)格擁擠度被定義為徑向空間中同一網(wǎng)格的數(shù)量,如式(15)所示.Gs代表選定的網(wǎng)格,|S|代表該網(wǎng)格中個體數(shù)量.收斂度通過目標(biāo)空間中歸一化后解的歐氏距離衡量,如式(16)所示.具體算法流程如算法2 所示.

算法 2.匹配選擇

匹配選擇得到的父代種群經(jīng)過模擬二項(xiàng)式交叉變異和多項(xiàng)式變異,得到子代種群Q.子代種群由預(yù)先建立的代理模型評估.然后子代種群和父代種群合并后進(jìn)行環(huán)境選擇.

2.2 環(huán)境選擇

本文算法的環(huán)境選擇首先考慮精英非支配排序,然后采用徑向網(wǎng)格劃分策略作為第2 準(zhǔn)則.當(dāng)非支配個體數(shù)量超過最大種群規(guī)模,計(jì)算擁擠度最大的網(wǎng)格中的各個個體適應(yīng)度.適應(yīng)度越大說明個體對種群多樣性和收斂性的維護(hù)幫助越小,刪除適應(yīng)度最大的個體,同時更新網(wǎng)格的擁擠度.適應(yīng)度式為:

式中,r隨著真實(shí)函數(shù)次數(shù)的增加而變小.綜合考慮目標(biāo)空間的收斂度和徑向空間的擁擠度,以保持種群的收斂性和多樣性.值得注意的是,在環(huán)境選擇中式(17)中Q表示已選擇個體的集合,在真實(shí)評估解的選擇中式(17)中Q表示同一聚類個體的集合.環(huán)境選擇如算法3 所示.

算法3.環(huán)境選擇

2.3 真實(shí)評估解的選擇

為了保證代理模型的質(zhì)量,在迭代一定世代后,部分解被選擇真實(shí)評估.被選擇的解應(yīng)該充分反映當(dāng)前種群的收斂性能和多樣性能.同時,代理模型存在陷入局部最優(yōu)的風(fēng)險(xiǎn),為了避免這一點(diǎn),一些能夠反映代理模型預(yù)測準(zhǔn)確度的解也被考慮真實(shí)評估.圖2(a)表示建立代理模型的個體位置分布.圖2(b)表示當(dāng)前種群在徑向空間中的位置分布較為擁擠,說明代理模型可能陷入了局部最優(yōu),此時站在代理模型角度選擇不確定程度大的解,幫助代理模型跳出局部最優(yōu).圖2(c)表示當(dāng)前種群在徑向空間中的分布稀疏,說明當(dāng)前分布性能較好,此時站在種群角度選擇反映種群收斂性能的解.

圖2 徑向空間中個體的位置分布情況Fig.2 Individual location distribution in radial space

流程如算法4 所示.首先,步驟2)～4)將固定檔案和當(dāng)前種群投影到徑向空間,分別得到固定檔案和當(dāng)前種群個體的徑向投影網(wǎng)格序號.然后,根據(jù)真實(shí)評估解的數(shù)量將當(dāng)前種群聚類成Q簇.接著,步驟9)判斷固定檔案中個體在徑向空間所占據(jù)的網(wǎng)格數(shù)量和當(dāng)前種群在徑向空間所占據(jù)的網(wǎng)格數(shù)量差異.當(dāng)前種群中個體所占據(jù)的網(wǎng)格數(shù)量更多時,說明當(dāng)前種群的較為稀疏,此時更偏重于收斂性的保持,于是在每個簇中利用式(17),選擇適應(yīng)度值最小的個體;當(dāng)前種群中個體所占據(jù)的網(wǎng)格數(shù)量更少時,說明當(dāng)前種群較為擁擠,此時更偏重于多樣性的保持,為了避免代理模型陷入局部最優(yōu),于是在每個簇中找到平均不確定性最大的個體進(jìn)行重評估.其中,步驟14)計(jì)算所有個體在各個目標(biāo)上的不確定性平均值,步驟16)選擇不確定性平均值最大的個體進(jìn)行真實(shí)評估.值得注意的是,算法4 中涉及到的k-means和unique 函數(shù)都是matlab 內(nèi)置函數(shù),前者表示K 中心聚類,后者的目的是尋找唯一元素序號;fitness 函數(shù)利用式(17)計(jì)算當(dāng)前個體適應(yīng)度值.

算法 4.選擇真實(shí)評估解

2.4 雙檔案維護(hù)策略

在獲得新的真實(shí)評估解后,更新固定檔案A1和可變檔案A2.對于固定檔案A1.為了限制建立代理模型的時間成本,加入一定數(shù)量新解就需要刪除一定數(shù)量劣解.新生成的新解被保留,A1中剩下的解被投影到徑向空間,在徑向空間中對其進(jìn)行K 中心聚類,然后針對每個聚類選擇目標(biāo)空間中收斂性最好的解,直到檔案的數(shù)量達(dá)到最大上限.對于可變檔案A2,新加入的解與原本檔案的解通過非支配排序,非支配第1 層級的解被保留,剩下的解被舍棄.具體算法流程見算法5.

算法5.雙檔案維護(hù)策略

2.5 時間復(fù)雜度分析

本節(jié)分析K-RSEA 算法的復(fù)雜度.該算法的主要時間成本來源于代理模型的建立、匹配選擇、環(huán)境選擇和雙層檔案的管理.設(shè)種群規(guī)模為N,目標(biāo)維數(shù)為M.建立代理模型的時間復(fù)雜度為 O (MN3);在匹配選擇時,采用二元錦標(biāo)賽準(zhǔn)則,時間復(fù)雜度為 O (MN2);在環(huán)境選擇過程中,考慮最壞情況下個體都是互不支配的,非支配排序的時間復(fù)雜度為O(MN2),徑向投影的時間復(fù)雜度為 O (MN),目標(biāo)空間收斂度計(jì)算復(fù)雜度為 O (MN),徑向空間分布度計(jì)算復(fù)雜度為 O (N),所以環(huán)境選擇總的計(jì)算復(fù)雜度為 O (MN2);在雙重檔案管理過程中,聚類的時間復(fù)雜度為O(N),遍歷每個類別的時間復(fù)雜度為O(N),因此,K-RSEA 算法最壞的時間復(fù)雜度為O(MN3).

3 仿真實(shí)驗(yàn)結(jié)果及分析

為了測試K-RSEA 算法的性能,選取了5 個最新提出的多目標(biāo)算法進(jìn)行比較.分別是傳統(tǒng)的多目標(biāo)算法基于參考點(diǎn)的非支配排序方法的多目標(biāo)進(jìn)化優(yōu)化算法(An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach,NSGA-III)[20],基于函數(shù)逼近的昂貴多目標(biāo)算法MOEA/D-EGO[9]和KRVEA[10],以及基于分類器的昂貴多目標(biāo)進(jìn)化算法CSEA[12]和CPS-MOEA[11].所有算法都是在多目標(biāo)進(jìn)化算法開源平臺PlatEMO[21]上運(yùn)行.實(shí)驗(yàn)仿真都是在Intel core,8 GB 內(nèi)存,2.20 GHz 主頻,Win1064位操作系統(tǒng)上運(yùn)行.

3.1 測試問題及算法參數(shù)設(shè)置

本文選取了DTLZ[22]和步行魚群(Walking fish group,WFG)[23]系列測試函數(shù)代替昂貴的多目標(biāo)優(yōu)化問題的真實(shí)函數(shù).表1 給出了測試問題及其特征.本文分別在基準(zhǔn)問題的3、4、6、8、10 個目標(biāo)上測試了算法的性能.所有問題的決策變量都被設(shè)置為10.種群規(guī)模設(shè)置為11d?1,d為決策變量數(shù)量.固定檔案大小也設(shè)置為11d?1.在更新代理模型之前的運(yùn)行代數(shù)設(shè)置為20,每次更新代理模型時選擇5 個解真實(shí)評估.針對每個測試問題,每個算法獨(dú)立運(yùn)行20 次,評價(jià)次數(shù)設(shè)置為300,K-RSEA和對比算法都采用置信度σ=0.05 的Wilcoxon 秩和檢驗(yàn)方法進(jìn)行評判.

表1 測試問題及特征Table 1 Test problems and their features

3.2 性能評價(jià)指標(biāo)

本文采用反轉(zhuǎn)世代距離(Inverted generation distance,IGD)[24]和超體積(Hypervolume,HV)[25]兩個綜合指標(biāo)來衡量算法的性能.

設(shè)P*是沿真實(shí)帕累托前沿面PF從目標(biāo)空間采樣的1 組均勻分布的解.設(shè)P是對真實(shí)帕累托前沿面的近似.IGD 定義如下:

式中,d(v,P)是帕累托最優(yōu)面上的點(diǎn)v到最終解集P中個體的最小歐氏距離.IGD 值越小,就意味著算法的綜合性能越好.

2) HV 指標(biāo)

超體積指標(biāo)是嚴(yán)格遵守Pareto 支配原則的.HV 定義如下:

式中,λ代表勒貝格測度,vi代表參考點(diǎn)和非支配個體Pi構(gòu)成的超體積,S代表非支配集.HV 值越大,說明算法的綜合性能越好.

3.3 仿真實(shí)驗(yàn)結(jié)果和分析

表2～5 分別收集了K-RSEA和5種對比算法在20 次獨(dú)立運(yùn)行期間在DTLZ 測試集和WFG 測試集上獲得的IGD 值和HV 值的統(tǒng)計(jì)結(jié)果,包括平均值和標(biāo)準(zhǔn)差,其中最佳結(jié)果粗體顯示.符號 “+”表示比較算法的統(tǒng)計(jì)結(jié)果優(yōu)于K-RSEA,符號 “?”表示比較算法的統(tǒng)計(jì)結(jié)果比K-RSEA 差,符號 “=”表示沒有顯著差異.

由表2～5 可以看出,K-RSEA 在DTLZ 測試集和WFG 測試集上整體表現(xiàn)最好.表2收集到的IGD 值中,K-RSEA 取得的IGD 最佳值數(shù)量為11 個,NSGA-III、CPS-MOEA、CSEA、MOEA/DEGO 以及K-RVEA 取得的最佳值IGD結(jié)果數(shù)量分別為0、1、10、4、9;表3 收集到的HV值中,KRSEA 取得的HV 最佳值的數(shù)量為13 個.表4 收集到的IGD 值中,K-RSEA 取得的IGD 最佳值的數(shù)量為21 個;表5 收集到的HV 值中,K-RSEA 取得的HV 最佳值的數(shù)量為29 個,NSGA-III、CPSMOEA、CSEA、MOEA/D-EGO和K-RVEA 取得的最佳值HV 值結(jié)果數(shù)量分別為0、1、5、1和9.

表2 6種算法在不同維數(shù)的DTLZ 測試問題上獲得的IGD 平均值和標(biāo)準(zhǔn)差Table 2 The IGD average and standard deviation obtained by the six algorithms on DTLZ test problems of different dimensions

表2 6種算法在不同維數(shù)的DTLZ 測試問題上獲得的IGD 平均值和標(biāo)準(zhǔn)差 (續(xù)表)Table 2 The IGD average and standard deviation obtained by the six algorithms on DTLZ test problems of different dimensions (continued table)

表3 6種算法在不同維數(shù)的DTLZ 測試問題上獲得的HV 平均值和標(biāo)準(zhǔn)差Table 3 The HV average and standard deviation obtained by the six algorithms on DTLZ test problems of different dimensions

表3 6種算法在不同維數(shù)的DTLZ 測試問題上獲得的HV 平均值和標(biāo)準(zhǔn)差 (續(xù)表)Table 3 The HV average and standard deviation obtained by the six algorithms on DTLZ test problems of different dimensions (continued table)

表4 6種算法在不同維數(shù)的WFG 測試問題上獲得的IGD 平均值和標(biāo)準(zhǔn)差 (續(xù)表)Table 4 The IGD average and standard deviation obtained by the six algorithms on WFG test problems of different dimensions (continued table)

表4 6種算法在不同維數(shù)的WFG 測試問題上獲得的IGD 平均值和標(biāo)準(zhǔn)差 (續(xù)表)Table 4 The IGD average and standard deviation obtained by the six algorithms on WFG test problems of different dimensions (continued table)

表5 6種算法在不同維數(shù)的WFG 測試問題上獲得的HV 平均值和標(biāo)準(zhǔn)差Table 5 The HV average and standard deviation obtained by the six algorithms on WFG test problems of different dimensions

表5 6種算法在不同維數(shù)的WFG 測試問題上獲得的HV 平均值和標(biāo)準(zhǔn)差 (續(xù)表)Table 5 The HV average and standard deviation obtained by the six algorithms on WFG test problems of different dimensions (continued table)

3.3.1 DTLZ 測試集IGD和HV 指標(biāo)對比實(shí)驗(yàn)和分析

黨的十八大明確指出要重點(diǎn)建設(shè)生態(tài)文明，而綠色營銷既是生態(tài)文明建設(shè)的內(nèi)在體現(xiàn)，又是生態(tài)文明建設(shè)取得成果的市場檢驗(yàn)。所以，生態(tài)文明建設(shè)必須依靠大力發(fā)展綠色營銷，只有綠色營銷落到實(shí)處，生態(tài)文明建設(shè)才會有成效。[1]碭山縣1999年被批準(zhǔn)為國家生態(tài)示范縣,2002年底被認(rèn)定為全國無公害農(nóng)產(chǎn)品(水果)生產(chǎn)示范基地縣達(dá)標(biāo)單位，這為碭山酥梨綠色營銷奠定了良好基礎(chǔ)。

對于DTLZ1和DTLZ3 具有多模態(tài)特點(diǎn)的問題,K-RSEA 未能取得令人滿意的結(jié)果,CSEA 在這類問題上取得了最佳結(jié)果.CSEA 利用分類器探索未知空間,對于處理具有多個局部最優(yōu)解的多模態(tài)問題具有更強(qiáng)優(yōu)勢.表2 獲得的統(tǒng)計(jì)結(jié)果中IGD值都很大,而在表3 獲得的統(tǒng)計(jì)結(jié)果中這兩類測試問題大部分HV 值都為0.這說明算法獲得的非支配集離真實(shí)的帕累托前沿依然很遠(yuǎn),解決這些問題需要更多函數(shù)評估.為了直觀地說明,圖3可視化了各算法在3 個目標(biāo)DTLZ1 問題上運(yùn)行得到的最佳IGD 值對應(yīng)的非支配解.由圖3 可以看出,CSEA相比其他算法更接近真實(shí)的帕累托前沿,傳統(tǒng)的進(jìn)化算法NSGA-III 表現(xiàn)最差.

圖3 6種算法在求解3 個目標(biāo)DTLZ1 問題過程中獲得的最佳HV 值對應(yīng)的非支配解集Fig.3 The non-dominated solution set corresponding to the best HV value obtained by the six algorithms in solving the three objective DTLZ1 problems

DTLZ2 是1 個具有凹面橢圓的測試問題,K-RSEA 在DTLZ2 問題上取得了最佳結(jié)果,其次是K-RVEA和MOEA/D-EGO,剩余的算法都表現(xiàn)出了相似的性能,都未能得到收斂性和多樣性良好的結(jié)果.圖4 可視化了具有10 個目標(biāo)的DTLZ2 問題的平行坐標(biāo)圖和徑向坐標(biāo)圖.從圖4 平行坐標(biāo)圖和徑向坐標(biāo)圖可以看出,K-RSEA 取得的結(jié)果相比其他算法具有更好的收斂性和分布性.

圖4 6種算法在10 個目標(biāo)DTLZ2 測試問題上最佳解集的平行坐標(biāo)圖和徑向坐標(biāo)圖Fig.4 Parallel coordinate diagram and radial coordinate diagram of the best solution set of the six algorithms on 10 objective DTLZ2 test problems

DTLZ4 是在DTLZ2 基礎(chǔ)上修改后得到的具有偏好特點(diǎn)的測試問題.K-RVEA和CSEA 取得了最佳結(jié)果,然后是K-RSEA、MOEA/D-EGO、CPS-MOEA和NSGA-III.K-RVEA 依靠預(yù)先定義的參考向量能夠快速定位偏好區(qū)域,而K-RSEA利用個體之間的鄰域關(guān)系,在搜索過程中可能被誤導(dǎo),從而在這個問題上表現(xiàn)較差,但是當(dāng)目標(biāo)數(shù)量更多時,如8、10 個目標(biāo),K-RSEA 的競爭力并不遜色于其他代理輔助進(jìn)化算法.如圖5(a)和圖5(b)所示,在求解3 個目標(biāo)DTLZ 問題時,K-RSEA 的結(jié)果與K-RVEA和CSEA 相比IGD 值和HV 值的變化都并不突出;但是如圖5(c)和圖5(d)所示,當(dāng)求解10 個目標(biāo)DTLZ4 問題時,無論是IGD 值還是HV 值的變化,K-RSEA 在對比算法中都極具優(yōu)勢.值得注意的是,部分算法的IGD和HV 值在迭代過程中表現(xiàn)出一條水平線,如MOEA/D-EGO,這說明算法在這個問題上陷入了局部最優(yōu).

圖5 K-RSEA和5種對比算法在求解3 個和10 個目標(biāo)DTZL4 問題時的IGD和HV 變化Fig.5 The IGD and HV changes of K-RSEA and five comparison algorithms when solving 3 and 10 objective DTZL4 problems

DTLZ5與DTLZ2 的表達(dá)式在形式上相似,但是具有退化的特點(diǎn).由表2～3 可以看出,K-RSEA在每個目標(biāo)上都取得了最佳結(jié)果.圖6反映了不同算法在處理DTLZ5 問題時IGD和HV 指標(biāo)變化情況.由圖6 可以看出,K-RSEA的IGD 值變化趨勢更快,而K-RVEA 雖然也取得了良好的結(jié)果,但是在迭代過程中有一段平緩的變化,說明其陷入了局部區(qū)域,所以呈現(xiàn)出階梯狀下降;K-RSEA 的HV值變化趨勢在對比算法中具有絕對優(yōu)勢.因此KRSEA 是擅長處理這類退化問題.

圖6 K-RSEA和5種對比算法在求解3 個目標(biāo)DTZL5 問題時的IGD和HV 變化Fig.6 The IGD and HV changes of K-RSEA and five comparison algorithms when solving 3 objective DTZL5 problems

DTLZ6 是在DTLZ5 問題上修改得到的,同時具有退化和偏好的特性.MOEA/D-EGO 在這個問題上取得了最好的結(jié)果,其次是K-RSEA和KRVEA.值得注意的是,大部分算法在3、4、6 個目標(biāo)上的HV 值都為0,這說明這類問題是難以被處理的,需要更多的函數(shù)評估.

DTLZ7 是具有1 組不連續(xù)帕累托最優(yōu)面的測試問題.圖7 可視化了3 個目標(biāo)DTLZ7 上得到的非支配解集.可以直觀地看到K-RSEA 取得了收斂性能和分布性能最佳的結(jié)果,MOEA/D-EGO和KRVEA 收斂性良好但是分布不佳,剩余算法則未能取得令人滿意的結(jié)果,基于分類器的算法甚至未能取得良好收斂的解,不適合處理這類不連續(xù)問題.

圖7 K-RSEA和5種對比算法求解DTLZ7 問題過程中獲得的最佳HV 值對應(yīng)的非支配前沿Fig.7 The non-dominant frontier corresponding to the best HV value obtained in the process of solving the DTLZ7 problem by K-RSEA and five comparison algorithms

從DTLZ 系列測試問題實(shí)驗(yàn)結(jié)果可以看到,KRSEA 在處理退化和不連續(xù)問題上具有極強(qiáng)的優(yōu)勢,雖然在處理多模態(tài)問題和偏好問題上表現(xiàn)不佳,但是,與其他算法相比K-RSEA 表現(xiàn)出了自身的競爭力.

3.3.2 WFG 測試集IGD和HV 指標(biāo)對比實(shí)驗(yàn)和分析

對于WFG1 問題,K-RSEA 未能取得最佳結(jié)果,CSEA和K-RVEA 在該問題上取得了最佳結(jié)果.這是因?yàn)閃FG1 的帕累托前沿不規(guī)則且具有偏好特性,CSEA 的分類器和K-RVEA 預(yù)先定義的參考向量都可以幫助快速定位偏好區(qū)域.K-RSEA僅僅依靠個體之間的鄰域關(guān)系,對于偏好區(qū)域的搜索性能略差.雖然K-RSEA 的性能稍遜于CSEA和K-RVEA,但是也表現(xiàn)出了較強(qiáng)的競爭力.

WFG2 問題的真實(shí)帕累托前沿面是斷開的.在所有算法中,只有K-RSEA 很好地處理了這個問題.在第3、4、6、8、10 個目標(biāo)上,K-RSEA 都取得了最佳結(jié)果.為了更直觀的感受不同算法在WFG2問題上的表現(xiàn),圖8 可視化了6 個算法在3 個目標(biāo)的WFG2 問題上的非支配前沿.其中只有K-RSEA取得了收斂和多樣性最好的解.CSEA和MOEA/D-EGO 取得了分布性良好,但收斂性不佳的結(jié)果;K-RVEA 結(jié)果收斂性良好,但是分布性不佳.這說明K-RSEA 有助于處理這類不連續(xù)的問題.

圖8 K-RSEA和5種對比算法求解WFG2 問題過程中獲得的最佳HV 值對應(yīng)的非支配前沿Fig.8 The non-dominant frontier corresponding to the best HV value obtained in the process of solving the WFG2 problem with K-RSEA and five comparison algorithms

WFG3 是一個退化問題,其最終結(jié)果是一條線性的退化曲線.由表4～5 可以看出,K-RSEA在第6、8、10 個目標(biāo)取得了最佳結(jié)果.其原因在于徑向空間能夠較好的衡量解的鄰域關(guān)系,在高維空間中保持解的多樣性更具有優(yōu)勢.

WFG4～9 的真實(shí)帕累托前沿面都是凹面的超橢圓.由表4～5 可以看出,針對WFG4和WFG9兩類多模態(tài)問題上,K-RSEA 的結(jié)果與K-RVEA表現(xiàn)出了相似的性能.這是因?yàn)镵-RSEA 采用徑向空間劃分方式指導(dǎo)種群搜索方向,而K-RVEA 利用空參考解數(shù)量變化判斷種群的收斂和分布.兩者對局部區(qū)域的探索能力相對較差.CSEA 的分類器有利于局部探索,在三維取得了良好的結(jié)果,但在高維表現(xiàn)出較差的結(jié)果,分類器在高維空間的誤差會變大,進(jìn)而影響了對局部區(qū)域的搜索能力.針對WFG5、6、7、8 問題,K-RSEA 取得了令人滿意的結(jié)果.圖9和圖10 反映了在處理WFG5、6、8 問題時的IGD 值和HV 值的變化.由圖9 可以看出,在WFG5 問題上,K-RSEA 的IGD 值是下降最快的.在WFG6和WFG8 不可分問題上,K-RSEA在迭代過程中出現(xiàn)了小幅度的波動,這是因?yàn)樘岢龅乃惴ú粌H僅考慮了種群特性,也考慮了代理模型的質(zhì)量,在陷入局部最優(yōu)時,選擇種群中不確定性程度大的解真實(shí)評估,最終取得了最佳結(jié)果.由圖10可以看出,在WFG5、6、8 問題上,K-RSEA 的HV 值上升趨勢最快,變化程度較為平滑,說明了算法相比同類算法更具有優(yōu)勢.圖11 可視化了10 個目標(biāo)WFG7 問題的平行坐標(biāo)圖和徑向坐標(biāo)圖.從平行坐標(biāo)可以發(fā)現(xiàn),K-RSEA和K-RVEA 都取得了良好收斂性的解集;從徑向坐標(biāo)可以發(fā)現(xiàn),KRSEA 的分布是最均勻的,說明了K-RSEA的優(yōu)秀性能.

圖9 K-RSEA和5種對比算法在求解3 個目標(biāo)WFG5、WFG6和WFG8 問題時的IGD 變化Fig.9 The IGD changes of K-RSEA and five comparison algorithms when solving three objective WFG5,WFG6 and WFG8 problems

圖10 K-RSEA和5種對比算法在求解10 個目標(biāo)WFG5、WFG6和WFG8 問題時的HV 變化Fig.10 The HV changes of K-RSEA and five comparison algorithms when solving 10 objective WFG5,WFG6 and WFG8 problems

圖11 6種算法在10 個目標(biāo)WFG7 測試問題上最佳解集的平行坐標(biāo)圖和徑向坐標(biāo)圖Fig.11 Parallel coordinate diagram and radial coordinate diagram of the best solution set of the six algorithms on 10 objective WFG7 test problems

3.3.3 算法指標(biāo)統(tǒng)計(jì)結(jié)果差異分析

從測試問題的統(tǒng)計(jì)結(jié)果可以看到在部分測試問題上,算法的IGD 值和HV 值排序并不一致,IGD值更優(yōu)的算法在HV 值上不一定更優(yōu),造成這種差異的原因有兩點(diǎn).1) IGD 指標(biāo)是GD 指標(biāo)的逆向映射,也就是說在使用IGD 指標(biāo)時候,需要在真實(shí)的帕累托前沿面上采樣;而HV 指標(biāo)根據(jù)設(shè)置的參考點(diǎn)計(jì)算,不需要知道真實(shí)的帕累托前沿.真實(shí)帕累托面采樣點(diǎn)的數(shù)量和參考點(diǎn)大小的設(shè)置會影響兩者的結(jié)果.2) IGD 指標(biāo)并不是嚴(yán)格滿足帕累托支配關(guān)系的,一個較好的解集可能被評估為較差,而HV 指標(biāo)是嚴(yán)格遵守帕累托支配原則的[26].IGD和HV 指標(biāo)都是綜合性指標(biāo),都能評價(jià)算法的綜合性能,然而大部分昂貴的現(xiàn)實(shí)問題往往是很難得到真實(shí)帕累托前沿面的,所以HV 指標(biāo)的結(jié)果可能會更有意義.

3.3.4 算法運(yùn)行時間對比分析

通過測試第5、10、15 個決策變量的WFG 系列問題檢驗(yàn)算法的時間成本.圖12 可視化了WFG2、WFG5和WFG8 在不同決策變量上的運(yùn)行時間.從圖12 可以很明顯地看出,在對比算法中擬議算法K-RSEA 的時間成本小于CSEA和MOEA/D-EGO.CSEA 采用人工神經(jīng)網(wǎng)絡(luò)作為分類器,在局部探索時具有優(yōu)勢,但是其時間成本也最高.MOEA/D-EGO 利用模糊聚類的方式建立了多個高斯回歸模型,增加了時間成本.K-RVEA和K-RSEA 取得了近似的時間成本,二者都是利用單一的代理逼近單一目標(biāo),但是K-RVEA 不涉及非支配排序,所以運(yùn)行時間相對較低.NSGA-III 是傳統(tǒng)的進(jìn)化算法,不適合解決昂貴的多目標(biāo)問題.CPS-MOEA 利用KNN 作為分類器對候選解進(jìn)行預(yù)篩選,在建立模型的過程中對訓(xùn)練模型數(shù)據(jù)量的要求較高,其雖然時間成本不高,但是其代理模型的質(zhì)量較差.K-RSEA 雖然未能取得最佳結(jié)果,但是其時間成本相比昂貴的多目標(biāo)優(yōu)化問題處于可接受的范圍.

圖12 6種算法分別在不同問題上的運(yùn)行時間比較Fig.12 Comparison of the running time of the six algorithms on different problems

4 汽車耐撞性設(shè)計(jì)問題

在汽車工業(yè)領(lǐng)域,耐撞性指標(biāo)尤其重要,然而對汽車做1 次有限元虛擬仿真實(shí)驗(yàn)的計(jì)算成本是及其高昂的,因此這類問題可以被視作計(jì)算昂貴的多目標(biāo)優(yōu)化問題.汽車耐撞性優(yōu)化設(shè)計(jì)要求在吸能、加速度集成和腳趾板入侵3 個目標(biāo)之間尋找最佳結(jié)果[27].本文采用傳統(tǒng)多目標(biāo)進(jìn)化算法NSGA-III、基于適應(yīng)度逼近的K-RVEA、MOEA/D-EGO和基于分類器的CSEA、CPS-MOEA和本文提出的KRSEA6 六種算法來解決這個問題.最大函數(shù)評價(jià)次數(shù)設(shè)置為150 次.種群設(shè)置為11d?1,d代表決策變量數(shù)量,本問題決策變量數(shù)量為5.在實(shí)際問題上10 次運(yùn)行得到的IGD和HV 平均值被用作評價(jià)結(jié)果.值得注意的的是,在計(jì)算IGD 值時,所有算法得到的非支配集作為參考集.最終得到的結(jié)果如表6 所示,最佳結(jié)果用粗體顯示.圖13 可視化了最終得到的非支配個體分布情況.從圖13 可以看出,K-RSEA 提供了分布性更好的解集,相較之下質(zhì)量更好.表6 記錄了10 次運(yùn)行得到的IGD和HV 值的平均值.K-RSEA 都取得了最佳結(jié)果.

表6 汽車碰撞優(yōu)化設(shè)計(jì)問題上獲得的IGD和HV 的平均值Table 6 The average values of IGD and HV obtained on the car crash optimization design problem

圖13 算法在汽車耐撞性優(yōu)化問題上的非支配解Fig.13 The non-dominant solution of the algorithm in the optimization of automobile crash-worthiness

5 結(jié)束語

本文提出了一種基于徑向空間劃分的昂貴多目標(biāo)進(jìn)化(K-RSEA)算法.該算法根據(jù)徑向空間中個體的擁擠程度選擇合適的解真實(shí)評估.所選擇的解兼顧種群的多樣和收斂性能的同時還考慮了代理模型的質(zhì)量.另外,固定檔案限制代理模型的訓(xùn)練時間成本,可變檔案存儲真實(shí)評估得到的非支配解,不僅僅降低了算法的時間成本,也提高了代理模型的質(zhì)量.數(shù)值實(shí)驗(yàn)表明,K-RSEA 在處理昂貴的多目標(biāo)優(yōu)化問題能夠提供分布性和多樣性更好的結(jié)果,與最新提出的幾種先進(jìn)算法相比,K-RSEA 解決昂貴多目標(biāo)優(yōu)化問題更具有優(yōu)勢.最后,在1 個汽車耐撞性優(yōu)化設(shè)計(jì)問題驗(yàn)證了算法的現(xiàn)實(shí)意義.未來工作將會把本文提出的算法K-RSEA 擴(kuò)展到復(fù)雜約束問題并嘗試解決更多的昂貴現(xiàn)實(shí)問題.