高維多目標優化算法研究綜述

過曉芳

（1.西安工業大學理學院，陜西 西安 710032；2.西安電子科技大學計算機學院，陜西 西安 710071）

0 引言

近年來，多目標優化問題的研究成果已廣泛應用于自動控制、生產調度、網絡交通、集成電路設計、化學工程和環境工程、數據庫和芯片設計、核能和機械設計等眾多領域。隨著研究問題的復雜度越來越高，優化目標的個數也不僅僅局限于2到3個，有時往往會達到4個或者甚至更多[1]。一般意義上，當多目標優化問題的優化目標個數達到3個以上時，我們將此類多目標優化問題稱為高維多目標優化問題[2]（Many-Objective Optimization，簡稱 MAP）。

進化算法作為一種基于種群的智能搜索方法，目前已經能夠成功地求解具有2、3個目標的多目標優化問題。然而，當遇到目標數目增至4個或4個以上的高維多目標優化問題時，基于Pareto支配排序的多目標進化算法在搜索能力、計算成本和可視化方面都遇到了很大的挑戰。因此，高維多目標優化問題的進化算法研究成為進化算法領域的一個難點和熱點問題。

由于高維多目標優化問題的復雜性，目前對于此類問題的算法研究尚處于起步階段，首先分析高維多目標優化問題研究存在的困難，然后對當前所提出的高維多目標進化算法進行分類概述，接下來重點總結了可降維的高維多目標優化問題的幾類目標縮減進化算法，最后給出了未來研究的方向。

1 高維多目標優化問題的基本概念

定義1(多目標優化問題和高維多目標優化問題)

高維多目標優化問題是建立在多目標優化問題的基礎上的。不失一般性，多目標優化問題（Multi-Objective Optimization，簡稱MOP）可表述[3]為：

其 x=（x1，x2，…xn）T∈X?Rn中是 n 維決策空間的決策向量，y=（y1，y2，…ym）T∈Y?Rm是 m 維目標空間的目標向量，目標函數 F（x）定義了m 個由決策空間到目標空間的映射函數，gi（x）≤0（i=1，2，…，k）是 k個約束條件。若k=0，則該多目標優化問題是一個無約束的多目標優化問題。當式(1)優化的目標數目高維過3個時，該多目標優化問題被稱為高維多目標優化問題。

通常，對于單目標優化問題，其全局最優解就是目標函數達到最優值的解，但是對于多目標優化問題來說，往往這些目標 f1（x），…fm（x）的最優函數值之間會相互沖突，不能同時達到最優值。這里，為了平衡多個相互沖突的目標，采用Pareto最優解來定義多目標優化問題的最優解。

定義2(可行解與可行域)

對于一個 x=（x1，x2，…xn）T∈X?Rn，如果 x 滿足式(1)中所有的約束條件 gi（x）≤0（i=1，2，…，k），則 x 為一個可行解。 由決策空間 X 中所有可行解構成的集合稱為可行域，記為Ω={x|x∈X∧gi（x）≤0（i=1，2，…，k）}。

定義3(Pareto支配)

對于可行域Ω中的兩個向量xA，xB，xA支配xB當且僅當滿足

定義4(Pareto最優解或非支配解)

一個解x*∈Ω被稱為Pareto最優解當且僅當在可行域Ω中x*不會被其他解x所Pareto支配，其中，?表示解之間的支配關系。即

定義5(Pareto最優解集)

Pareto最優解集(Pareto Set，簡稱PS)是決策空間中所有Pareto最優解集合。即

定義6(Pareto最優前沿)

Pareto最優解集中所有Pareto最優解在目標空間中的像構成了Pareto最優前沿(Pareto Front,簡稱PF)。

多目標優化問題通常有非常多或者無窮多個Pareto最優解，但是要找到所有的Pareto最優解往往是不太可能的，因此，希望找到盡可能多的Pareto最優解以便為決策者提供更多的選擇。在利用進化算法求解多目標優化問題的過程中，進化算法使用適應度函數引導群體向Pareto最優前沿收斂，在設計算法時需要考慮下面兩個方面：一是算法的收斂性，即希望算法的求解過程是一個不斷逼近Pareto最優解集的過程；二是算法的分布性，即要求所求出的Pareto最優解集中的非支配解盡可能均勻且寬廣的分布在目標函數空間中。

2 高維多目標優化問題研究難點

Hughes通過實驗表明基于Pareto排序多目標進化算法 (如NSGAII，SPEA2等)在具有較少目標(2個或3個)時非常有效，但是，隨著多目標優化問題目標數目的不斷增多，目前經典的求解一般多目標優化問題的多目標進化算法的搜索性能將大大下降，從而導致求出的近似Pareto最優解集的收斂性能急劇下降。對于此類問題的研究難點在于：

1）經典的多目標進化算法通常利用傳統的Pareto支配關系對個體進行適應度賦值，但是隨著目標個數的不斷增多，非支配個體在種群中所占比例將迅速上升，甚至種群中大部分個體都變為非支配解，因此，基于Pareto支配的個體排序策略會使種群中的大部分個體具有相同的排序值而導致選擇操作無法挑選出優良個體，從而使得進化算法搜索能力下降。

2）隨著目標數目的不斷增多，覆蓋Pareto Front最優解的數量隨著目標個數呈指數級增長，這將導致無法求出完整的PF前沿[4-5]。

3）對于高維多目標優化問題來說，當Pareto前沿面的維數多于3個時，我們就無法在空間中將其表示出來，這給決策者帶來了諸多不便，因此，可視化也是高維多目標優化的一個難點問題。目前，研究者們相繼提出了用決策圖、測地線圖、并行坐標圖等方法來可視化問題的Pareto前沿面。

3 高維多目標進化算法分類

目前的高維多目標優化問題按照Pareto前沿的實際維數可以分為以下兩類。一類問題是高維多目標優化問題真正的Pareto前沿所含的目標個數要小于目標空間的個數，也就是說，存在著原始目標集合的一個子集能生成與原始目標集合相同的Pareto前沿，具有該性質的原始目標集合的最小元素子集稱為非冗余目標集，而原始目標集合中去掉非冗余目標集的剩余目標稱為冗余目標，此類問題稱為含有冗余的高維多目標優化問題，求解此類問題的方法就是利用目標縮減技術刪除這些冗余目標，從而確定構造Pareto最優前沿所需的最少目標數目，以此來達到使問題得到簡化的目標。與此類問題相對的是一類不含冗余目標的高維多目標優化問題，其分類結構圖如1所示。

對于不含冗余目標的高維多目標優化問題來說，非支配個體在種群中所占比例隨著目標個數的增加迅速上升，利用傳統的Pareto支配關系大大削弱了算法進行排序與選擇的效果，導致進化算法搜索能力下降。所以，處理此類問題的方法大致分為三種：一是采用松馳的Pareto排序方式對傳統的Pareto排序方式進行修改，從而增強算法對非支配個體的排序和選擇能力，進一步改善算法的收斂性能；二是采用聚合或分解的方法將多目標優化問題整合成單目標優化問題求解。三是基于評價指標的方法：基于評價指標的高維多目標進化算法(Indicator-based Evolutionary Algorithm簡稱IBEA)的基本思想是利用評價非支配解集優劣的某些指標作為評價個體優劣的度量方式并進行適應度賦值，從而將原始的高維多目標問題轉化為以優化該指標為目標的單目標優化問題。直接應用一些評價指標代替Pareto支配關系以指導進化算法的搜索過程。

4 含有冗余目標的高維多目標優化問題的目標縮減算法

求解含有冗余目標的高維多目標優化問題的方法就是利用目標縮減技術尋找并刪除冗余目標，從而確定構造Pareto最優前沿所需的最少目標數目。處理含有冗余目標的高維多目標優化問題的方法大致分為兩種：一種是基于目標之間相互關系的目標縮減方法，另一種是基于保持個體間Pareto支配關系的目標縮減方法。下面介紹兩類算法的基本思想。

（1）基于目標之間相互關系的目標縮減方法

此方法首先利用多目標進化算法獲得的非支配解集合作為樣本數據來分析目標之間的相互關系，然后通過分析目標間相關性的強弱來尋找冗余目標。2005年，Deb等提出了基于主成分分析法的高維多目標問題的目標縮減方法（PCA-NSGAII）。該算法將進化算法NSGAII和刪除冗余目標的過程相結合，目標間的相關性是通過分析非支配集的相關系數來得到的，并由此生成目標集合中兩兩目標間的相互關系矩陣，然后通過分析相互關系矩陣的特征值和特征向量來提取互不相關沖突目標來表示原始目標集合，從而達到目標縮減的目的。Jaimes等提出了基于無監督特征選擇技術的目標縮減方法來求解高維多目標優化問題。在該方法中，原始目標集按照目標間的相互關系矩陣劃分成若干個均勻的分區。算法將目標間的沖突關系類比于點之間的距離，兩個目標間的沖突性越強，則它們在目標空間中對應的兩點之間的距離越遠。算法要尋找的冗余目標是在聯系最緊密的分區中尋找的。

（2）基于保持個體間Pareto支配關系的目標縮減方法

Brockhoff等研究了一種基于Pareto支配關系的目標縮減方法，該方法認為如果某個目標的存在與否對非支配解集中個體之間的Pareto支配關系沒有影響或影響很小，則可以將其視為冗余目標刪除。他們在其文獻中定義了目標集合間相互沖突的定義，并提出了兩種目標縮減算法δ－MOSS和k－MOSS，使得在一定誤差允許下保留非支配解集中個體間的非支配關系。

另外，HK Singh提出了一種新的基于Pareto支配關系的目標縮減方法，(Pareto Corner Search Evolutionary Algorithm and Objective Reduction簡稱PCSEA)，該算法將一些具有代表性的處于邊界區域的非支配解作為辨識冗余目標的樣本點集，并通過逐個刪除每個目標能否保持樣本集中解的非支配性來辨識冗余目標。

高維多目標優化問題的求解算法是科學研究和工程實踐領域的一個非常重要的研究課題，同時亦是目前進化算法領域的一個研究熱點問題之一。但是由于問題求解復雜，當前的研究成果還較少，還有待進一步研究和探討。今后，對于高維多目標優化問題的求解算法的進一步研究可以從以下幾個方面展開：

1）引入新的非支配個體的評價機制。在高維多目標優化問題中，基于Pareto支配關系的個體排序策略由于缺乏選擇壓力而無法將位于不同區域的非支配個體區分開來，所以如何設計新的非支配個體的評價機制對這些個體進行比較和排序，既能保證搜索能力不受目標個數增加的影響，又能得到Pareto最優解。

2）探索新的目標縮減算法。為了減輕高維目標所帶來的高額的計算成本，目標縮減技術仍然是當前求解高維多目標優化問題的一個重要方向。

3）多種策略融合。在高維多目標優化問題的求解過程中，將基于分解的技術和新的個體適應度賦值策略相結合，既能有效的增加個體在選擇操作中的選擇壓力，又能在進化過程中更好地維持種群的多樣性。

［1］Purshouse R C,Fleming P J.Evolutionary many objective optimization：An exploratory analysis[C]//Proc of 2003 IEEE Congress on Evolutionary Computation.Canberra：IEEE Service Center,2003：2066-2073.

［2］孔維健.高維多目標進化算法研究綜述[J].控制與決策,2010,25(3)：321-326.

［3］公茂果,焦李成,楊咚咚,等.進化多目標優化算法研究[J].軟件學報,2009,2(20)：271-289.