潘曉英 李昂儒 陳雪靜 趙 倩

（西安郵電大學(xué)計算機學(xué)院 西安 710121）

1 引言

在現(xiàn)實生活的許多領(lǐng)域，多目標優(yōu)化問題較多地涉及到四個以上目標對應(yīng)的高維多目標優(yōu)化問題［1］（many objective optimization problems MAPs），如設(shè)計的控制器、制造半導(dǎo)體、優(yōu)化設(shè)計等，其共同點在于，它們包含多個目標且之間有沖突。作為經(jīng)典的多目標優(yōu)化方法（Multi-objective evolutionary algorithm，MOEA），NSGA2，SPEA2等已成功解決相關(guān)問題，但低維優(yōu)化效果好的算法未能很好解決高維問題，目前研究熱點有：1）基于松散Pareto支配關(guān)系［4］來提高Pareto非支配排序方法的選擇能力，從而提高算法的收斂性能；2）目標降維［2～3］法，通過結(jié)合數(shù)學(xué)方法將目標維數(shù)縮減，刪除優(yōu)化問題中的冗余目標，將高維轉(zhuǎn)化為低維問題；3）采用聚合或分解的方法將高維優(yōu)化問題整合為低維多目標問題求解［5～6］；4）采用不同評價指標的高維多目標優(yōu)化 算 法（Indicator-based Evolutionary Algorithm，IBEA）［7］的思想是利用評價非支配解優(yōu)劣的某些指標來衡量個體的優(yōu)劣程度并進行相應(yīng)的適應(yīng)度賦值。其中基于分解思想求解多目標優(yōu)化問題的MOEA/D［5］算法已經(jīng)很成功地解決了兩個或三個目標的優(yōu)化問題，它結(jié)合數(shù)學(xué)規(guī)劃和進化算法，將一個復(fù)雜多目標問題分解成若干個單目標優(yōu)化子問題，然后用進化算法同時求解這些子問題的最優(yōu)解作為多目標問題的最終解。在這類方法中，擁有顯著效果的還有：AMS算法［8］、PPD-MOEA［9］以及 NS?GA3［10］算法。通過對上述算法的研究可知，分解方法對解決高維多目標優(yōu)化問題較好。

在上述基礎(chǔ)上，本文提出一種基于相關(guān)性選擇的多目標優(yōu)化算法（Correlative selection mecha?nism-based evolutionary algorithm for many-objec?tive optimization，CSEAM）。在CSEAM算法中，首先在平面上產(chǎn)生一組分布較均勻的參考點，一個參考點決定一條理想點的參考線；如果目標空間中的某個個體離某條參考線的距離比其他參考線都近，那么該參考線對應(yīng)的參考點就是該個體的相關(guān)參考點，對應(yīng)的個體是該參考線的相關(guān)個體。本文算法主要通過給每個參考點至少找到一個相關(guān)個體，來保證種群多樣性；另外我們會剔除同一參考點下的標量子函數(shù)最大的個體，保證種群向理想帕累托前沿方向進行。最后由于CSEAM算法未采用非支配擁擠度排序等龐大的計算方法，在很大程度上可以削減算法的計算復(fù)雜度。

2 相關(guān)理論背景

2.1 參考點的選擇

多目標分解進化算法一般在單位平面上產(chǎn)生一組均勻分布的參考點，一般采用Das和Dennis的方案［11］，該方案在M-1維的單位超平面上均勻產(chǎn)生一組參考點，令M表示優(yōu)化目標個數(shù)，參考點的總數(shù)目H是由參數(shù)D控制，參數(shù)D代表每個目標上劃分的份數(shù)。用符號組r1，r2，…，rH表示所有參考點，參考點ri（i=1，…，H）中的每一維元素都在中取值，所以ri（i=1，…，H）中的所有元素之和為1。參考點的總數(shù)目H和參數(shù)D會滿足以下式（1）。

以3個目標的多目標優(yōu)化問題為例（M=3），則參考點將會分布在（1，0，0）、（0，1，0）、（0，0，1）為三個頂點的三角平面上，如果D參數(shù)被設(shè)定為3，參考點的個數(shù)H就為10。如圖1，展示了這10個參考點的具體分布情況。但是當目標數(shù)M為8時，即使參數(shù)P設(shè)置為8，那么參考點的總數(shù)目H也將會達到5040，這樣種群的規(guī)模變得非常大或者冗余。為解決參考點總數(shù)目H隨著M和D急劇上升的問題，在這章中必須應(yīng)用更加高級的方案，當目標數(shù)比較大時，我們采用兩層產(chǎn)生參考點的方案。例如對于目標數(shù)M為8時，我們在第一層設(shè)置參數(shù)D=3，根據(jù)式（1），則產(chǎn)生120個參考點；在第二層上，我們設(shè)置參數(shù)D=2，再據(jù)式（1），產(chǎn)生36個參考點。故總共產(chǎn)生120+36=156個參考點，遠小于原來的個數(shù)。

圖1 單層參考點分布

圖2展示了針對3個目標優(yōu)化問題應(yīng)用兩層方案產(chǎn)生參考點。對于更多目標數(shù)目的優(yōu)化問題，同樣可采用此二層產(chǎn)生方案。

圖2 雙層參考點分布情況

下面給出兩層方案的算法流程，M為優(yōu)化問題的目標函數(shù)的個數(shù)；D1表示在第一層中沿每個目標方向劃分的份數(shù)；D2表示在第二層中沿每個目標方向劃分的份數(shù)；R1為參考集。如圖3。

上述算法中用到的子函數(shù)Recursion如圖4所示，其中R為參考集（初始化為空集）；r'表示一個M 維的向量，（初始化為0向量）；k代表函數(shù)本身的遞歸次數(shù)（初始化為0）；M 為優(yōu)化問題的目標函數(shù)的個數(shù)；D表示沿每個目標方向劃分的分數(shù)；total為參考點r'的前k維元素之和。

圖3 兩層參考點產(chǎn)生算法流程

圖4 Recursion子函數(shù)流程

2.2 個體與參考點之間的相關(guān)性

圖5給出了相關(guān)性概念，圖中z*和r分別表示理想點和一個參考點。在實際問題中，理想點一般都是未知的，所以一般使用當前出現(xiàn)過的每個目標的最好值作為理想值，即，其中，P表示當前出現(xiàn)過的所有個體解集合；λ=r-z*代表通過理想點z和參考點r的參考線；圖中的距離d1表示F（x）在參考線λ上的投影；距離d2表示F（x）到參考線λ的垂直距離。這里的距離 d1、距離 d2分別可以通過式（2）和式（3）計算得來［12］。

圖5 個體與參考點之間相關(guān)性說明

若點F（x）與參考線λ的垂直距離d2比到其他參考線的垂直距離都要小，這時則可定義個體x與參考線λ對應(yīng)的參考點r成相關(guān)性關(guān)系，并稱個體x是參考點r的相關(guān)個體，參考點r是個體x的相關(guān)參考點。根據(jù)上面定義可以得到每一個個體必須有一個且只能有一個相關(guān)參考點，而一個參考點卻可以沒有或者1個、2個甚至更多的相關(guān)個體。

3 基于相關(guān)性選擇的高維多目標優(yōu)化算法

3.1 基于相關(guān)性的差分進化及多項式變異選擇

本節(jié)將基于相關(guān)性的差分進化及多項式變異選擇機制和基于相關(guān)性的種群替換機制引入。在詳細介紹這兩種機制前，先給出每個個體和參考點的相關(guān)屬性定義。

對于每個個體x，存在3個屬性：1）相關(guān)參考點rx；2）目標函數(shù)F(x)與相關(guān)參考點rx對應(yīng)的參考線之間的垂直距離記為d1x（即圖5中的d2）；3）目標函數(shù)F(x)與相關(guān)參考點rx對應(yīng)的參考線之間的懲罰距離為d2x=d1+θd2，這里的d1和d2即如圖5中的d1和d2，θ為懲罰參數(shù)，在實驗設(shè)置中設(shè)置為5，與對比算法MOEA/D中的建議值相同。

對于每個參考點，同樣存在3個屬性：1）在父代解種群中，參考點r的所有相關(guān)個體集合記為Ur；2）在父代解種群中，參考點r的所有相關(guān)個體的數(shù)目為nr；3）對于參考點r，在所有參考點集中，參考點r最近的T個參考點集Vr，T是固定的參數(shù)，在實驗中設(shè)置為8。

在進行基于相關(guān)性的差分進化及多項式變異選擇之前，所有個體和參考點的3個屬性都會提前被計算好，值得注意的是，每個個體的參考點的屬性都是針對當前解種群而言的。圖6給出了基于相關(guān)性的差分進化及多項式變異選擇方法的具體操作過程。

直至得到的后代個體個數(shù)滿足popsize，則停止算法。因為提出的算法中，個體總數(shù)是成雙數(shù)的，所以種群規(guī)模也取為偶數(shù)。而在基于分解的進化算法中，種群規(guī)模一般和參考點的數(shù)目相等，若參考點數(shù)目呈奇數(shù)，則種群數(shù)目就為參考點數(shù)目加1；若參考點數(shù)目為偶數(shù)，則種群數(shù)目就為參考點數(shù)目。

圖6 基于相關(guān)性的差分進化及多項式變異選擇方法

3.2 基于相關(guān)性的種群更新選擇

基于相關(guān)性的種群更新選擇方法，是利用基于相關(guān)性的差分進化及多項式變異選擇算法所得的子代種群，來更新父代種群的。如圖7詳細算法流程如下，對于每個子代種群Qt中的第k個個體xk，計算該個體的3個屬性，且記為rk、d1xk和d2xk，并且確定其參考點rk的3個屬性，分別被記為Urk、nrk和Vrk。

若存在一個個體的參考點rk擁有的相關(guān)個體數(shù)目為0，則直接將該個體加入到當前父代種群Pt和Urk中，且參考點rk擁有的相關(guān)個體數(shù)目nrk+1；在找出所有參考點中相關(guān)個體的數(shù)目最多的參考點rmax；在參考點rmax的所有的相關(guān)個體中，找出第3個屬性值最大的個體，代表該解的相對收斂性最小，需要將該個體從當前父種群中剔除；最后更新rmax的3個屬性。

若不存在參考點的相關(guān)個體數(shù)目為0，則直接將個體xk加入到當前種群Pt和對應(yīng)的相關(guān)參考點rk的解集Urk中，且相關(guān)個體數(shù)nrk+1；接著在Urk中，找到第3個屬性值懲罰距離最大的個體xmax，并且將它從Pt和Urk中剔除。

通過上述的內(nèi)容，設(shè)定參考點的總數(shù)目等于所有參考點相關(guān)個體數(shù)目之和（或相差為1），這樣在搜索時，會出現(xiàn)有的參考點相關(guān)個體總數(shù)多，有的參考點相關(guān)個體總數(shù)少或者為0的情況，此時就需要找出相關(guān)個體數(shù)目最多的參考點，并將該參考點相關(guān)個體中的第3個屬性值懲罰距離最大的個體從當前種群中刪除，以此來保證種群的收斂性。具體算法流程見圖7。

圖7 算法CSEAM的主要流程

4 實驗結(jié)果與分析

4.1 DTLZ系列標準多目標優(yōu)化測試函數(shù)

本章采用Deb等提出的DTLZ系列多目標優(yōu)化測 試 函 數(shù)［13～14］來 分 析 CSEAM 的 性 能 ，分 別 為DTLZ1、DTLZ2、DTLZ3和DTLZ4，且這些測試函數(shù)在多篇文獻中作為標準測試問題用以衡量算法性能，函數(shù)詳細描述如表4所示。

測試函數(shù)，將參數(shù)k設(shè)置為5，對于DTLZ2、DTLZ3和DTLZ4測試函數(shù)，參數(shù)k被設(shè)置為10。

4.2 評價指標

為了更好地評價算法的收斂性和多樣性，這里采用性能指標IGD［15］，在介紹IGD之前，先來了解下指標GD的概念。

GD（Generational Distance）是由V.Veldhuizen和Lamont提出的一種評價方法［16］，用來描述算法所得的非劣解與問題的真是Pareto前沿之間的距離：

式（4）中，popsize為所求種群PFknown中解數(shù)量，disti表示在目標空間中，每一維向量與Pareto前沿PFtrue中的最近向量之間的歐式距離。

表1 DTLZ系列測試問題的數(shù)學(xué)描述

反代間距離（Inverted generational distance，IGD），表示算法求得的值和理想最優(yōu)解的趨近差值，設(shè)P*為帕累托前沿分布均勻的集合點，P是算法得到的近似Pareto最優(yōu)解集合。P*到P的平均距離IGD定義為d( )

ν，P 是ν與P中所有點的直線距離最小，如果|P*|能達到一定值，IGD從某種程度上代表P的兩個性能指標。IGD值越小，表示P與P*的PF越接近

4.3 實驗設(shè)置

這里將NSGA-III和MOEA/D作為對比算法，因為這兩種算法均使用了PBI分解方法。我們使用CDEAM、NSGA-III和MOEA/D來處理表1中的四個測試問題，每種算法分別獨立運行30次，取均值來作為算法最終性能，并且比較三者所得結(jié)果來分析所提出的CDEAM算法的性能。

表2 目標函數(shù)個數(shù)、參考點數(shù)目和種群規(guī)模參數(shù)設(shè)置

表2給出了目標函數(shù)的個數(shù)、參考點的數(shù)目和種群規(guī)模，表3給出了CDEAM、NSGA-III和MOEA/D的一些其他參數(shù)設(shè)置。

表3 CDEAM、NSGA-III和MOEA/D的其他參數(shù)

4.4 實驗結(jié)果

對于DTLZ1測試函數(shù)，當目標個數(shù)為5和8時，IGD值都小于NSGA-III和MOEA/D，而當在目標個數(shù)為15時，IGD值大于NSGA-III和MOEA/D，但是IGD值小于MOEA/D。由此可以看出，若目標數(shù)小于15維，CSEAM算法的多樣性和收斂性的綜合性能就要優(yōu)于NSGA-III，且對于5維、8維、15維，CSEAM的綜合效果一直均好于MOEA/D；而對于DTLZ3測試函數(shù)的5、8和15維目標下，CSEAM的IGD值均小于NSGA-III和MOEA/D，整體效果要比其他兩個算法效果要好；對于DTLZ4測試函數(shù)的8維和15維，CSEAM效果均優(yōu)于NSGA-III和MOEA/D，當目標維數(shù)為5時，其效果要差于NSGA-III，但仍優(yōu)于MOEA/D，所以在較高維的DTLZ4問題上，CSEAM表現(xiàn)較好；對于DTLZ2的5維、8維情況下，算法MOEA/D均稍優(yōu)于CSEAM，在15維情況下，CSEAM算法IGD值小于MOEA/D，另外5維情況下，NSGA-III的效果稍優(yōu)于CSEAM，但是對于8維和15維的DTLZ2，CSEAM均遠優(yōu)于NSGA-III，所以對于DTLZ2測試問題，維數(shù)越高，CSEAM算法的優(yōu)勢越明顯。

表4 三種算法在DTLZ1-4測試問題上獲得的IGD均值和方差

通過實驗仿真和分析可得出，本文的算法在幾個測試問題的5維、8維和15維上，綜合性能均是最好的。其中對于DTLZ1，維數(shù)較低較有效；對于DTLZ2，維數(shù)較高整體表現(xiàn)較有效；對于DTLZ3，整體性能表現(xiàn)良好；對于DTLZ4，維數(shù)越高綜合性能越好。

5 結(jié)語

本章提出了基于相關(guān)性選擇的高維多目標優(yōu)化算法（CSEAM算法），新算法由兩部分組成，其中包括基于相關(guān)性的差分進化及多項式變異選擇，和基于相關(guān)性的種群更新選擇機制。首先，為清楚的描述相關(guān)性選擇機制的原理和操作過程，本章給出了個體和參考點相關(guān)性的概念，以及參考點的3個屬性、個體的3個屬性等概念。然后，給出了基于相關(guān)性的差分進化及多項式變異選擇以及基于相關(guān)性的種群更新選擇機制的詳細算法流程，之后對所提出的算法CSEAM整體流程做了介紹。最后，將CSEAM算法與NSGA-III算法和MOEA/D算法就解決DTLZ1、DTLZ2、DTLZ3和DTLZ4標準測試問題所得的結(jié)果進行了對比。通過對所得解集與真實的Pareto解集之間的距離即IGD指標進行分析，驗證所提出的算法CSEAM在大部分優(yōu)化問題上，獲得了更優(yōu)秀的近似解。

［1］K.PRADITWONG AND X.YA.A new multi-objective evolutionary optimization algorithm：The two-archive algo?rithm［C］//Guangzhou，China：International Conference on Computational Intelligence.Security，2006：286-291.

［2］X.ZOU，Y.CHEN，M.LIU，AND L.KANG.A new evo?lutionary algorithm for solving many-objective optimiza?tion problems［J］.IEEE Transactions On Systems，Man，and Cybernetics-Part B，2008，38（5）：1402-1412.

［3］D.K.SAXENA AND K.DEB.Non-linear dimensionality reduction procedures for certain large-dimensional multi-objective optimization problems：Employing corrent?ropy and a novel maximum variance unfolding［J］.Evolu?tionary Multi-Criterion Optimization，2007，4403（s.n.）：772-787.

［4］Korudu P，Das S，Welch SM.Multi-Objective hybrid PSO using μ-fuzzy dominance［C］.Proc.of the Genetic and Evolutionary Computation Conf，New York：ACM Press，2007.853-860.

［5］Zhang QF，Li H.MOEA/D：A multiobjective evolutionary algorithm based on decomposition［J］.IEEE Trans.on Evolutionary Computation，2007，11（6）：712-731.

［6］Li H，Zhang QF.Multiobjective optimization problems with complicated Pareto sets［J］.MOEA/D and NSGA-II.IEEE Trans.on Evolutionary Computation，2009，13（2）：284-302.

［7］Zitzler E，Brockhoff D，Thiele L.The hypervolume indica?tor revisited：On the design of Pareto-compliant indicators via weighted integration［C］.Evolutionary Multi-Criterion Optimization-EMO，Berlin：Springer-Verlag，2007.86-2287.

［8］I.GIAGKIOZIS，R.C.PURSHOUSE，AND P.J.FLEM?ING.Generalized decomposition［J］.Evolutionary Multi-Criterion optimization，2013，7811（s.n.）：428-442.

［9］Sato H，Aguirre H E，Tanaka K.Pareto partial dominance MOEA and hybrid archiving strategy included CDAS in many-objective optimization［C］//Evolutionary Computa?tion.IEEE，2010：1-8.

［10］K.LI，Q.ZHANG，S.KWONG，et al.Stable Match?ing-Based Selection in Evolutionary Multiobjective opti?mization［J］.IEEE Transaction on Evolutionary Computa?tion，2014，18（6）：909-923.

［11］A.ZHOU，Q.ZHANG，AND G.ZHANG.Aapproxima?tion model guided selection for evolutionary multi-objec?tive optimization［J］.Evolutionary Multi-Criterion Opti?miztion，2013，7811（s.n.）：398-412.

［12］K.DEB，A.SINHA，P.J.KORHONEN，AND J.WAL?LENIUS.An interactive evolutionary nulti-objective opti?mization method based on progressively approximated value functions［J］.IEEE Transactions on Evolutionary Computation，2010，14（s.n.）：723-739.

［13］K.DEB.Multi-objective optimization using evolutionary algorithms［M］.Chichester，UK：Wiley，2001.1-299.

［14］Q.ZHANG，A.ZHOU，S.Z.ZHAO，P.N.SUGAN?THAN，W.LIU，AND S.Tiwari.Multi-objective optimi?zation test instances for the cec-2009 special session and competition［M］.Singapore：Nanyang Technological University，Tech.Rep.，2008.

［15］H.Sato，H.Aguirre，and K.Tanaka.Local Dominance Using Polar Coordinates to Enhance Multi-objeetive Evo?lutionay Algorithms［J］.Proc.2004 IEEE Congresson Evolutionary Computation，2004，1（s.n.）：188-195.

［16］D A Van Velclhuizen，G B Lamont.Evolutionary Compu?tation and Convergence to a Pareto Front［C］.Late Break?ing PaPers at the Genetic Programming 1998 Conf，Cali?fornia：Stanford Bookstore，1998：221-228.