一種新的全局排序高維多目標(biāo)優(yōu)化算法

劉仁云, 張美娜, 姚亦飛, 于繁華

(1. 長(zhǎng)春師范大學(xué) 數(shù)學(xué)學(xué)院, 長(zhǎng)春 130032； 2. 長(zhǎng)春師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130032；3. 北華大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 吉林 吉林 132013)

多目標(biāo)最優(yōu)化問(wèn)題(multi-objective optimization problems, MOPs)在工程實(shí)踐和日常生活中應(yīng)用廣泛. 多目標(biāo)優(yōu)化問(wèn)題需要同時(shí)對(duì)多個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化, 而一個(gè)目標(biāo)的性能提高通常會(huì)導(dǎo)致其他目標(biāo)的性能下降, 使得對(duì)這類算法的求解變得更困難. 目前, 已有許多應(yīng)用廣泛的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithms, MOEAs), 例如： 一個(gè)快速精英機(jī)制的多目標(biāo)遺傳算法(a fast and elitist multiobjective genetic algorithm, NSGA-Ⅱ)[1], Pareto進(jìn)化算法的改進(jìn)(improving the strength Pareto evolutionary algorithm, SPEA2)[2]等算法, 但這些算法在求解高維多目標(biāo)優(yōu)化問(wèn)題時(shí)性能顯著下降. 針對(duì)高維多目標(biāo)優(yōu)化求解問(wèn)題目前已有許多方法, 主要分為Pareto支配和非Pareto支配方法. Pareto支配方法, 如ε-Pareto支配[3]、 網(wǎng)格排序[4]、α-支配[5]等, 該類方法的缺點(diǎn)是需要根據(jù)主觀偏好給出相應(yīng)的準(zhǔn)則, 隨著目標(biāo)個(gè)數(shù)的增加, 在一定程度上增大了非支配個(gè)體的選擇壓力, 不能從根本上解決選擇壓力退化的問(wèn)題. 非Pareto支配方法, 如平均等級(jí)排序(average ranking, AR)[6]、 全局排序(global ranking, GR)[7]等, 這些方法能獲得較好的解集收斂性, 但沒(méi)有很好地解決解集分布性. 針對(duì)非Pareto支配存在的問(wèn)題, 本文提出一種新的基于全局排序求解高維多目標(biāo)優(yōu)化問(wèn)題算法(a novel global sorting many-objective optimization algorithm, NGR-MOEA), 該算法不僅具有良好的收斂性, 而且解決了解集分布不均勻的問(wèn)題.

1 高維多目標(biāo)優(yōu)化問(wèn)題描述

多目標(biāo)優(yōu)化問(wèn)題定義為

(1)

其中Ω是決策(變量)空間,F:Ω→m由m個(gè)真實(shí)的目標(biāo)函數(shù)組成, 且m稱為目標(biāo)空間, 可實(shí)現(xiàn)的目標(biāo)集定義為集合{F(x)|x∈Ω}.

定義1(Pareto支配)[7]假設(shè)有兩個(gè)解p和q, 如果滿足下列條件:

(2)

則稱pPareto支配q, 其中m是目標(biāo)個(gè)數(shù).

定義2(Pareto最優(yōu)解集)[7]對(duì)于問(wèn)題(1)的一個(gè)解x*∈Ω, 如果不存在x∈Ω, 使得xx*, 則x*為該問(wèn)題的Pareto最優(yōu)解. 由所有Pareto最優(yōu)解構(gòu)成的集合, 稱為Pareto最優(yōu)解集(Pareto optimal solution set, PS).

定義3(Pareto前沿)[7]Pareto最優(yōu)解集在目標(biāo)空間形成的曲面, 稱為Pareto前沿(Pareto optimal front, PF).

2 新的全局排序高維多目標(biāo)進(jìn)化算法

MOEAs的目的是將非支配目標(biāo)向量較好地收斂到PF, 同時(shí)生成的向量在PF上有良好的分布性. 為提高M(jìn)OEAs在高維多目標(biāo)優(yōu)化問(wèn)題上的收斂性和分布性, 本文提出一種新的基于全局排序的高維多目標(biāo)進(jìn)化算法(NGR-MODE).

2.1 個(gè)體目標(biāo)適應(yīng)度計(jì)算策略

文獻(xiàn)[7]給出了一種個(gè)體目標(biāo)適應(yīng)度計(jì)算方法, 該方法對(duì)兩兩個(gè)體在目標(biāo)空間中進(jìn)行比較, 進(jìn)而確定個(gè)體適應(yīng)度. 定義種群POP中每個(gè)個(gè)體Xi的全局排序值GR(Xi)等于該個(gè)體在所有目標(biāo)上與種群中所有其他個(gè)體相應(yīng)目標(biāo)值的差值之和, 計(jì)算公式為

(3)

其中個(gè)體Xj為種群POP中不同于Xi的任意個(gè)體,m∈[1,M]為目標(biāo)維數(shù),fm為個(gè)體在第m個(gè)目標(biāo)上的歸一化函數(shù)值.

2.2 灰色關(guān)聯(lián)分析

灰色關(guān)聯(lián)分析[8]是指對(duì)一個(gè)系統(tǒng)發(fā)展變化態(tài)勢(shì)的定量描述和比較方法, 其基本思想是通過(guò)確定參考數(shù)據(jù)列和若干個(gè)比較數(shù)據(jù)列的幾何形狀相似程度判斷其聯(lián)系是否緊密, 其反映了曲線間的關(guān)聯(lián)程度.操作步驟如下：

1) 確定反映系統(tǒng)行為特征的母序列及影響系統(tǒng)行為的子序列；

2) 對(duì)數(shù)據(jù)進(jìn)行無(wú)量綱化處理(由于系統(tǒng)中各因子列的數(shù)據(jù)可能存在維數(shù)上的差異, 比較不方便或難以得出正確的結(jié)論, 因此灰色關(guān)聯(lián)度分析一般需要對(duì)數(shù)據(jù)進(jìn)行無(wú)量綱處理, 即歸一化處理), 計(jì)算公式為

(4)

3) 計(jì)算關(guān)聯(lián)系數(shù)

(5)

4) 計(jì)算灰色關(guān)聯(lián)度

(6)

5) 評(píng)價(jià)分析, 根據(jù)灰色關(guān)聯(lián)度對(duì)評(píng)價(jià)對(duì)象進(jìn)行排序, 關(guān)聯(lián)度越高, 評(píng)價(jià)結(jié)果越好.

2.3 新的全局排序方法策略

目前, 大多數(shù)MOEAs的適應(yīng)值評(píng)價(jià)方法僅計(jì)算個(gè)體在每個(gè)目標(biāo)上的函數(shù)值, 再通過(guò)各類支配排序方法比較其優(yōu)劣. 在高維多目標(biāo)優(yōu)化問(wèn)題中, 許多支配排序方法被改進(jìn), 改進(jìn)后的支配排序方法雖能在一定程度上增強(qiáng)選擇壓力, 提升收斂性能, 但解集的分布性欠佳. 有些算法在充分考慮分布性后收斂性得不到滿足. 基于此, 本文將個(gè)體目標(biāo)適應(yīng)度計(jì)算策略與灰色關(guān)聯(lián)分析相結(jié)合, 設(shè)計(jì)一種新的精英選擇策略. 對(duì)于種群中個(gè)體Xi, 假設(shè)其在所有目標(biāo)函數(shù)上與種群中其他個(gè)體相應(yīng)目標(biāo)值的差值之和為GR(Xi), 與種群中其他個(gè)體相應(yīng)目標(biāo)值的灰色關(guān)聯(lián)度為GRA(Xi), 則其全局適應(yīng)度值為

fitness(Xi)=w1×GR(Xi)-w2×GRA(Xi),

(7)

其中w1和w2為在[0,1]內(nèi)取值的權(quán)重系數(shù), 用于協(xié)調(diào)收斂性及分布性的權(quán)重, 本文取值分別為1.5和0.5.

該精英選擇策略由兩部分組成： 一是通過(guò)個(gè)體目標(biāo)適應(yīng)度計(jì)算策略直接給出種群中每個(gè)個(gè)體的優(yōu)劣程度； 二是在每次迭代中選取函數(shù)值最小目標(biāo)組成理想點(diǎn)序列(母序列), 每個(gè)個(gè)體的目標(biāo)函數(shù)值組成比較序列(子序列). 通過(guò)灰色關(guān)聯(lián)分析計(jì)算母序列與子序列的關(guān)聯(lián)度, 增強(qiáng)灰色關(guān)聯(lián)度高的子序列所對(duì)應(yīng)個(gè)體被選擇的概率. 通過(guò)確定母序列和若干子序列的幾何形狀相似程度判斷其聯(lián)系是否緊密, 緊密程度越高其分布越接近理想點(diǎn)序列, 反之亦然, 以此保證PF上具有良好的分布性.

2.4 算法流程

本文以遺傳算法(genetic algorithm, GA)為基底, 分別將全局排序(global ranking, GR)、 灰色關(guān)聯(lián)分析(grey relation analysis, GRA)引入遺傳算法的框架中.

算法1NGR-MOEA.

輸入: 目標(biāo)個(gè)數(shù)M, 種群大小N, 最大迭代次數(shù)MaxGen; /*輸入目標(biāo)個(gè)數(shù)、 種群大小、 最大迭代次數(shù)*/

輸出: 新種群; /*輸出新的種群*/

步驟:

1)P=?,i=1;

2)P=Randominitiate(P);/*隨機(jī)初始化種群*/

4)Q=MatingSelection(P); /*交配選擇*/

5)Q=Variation(Q); /*交叉變異*/

6)R=P∪Q; /*將父代種群與子種群混合*/

7) ComputeFunctionValue(R)；

8) ComputeGlobalsortingValue(R)； /*計(jì)算每個(gè)解的全局排序值*/

9) ComputeGreyRelationDegree(R)； /*計(jì)算每個(gè)解的灰色關(guān)聯(lián)度*/

10) ComputeFitnessValue

fori=1∶size(newpopulation,1)

FitnessValue(i)=w1×GR(Xi)-w2×GRA(Xi)

end

[B,I]=sort(FitnessValue)； /*對(duì)每個(gè)解的適應(yīng)度評(píng)估值進(jìn)行排序*/

11) end while.

NGR-MOEA隨機(jī)產(chǎn)生初始種群P, 使|P|=N.每次迭代, NGR-MOEA應(yīng)用一些遺傳運(yùn)算符, 如在步驟4),5)的交配選擇[9]和交叉變異[10], 產(chǎn)生子種群Q.將P和Q混合成臨時(shí)種群R=Q∪P, 即|R|=2N.最后, 利用步驟7)～10)的環(huán)境選擇對(duì)混合種群進(jìn)行排序, 并選擇精英解進(jìn)入下一代.

在環(huán)境選擇中, 首先在步驟7)計(jì)算每個(gè)解的目標(biāo)函數(shù)值; 然后利用式(4)目標(biāo)函數(shù)進(jìn)行歸一化處理, 并利用式(3)在步驟8)計(jì)算每個(gè)解的全局排序值, 利用式(6)在步驟9)計(jì)算每個(gè)解的灰色關(guān)聯(lián)度; 最后將全局排序值與灰色關(guān)聯(lián)度進(jìn)行混合設(shè)計(jì)新的適應(yīng)度函數(shù), 計(jì)算每個(gè)解的適應(yīng)度函數(shù)值, 選擇精英個(gè)體, 直到達(dá)到終止條件, 算法停止.

3 仿真實(shí)驗(yàn)結(jié)果與討論

本文實(shí)驗(yàn)使用反世代距離評(píng)價(jià)指標(biāo)(inverted generational distance, IGD)[11]和空間評(píng)測(cè)方法(spacing metric, SM)[12]兩個(gè)質(zhì)量指標(biāo)對(duì)算法進(jìn)行性能評(píng)估. 實(shí)驗(yàn)中, 將NGR-MOEA與傳統(tǒng)多目標(biāo)進(jìn)化算法進(jìn)行比較, 從而驗(yàn)證NGR-MOEA的性能.

3.1 實(shí)驗(yàn)設(shè)計(jì)

3.1.1 測(cè)試問(wèn)題

采用多目標(biāo)優(yōu)化測(cè)試函數(shù)DTLZ[13]作為基礎(chǔ)實(shí)驗(yàn)比較. 為更突出算法的性能, 本文考慮了DTLZ2,DTLZ4,DTLZ5及DTLZ6 測(cè)試問(wèn)題. 這些測(cè)試問(wèn)題均具有線性、 混合(凸/凹)、 多模型、 脫節(jié)、 退化和尺度不一致等特點(diǎn), 可測(cè)試算法的不同性能.

3.1.2 質(zhì)量測(cè)量指標(biāo)

質(zhì)量指標(biāo)是評(píng)價(jià)算法性能的一個(gè)重要指標(biāo). 本文實(shí)驗(yàn)分別采用反世代距離和空間評(píng)測(cè)方法兩種質(zhì)量測(cè)量指標(biāo). 其中, IGD是應(yīng)用最廣泛的指標(biāo)之一, 可以同時(shí)評(píng)估算法的收斂性和多樣性, 其表示參考點(diǎn)到最近解的距離平均值. IGD值越小, 算法的綜合性能越好. IGD值計(jì)算公式為

(8)

其中P是算法求得的解集,P*是從PF上采集的一組均勻分布的參考點(diǎn), dis(x,y)表示參考集P*中的點(diǎn)x到解集P中的點(diǎn)y之間的歐氏距離.

SM描述了解向量的分布, 可衡量PF近似解集中個(gè)體在目標(biāo)空間的分布情況, 并通過(guò)與實(shí)際Pareto邊界的比較度量算法對(duì)非支配解的收斂程度. 其所度量的是每個(gè)解到其他解最小距離的標(biāo)準(zhǔn)差. 空間度量值越小, 說(shuō)明解集越均勻. SM計(jì)算公式為

(9)

3.2 仿真實(shí)驗(yàn)結(jié)果

為驗(yàn)證NGR-MOEA在高維多目標(biāo)優(yōu)化問(wèn)題上的求解性能, 將其與NSGA-Ⅱ,GR-MODE和SPEA2這3種目前最具代表性的MOEAs在10,12,15,20目標(biāo)的DTLZ測(cè)試函數(shù)集上進(jìn)行對(duì)比實(shí)驗(yàn). 選用可擴(kuò)展為任意目標(biāo)維數(shù)和自變量維數(shù)的通用測(cè)試函數(shù)DTLZ{2,4,5,6}.

設(shè)置種群規(guī)模N=100, 迭代次數(shù)為250. 為保證實(shí)驗(yàn)的公平性和科學(xué)性, 對(duì)比算法的控制參數(shù)設(shè)置均采用相應(yīng)原文獻(xiàn)中的推薦值, 且所有實(shí)驗(yàn)結(jié)果均為各種算法獨(dú)立運(yùn)行30次后對(duì)應(yīng)IGD 和SM的統(tǒng)計(jì)平均值, 不同算法的對(duì)比結(jié)果列于表1～表4.

表1 不同算法在DTLZ2中的IGD和SM值對(duì)比結(jié)果

表2 不同算法在DTLZ4中的IGD和SM值對(duì)比結(jié)果

由表1～表4可見(jiàn), NGR-MOEA算法的IGD和SM值在多數(shù)情況下優(yōu)于NSGA-Ⅱ,GR-MODE和SPEA2等算法, 這是因?yàn)镹GR-MOEA算法在比較個(gè)體之間的優(yōu)劣程度時(shí)從優(yōu)于目標(biāo)數(shù)目和優(yōu)于幅度兩個(gè)角度度量, 同時(shí)還考慮了每個(gè)個(gè)體形成的子序列與母序列所形成幾何曲線的關(guān)聯(lián)度. 因此, 所獲得的最優(yōu)解集更逼近理論P(yáng)areto前沿. 根據(jù)DTLZ{2,4,5,6}函數(shù)各自功能特性可見(jiàn)： NGR-MOEA在高維多目標(biāo)優(yōu)化過(guò)程中能獲得良好的收斂性能和分布性能, 且隨著目標(biāo)維數(shù)增多, GRA-MOEA的性能越好, 表明了NGR-MOEA具有相對(duì)較強(qiáng)的穩(wěn)定性, 適合于高維多目標(biāo)優(yōu)化問(wèn)題的求解.

表3 不同算法在DTLZ5中的IGD和SM值對(duì)比結(jié)果

表4 不同算法在DTLZ6中的IGD和SM值對(duì)比結(jié)果

綜上所述, 針對(duì)傳統(tǒng)高維多目標(biāo)優(yōu)化問(wèn)題解決方法存在解集收斂性與解集分布均勻性缺陷的問(wèn)題, 本文提出了一種新的基于全局排序求解高維多目標(biāo)優(yōu)化問(wèn)題算法, 該算法將個(gè)體目標(biāo)適應(yīng)度計(jì)算策略與灰色關(guān)聯(lián)策略相結(jié)合設(shè)計(jì)新的適應(yīng)度函數(shù), 從而解決了高維多目標(biāo)優(yōu)化問(wèn)題難以取得良好的收斂性和解集分布性的缺陷. 為驗(yàn)證算法的有效性, 將NGR-MOEA與NSGA-Ⅱ,SPEA2,GR-MODE三種算法進(jìn)行對(duì)比實(shí)驗(yàn), 實(shí)驗(yàn)結(jié)果表明, NGR-MOEA在10～20 維多目標(biāo)優(yōu)化問(wèn)題上的求解性能具有明顯優(yōu)勢(shì), 算法性能得到穩(wěn)步提高.