基于兩階段參考點(diǎn)三層選擇的多目標(biāo)優(yōu)化算法

徐立龍, 李二超

(蘭州理工大學(xué)電氣工程與信息工程學(xué)院, 蘭州 730050)

多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithms, MOEAs)已廣泛應(yīng)用于現(xiàn)實(shí)生活中, 如: 盲源分離[1]、流水車間調(diào)度[2]、物流配送[3]等, 但算法的運(yùn)行效率、收斂性、多樣性等方面的效果不佳; 因此, 研究者對(duì)多目標(biāo)進(jìn)化算法提出了各種改進(jìn)措施．針對(duì)NSGA-Ⅱ中的非支配排序存在大量解重復(fù)比較的情況, Zhang等[4]提出一種有效的非支配排序(effective non-dominated sorting, ENS)以提高運(yùn)算效率, 但隨著目標(biāo)維數(shù)的增加, 運(yùn)算效率會(huì)降低; Yuan等[5]提出基于θ占優(yōu)的進(jìn)化算法, 通過將解分配到分布均勻的參考點(diǎn)對(duì)應(yīng)的類中, 且僅比較同類中解的占優(yōu)關(guān)系, 從而增加了Pareto最優(yōu)解的選擇壓力, 并保證解的分布性, 該算法同時(shí)考慮分布性與收斂壓力, 但未考慮分類過程計(jì)算量大的問題,降低了運(yùn)算效率; Luo等[6]提出一種計(jì)算資源的分配更新策略來提高運(yùn)算效率, 但改進(jìn)較小的個(gè)體時(shí)會(huì)導(dǎo)致種群多樣性丟失; 韓紅艷[7]提出兩層PBI(penalty-based boundary intersection)聚類策略, 分別通過個(gè)體到權(quán)重向量的垂直距離和個(gè)體在權(quán)重向量上的投影距離解決多樣性和收斂性問題, 以聚類后每類中的優(yōu)秀個(gè)體為聚類中心, 距離聚類中心最近的個(gè)體重新聚為一類; Li等[8]將基于聚合函數(shù)分解和基于Pareto占優(yōu)的方法結(jié)合, 充分利用兩種方法的優(yōu)勢(shì), 權(quán)衡算法的收斂性和多樣性但未考慮聚類過程的計(jì)算復(fù)雜度; Zhou等[9]提出一種新的PBI聚合方法, 即利用每個(gè)解到超平面之間的垂直距離代替解在參考向量上的投影距離, 與傳統(tǒng)的PBI聚合方法相比,該算法收斂速度快,但是該算法聚類過程計(jì)算成本過大,運(yùn)算效率不高．本文在文獻(xiàn)[9]的基礎(chǔ)上, 提出一種基于兩階段參考點(diǎn)三層選擇的多目標(biāo)優(yōu)化算法(multi-objective evolutionary algorithm for two-stage reference point three-hierarchy selection, TT-MOEA)．

1 TT-MOEA算法

1.1 聚類

個(gè)體的目標(biāo)函數(shù)值f(X)距離所有參考向量中垂直距離最小的參考向量歸類于該參考向量, 可用基于懲罰邊界交叉[6,9]公式F(X)=di,1+θdi,2表示, 其中F(X)為個(gè)體的聚合函數(shù)值,di,1是個(gè)體在參考向量上的投影距離,di,2是個(gè)體到參考向量的垂直距離, 預(yù)設(shè)參數(shù)θ>0, 并用個(gè)體到超平面[9-10]的垂直距代替投影距離, 聚類原理如圖1所示．

轉(zhuǎn)換公式為F(X)=θdi,2-dL, 其中dL為個(gè)體到超平面的垂直距離, 為使F(X)取最小值, 須滿足

(1)

1.2 參考點(diǎn)的生成

1.3 兩階段策略

本文以代數(shù)的前一半與后一半分為前期與后期, 前期因設(shè)置的參考點(diǎn)少而形成少量的參考向量,此時(shí)聚類起到的多樣性作用不大,故前期以Pareto支配的快速收斂作用為主;后期的參考點(diǎn)較多,形成的參考向量會(huì)形成更多的聚類領(lǐng)域,聚類前首先對(duì)個(gè)體的目標(biāo)函數(shù)值進(jìn)行歸一化處理,使得參考向量均勻分布在截距為1的超平面上,并在每個(gè)聚類領(lǐng)域內(nèi)再進(jìn)行小生境選擇,在稀疏領(lǐng)域中添加個(gè)體, 從而增加種群的多樣性．

1.4 三層選擇策略

三層選擇思想如圖3所示．父代種群經(jīng)交叉變異產(chǎn)生子代種群, 將子父代種群合并, 經(jīng)ENS排序, 根據(jù)非支配等級(jí)將其分為3類, 若前L-1層的個(gè)體數(shù)為q, 未達(dá)到種群個(gè)體數(shù)N, 則要添加第L層的個(gè)體, 使種群個(gè)數(shù)大于等于N, 此層稱為臨界層．將大于L層的個(gè)體刪除, 選出大于種群個(gè)數(shù)的優(yōu)秀個(gè)體數(shù)U,此層主要是為了加速收斂．再將ENS選出的臨界層作為第2次選取種群, 對(duì)其進(jìn)行聚類操作,每一類個(gè)體求其PBI聚合函數(shù)值,將每類中最小聚合函數(shù)值的個(gè)體視為第1層F1, 依次類推有{F2,F3,…},原理如圖4所示．同理, 根據(jù)PBI依次選取種群并將其分為3類, 若前w-1層所選個(gè)體數(shù)目P<(U+q)-N, 則再添加第w層個(gè)體, 使P≥(U+q)-N, 此時(shí)將大于w層級(jí)的個(gè)體刪除．二次選出臨界層個(gè)體的數(shù)目為K, 綜合考慮收斂性與多樣性, 對(duì)PBI選出的K個(gè)個(gè)體使用小生境選擇, 選出N-(P+q)個(gè)優(yōu)秀個(gè)體, 主要為了增加多樣性, 最終使得下一代個(gè)體的數(shù)目等于初始種群個(gè)數(shù)．

2 測(cè)試函數(shù)與評(píng)價(jià)指標(biāo)

為驗(yàn)證TT-MOEA算法的性能, 選取T-MOEA(不含兩階段策略的本文算法)、NSGA-Ⅱ[12]、MOEA/D[13]、MOEA/D-TCH[14]、NSGA-Ⅲ[15]5類算法對(duì)測(cè)試函數(shù)DTLZ[16]與ZDT[17]進(jìn)行計(jì)算, 通過運(yùn)行時(shí)間與多種性能指標(biāo)來比較不同算法的計(jì)算效果．

2.1 測(cè)試函數(shù)及參數(shù)設(shè)置

ZDT1～ZDT3測(cè)試函數(shù)目標(biāo)之間相互沖突,即存在一增一減的關(guān)系．DTLZ2測(cè)試函數(shù)的目標(biāo)相關(guān)性如圖6所示．從圖6可以看出, 測(cè)試問題滿足Pareto最優(yōu)邊界時(shí), 對(duì)應(yīng)著屬于XM的所有xi=0.5, 可得g(XM)=0, 使得決策變量在同一范圍內(nèi)變化; 取x1=x2, 則表達(dá)式為f1(X)=cos2(x1π/2),f2(X)=0.5sin(x1π),f3(X)=sin(x1π/2)．DTLZ7測(cè)試函數(shù)的目標(biāo)相關(guān)性如圖7所示．從圖7可以看出, 滿足Pareto最優(yōu)邊界條件使XM=0時(shí),g(XM)=1, 取其特殊關(guān)系判斷, 即x1=x2, 表達(dá)式等價(jià)于f1(X)=f2(X)=x1,f3(X)=6-2f1(1+sin(3πf1))．

相關(guān)參數(shù)選取[9]: 交叉指數(shù)m=30, 變異指數(shù)mm=20, 變異概率Pm=1/V, 交叉概率PCR=1.0, 懲罰因子θ=5, 差分進(jìn)化參數(shù)F=0.5, 并設(shè)置兩階段參考點(diǎn)閾值為G/2代．求取參考點(diǎn)個(gè)數(shù)時(shí),第一階段設(shè)置兩目標(biāo)參數(shù)P=2, 三目標(biāo)參數(shù)P=4; 第二階段設(shè)置兩目標(biāo)參數(shù)P=N-1, 三目標(biāo)參數(shù)P=23, 計(jì)算出與種群個(gè)數(shù)相同的參考點(diǎn)．本文設(shè)置算法循環(huán)代數(shù)為250, 兩目標(biāo)種群個(gè)數(shù)為100, 三目標(biāo)種群個(gè)數(shù)為300, 決策變量數(shù)為V=M+9．

2.2 評(píng)價(jià)指標(biāo)

1) 運(yùn)行時(shí)間表示算法從初始化到程序運(yùn)行結(jié)束的總時(shí)間．

3 結(jié)果與討論

本文TT-MOEA算法與上述5類算法在標(biāo)準(zhǔn)測(cè)試函數(shù)上得到的評(píng)價(jià)指標(biāo)列于表1, 圖8為部分仿真結(jié)果．測(cè)試結(jié)果顯示: 1) 本文算法在ZDT3上運(yùn)行時(shí)間最短, 而在其他測(cè)試函數(shù)上MOEA/D-TCH算法效率較高; 同時(shí)在兩目標(biāo)上本文算法效率較高, 三目標(biāo)上MOEA/D-PBI算法效率較高; 總之, 在每個(gè)測(cè)試函數(shù)上本文算法運(yùn)行效率優(yōu)于T-MOEA算法, 表明聚類過程是使算法運(yùn)行效率降低的重要環(huán)節(jié)．NSGA-Ⅱ次之, NSGA-Ⅲ由于復(fù)雜的框架結(jié)構(gòu)導(dǎo)致運(yùn)算效率最慢．2) 由GD值可知, MOEA/D算法除ZDT2測(cè)試函數(shù)外均好于其他算法,結(jié)合仿真圖可以看出, 對(duì)于不連續(xù)函數(shù), MOEA/D算法只是個(gè)體的局部收斂性能好; NSGA-Ⅲ在不連續(xù)Pareto前沿與ZDT2上表現(xiàn)較好, 本文算法次之, NSGA-Ⅱ算法最差． 3) 由S值可知, 除在測(cè)試函數(shù)ZDT1上本文算法表現(xiàn)較好, 其他測(cè)試函數(shù)上T-MOEA算法表現(xiàn)最好, 本文算法次之．這是因?yàn)楸疚乃惴ㄇ捌诳紤]收斂性, 設(shè)置了較少的參考點(diǎn), 使聚類效果減弱,導(dǎo)致種群多樣性變差,使本文算法略弱于T-MOEA算法．4) 由IGD值可知, 除MOEA/D-PBI算法在測(cè)試函數(shù)ZDT1上表現(xiàn)較好,在其余測(cè)試函數(shù)上MOEA/DTCH算法表現(xiàn)最好, NSGA-Ⅲ算法次之; 在連續(xù)測(cè)試函數(shù)上, MOEA/D-PBI算法與MOEA/DTCH算法略好于本文算法;在Pareto前沿不連續(xù)測(cè)試函數(shù)上本文算法較好,NSGA-Ⅱ算法最差．由標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真結(jié)果與性能指標(biāo)表明,本文算法針對(duì)多目標(biāo)優(yōu)化,對(duì)于凸凹問題都適用,通過比較測(cè)試函數(shù)ZDT1與ZDT2的IGD值可知,整體優(yōu)化更適用于凹問題．

表1 不同算法求解標(biāo)準(zhǔn)測(cè)試函數(shù)所得的評(píng)價(jià)指標(biāo)和t值