梁海娜，王宇嘉，林煒星，陳萬芬

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620)

0 引 言

多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithms, MOEAs)是一種結(jié)合生物進(jìn)化理論和隨機(jī)搜索機(jī)制來求解多目標(biāo)優(yōu)化問題(multi-objective optimization problem, MOP)的算法，被廣泛應(yīng)用于數(shù)據(jù)挖掘[1]、路徑規(guī)劃[2]、過程控制與操作優(yōu)化[3]、交通與物流系統(tǒng)優(yōu)化[4]等領(lǐng)域。

在實(shí)際應(yīng)用中，由于個(gè)人偏好或者實(shí)際生產(chǎn)需求，決策者可能只需要Pareto解集的部分解個(gè)體供其決策，不需要算法求解整個(gè)非支配解集。因此，在算法求解過程中，加入偏好信息協(xié)助算法搜索偏好解集，成為多目標(biāo)優(yōu)化領(lǐng)域的一大研究熱點(diǎn)。通過加入偏好信息，一方面提高了算法的搜索效率，減少對(duì)多余目標(biāo)空間的搜索；另一方面也減輕了決策者的選擇壓力。

目前，研究者已經(jīng)提出多種基于偏好信息的多目標(biāo)進(jìn)化算法。J. Molina等[5]提出了g-占優(yōu)的g-NSGAII算法，該算法可以緩解候選解支配選擇壓力，但偏好點(diǎn)所處目標(biāo)空間位置會(huì)影響算法的優(yōu)化性能；邱飛岳等[6]結(jié)合g-占優(yōu)和正負(fù)偏好信息，提出了雙極偏好支配方法，在種群個(gè)體間定義了一種更嚴(yán)格的支配關(guān)系，但是當(dāng)決策者提供的正偏好點(diǎn)距離前沿較遠(yuǎn)，而負(fù)偏好點(diǎn)距離前沿較近時(shí)，種群易陷入局部最優(yōu)；A.Jaszkiewicz等[7]采用了結(jié)合光速搜索的思想，沒有考慮負(fù)偏好信息，在解決高維優(yōu)化問題上性能不足； P.Korhonen等[8]提出了一種可視化互動(dòng)方法， 此種方法需要決策者進(jìn)行交互，增加了決策者的選擇壓力；文獻(xiàn)[9]結(jié)合Pareto支配策略，定義了一種r-dominance支配關(guān)系的r-NSGAII算法,當(dāng)參考點(diǎn)距離真實(shí)前沿較遠(yuǎn)時(shí)，偏好解集遠(yuǎn)離真實(shí)前沿面，收斂性較差；文獻(xiàn)[10]基于分解算法思想，結(jié)合權(quán)重迭代求解偏好多目標(biāo)優(yōu)化問題；鄭金華等[11]結(jié)合了個(gè)體間偏好角度思想，提出了一種基于角度的AD-NSGA-II算法；文獻(xiàn)[12]提出一種基于指標(biāo)的交互式算法，這些研究成果結(jié)合了偏好區(qū)域引導(dǎo)思想來求解偏好多目標(biāo)優(yōu)化問題。

上述研究一般采用單一偏好信息引導(dǎo)尋優(yōu)，沒有從多角度充分利用偏好信息指導(dǎo)算法迭代，導(dǎo)致算法易受偏好點(diǎn)位置影響或不能控制偏好解集范圍，給決策者帶來決策負(fù)擔(dān)。因此，本文結(jié)合偏好點(diǎn)和偏好向量這2種偏好信息，提出了一種兩階段混合引導(dǎo)的偏好多目標(biāo)優(yōu)化算法，采用NSGA-II算法[13]框架，分階段調(diào)整偏好引導(dǎo)方式，將g-占優(yōu)和偏好向量引導(dǎo)相結(jié)合，算法充分利用了偏好信息。實(shí)驗(yàn)結(jié)果表明，本文所提算法能夠使得種群快速收斂到偏好區(qū)域，獲得合適規(guī)模的偏好解集。

1 相關(guān)概念

1.1 多目標(biāo)優(yōu)化問題

多目標(biāo)優(yōu)化問題通?？梢员硎境扇缦伦钚』瘑栴}

minF(x)=min{f1(x),f2(x),…,fm(x)}，x∈Rn

(1)

(1)式中：x=(x1,x2,…,xn)為決策空間Rn中的一個(gè)決策變量；n為決策變量的維度；fi(x)為目標(biāo)空間Rm中的第i個(gè)目標(biāo)向量，其中，i=1,2,…,m，m為優(yōu)化問題目標(biāo)個(gè)數(shù)；gi(x)≤0對(duì)應(yīng)此類優(yōu)化問題的線性p個(gè)不等式約束條件；hj(x)=0則對(duì)應(yīng)優(yōu)化問題的q個(gè)線性等式約束條件。在求解多目標(biāo)優(yōu)化問題時(shí)，Pareto相關(guān)定義如下[14]。

1)Pareto支配。選取決策空間中任意2個(gè)決策變量xa,xb∈Rn，其中，xa=(xa1,xa2,…,xan)，xb=(xb1,xb2,…,xbn)，當(dāng)且僅當(dāng)滿足如下2個(gè)條件，定義xaPareto支配xb,記做xaxb。

①fi(xa)≤fi(xb),?i∈{1,2,…,m}；

②?j∈{1,2,…,m}，fj(xa)

2)Pareto最優(yōu)解。在決策空間中的xa∈Rn，表示MOP的一個(gè)可行解，當(dāng)滿足(2)式，則稱xa為此優(yōu)化問題的Pareto最優(yōu)解。

┐?x∈Rn,xxa

(2)

3)Pareto最優(yōu)解集。多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解集的定義為

P*={x∈Rn|┐?xd∈Rn,xdx}

(3)

1.2 g-支配概念

Molina等提出了g-dominance[5]策略，該策略根據(jù)決策者提供的偏好點(diǎn)，定義一種新的個(gè)體間支配關(guān)系，使得個(gè)體之間的支配關(guān)系變得緩和，目標(biāo)空間得到了偏好和非偏好區(qū)域的劃分，增強(qiáng)了傳統(tǒng)Pareto支配算法的種群個(gè)體支配排序選擇壓力。

若g為決策者偏好點(diǎn)，設(shè)y為目標(biāo)空間中任意一個(gè)目標(biāo)向量，定義flagg(y)為

(4)

根據(jù)flagg(y)的定義，對(duì)于2個(gè)目標(biāo)向量ya,yb∈Rm,如果下面條件之一成立，稱yag-支配yb。

①flagg(ya)≥flagg(yb)；

② 若flagg(ya)=flagg(yb)，需要滿足任意yai≤ybi(?i=1,…,m)，且至少存在一個(gè)i使得yai

1.3 快速非支配排序遺傳算法

快速非支配排序遺傳算法(NSGA-II)是多目標(biāo)進(jìn)化優(yōu)化領(lǐng)域應(yīng)用較廣泛的遺傳算法之一。該算法在傳統(tǒng)遺傳算法框架上引入精英選擇策略和快速非支配排序方法，具有求解效率高、優(yōu)化解集收斂性好的優(yōu)勢(shì)。因此，本文采用此算法框架加入偏好引導(dǎo)機(jī)制，求解偏好多目標(biāo)優(yōu)化問題。偏好信息表示如圖1所示，其中，p為偏好點(diǎn)，F(xiàn)1和F2是歸一化目標(biāo)函數(shù)值。

圖1 偏好信息表示示意圖Fig.1 Diagram of preference information representation

2 兩階段混合引導(dǎo)偏好多目標(biāo)算法

2.1 偏好信息表示

定義1(偏好點(diǎn)) 決策者對(duì)每個(gè)目標(biāo)的優(yōu)化期望值所構(gòu)成的目標(biāo)值集合為目標(biāo)空間的一個(gè)偏好點(diǎn)，通常記作p(fp1,fp2,…,fpm)。

定義2(個(gè)體偏好距離) 在目標(biāo)空間中，一般將經(jīng)過原點(diǎn)和偏好點(diǎn)的向量定義為偏好向量，目標(biāo)空間偏好區(qū)域劃分示意圖如圖2所示，其中，Op(原點(diǎn)O和p點(diǎn)的連線)即為偏好向量。

對(duì)于種群中的任意個(gè)體xj,j=1,2,…,N，N為種群規(guī)模，其在目標(biāo)空間中映射的目標(biāo)向量為yj，表示為

yj=(f1(xj),f2(xj),…,fm(xj))

(5)

將種群中任意個(gè)體xj對(duì)應(yīng)的目標(biāo)向量yj到偏好向量的垂直距離定義為個(gè)體xj的偏好距離，記做Dis(xj)，其計(jì)算方法表示為

j=1,2,…,N

(6)

根據(jù)(6)式，圖2中線段y1H的長(zhǎng)度即為種群個(gè)體x1的偏好距離。

圖2 目標(biāo)空間偏好區(qū)域劃分示意圖Fig.2 Diagram of objective space preference area division

定義3(偏好半徑) 為得到滿足決策者偏好合適范圍的偏好解集，設(shè)定偏好距離的上界限，定義其為偏好半徑，記作R。

2.2 動(dòng)態(tài)調(diào)整偏好區(qū)域界限策略

基于g-占優(yōu)引導(dǎo)方式算法優(yōu)化前期，候選解集中被偏好點(diǎn)Pareto支配的個(gè)體所占比例較大，且這些個(gè)體之間根據(jù)Pareto非支配進(jìn)行排序選擇，偏好收斂性不強(qiáng)。為提升算法初期種群偏好收斂速度，本文提出一種基于g-支配動(dòng)態(tài)調(diào)整偏好區(qū)域界限策略。

首先，根據(jù)g-占優(yōu)的定義可知，算法優(yōu)先選擇flagg值為1的個(gè)體，即在Pareto意義上支配偏好點(diǎn)和被偏好點(diǎn)支配的個(gè)體。為了更好地區(qū)分偏好區(qū)域內(nèi)的個(gè)體，挖掘種群潛在的偏好信息，指導(dǎo)種群朝著偏好區(qū)域進(jìn)化，本文將偏好區(qū)域做進(jìn)一步劃分，劃分規(guī)則表示為

(7)

此劃分規(guī)則將支配偏好點(diǎn)的個(gè)體定義其flagp值為1，而被偏好點(diǎn)支配的個(gè)體定義其flagp值為-1，其余個(gè)體定義其flagp為0。通過此種劃分規(guī)則，目標(biāo)空間區(qū)域被劃分為4個(gè)部分，見圖2。

然后，根據(jù)種群分布情況調(diào)整偏好界限，對(duì)采用g-占優(yōu)得到的候選種群P，通過以上偏好區(qū)域劃分規(guī)則，標(biāo)記個(gè)體的flagp值。選擇出flagp為-1的個(gè)體進(jìn)行臨時(shí)存檔，并記其個(gè)數(shù)為num，通過(8)式計(jì)算該檔案內(nèi)個(gè)體數(shù)占種群總體的比例ratio-1。當(dāng)該指標(biāo)滿足決策者指定范圍時(shí)，對(duì)檔案執(zhí)行(9)式計(jì)算偏好區(qū)域界限pnew。

(8)

pnew=(pnew1,pnew2,…,pnewm)

(9)

偏好區(qū)域界限動(dòng)態(tài)調(diào)整方法偽代碼如算法1所示。

算法1偏好界限動(dòng)態(tài)調(diào)整策略

INPUT：基于g-占優(yōu)得到的種群P,決策者偏好點(diǎn)

p(fp1,fp2,...fpm)，種群規(guī)模N；

OUTPUT：pnew，ratio-1；

1.flagp=zeros(N,1)//初始化種群個(gè)體flagp值；

2.for eachxj∈P, do

3.if all(fpi≤fiXj) then

4.flagpj←-1//被偏好點(diǎn)支配的個(gè)體flagp賦值為-1；

5.else if all(fpi≥fiXj) then

6.flagpj←1//支配偏好點(diǎn)的個(gè)體flagp賦值為1；

7.elseflagpj=0

8.end if

9.end for

10.flagpj為-1的個(gè)體數(shù)量記為num；

11.根據(jù)(8)式計(jì)算ratio-1；

12.根據(jù)(9)式計(jì)算pnew。

最后，根據(jù)計(jì)算所得偏好界限，定義位于界限之內(nèi)的個(gè)體偏好支配該界限之外的解，同時(shí)界限之內(nèi)的個(gè)體根據(jù)g-支配策略非支配排序，界限之外的個(gè)體以Pnew為偏好點(diǎn)采用g-支配排序策略，使得靠近偏好點(diǎn)邊界的候選解支配等級(jí)降低被舍棄，種群偏好收斂性能得到一定的提升，個(gè)體之間偏好區(qū)域界限支配策略偽代碼如算法2所示。

算法2偏好區(qū)域界限支配策略

OUTPUT：Palt；

1.對(duì)種群P執(zhí)行選擇、交叉、變異策略，得到子代種群P1；

2.P=P∪P1//種群合并

3.for eachxj∈P, do

4.if all(fiXj≤fPnewi) then

6.else

8.end if

9.end for

14 else

16.P=Palt

17.end if。

2.3 偏好向量引導(dǎo)策略

2.3.1 偏好向量的設(shè)定

多數(shù)研究成果中將偏好點(diǎn)和原點(diǎn)的連線作為偏好向量[15]，由于真實(shí)前沿和偏好點(diǎn)的位置關(guān)系未知，采用此種偏好向量為偏好信息載體，可能會(huì)引導(dǎo)算法朝著遠(yuǎn)離偏好區(qū)域進(jìn)化。另外，隨著算法迭代次數(shù)的增加，種群越來越能表征決策者的偏好信息，因此，本文根據(jù)種群進(jìn)化過程，提出一種動(dòng)態(tài)偏好向量的定義，首先計(jì)算當(dāng)前種群個(gè)體對(duì)應(yīng)的目標(biāo)向量和偏好點(diǎn)的歐氏距離,記做Distance(xj|p)，找出歐氏距離最小的解個(gè)體，記為xdirec，將其和偏好點(diǎn)的連線作為此時(shí)的偏好向量，計(jì)算方法表示為

i=1,2,…,m,j=1,2,…,N

(10)

(11)

2.3.2 偏好向量支配策略

決策者總是希望得到滿足偏好范圍的非支配解集，供其做出決策選擇。但通?；谄命c(diǎn)的引導(dǎo)方式不能控制解集偏好范圍，使得優(yōu)化結(jié)果得到過多非支配解，給最終決策帶來決策選擇壓力。為控制偏好解集規(guī)模，本文結(jié)合偏好向量和決策者提供的偏好半徑，對(duì)目標(biāo)空間進(jìn)行新的偏好區(qū)域劃分，同時(shí)對(duì)種群個(gè)體采取新的偏好支配排序方法，增強(qiáng)種群選擇壓力。根據(jù)個(gè)體的偏好距離和偏好半徑大小的關(guān)系，對(duì)目標(biāo)空間進(jìn)行相應(yīng)的偏好區(qū)域劃分，表示為

(12)

(12)式中：R表示偏好半徑，是決策者事先提供的定值；Dis(xj)為(6)式定義的個(gè)體xj的偏好距離。

根據(jù)(12)式，目標(biāo)空間被劃分為偏好區(qū)域和非偏好區(qū)域2部分。同時(shí)種群個(gè)體之間支配關(guān)系發(fā)生相應(yīng)的改變，假設(shè)種群中任意個(gè)體xa和xb，當(dāng)滿足以下任意一條件時(shí)，定義xa偏好占優(yōu)(Rd-dominance)xb。

1)xa和xb在同一個(gè)區(qū)域，xa在Pareto意義占優(yōu)xb;

2)xa屬于偏好區(qū)域，xb在非偏好區(qū)域。

2.4 混合偏好引導(dǎo)策略

算法通過g-占優(yōu)結(jié)合偏好界限動(dòng)態(tài)調(diào)整策略進(jìn)化到一定代數(shù)后，得到具有一定偏好收斂特性的進(jìn)化種群。后期為控制偏好解集范圍，結(jié)合g-占優(yōu)和偏好向量混合引導(dǎo)策略，同時(shí)增強(qiáng)候選解的選擇壓力。候選解之間混合偏好支配準(zhǔn)則如下。

1)flagg值為1的個(gè)體支配其他分區(qū)內(nèi)的個(gè)體，flagg值為1的個(gè)體之間采用Pareto非支配排序選擇，相同Pareto非支配等級(jí)個(gè)體則采用Rd-dominance支配策略。

2)flagg為-1和0的個(gè)體均按Pareto非支配排序，同一Pareto支配等級(jí)個(gè)體按照Rd-dominance支配原則排序。

根據(jù)以上支配規(guī)則，混合偏好引導(dǎo)策略偽碼如算法3所示。

算法3混合偏好引導(dǎo)種群個(gè)體支配選擇策略

INPUT：合并種群P,種群規(guī)模N，決策點(diǎn)偏好點(diǎn)p(fp1,fp2,…,fpm),定義2個(gè)空檔案集合Pflag=1和Pother，種群候選檔案Palt，

OUTPUT：Palt。

1.for eachxj∈P, do

2.if all(fiXj≤fPi) then

3.Pflag=1=Pflag=1∪{xj}//將位于偏好界限內(nèi)的個(gè)體存儲(chǔ)在Pflag=1中；

4.else

5.Pother=Pother∪{xj}//將在偏好界限外的個(gè)體存儲(chǔ)在Pother中；

6.end if

7.end for

8.for eachxj∈P, do

9.根據(jù)(11)式計(jì)算Distance(xj)；

10.end for

11.Xdirec=find(min(Distance(xj)) )//找出距離偏好點(diǎn)最近的個(gè)體；

12.ifNum(Pflag=1)≤Nthen//判斷Pflag=1檔案集中個(gè)體數(shù)量和N的大小關(guān)系；

13.Palt={Pflag=1}//將Pflag=1所有個(gè)體放入候選解檔案集中；

14.num2=N-Num(Pflag=1)

15.對(duì)Pother非支配排序，得到個(gè)體支配等級(jí)frontvalue；

16.逐級(jí)選取個(gè)體放入Palt中，同一支配等級(jí)計(jì)算其偏好距離，選擇不大于R的個(gè)體放入Palt中，若均在偏好區(qū)域內(nèi)，根據(jù)擁擠距離排序選擇，直到所選解個(gè)數(shù)為num2；

17.else

18.對(duì)Pflag=1非支配排序，得到個(gè)體支配等級(jí)frontvalue；

19.逐級(jí)選取個(gè)體放入Palt中，同一支配等級(jí)計(jì)算其偏好距離，選擇不大于R的個(gè)體，放入Palt中，若都在偏好區(qū)域內(nèi)，根據(jù)擁擠距離排序選擇，直到所選解個(gè)數(shù)為N；

20.end if

21.P=Palt。

混合偏好引導(dǎo)個(gè)體支配關(guān)系示意圖如圖3所示。

圖3 混合偏好引導(dǎo)個(gè)體支配關(guān)系示意圖Fig.3 Diagram of individual dominance relationship guided by hybrid preference

種群內(nèi)共有8個(gè)候選解，個(gè)體a4距離偏好點(diǎn)p最近，該個(gè)體和偏好點(diǎn)連線為偏好向量，根據(jù)混合偏好引導(dǎo)策略，此時(shí)的種群個(gè)體之間支配關(guān)系為a1=a2a3a4c1c2b1=b2；若采用g-占優(yōu)策略，種群之間的支配關(guān)系為a1=a2=a3a4b2=b1c1=c2；若單獨(dú)使用偏好向量，支配關(guān)系為a1=a2a3a4=c1c2b2=b1。對(duì)比發(fā)現(xiàn)采用本文所提混合支配策略能減輕候選解的選擇壓力，同時(shí)更能體現(xiàn)決策者的偏好。

2.5 算法流程

本文所提兩階段混合引導(dǎo)偏好多目標(biāo)優(yōu)化算法(TSMg-NSGAII)流程圖如圖4所示，其中，it為算法迭代次數(shù)。

圖4 算法流程圖Fig.4 Algorithm flowchart

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

將本文所提算法和基于偏好點(diǎn)引導(dǎo)方式的g-NSGAII算法、基于偏好區(qū)域引導(dǎo)的r-NSGAII算法進(jìn)行實(shí)驗(yàn)對(duì)比。根據(jù)文獻(xiàn)[9]，r-NSGAII算法設(shè)置各目標(biāo)權(quán)重為平均權(quán)重，非支配閾值δ取值為0.1，為了對(duì)比分析，本文偏好向量引導(dǎo)的R也設(shè)置為0.1；為防止過度使用偏好區(qū)域調(diào)整策略，丟失種群多樣性，本文所提算法中偏好收斂指標(biāo)γ設(shè)置為0.5；前期基于偏好點(diǎn)的引導(dǎo)方式中設(shè)置it為20。在3種算法遺傳操作算子設(shè)置上，選取模擬二進(jìn)制交叉方法和多項(xiàng)式變異，設(shè)置相同的交叉概率和變異概率，分別取0.99和0.1。

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

實(shí)驗(yàn)選取ZDT[16]系列的ZDT1、ZDT2、ZDT3和DTLZ[17]系列中的DTLZ2作為基準(zhǔn)測(cè)試函數(shù)。ZDT系列為兩目標(biāo)優(yōu)化問題，種群規(guī)模N為100，最大迭代次數(shù)設(shè)置為200。對(duì)于DTLZ2測(cè)試函數(shù)，本文選取的是有三目標(biāo)函數(shù)的DTLZ2，種群規(guī)模和最大迭代次數(shù)分別設(shè)置為150和300，同時(shí)為測(cè)試算法偏好點(diǎn)處于特殊位置的優(yōu)化性能，根據(jù)偏好點(diǎn)和基準(zhǔn)測(cè)試函數(shù)真實(shí)前沿位置關(guān)系，分別選取位于前沿上、不可行域和可行域這3種偏好點(diǎn)作對(duì)比試驗(yàn)分析，這些基準(zhǔn)函數(shù)參數(shù)的設(shè)置和偏好點(diǎn)選取如表1所示。

表1 基準(zhǔn)測(cè)試函數(shù)參數(shù)設(shè)置Tab.1 Parameter setting of test functions

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

本文選取世代距離(generational distance,GD)[18]指標(biāo)來評(píng)價(jià)算法的收斂性能，定義為

(13)

(13)式中，disi是種群中個(gè)體i到真實(shí)前沿的最小歐氏距離，此指標(biāo)用來表示優(yōu)化解集和真實(shí)前沿的接近程度，其值越小，表明該解集總體距離真實(shí)Pareto前沿越近，也即算法的收斂性能越好。

同時(shí)為評(píng)價(jià)算法的分布性能，采用SP指標(biāo)[19]，該指標(biāo)能反映一個(gè)數(shù)據(jù)集的離散程度，用來衡量一定范圍內(nèi)臨近解的差異大小，表征所得解集的分布性能，其數(shù)學(xué)表達(dá)式為

(14)

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

3.3.1 g-支配偏好區(qū)域界限調(diào)整策略優(yōu)化性能分析

g-支配偏好區(qū)域界限調(diào)整策略根據(jù)算法迭代過程中種群個(gè)體分布情況，動(dòng)態(tài)調(diào)整偏好區(qū)域界限，同時(shí)改變種群個(gè)體之間的偏好支配關(guān)系，增強(qiáng)g-支配的種群選擇壓力，偏好收斂性能得到提高。為測(cè)試該策略的有效性，該策略與對(duì)比算法g-NSGAII和r-NSGAII在ZDT1和ZDT2測(cè)試函數(shù)上得到的優(yōu)化結(jié)果如圖5所示。

從圖5a可以看出，在ZDT1上且偏好點(diǎn)位于可行域時(shí)，g-NSGAII和r-NSGAII得到的解集均靠近偏好點(diǎn)(0.8,0.8)附近，但和真實(shí)前沿的距離沒有本文算法近，即本文算法的前期收斂性更好。其中，基于r-占優(yōu)策略的r-NSGAII算法所得到的偏好解集偏向于距離偏好點(diǎn)附近，因此，在算法前期進(jìn)化種群會(huì)集中于偏好點(diǎn)附近。

圖5b是偏好點(diǎn)位于ZDT2真實(shí)前沿上得到的結(jié)果，可以看出，g-NSGAII算法在可行域搜索，進(jìn)化種群聚集于偏好點(diǎn)的一側(cè)，而r-NSGAII算法所得解集在距離偏好點(diǎn)較近的目標(biāo)空間區(qū)域搜索，本文算法采用動(dòng)態(tài)調(diào)整偏好區(qū)域界限策略，所得到的解集收斂性更好，達(dá)到了算法前期得到具有一定偏好收斂性進(jìn)化種群的目的。

圖6為圖5中對(duì)應(yīng)的3種算法分別以ZDT1和ZDT2為測(cè)試函數(shù)，其種群迭代過程中的GD值變化曲線，可以看出，基于r-占優(yōu)算法前期收斂速度較慢，且GD收斂曲線具有曲折性，算法收斂性能較差；本文算法得到的GD值最先達(dá)到最小值，并且始終優(yōu)于其他2種對(duì)比算法，因此，收斂特性優(yōu)于r-NSGAII和g-NSGAII算法。

圖5 算法在ZDT1、ZDT2上迭代20代所得偏好解集Fig.5 Preferred solutions on ZDT1 and ZDT2 run by the algorithms for 20 iterations

圖6 算法在ZDT1、ZDT2上迭代20代的GD進(jìn)化曲線Fig.6 Evolutionary curve of GD on ZDT1 and ZDT2 run by the algorithms for 20 iterations

3.3.2 算法整體優(yōu)化性能分析

3種算法在ZDT測(cè)試函數(shù)上運(yùn)行所得的偏好解集如圖7所示。圖7a為偏好點(diǎn)位于ZDT1真實(shí)前沿上，運(yùn)行3種對(duì)比算法所得的偏好解集，可以看出，g-NSGAII算法受此偏好點(diǎn)位置影響較大，解集收斂性較差；基于r-占優(yōu)算法能得到收斂性很好的偏好解集，但偏好范圍過于集中；而本文算法能得到收斂性能較好且滿足決策者偏好范圍的偏好解集。

圖7b為偏好點(diǎn)位于ZDT1可行域時(shí)的優(yōu)化結(jié)果，可以看出，r-占優(yōu)所得偏好解集整體距離前沿最遠(yuǎn)，本文所提算法和g-占優(yōu)算法所得偏好解收斂性能相當(dāng)。但基于g-占優(yōu)所得解集覆蓋了整個(gè)真實(shí)前沿，不利于決策者的最終決策選擇，而本文算法很好地控制了偏好解集規(guī)模，得到了滿足決策者要求的部分非支配解。

圖7c為偏好點(diǎn)位于ZDT2的不可行域得到的偏好解集，可以看出，本文算法和r-占優(yōu)算法所得偏好解集收斂性相當(dāng)，但本文算法得到的解集有著滿足決策者偏好的偏好解集范圍。而g-占優(yōu)得到的偏好解集過多，不便于決策者決策。

圖7d中測(cè)試函數(shù)為真實(shí)前沿非連續(xù)的ZDT3，且偏好點(diǎn)設(shè)置于其可行域得到的偏好解集，從圖7d可以看出，g-NSGAII和r-NSGAII算法得到的偏好解集為局部偏好解，且r-占優(yōu)所得解集的部分解沒有收斂到真實(shí)前沿附近，而是收斂于偏好點(diǎn)附近。而本文算法得到的偏好解集收斂于真實(shí)前沿附近，收斂性優(yōu)于g-占優(yōu)，且很好地控制了解集的偏好范圍，同時(shí)也表明本文算法能很好地解決具有不規(guī)則Pareto前沿的偏好優(yōu)化問題。

圖7 3種算法在ZDT測(cè)試函數(shù)上運(yùn)行所得偏好解集Fig.7 Preferred solutions on ZDT run by the three algorithms

在三目標(biāo)DTLZ2基準(zhǔn)測(cè)試函數(shù)上運(yùn)行3種算法所得的偏好解集如圖8所示。圖8a和圖8b為偏好點(diǎn)位于其真實(shí)前沿面上得到的解集正面和側(cè)面示意圖?？梢钥闯?，隨著目標(biāo)維數(shù)的增多，g-NSGAII在此基準(zhǔn)函數(shù)上所得偏好解集收斂性依舊很差； r-NSGAII和本文算法收斂性能相當(dāng)，但解集分布過于集中，缺乏偏好多樣性，不便于決策者最終決策；而本文算法得到了具有一定范圍的偏好解集。

圖8c和圖8d為當(dāng)偏好點(diǎn)位于非可行域時(shí)得到的優(yōu)化結(jié)果的正側(cè)面示意圖。g-占優(yōu)算法得到的解集不僅收斂性較差，偏好解集分布也過于分散； r-占優(yōu)算法得到的結(jié)果收斂于前沿附近，但解集聚集在一起；本文算法得到的偏好解集收斂于真實(shí)前沿上，且分布在指定的偏好區(qū)域內(nèi)。

另外，計(jì)算所得種群的GD指標(biāo)和SP指標(biāo)值，用來測(cè)試算法的收斂性能和分布性能。為了減少實(shí)驗(yàn)誤差，每種算法基于每個(gè)偏好點(diǎn)獨(dú)立運(yùn)行20次，取其平均值作為指標(biāo)最終計(jì)算結(jié)果。指標(biāo)計(jì)算結(jié)果如表2和表3所示。加下劃線的數(shù)值表示3種算法運(yùn)行結(jié)果對(duì)比中的最小指標(biāo)值，即該數(shù)值對(duì)應(yīng)的算法在該測(cè)試函數(shù)上的優(yōu)化性能最好。

通過表2和表3 可以看出，在幾次試驗(yàn)結(jié)果中，GD值最小時(shí)對(duì)應(yīng)的算法試驗(yàn)次數(shù)：g-NSGAI算法和r-NSGAII對(duì)應(yīng)的都是2次最優(yōu)，分別對(duì)應(yīng)偏好點(diǎn)在ZDT1的不可行域和可行域、偏好點(diǎn)在ZDT2的可行域和在DTLZ2的不可行域的對(duì)比實(shí)驗(yàn)上。g-占優(yōu)在ZDT1上表現(xiàn)最優(yōu)的2次實(shí)驗(yàn)和本文算法得到的指標(biāo)值相當(dāng)，這是因?yàn)間-占優(yōu)策略在解決簡(jiǎn)單二維優(yōu)化問題，且偏好點(diǎn)位于非特殊目標(biāo)空間位置上有著良好的收斂性能。r-占優(yōu)在DTLZ2上表現(xiàn)最優(yōu)的2次實(shí)驗(yàn)和本文算法所得指標(biāo)值也相當(dāng)，這是因?yàn)閞-占優(yōu)在解決三維優(yōu)化問題上較g-占優(yōu)收斂性能更好，且偏好點(diǎn)位于前沿上，能更快引導(dǎo)算法收斂到前沿區(qū)域。而本文算法的大多數(shù)實(shí)驗(yàn)結(jié)果最優(yōu)，表明本文算法不受偏好點(diǎn)位置影響，并且針對(duì)不同Pareto前沿形狀測(cè)試問題，都有著良好的偏好收斂性能。在表2中， 對(duì)應(yīng)SP值最優(yōu)的算法實(shí)驗(yàn)次數(shù)中，本文算法也占了大多數(shù)。因此，本文算法有著較好的收斂性和分布性能。

圖8 3種算法在三目標(biāo)DTLZ2 測(cè)試函數(shù)上運(yùn)行所得偏好解集Fig.8 Preferred solutions on three-objectives DTLTZ2 run by the three algorithms

表2 3種算法在測(cè)試函數(shù)上分別運(yùn)行20次GD計(jì)算結(jié)果

表3 3種算法在測(cè)試函數(shù)上運(yùn)行20次SP計(jì)算結(jié)果Tab.3 Calculation results of SP obtained by running the three algorithms on test functions for 20 times

為分析本文算法收斂速度的情況，3種算法在測(cè)試函數(shù)上的GD進(jìn)化曲線如圖9所示。

圖9a中，在有著非連續(xù)前沿的ZDT3上，當(dāng)偏好點(diǎn)位于可行域時(shí)，算法前期本文加入動(dòng)態(tài)偏好界限調(diào)整策略，GD指標(biāo)優(yōu)于g-占優(yōu)策略，r-占優(yōu)對(duì)此種優(yōu)化問題較為敏感，前期收斂速度較慢，最終收斂性能稍差于本文算法。圖9b中，偏好點(diǎn)位于DTLZ2前沿上，可以看出 r-占優(yōu)在解決三維目標(biāo)優(yōu)化問題上能快速收斂。隨著目標(biāo)函數(shù)的增多，g-占優(yōu)策略引導(dǎo)的種群中非支配解較多，選擇壓力增大，收斂速度較為緩慢。而本文算法前期收斂速度優(yōu)于g-占優(yōu)，后期收斂速度超過r-占優(yōu)策略，最終收斂性能最優(yōu)。

圖9 3種算法在測(cè)試函數(shù)上的GD進(jìn)化曲線Fig.9 GD evolution curve of three algorithms on test functions

4 結(jié) 論

本文提出了一種兩階段混合引導(dǎo)的偏好多目標(biāo)優(yōu)化算法，算法前期采用基于g-支配進(jìn)化策略，結(jié)合偏好區(qū)域界限動(dòng)態(tài)調(diào)整策略，進(jìn)化到指定代數(shù)，獲得偏好收斂性較好的候選種群，減少對(duì)不必要目標(biāo)空間的搜索代價(jià)；后期結(jié)合決策者給出的偏好半徑，采用偏好向量引導(dǎo)機(jī)制，控制偏好解集規(guī)模。通過對(duì)算法進(jìn)行實(shí)驗(yàn)比較，結(jié)果表明，本文算法所得偏好解集不受偏好點(diǎn)具體位置影響，同時(shí)能控制偏好解集的規(guī)模，得到收斂性和分布性良好的偏好解集，便于決策者的最終決策。