淺析多目標(biāo)優(yōu)化問題

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

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

多目標(biāo)優(yōu)化問題MOPs(Multi objective Optimization Problems)是工程實(shí)踐和科學(xué)研究中的主要問題形式之一，廣泛存在于優(yōu)化控制、機(jī)械設(shè)計(jì)、數(shù)據(jù)挖掘、移動(dòng)網(wǎng)絡(luò)規(guī)劃和邏輯電路設(shè)計(jì)等問題中。MOPs有多個(gè)目標(biāo)，且各目標(biāo)相互沖突。對(duì)于MOPs，通常存在一個(gè)折衷的解集(即Pareto最優(yōu)解集)，解集中的各個(gè)解在多目標(biāo)之間進(jìn)行權(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 個(gè)相互沖突的目標(biāo)函數(shù)。 對(duì)于解 x1，x2∈Ω，x1支配 x2（記作 x1?x2），當(dāng)且僅當(dāng)?i∈（1，2，…，m）使得 fi（x1）≤fi（x2），且?i∈｛1，2，…，m｝，使得 fi（x1）≤fi（x2）。解 x*∈Ω 為 Pareto 最優(yōu)解，當(dāng)且僅當(dāng)不存在解x∈Ω，使得x?x*。Pareto最優(yōu)解的集合稱為Pareto 最優(yōu)解集（記作 P*），P*＝｛x*∈Ω｜﹁?x∈Ω：x?x*｝。 Pareto 最優(yōu)解集P*在目標(biāo)空間的映射稱為真實(shí)Pareto前沿面 （記作PF*），PF*＝｛F（x*）＝（f1（x*），f2（x*），…，fm（x*））｜x*∈P*｝。若 x1?x2，則稱 x2為支配解。解集P'被稱為非支配解集，當(dāng)且僅當(dāng)P'中不含支配解。

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

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

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

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

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

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

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

3 評(píng)估方法

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

4 測試用例

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

5 挑戰(zhàn)和困難

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

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

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

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

6 結(jié)論

MOPs在工程實(shí)踐和科學(xué)研究中是非常重要的。本文通過對(duì)MOPs的問題定義、多目標(biāo)優(yōu)化算法、評(píng)估方法、測試用例四個(gè)方面對(duì)MOPs的相關(guān)問題進(jì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］鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，2007.

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