無參分組大規模變量的多目標算法研究*

朱登京，段倩倩

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

1 引言

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

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

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

2 背景

2.1 多目標問題的定義

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

(1)

其中，Ω是決策空間，F:Ω→Rm包括m個實值目標函數值，Rm稱為目標空間。x是在可行域Ω的決策向量。

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

2.2 基于分解的多目標進化算法(MOEA/D)框架

基于分解的多目標進化算法的主要思想是使用一個聚合函數將多目標優化問題轉化為一系列單目標優化子問題，然后利用一定數量相鄰問題的信息，采用進化算法對這些子問題同時進行優化。

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

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

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

z=(z1,…,zm)T，其中zi為目前為止目標函數fi的最優解；

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

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

算法1 MOEA/D

輸入 需要被優化的多目標問題MOP；

N：子問題的個數；

N個均勻分布的權重向量λ1,…,λN；

T：權重向量的相鄰向量的個數；

算法終止條件，例如,最大迭代次數、算法最大運行時間等。

輸出EP。

步驟1 初始化各項參數：

步驟1.1 使得EP為空集；

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

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

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

步驟2 更新：

Fori=1,…,Ndo

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

步驟2.2 修復/改進：使用基于特定問題的啟發式對解y修復或改進為y′；

步驟2.3 更新參考點z：如果zj

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

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

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

2.3 交互變量的定義

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

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

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

(2)

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

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

(3)

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

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

(4)

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

(5)

所以：

(6)

證明完畢。

定理2 當f(x)是連續可分函數時，若?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說明，給定一個連續可分離函數f(x)，如果用任意2個不同值xp和xq對式(8)進行求值，得到不同的結果，那么2個變量xp和xq是交互變量。

證明 由定理1可知，當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。然而由于在計算機中的浮點精度有限，這種利用等式檢查交互變量的方式是不可行的。因此，現在的檢查方式是將等式轉化為不等式，通過引入1個參數來提高檢測的敏感性：λ=|Δ左-Δ右|>ε,ε通常是1個很小的數。如果λ大于ε，那么就認為2個變量之間是交互的，便將變量分在同一組。如果λ小于ε，那么就認為2個變量之間不存在交互性。

3 不含參數的交互變量分組的多目標優化算法

3.1 不含參數的分組策略

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

目前絕大多數的個人計算機和工作站采用的是IEEE754標準，在使用有限精度的計算機存儲單元來表示無限精度的實數時，舍入誤差的產生是不可避免的。

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

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

fl(x)=x(1+δ)

(9)

(10)

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

定理4 若給定一系列滿足IEEE754標準的浮點數，則|δi|<μM,可以得到[12]：

(11)

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

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

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)|

通過上面的推導可以看出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)范圍內的值，使用下面的邊界加權平均值設置閾值：

(14)

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

3.2 不含參數的交互變量分組的多目標優化算法框架

算法2 無參變量分組算法

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

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

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

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

算法3 MOEA/DGWP

輸入：MOP；停止準則；MOEA/D中考慮的子問題的數量；1組均勻的權重向量；每個權向量的鄰居權向量的個數。

輸出：EP。

步驟1 初始化和設置各項參數大??；

步驟2 對種群進行交叉變異操作產生子種群；

步驟3 通過無參變量分組算法對決策變量進行分組；

步驟4 使用MOEA/D算法對步驟3所產生的交互變量分組后產生的子問題進行求解，得到局部最優解；

步驟5 將步驟4產生的局部最優解合并到全局最優解；

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

在MOEA/DGWP算法中，將交互變量分組和基于分解的多目標優化進化算法進行協同來優化多目標問題。通過計算舍入誤差的方式來提高分組的精確性，將大規模變量問題分解為低維問題來提高算法解集的質量。

4 實驗研究

4.1 測試問題及參數設置

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

4.2 實驗結果

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

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

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

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

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

4.3 算法評價指標

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

(15)

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

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

5 結束語

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

Table 1 IGD standard values and mean square error表1 IGD的標準值和均方差