弓佳明，章騰浩，許麗娟

（廣州華商學(xué)院數(shù)據(jù)科學(xué)學(xué)院，廣州 511300）

0 引言

時代造就了科技水平的提高，人類文明的不斷推進(jìn)。無論是在醫(yī)學(xué)、金融，還是交通等方面都出現(xiàn)了許多優(yōu)化問題。為此，研究人員研究了一種模擬自然進(jìn)化算法（EA）的隨機(jī)搜索算法，由于這類算法在科研領(lǐng)域有很強(qiáng)的適配性，該算法被廣泛用于解決非常復(fù)雜的非線性結(jié)構(gòu)。然而現(xiàn)實中的優(yōu)化問題通常是擁有多個屬性且相互聯(lián)系的，例如：一個國家想要強(qiáng)大，經(jīng)濟(jì)實力和國防力量是支撐。國家的經(jīng)濟(jì)發(fā)展與其軍事國防發(fā)展間的優(yōu)化關(guān)系。國家發(fā)展好了，那么經(jīng)濟(jì)就會對其軍事力量提供更好的資金支持；反過來，只有武器力量強(qiáng)大了才能在世界上站穩(wěn)腳跟，更好地發(fā)展經(jīng)濟(jì)。其兩者是相互促進(jìn)，密不可分的。同時，這兩者又是相互矛盾的，倘若過度投資國防不發(fā)展經(jīng)濟(jì)，就會頭重腳輕，到最后國防資金供給不足；反之亦然，落后就要挨打，處于水深火熱之中的經(jīng)濟(jì)更加燃不起火苗。所以，關(guān)鍵在于衡量這兩者之間的投入比例使其達(dá)到最優(yōu)解。

為了實現(xiàn)總目標(biāo)的最優(yōu)化，研究者們往往需要對彼此矛盾的影響因子進(jìn)行綜合考慮，于是便衍生了多目標(biāo)進(jìn)化算法。MOEA 的種類有許多，本文只研究基于分解的多目標(biāo)優(yōu)化算法（MOEA/D）。根據(jù)多目標(biāo)演化算法將多目標(biāo)問題（MOPS）轉(zhuǎn)化為一些單個體，之后利用小個體的鄰近子問題的關(guān)系進(jìn)一步重復(fù)更新迭代［1］。由于分解成一個個小目標(biāo)，這使得該方法在處理相關(guān)聯(lián)系的信息就不會進(jìn)入極端的局部最優(yōu)，而這些個體目標(biāo)所組成的結(jié)果最終會接近最優(yōu)解邊界（PF），即一組Pareto最優(yōu)解集。

1 基于分解策略的多目標(biāo)優(yōu)化算法概述

1.1 多目標(biāo)優(yōu)化問題（MOP）

在解決多目標(biāo)優(yōu)化問題時，有些問題是難以解決的。這是因為多目標(biāo)優(yōu)化問題（MOPs）不同于單目標(biāo)優(yōu)化（SOPs），在最優(yōu)解上多目標(biāo)優(yōu)化問題具有多個最優(yōu)解。那么接下來的問題即是，對于這些最優(yōu)解集哪些才是解決問題所需要的，如何構(gòu)造這些最優(yōu)解集？為了解決這些問題，研究者們給出了這樣的描述。

對于一個具有m個目標(biāo)，n維決策變量的MOPs，其數(shù)學(xué)模型［2］為

其中x=(x1,…,xm)∈Ω 被稱為m維決策向量，為一組個體。在目標(biāo)進(jìn)化中優(yōu)化函數(shù)向量minF(x)=(f1(x),f2(x),…,fk(x))T，k是目標(biāo)函數(shù)的個數(shù)。在多目標(biāo)優(yōu)化問題中，對于不同的子目標(biāo)函數(shù)可能會有不同的最優(yōu)解?？偨Y(jié)起來歸為三類情況：①最大化所有子目標(biāo)函數(shù)；②最小化所有子目標(biāo)函數(shù)；③最小化部分子目標(biāo)函數(shù)，最大化其他子目標(biāo)函數(shù)。

1.2 Pareto最優(yōu)解和最優(yōu)邊界

Pareto 最優(yōu)解：多目標(biāo)的最優(yōu)解通常被稱為Pareto最優(yōu)解。它是由經(jīng)濟(jì)學(xué)領(lǐng)域的專家為提高經(jīng)濟(jì)上的效率問題和收入方面的分配方法而研究得到的，是屬于資源分配的“烏托邦”，在進(jìn)行分撥的過程中整體趨勢向著好的方向發(fā)展，并不會存在一個由于其他的優(yōu)化而惡化，這就是帕累托最優(yōu)化。

Pareto 最優(yōu)邊界：在目標(biāo)空間中，多目標(biāo)的最優(yōu)解集就是目標(biāo)函數(shù)的切點。它們總是落在搜索區(qū)域的邊界上。如圖1所示。A、B、C、D、E和F所在曲線便是最優(yōu)解邊界，而這些實心點所組成的集合即為Pareto最優(yōu)解集，其余點便不屬于該集內(nèi)。

圖1 最優(yōu)邊界

1.3 分解策略

分解策略是用傳統(tǒng)數(shù)學(xué)規(guī)劃解決多目標(biāo)優(yōu)化問題的一個基本思路。在給定權(quán)重偏好或者參考點信息的情況下，分解法通過線性或者非線性方法將原MOPS中的各個目標(biāo)聚合得到一個個單目標(biāo)優(yōu)化問題，并且使單目標(biāo)優(yōu)化方法求出一個Pareto 最優(yōu)解［3］。為了得到整個PF 的逼近，Zhang等［4］在2008年提出了基于分解的多目標(biāo)優(yōu)化算法，該算法在科研領(lǐng)域得到了廣泛使用，成為目前最具影響力的MOEA/D之一。

1.4 基于分解策略的多目標(biāo)優(yōu)化算法的分解方法

權(quán)重聚合方法（Weighted Sum Approach）［4］是一種常用的線性多目標(biāo)聚合方法，其目標(biāo)函數(shù)的聚合形式定義為

如式（2），x∈Ω為決策向量，λ=(λ1,λ2,…,λm)為權(quán)重向量，滿足λi≥0,i=1,2,…,m且=1如圖2 所示，綠色為等值線，紅色為權(quán)重向量，等值線與方向向量垂直。當(dāng)最小化問題的PF 為凸?fàn)顣r，單個最優(yōu)等值線會與PF 相交于一個切點。該類聚合方法所得到的結(jié)果能夠較好符合貼近PF 的要求，這使得研究者們遇到高維度的空間難題時用該類方法解決好這一復(fù)雜問題。

圖2 權(quán)重逼近

權(quán)重聚合方法也有其缺點，那就是當(dāng)最小化問題的Pareto前沿面為凹狀時，所有最優(yōu)解位于Pareto面的邊緣地帶。這是因為Pareto 面中間凹下去那部分的解會與其他的解“格格不入”，形成了較大的差值比較，從而降低了最終結(jié)果的精確度，即相比Pareto 面的邊緣具有更大的函數(shù)值。所以權(quán)重聚合方法并不能很好地解決Pareto面為凹狀的情況。

基于懲罰的邊界交叉方法（Boundary Inter?sectionApproach）［5］是于2007 年被提出的基于方向的分解法，其定義如下：

邊界交叉有一個缺點就是必須處理等式約束，為此引入了懲罰參數(shù)θ，數(shù)學(xué)描述見公式（3），λ和z*分別是權(quán)重向量和參考點，l1是F(x)投影點到參考點的距離，其中θ>0是預(yù)設(shè)參數(shù)，用來處理等式約束。

切比雪夫分解法（Tchebycheff Approach）是一種非線性的多目標(biāo)聚合方法［6］，其聚合函數(shù)定義如下：

其中z*為目標(biāo)函數(shù)f（x）的最小值，將其定義z*=min{fi(x)|x∈Ω}；λ定義與上述的權(quán)重聚合的λ定義一致。

2 切比雪夫分解法

2.1 切比雪夫分解法概述

切比雪夫分解法無論是解決Pareto凸?fàn)顔栴}還是凹狀問題都具有良好的適配性，一定程度上解決了權(quán)重聚合方法不能適應(yīng)凹狀問題的缺點。其數(shù)學(xué)描述如公式（4）所示，=1，其中z*為理想點，同時也為目標(biāo)函數(shù)的最小值；w為權(quán)重向量，x∈Ω 為決策向量，T為權(quán)重向量，其中滿足wi≥0,i=1,2,…,m。

如圖3 所示，坐標(biāo)軸是兩個目標(biāo)函數(shù)f1和f2。首先根據(jù)定義式分別計算w1*|f1(x)-z1|和w2*|f2(x)-z2|，把計算出來的最大值保留。保留的這個數(shù)值越大，說明在這個目標(biāo)函數(shù)上它離點z*越遠(yuǎn)。若w1*|f1(x)-z1|較大，逐漸改變自變量x，使得這個值離點z*越來越近，直到達(dá)到PF 上對應(yīng)的點為止。這個過程其實就是求函數(shù)gtche=w1*|f1(x)-z1|的最小值。若這個較大的定義式達(dá)到了它的最小值，那么w2方向的式子也就相應(yīng)地達(dá)到它的最小值。其他的權(quán)重向量都是采用這種方式不斷地進(jìn)行更新迭代，直至獲得Pareto最優(yōu)解集。

圖3 切比雪夫方法

這種方法類似于物理上力的分解平行四邊形法則和Pareto最優(yōu)解思想的結(jié)合。通過對一個權(quán)重向量上任意點基于目標(biāo)函數(shù)進(jìn)行分解，將其分解成兩個方向，當(dāng)其中較大的那個函數(shù)通過改變x的值達(dá)到最小值時，相應(yīng)的另外的函數(shù)也就達(dá)到了理想值［7］。從原來的狀態(tài)到另一種狀態(tài)的變化過程中，在原有情況下沒有使其變壞的前提下，使得其中的某一項變得更好。此時該函數(shù)已達(dá)到Pareto邊界的逼近，即最優(yōu)解。

2.2 基于切比雪夫分解法的MOEA/D算法框架

與其他的MOEA算法不一樣的是，MOEA/D算法是屬于比較開放的算法類型，它會在分解的基礎(chǔ)上在附近選擇一個父個體，通過穿插變異得到一個新的子個體，且這一個體經(jīng)過一定的運算法則更新附近種群。其基本思想——通過將整體分為一個個小個體，這些子問題之間存在的相鄰聯(lián)系，相互協(xié)作做到同時優(yōu)化這些子問題，最終滿足無限接近于PF。

基于分解的MOEA/D 算法框架最大的特點便是分解與合作。要了解基于切比雪夫分解法的MOEA/D 算法框架首先要定義其數(shù)據(jù)結(jié)構(gòu)。根據(jù)其定義式所需，其數(shù)據(jù)結(jié)構(gòu)定義如下：

（1）首先定義關(guān)于切比雪夫分解法所需的權(quán)重向量集合{w1,w2,…,wi}和理想點z；

（2）對于每個子問題分配一個個體，然后將這些個體集合{x1,x2,…,xi}組合成一個進(jìn)化種群Q；

（3）用于存儲逼近Pareto 邊界最優(yōu)解的精英種群EQ；

MOEA/D的算法流程如圖4所示。

圖4 MOEA/D算法流程圖

初始化：在進(jìn)行初始化的時候需設(shè)EQ=?；確定每個權(quán)重wi的k個相鄰的權(quán)重向量{w1,…,wk}，同時計算初始化種群的目標(biāo)向量（通過計算權(quán)重向量之間的歐幾里得距離來計算子問題的鄰域關(guān)系）；初始化理想點z*。

更新：更新操作是對原來的個體進(jìn)行交叉變異，即從鄰域中隨機(jī)挑選兩個個體進(jìn)行基因重組，從而產(chǎn)生新的個體（其中在鄰域中修正約束解時，鄰域的大小和替換個體的次數(shù)將會影響到這個種群的多樣性與收斂性），如此往復(fù)使其逐步逼近Pareto邊界。

2.3 算法相關(guān)代碼示例

由于進(jìn)化算法相對復(fù)雜，針對采用Tcheby?cheff 的MOEA/D 實驗方法將兩個多目標(biāo)測試問題進(jìn)行運算舉例說明，如算法1所示。

3 MOEA/D的性能評價

3.1 MOEA/D的性能評價的概述

通常在對一個多目標(biāo)進(jìn)化算法的性能進(jìn)行評價時，總是需要有一套能客觀評價MOEA/D優(yōu)劣性的評價方法或者工具，同時也要選取一組較有代表性的測試來說明問題。

一般來說，衡量MOEA/D 性能的評價有兩個標(biāo)準(zhǔn)。第一是MOEA/D 的效果，具體來說即是目標(biāo)函數(shù)所求得的Pareto最優(yōu)解的質(zhì)量，而這主要取決于它的收斂結(jié)果和分布結(jié)果；第二是MOEA/D 的效率，由于多目標(biāo)優(yōu)化算法的復(fù)雜性影響著算法的效率，所以也要考慮硬件問題，比如電腦CPU 運算算法的時間效率問題或電腦的空間存儲問題。

3.2 MOEA/D的性能評價的方法

通常采用兩種方法來對MOEA/D 的性能進(jìn)行評價，一種是對MOEA/D 的性能進(jìn)行理論上的分析，另外一種是在實驗的過程中對MOEA/D的性能進(jìn)行測試和比較。一般來說，MOEA/D算法的運行效率和收斂性是可以通過理論方法來進(jìn)行分析的，但是由于目前對MOEA/D 收斂性的研究還不是特別深入，相關(guān)的論證還局限于時間趨近于無窮大的狀態(tài)。因此很難從理論上去判斷它們哪一個更加適合。所以在現(xiàn)實研究中，研究者們通常采用理論分析和實驗相結(jié)合的方法對一個MOEA/D算法進(jìn)行綜合評價。

在眾多MOEA/D 性能評價的方法中又可以歸類為三大類：

（1）收斂性：評價解集和真正的最優(yōu)邊界的逼近程度；

（2）分布性：評價解集的多樣性和分布性；

（3）綜合性能：綜合考慮解集的收斂性和分布性。

要根據(jù)具體問題來具體分析，針對算法的相關(guān)特征選取與之適應(yīng)的評價方法。

3.2.1 收斂性評價方法

（1）世代距離（Generationl Distance，GD）

世代距離表示PFknown和PFtrue之間的間隔距離，PFtrue是問題的真正最優(yōu)邊界，數(shù)值越大，離真正最優(yōu)邊界的偏差越大，相應(yīng)的收斂性也越大。其定義式見式（5），其中n是PFknown中向量的個數(shù)；當(dāng)p=2時，為歐氏距離。

如圖5 所示，di的點距離Pareto 最優(yōu)解集非常接近，結(jié)合公式可知它的收斂性比較好。但是世代距離也有缺點——那就是在一些解集分布性能不好的情況下，可能會影響到最終結(jié)果。

圖5 世代距離

（2）基于距離的趨近度評價法［8］

其原理是通過計算兩個解集之間的最短距離來測量算法的近似值，該距離是最優(yōu)的或可參考的。距離越小，說明計算結(jié)果和真實就越接近。在估計算法的收斂程度時，這種方法需要定義一個集作為運算的參照，可以是最優(yōu)解集，也可以是過去幾代的非支配集。通常很難在許多優(yōu)化問題上得到一組最優(yōu)解，所以參考集都是選取歷代非支配集并集的非支配集。

（3）C-metric解集覆蓋率［9］

Zitzler 等［9］提出通過計算兩個不同解集的覆蓋率，然后對它們進(jìn)行比較，在MOEA/D 的論文中也用到了該性能指標(biāo)。其定義為：對于兩個相近解集A和B，C（A,B）是B被A中至少一個解支配的解占B中解數(shù)量的比值。C（A,B）=100表示B中所有的解都被A中至少一個解支配。C（A,B）=0 表示B中沒有解被A中的解支配。但是C（A,B）不一定等于1-C（B,A）。其公式為

3.2.2 對于分布性評價方法

（1）空間評價方法［10］

空間評價方法是用來評價近似解集中個體在目標(biāo)空間的分布情況，其評價函數(shù)定義式如下：

其中非支配邊界上兩個連續(xù)向量的歐幾里得距離，d是這些矢量Euclidean-distance 的平均值，PF是已知的Pareto 最優(yōu)解面。在此基礎(chǔ)上提出了一種新的多屬性決策分析中關(guān)于方案排序和擇優(yōu)問題的綜合決策模型，并給出相應(yīng)的算法步驟與實現(xiàn)過程。最后通過一個算例說明了該方法的有效性與可行性。值得一提的是，這種評價方法只適用于二維目標(biāo)空間，對于高維目標(biāo)并不能很好地解決評價問題。

（2）對空間評價法的進(jìn)一步優(yōu)化

通過計算一個給定點到它最近鄰居的距離來解決高維目標(biāo)的問題［10］。改進(jìn)后的指標(biāo)如下：

3.2.3 對于綜合性評價方法

（1）超體積指標(biāo)——Hypervolume指標(biāo)［7］

它可以根據(jù)超過體積的單個值來判斷群解的質(zhì)量，是唯一已知的符合帕累托主導(dǎo)概念的指標(biāo)。超體積是估計近似解集收斂性和多樣性的綜合指標(biāo)。如圖6所示。

圖6 超體指標(biāo)

超體積值越大，該解集越好。研究者們基于上述研究結(jié)果提出了一種新的快速迭代算法：超體積迭代法。該方法通過引入兩個參數(shù)來提高收斂速度。數(shù)值實驗表明該算法具有較好的性能。超體積的主要優(yōu)點之一是它能使解接近于單個數(shù)的最優(yōu)集合，并能在一定程度上反映解在目標(biāo)空間中的分布。缺點是計算過度復(fù)雜，而且參考點選取對精確度有一定的影響。

（2）反轉(zhuǎn)世代距離［11］

該方法基于世代距離的逆向思考。首先，將問題轉(zhuǎn)換為一個非線性規(guī)劃模型，然后利用基于遺傳算法（GA）的進(jìn)化策略求解，這就改進(jìn)了傳統(tǒng)遺傳算法收斂速度慢的缺陷。最后給出算例，說明其有效性和可行性。它表示從Pareto最優(yōu)解集的個體到算法得到的非支配解集的平均距離。其定義式為

IGD值越小，說明算法的綜合性能就越好。倘若分布性能不好，計算得出的IGD值相對會比較大，如果解集收斂性好并且分布也均勻，那么得到的IGD值必然很小。由此可得到的IGD指標(biāo)既可以表示MOEA 的收斂性，同時也可以反映出MOEA的分布情況。

圖7 反向世代距離

4 MOEA/D在現(xiàn)實中的應(yīng)用

4.1 MOEA/D產(chǎn)生背景

近來，出現(xiàn)了許多優(yōu)秀的多目標(biāo)進(jìn)化算法，研究者們研究這些算法的目的是希望種群盡可能地逼近PF。但是恰當(dāng)?shù)貙⒂嬎阗Y源分配到不同的前沿部位是目前為止的難點所在，所以他們通常都不能沿PF產(chǎn)生一組分布均勻的解，之所以這樣，其主要原因是多目標(biāo)優(yōu)化是個復(fù)雜的問題，子目標(biāo)之間又相互聯(lián)系，稍有不注意優(yōu)化一個目標(biāo)就可能惡化其他目標(biāo)，想要同一時間使所有目標(biāo)達(dá)到最優(yōu)是不可能的。為此，我們就需要選取一組Pareto最優(yōu)解來作為結(jié)果的候選解。

為了解決這些問題，Zhang 等［4］便提出了基于分解的多目標(biāo)優(yōu)化算法，通過一些偏好或者規(guī)則得到這些子問題的最優(yōu)解，整體趨勢向優(yōu)，也就是Pareto最優(yōu)解集。

4.2 應(yīng)用概述

在環(huán)境發(fā)展方面：聯(lián)合國開發(fā)計劃署的援華項目“華北水資源管理”中，對華北宏觀經(jīng)濟(jì)水資源規(guī)劃進(jìn)行輔助調(diào)控，該項目是一個基于宏觀經(jīng)濟(jì)水資源系統(tǒng)規(guī)劃理論的大型綜合性模型。包括北京、天津、河北、山東等省市，并且考慮區(qū)內(nèi)國民生產(chǎn)總值、就業(yè)率、生物化學(xué)需氧量的排放量最小，糧食產(chǎn)量最大四個因素。工程和節(jié)水措施方面采用的是0～1 變量，是一個0～1 混合整數(shù)線性模型。后來史慧斌等［12］在此基礎(chǔ)上對其用Tchebycheff 原理與求解多目標(biāo)交互相結(jié)合，在切比雪夫求解構(gòu)成中增加了群決策，對原有理論進(jìn)行了擴(kuò)展研究。

在人工智能方面：該類算法主要應(yīng)用于對人工智能的路徑規(guī)劃問題、模糊規(guī)則、故障診斷、機(jī)械臂等。例如，機(jī)械臂的應(yīng)用多出現(xiàn)在制造車間或者一些危險地帶，解決人類難以解決的問題，但由于機(jī)械臂的操作是多約束的優(yōu)化函數(shù)，與傳統(tǒng)的算法相比，MOEA/D 在解決復(fù)雜優(yōu)化問題時往往會起到“大事化小，小事化了”的奇效。

在機(jī)動車行駛路徑方面：在解決行駛路徑問題時，通常把服務(wù)對象稱之為顧客，以滿足顧客需求為服務(wù)，確定好顧客的所在地。在面對一系列位置分散的顧客點，滿足一定限制條件時，通過算法分解得出最優(yōu)的行車路徑，使車輛達(dá)到最優(yōu)滿足顧客需求又使車輛數(shù)量較少。

5 結(jié)語

本文首先闡述了什么是多目標(biāo)優(yōu)化問題，然后介紹了多目標(biāo)優(yōu)化問題所需要面對的事情，那就是如何在原有狀態(tài)不惡化的情況下，改變某些因素使得整體趨勢變得更加符合研究者的需求，由此引出Pareto最優(yōu)解的概念以及更加抽象化的Pareto 最優(yōu)邊界。為了達(dá)到Pareto 最優(yōu)邊界的逼近，Zhang 等［4］提出了MOEA/D 這一思想，將傳統(tǒng)的數(shù)學(xué)模型引入到多目標(biāo)優(yōu)化算法中來，這一思想的提出掀起了研究者們對多目標(biāo)進(jìn)化算法的科研熱潮。而分解的策略方法又詳細(xì)分為了三種——權(quán)重求和方法、邊界交叉方法和切比雪夫方法。

其次，本文研究了基于分解的多目標(biāo)優(yōu)化算法的性能評價方法。要評價多目標(biāo)進(jìn)化算法有兩個標(biāo)準(zhǔn)，一是MOEA/D 的最終效果取得的最優(yōu)解集的質(zhì)量是否優(yōu)秀；二是算法的效率，從數(shù)據(jù)結(jié)構(gòu)的知識來說，即是時間復(fù)雜度和空間復(fù)雜度問題。MOEA/D 性能評價方法主要從收斂性、分布性、綜合性能三個方面考慮。在這三個方面，本文羅列了一些研究常用的評價方式，包括世代距離法、基于距離的趨近度評價法、空間評價法、超體積指標(biāo)等。