楊景明，郝佳佳，孫 浩，魏之慧，李霞霞

（燕山大學(xué) 電氣工程學(xué)院，河北 秦皇島 066004）

1 引言

在科學(xué)研究和實(shí)際問(wèn)題中常常需要同時(shí)優(yōu)化多個(gè)相互沖突的目標(biāo)，這類問(wèn)題被稱為多目標(biāo)優(yōu)化問(wèn)題（multi-objective optimization problems，MOPs）［1］。而常規(guī)方法在求解目標(biāo)個(gè)數(shù)大于3的問(wèn)題（即MaOPs）時(shí)，種群的非支配解隨目標(biāo)數(shù)呈指數(shù)級(jí)增加，選擇壓力急劇下降，算法處于停滯狀態(tài)［2］；同時(shí)目標(biāo)空間增大，Pareto前沿更加復(fù)雜，算法的收斂性和分布性難以同時(shí)保持。

目前，研究人員已經(jīng)提出許多解決MaOPs的算法，大致可以分為3類：1）基于Pareto支配。這種方法需要引入新的機(jī)制來(lái)增強(qiáng)選擇壓力。例如，網(wǎng)格支配［3］通過(guò)自適應(yīng)網(wǎng)格結(jié)構(gòu)增加了選擇壓力，模糊支配［4］在Pareto支配的基礎(chǔ)上引入了模糊的概念來(lái)選解，此外還有ε-MOEA［5］、KnEA［6］等。這類算法的收斂性一般比較好，缺點(diǎn)是常常需要引入一些參數(shù)，參數(shù)的確定比較困難。2）基于分解。該方法將多目標(biāo)問(wèn)題分解為若干個(gè)單目標(biāo)子問(wèn)題，然后對(duì)這些子問(wèn)題進(jìn)行同步優(yōu)化和協(xié)同優(yōu)化。經(jīng)典的有MOEA／DD［7］、參考向量引導(dǎo)的進(jìn)化算法RVEA［8］等。這類算法的收斂和分布效果受權(quán)重分布影響，因而面對(duì)退化、不連續(xù)或真實(shí)PF面不規(guī)則的問(wèn)題時(shí)效果不佳。3）基于性能指標(biāo)。算法在環(huán)境選擇過(guò)程中采用個(gè)體的性能指標(biāo)值選擇個(gè)體。例如超體積算法Hype［9］、基于R2指標(biāo)的高維多目標(biāo)進(jìn)化算法MOMBI-II［10］等。這類算法的主要缺點(diǎn)是需要大量的計(jì)算。針對(duì)上述問(wèn)題，本文提出一種基于拐點(diǎn)和區(qū)域劃分的高維多目標(biāo)進(jìn)化算法（KnSP算法）。

2 背景描述

2.1 高維多目標(biāo)問(wèn)題描述

不失一般性，考慮如下MaOPs：

式中：X＝［x1，x2，…，xn］T為n維決策向量；S為x的可行域；fm（x）為第m個(gè)目標(biāo)函數(shù)，m＝1，…，M，M為目標(biāo)函數(shù)個(gè)數(shù)。

Pareto支配（定義）：設(shè)xA，xB∈Xf是式（1）所示的MaOPs的2個(gè)可行解，當(dāng)且僅當(dāng)對(duì)于任意i＝1，2，…，m，fi（xA）≤fi（xB）且存在j＝1，2，…，m，fj（xA）＜fj（xB）時(shí)，稱xA支配xB，記為xA?xB［11］。

Pareto最優(yōu)解（定義）：一個(gè)解x*∈Xf稱為Pareto最優(yōu)解，當(dāng)且僅當(dāng)滿足以下條件［11］：

Pareto最優(yōu)解集（定義）：Pareto最優(yōu)解集是所有Pareto最優(yōu)解的集合［11］：

Pareto前沿（定義）：Pareto最優(yōu)解集p*是所有Pareto最優(yōu)解對(duì)應(yīng)的目標(biāo)矢量組前沿面PF*［11］：

2.2 基于CHIM的拐點(diǎn)確定法

在許多實(shí)際問(wèn)題中，給定一個(gè)折衷解曲線或類似Pareto前沿曲面，一般會(huì)選擇曲面的“中間”點(diǎn)作為代表性點(diǎn)。因?yàn)樗cPareto曲面的極值點(diǎn)距離最遠(yuǎn)，在某種程度上可以代表良好的“折衷”，這種“凸起”被統(tǒng)稱為曲線的拐點(diǎn)。例如，在圖1中，Pareto曲線是AKB，選擇的拐點(diǎn)可以是K點(diǎn)，也可以是K點(diǎn)附近的點(diǎn)。

圖1 拐點(diǎn)K通常為Pareto前沿比較代表性的點(diǎn)Fig.1 The knee point K is usually a representative point in the Pareto front

確定拐點(diǎn)采用Das和Bechikh等［12］中提出的定義。理想點(diǎn)F*被定義為包含目標(biāo)的單個(gè)全局最小值的向量，則：

3 KnSP算法

3.1 確定拐點(diǎn)和第一次區(qū)域劃分

在MaOPs中，拐點(diǎn)是帕累托最優(yōu)解的子集，其中一個(gè)目標(biāo)的改進(jìn)將導(dǎo)致至少另一個(gè)目標(biāo)的嚴(yán)重退化，在沒(méi)有用戶指定或特定問(wèn)題的偏好時(shí)，帕累托前沿的拐點(diǎn)自然是首選。

3.1.1 確定拐點(diǎn)

在每一個(gè)非支配前沿中，極值超平面L的求解與CHIM類似。根據(jù)種群目標(biāo)空間的單極值點(diǎn)可以確定一個(gè)極值超平面L。計(jì)算個(gè)體到超平面L上的距離，若解到極值超平面的距離是最大值，那么該解被視為該非支配前沿的第一個(gè)拐點(diǎn)，再根據(jù)自適應(yīng)生成的鄰域，可以依次找出所有拐點(diǎn)。

3.1.2 第1次區(qū)域劃分

第1次區(qū)域劃分是將獲得的拐點(diǎn)作為中心點(diǎn)，自適應(yīng)的生成1個(gè)鄰域。而鄰域大小將嚴(yán)重影響拐點(diǎn)的識(shí)別結(jié)果。

根據(jù)文獻(xiàn)［6］來(lái)自適應(yīng)生成鄰域。假設(shè)第g代組合種群包含l個(gè)非支配前沿，每個(gè)前沿都有1組非支配解，用Fi表示，1≤i≤l。解的鄰域由1個(gè)維度為M的超立方體組成。第j（1≤i≤M）個(gè)維度上的鄰域大小被確定為Rj。

式中：rg－1為第（g－1）代Fi中解的鄰域個(gè)數(shù)與第j個(gè)目標(biāo)的跨度之比；M為目標(biāo)數(shù)；tg－1為拐點(diǎn)與第（g－1）代前沿Fi非支配解的數(shù)量比；0＜T＜1是控制解集Fi中拐點(diǎn)比率的閾值。式（6）確保當(dāng)tg－1遠(yuǎn)小于指定閾值T時(shí)rg將顯著減小，并且隨著tg－1的值變大，rg的減小將變得更慢。當(dāng)tg－1達(dá)到給定閾值T時(shí)，將保持不變。tg和rg分別初始化為0和1，即t0＝0和r0＝1。拐點(diǎn)確定和第一次區(qū)域劃分如算法1所示。

算法1 確定拐點(diǎn)和第1次區(qū)域劃分（Find_kneepoint（F，T，r，t）→［K，NB，r，t］）

3.2 第2次區(qū)域劃分

第2區(qū)域劃分是將3.1.2節(jié)中的鄰域通過(guò)角度分層進(jìn)行第2次區(qū)域劃分得到最終子區(qū)域，然后在每個(gè)子區(qū)域內(nèi)選擇1個(gè)最優(yōu)解作為候選解。

2目標(biāo)情況下的第2區(qū)域劃分如圖2所示，其中Z*為每1個(gè)鄰域內(nèi)的理想點(diǎn)（即每1維度上的最小點(diǎn)），向量V是坐標(biāo)系中的中間向量，S1、S2是第2次區(qū)域劃分后的最終子區(qū)域，α為區(qū)域劃分的角度，第2區(qū)域劃分過(guò)程如算法2所示。

圖2 2次區(qū)域劃分示意圖Fig.2 The second region division

假設(shè)某個(gè)鄰域內(nèi)有8個(gè)點(diǎn)A～H，進(jìn)行二次區(qū)域劃分時(shí)，首先需要進(jìn)行標(biāo)準(zhǔn)化，使得Z*成為原點(diǎn)。將中間向量V設(shè)置為V＝［1，1，…，1］，計(jì)算每個(gè)點(diǎn)與向量V之間的夾角β，取，將每個(gè)點(diǎn)劃分到所屬的子區(qū)域中。從圖2可以得出點(diǎn)A、B、G、H屬于子區(qū)域S1，而點(diǎn)C、D、E、F屬于子區(qū)域S2。高維情況下的劃分情況與此相同。二次區(qū)域劃分完成之后在每一個(gè)鄰域內(nèi)的每一個(gè)子區(qū)域中選擇距離超平面L最遠(yuǎn)的個(gè)體作為候選解。

算法2 第2次區(qū)域劃分（Second_region（NBH）→Φ）

3.3 環(huán)境選擇

環(huán)境選擇是為了從種群中選擇性能較好的解作為下一代的父代種群。由于在高維情況下的個(gè)體基本上都是非支配而拐點(diǎn)的個(gè)數(shù)一般會(huì)小于當(dāng)前種群，所以需要進(jìn)行兩次區(qū)域劃分來(lái)進(jìn)行種群選擇。環(huán)境選擇過(guò)程如算法3所示。

算法3 環(huán)境選擇（Environment_selection（F，K，N，NB，Φ）→Next）

若種群選擇后下1代種群的個(gè)數(shù)仍小于當(dāng)前種群規(guī)模，則計(jì)算候選解與剩余個(gè)體的角度，選擇角度最大的個(gè)體直到所選下1代種群的數(shù)量等于種群規(guī)模。若所選下1代種群的個(gè)數(shù)大于種群規(guī)模時(shí)采用角度去除法，計(jì)算候選解彼此之間的角度，選擇角度最小的2個(gè)點(diǎn)，然后比較這2個(gè)點(diǎn)與其它點(diǎn)之間的角度值，去除角度較小的個(gè)體。

需要注意的是，每次通過(guò)角度增加或去除一個(gè)個(gè)體之后都需要重新計(jì)算角度值再進(jìn)行下一個(gè)個(gè)體的增加或去除。

3.4 算法的總框架

下面算法為KnSP的總框架。

算法4 KnSP總框架（General Framework of KnSP）

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

為了公平比較幾種算法的性能，采用能夠使比較算法處于良好性能狀態(tài)的參數(shù)。

1）交叉和變異。交叉和變異采用SBX［14］和多項(xiàng)式變異［15］來(lái)產(chǎn)生后代種群。根據(jù)文獻(xiàn)［16］設(shè)置相應(yīng)的參數(shù)。

2）常規(guī)參數(shù)設(shè)置。對(duì)于每種算法中每種測(cè)試函數(shù)在同一設(shè)備上均獨(dú)立運(yùn)行20次，將迭代次數(shù)作為終止條件。WFG1的最大迭代數(shù)設(shè)置為1 000，WFG2為700，其他的設(shè)置為250代。

3）其它參數(shù)設(shè)置。GrEA中表示維度分割的參數(shù)div根據(jù)文獻(xiàn)［3］來(lái)設(shè)置。對(duì)于MOEA／DD，所有測(cè)試問(wèn)題的鄰域范圍都設(shè)置為N／10，使用Tchebycheff方法作為聚集函數(shù)，其中N為種群大小。

4）性能指標(biāo)。

超體積指標(biāo)（hyper volume，HV）［17］和反向世代距離（inverted generational distance，IGD）［18］是2個(gè)廣泛用于評(píng)估比較算法的性能指標(biāo)。這2個(gè)性能指標(biāo)不僅可以說(shuō)明算法的收斂性，也可以衡量算法的分布性。其具體設(shè)置根據(jù)文獻(xiàn)［17，18］設(shè)置。

4.2 實(shí)驗(yàn)結(jié)果分析

本文選取6個(gè)測(cè)試問(wèn)題WFG1、WFG2、WFG4、WFG5、WFG7和WFG8進(jìn)行試驗(yàn)對(duì)比。表1和表2分別列出了5種算法在測(cè)試函數(shù)上立運(yùn)行20次的IGD值和HV值的平均值和標(biāo)準(zhǔn)偏差值（括號(hào)內(nèi)數(shù)值），其中性能表現(xiàn)最好的用加粗字體標(biāo)出。

從表1中可以得出以下結(jié)論：首先，NSGA-III在WFG系列測(cè)試問(wèn)題上表現(xiàn)出良好的性能，尤其是在3個(gè)目標(biāo)和5個(gè)目標(biāo)的情況下，說(shuō)明NSGA-III處理低維多目標(biāo)問(wèn)題十分有效。對(duì)于具有8個(gè)目標(biāo)的WFG問(wèn)題，GrEA有2個(gè)表現(xiàn)最好，而KnSP有3個(gè)處于最優(yōu)位置，展現(xiàn)出一定的爭(zhēng)力。在10個(gè)目標(biāo)和15個(gè)目標(biāo)情況下，KnSP表現(xiàn)出較好的性能，其中10個(gè)目標(biāo)時(shí)IGD值最小的測(cè)試函數(shù)有4個(gè)，15個(gè)目標(biāo)均為最好。就IGD值而言，KnSP在整個(gè)WFG測(cè)試函數(shù)中的性能較好。這是因?yàn)镵nSP算法的主要選擇標(biāo)準(zhǔn)是距離超平面L的距離，而距離L越遠(yuǎn)，距離Pareto前沿的距離也就最近，而在目標(biāo)維數(shù)增多的過(guò)程中是用了2次區(qū)域劃分來(lái)縮小目標(biāo)空間，增加選擇壓力，所以種群的收斂性能在高維情況下表現(xiàn)良好。從表2中可以看出相比之下，NSGA-III和GrEA在WFG問(wèn)題上的HV具有3個(gè)以上目標(biāo)的情況下，其性能大體上比MOEA／DD和KnEA要好。NSGA-III和GrEA在所有具有3個(gè)以上目標(biāo)的WFG問(wèn)題上，尤其是WFG1中獲得了最佳HV或接近最佳HV。在5個(gè)比較算法中，KnSP在具有10個(gè)目標(biāo)上獲得了3個(gè)最佳的HV，而在15目標(biāo)的情況下基本上都是最優(yōu)或者接近最優(yōu)。這些結(jié)果表明，與其它算法相比，KnSP更適合于處理具有8個(gè)以上目標(biāo)的MaOPs。在本文考慮的30個(gè)WFG測(cè)試實(shí)例中，KnSP在12個(gè)測(cè)試實(shí)例上獲得了最佳的HV。總體而言，就HV而言，KnSP在WFG測(cè)試套件上的性能優(yōu)于其他比較算法。這是因?yàn)樵贙nSP算法中二次區(qū)域劃分時(shí)在每一個(gè)小區(qū)域內(nèi)都保留了一些分布性較好的個(gè)體，而且還采用了角度增加個(gè)體或者刪減個(gè)體的機(jī)制，將角度相差較大的個(gè)體進(jìn)行保留，對(duì)角度相差較小的個(gè)體進(jìn)行去除。

表1 5種算法在WFG測(cè)試函數(shù)上的IGD值統(tǒng)計(jì)表Tab.1 The IGD value of 5 algorithms on WFG test functions

表2 5種算法在WFG1～WFG8測(cè)試函數(shù)上的HV值統(tǒng)計(jì)表Tab.2 The HV value of 5 algorithms on WFG test functions

為更加直觀得到算法在測(cè)試函數(shù)上的表現(xiàn)結(jié)果，選取3目標(biāo)和15目標(biāo)的WFG1作為代表，測(cè)試結(jié)果如圖3所示。

圖3 5種算法在3目標(biāo)和15目標(biāo)下的WFG1測(cè)試結(jié)果圖Fig.3 The experimental results of 5 algorithms for WFG1 in 3 objectives and 15 objectives

圖3（a）為3目標(biāo)下的WFG1測(cè)試結(jié)果圖。圖3（a）可以很直觀地表示出解的優(yōu)劣。其中，解的收斂性表現(xiàn)最好的是NSGA-Ⅲ，其次為GrEA、MOEA／DD和KnEA，這3種算法的收斂性相差不大，而KnSP則表現(xiàn)較差。從分布性上來(lái)說(shuō)，NSGA-Ⅲ的解分布均較為均勻，而GrEA、MOEA／DD和KnEA相差不大，略遜于NSGA-Ⅲ，而KnSP則表現(xiàn)較差?？傮w來(lái)說(shuō)，NSGA-Ⅲ在3目標(biāo)情況下的WFG1中表現(xiàn)最好，而KnSP表現(xiàn)最差。

15目標(biāo)下的WFG1測(cè)試結(jié)果如圖3（b）所示。平行坐標(biāo)是一種常用的將高維數(shù)據(jù)可視化的方法，其橫軸表示目標(biāo)的維數(shù)，豎軸表示目標(biāo)值的大小，1個(gè)高維空間的點(diǎn)可以被表示為1條拐點(diǎn)在多條平行坐標(biāo)軸上的折線。由于豎軸反映對(duì)應(yīng)維度上的目標(biāo)值，所以根據(jù)目標(biāo)值的情況和測(cè)試函數(shù)的真實(shí)前沿可以大體判斷算法的收斂性和分布性的性能表現(xiàn)。一般來(lái)說(shuō)，豎軸上的目標(biāo)值距離真實(shí)前沿相同維度上的目標(biāo)值越遠(yuǎn)，收斂性越差；平行坐標(biāo)中，折線的重復(fù)程度越大，則分布性越差。

由圖3可知，MOEA／DD在第4～6目標(biāo)維度上的目標(biāo)值較小，GrEA在第1、2和4維度上數(shù)值較小，KnEA是第2和6維度上數(shù)值較小，NSGA-Ⅲ在第8、14和15維度上數(shù)值較小，而KnSP在第1～3維度上的目標(biāo)值較小。根據(jù)WFG1測(cè)試函數(shù)的特性可知目標(biāo)維數(shù)越大，目標(biāo)值的最大值也最大，而NSGA-Ⅲ在3個(gè)維數(shù)較高的目標(biāo)上數(shù)值很小，所以NSGA-Ⅲ在這些目標(biāo)維度上的收斂性就會(huì)很差，進(jìn)而在種群中的收斂性上就會(huì)表現(xiàn)較差，反之KnSP的收斂性相對(duì)較好。從折線的重復(fù)程度上來(lái)看，MOEA／DD和NSGA-Ⅲ的重復(fù)程度較大，其次是GrEA和KnEA，KnSP的重復(fù)程度最小，所以，MOEA／DD和NSGA-Ⅲ的分布性較差，KnSP的分布性最好。

5 結(jié)論

為了更好地平衡收斂性和分布性這兩個(gè)重要的性能指標(biāo)，本文提出一種基于拐點(diǎn)和區(qū)域劃分的KnSP算法。與4種算法的比較實(shí)驗(yàn)結(jié)果表明，提出的KnSP算法在分布性與收斂性性能指標(biāo)占優(yōu)的比例接近一半，尤其在目標(biāo)維數(shù)大于8時(shí)，基本上處于占優(yōu)位置，展現(xiàn)出極大的競(jìng)爭(zhēng)力。本文證明了使用拐點(diǎn)來(lái)增加MaOPs的選擇壓力的想法是可行的。進(jìn)一步開(kāi)展工作以開(kāi)發(fā)更有效和計(jì)算效率更高的算法來(lái)識(shí)別拐點(diǎn)是非常必要的。最后，算法性能仍有待在實(shí)際的MaOPs上進(jìn)行驗(yàn)證。