多目標進化算法綜述

梅志偉

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

關鍵詞：多目標優化；進化算法；支配；分解

DOIDOI：10.11907/rjdk.171169

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2017）006-0204-04

0 引言

在人們的實際生活中，大多數優化問題都是多目標優化問題，廣泛存在于經濟管理、工程實踐和科學研究等領域中。當前，多目標優化在理論和應用方面均取得了不少進展，但是由于多目標優化問題的復雜性，因此仍存在大量挑戰。

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

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

1 多目標進化問題概述

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

2 多目標進化算法一般流程

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

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

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

3 多目標進化算法分類

從進化算法誕生之初，由于其在多目標優化問題上的優異表現，眾多研究人員提出了多種多目標進化算法。根據算法特性不同，具體可分為以下幾類：

3.1 基于Pareto支配關系的多目標進化算法

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

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

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

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

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

3.2 基于分解的多目標進化算法

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

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

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

3.3 基于指標的多目標進化算法

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

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

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

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

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

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

3.4 混合算法

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

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

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

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

4 結語

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

參考文獻：

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

（責任編輯：黃 健）