傅紅宇

(重慶郵電大學(xué) 自動(dòng)化學(xué)院，重慶 400065)

0 引言

目前，多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem，MOP)已出現(xiàn)在眾多工程領(lǐng)域，與傳統(tǒng)單目標(biāo)優(yōu)化問題不同，MOP中存在多個(gè)相互沖突的目標(biāo)，如何獲得所有目標(biāo)的最優(yōu)解，一直是學(xué)術(shù)領(lǐng)域和工程領(lǐng)域關(guān)注的焦點(diǎn)[1]。自1985年Scahffer[2]首次提出求解MOP的算法——基于矢量評(píng)價(jià)遺傳算法 (Vector Evaluated Genetic Algorithm，VEGA)以來，眾多的多目標(biāo)優(yōu)化算法也相繼被提出。

分布估計(jì)算法(Estimation of Distribution Algorithm，EDA)是眾多優(yōu)化算法中的一種[3]，因其亮眼的表現(xiàn)，也被應(yīng)用于MOP[4]。與傳統(tǒng)的優(yōu)化算法相比，EDA沒有交叉和變異操作，而是通過提取全局統(tǒng)計(jì)信息來建立概率分布模型，然后采樣生成新的解決方案。

在一定的平滑情況下，根據(jù)Karush-Kuhn-Tucker條件，連續(xù)MOP的中帕累托解集PS是一個(gè)(m-1)維的分段連續(xù)的流形[5]，其中m為目標(biāo)函數(shù)的個(gè)數(shù)。基于此，Zhang等[5]于2008年提出基于規(guī)則模型的多目標(biāo)分布估計(jì)算法(Regularity Model-based Multio-bjective Estimation of Distribution Algorithm，RM-MEDA)來解決MOP。在RM-MEDA中，采用LPCA算法建立K個(gè)概率模型來分別描述子種群的分布信息，然后采樣生成新個(gè)體。同時(shí)，RM-MEDA也存在以下不足：① 該算法的全局搜索能力較弱，從而影響了算法的收斂速度；② 概率模型的準(zhǔn)確性依賴于聚類數(shù)目K值，具體問題的K值是不盡相同的，預(yù)設(shè)的K值過大或過小，都將影響概率模型的準(zhǔn)確性，從而影響算法的性能。

針對(duì)RM-MEDA全局搜索能力較弱的問題，許多學(xué)者通過引入全局搜索能力強(qiáng)的多目標(biāo)優(yōu)化算法與之結(jié)合，在一定程度上提高了算法的性能。王劍文[6]通過判斷種群是否收斂來自適應(yīng)地選擇遺傳操作或者建模采樣操作來生成下一代種群，提高了算法的收斂性。向健[7]將差分變異算子與RM-MEDA相結(jié)合，混合產(chǎn)生新的個(gè)體，有效提高了全局搜索和局部搜索能力。2019年王惠君[8]在RM-MEDA的基礎(chǔ)上，與另一種基于逆模型的連續(xù)多目標(biāo)分布估計(jì)算法相結(jié)合，自適應(yīng)地通過2種算法生成新個(gè)體，在一定程度上提高了算法的整體性能和解的分布性。

為了降低預(yù)設(shè)K值對(duì)算法性能的影響，當(dāng)預(yù)設(shè)的K值大于實(shí)際情況時(shí)，Wang等[9]提出了一種去冗余聚類算子(RRCO)來修正K值，以此在進(jìn)化過程中建立更精確的模型，提高了算法的收斂能力。當(dāng)預(yù)設(shè)的K值小于實(shí)際情況時(shí)，無法建立正確的概率模型，從而降低算法的性能，故Shi等[10]提出了去聚類操作，同時(shí)結(jié)合全變量高斯模型，提高了算法的整體性能。不同問題的PS所構(gòu)成的流形結(jié)構(gòu)不同，故所需的K值是不盡相同的，如何根據(jù)實(shí)際問題自動(dòng)確定K值是研究的重要內(nèi)容。

基于以上分析，本文提出了一種基于近鄰傳播(Affinity Propagation，AP)的多目標(biāo)分布估計(jì)算法(AP-RM-MEDA)。針對(duì)RM-MEDA中預(yù)設(shè)的K值可能與實(shí)際不符從而導(dǎo)致無法建立準(zhǔn)確的概率模型的情況，引入了AP算法來自動(dòng)確定種群的聚類個(gè)數(shù)，從而避免人為設(shè)置K值的不確定性；考慮到迭代后期種群的數(shù)據(jù)信息逐漸趨同，提出了一種聚類數(shù)目重用策略，根據(jù)重用策略來判斷是否進(jìn)行聚類操作或重用之前的聚類結(jié)果，在一定程度上減小了聚類操作所帶來的計(jì)算開銷；針對(duì)RM-MED全局搜索能力較弱的問題，除根據(jù)概率模型采樣生成新個(gè)體外，還將混合差分變異算子產(chǎn)生部分新的個(gè)體，提高了算法的整體性能。

1 問題描述

一個(gè)MOP通常由N個(gè)決策變量、M個(gè)目標(biāo)和若干約束條件組成[11]，表示如下：

minF(x)=(f1(x),f2(x),…,fM(x))T，

(1)

s.t.x∈Ω

gi(x)≤0;i=1,2,…,p，

(2)

hj(x)=0;j=1,2,…,q，

(3)

式中，x=(x1,x2,…,xM)為M個(gè)N維決策變量形成的變量集；fi(x):Rn→R,i=(1,2,…,M)為第i個(gè)目標(biāo)函數(shù)；F(x)為M個(gè)目標(biāo)函數(shù)組成的目標(biāo)向量集。式(2)為p個(gè)不等式約束條件；式(3)為q個(gè)等式約束條件。

大多數(shù)情況下，各目標(biāo)函數(shù)之間是相互沖突的，同時(shí)使得所有的目標(biāo)函數(shù)達(dá)到最優(yōu)是不太容易實(shí)現(xiàn)的，故需要尋得一組均衡解集[12]，即Pareto解集，使得目標(biāo)函數(shù)在滿足給定約束條件的情況下盡可能達(dá)到最優(yōu)。

2 AP-RM-MEDA算法

在RM-MEDA算法中，按照預(yù)設(shè)值，將種群分為K類，并通過PCA算法建立相應(yīng)的概率模型。但是對(duì)于不同的問題，預(yù)設(shè)的K值并不一定符合實(shí)際問題。如果K值設(shè)置得過大，對(duì)于實(shí)際問題的Pareto前沿則顯得冗余；如果K值設(shè)置得過小，則不能覆蓋實(shí)際的Pareto前沿，從而無法準(zhǔn)確地刻畫種群的分布。因此，如何設(shè)定合理的K值是一個(gè)比較困難的問題。

本文提出的一種AP-RM-MEDA，根據(jù)具體的種群數(shù)據(jù)信息對(duì)種群進(jìn)行聚類，自動(dòng)確定了種群的聚類數(shù)目，從而避免了人為設(shè)置K值的不確定性。

2.1 AP聚類

AP算法是Frey等[13]于2007年提出的一種聚類算法。與其他經(jīng)典聚類算法不同的是，該算法不需要指定聚類數(shù)目[14]和初始聚類中心，而是以數(shù)據(jù)點(diǎn)集合的相似度矩陣作為輸入，將所有的數(shù)據(jù)點(diǎn)作為潛在的聚類中心，通過傳遞、交換數(shù)據(jù)點(diǎn)之間的信息來確定聚類中心，從而得到聚類結(jié)果。

在AP算法中，傳遞的信息參數(shù)包括吸引度(Responsibility)和歸屬度(Availability)2種。吸引度r(i,k)代表的是，考慮樣本點(diǎn)xi對(duì)其他候選類中心點(diǎn)支持程度的情況，數(shù)據(jù)點(diǎn)xk適合作為xi類中心點(diǎn)的程度。歸屬度a(i,k)代表的是，考慮其他數(shù)據(jù)點(diǎn)對(duì)xk的支持度的同時(shí)，樣本點(diǎn)xi選擇xk作為其類中心點(diǎn)的適合程度。通過對(duì)歸屬度和吸引度的計(jì)算更新，當(dāng)二者的和穩(wěn)定不變時(shí)，得到聚類結(jié)果，計(jì)算步驟如下：

① 設(shè)置吸引度和歸屬度的初始值：r(i,k)，a(i,k)均為零。

② 根據(jù)式(4)對(duì)吸引度進(jìn)行計(jì)算更新：

(4)

式中，s(i,k)表示樣本點(diǎn)xi和數(shù)據(jù)點(diǎn)xk之間的相似度，吸引度r(i,k)的更新使得所有數(shù)據(jù)點(diǎn)都能成為候選類中心點(diǎn)。

(1)更新歸屬度

(5)

歸屬度a(i,k)的更新將確定每個(gè)候選類中心點(diǎn)是否是一個(gè)好的類中心點(diǎn)。式中，r(k,k)表示數(shù)據(jù)點(diǎn)xk的自我吸引度。

(2)自我歸屬度a(k,k)更新

(6)

式(6)反映了基于其他數(shù)據(jù)點(diǎn)對(duì)候選點(diǎn)xk的支持，數(shù)據(jù)點(diǎn)xk成為類中心點(diǎn)的適合程度。

(3)得到類中心點(diǎn)

對(duì)吸引度和歸屬度進(jìn)行多次計(jì)算更新后，當(dāng)r(i,k)+a(i,k)連續(xù)多次取得最大值k不變時(shí)，則表明xk成為當(dāng)前樣本點(diǎn)xi的類中心點(diǎn)。若i=k，表明xi為當(dāng)前類的類中心點(diǎn)；若i≠k，表明xi屬于xk代表的類。

2.2 聚類數(shù)目重用策略

為了減小AP聚類操作帶來的計(jì)算量，在不過多損失聚類結(jié)果準(zhǔn)確度的前提下，在提出的AP-RM-MEDA算法中，考慮重用聚類數(shù)目K值。即如果連續(xù)L代的聚類結(jié)果都保持不變，表明相鄰種群的個(gè)體組成差異較小，種群分布信息類似，則直接使用當(dāng)代聚類數(shù)目作為后續(xù)種群的聚類數(shù)目。具體的實(shí)現(xiàn)過程如下：

① 保存歷代AP聚類結(jié)果K值。

② 判斷連續(xù)L代的K值是否改變，若保持不變則將該值作為當(dāng)前及后續(xù)進(jìn)化的聚類數(shù)目。

從上述可以看出，該重用機(jī)制本身并沒有帶來額外的計(jì)算量。通過后續(xù)實(shí)驗(yàn)發(fā)現(xiàn)，在迭代次數(shù)較大的情況下，尤其在算法進(jìn)化的后期，每代AP聚類結(jié)果變化率很小，故這種重用機(jī)制在沒有過多影響算法的性能下能較好地減小計(jì)算開銷。

2.3 混合算子

在RM-MEDA中，執(zhí)行聚類操作后通過LPCA對(duì)每一類群體建立對(duì)應(yīng)的概率模型，高斯采樣生成新的種群。這種建模操作屬于宏觀操作，有利于開采種群的統(tǒng)計(jì)信息，充分體現(xiàn)了解集在決策空間的分布性，但忽略了個(gè)體的特征，不利于勘探搜索空間的不同區(qū)域。故考慮引入簡(jiǎn)單高效的差分變異算子進(jìn)行搜索[15]，利用個(gè)體的信息可以增強(qiáng)算法的性能。由此，通過建模采樣和差分變異2種算子混合產(chǎn)生新解，有利于提高RM-MEDA的求解能力。

采用差分變異算子產(chǎn)生新解的過程如下：聚類操作之后，從每類當(dāng)中隨機(jī)選擇2個(gè)個(gè)體，組成全局子種群I。然后，隨機(jī)從全局子種群中選擇2個(gè)個(gè)體作為父?jìng)€(gè)體xr1，xr2，采用差分進(jìn)化算子產(chǎn)生新解：

x′i=xr+u×(xr1-xr2)+F×(xr1-xr2)，

(7)

式中，xr是從當(dāng)前種群中隨機(jī)選擇的個(gè)體；u為0～1的隨機(jī)數(shù)；xr1，xr2是從全局子種群I中隨機(jī)選擇的互不相同的個(gè)體；F為變異因子的縮放參數(shù)。

2.4 AP-RM-MEDA算法步驟

根據(jù)2.2節(jié)中提出的聚類數(shù)目重用策略判斷是否進(jìn)行AP聚類操作，然后根據(jù)其聚類結(jié)果或重用聚類結(jié)果分簇建立相應(yīng)的概率模型，其建模步驟如下：

(8)

式中，Xi為種群第k簇決策向量的集合；n為每簇所包含的個(gè)體數(shù)量。

② 每簇的協(xié)方差矩陣D為：

(9)

③ 根據(jù)協(xié)方差矩陣計(jì)算每簇個(gè)體的特征值λi及特征向量a，并根據(jù)特征值降序排列，選擇前(m-1)個(gè)特征向量作為主向量，且由主向量組成向量矩陣A。

④ 將每簇的個(gè)體都按照主向量方向進(jìn)行投影，計(jì)算每簇子種群的概率矩陣B：

(10)

對(duì)每簇生成的(m-1)個(gè)主成分概率模型采樣生成新的個(gè)體向量，同時(shí)為了使個(gè)體更加均勻地分布在非支配解集周圍，疊加一個(gè)均值為0的噪聲向量ε：

x′=x+ε，

(11)

式中，x′為新產(chǎn)生的個(gè)體；x為采樣得到的個(gè)體向量。

AP-RM-MRDA算法的完整步驟如下所示。

輸入：種群規(guī)模NX，決策變量維度DX，最大進(jìn)化代數(shù)MaxIter，決策變量的最大值XUpp及最小值XLow。

輸出：算法最終得到的新種群PopX(t)及其目標(biāo)函數(shù)值PopF(t)。

(1)種群的初始化：隨機(jī)生成初始種群PopX(0)，并計(jì)算其目標(biāo)函數(shù)值PopF(0)。

(2)判斷算法是否滿足停止條件：若t>MaxIter，結(jié)束算法并輸出結(jié)果；否則執(zhí)行步驟(3)。

(3)根據(jù)2.2節(jié)聚類數(shù)目重用策略判斷是否執(zhí)行AP聚類操作，若不滿足條件，根據(jù)2.1節(jié)執(zhí)行AP聚類操作，輸出聚類結(jié)果，執(zhí)行步驟(4)；若滿足條件，則直接重用上一代聚類結(jié)果，執(zhí)行步驟(4)。

(4)通過建模采樣方式和差分變異算子共同生成新個(gè)體：

① 根據(jù)步驟(3)的聚類結(jié)果，根據(jù)式(8)～式(10)分簇建立對(duì)應(yīng)的概率模型，對(duì)概率矩陣B按式(11)采樣生成新的子種群Pk；

② 從每類子種群中隨機(jī)選擇一個(gè)個(gè)體組成全局子種群I，并從I中隨機(jī)選擇父?jìng)€(gè)體，通過差分變異算子式(7)生成新的子種群Q，并計(jì)算其目標(biāo)函數(shù)值。

(5)環(huán)境選擇：采用NSGA-Ⅱ非支配排序選擇，從P∪Q∪PopX(t)中選擇NX個(gè)優(yōu)秀個(gè)體作為下一代種群PopX(t+1)。

(6)t=t+1，跳轉(zhuǎn)到步驟(2)。

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

本文選擇RM-MEDA[5]、基于差分進(jìn)化采樣(Differential Evolution Sampling，DES)的多目標(biāo)分布估計(jì)算法DES-RM-MEDA[16]、基于規(guī)則模型的無聚類多目標(biāo)分布估計(jì)算法FRM-MEDA[10]作為對(duì)比算法來測(cè)試AP-RM-MEDA算法的性能。由于本算法是基于RM-MEDA改進(jìn)的，與之對(duì)比將突顯所提算法的性能。與RM-MEDA采用高斯采樣方法不同，DES-RM-MEDA將決策變量中的個(gè)體映射到隱空間中，然后采用差分變異算子進(jìn)行變異操作，再映射回原空間中，由此避免對(duì)概率模型進(jìn)行擴(kuò)展。FRM-MEDA通過去聚類操作來消除聚類數(shù)目K值對(duì)算法的影響，同時(shí)引入全變量高斯模型來彌補(bǔ)去聚類操作對(duì)算法多樣性的影響，從而保持了算法的良好性能。

3.1 多目標(biāo)算法的評(píng)價(jià)指標(biāo)

為了更直觀、準(zhǔn)確地體現(xiàn)以上4種算法的性能，本文選擇世代距離(Generational Distance，GD)[17]和反世代距離(Inverted Generational Distance，IGD)[18]作為算法性能評(píng)價(jià)指標(biāo)，具體如下：

① GD：該指標(biāo)通過計(jì)算算法尋得的Pareto解集到真實(shí)Pareto前沿上的平均距離，定量地評(píng)價(jià)了算法的收斂性，其值越小說明算法求得的最優(yōu)解集越逼近真實(shí)Pareto前沿。計(jì)算表達(dá)式為：

(12)

式中，d(x,p)表示個(gè)體xi到真實(shí)Pareto前沿的歐氏距離；|P*|表示算法尋得的Pareto解集中解的個(gè)數(shù)。

② IGD：該指標(biāo)為綜合性指標(biāo)，通過計(jì)算真實(shí)Pareto前沿到算法得到的Pareto解集上的平均距離，其值越小越突出解的多樣性和算法的收斂性。計(jì)算表達(dá)式為：

(13)

式中，|P|表示真實(shí)Pareto前沿中的參考點(diǎn)個(gè)數(shù)。

3.2 參數(shù)設(shè)置

在本文的實(shí)驗(yàn)中，算法的決策變量維度DX設(shè)為30，RM-MEDA，DES-RM-MEDA兩種算法的聚類數(shù)目K值均設(shè)為5，而FRM-MEDA的K值為1。在RM-MEDA中，模型的縮放比例為0.25。DES-RM-MEDA和ADC-RM-MEDA中變異算子中的縮放因子F均設(shè)為0.4。

AP-RM-MEDA中，在執(zhí)行混合算子產(chǎn)生新種群時(shí)，需要設(shè)置一個(gè)參數(shù)H來設(shè)置2種算子產(chǎn)生新個(gè)體的比例，由于差分變異算子利用了個(gè)體的信息，可以增加種群的多樣性，但是在進(jìn)化后期產(chǎn)生有效解的概率不大，所以引入迭代次數(shù)以控制該值，即：

H=0.2-0.1×iter/MaxIter，

(14)

式中，iter為當(dāng)前迭代次數(shù)；MaxIter為最大迭代次數(shù)。

本文將以上4種算法利用文獻(xiàn)[5]中的測(cè)試函數(shù)F1～F4，F(xiàn)7～F9和DTLZ2，共8個(gè)測(cè)試函數(shù)上進(jìn)行實(shí)驗(yàn)比較。其中，F(xiàn)4，F(xiàn)8，DTLZ2屬于三目標(biāo)函數(shù)，F(xiàn)4中變量線性相關(guān)，F(xiàn)8中變量非線性相關(guān)，DTLZ2為變量無關(guān)測(cè)試函數(shù)，種群規(guī)模NX為200；F1，F(xiàn)2，F(xiàn)3，F(xiàn)7，F(xiàn)9為兩目標(biāo)函數(shù)；F1，F(xiàn)2，F(xiàn)3為變量線性相關(guān)測(cè)試函數(shù)；F7，F(xiàn)9為變量非線性相關(guān)函數(shù)，種群規(guī)模NX為200。對(duì)于兩目標(biāo)測(cè)試函數(shù)F1，F(xiàn)2，MaxIter設(shè)置為100，對(duì)于三目標(biāo)測(cè)試函數(shù)，MaxIter設(shè)置為200，其余測(cè)試函數(shù)為1 000。對(duì)于每個(gè)測(cè)試函數(shù)，每種算法各單獨(dú)運(yùn)行20次。算法在各個(gè)測(cè)試函數(shù)所需的迭代次數(shù)、種群規(guī)模以及真實(shí)Pareto前沿的參考點(diǎn)個(gè)數(shù)如表1所示。

表1 各個(gè)測(cè)試函數(shù)所需的不同參數(shù)Tab.1 Different parameters required by each test function

3.3 重用策略的有效性

在AP-RM-MEDA中，為了降低AP聚類操作帶來的計(jì)算開銷，將重用連續(xù)L=20代都保持不變的聚類數(shù)目K值，而不再進(jìn)行AP聚類。為了驗(yàn)證其有效性，使用帶重用機(jī)制的和不帶重用機(jī)制的AP-RM-MEDA算法分別對(duì)迭代次數(shù)1 000的測(cè)試函數(shù)F3，F(xiàn)7，F(xiàn)9進(jìn)行實(shí)驗(yàn)驗(yàn)證。其中，不帶重用機(jī)制是指算法每次迭代過程中都將進(jìn)行AP聚類操作，得到聚類數(shù)目K。在獨(dú)立運(yùn)行算法20次之后，2種算法得到的評(píng)價(jià)指標(biāo)的均值、方差以及帶重用機(jī)制算法的平均聚類次數(shù)如表2所示。

表2 2種算法在測(cè)試函數(shù)上的GD，IGD和HV的均值及方差Tab.2 The mean and variance of GD, IGD and HV of two algorithms on the test function

表2的數(shù)據(jù)結(jié)果顯示，對(duì)于有或無重用機(jī)制的2種算法在以上測(cè)試函數(shù)上所表現(xiàn)的性能并沒有較大差異。從聚類次數(shù)上看，帶有重用機(jī)制的算法需要的聚類次數(shù)大大減少，而沒有重用機(jī)制的算法均需要聚類1 000次。基于上述實(shí)驗(yàn)結(jié)果可以證明，在對(duì)提出的AP-RM-MEDA算法性能影響不大的前提下，重用機(jī)制能有效地降低算法的計(jì)算開銷。

3.4 實(shí)驗(yàn)對(duì)比結(jié)果及分析

表3、表4和圖1分別是4種算法在兩目標(biāo)測(cè)試函數(shù)上測(cè)試得到的評(píng)價(jià)指標(biāo)GD和IGD的均值、方差及解集構(gòu)成的Pareto前沿。表3和表4中，為了更好地突出最好的數(shù)據(jù)值，對(duì)結(jié)果數(shù)據(jù)中最好的值進(jìn)行加粗表示。

表3 4種算法在兩目標(biāo)測(cè)試函數(shù)上的GD的均值及方差Tab.3 The mean and variance of GD of four algorithms on the two-objective test functions

表4 4種算法在兩目標(biāo)測(cè)試函數(shù)上的IGD的均值及方差Tab.4 The mean and variance of IGD of the four algorithms on the two-objective test functions

(a) 4種算法在F1函數(shù)上獲得的PF對(duì)比圖

(b) 4種算法在F2函數(shù)上獲得的PF對(duì)比圖

(c) 4種算法在F3函數(shù)上獲得的PF對(duì)比圖

(d) 4種算法在F7函數(shù)上獲得的PF對(duì)比圖

(e) 4種算法在F9函數(shù)上獲得的PF對(duì)比圖圖1 4種算法在兩目標(biāo)函數(shù)上獲得的Pareto前沿對(duì)比Fig.1 Comparison of Pareto front obtained by four algorithms on two-objective functions

從表3和表4中的數(shù)據(jù)可以看出，在絕大多數(shù)兩目標(biāo)測(cè)試函數(shù)上，AP-RM-MEDA算法與對(duì)比算法相比具有更好的表現(xiàn)。從表3中GD的結(jié)果數(shù)據(jù)可看出，對(duì)于較為簡(jiǎn)單的測(cè)試函數(shù)，無論是凸函數(shù)還是凹函數(shù)(如F1和F2)，AP-RM-MEDA算法的表現(xiàn)更加穩(wěn)定，收斂能力得到明顯提升。對(duì)于較困難的測(cè)試函數(shù)(如F3，F(xiàn)7和F9)，AP-RM-MEDA算法的收斂效果也好于其他對(duì)比算法。表4中IGD的數(shù)據(jù)顯示，在收斂性和多樣性方面，AP-RM-MEDA算法的綜合性能表現(xiàn)也不差于RM-MEDA。

表5和表6分別是4種算法在三目標(biāo)測(cè)試函數(shù)上測(cè)試得到的評(píng)價(jià)指標(biāo)GD和IGD的均值、方差。在表5和表6中，為了更好地突出最好的數(shù)據(jù)值，對(duì)結(jié)果數(shù)據(jù)中最好的值進(jìn)行加粗表示。

表5 4種算法在三目標(biāo)測(cè)試函數(shù)上的GD的均值及方差Tab.5 The mean and variance of GD of four algorithms on the three-objective test functions

表6 4種算法在三目標(biāo)測(cè)試函數(shù)上的IGD的均值及方差Tab.6 The mean and variance of IGD of four algorithms on the three-objective test functions

4種算法在三目標(biāo)測(cè)試函數(shù)F4上獲得的Pareto前沿對(duì)比如圖2所示。

(a) RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(b) DES-RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(c) FRM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(d) AP-RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖圖2 4種算法在F4上獲得的Pareto前沿Fig.2 Pareto front obtained by four algorithms on F4

4種算法在三目標(biāo)測(cè)試函數(shù)F8上獲得的Pareto前沿對(duì)比如圖3所示。

(a) RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(b) DES-RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(d) AP-RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖圖3 4種算法在F8上獲得的Pareto前沿Fig.3 Pareto front obtained by four algorithms on F8

4種算法在三目標(biāo)測(cè)試函數(shù)DTLZ2上獲得的Pareto前沿對(duì)比如圖4所示。

(a) RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(b) DES-RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(c) FRM-MEDA獲得的PF與真實(shí)PF對(duì)比圖

(d) AP-RM-MEDA獲得的PF與真實(shí)PF對(duì)比圖圖4 4種算法在DTLZ2上獲得的Pareto前沿Fig.4 Pareto front obtained by four algorithms on DTLZ2

從表5、表6和圖2～圖4中的數(shù)據(jù)可以看出，在三目標(biāo)測(cè)試函數(shù)上，AP-RM-MEDA算法與對(duì)比算法相比，其非支配解都可以更好地收斂到真實(shí)Pareto前沿上，其綜合性能也有一定程度的提升。

結(jié)合上述表中的對(duì)比數(shù)據(jù)和Pareto前沿的對(duì)比圖表明，AP-RM-MEDA算法在收斂性和多樣性方面有著較優(yōu)的表現(xiàn)。

4 結(jié)束語

本文提出的基于AP的多目標(biāo)分布估計(jì)算法中，通過引入AP聚類操作來自動(dòng)確定種群需要聚類的數(shù)目，避免了人為確定聚類數(shù)目的不準(zhǔn)確性以及聚類數(shù)目與實(shí)際所需不等時(shí)以致算法無法建立正確的概率模型。同時(shí)，為了減小AP聚類操作所帶來的額外計(jì)算開銷，設(shè)計(jì)了一種將聚類數(shù)目進(jìn)行重用的策略，并通過實(shí)驗(yàn)驗(yàn)證了其有效性。通過混合算子共同生成新的個(gè)體，結(jié)合種群的整體和個(gè)體信息，提高了算法的全局搜索能力。與其他3種算法的對(duì)比實(shí)驗(yàn)結(jié)果表明，本文提出的AP-RM-MEDA算法與其他幾種性能較好的算法相比，收斂性和整體性能均有提升，同時(shí)在絕大多數(shù)兩目標(biāo)和三目標(biāo)測(cè)試問題中，都有著更好的表現(xiàn)。