多目標優化非支配集構造方法的研究進展

李志強，藺想紅

西北師范大學計算機科學與工程學院，蘭州 730070

多目標優化非支配集構造方法的研究進展

李志強，藺想紅

西北師范大學計算機科學與工程學院，蘭州 730070

1 引言

最優化問題是工程實踐和科學研究中主要的問題形式之一，其中目標函數超過一個并且需要同時處理的最優化問題被稱為多目標優化問題[1-2]（MOP）。通常情況下，同一問題中的多個目標函數相互制約，是彼此矛盾的，因此最終結果是獲得一系列折衷解的集合，稱為Pareto最優解集（Pareto Optimal Set）或非支配解集（Non-dominated Set）。

多目標進化算法（Multi-Objective Evolutionary Algorithm，MOEA）是一類模擬生物進化機制而形成的全局性概率優化搜索方法，特別適合用于解決多目標優化問題，已被成功應用于多目標優化領域。近年來，MOEA的研究進入了快速發展階段，越來越多的研究者開始致力于MOEA的設計與實現，因此MOEA的應用也日益廣泛。大多數研究者都著眼于用MOEA解決實際問題，而關于MOEA理論方面的研究成果比較少，例如非支配解集的構造方法、算法的性能評價準則、MOEA的測試以及測試問題的構造等方面。

縱觀國內外該領域的研究情況，認為有必要對基于Pareto非支配集構造方法的研究現狀作一個全面的介紹。本文首先介紹了多目標優化問題以及用于解決MOP的一般框架，然后描述了目前主要用于構造非支配集幾種方法的基本思路，并分析了各自的效率，最后總結和展望了多目標優化非支配集構造方法研究的未來發展趨勢。

2 多目標優化問題的數學描述

MOP的解并不局限于單個解，而可能有多個解，求解MOP就是求其Pareto最優解集。不失一般性，一個具有n維決策向量，m維子目標的多目標優化問題描述如下：

其中，x=(x1，x2，…，xn)∈X，y=(y1，y2，…，ym)∈Y。x表示n維的決策向量，X表示n維的決策空間，y表示m維的目標向量，Y表示m維的目標空間。目標函數f(x)定義了m個由決策向量空間向目標空間的映射函數，該問題具有a個不等式約束和b個等式約束，確定了決策變量可行的取值范圍。關于Pareto的一些基本概念如下：

3 多目標進化算法的一般框架

由于MOEA種類較多，所采用的方法和技術有較大差異，本文主要是基于Pareto的多目標進化算法。這類算法解決MOP的一般框架，如圖1所示：MOEA從一組隨機產生的初始種群P出發，通過對種群執行選擇、交叉和變異等進化操作，生成后代群體Q，根據定義1選擇P和Q中的非支配個體組合成非支配群體R，然后按照某種策略對非支配集R進行調整，一方面使R滿足大小要求，同時也盡量使保留在R的非支配個體具有好的分布性，之后判斷是否滿足終止條件，若滿足終止條件，則結束，否則將R中的個體復制到P中并繼續下一趟進化。保留上一代非支配集，并使之參與新一代的進化操作，從而使新一代的非支配集不比上一代差。這樣經過多代進化，種群中個體的適應度不斷提高，從而進化群體的非支配集逐步逼近真正的最優前沿。

圖1 多目標進化算法的基本框架圖

MOEA中的每個個體對應一個解，非支配解也稱為非支配個體，支配解也稱為支配個體。非支配解通常不止一個，構成了一個非支配集，又稱為歸檔集。

MOEA的一個重要步驟就是構造進化群體的非支配解集，并使非支配集不斷地逼近Pareto前沿的過程。每一代中非支配個體的集合稱為進化群體的非支配集，實際上就是當前進化群體的最優個體集合。因此，如何研究構造一個多目標進化Pareto非支配集，實際上就是研究如何構造進化群體的非支配集。然而，進化算法的每一代進化，都要構造一次非支配集，因而構造非支配集的效率將直接影響多目標進化算法的運行效率。由此可見，高效的非支配解集構造方法是MOEA研究的重要內容。

4 非支配集的主要構造方法

關于多目標進化Pareto非支配集的構造方法，國內外研究人員做了許多工作，下面就詳細地概括當前非支配集的構造方法研究的基本現狀。

（1）等級排序法

Deb等[3]提出了NSGA-II算法，它是迄今為止最優秀的進化多目標優化算法之一。其構造非支配集的方法是首先根據個體之間的支配關系計算組合種群中每個個體的等級值，然后再計算每個個體的擁擠距離，最后根據個體的等級值和擁擠距離構造新群體。

文獻[4]又提出了全方位非支配等級排序的方法，首先對組合種群進行等級排序，然后對各等級中的個體按照其支配關系分別構造各個等級的非支配集。

Rio等[5]基于新的等級策略提出了改進的NSGA-II算法，其思路是依次對每個目標進行排序，并按目標分別記錄每個個體的位置，然后按照所有目標個體的位置總和對個體等級賦值。這樣具有相同位置的個體其等級是一樣，以此進行構造非支配集，算法的效率得到了提高。

（2）遞歸法

基于分治技術，Kung等[6]采用遞歸的思想，提出了從向量集合中尋找一組最大向量集的方法：按第一個目標值的大小進行排序，在此基礎上不斷地進行遞歸調用。

Jensen[7]擴展了Kung的分治向量排序算法，提出了一種構造非支配集的算法，首先對群體進化預排序，通過遞歸調用的方法構造非支配集，降低了時間復雜度。但是當目標數目M很大時，算法的效率不斷地降低，而復雜度卻不斷地增加。

Fang等[8]根據分治算法的思想，通過引入支配樹這種新的數據結構，用于記錄所有群體比較的支配信息，從而減少了非支配個體之間的比較次數，提高了算法效率。

（3）快速排序法

文獻[9-10]通過快速排序建立索引表的方式，提出了一種總體優前劣后檢查方法，它不直接求原集合的非支配集而是轉化成求一個整型集合的非支配集；它制定一個總體上非支配個體在前、支配個體在后的檢查序列，并以盡可能少的比較次數檢查一個個體的非支配性，一旦發現后面的個體全是支配的，則終止搜索。當非支配集較大時，該算法具有較高的效率。

Zheng等[11]基于快速排序的思想構造進化群體的非支配集，每次選取一個或兩個個體作為比較對象，將構造集以比較對象為中心分成兩部分：一部分是比較對象支配的個體，這些個體不再進入以后的比較；第二部分是支配比較對象的個體或者是相互不被支配的，若沒有個體支配比較對象，則比較對象是非支配個體從而加入到非支配集中。如此，再將第二部分中的個體看做構造集重復以上過程，直到構造集為空時結束。此方法當群體中非支配個體比較多時，到了排序后期有可能形成慢速現象。

Du等[12]通過對每個目標值的大小進行快速排序，然后根據目標值分別記錄每個個體的得分值，進而求出所有個體的總得分值，再按總得分值排序得到新的求和序列，最后根據求和序列找出其中的非支配個體，并刪除支配個體，從而構造非支配集。此方法采用得分和求和序列的提高技術來減少計算復雜度。

Mishra等[13]也是基于類似的思想構造非支配集的。首先根據第一個目標值的大小進行快速排序得到一排序列表，然后將排序列表中的每個個體與非支配集的個體比較，如果此個體被非支配集中的任一個體支配，將此個體從排序列表中刪除；如果非支配集中的個體被此個體支配，則刪除非支配集中的個體；如果非支配集中沒有個體支配此個體，則把此個體加入到非支配集中。

（4）排除法

排除法[14]的思路是：將進化群體中的每個個體依次與非支配集中的個體比較，如果群體中的個體支配非支配集的個體，將非支配集中的個體刪除（即排除掉），如果群體中的個體不被非支配集中任何一個個體所支配，則群體中的個體加入到非支配集中。此方法，非支配集中的個體不一定是非支配的。

（5）莊家法

莊家法[15]的思路是：從構造集中任選一個個體出任莊家，由莊家對其他個體進行支配比較，并將莊家所支配的個體淘汰出局，如果莊家個體不被任何其他個體所支配，則莊家個體即為非支配個體，否則莊家個體在該趟比較結束時也被淘汰出局。按照這種方法進行下一趟比較，直至構造集為空，每一趟比較不一定能構造出一個新的非支配個體。

（6）擂臺賽法

擂臺賽法[16]的思想是：從構造集中任選一個個體出任擂主，由擂主與其他個體進行支配比較，敗者被淘汰出局，勝者成為新擂主，并繼續與剩下的其他個體進行比較，最后的擂主即為非支配個體。按照這種方法繼續找出其他非支配個體，直至構造集為空。每一趟比較能構造出一個新的非支配個體，此方法具有比較高的構造非支配集的效率。

（7）選舉法

用選舉法[17]構造非支配集的思路是：從構造集中選出兩個個體擔任候選競選個體，保證兩個候選競選個體互不支配，再依次從構造集中選取一個個體與兩個候選競選個體進行比較，敗者被淘汰出局，勝者成為新的候選競選個體。若競選個體發生替換，則還要再次比較這兩個候選競選個體，淘汰弱者，以保證它們互不支配，并繼續該趟比較，一趟比較后，兩個候選競選個體即為非支配個體。按照此方法進行下一趟比較，直至構造集為空。此算法在構造非支配集上有較高的效率。

（8）歸一化法

歸一化法[18]是基于歸一化的思想的，首先計算進化群體中每個個體多目標值的歸一化和，按照個體間的支配關系建立進化群體中所有個體從大到小的全排序。排序隊列的第一個個體是非支配個體，直接進入非支配集，排序隊列中的其他個體依次與非支配集中的非支配個體比較，不被支配的個體就進入非支配集。每一代進化群體中的個體只需要與非支配集中的非支配個體比較，從而減少了比較次數。

（9）偽二叉樹法

偽二叉樹法[19]是根據個體間的支配關系，從進化群體中選出一個個體，將該個體與當前非支配集中的個體進行比較，淘汰被支配的個體，而未被淘汰的個體將插入到非支配集中第一個被淘汰個體的位置。依次進行，直到進化群體中的個體比較完畢，從而生成排序的偽二叉樹。當目標數較大時(M≥5)，構造非支配集的效率比較高。

（10）爬山法和演繹法

最近McClymont等[20]提出了爬山排序和演繹排序法，用于非支配集的構造。爬山法是根據支配個體尋找非支配的個體的過程，首先從一個個體出發，當遇到支配個體時，標記并丟棄此支配個體，接著比較剩余的沒有被標記的個體，當遇到非支配個體時，把非支配個體插入到當前前沿中，然后爬山排序移動到其不相關的個體，重復以上過程直到所有個體都被分配賦值。

演繹排序法實現了推理支配，不同于爬山排序法。首先對群體中的個體編號，從第一個個體開始依次作為比較對象，與所有以下的個體進行比較（不比較先前個體），標記被比較對象支配的個體，這些個體以后不再考慮，若有個體支配比較對象，標記比較對象并選擇下一個體為比較對象，直至最后一個編號的個體。

目前，國內外研究人員所提出的幾類非支配解集的構造方法，其時間復雜度也都不同。而MOEA在每一次迭代時都要構造Pareto非支配集，因此構造Pareto非支配集的效率對MOEA的運行效率有很大的影響。表1給出了以上所有構造非支配集方法的時間復雜度。

表1 各種構造方法的時間復雜度

表中，M表示目標函數的數目，N表示種群中個體的數目，L為非支配個體的數目。從以上構造多目標Pareto非支配集的方法可以看出，其特點是：非支配解的產生是通過構造集中個體的依次比較來實現的，大多數算法都是盡可能地減少個體之間的比較次數，以提高非支配集的構造效率；多數算法每一趟的比較最多只能找到一個非支配解。

5 結論和展望

多目標進化算法特別適合用于解決多目標優化問題，能同時處理一組可能的解，并在一次算法過程中就可以找到Pareto最優解集中的多個解。目前，多目標進化算法的研究在國內外發展很快，并取得了許多研究成果，也得到了不少研究者的關注，但是多目標進化算法理論及其應用還值得更加深入地研究和完善。近年來，也有一些研究者致力于構造多目標Pareto非支配集，這就非常有必要從理論上論證，對于一個有M個目標的優化問題，構造Pareto非支配集最小的計算復雜度，其中主要的時間開銷在于非支配集的構造上，因此一個快速的構造非支配集的算法有利于提高MOEA的效率。

對于一個多目標優化問題，一般的思路是先通過各種進化算法構造非支配集，并使其擴散到整個Pareto前沿。雖然MOEA已經受到越來越多的關注，但在MOEA的發展和應用過程中，仍有大量問題值得研究和探索。進一步可能的研究方向包括：

（1）構造效率。多目標Pareto非支配解集的構造效率是一個值得關注的問題，特別是應用到解決實際問題的時候。提高效率的方式主要有兩種：一種是改進現有的構造方法；而另外一種方式是優化現有的構造方法，合理地設計算法的數據結構來提高運行效率[21-22]。在實際應用方面，第二種方式就非常值得重視。

（2）多策略結合的優勢。對于多目標Pareto非支配集構造而言，當非支配集的大小超過了約定值時，可以采用聚類方法[23]來降低非支配集的大小，用于維持群體的多樣性。另外，文獻[24]結合人工免疫系統模擬免疫學功能、原理和模型，用于構造非支配集，當問題的目標數比較多時，其效率比較高。現有的大多數構造方法都集中在非支配集的搜索，很少考慮到決策者的偏好，結合特定的偏好信息[25-27]能有效地縮小搜索空間。因此，如何將決策者的偏好信息結合到構造非支配集方法中，使所得的結果主要集中在決策者所感興趣的區域，也是非常值得研究的內容。

[1]Deb M.Multi-objective optimization using evolutionary algorithms[M].Chichester，UM：John Wiley&Sons，2001.

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

[3]Deb K，Pratap A，Agarwal S，et al.A fast elitist multi-objective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[4]Deb K，Tiwari S.Omni-optimizer：a procedure for single and multi-objective optimization[M]//Coello Coello C A，Hernandez A A，Zitzler E.Evolutionary Multi-Criterion Optimization.[S.l.]：Springer，2003：47-61.

[5]Rio G L，Dsouza K，Chandra S，et al.Improved NSGA-II based on a novel ranking scheme[J].Journal of Computing，2010，2：91-95.

[6]Kung H T，Luccio F，Preparata F P.On finding the maxima of a set of vectors[J].Journal of the ACM，1975，22：469-476.

[7]Jensen M T.Reducing the run-time complexity of multi-objective EAs：the NSGA-II and other algorithms[J].IEEE Transactions on Evolutionary Computation，2003，7（5）：503-515.

[8]Fang H，Wang Q，Tu Y C，et al.An efficient non-dominated sortingmethodforevolutionaryalgorithms[J].Evolutionary Computation，2008，16（3）：355-384.

[9]Ding L，Zeng S，Kang L.A fast algorithm on finding the nondominated set in multi-objective optimization[C]//Proceedings of International Conference on Evolutionary Computation，2003.

[10]曾三友，李輝，丁立新，等.基于排序的非劣集合快速求解算法[J].計算機研究與發展，2004，41（9）：1565-1571.

[11]Zheng J，Ling C，Shi Z，et al.A multi-objective genetic algorithm based on quick sort[C]//Proceedings of 17th Conference of the Canadian Society for Computational Studies of Intelligence，Canadian AI，2004，3060：175-186.

[12]Du J，Cai Z，Chen Y.A sorting based algorithm for finding non-dominated set in multi-objective optimization[C]//Proceedings of the 3rd International Conference on Natural Computation（ICNC2007），2007，4：436-440.

[13]Mishra K K，Harit S.A fast algorithm for finding the non dominated set in multi objective optimization[J].International Journal of Computer Applications，2010，25（1）：35-39.

[14]李麗榮，鄭金華.基于Pareto Front的多目標遺傳算法[J].湘潭大學自然科學學報，2004，26（1）：39-41.

[15]Zheng J，Shi Z，Ling C，et al.A new method to construct the non-dominated set in multi-objective genetic algorithms[C]// Proceedings of the International Conference on Intelligent Information Processing（IIP2004），Beijing China，2004.

[16]鄭金華，蔣浩，鄺達，等.用擂臺賽法則構造多目標Pareto最優解集的方法[J].軟件學報，2007，18（6）：1287-1297.

[17]楊平，鄭金華，李密青，等.一種快速構造多目標Pareto非支配集的方法：選舉法則[J].計算機應用研究，2009，26（2）：488-491.

[18]鮑培明，朱慶保.用于多目標進化的歸一化排序非支配集構造方法[J].電子學報，2009，37（9）：23-28.

[19]胡煥耀，董渭清.用偽二叉樹法則構造多目標Pareto最優解集的方法[J].西安交通大學學報，2009，43（2）：29-32.

[20]McClymont K，Keedwell E.Deductive sort and climbing sort：new methods for non-dominated sorting[J].Evolutionary Computation，2012，20（1）：1-26.

[21]Mostaghim S，Teich J.Quad-trees：a data structure for storing Pareto-sets in multi-objective evolutionary algorithms with elitism[M]//EvolutionaryComputationBasedMulti-criteria Optimization：Theoretical Advances and Applications.[S.l.]：Springer，2005：81-104.

[22]Shi C，Yan Z，Lu K.A dominance tree and its application in evolutionary multi-objective optimization[J].International Journal of Information Sciences，2009，179（20）：3540-3560.

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

[24]Zhou X，Shen J，Shen J.An immune recognition based algorithm for finding non-dominated set in multi-objective optimization[C]//Proceedings of the IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application，2008，1：305-310.

[25]Coello Coello C A.Handling preferences in evolutionary multiobjective optimization：a survey[C]//Proceedings of the Congress on Evolutionary Computation，New Jersey，2000：30-37.

[26]Thiele L，Miettinen K，Korhonen P J，et al.A preference-based evolutionaryalgorithmformultiobjectiveoptimization[J]. Evolutionary Computation，2009，17（3）：411-436.

[27]Sindhya K，Ruiz A B，Miettinen K.A preference based interactive evolutionary algorithm for multi-objective optimization：PIE[C]//Proceedingsofthe6thInternationalConference on Evolutionary Multi-Criterion Optimization（EMO2011），2011，6576：212-225.

LI Zhiqiang,LIN Xianghong

School of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China

Constructing the multi-objective optimization non-dominated set is an important step in the Multi-Objective Evolutionary Algorithm（MOEA）.It aims to study the operational efficiency to solve Multi-objective Optimization Problem（MOP）by MOEA.Firstly,the MOP is described as well as the basic framework of solving algorithm is given.Next,several non-dominated set building methods based on Pareto are discussed including their computational complexity.Finally,the future trends of this research filed are concluded and prospected.

Multi-Objective Evolutionary Algorithm（MOEA）;Multi-objective Optimization Problem（MOP）;non-dominated set;Pareto front

多目標優化非支配集的構造是多目標進化算法研究領域的一個重要步驟，旨在研究用多目標進化算法解決多目標優化問題的效率。對多目標優化問題進行了描述并且給出了求解算法的一般框架，結合研究現狀討論了目前該領域幾種主要的基于Pareto非支配集的構造算法，以及它們的計算時間復雜度；總結并展望了該領域未來的發展趨勢。

多目標進化算法（MOEA）；多目標優化問題（MOP）；非支配集；Pareto前沿

A

TP18

10.3778/j.issn.1002-8331.1305-0004

LI Zhiqiang,LIN Xianghong.Research advance of multi-objective optimization non-dominated set construction methods. Computer Engineering and Applications,2013,49（19）：31-35.

國家自然科學基金（No.61165002）；甘肅省自然科學基金（No.1010RJZA019）。

李志強（1987—），男，碩士研究生，研究領域為神經信息學，進化計算；藺想紅（1976—），男，博士，副教授，研究領域為神經網絡,進化計算與人工生命。E-mail：lzq115@163.com

2013-05-07

2013-07-01

1002-8331（2013）19-0031-05