朱登京，段倩倩

(上海工程技術(shù)大學(xué)電子電氣工程學(xué)院，上海 201600)

1 引言

工程設(shè)計問題涉及同時優(yōu)化多個目標(biāo)函數(shù)，它不同于單目標(biāo)優(yōu)化問題，同時優(yōu)化多個目標(biāo)函數(shù)往往沒有唯一解。在沒有決策者先驗信息的情況下，多目標(biāo)優(yōu)化問題MOPs(Multi-objective Optimization Problems)旨在尋找最佳折衷。目前，大規(guī)模全局優(yōu)化問題的求解算法主要分為2種類型：一類是進(jìn)化算法，對大規(guī)模全局優(yōu)化問題進(jìn)行整體求解，這種算法的主要代表有群體智能算法、進(jìn)化計算算法等。另一類是目前取得成果較多的基于分組與局部搜索的算法，即協(xié)作型協(xié)同進(jìn)化方法簡稱 CC(Cooperative Coevolution)算法。CC類算法利用分治的思想，首先將高維問題分解成若干個低維子問題，然后對每個子問題分別進(jìn)行求解。協(xié)作型協(xié)同進(jìn)化框架能將高維的問題分解成多個子問題，因此協(xié)作型協(xié)同進(jìn)化算法在大規(guī)模變量問題上有更加優(yōu)秀的表現(xiàn)。

1994年P(guān)otter等[1]提出了協(xié)同進(jìn)化算法，通過分解來解決大而復(fù)雜的問題，將1個N維問題直接分成N個一維的子問題，再用遺傳算法對子問題進(jìn)行求解。這種方式未考慮到變量之間的關(guān)聯(lián)性。2000年P(guān)otter等[2]提出了一種基于子組件體系結(jié)構(gòu)的協(xié)同優(yōu)化算法，將1個N維問題分解成2組N/2維的子問題，該算法雖然在一定程度上考慮到了變量間的關(guān)聯(lián)性，但是如果N很大，每組會產(chǎn)生許多決策變量，導(dǎo)致算法解集質(zhì)量下降。2005年Shi等[3]將差分分組融入到協(xié)同優(yōu)化算法框架之中，實驗表明差分分組的實驗結(jié)果要優(yōu)于遺傳算法和差分分組本身。隨著工程問題變得越來越復(fù)雜，相應(yīng)實際模型的決策變量也更加復(fù)雜。因此，在2008年Yang等[4]引入了自適應(yīng)權(quán)重和隨機(jī)分組的模式，提出了一種能夠優(yōu)化大規(guī)模不可分問題的協(xié)同進(jìn)化框架EACC-G(Evolutionary Algorithms Cooperative Coevolution-Group)，該方法通過隨機(jī)分組的方式增大了交互變量分到同一組的概率。隨機(jī)分組的方式能夠有較大的概率使得2個交互變量分到同一組，然而將多個交互變量分到同一組的概率卻不夠高。2009年Li等[5]提出了差分進(jìn)化DE(Differential Evolution)的基于分解的多目標(biāo)優(yōu)化算法MOEA/D(Multi-Objective Evolutionary Algorithm based on Decomposition)新版本，實驗結(jié)果表明MOEA/D-DE的性能明顯優(yōu)于NSGA-II。這表明基于分解的多目標(biāo)進(jìn)化算法在處理復(fù)雜的PS(Pareto Set)形狀時能夠提升算法解集質(zhì)量。2014年Omidvar等[6]提出了一種基于變量交互性來劃分變量的方法，此方法通過2個變量之間差值的大小來判斷變量間是否交互；2個決策變量的交互系數(shù)大于某個設(shè)定好的閾值，才會將這2個決策變量分到同一組。該方法比隨機(jī)分組的方式具有更強(qiáng)的魯棒性。2016年Cheng等[7]提出了一種處理不規(guī)則PFs的參考向量再生策略算法RVEA(Reference Vector-guided Evolutionary Algorithm)，該算法采用了一種稱為角度懲罰距離的尺度化方法來平衡高維目標(biāo)空間中解的收斂性和多樣性。對于多目標(biāo)問題來說，決策變量的規(guī)模越大，變量間的關(guān)聯(lián)性也隨之增大。根據(jù)決策變量間的交互性對變量進(jìn)行分組，能夠?qū)⒏呔S的問題分解為簡單的低維問題，從而能夠更大程度上保證解集的質(zhì)量。

本文將協(xié)同優(yōu)化與MOEA/D[8]相結(jié)合，并對基于變量交互性分組的方式進(jìn)行改進(jìn),提出了一種無參交互變量分組的多目標(biāo)優(yōu)化算法MOEA/DGWP(Multi-Objective Evolutionary Algorithm based on Decomposition-Group Without Parameters)。此算法的主要優(yōu)點(diǎn)是通過自動計算其閾值參數(shù)(ε)，能夠更加精確地識別出決策變量之間的交互性，提高變量分組的精確性。最后經(jīng)過實驗分析，MOEA/DGWP算法產(chǎn)生的解集具有更好的多樣性和收斂性。

2 背景

2.1 多目標(biāo)問題的定義

一個具有n個決策變量，m個目標(biāo)變量的多目標(biāo)優(yōu)化問題(MOPs)描述為[9]：

(1)

其中，Ω是決策空間，F(xiàn):Ω→Rm包括m個實值目標(biāo)函數(shù)值，Rm稱為目標(biāo)空間。x是在可行域Ω的決策向量。

令u,v∈Rm，如果對于任意的的i,ui≥vi，當(dāng)且僅當(dāng)對于任意的i∈{1,…,m}，ui≥vi并且至少存在1個下標(biāo)j∈{1,…,m}，uj>vj，那么稱為u支配v(表示成uv)。如果在決策空間中，沒有1個點(diǎn)x∈Ω使得F(x)F(x*)，那么將x*∈Ω稱為Pareto最優(yōu)解。換句話說，對于Pareto最優(yōu)點(diǎn)在某一個目標(biāo)函數(shù)上的提高，都會造成至少1個其余目標(biāo)函數(shù)的退化。所有Pareto最優(yōu)解的集合稱為Pareto集合(PS)，所有最優(yōu)向量的集合被稱為Pareto前沿PF(Pareto Front)。

2.2 基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)框架

基于分解的多目標(biāo)進(jìn)化算法的主要思想是使用一個聚合函數(shù)將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為一系列單目標(biāo)優(yōu)化子問題，然后利用一定數(shù)量相鄰問題的信息，采用進(jìn)化算法對這些子問題同時進(jìn)行優(yōu)化。

MOEA/D算法在每一代中需要保存如下信息：

N個種群{x1,…,xN}，其中xi是第i個子問題的當(dāng)前解；

FV1,…,FVN，其中FVi為xi的F值，即FVi=F(xi)，1=1,2,…,N；

z=(z1,…,zm)T，其中zi為目前為止目標(biāo)函數(shù)fi的最優(yōu)解；

用于存放搜索過程中搜尋到的非支配解的外部種群庫EP(External Population)。

MOEA/D算法具體步驟如算法1所示。

算法1 MOEA/D

輸入 需要被優(yōu)化的多目標(biāo)問題MOP；

N：子問題的個數(shù)；

N個均勻分布的權(quán)重向量λ1,…,λN；

T：權(quán)重向量的相鄰向量的個數(shù)；

算法終止條件，例如,最大迭代次數(shù)、算法最大運(yùn)行時間等。

輸出EP。

步驟1 初始化各項參數(shù)：

步驟1.1 使得EP為空集；

步驟1.2 計算任意2個權(quán)重向量之間的歐氏距離，再根據(jù)歐氏距離來為每個權(quán)重向量選出T個權(quán)重向量作為它的鄰居。設(shè)B(i)={i1,…,iT}，i=1,…,N。其中λi1，…,λiT為λi的T個最近的權(quán)重向量；

步驟1.3 隨機(jī)產(chǎn)1個初始種群x1,…,xN，令FVi=F(xi)。

步驟1.4 初始化參考點(diǎn)z=(z1,…,zm)T。

步驟2 更新：

Fori=1,…,Ndo

步驟2.1 繁殖操作：從B(i)中隨機(jī)選擇2個索引k,l，再通過遺傳算子從xk和xl中產(chǎn)生新的解y；

步驟2.2 修復(fù)/改進(jìn)：使用基于特定問題的啟發(fā)式對解y修復(fù)或改進(jìn)為y′；

步驟2.3 更新參考點(diǎn)z：如果zj

步驟2.4 更新鄰域解：對于每個索引j∈B(i)，如果gte(y′|λj,z)≤gte(xj|λj,z)，則令xj=y′，F(xiàn)Vj=F(y′)；

步驟2.5 更新外部種群EP：移除EP中所有被F(y′)支配的向量，如果EP中沒有被F(y′)支配的向量，則將F(y′)添加到外部種群EP中。

步驟3 終止：如果滿足終止條件，例如達(dá)到最大迭代次數(shù)、最長運(yùn)行時間等，則停止算法并輸出外部種群EP；否則，返回步驟2。

2.3 交互變量的定義

在生物學(xué)中，如果存在2個基因同時對某個生物的特性產(chǎn)生影響，那么稱這2個基因之間是相似的。在遺傳算法中，當(dāng)一個變量的改變導(dǎo)致另外一個變量也改變，那么稱這2個變量為交互變量。反之，一個變量的改變不會影響另外一個變量，這2個變量稱為非交互變量。函數(shù)的可分性和不可分離性定義如下：

定義1 函數(shù)f(x1,…,xn)是可分的當(dāng)且僅當(dāng)[10]：

arg minx1,…,xnf(x1,…,xn)=(arg minx1,f(x1,…)…,arg minxnf(…,xn))

(2)

換句話說，如果可以通過一次優(yōu)化一個維度來找到函數(shù)的全局最優(yōu)值，而不管其他維度的值如何，則該函數(shù)被稱為可分離函數(shù)；否則就是不可分離函數(shù)。

定理1 如果f(x)是連續(xù)可分離函數(shù)，那么對于x中的任意1個分量xp有：

(3)

其中，f(xi)為f(x)的任意一個分函數(shù)。

證明 因為f(x)是連續(xù)可分函數(shù)，所以得到：

(4)

其中x1,…,xm是互斥的決策向量。因此：

(5)

所以：

(6)

證明完畢。

定理2 當(dāng)f(x)是連續(xù)可分函數(shù)時，若?a,b1≠b2,δ≠0使得下式成立,則xp和xq為交互變量。

Δδ,xp[f](x)|xp=a,xq=b1≠Δδ,xp[f](x)|xp=a,xq=b2

(7)

其中:

Δδ,xp[f](x)=f(…,xp+δ,…)-f(…,xp,…)

(8)

定理2說明，給定一個連續(xù)可分離函數(shù)f(x)，如果用任意2個不同值xp和xq對式(8)進(jìn)行求值，得到不同的結(jié)果，那么2個變量xp和xq是交互變量。

證明 由定理1可知，當(dāng)xp不是xi的分量時：

?b1≠b2

Δδ,xp[f](x)|xp=a,xq=b1=Δδ,xp[f](x)|xp=a,xq=b2

?a,b1≠b2,δ∈R,δ≠0

證明完畢。

為了易于描述，本文接下來將式(7)的左邊使用Δ左表示，右邊用Δ右表示。通過式(7)可以得出Δ左≠Δ右?|Δ左-Δ右|≠0。然而由于在計算機(jī)中的浮點(diǎn)精度有限，這種利用等式檢查交互變量的方式是不可行的。因此，現(xiàn)在的檢查方式是將等式轉(zhuǎn)化為不等式，通過引入1個參數(shù)來提高檢測的敏感性：λ=|Δ左-Δ右|>ε,ε通常是1個很小的數(shù)。如果λ大于ε，那么就認(rèn)為2個變量之間是交互的，便將變量分在同一組。如果λ小于ε，那么就認(rèn)為2個變量之間不存在交互性。

3 不含參數(shù)的交互變量分組的多目標(biāo)優(yōu)化算法

3.1 不含參數(shù)的分組策略

本文通過估計舍入誤差的最大下界einf和最小上界esup來得到1個閾值。如果λ=|Δ左-Δ右|>esup,則認(rèn)為2個變量之間是交互的；如果λ=|Δ左-Δ右|

目前絕大多數(shù)的個人計算機(jī)和工作站采用的是IEEE754標(biāo)準(zhǔn)，在使用有限精度的計算機(jī)存儲單元來表示無限精度的實數(shù)時，舍入誤差的產(chǎn)生是不可避免的。

在IEEE754標(biāo)準(zhǔn)中，浮點(diǎn)數(shù)集合(包括0)是1個有限的集合，記為F。集合F中的非零浮點(diǎn)數(shù)均勻地分布在[-M,-g]和[g,M]上，其中g(shù)和M是機(jī)器能表示的最小和最大正浮點(diǎn)數(shù)。

對于實數(shù)x，對應(yīng)機(jī)器上的浮點(diǎn)數(shù)記為fl(x)。如果x=0，那么fl(x)取0。如果g≤|x|≤M，采用舍入法，取fl(x)為F中最接近x的數(shù)。若|x|M,那么fl(x)不存在。由此可以得到定理3。

fl(x)=x(1+δ)

(9)

(10)

除了上述提到的舍入誤差以外，計算機(jī)上基本算術(shù)運(yùn)算也將產(chǎn)生舍入誤差。在IEEE標(biāo)準(zhǔn)中規(guī)定了x⊕y=fl(x+y)，其中⊕意為浮點(diǎn)求和運(yùn)算。換句話說，保證了2個數(shù)字的浮點(diǎn)和等于與2個數(shù)字的實際和最近的浮點(diǎn)數(shù)。

定理4 若給定一系列滿足IEEE754標(biāo)準(zhǔn)的浮點(diǎn)數(shù)，則|δi|<μM,可以得到[12]：

(11)

為方便描述本文將nμM/(1-nμM)用γn代替。

定理4可以用于在任何計算中找出累積算術(shù)誤差的上界。本文利用定理4給出了計算誤差的一個合理的上、下界。為了估計舍入誤差大小的最大下界，假定f(x)的計算是無誤差的，錯誤的唯一來源是在計算λ=|Δ左-Δ右|時產(chǎn)生的，因此：

fl(Δ左)=f(x)?f(x′)=

(f(x)-f(x′))(1+δ1)=Δ左(1+δ1)

fl(Δ右)=f(y)?f(y′)=

(f(y)-f(y′))(1+δ1)=Δ右(1+δ2)

fl(λ)=|fl(Δ左)?fl(Δ右)|=

|fl(Δ左)-fl(Δ右)|(1+δ3)=

|f(x)(1+δ1)(1+δ3)-f(x′)(1+δ1)(1+δ3)-

f(y)(1+δ2)(1+δ3)+f(y′)(1+δ2)(1+δ3)|

通過上面的推導(dǎo)可以看出n=2，因此通過定理4可以得到下式：

|λ-fl(λ)|≤γ2|(f(x)-f(x′))-

(f(y)-f(y′))|=γ2|(f(x)+

f(y′))-(f(y)+f(x′))|≤γ2·

max{(f(x)+f(y′)),(f(y)+f(x′))}

即舍入誤差的最大下界einf=γ2·max{(f(x)+f(y′)),(f(y)+f(x′))}。

(12)

(13)

通過估計最小上界esup和最大下界einf，可以識別可靠的λ值。所有λ大于esup的值將被視為真正的非零值(交互變量)，所有小于einf的值被視為真正的零值(分離變量)。最后，對于(einf，esup)范圍內(nèi)的值，使用下面的邊界加權(quán)平均值設(shè)置閾值：

(14)

其中η0是通過λ=|Δ左-Δ右|計算得的值中大于einf的個數(shù)，η1是通過λ=|Δ左-Δ右|計算得的值中小于esup的個數(shù)。

3.2 不含參數(shù)的交互變量分組的多目標(biāo)優(yōu)化算法框架

算法2 無參變量分組算法

步驟1 利用定理4計算出舍入誤差的最大下界einf和最小上界esup，再利用式(14)計算出ε的值。

步驟2 從種群中隨機(jī)選取2個不同變量i和j，計算λ=|Δ左-Δ右|的值并作出如下判斷：若λ大于esup，則認(rèn)為變量i和j是交互變量，將它們放入同一組中；若λ小于einf，則認(rèn)為變量i和j為可分離變量；若λ∈[einf,esup]，則將λ與ε比較，大于ε便認(rèn)為i和j是交互變量，否則為可分離變量。

步驟3 重復(fù)上述步驟2識別其它所有變量是否與變量i交互，若存在交互，則放在同一組中。然后與第i+1個變量進(jìn)行交互性檢測和分組，直到所有的決策變量都被檢測完為止。

本文提出的無參變量分組的分解多目標(biāo)優(yōu)化算法(MOEA/DGWP)，不僅將協(xié)同優(yōu)化算法引入到MOEA/D算法中，還對交互變量識別、分組方式進(jìn)行改進(jìn)。算法通過將交互變量盡可能地分到同一組中，減少分組后子問題之間的相互依賴，從而能夠有效地提高解集的質(zhì)量。該算法步驟如算法3所示。

算法3 MOEA/DGWP

輸入：MOP；停止準(zhǔn)則；MOEA/D中考慮的子問題的數(shù)量；1組均勻的權(quán)重向量；每個權(quán)向量的鄰居權(quán)向量的個數(shù)。

輸出：EP。

步驟1 初始化和設(shè)置各項參數(shù)大??；

步驟2 對種群進(jìn)行交叉變異操作產(chǎn)生子種群；

步驟3 通過無參變量分組算法對決策變量進(jìn)行分組；

步驟4 使用MOEA/D算法對步驟3所產(chǎn)生的交互變量分組后產(chǎn)生的子問題進(jìn)行求解，得到局部最優(yōu)解；

步驟5 將步驟4產(chǎn)生的局部最優(yōu)解合并到全局最優(yōu)解；

步驟6 若滿足終止條件，輸出EP；否則，更新每個子問題權(quán)重系數(shù)，返回步驟3。

在MOEA/DGWP算法中，將交互變量分組和基于分解的多目標(biāo)優(yōu)化進(jìn)化算法進(jìn)行協(xié)同來優(yōu)化多目標(biāo)問題。通過計算舍入誤差的方式來提高分組的精確性，將大規(guī)模變量問題分解為低維問題來提高算法解集的質(zhì)量。

4 實驗研究

4.1 測試問題及參數(shù)設(shè)置

為了測試本文所提出的算法處理大規(guī)模變量多目標(biāo)問題的性能，本文使用測試多目標(biāo)問題的測試函數(shù)UF1和UF2。仿真實驗中所有種群大小N統(tǒng)一設(shè)置為100，迭代次數(shù)均為1 000 000次。為降低實驗的偶然性，各算法將各多目標(biāo)問題測試30次。決策變量維數(shù)為100,200。并且與MOEA/D、RVEA、MOEA/D-DE多目標(biāo)優(yōu)化算法進(jìn)行比較。

4.2 實驗結(jié)果

從圖1～圖4中可以看出，隨著決策變量的增加，算法MOEA/D、RVEA和MOEA/D-DE的解集質(zhì)量變得越來越差。MOEA/DGWP的解集質(zhì)量在不同測試函數(shù)和不同決策變量維數(shù)下均要優(yōu)于所測試的其它多目標(biāo)優(yōu)化算法的。

Figure 1 PF of test function UF1 with different algorithms under 100 variables圖1 100個決策變量下各算法測試函數(shù)UF1的Pareto前沿

Figure 2 PF of test function UF1 with different algorithms under 200 variables圖2 200個決策變量下各算法測試函數(shù)UF1的Pareto前沿

Figure 3 PF of test function UF2 with different algorithms under 100 variables圖3 100個決策變量下各算法測試函數(shù)UF2的Pareto前沿

Figure 4 PF of test function UF2 with different algorithms under 200 variables圖4 200個決策變量下各算法測試函數(shù)UF2的Pareto前沿

4.3 算法評價指標(biāo)

本文使用綜合評價指標(biāo)反世代距離(IGD)來衡量算法的收斂性和分布性。反世代距離采用Pareto最優(yōu)解集PFture中的個體到算法所求的非支配解集PFknown的平均距離表示[13]。計算公式為：

(15)

其中，P是優(yōu)化算法求得的解集，P*是從PF上采樣的一組均勻分布的參考點(diǎn)，dis(x,y)表示參考集P中點(diǎn)x到參考集P中點(diǎn)y之間的歐幾里得距離。IGD的值越小，就意味著算法的綜合性能就越好。

仿真實驗得到的結(jié)果如表1所示。表1統(tǒng)計了5個算法在不同決策變量個數(shù)下求解測試函數(shù)UF1和UF2的IGD均值和均方差(括號內(nèi)為均方差)，D表示決策變量個數(shù)。從表1可以看出，MOEA/DWPG的IGD均值和均方差都要低于MOEA/D和其它先進(jìn)算法的。IGD的均值越低表示算法的收斂性和分布性能越好。IGD的均方差表示了IGD的離散程度，均方差值越低，則代表每次運(yùn)行結(jié)果差異性越低，結(jié)果更加穩(wěn)定可靠。從實驗結(jié)果可以看出，基于無參數(shù)交互變量分組的方法能夠有效地將交互變量分到同一組，MOEA/DGWP在求解測試問題UF1和UF2時所獲得的解集質(zhì)量更高，有著比MOEA/D和其它先進(jìn)算法更好的收斂性和分布性。

5 結(jié)束語

本文提出的基于無參數(shù)交互變量分組的多目標(biāo)進(jìn)化算法(MOEA/DGWP)，將協(xié)同優(yōu)化與基于分解的多目標(biāo)優(yōu)化算法相結(jié)合，設(shè)計了一種新的分組方式，該分組方式通過計算舍入誤差提高了變量分組的精確性。通過與MOEA/D和其它先進(jìn)算法的比較表明，MOEA/DGWP算法在求解大規(guī)模變量優(yōu)化問題時所獲得的解集質(zhì)量更高。

Table 1 IGD standard values and mean square error表1 IGD的標(biāo)準(zhǔn)值和均方差