多目標(biāo)進化算法綜述

梅志偉

摘要：基于種群的進化算法在一次運行中能夠產(chǎn)生一組近似的 Pareto 最優(yōu)解集，因此多目標(biāo)進化算法成為處理多目標(biāo)優(yōu)化問題中的主流方法。介紹了多目標(biāo)優(yōu)化問題中的數(shù)學(xué)模型以及相關(guān)定義，根據(jù)多目標(biāo)進化算法的特點，將現(xiàn)有算法分為4類并分別進行闡述，同時分析了它們的優(yōu)缺點。

關(guān)鍵詞：多目標(biāo)優(yōu)化；進化算法；支配；分解

DOIDOI：10.11907/rjdk.171169

中圖分類號：TP301

文獻標(biāo)識碼：A 文章編號：1672-7800（2017）006-0204-04

0 引言

在人們的實際生活中，大多數(shù)優(yōu)化問題都是多目標(biāo)優(yōu)化問題，廣泛存在于經(jīng)濟管理、工程實踐和科學(xué)研究等領(lǐng)域中。當(dāng)前，多目標(biāo)優(yōu)化在理論和應(yīng)用方面均取得了不少進展，但是由于多目標(biāo)優(yōu)化問題的復(fù)雜性，因此仍存在大量挑戰(zhàn)。

多目標(biāo)優(yōu)化問題中往往存在多個彼此相互沖突的目標(biāo)。與單目標(biāo)優(yōu)化不同，在多目標(biāo)優(yōu)化中，提高一個目標(biāo)的性能會引起其它一個或多個目標(biāo)性能的下降。因此，多目標(biāo)優(yōu)化問題中不存在一個單獨的最優(yōu)解，而是存在一組表示各個目標(biāo)間權(quán)衡和折中關(guān)系的解集，稱該解集為Pareto最優(yōu)解集。Pareto最優(yōu)解集在目標(biāo)域的投影被稱為Pareto前沿。

由于很多現(xiàn)實工程問題中的優(yōu)化問題是NP難，傳統(tǒng)的數(shù)學(xué)規(guī)劃方法將會變得異常困難。而具有自然界規(guī)律啟發(fā)式特征的求解方法往往適合近似求解這些困難問題，這些方法被稱為進化計算[1]。進化算法基于種群的特性使其十分適合多目標(biāo)優(yōu)化問題的求解。同時，進化算法還具有魯棒性強的特點。因此，進化算法被廣泛應(yīng)用在多目標(biāo)優(yōu)化問題的求解上。

1 多目標(biāo)進化問題概述

多目標(biāo)優(yōu)化問題同時優(yōu)化多個目標(biāo)，這些待優(yōu)化的目標(biāo)包含最大化、最小化或者兩者都有的問題。在實際處理時，為了簡化問題，可以將最大化或最小化問題取反，使所有優(yōu)化目標(biāo)全部轉(zhuǎn)化成最小化或最大化問題。本文中將討論最小化問題。

2 多目標(biāo)進化算法一般流程

生物進化是一個不斷優(yōu)化的過程，在不斷的變化過程中增加自身的適應(yīng)性。進化計算以生物進化為啟發(fā)，對一個解進行抽象編碼，模擬生物進化中的基因。進化算法以種群為基礎(chǔ)，是一個黑盒的搜索、優(yōu)化方法，進化算法不需要優(yōu)化問題具備一定的前提條件，例如連續(xù)性、可微性等，且一次運行能夠產(chǎn)生一組解。因此，進化算法特別適合處理多目標(biāo)優(yōu)化問題。

生物的進化過程主要包括繁殖、變異、競爭和選擇。與之類似，一個典型的進化算法主要包含以下步驟：①初始化：生成一個初始化種群，記為P，其中包含N個個體（解），并記當(dāng)前代數(shù)t=0；②適應(yīng)度評價：計算每個個體x∈P的適應(yīng)度值F（x）；③繁殖：從父代種群P繁殖出后代種群Q，具體包括交叉和變異過程；④選擇：使用選擇算子從P∪Q中選擇出N個精英個體，作為下一代的父代種群P；⑤下一代進化：增加進化代數(shù)t=t+1，如果滿足終止條件，則停止算法并輸出P，否則進入下一代迭代過程，即轉(zhuǎn)入第2步。

一個典型的進化算法流程如圖1所示。

3 多目標(biāo)進化算法分類

從進化算法誕生之初，由于其在多目標(biāo)優(yōu)化問題上的優(yōu)異表現(xiàn)，眾多研究人員提出了多種多目標(biāo)進化算法。根據(jù)算法特性不同，具體可分為以下幾類：

3.1 基于Pareto支配關(guān)系的多目標(biāo)進化算法

通過Pareto支配關(guān)系，可以對兩個解進行對比，從而利用支配信息指導(dǎo)解集的選擇?；赑areto支配關(guān)系的多目標(biāo)進化算法一直以來都是一個熱門研究方向，研究人員提出了許多算法，例如SPEA[2]、SPEA2[3]、PESA[4]、PESA-II[5]、NSGA-II[6]等。

基于Pareto支配的多目標(biāo)進化算法取得了令人矚目的成就，然而在處理超多目標(biāo)優(yōu)化問題時卻面臨許多挑戰(zhàn)。由于Pareto支配的特性，超多目標(biāo)空間中的大部分解均為非支配關(guān)系，從而失去了選擇壓力。研究人員通過改進Pareto支配關(guān)系，提出了一系列方法。

Laummans等[7]定義了一種ε支配關(guān)系，增加了一個解的支配空間；Deb等[8]根據(jù)ε支配關(guān)系，提出了ε-MOEA算法，在超多目標(biāo)優(yōu)化問題中取得了較好效果。ε-MOEA算法將目標(biāo)空間劃分成網(wǎng)格，不同網(wǎng)格中的解使用ε支配關(guān)系進行比較，相同網(wǎng)格中的解則使用傳統(tǒng)的Pareto支配關(guān)系。

2001年，Ikeda等[9]也提出了一種新的支配關(guān)系，稱為α支配。在α支配關(guān)系中，比較一個目標(biāo)的同時會考慮其它目標(biāo)函數(shù)值。通過一個線性平衡函數(shù)重新計算對比時的目標(biāo)值，若一個解在一個目標(biāo)上顯著優(yōu)于另一個解，而在另一個目標(biāo)上則略微處于弱勢，則前者仍然能α支配后者，這樣的支配關(guān)系有利于選擇更好的解。

除此之外，還有多種算法建立在改進的Pareto支配關(guān)系之上，例如基于網(wǎng)格支配的GrEA算法[10]、基于ε排序策略的εR-EMO算法[11]等。

3.2 基于分解的多目標(biāo)進化算法

將一個多目標(biāo)優(yōu)化問題分解為一組單目標(biāo)的子問題進行求解也是一個常見的解決方法。常見的分解方法包括加權(quán)和法、切比雪夫法以及基于懲罰值的邊界交叉法[12]。

2007年，Zhang等[13]結(jié)合了上述幾種分解方法提出了一種基于分解的多目標(biāo)進化算法（MOEA/D），這是近年來的一個熱門算法框架。在MOEA/D算法中，通過傳統(tǒng)的分解方法將一個多目標(biāo)優(yōu)化問題分解為一組單目標(biāo)的子問題，然后使用進化算法同時求解這些子問題。MOEA/D還通過權(quán)重向量之間的距離關(guān)系定義了子問題間的鄰居關(guān)系。在優(yōu)化一個子問題時，通過相鄰子問題間交叉變異的進化過程生成新解，并使用新解來更新當(dāng)前子問題的解。MOEA/D中還引入了一種鄰居子問題間的信息共享方法，即一個新解在更新對應(yīng)子問題的同時還會更新其鄰居子問題。實驗表明，MOEA/D算法相較于以往的一些基于分解的算法，效果更為突出。Li等[14]將差分進化的思想引入到MOEA/D的進化過程中，同時還限制了鄰居子問題的最大更新數(shù)目，進一步提高了算法性能。

與基于Pareto支配關(guān)系的算法在超多目標(biāo)優(yōu)化問題中的局限不同，基于分解的算法能夠直接適用于超多目標(biāo)優(yōu)化問題中。針對超多目標(biāo)優(yōu)化問題的特性，研究人員也提出了許多改進方法。Asafuddoula等[15]將系統(tǒng)抽樣和自適應(yīng)的ε控制技術(shù)引入到基于分解的進化算法中，在超多目標(biāo)空間中生成均勻的權(quán)重向量，平衡解集的收斂性與多樣性；為了解決超多目標(biāo)空間選擇壓力過大導(dǎo)致的多樣性丟失問題，F(xiàn)abre等[16]提出了一種并行的遺傳算法，將每個子問題都關(guān)聯(lián)到一個子種群，通過子種群的進化實現(xiàn)整個種群的進化，實驗結(jié)果也驗證了其在多樣性保持方面的優(yōu)勢。

3.3 基于指標(biāo)的多目標(biāo)進化算法

多目標(biāo)進化算法求得的解集可以通過許多評價指標(biāo)來衡量，基于指標(biāo)的多目標(biāo)進化算法通過評價指標(biāo)來指引算法的搜索方向，指導(dǎo)進化過程中新種群的選擇。

Zitzler等[17]首先將評價指標(biāo)引入到進化算法的選擇策略中，提出一種基于評價指標(biāo)的進化算法（IBEA），可以通過任意一種評價指標(biāo)來對比候選解。在IBEA中，不需要使用例如適應(yīng)值共享等多樣性保持策略，也不需要對整個近似Pareto最優(yōu)解集進行計算，只需對比其中的部分解即可。

IH指標(biāo)可以衡量一個解集的質(zhì)量，IH指標(biāo)值越大，表示解集質(zhì)量越好。為了能夠最大化一個解集的IH指標(biāo)值，Emmerich等[18]提出了一種基于S-度量選擇的多目標(biāo)進化算法（SMS-EMOA）。SMS-EMOA通過IH指標(biāo)的梯度信息來指導(dǎo)種群進化過程。在處理低維的多目標(biāo)優(yōu)化問題時，SMS-EMOA求得的解集具有很好的收斂性和多樣性。但是，在面對超多目標(biāo)優(yōu)化問題時，SMS-EMOA的計算復(fù)雜度成指數(shù)上升，算法效果急劇下降。其每一代進化的計算復(fù)雜度為O（Nm/2+1），其中N為種群大小，m為問題的目標(biāo)個數(shù)。

Brockhoff等[19]將目標(biāo)空間縮小技術(shù)與基于IH指標(biāo)的方法結(jié)合起來，提出一種新的算法，通過使用不同的目標(biāo)空間縮小方法提高基于IH指標(biāo)的算法性能。

IH指標(biāo)的計算是一個非常耗時的過程，對基于IH指標(biāo)的算法有很大影響。為了克服計算過于復(fù)雜的弊端，Bader等[20]提出了一種快速的近似計算方法，使用蒙特卡羅模擬近似計算解集的IH值，并提出了一種基于IH指標(biāo)近似的多目標(biāo)進化算法，在處理超多目標(biāo)優(yōu)化問題上取得了令人滿意的成果。

通過將非支配排序和R2指標(biāo)結(jié)合起來，Manriquez等[21]提出了R2-MOGA和R2-MODE算法，在處理超多目標(biāo)優(yōu)化問題時有顯著優(yōu)勢；Gomez等[22]也提出了一種基于R2指標(biāo)的優(yōu)化算法MOMBI，同樣也取得了不錯的優(yōu)化效果。

3.4 混合算法

在多目標(biāo)進化算法中，研究人員提出了眾多優(yōu)化技術(shù)，不同技術(shù)均有其獨特優(yōu)勢，例如基于Pareto支配關(guān)系的算法能夠適應(yīng)各種形狀的Pareto前沿，但在處理超多目標(biāo)優(yōu)化問題時卻顯得不盡如人意；基于分解的算法通用性較好，但是常規(guī)的分解方法卻容易導(dǎo)致解集多樣性的丟失。其它的優(yōu)化技術(shù)也各有優(yōu)缺點。將這些技術(shù)混合起來，結(jié)合各種方法的優(yōu)點來處理復(fù)雜的優(yōu)化問題，也是一種非常有效的方法。

一種方法是將全局搜索與局部搜索結(jié)合起來，即多目標(biāo)模因算法。例如，在Adra等[23]的算法中，對每一代進化中求得的最優(yōu)解使用局部搜索策略在目標(biāo)空間進一步優(yōu)化，隨后將優(yōu)化后的解映射到對應(yīng)的決策空間并預(yù)測其具體的決策向量；在Wang等[24]的算法中，則使用局部搜索來生成子代解。

另一種廣泛使用的方法是將不同方法中的搜索策略結(jié)合起來，例如將粒子群優(yōu)化和進化算法結(jié)合起來[25]，在每一代中，由粒子群優(yōu)化產(chǎn)生的解再使用進化算法進行優(yōu)化。

另一方面，還可以根據(jù)進化過程的不同特性將整個進化過程劃分為多個階段，在不同階段使用不同的搜索策略。例如在Yang等[26]的算法中，進化過程包含3個階段，分別側(cè)重于被支配的解、平衡支配解和非支配解，以及著重于非支配解3個部分，結(jié)合NSGA-II算法的思想和局部增強搜索策略來實現(xiàn)各個階段的進化過程。

4 結(jié)語

多目標(biāo)進化算法由于其基于種群的特性而成為處理多目標(biāo)優(yōu)化問題的一種熱門方法。本文進行了多目標(biāo)優(yōu)化問題的相關(guān)數(shù)學(xué)描述，簡要介紹了相關(guān)理論定義。根據(jù)多目標(biāo)進化算法的特性，本文還將近年來的主流進化算法分為4類進行闡述，并分析了它們的優(yōu)缺點，以更好地應(yīng)用于多目標(biāo)優(yōu)化問題的求解。

參考文獻：

[1]POOLE D，MACKWORTH A，GOEBEL R.Computational intelligence：a logical approach[M].Oxford University Press，1997.

[2]ZITZLER E，THIELE L.Multiobjective evolutionary algorithms：a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271.

[3]ZITZLER E，LAUMANNS M，THIELE L.SPEA2：improving the strength Pareto evolutionary algorithm[C].Eurogen，2001，3242（103）：95-100.

[4]CORNE D W，KNOWLES J D，OATES M J.The Pareto envelope-based selection algorithm for multiobjective optimization[C].International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg，2000：839-848.

[5]CORNE D W，JERRAM N R，KNOWLES J D，et al.PESA-II：region-based selection in evolutionary multiobjective optimization[C].Proceedings of the Genetic And Evolutionary Computation Conference （GECCO2001），2001.

[6]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.

[7]LAUMANNS M，THIELE L，DEB K，et al.Combining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation，2002，10（3）：263-282.

[8]DEB K，MOHAN M，MISHRA S.Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions[J].Evolutionary Computation，2005，13（4）：501-525.

[9]IKEDA K，KITA H，KOBAYASHI S.Failure of pareto-based MOEAs：does non-dominated really mean near to optimal？[C].Evolutionary Computation，Proceedings of the 2001 Congress on.IEEE，2001：957-962.

[10]YANG S，LI M，LIU X，et al.A grid-based evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2013，17（5）：721-736.

[11]AGUIRRE H，TANAKA K.Space partitioning with adaptive ε-ranking and substitute distance assignments：a comparative study on many-objective mnk-landscapes[C].Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation.ACM，2009：547-554.

[12]MIETTINEN K.Nonlinear multiobjective optimization[M].Springer Science & Business Media，2012.

[13]ZHANG Q，LI H.MOEA/D：A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.

[14]LI H，ZHANG Q.Multiobjective optimization problems with complicated Pareto sets，MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation，2009，13（2）：284-302.

[15]ASAFUDDOULA M，RAY T，SARKER R.A decomposition-based evolutionary algorithm for many objective optimization[J].IEEE Transactions on Evolutionary Computation，2015，19（3）：445-460.

[16]GARZA-FABRE M，TOSCANO-PULIDO G，COELLO C A C，et al.Effective ranking+ speciation= many-objective optimization[C].2011 IEEE Congress of Evolutionary Computation （CEC）.IEEE，2011：2115-2122.

[17]ZITZLER E，KNZLI S.Indicator-based selection in multiobjective search[C].International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg，2004：832-842.

[18]EMMERICH M，BEUME N，NAUJOKS B.An EMO algorithm using the hypervolume measure as selection criterion[C].International Conference on Evolutionary Multi-Criterion Optimization.Springer Berlin Heidelberg，2005：62-76.

[19]BROCKHOFF D，ZITZLER E.Improving hypervolume-based multiobjective evolutionary algorithms by using objective reduction methods[C].2007 IEEE Congress on Evolutionary Computation.IEEE，2007：2086-2093.

[20]BADER J，ZITZLER E.HypE：an algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation，2011，19（1）：45-76.

[21]DAZ-MANRQUEZ A，TOSCANO-PULIDO G，COELLO C A C，et al.A ranking method based on the R2 indicator for many-objective optimization[C].2013 IEEE Congress on Evolutionary Computation.IEEE，2013：1523-1530.

[22]GMEZ R H，COELLO C A C.MOMBI：a new metaheuristic for many-objective optimization based on the R2 indicator[C].2013 IEEE Congress on Evolutionary Computation，2013：2488-2495.

[23]ADRA S F，DODD T J，GRIFFIN I A，et al.Convergence acceleration operator for multiobjective optimization[J].IEEE Transactions on Evolutionary Computation，2009，13（4）：825-847.

[24]WANG Y，CAI Z，GUO G，et al.Multiobjective optimization and hybrid evolutionary algorithm to solve constrained optimization problems[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B （Cybernetics），2007，37（3）：560-575.

[25]ELHOSSINI A，AREIBI S，DONY R.Strength Pareto particle swarm optimization and hybrid EA-PSO for multi-objective optimization[J].Evolutionary Computation，2010，18（1）：127-156.

[26]YANG D，JIAO L，GONG M.Adaptive multi-objective optimization based on nondominated solutions[J].Computational Intelligence，2009，25（2）：84-108.

（責(zé)任編輯：黃 ?。?