張淑艷 段鵬松 鄒衛(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)鍵。
最小化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'中不含支配解。
目前,大量算法用于求解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ì)于直接得到非支配解集是非常有效的?;谶M(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。
求解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ù)等。
算法性能的評(píng)估需要客觀的測(cè)試用例。Schaffer、Kursawe和Deb分別在1985年、1991年和1999年提出了較簡(jiǎn)單的兩目標(biāo)優(yōu)化測(cè)試用例SCH、KUR和DEB。Zitzler、Deb和Thiele在2000年提出了6個(gè)兩目標(biāo)優(yōu)化測(cè)試用例 ZDT1~ZDT6。 Deb、Thiele、Laumanns和 Zitzler在2002年提出了 7個(gè)多目標(biāo)優(yōu)化測(cè)試用例 DTLZ1~DTLZ7,DTLZ1~DTLZ7的決策變量和目標(biāo)數(shù)可以擴(kuò)展到任何數(shù)目[4]。上述測(cè)試用例均無約束,其Pareto最優(yōu)解集和真實(shí)Pareto前沿面可在(http://www.cs.cinvestav.mx/~emoobook/)下載。 Liu在 2008年為 CEC2009提出了 23個(gè)更加復(fù)雜的測(cè)試用例 CF1~CF10、R2-DTLZ2、R3-DTLZ3、WFG1 和CF1~CF10。其中CF1~CF7為7個(gè)無約束兩目標(biāo)優(yōu)化測(cè)試用例,CF8~CF10 為 3 個(gè)無約束三目標(biāo)優(yōu)化測(cè)試用例,R2-DTLZ2、R3-DTLZ3、WFG1為3個(gè)無約束五目標(biāo)優(yōu)化測(cè)試用例,CF1~CF7為7個(gè)帶約束兩目標(biāo)優(yōu)化測(cè)試用例,CF8~CF10為3個(gè)帶約束三目標(biāo)優(yōu)化測(cè)試用例。CEC2009的測(cè)試用例的問題描述、Pareto最優(yōu)解集和真實(shí)Pareto前沿面 可 在 網(wǎng) 站 (http://dces.essex.ac.uk/staff/qzhang/moeacompetition09.htm)下載。
由于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)估方法和一組測(cè)試用例。評(píng)估方法和測(cè)試用例的選擇和設(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è)尚待研究的問題。
MOPs在工程實(shí)踐和科學(xué)研究中是非常重要的。本文通過對(duì)MOPs的問題定義、多目標(biāo)優(yōu)化算法、評(píng)估方法、測(cè)試用例四個(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.