張淑艷 段鵬松 鄒衛(wèi)琴

（1.鄭州大學 軟件技術(shù)學院，河南 鄭州 450000；2.江西理工大學 軟件學院，江西 南昌 330000）

多目標優(yōu)化問題MOPs(Multi objective Optimization Problems)是工程實踐和科學研究中的主要問題形式之一，廣泛存在于優(yōu)化控制、機械設(shè)計、數(shù)據(jù)挖掘、移動網(wǎng)絡(luò)規(guī)劃和邏輯電路設(shè)計等問題中。MOPs有多個目標，且各目標相互沖突。對于MOPs，通常存在一個折衷的解集(即Pareto最優(yōu)解集)，解集中的各個解在多目標之間進行權(quán)衡。獲取具有良好收斂性及分布性的解集是求解MOPs的關(guān)鍵。

1 問題定義

最小化MOPs的一般描述如下：

min F（x）＝（f1（x），f2（x），…，fm（x））

其中解x＝（x1，x2，…，xn）∈Ω為在決策空間Ω中的n維決策向量，f1（x），f2（x），…，fm（x）為 m 個相互沖突的目標函數(shù)。 對于解 x1，x2∈Ω，x1支配 x2（記作 x1?x2），當且僅當?i∈（1，2，…，m）使得 fi（x1）≤fi（x2），且?i∈｛1，2，…，m｝，使得 fi（x1）≤fi（x2）。解 x*∈Ω 為 Pareto 最優(yōu)解，當且僅當不存在解x∈Ω，使得x?x*。Pareto最優(yōu)解的集合稱為Pareto 最優(yōu)解集（記作 P*），P*＝｛x*∈Ω｜﹁?x∈Ω：x?x*｝。 Pareto 最優(yōu)解集P*在目標空間的映射稱為真實Pareto前沿面 （記作PF*），PF*＝｛F（x*）＝（f1（x*），f2（x*），…，fm（x*））｜x*∈P*｝。若 x1?x2，則稱 x2為支配解。解集P'被稱為非支配解集，當且僅當P'中不含支配解。

2 多目標優(yōu)化算法

目前，大量算法用于求解MOPs。通常，可以將求解MOPs的算法分為兩類。

第一類算法，將MOPs轉(zhuǎn)化為單目標優(yōu)化問題。算法為每個目標設(shè)置權(quán)值，通過加權(quán)的方式將多目標轉(zhuǎn)化為單目標。經(jīng)過改變權(quán)值大小，多次求解MOPs可以得到多個最優(yōu)解，構(gòu)成非支配解集[1]。

第二類算法，直接求解MOPs。這類算法主要依靠進化算法。進化算法這種面向種群的全局搜索法，對于直接得到非支配解集是非常有效的。基于進化算法的多目標優(yōu)化算法被稱為多目標進化算法。根據(jù)其特性，多目標進化算法可以劃分為兩代[2]。

（1）第一代算法：以適應(yīng)度共享機制為分布性策略，并利用Pareto支配關(guān)系設(shè)計適應(yīng)度函數(shù)。代表算法如下。VEGA將種群劃分為若干子種群，每個子種群相對于一個目標進行優(yōu)化，最終將子種群合并。MOGA根據(jù)解的支配關(guān)系，為每個解分配等級，算法按照等級為解設(shè)置適應(yīng)度函數(shù)。NSGA采用非支配排序的思想為每個解分配虛擬適應(yīng)度值，在進化過程中，算法根據(jù)虛擬適應(yīng)度值采用比例選擇法選擇下一代。NPGA根據(jù)支配關(guān)系采用錦標賽選擇法，當解的支配關(guān)系相同時，算法使用小生境技術(shù)選擇最優(yōu)的解進入下一代。

（2）第二代算法：以精英解保留機制為特征，并提出了多種較好的分布性策略。代表算法如下。NSGA－II降低了非支配排序的復(fù)雜度，并提出了基于擁擠距離的分布性策略。SPEA2提出了新的適應(yīng)度分配策略和基于環(huán)境選擇的分布性策略。PESA－II根據(jù)網(wǎng)絡(luò)超格選擇個體并使用了基于擁擠系數(shù)的分布性策略。

近年來，在求解MOPs上，新的算法框架也在不斷提出。粒子群算法、分布估計算法、分解算法等已被逐漸用于求解MOPs。

3 評估方法

求解MOPs通常得到一個非支配解集，而解集的評估相對于單個解的評估更加復(fù)雜。目前存在多種方法評估非支配解集的質(zhì)量。通常，對非支配解集的評估分為兩個方面[3]。一方面，是收斂性，即評估非支配解集在目標空間與真實Pareto前沿面的趨近程度。常用方法有錯誤率、覆蓋率、世代距離、高維空間及其比率、基于聚集距離的趨近度評價方法等；另一方面，是分布性，即評估非支配解集在目標空間分布的廣度和均勻度，常用方法有空間評價方法、基于個體信息的評價方法、網(wǎng)格分布評價方法、個體空間的分布度評價方法、基于聚類的評價函數(shù)等。

4 測試用例

算法性能的評估需要客觀的測試用例。Schaffer、Kursawe和Deb分別在1985年、1991年和1999年提出了較簡單的兩目標優(yōu)化測試用例SCH、KUR和DEB。Zitzler、Deb和Thiele在2000年提出了6個兩目標優(yōu)化測試用例 ZDT1～ZDT6。 Deb、Thiele、Laumanns和 Zitzler在2002年提出了 7個多目標優(yōu)化測試用例 DTLZ1～DTLZ7，DTLZ1～DTLZ7的決策變量和目標數(shù)可以擴展到任何數(shù)目[4]。上述測試用例均無約束，其Pareto最優(yōu)解集和真實Pareto前沿面可在(http://www.cs.cinvestav.mx/～emoobook/)下載。 Liu在 2008年為 CEC2009提出了 23個更加復(fù)雜的測試用例 CF1～CF10、R2－DTLZ2、R3－DTLZ3、WFG1 和CF1～CF10。其中CF1～CF7為7個無約束兩目標優(yōu)化測試用例，CF8～CF10 為 3 個無約束三目標優(yōu)化測試用例，R2－DTLZ2、R3－DTLZ3、WFG1為3個無約束五目標優(yōu)化測試用例，CF1～CF7為7個帶約束兩目標優(yōu)化測試用例，CF8～CF10為3個帶約束三目標優(yōu)化測試用例。CEC2009的測試用例的問題描述、Pareto最優(yōu)解集和真實Pareto前沿面 可 在 網(wǎng) 站 (http://dces.essex.ac.uk/staff/qzhang/moeacompetition09.htm)下載。

5 挑戰(zhàn)和困難

由于MOPs與現(xiàn)實應(yīng)用的密切相關(guān)性，MOPs面臨許多研究課題：

（1）現(xiàn)有大部分求解MOPs的算法都基于進化算法，新的算法框架亟待提出。

（2）對多目標優(yōu)化算法的評估需要能夠客觀反映算法優(yōu)劣的評估方法和一組測試用例。評估方法和測試用例的選擇和設(shè)計，是一個研究的關(guān)鍵問題。

（3）現(xiàn)有多目標優(yōu)化算法各有其優(yōu)缺點，某個算法對求解一個問題是有效的，而對求解另一個問題可能是無效的。那么如何使各算法的優(yōu)缺點互補也是一個尚待研究的問題。

6 結(jié)論

MOPs在工程實踐和科學研究中是非常重要的。本文通過對MOPs的問題定義、多目標優(yōu)化算法、評估方法、測試用例四個方面對MOPs的相關(guān)問題進行闡述，最后分析了求解MOPs的挑戰(zhàn)和困難。

［1］P.Hajela and C.Y.Lin.Genetic search strategies in multicriterion optimal design[J].Structural and Multidisciplinary Optimization,1992,4(2):99－107.

［2］Coello Coello,C.A.Evolutionary Multi－Objective Optimization:A Historical View of the Field[J].IEEE Computational Intelligence Magazine,2006,1(1):28－36.

［3］鄭金華.多目標進化算法及其應(yīng)用[M].北京：科學出版社，2007.

［4］公茂果,焦李成,楊咚咚,馬文萍.進化多目標優(yōu)化算法研究[J].軟件學報,2009,20(2):271－289.