一種基于Pareto排序的混合多目標進化算法

吳坤安，嚴宣輝，陳振興

福建師范大學 數學與計算機科學學院，福州 350007

1 引言

最優化問題是工業設計、城市規劃和管理科學領域廣泛研究和探討的問題，其中僅有一個目標函數的最優化問題稱為單目標優化問題，目標函數超過一個并且需要同時處理的最優化問題稱為多目標優化問題（Multi-objective Optimization Problems，MOPs）。對于多目標優化問題，一個解對于某個目標來說可能是較好的，而對于其他目標來講可能是較差的。因此，存在一個折衷解的集合，稱為Pareto最優解集（Pareto-optimal set）或非支配解集（non-dominated set）[1]。

自從Schaffer首次將矢量評價遺傳算法VEGA[2]應用于MOPs求解以來，各種各樣的多目標進化算法從傳統的進化算法到成熟的最新技術都已被廣泛應用到不同的領域中。基于算法所采用的選擇機制，這些多目標進化算法可劃分為以下三類：聚集函數法、基于群體的方法、基于Pareto的方法。聚集函數方法是將被優化的所有子目標聚集為單個目標，從而將多目標優化問題轉化成單目標的優化問題。這種方法的最大困難在于怎樣設置每個目標的權值；基于群體的方法主要依靠群體的進化來實現分別搜索，每一代進化時，依次針對每個子目標利用比例選擇法產生r子群體，每個子群體大小為N/r（N為進化群體大小，r為子目標數），各子群體獨立的執行進化操作，然后，再將r個子群體合并為一個群體大小為N的總群體，并執行進化操作。這種方法的缺點是對于一個好的折衷解，考慮了所有的子目標，但它對于單個子目標來說就不是最優解，這樣的解在選擇操作時可能會被“丟棄”。目前，大多數多目標進化算法歸屬于基于Pareto的方法，該方法的主要特征是在選擇機制中融入了Pareto最優的概念，具有代表性的算法有 Niched Pareto Genetic Algorithm（NPGA）[3]、Nondominated Sorting Genetic Algorithm（NSGA）以及其改進版本 NSGA-II[4]，Pareto Envelope-based Selection Algorithm for Multiobjective Optimization（PESA）以及其改進版本 PESAII[5]，Strength Pareto Evolutionary Algorithm（SPEA）以及其改進版本SPEA2[6]。相關研究還可參看文獻[7-9]。

在多目標進化算法的研究中，如何提升算法的收斂性和解集的多樣性是算法設計的兩個核心內容。在基于Pareto優化的多目標進化算法中，進化過程中每一代的主要工作就是構造非支配集以逐步地逼近Pareto前沿面，所以非支配集的構造是算法的重點。多目標進化的交叉、變異算子的參數，一般靠人為經驗設置且固定不變，這不僅存在很大的偶然性而且對算法的收斂性和多樣性都有影響。一些算法如NSGA-II采用的模擬二進制交叉算子SBX（Simulated Binary Crossover），對解空間搜索能力相對較弱，也一定程度上影響了算法的性能。

針對上面的問題，提出一種基于Pareto排序的混合多目標進化算法PHMOEA（HybridMulti-objective Evolutionary Algorithm Based on the Pareto Sort）。主要改進思想有以下幾點：（1）在PHMOEA中，相入了干擾集（Interference Sets）用以刺激并優化非支配集的構造，從而改善解集的多樣性和算法的收斂性；（2）在交叉算子中利用Pareto等級來自動調整相關參數，形成在交叉過程中的自適應運算并使得優秀個體基因盡可能的得到保留；（3）在變異操作中使用差分變異策略，并引入極端集（Extreme Set）中的個體來生成差異向量，從而提高解集的分布性。

2 Pareto多目標優化問題的相關定義

多目標優化問題又稱為多標準優化問題。不失一般性，一個具有n個決策變量，m個目標變量的多目標優化問題可表述為：

其中，x=(x1，x2，…，xn)∈X?Rn為n維的決策矢量，X為n維的決策空間，y=(y1，y2，…，ym)∈Y?Rm為m維的目標矢量，Y為m維的目標空間。目標函數F(x)定義了m個由決策空間向目標空間的的映射函數；gi(x)≤0，(i=1，2，…，q)定義了q個不等式的約束；hj(x)=0，(j=1，2，…，p)定義了p個等式約束。進一步，定義集合Ω={x|gi(x)≤0，hj(x)=0}為問題的可行域。在此基礎上，給出以下幾個重要定義。

定義1（Pareto支配）設f：Rn→Rm，xA，xB∈Ω?Rn。稱個體xA支配個體xB當且僅當：

記作xA?xB。

定義2（Pareto最優解）個體x*∈Ω被稱為Pareto最優解（或非支配解），當且僅當滿足以下條件：

定義3（Pareto最優解集）Pareto最優解集是所有Pareto最優解組成的集合，定義如下：

定義4（Pareto前沿面）Pareto最優解集P*中所有Pareto最優解對應的目標矢量組成的曲面稱為Pareto前沿面PF*：

定義5（極端集）在多目標進化算法中，對于單個目標每代最優的點稱之為極值點，所有目標的極值點集合稱為極端集。

3 PHMOEA算法設計與描述

基于Pareto的多目標進化算法，是通過構造進化群體的非支配集，并使非支配集在進化過程中不斷逼近真正的Pareto最優前沿面。一個進化群體的非支配集，實際上也是當前進化群體的最優個體集合。進化算法的每一次迭代，或每一代進化，都是為了構造更好的非支配集。在算法收斂之前，這樣的非支配集是局部最優解集。由此可見，非支配集的好壞決定了進化算法的收斂性和多樣性的好壞。本文通過設置一個外部干擾集，在進化過程中通過提高算法的搜索空間來達到不斷影響并優化非支配集構造，從而提高算法的收斂性和解集的多樣性。

多目標優化算法開始時，一般很難一下定位到最優解。所以，在算法初始階段，越是難優化的問題越需要加強全局搜索能力，一旦定位到最優解的大致位置，越需要加強局部搜索能力，即加強精細的局部搜索。本文設計的交叉和變異操作都有一定自適應調整功能，較好地平衡了全局搜索與局部搜索。

3.1 種群的構造

在一般Pareto進化算法中，算法開始時隨機產生一個初始群體Pt，在此基礎上采用選擇、交叉和變異操作產生一個新群體Qt，Pt和Qt的群體規模均為N，將Pt和Qt并入到大小為2N的Rt（初始t=0）中，然后根據Pareto排序從Rt選取個體進入Pt+1，直至Pt+1的規模為N。

圖1 算法原始狀態

圖2 干擾集產生

圖3 干擾集的作用

3.2 交叉算子

針對二進制交叉算子SBX的缺點，本文采用算術交叉算法，一般以實數編碼的交叉算子公式如下：

其中，λ為參數，在進化算法中一般根據經驗設定，存在很大的偶然性。在精英保留機制的進化算法中，進化過程中的交叉運算中，都希望前一代較優的個體基因，在進化時盡可能得以保留；例如在公式（6）中，希望將前一代較優個體基因盡可能地保存在中。基于這一想法，本文重新定義了交叉算子的參數λ，讓其與個體在群體中所處的等級相關聯：

在計算運行初期，由于Pareto等級的關系，λ的變化較大，但隨著進化的發展，種群中個體都趨向同一Pareto前沿面，λ趨于常值0.5，從而實現了交叉過程中的自適應調整。由于前一代較優個體基因被保留在中，所以在后面的變異操作中，將被賦予更大的概率進行變異操作。

3.3 變異算子

極值的引用會極大地提高算法的尋優效率[10]，變異操作在引用差分算法DE[11]的基礎上，引用每代中的極值點并與所在Pareto等級相聯系：

其中，xe，G為第G代極端集中的一個極值點，xe，G為G代種群中不等于xe，G的任意個體，n為xr1，G所在Pareto等級，m為種群中Pareto等級的最大值。

在算法的初期，種群分布區域較為寬廣，個體差異較大，產生的差分向量 xe，G-xr1，G值較大，對個體xr1，G的擾動較大，從而實現算法的全局搜索。在進化的后期，種群的個體分布在最優解的附近，差分向量 xe，G-xr1，G的值較小，對個體xr1，G有微調作用，實現了算法的局部搜索。從整體上實現了變異算子的自適應操作。

為了檢驗極端值和差分變異的效果，將PHMOEA和NSGA-II算法在目標函數為2維的ZDT[12]測試函數上進行驗證；設種群大小為100，迭代次數為50代，對比結果如圖4所示。

在圖4中，Ptrue即紅線表示理論Pareto最優解。從圖4中可以看出，PHMOEA算法的多樣性明顯好于NSGA-II，并且在收斂性上也強于NSGA-II。

在利用差分策略變異后，多目標進化算法存在這樣一個問題：選擇只在vi，G+1和xr1，G這兩個個體比較支配關系后就做出取舍，顯然這樣的操作對MOEA來講是不合適的，因為在MOEA中每個個體的優劣是和整個群體的狀態相關的。為了避免上述問題，本文提出的選擇操作將所有目標個體和由其產生的全部新個體一起構建一個新群體R。然后在群體R中，根據支配關系做出選擇。

3.4 種群維護

基于Pareto排序的個體選擇可以保證解沿著Pareto前沿進化，另一方面根據個體的擁擠距離的大小比較選擇，可以使得群體的多樣性、均勻性得到有效保護與維持。按照個體的密度估計方法[4]來評價每一個個體的擁擠距離度量，群體中每一個體i有兩種可以比較的屬性：

（1）非劣級別irank，irank表示個體i在種群中所在的Pareto等級，等級越小，個體越優。

（2）擁擠距離度量idistance，idistance表示個體i在種群中的聚集距離，距離越大被選中的可能性越大。

基于此，下面介紹具體的選擇操作——擁擠二元錦標賽選擇算子，在該算子中，個體i和j在聯賽中獲勝是基于下面的兩個比較中的一個成立即可：

（1）個體i比j有比較好的非劣級別，即irank＜jrank。

圖4 PHMOEA與NSGA-II在ZDT函數上50次迭代結果

（2）若i和j有相同的非劣級別，但i有較好的擁擠距離，即irank=jrank，且idistance＞jdistance。

3.5 算法主要流程

基于Pareto排序的混合多目標進化算法PHMOEA主要流程如下：

步驟1初始化大小為N的種群Pt和空的大小為2N+M的集合Rt（初始時t=0）（參見3.1節描述）。

步驟2從初始種群Pt中用二元錦標賽方法選取個體，進行交叉操作（根據公式（6）、（7））得到Pt(c)。

步驟3對Pt(c)中的個體采用公式（8）所述變異算子，進行變異操作，得到一個新群體Pt(c+m)，Pt和Pt(c+m)的群體規模均為N。

步驟4生成大小為M的干擾集ISt，將Pt、Pt(c+m)和ISt并入到Rt中，對Rt所有個體進行Pareto分層排序，并按Pareto等級從低到高并根據需要計算某個層次中的所有個體的擁擠距離依次進入Pt+1，直至Pt+1的規模為N。

步驟5若不滿足終止條件，轉步驟2。

步驟6否則，算法終止，現有種群即為所得Pareto最優解集。

4 性能測試實驗與結果

為了驗證PHMOEA算法在多目標優化問題上的求解性能，將其與NSGA-II和SPEA2算法在Schaffer[13]、Fonseca[14]、Kursawe[15]和 2 目標的 ZDT[12]、3 目標 DTLZ[16]測試函數集上進行實驗對比。所有實驗均在硬件配置為Intel?CoreTMCPU 2.80 GHz，內存4 GB的PC上進行。

參數設置如表1（n表示決策變量個數），其中PHMOEA中干擾集的大小設為15。

表1 算法參數值設置

算法性能對比采用通用的兩個性能評價標準：

（1）Generational Distance[17]（GD）指標γ。γ測量算法最終獲得的非支配解集Q與理論Pareto最優解近似集P*的逼近程度：

式中，di為Q中第i個體與P*之間在目標空間中的最小歐式距離；γ的值越小，說明算法獲得的非支配解Q越接近真實的Pareto前沿，算法收斂性越好。

（2）Spread[17]度量指標 Δ。 Δ用來衡量算法最終獲得的非支配解集Q中個體的分布均勻性及擴展程度：

圖5 NSGA-II、SPEA2和PHMOEA求解13個測試問題的GD指標的統計盒圖

所有算法在各個測試函數上的初始種群大小NP均設置為100，迭代次數為250，交叉變異概率及其他指標同上。為了直觀地看出算法對于各種測試問題的統計結果，利用盒圖（boxplot）來統計數值。盒圖是一種統計分析的重要工具，它可以很好地反應數據的統計分布情況。本文用該工具表現NSGA-II、SPEA2、PHMOEA這3種算法獨立運行30次得到的解統計特性。其中，盒子的上下兩條線分別表示樣本的上下四分位數，盒子中間的水平線為樣本的中位數，盒子上下的虛線表示樣本的其余部分（野值除外），樣本最大值為虛線頂端，樣本最小值為虛線底端，“+”表示野值，盒子的切口為樣本的置信區間。

從圖5可以看出NSGA-II在ZDT3、DTLZ2和DTLZ3上的收斂性好于PHMOEA，在其他10個測試函數問題上PHMOEA收斂性均好于NSGA-II；而SPEA2在ZDT3、DTLZ1、DTLZ2和DTLZ3的收斂性較好，其他9個測試函數上PHMOEA效果較好。從圖6中可以看出NSGA-II算法在DTLZ1、DTLZ2、和DTLZ6的多樣性上較好，在其他10個測試函數上PHMOEA效果較好；SPEA2在DTLZ2、DTLZ4和DTLZ6多樣性較好，在其他10個測試函數問題上PHMOEA效果較好。

在PHMOEA中，由于干擾集的加入，增加了Pareto排序的時間，但算法在交叉、變異操作上的時間效率較高，因此算法整體上的時間效率并不差。實驗結果表明，PHMOEA在收斂性和多樣性綜合方面表現良好，與其他幾種著名的算法相比有一定的優勢。

5 結束語

在多目標進化算法的研究中，提升算法的收斂性和解集的多樣性是算法設計的兩個核心內容。本文提出一種基于Pareto排序的混合多目標進化算法PHMOEA，在Pareto排序的基礎上，引入了干擾集以刺激并優化非支配集的構造，從而提高算法的收斂性和解集多樣性，同時利用個體的Pareto等級和極端集改進了交叉和變異策略。通過和經典的NSGA-II和SPEA2算法在Schaffer、Fonseca、Kursawe和5個ZDT測試函數，5個DTLZ測試函數總共13個測試函數的實驗結果對比和分析，說明了本文算法的有效性。

圖6 NSGA-II、SPEA2和PHMOEA求解13個測試問題的Spread指標統計盒圖

[1]Deb K.Multi-objective optimization using evolutionary algorithms[M].Chichester UK：Wiley，2001.

[2]Schaffer J D.Multiple objective optimization with vector evaluated genetic algorithms[C]//Proc of the Int’l Conf on Genetic Algorithms and their Application，1985：93-100.

[3]Horn J，Nafpliotis N，Goldberg D E.A niched Pareto genetic algorithm for multi-objective optimization[C]//Proc of the 1st IEEE Congress on Evolutionary Computation，1994：82-87.

[4]Deb K，Pratap A，Agarwal S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[5]Corne D W，Knowles J D，Oates M J.PESA-II：regionbased selection in evolutionary multiobjective optimization[C]//Proc of the Genetic and Evolutionary Computation.SanFrancisco：MorganKaufmannPublisher，2001：283-290.

[6]Zitzler E L M，Thiele L.SPEA2：improving the strength pareto evolutionary algorithm[M]//Evolution Methods for Design，Optimization and Control with Applications to Industrial Problems.Berlin：Springer-Verlag，2002：95-100.

[7]公茂果，焦李成，楊咚咚，等.進化多目標優化算法研究[J].軟件學報，2009，20（2）：271-289.

[8]鄭金華.多目標進化算法及其應用[M].北京：科學出版社，2010.

[9]劉鎏，李敏強.多目標優化進化算法及應用研究[D].天津：天津大學，2009.

[10]胡勁松，鄭啟倫.基于極值組合分析遺傳算法之誤[J].計算機學報，2003，26（12）：1759-1764.

[11]Storn R，Price K.Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997，11（4）：341-359.

[12]Zitzler E，Deb K，Thiele L.Comparison of multi-objective evolutionary：empirical results[J].Evolutionary Computation，2000，8（2）：173-195.

[13]Schaffer J D.Multi-objective optimization with vector evaluated genetic algorithms[C]//Proc of Int Conf on Genetic Algorithms and Their Applications，1985：93-100.

[14]Fonseca C M，Fleming P J.Multiobjective optimization and multiple constrant handling with evolutinary algorithms—Part II[J].IEEE Trans on Syst，Man：Cybern A，1998，28：38-47.

[15]Kursawe F.A variant of evolution stragies for vector optimization[M]//Parallel Problem Solving from Nature-PPSN.Berlin：Springer，1991：193-197.

[16]Deb K，Thiele L，Laumanns M，et al.Scalable test problems for evolutionary multiobjective optimization[M]//Evolutionary Multiobjective Optimization，Theoretical Advance and Applications.Berlin Germany：Springer-Verlag，2005：825-830.

[17]Lixin T，Xianpeng W.A hybrid multiobjective evolutionary algorithm formultiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation，2013，17（1）：20-45.