譚陽 唐德權(quán) 曹守富

摘 要：高維多目標(biāo)優(yōu)化問題（MAOP）會隨著待優(yōu)化問題維度的增加形成巨大的目標(biāo)空間，導(dǎo)致在目標(biāo)空間中非支配解的比例急劇增加，削弱了進化算法的選擇壓力，降低了進化算法對MAOP的求解效率。針對這一問題，提出一種以超球型支配關(guān)系降低種群中非支配解數(shù)量的粒子群優(yōu)化（PSO）算法。算法以模糊支配策略來維持種群對MAOP的選擇壓力，并通過全局極值的選擇和外部檔案的維護來保持種群個體在目標(biāo)空間中的分布。在標(biāo)準(zhǔn)測試集DTLZ和WFG上的仿真結(jié)果表明，所提算法在求解MAOP時具備較優(yōu)的收斂性和分布性。

關(guān)鍵詞：高維多目標(biāo)優(yōu)化問題;Pareto支配;粒子群;多樣性

中圖分類號：TP301.6

文獻標(biāo)志碼：A

Manyobjective particle swarm optimization algorithm based on

hyperspherical fuzzy dominance

TAN Yang1，2*， TANG Dequan1，3， CAO Shoufu1，2

1.College of Mathematics and Statistics， Hunan Normal University， Changsha Hunan 410081， China;

2.Department of Network Technology， Hunan Radio and Television University， Changsha Hunan 410004， China;

3.Department of information technology， Hunan Police Academy， Changsha Hunan 410138， China

Abstract：

With the increase ofthe dimension of the problem to be optimized， Manyobjective Optimization Problem （MAOP） will form a huge target space， resulting in a sharp increase of the proportion of nondominant solutions. And the selection pressure of evolutionary algorithms is weakened and the efficiency of evolutionary algorithms for solving MAOP is reduced. To solve this problem， a Particle Swarm Optimization （PSO） algorithm using hyperspherical dominance relationship to reduce the number of nondominant solutions was proposed. The fuzzy dominance strategy was used to maintain the selection pressure of the population to MAOP. And the distribution of individuals in the target space was maintained by the selection of global extremum and the maintenance of external files. The simulation results on standard test sets DTLZ and WFG show that the proposed algorithm has better convergence and distribution when solving MAOP.

Key words：

Manyobjective Optimization Problem （MAOP）; Pareto dominance; particle swarm; diversity

0?引言

最優(yōu)化問題一直是工程實踐和科學(xué)研究中主要的問題形式之一[1]。其中，函數(shù)優(yōu)化目標(biāo)在2～3個并且需要同時處理的最優(yōu)化問題被稱為多目標(biāo)優(yōu)化問題（Multiobjective Optimization Problems， MOP）。而函數(shù)優(yōu)化目標(biāo)等于或大于4個的優(yōu)化問題則被稱為高維多目標(biāo)優(yōu)化問題（Manyobjective Optimization Problem， MAOP）。多目標(biāo)問題會隨著目標(biāo)維度的增加導(dǎo)致解空間急劇增大，尋優(yōu)算法在解空間中幾乎全部互為非支配個體;傳統(tǒng)的Pareto支配關(guān)系無法使算法產(chǎn)生足夠的選擇壓力，致使算法搜索困難[2]。針對這一問題，國內(nèi)外的學(xué)者們分別提出不同的解決思路。Farina等[3]基于人工決策系統(tǒng)的模糊型最優(yōu)性定義，提出以非偏好為基礎(chǔ)來改進支配關(guān)系，從而在優(yōu)化高維多目標(biāo)問題時擴大了支配域，但該方法存在容易產(chǎn)生循環(huán)支配的缺陷。Li等[4]提出基于移位的密度估計多樣性策略，通過調(diào)整Pareto支配關(guān)系和偏好維護機制的方法來平衡算法的性能，由于該方法需要考慮對目標(biāo)函數(shù)的縮放，因此在優(yōu)化凹面函數(shù)時其分布性能受限。Wang等[5]采用自適應(yīng)的分解方法，以分治法對高維多目標(biāo)問題進行降維分解，該方法可以提高算法的性能，但其困難之處在于需要對分解所得的子問題施加人工約束。陳振興等[6]在張角概念的基礎(chǔ)上提出了一種新的擁擠控制策略，能夠較好地維護種群的分布的均勻性，但該方法效能嚴重依賴于角度閾值參數(shù)的設(shè)定。Deb等[7]通過篩選部分非支配個體的方式來為整個種群選取一組參考點，并以該組參考點來評價個體的質(zhì)量，從而輔助控制種群在目標(biāo)空間中的分布，并提出了帶精英策略的快速非支配排序遺傳算法（Nondominated Sorting Genetic Algorithms Ⅲ， NSGAⅢ）算法。但值得注意的是，文獻中并沒有討論該方法在有約束優(yōu)化問題上的性能。

粒子群優(yōu)化算法（Particle Swarm Optimization， PSO）是由Kennedy等[8]于1995年提出的一種智能優(yōu)化算法。PSO算法是一種源于對鳥群等群體運動行為的優(yōu)化工具，與其他的優(yōu)化算法相比較，PSO具有算法簡單、收斂速度快、對目標(biāo)函數(shù)要求少等特點，因而成為重要的優(yōu)化工具。近年來，國內(nèi)外學(xué)者在研究PSO優(yōu)化多目標(biāo)問題的領(lǐng)域取得了很大的進展，提出了不少基于PSO的多目標(biāo)優(yōu)化算法，但將PSO用于高維多目標(biāo)優(yōu)化問題求解的理論和方法較少。其原因在高維多目標(biāo)優(yōu)化問題上最優(yōu)解分布于Pareto最優(yōu)前沿面之上，巨大的解空間將導(dǎo)致PSO的選擇壓力迅速降低，算法早熟收斂而無法有效獲取問題的最優(yōu)前沿面。

針對PSO的缺陷，本文提出一種基于超球形模糊支配的高維多目標(biāo)粒子群優(yōu)化（Hyperspherical Fuzzy dominance Particle Swarm Optimization， HFPSO）算法。在可行解全部目標(biāo)維度上增加一個半徑以形成超球體，以超球體所張成的空間來擴展可行解的支配域。同時，為增加算法的選擇壓力，以模糊支配策略來進一步降低非支配解在種群中的比例。在分布性維護操作上，將個體全局最優(yōu)值的選擇策略調(diào)整為動態(tài)概率選擇， 更好地平衡了算法的收斂性和多樣性。

1?基本理論與概念

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

不失一般性，一個具有n個決策變量、m個目標(biāo)變量的多目標(biāo)優(yōu)化問題通常被描述[9]為：

miny=F（x）=（f1（x）， f2（x），…， fm（x））T（1）

s.t.x=（x1，x2，…，xn）∈XRn，

y=（y1，y2，…，ym）∈YRm

其中，X為n維的決策空間，Y為m維的目標(biāo)空間。只有當(dāng)優(yōu)化目標(biāo)為1時，最優(yōu)解才是在給定約束條件下使目標(biāo)函數(shù)最大的解，而當(dāng)多個目標(biāo)要求同時最優(yōu)時，最優(yōu)解就是Pareto最優(yōu)集。下面給出MAOP常用到幾個相關(guān)定義[9]：

定義1?可行解。對于某個x∈X，如果x滿足gi（x）≤0（i=1，2，…，q）和hj（x）≤0（j=1，2，…，p），則稱x為可行解。

定義2?Pareto最優(yōu)。若一個解x*∈Xf是Pareto最優(yōu)（非支配解），當(dāng)且僅當(dāng)x∈Xf：xx*。

定義3?Pareto最優(yōu)解集。所有Pareto最優(yōu)解的集合：

P*{x*x∈Xf：xx*}

定義4?Pareto最優(yōu)前沿面。所有Pareto最優(yōu)解對應(yīng)目標(biāo)矢量所組成的曲面稱為Pareto最優(yōu)前沿面或均衡面PF：

PF*

{F（x）*=（f1（x*）， f2（x*），…， fm（x*））x*∈P*}

1.2?標(biāo)準(zhǔn)PSO算法

在標(biāo)準(zhǔn)粒子群優(yōu)化（PSO）算法中，初始粒子在搜索空間中以一定的速度飛行，并通過追蹤兩個極值來更新自己完成尋優(yōu)。兩個極值分別為：粒子自身所找到的最優(yōu)解，稱為個體極值pbest;另一個是整個粒子種群目前找到的最優(yōu)解，稱為全局極值gbest。在兩個極值的作用下，粒子會依據(jù)式（2）來更新自己的速度和位置[8]：

vk+1=c0vk+c1（pbestk-xk）+c2（gbestk-xk）

xk+1=xk+vk+1（2）

其中：vk是粒子的速度向量; xk是粒子當(dāng)前的位置; c0、c1、c2表示群體認知系數(shù)，標(biāo)準(zhǔn)PSO中c0一般取（0，1）的隨機數(shù)，c1、c2?。?，2）的隨機數(shù)。在每一維上粒子的速度都會被限制在一個最大速度vmax（vmax>0）內(nèi)，即vk>vmax或vk<-vmax時，vk=vmax或vk=-vmax。

1.3?標(biāo)準(zhǔn)PSO對MAOP優(yōu)化的分析

基于Pareto支配關(guān)系，標(biāo)準(zhǔn)PSO的種群能夠逐漸收斂到一個不被任何其他解支配的Pareto最優(yōu)解集上。但基于Pareto支配方法的優(yōu)化效果與種群中非支配解個體所占比例密切相關(guān)，Adra等[10]曾指出非支配個體在種群中所占比例會隨著算法迭代次數(shù)增加而迅速上升，甚至大部分個體都成為非支配解。這將導(dǎo)致算法各種擇優(yōu)策略無法實施，削弱基于Pareto支配比較與選擇的效果，導(dǎo)致優(yōu)化算法搜索能力的下降。為了更具體地分析標(biāo)準(zhǔn)PSO對MAOP優(yōu)化的性能，以可擴展目標(biāo)維度的DTLZ1函數(shù)[11]為例，分別設(shè)置不同的目標(biāo)維度數(shù)。設(shè)置PSO的種群規(guī)模為N=200，并限定PSO的最大迭代次數(shù)Tmax=20，記錄PSO在完成不同目標(biāo)維度優(yōu)化問題后非支配解的數(shù)量。為了消除其他因素的影響，對每種不同目標(biāo)維度的MAOP獨立優(yōu)化30次，取平均值，結(jié)果如圖1所示。

實驗結(jié)果顯示隨著目標(biāo)維度的增加，標(biāo)準(zhǔn)PSO中非支配解所占比例迅速提高，削弱了PSO種群在進化過程中基于Pareto支配的選擇壓力，導(dǎo)致算法性能下降。

2?基于超球形模糊支配的粒子群算法

2.1?超球形支配關(guān)系

隨著優(yōu)化問題目標(biāo)維度的進一步增加，種群中非支配個體的數(shù)量將呈指數(shù)上升，將大大削弱PSO基于Pareto比較進行選擇與搜索的能力。因此，適當(dāng)放寬Pareto支配關(guān)系，則能對其他非支配個體進行比較與選擇。Sato等[12]提出了一種擴展支配域的方法，并應(yīng)用于NSGAⅡ上[13]，提高了NSGAⅡ的性能;但這一方法的主要缺陷在于需要為每一待優(yōu)化的目標(biāo)函數(shù)設(shè)置修正參數(shù)?？紤]到MAOP中最優(yōu)前沿面為一超平面，算法種群中的個體為了逼近這一超平面，在優(yōu)化的過程會形成支配關(guān)系，而決定個體支配關(guān)系的主要因素在于解空間中個體支配域的范圍。個體支配域較小，容易提升種群出現(xiàn)非支配解的幾率， 大量的非支配解的出現(xiàn)會導(dǎo)致Pareto支配關(guān)系在高維空間中面臨失效的境地。因此，要維護算法對MAOP的性能，需要擴展個體的支配域，降低非支配個體的數(shù)量，維持算法的選擇壓力以促進算法的收斂?；诖?，若以種群中任意可行解為基礎(chǔ)，并在其所有維度上都增加一個值為r的半徑，那么可得到一半徑為r的超球形。該超球形在解空間中所張成的支配域則由可行解現(xiàn)有的支配域擴展而來，以此擴展了個體支配域的范圍。

由圖2可以看出，按照Pareto支配關(guān)系A(chǔ)、B、C互為非支配個體;但在擴展支配域中個體A、C被B所支配。寬松支配關(guān)系的核心是提升較優(yōu)個體的支配概率，通過擴展支配域來放寬支配關(guān)系，則降低了對較優(yōu)目標(biāo)個數(shù)所占比重的要求。此舉使得種群中的個體更易形成支配關(guān)系，從而提高支配的概率和種群的選擇壓力，促進算法的收斂。調(diào)整半徑值r的大小，可控制超球體所張成的擴展支配域。在優(yōu)化高維多目標(biāo)問題時可將r值設(shè)定為后期小一些，隨著迭代次數(shù)的增加r值逐漸減小至0，種群中非支配解更容易產(chǎn)生，以加速收斂。式（3）給出了半徑值r的動態(tài)計算方法，隨著迭代次數(shù)的增加而動態(tài)減小，實現(xiàn)算法在初始時利于全局搜索，后期則加速收斂。

r=rmax-（t×rmax/Tmax）; rmax=（vmax×m）/N（3）

其中：rmax為最大半徑值，Tmax為算法的最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，vmax為粒子在目標(biāo)空間中的最大速度，m為MAOP的維數(shù)，N為種群規(guī)模。

2.2?模糊支配策略

超球形支配關(guān)系會使得個體目標(biāo)函數(shù)產(chǎn)生不可預(yù)測性，為避免種群個體發(fā)生循環(huán)支配，F(xiàn)arina等[3]將模糊理論應(yīng)用于MAOP的優(yōu)化，提出以個體間目標(biāo)優(yōu)劣的數(shù)量來衡量個體的支配關(guān)系。受此啟發(fā)，提出一種模糊支配的策略。令F（xi）為個體xi的目標(biāo)向量。對種群中任意兩個不相同個體xi和xj（i≠j）的目標(biāo)向量F（xi）和F（xj）比較后，可得到xi優(yōu)于xj、xi等于xj和xi劣于xj三種不同的目標(biāo)維度比較值，且分別用Better（xi，xj）、Equal（xi，xj）和Worse（xi，xj）表示;則個體xi和xj的模糊支配度C（xi，xj）由式（4）計算;其模糊支配集CS由式（5）表示：

C（xi，xj）=

Better（xi，xj）+Equal（xi，xj）Better（xi，xj）+Equal（xi，xj）+Worse（xi，xj）（4）

CS={C（xi，xj）xi，xj∈[1∶N]∧i≠j}（5）

本文將xi等于xj目標(biāo)維度數(shù)視作xi優(yōu)于xj的維度數(shù)，目的是通過寬松模糊支配關(guān)系進一步降低種群中非支配解的比例，維持算法在高維空間中的選擇壓力。由于大多數(shù)MAOP的最優(yōu)前沿面是事先未知的，超球形模糊支配關(guān)系的評價無需其他額外參數(shù)，完全利用MAOP函數(shù)自身的信息，進而提升算法的選擇壓力，推動種群有效地逼近真實Pareto前沿。

2.3?全局極值選取策略

在標(biāo)準(zhǔn)PSO中，全局極值gbest起著引導(dǎo)粒子向Pareto最優(yōu)前沿面逼近的作用， 因此，也是改善算法分布性能的關(guān)鍵。通過調(diào)整全局極值的選取策略，可以引導(dǎo)種群向真實Pareto前沿推進，或者沿Pareto前沿進行多樣性分布，從而有效改善算法的分布性能。但由于MAOP的最優(yōu)解是由若干非劣解所構(gòu)成的集合，在優(yōu)化MAOP時不能像單目標(biāo)優(yōu)化問題那樣明確方向，因此需要重新定義對MAOP的gbest;構(gòu)建由多個占優(yōu)個體所組成的gbest候選集，實現(xiàn)gbest選擇的多樣化。為了簡化候選集的維護，這里直接將個體的pbest作為gbest候選集，并賦予候選集中所有個體相同的被選幾率。

直接將pbest作為gbest候選集，可能會導(dǎo)致PSO出現(xiàn)停滯和群聚兩個方面的問題[14]。因此，首先要確定個體在選擇全局極值時不能自我選擇，只能在其他的（N-1）個體中選擇，以避免PSO出現(xiàn)停滯; 其次，PSO在運行初期可能會出現(xiàn)超級個體，超級個體通過自身的競爭優(yōu)勢而被種群其他個體反復(fù)選擇，從而產(chǎn)生群聚效應(yīng)，致使種群的多樣性下降算法發(fā)生退化。為了避免群聚效應(yīng)的出現(xiàn)，gbest候選集中個體的被選幾率為動態(tài)概率。若令種群中任意個體i的被選概率為pi，則初始情況下pi=1/（N-1）。若個體i的pbesti被其他任意個體j（j≠i）所選擇，那么對于其他（N-2）個個體而言，個體i的被選概率降低，其他的（N-1）個體的被選擇概率提升。式（6）給出了個體i被選擇為全局極值后概率的變化：

i-1/（N-1）， Selected individual

pj=pj+[1/（N-1）2]， 其他 （6）

其中，i=1，2，…，N， j=1，2，…，N且j≠i。初始情況下pi=pj=1/（N-1）。

2.4?外部檔案維護策略

本文所提出的基于超球形模糊支配的粒子群算法與其他經(jīng)典的多目標(biāo)優(yōu)化算法相同，要建立用于存儲非支配解的外部檔案Rep，用于保存種群在進化過程中所發(fā)現(xiàn)的非支配個體，并以支配關(guān)系對個體進行比較。為了優(yōu)化最終解在目標(biāo)空間的分布性能，要求Rep中的個體能夠盡量廣泛且均勻地分布在目標(biāo)空間之中。因此，維護Rep中個體間的分布也是優(yōu)化MAOP的關(guān)鍵技術(shù)之一。當(dāng)算法所得到的非支配解數(shù)量超過Rep限定最大容量時，則需要刪除超出其最大容量的非支配解。對于任意非支配個體i而言，其與Rep中個體的平均距離di值由式（7）計算：

di=NRep（1/di，1）+（1/di，2）+…+（1/di，NRep）（7）

其中：NRep表示外部檔案規(guī)模的大小，di，1，di，2，…，di，NRep分別表示非支配個體i與Rep中個體間的距離。因此，外部檔案維護策略為：根據(jù)的Rep規(guī)模NRep，依次刪除平均距離di值最小的解。

2.5?算法流程

綜上所述，基于超球形模糊支配的高維多目標(biāo)粒子群算法總體流程如下：

步驟1?初始化。設(shè)置種群規(guī)模N和Rep規(guī)模NRep，設(shè)定算法最大迭代次數(shù)Tmax，并初始化種群粒子，并以當(dāng)前位置為個體最優(yōu)pbest，初始化Rep;令t=0。

步驟2?t←t+1。根據(jù)2.3節(jié)所介紹的方法，為每個粒子選擇gbest，按式（2）來更新粒子的速度和位置;計算更新后粒子的目標(biāo)函數(shù)值。

步驟3?根據(jù)2.1節(jié)、2.2節(jié)所提出的超球形模糊支配策略，將種群中的粒子與Rep中的解比較，若粒子支配Rep中現(xiàn)有的解，或兩者互不支配，則將粒子保存到Rep之中，并刪除Rep中被支配的解。

步驟4?判斷Rep中解的數(shù)量是否大于NRep：若成立，則根據(jù)2.4節(jié)所提出的外部檔案維護策略，刪除Rep中多余數(shù)量的解;否則，執(zhí)行下一步。

步驟5?判斷t≤Tmax是否成立。若成立，則跳轉(zhuǎn)返回步驟2;否則，輸出Rep中所保存的非支配解。

3?實驗及結(jié)果分析

為了驗證算法的性能，這里選取5個代表性的多目標(biāo)進化算法作為對比算法，分別為：基于網(wǎng)格的進化算法（Gridbased Evolutionary Algorithm， GrEA）[15]、NSGAⅢ[7]、提升Pareto前沿的進化算法（Strength Pareto Evolutionary Algorithm， SPEA2+）[16]、拐點驅(qū)動的進化算法（Knee PointDriven Evolutionary Algorithm， KnEA）[17]和基于分解的多目標(biāo)進化算法（Multiobjective Evolutionary Algorithms based on Decomposition， MOEA/D）[5]，并選擇在高維多目標(biāo)優(yōu)化領(lǐng)域通用的DTLZ測試函數(shù)集[11]及WFG測試函數(shù)集[18]上進行對比實驗。為了盡量獲取一致的數(shù)據(jù)，按照原文獻中所提供的控制參數(shù)，使用Python重寫了所有對比算法。其中，HFPSO的外部檔案與種群大小一致，且c0?。?，1）的隨機數(shù);c1、c2取（0，2）的隨機數(shù)。6種對比算法對DTLZ及WFG測試函數(shù)分別設(shè)定4種不同的目標(biāo)維度m=4、6、10、20用于測試比較，對比算法的最大迭代次數(shù)均為10-000并獨立運行30次取平均值。實驗平臺為：Core i5 3.3GHz的CPU和8GB的內(nèi)存。

3.1?算法性能評價指標(biāo)

現(xiàn)有的研究中一般采用反轉(zhuǎn)世代距離（Inverted Generational Distance， IGD）[19]來評價算法綜合性能的優(yōu)劣，IGD可以同時評價算法所獲解集的收斂性和分布性。由于DTLZ及測試函數(shù)集的真實Pareto解集已知，所以通過IGD的評價可以直接說明對比算法近似Pareto前沿的收斂性和多樣性。通常，IGD指標(biāo)值越小則說明算法的性能越好。

IGD（P，P*）=∑ v∈P*d（v，P）P*（8）

其中： P為算法在目標(biāo)空間中所獲得的最終解集，P*為均勻分布的Pareto最優(yōu)前沿面，d（v，P）為Pareto最優(yōu)前沿面上的點v∈P*到最終解集的最小歐氏距離，P*為Pareto最優(yōu)前沿面上點的總數(shù)。

3.2?實驗結(jié)果與分析

表1中為各對比算法在DTLZ測試函數(shù)集上的平均IGD，最好結(jié)果用加粗字體表示。另外為了比較HFPSO與另外5種對比算法所獲得的平均IGD值之間的差異，給出各對比算法的標(biāo)準(zhǔn)差（Std），以反映各算法的穩(wěn)定性。

從表1中可以看出，在線性多模態(tài)測試函數(shù)DTLZ1的優(yōu)化上，HFPSO在目標(biāo)維度為10時取得了最優(yōu)結(jié)果，并在目標(biāo)維度為4、6時取得了次優(yōu)結(jié)果;與在該函數(shù)上表現(xiàn)最好的NSGAⅢ相差無幾，表現(xiàn)出較強的收斂能力。在凹面函數(shù)DTLZ2上，HFPSO分別取得了目標(biāo)維度為10、20時的最優(yōu)結(jié)果，并取得了目標(biāo)維度為6時的次優(yōu)結(jié)果;這表明HFPSO在增大目標(biāo)維度后其運算能力并沒有出現(xiàn)快速退化的現(xiàn)象，表現(xiàn)出較好的穩(wěn)定性。對凹面多模態(tài)測試函數(shù)DTLZ3而言，HFPSO取得了目標(biāo)維度為6、20時的最優(yōu)結(jié)果，同時也獲得了目標(biāo)維度為4時的次優(yōu)結(jié)果，這也表明HFPSO較其他對比算法，其全局優(yōu)化能力有較好的表現(xiàn)。DTLZ4函數(shù)是一凹面有偏好的測試函數(shù)，主要用于測試算法的分布性及保持分布性的能力，表中HFPSO在目標(biāo)維度為6時取得了最優(yōu)結(jié)果，并分別取得目標(biāo)維度為4、10時的次優(yōu)結(jié)果，這也表明HFPSO的全局極值選取策略能夠有效維護種群分布的多樣性。對于凹面退化的測試函數(shù)DTLZ5，HFPSO僅在目標(biāo)維度為4、6、20時取得次優(yōu)結(jié)果，相較在該函數(shù)上表現(xiàn)最好的MOEA/D而言，HFPSO的曲線收斂能力一般，其主要原因在于超球形的支配關(guān)系受到了Pareto最優(yōu)前沿曲面的影響，在部分目標(biāo)空間中沒有形成有效的超球形支配關(guān)系。DTLZ6同樣為凹面退化的測試函數(shù)，但不同于DTLZ5，DTLZ6具有偏好;因此HFPSO在目標(biāo)維度為4、10時取得了最優(yōu)結(jié)果，并在目標(biāo)維度為6、20時取得了次優(yōu)結(jié)果，表現(xiàn)出很強的競爭力。在不連續(xù)且多模態(tài)的測試函數(shù)DTLZ7上，HFPSO取得目標(biāo)維度為6、20時的最優(yōu)結(jié)果，值得注意的是KnEA分別取得目標(biāo)維度為4、10時的最優(yōu)結(jié)果;SPEA2+則取得該測試函數(shù)全部目標(biāo)維度的次優(yōu)結(jié)果;三種算法均具備較強的在多種Pareto前沿面維護分布性的能力。

表2為各對比算法在WFG測試函數(shù)集上的平均IGD，最好結(jié)果用加粗字體表示。

從表2中可以看出，在對帶有偏好及混合結(jié)構(gòu)的WFG1的優(yōu)化上，HFPSO在目標(biāo)維度為6時取得了最優(yōu)結(jié)果，稍遜于表現(xiàn)最好的SPEA2+。在不連續(xù)的WFG2問題上，HFPSO表現(xiàn)出不錯的性能，在目標(biāo)維度為4、6時取得了最優(yōu)結(jié)果并取得了目標(biāo)維度為20時的次優(yōu)結(jié)果。復(fù)雜性問題WFG3，其兼具最優(yōu)前沿退化和決策變量不可以分離的特性，因此優(yōu)化較為復(fù)雜，但在這一問題上HFPSO分別取得了目標(biāo)維度為6、10時的最優(yōu)結(jié)果和目標(biāo)維度為4時的次優(yōu)結(jié)果，表現(xiàn)出較強的對高維復(fù)雜問題的優(yōu)化能力。在WFG4～WFG9這6類凸面優(yōu)化問題的優(yōu)化上，HFPSO共取得了9次最優(yōu)結(jié)果和8次次優(yōu)結(jié)果，除了在WFG6上與其他對比算法相似外，在高維凸面問題上明顯優(yōu)于其他對比算法。

綜觀表1、2的結(jié)果，HFPSO整體表現(xiàn)最好。其中，在DTLZ測試集上共取得了10次最優(yōu)結(jié)果和11次次優(yōu)結(jié)果;在WFG測試集上，HFPSO共取得了14次最優(yōu)結(jié)果和10次次優(yōu)結(jié)果，表現(xiàn)出較優(yōu)的總體性能。相較其他5種對比算法，本文算法具有較強的收斂性和多樣性上的優(yōu)勢，能有效處理所有的測試函數(shù)，且表中的數(shù)據(jù)也反映出HFPSO具有較好的穩(wěn)定性。

為了能更進一步地說明HFPSO的收斂性，在表3和表4分別給出了反映6種對比算法收斂性的世代距離指標(biāo)（Generational Distance， GD）[20]，其中GD值越小，說明通過算法得到的非支配解集越逼近真實解集，收斂性越好。

限于篇幅，表3和表4中只給出了具有代表性的線性Parto前沿DTLZ1、凹Parto前沿DTLZ4、凸Parto前沿WFG2、混合前沿DTLZ7和多模態(tài)前沿WFG9在目標(biāo)維度（m）為10和20時的GD指標(biāo)數(shù)據(jù)。

綜合表3和表4的結(jié)果，HFPSO共取得了4次GD指標(biāo)最優(yōu)，其中：在DTLZ1的收斂性測試上取得了目標(biāo)維度為10、20的次優(yōu)結(jié)果，與MOEA/D和SPEA2+一致，表現(xiàn)出較好的收斂性。在凹Parto前沿DTLZ4測試中HFPSO取得了目標(biāo)維度為10時的最優(yōu)結(jié)果，與表現(xiàn)最優(yōu)的SPEA2+相差無幾。對于凸Parto前沿的WFG2，HFPSO的收斂能力表現(xiàn)一般，主要因為是超球體支配關(guān)系在容易在凸Parto前沿測試函數(shù)上形成無效的擴展支配域，導(dǎo)致支配概率的相對下降。在混合前沿DTLZ7上HFPSO取得了目標(biāo)維度為20時的最優(yōu)解并取得了目標(biāo)維度為10時的次優(yōu)解，表現(xiàn)出良好的性能。對于多模態(tài)前沿的WFG9函數(shù)HFPSO則全面優(yōu)于其他對比算法，超球形支配關(guān)系在多模態(tài)前沿問題的優(yōu)化上表現(xiàn)出很強的競爭力。

為了能夠直觀地反映所有算法得到的最終解集在高維目標(biāo)空間中的分布情況，采用平行坐標(biāo)來可視化高維目標(biāo)數(shù)據(jù)，圖3中給出了各對比算法在DTLZ4（m=10）上的最終解集。圖3中可以看出HFPSO具有良好的解集分布維護性能，其最終解集較其他對比算法具備更好的分布性。這也說明HFPSO所設(shè)計的基于超球形模糊支配策略能夠有效引導(dǎo)種群收斂，全局極值選取策略和外部檔案維護策略能夠有效增加解集的分布性，在求解MAOP時能夠保持良好的收斂性和解集分布性。

4?結(jié)語

高維多目標(biāo)優(yōu)化問題的目標(biāo)空間會隨著目標(biāo)維度的增加呈指數(shù)級上升，從而導(dǎo)致難以對其進行有效的優(yōu)化。針對這一問題，提出以種群個體在維度上增加半徑的方式來擴展支配范圍，形成以維度半徑所張成的超球形擴展支配域，并通過增加模糊支配策略來有效降低種群中非支配個體的數(shù)量;維持了算法在高維空間中的選擇壓力，使得算法的搜索能力不受目標(biāo)個數(shù)增加的影響。

同時，所提出的全局極值選取策略和外部檔案維護策略避免了解集多樣性的丟失，維護了最終解集的多樣性。在對DTLZ測試集和WFG測試集的16個測試函數(shù)進行測試后，結(jié)果表明HFPSO算法在求解高維多目標(biāo)問題較對比算法而言，具有收斂性和多樣性的優(yōu)勢。

參考文獻 （References）

[1]ALI M， SIARRY P， PANT M. An efficient differential evolution based algorithm for solving multiobjective optimization problems[J]. European Journal of Operational Research， 2012， 217（2）：404-416.

[2]ZHANG X， TIAN Y， CHENG R， et al. A decision variable clusteringbased evolutionary algorithm for largescale manyobjective optimization[J]. IEEE Transactions on Evolutionary Computation， 2018， 22（1）：97-112.

[3]FARINA M， AMATO P. A fuzzy definition of “optimality” for manycriteria optimization problems[J]. IEEE Transactions on Systems， Man， Cybernetics — Part A： Systems and Humans， 2004， 34（3）： 315-326.

[4]LI M， YANG S， LIU X. Shiftbased density estimation for Paretobased algorithms in manyobjective optimization[J]. IEEE Transactions on Evolutionary Computation， 2014， 18（3）： 348-365.

[5]WANG L， ZHANG Q. Constrained sub problems in decomposition based multiobjective evolutionary algorithm[J]. IEEE Transactions on Evolutionary Computation， 2016， 20（3）：475-480.

[6]陳振興，嚴宣輝，吳坤安，等. 融合張角擁擠控制策略的高維多目標(biāo)優(yōu)化[J]. 自動化學(xué)報， 2015， 41（6）： 1145-1158. （CHEN Z X， YAN X H， WU K A， et al. Manyobjective optimization integrating open angle based congestion control strategy[J]. Acta Automatica Sinica， 2015， 41（6）： 1145-1158.）

[7]DEB K， JAIN H. An evolutionary manyobjective optimization algorithm using referencepointbased nondominated sorting approach， part I： solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation， 2014， 18（4）： 577-601.

[8]KENNEDY J， EBERHART R C. Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway： IEEE， 1995： 1942-1948.

[9]SADOLLAH A， ESKANDAR H， BAHREININEJAD A， et al. Water cycle algorithm for solving multiobjective optimization problems[J]. Soft Computing， 2015， 19（9）：2587-2603.

[10]ADRA S F， FLEMING P J. A diversity management operator for evolutionary manyobjective optimization[C]// Proceedings of the 2009 International Conference on Evolutionary Multicriterion Optimization， LNCS 5467. Berlin： Springer， 2009： 81-94.

[11]DEB K， THIELE L， LAUMANNS M， et al. Scalable test problems for evolutionary multiobjective optimization[C]// Proceedings of the 2002 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2002： 825-830.

[12]SATO H， AGUIRRE H E， TANAKA K. Controlling dominance area of solutions and its impact on the performance of MOEAs[C]// Proceedings of the 2007 International Conference on Evolutionary MultiCriterion Optimization， LNCS 4403. Berlin： Springer， 2007：5-20.

[13]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGAⅡ[J]. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[14]BENUWA B B， GHANSAH B， WORNYO D K， et al. A comprehensive review of particle swarm optimization[J]. International Journal of Engineering Research in Africa， 2016， 23：141-161.

[15]YANG S， LI M， LIU X， et al. A gridbased evolutionary algorithm for manyobjective optimization[J]. IEEE Transactions on Evolutionary Computation， 2013， 17（5）：721-736.

[16]LI M， YANG S， LIU X. Shiftbased density estimation for paretobased algorithms in manyobjective optimization[J]. IEEE Transactions on Evolutionary Computation， 2014， 18（3）：348-365.

[17]ZHANG X， TIAN Y， JIN Y. A knee pointdriven evolutionary algorithm for manyobjective optimization[J]. IEEE Transactions on Evolutionary Computation， 2015， 19（6）：761-776.

[18]HUBAND S， BARONE L， WHILE L， et al. A scalable multiobjective test problem toolkit[C]// Proceedings of the 2005 International Conference on Evolutionary MultiCriterion Optimization， LNCS 3410. Berlin： Springer， 2005：280-295.

[19]ZITZLER E， THIELE L， LAUMANNS M， et al. Performance assessment of multiobjective optimizers： an analysis and review[J]. IEEE Transactions on Evolutionary Computation， 2003， 7（2）：117-132.

[20]LIN Q， LIU S， ZHU Q， et al. Particle swarm optimization with a balanceable fitness estimation for manyobjective optimization problems[J]. IEEE Transactions on Evolutionary Computation， 2018， 22（1）：32-46.

This work is partially supported by the National Natural Science Foundation of China （61471169）， the Natural Science Foundation of Hunan Province （2018JJ2104）， the Scientific Research Fund of Hunan Department of Education （15C0928）.

TAN Yang， born in 1979， M. S.， associate professor. His research interests include intelligent computing， information security.

TANG Dequan， born in 1979， Ph. D.， associate professor. His research interests include data mining， artificial intelligence.

CAO Soufu， born in 1981， M. S.， lecturer. His research interests include information system engineering， multimedia information processing.