多目標優(yōu)化非支配集構(gòu)造方法的研究進展

李志強，藺想紅

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

多目標優(yōu)化非支配集構(gòu)造方法的研究進展

李志強，藺想紅

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

1 引言

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

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

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

2 多目標優(yōu)化問題的數(shù)學(xué)描述

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

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

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

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

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

MOEA中的每個個體對應(yīng)一個解，非支配解也稱為非支配個體，支配解也稱為支配個體。非支配解通常不止一個，構(gòu)成了一個非支配集，又稱為歸檔集。

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

4 非支配集的主要構(gòu)造方法

關(guān)于多目標進化Pareto非支配集的構(gòu)造方法，國內(nèi)外研究人員做了許多工作，下面就詳細地概括當前非支配集的構(gòu)造方法研究的基本現(xiàn)狀。

（1）等級排序法

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

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

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

（2）遞歸法

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

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

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

（3）快速排序法

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

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

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

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

（4）排除法

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

（5）莊家法

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

（6）擂臺賽法

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

（7）選舉法

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

（8）歸一化法

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

（9）偽二叉樹法

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

（10）爬山法和演繹法

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

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

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

表1 各種構(gòu)造方法的時間復(fù)雜度

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

5 結(jié)論和展望

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

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

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

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

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

[2]鄭金華.多目標進化算法及其應(yīng)用[M].北京：科學(xué)出版社，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].計算機研究與發(fā)展，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].湘潭大學(xué)自然科學(xué)學(xué)報，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]鄭金華，蔣浩，鄺達，等.用擂臺賽法則構(gòu)造多目標Pareto最優(yōu)解集的方法[J].軟件學(xué)報，2007，18（6）：1287-1297.

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

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

[19]胡煥耀，董渭清.用偽二叉樹法則構(gòu)造多目標Pareto最優(yōu)解集的方法[J].西安交通大學(xué)學(xué)報，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

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

多目標進化算法（MOEA）；多目標優(yōu)化問題（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.

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

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

2013-05-07

2013-07-01

1002-8331（2013）19-0031-05