吳坤安，嚴宣輝，陳振興

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

1 引言

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

自從Schaffer首次將矢量評價遺傳算法VEGA[2]應用于MOPs求解以來，各種各樣的多目標進化算法從傳統(tǒng)的進化算法到成熟的最新技術(shù)都已被廣泛應用到不同的領(lǐng)域中?；谒惴ㄋ捎玫倪x擇機制，這些多目標進化算法可劃分為以下三類：聚集函數(shù)法、基于群體的方法、基于Pareto的方法。聚集函數(shù)方法是將被優(yōu)化的所有子目標聚集為單個目標，從而將多目標優(yōu)化問題轉(zhuǎn)化成單目標的優(yōu)化問題。這種方法的最大困難在于怎樣設置每個目標的權(quán)值；基于群體的方法主要依靠群體的進化來實現(xiàn)分別搜索，每一代進化時，依次針對每個子目標利用比例選擇法產(chǎn)生r子群體，每個子群體大小為N/r（N為進化群體大小，r為子目標數(shù)），各子群體獨立的執(zhí)行進化操作，然后，再將r個子群體合并為一個群體大小為N的總?cè)后w，并執(zhí)行進化操作。這種方法的缺點是對于一個好的折衷解，考慮了所有的子目標，但它對于單個子目標來說就不是最優(yōu)解，這樣的解在選擇操作時可能會被“丟棄”。目前，大多數(shù)多目標進化算法歸屬于基于Pareto的方法，該方法的主要特征是在選擇機制中融入了Pareto最優(yōu)的概念，具有代表性的算法有 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]。相關(guān)研究還可參看文獻[7-9]。

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

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

2 Pareto多目標優(yōu)化問題的相關(guān)定義

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

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

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

記作xA?xB。

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

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

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

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

3 PHMOEA算法設計與描述

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

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

3.1 種群的構(gòu)造

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

圖1 算法原始狀態(tài)

圖2 干擾集產(chǎn)生

圖3 干擾集的作用

3.2 交叉算子

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

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

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

3.3 變異算子

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

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

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

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

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

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

3.4 種群維護

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

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

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

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

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

圖4 PHMOEA與NSGA-II在ZDT函數(shù)上50次迭代結(jié)果

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

3.5 算法主要流程

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

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

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

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

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

步驟5若不滿足終止條件，轉(zhuǎn)步驟2。

步驟6否則，算法終止，現(xiàn)有種群即為所得Pareto最優(yōu)解集。

4 性能測試實驗與結(jié)果

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

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

表1 算法參數(shù)值設置

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

[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]公茂果，焦李成，楊咚咚，等.進化多目標優(yōu)化算法研究[J].軟件學報，2009，20（2）：271-289.

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

[9]劉鎏，李敏強.多目標優(yōu)化進化算法及應用研究[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，F(xiàn)leming 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.