高維多目標(biāo)優(yōu)化算法研究綜述

過曉芳

（1.西安工業(yè)大學(xué)理學(xué)院，陜西 西安 710032；2.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710071）

0 引言

近年來(lái)，多目標(biāo)優(yōu)化問題的研究成果已廣泛應(yīng)用于自動(dòng)控制、生產(chǎn)調(diào)度、網(wǎng)絡(luò)交通、集成電路設(shè)計(jì)、化學(xué)工程和環(huán)境工程、數(shù)據(jù)庫(kù)和芯片設(shè)計(jì)、核能和機(jī)械設(shè)計(jì)等眾多領(lǐng)域。隨著研究問題的復(fù)雜度越來(lái)越高，優(yōu)化目標(biāo)的個(gè)數(shù)也不僅僅局限于2到3個(gè)，有時(shí)往往會(huì)達(dá)到4個(gè)或者甚至更多[1]。一般意義上，當(dāng)多目標(biāo)優(yōu)化問題的優(yōu)化目標(biāo)個(gè)數(shù)達(dá)到3個(gè)以上時(shí)，我們將此類多目標(biāo)優(yōu)化問題稱為高維多目標(biāo)優(yōu)化問題[2]（Many-Objective Optimization，簡(jiǎn)稱 MAP）。

進(jìn)化算法作為一種基于種群的智能搜索方法，目前已經(jīng)能夠成功地求解具有2、3個(gè)目標(biāo)的多目標(biāo)優(yōu)化問題。然而，當(dāng)遇到目標(biāo)數(shù)目增至4個(gè)或4個(gè)以上的高維多目標(biāo)優(yōu)化問題時(shí)，基于Pareto支配排序的多目標(biāo)進(jìn)化算法在搜索能力、計(jì)算成本和可視化方面都遇到了很大的挑戰(zhàn)。因此，高維多目標(biāo)優(yōu)化問題的進(jìn)化算法研究成為進(jìn)化算法領(lǐng)域的一個(gè)難點(diǎn)和熱點(diǎn)問題。

由于高維多目標(biāo)優(yōu)化問題的復(fù)雜性，目前對(duì)于此類問題的算法研究尚處于起步階段，首先分析高維多目標(biāo)優(yōu)化問題研究存在的困難，然后對(duì)當(dāng)前所提出的高維多目標(biāo)進(jìn)化算法進(jìn)行分類概述，接下來(lái)重點(diǎn)總結(jié)了可降維的高維多目標(biāo)優(yōu)化問題的幾類目標(biāo)縮減進(jìn)化算法，最后給出了未來(lái)研究的方向。

1 高維多目標(biāo)優(yōu)化問題的基本概念

定義1(多目標(biāo)優(yōu)化問題和高維多目標(biāo)優(yōu)化問題)

高維多目標(biāo)優(yōu)化問題是建立在多目標(biāo)優(yōu)化問題的基礎(chǔ)上的。不失一般性，多目標(biāo)優(yōu)化問題（Multi-Objective Optimization，簡(jiǎn)稱MOP）可表述[3]為：

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

通常，對(duì)于單目標(biāo)優(yōu)化問題，其全局最優(yōu)解就是目標(biāo)函數(shù)達(dá)到最優(yōu)值的解，但是對(duì)于多目標(biāo)優(yōu)化問題來(lái)說(shuō)，往往這些目標(biāo) f1（x），…fm（x）的最優(yōu)函數(shù)值之間會(huì)相互沖突，不能同時(shí)達(dá)到最優(yōu)值。這里，為了平衡多個(gè)相互沖突的目標(biāo)，采用Pareto最優(yōu)解來(lái)定義多目標(biāo)優(yōu)化問題的最優(yōu)解。

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

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

定義3(Pareto支配)

對(duì)于可行域Ω中的兩個(gè)向量xA，xB，xA支配xB當(dāng)且僅當(dāng)滿足

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

一個(gè)解x*∈Ω被稱為Pareto最優(yōu)解當(dāng)且僅當(dāng)在可行域Ω中x*不會(huì)被其他解x所Pareto支配，其中，?表示解之間的支配關(guān)系。即

定義5(Pareto最優(yōu)解集)

Pareto最優(yōu)解集(Pareto Set，簡(jiǎn)稱PS)是決策空間中所有Pareto最優(yōu)解集合。即

定義6(Pareto最優(yōu)前沿)

Pareto最優(yōu)解集中所有Pareto最優(yōu)解在目標(biāo)空間中的像構(gòu)成了Pareto最優(yōu)前沿(Pareto Front,簡(jiǎn)稱PF)。

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

2 高維多目標(biāo)優(yōu)化問題研究難點(diǎn)

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

1）經(jīng)典的多目標(biāo)進(jìn)化算法通常利用傳統(tǒng)的Pareto支配關(guān)系對(duì)個(gè)體進(jìn)行適應(yīng)度賦值，但是隨著目標(biāo)個(gè)數(shù)的不斷增多，非支配個(gè)體在種群中所占比例將迅速上升，甚至種群中大部分個(gè)體都變?yōu)榉侵浣猓虼?，基于Pareto支配的個(gè)體排序策略會(huì)使種群中的大部分個(gè)體具有相同的排序值而導(dǎo)致選擇操作無(wú)法挑選出優(yōu)良個(gè)體，從而使得進(jìn)化算法搜索能力下降。

2）隨著目標(biāo)數(shù)目的不斷增多，覆蓋Pareto Front最優(yōu)解的數(shù)量隨著目標(biāo)個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)，這將導(dǎo)致無(wú)法求出完整的PF前沿[4-5]。

3）對(duì)于高維多目標(biāo)優(yōu)化問題來(lái)說(shuō)，當(dāng)Pareto前沿面的維數(shù)多于3個(gè)時(shí)，我們就無(wú)法在空間中將其表示出來(lái)，這給決策者帶來(lái)了諸多不便，因此，可視化也是高維多目標(biāo)優(yōu)化的一個(gè)難點(diǎn)問題。目前，研究者們相繼提出了用決策圖、測(cè)地線圖、并行坐標(biāo)圖等方法來(lái)可視化問題的Pareto前沿面。

3 高維多目標(biāo)進(jìn)化算法分類

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

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

4 含有冗余目標(biāo)的高維多目標(biāo)優(yōu)化問題的目標(biāo)縮減算法

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

（1）基于目標(biāo)之間相互關(guān)系的目標(biāo)縮減方法

此方法首先利用多目標(biāo)進(jìn)化算法獲得的非支配解集合作為樣本數(shù)據(jù)來(lái)分析目標(biāo)之間的相互關(guān)系，然后通過分析目標(biāo)間相關(guān)性的強(qiáng)弱來(lái)尋找冗余目標(biāo)。2005年，Deb等提出了基于主成分分析法的高維多目標(biāo)問題的目標(biāo)縮減方法（PCA-NSGAII）。該算法將進(jìn)化算法NSGAII和刪除冗余目標(biāo)的過程相結(jié)合，目標(biāo)間的相關(guān)性是通過分析非支配集的相關(guān)系數(shù)來(lái)得到的，并由此生成目標(biāo)集合中兩兩目標(biāo)間的相互關(guān)系矩陣，然后通過分析相互關(guān)系矩陣的特征值和特征向量來(lái)提取互不相關(guān)沖突目標(biāo)來(lái)表示原始目標(biāo)集合，從而達(dá)到目標(biāo)縮減的目的。Jaimes等提出了基于無(wú)監(jiān)督特征選擇技術(shù)的目標(biāo)縮減方法來(lái)求解高維多目標(biāo)優(yōu)化問題。在該方法中，原始目標(biāo)集按照目標(biāo)間的相互關(guān)系矩陣劃分成若干個(gè)均勻的分區(qū)。算法將目標(biāo)間的沖突關(guān)系類比于點(diǎn)之間的距離，兩個(gè)目標(biāo)間的沖突性越強(qiáng)，則它們?cè)谀繕?biāo)空間中對(duì)應(yīng)的兩點(diǎn)之間的距離越遠(yuǎn)。算法要尋找的冗余目標(biāo)是在聯(lián)系最緊密的分區(qū)中尋找的。

（2）基于保持個(gè)體間Pareto支配關(guān)系的目標(biāo)縮減方法

Brockhoff等研究了一種基于Pareto支配關(guān)系的目標(biāo)縮減方法，該方法認(rèn)為如果某個(gè)目標(biāo)的存在與否對(duì)非支配解集中個(gè)體之間的Pareto支配關(guān)系沒有影響或影響很小，則可以將其視為冗余目標(biāo)刪除。他們?cè)谄湮墨I(xiàn)中定義了目標(biāo)集合間相互沖突的定義，并提出了兩種目標(biāo)縮減算法δ－MOSS和k－MOSS，使得在一定誤差允許下保留非支配解集中個(gè)體間的非支配關(guān)系。

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

高維多目標(biāo)優(yōu)化問題的求解算法是科學(xué)研究和工程實(shí)踐領(lǐng)域的一個(gè)非常重要的研究課題，同時(shí)亦是目前進(jìn)化算法領(lǐng)域的一個(gè)研究熱點(diǎn)問題之一。但是由于問題求解復(fù)雜，當(dāng)前的研究成果還較少，還有待進(jìn)一步研究和探討。今后，對(duì)于高維多目標(biāo)優(yōu)化問題的求解算法的進(jìn)一步研究可以從以下幾個(gè)方面展開：

1）引入新的非支配個(gè)體的評(píng)價(jià)機(jī)制。在高維多目標(biāo)優(yōu)化問題中，基于Pareto支配關(guān)系的個(gè)體排序策略由于缺乏選擇壓力而無(wú)法將位于不同區(qū)域的非支配個(gè)體區(qū)分開來(lái)，所以如何設(shè)計(jì)新的非支配個(gè)體的評(píng)價(jià)機(jī)制對(duì)這些個(gè)體進(jìn)行比較和排序，既能保證搜索能力不受目標(biāo)個(gè)數(shù)增加的影響，又能得到Pareto最優(yōu)解。

2）探索新的目標(biāo)縮減算法。為了減輕高維目標(biāo)所帶來(lái)的高額的計(jì)算成本，目標(biāo)縮減技術(shù)仍然是當(dāng)前求解高維多目標(biāo)優(yōu)化問題的一個(gè)重要方向。

3）多種策略融合。在高維多目標(biāo)優(yōu)化問題的求解過程中，將基于分解的技術(shù)和新的個(gè)體適應(yīng)度賦值策略相結(jié)合，既能有效的增加個(gè)體在選擇操作中的選擇壓力，又能在進(jìn)化過程中更好地維持種群的多樣性。

［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］孔維健.高維多目標(biāo)進(jìn)化算法研究綜述[J].控制與決策,2010,25(3)：321-326.

［3］公茂果,焦李成,楊咚咚,等.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào),2009,2(20)：271-289.