基于角度軌跡和自適應權重的改進MOEA/D算法

蒙毅 魏文紅 吳帥

(東莞理工學院 計算機科學與技術學院,廣東東莞 523808)

基于分解的多目標進化算法(MOEA/D, Multi-objective Evolutionary Algorithm Based on Decomposition)[1]是廣泛使用的多目標優(yōu)化算法,該算法能將原始多目標問題分解為一組對應不同決策偏好的標量子問題并行優(yōu)化,最終實現(xiàn)對多目標最優(yōu)化問題的求解。多目標進化算法在解決NP(Nondeterministic Polynomial)問題中具有求解速度上的優(yōu)勢,在許多領域中被用來解決決策和最優(yōu)化問題。在工程優(yōu)化中,多目標進化算法可以用于解決復雜的設計問題,如結構優(yōu)化、參數(shù)優(yōu)化和排隊等問題[2-4]。此外,多目標進化算法還可以應用于金融領域的投資組合優(yōu)化、交通規(guī)劃、電力系統(tǒng)調度、醫(yī)療決策等領域[5],為各行各業(yè)的決策和優(yōu)化問題提供實用和高效的工具。

傳統(tǒng)的MOEA/D算法采用一組均勻的權重向量,在對應目標空間的超平面中均勻分布。理論上,在算法迭代過程中,標量子問題會向超平面收斂,從而形成分布均勻的Pareto最優(yōu)解[6]。然而,對具有復雜前沿的多目標問題,不同的子問題向Pareto前沿收斂的難度也不同。若計算資源均勻分布,則易搜索區(qū)域容易出現(xiàn)資源飽和,Pareto最優(yōu)解分布密集,而難以解決的區(qū)域則會出現(xiàn)資源短缺,Pareto最優(yōu)解分布稀疏。因此,在存在尖峰、長尾和不連續(xù)前沿的情況下,MOEA/D求解得到的近似Pareto前沿往往分布不均勻,解集無法完全覆蓋Pareto前沿。如何更快、更全面地搜索高質量種群,仍然是多目標進化算法領域需要進一步研究的問題。

近年來,針對MOEA/D算法在該問題上的缺陷,學者們針對改進權重向量分布做了許多工作。張寧等人針對不連續(xù)前沿問題提出了MOEA/D-DE-DC算法[7],該算法使用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚類方法,將不連續(xù)前沿轉化為多個連續(xù)前沿子問題。劉慶等人采用模擬退火的局部搜索方法提出了IMOEA/D[2],加強了復雜前沿的搜索能力。Dong等人提出了一種使用鏈式分段策略的自適應權重向量調整策略的MOEA/D-DE-CS算法[8],該算法從人口分布中導出鏈式結構以獲得適應前沿形狀的權重向量分布。此外,還出現(xiàn)了MOEA/D-URAW[9]、MOEA/D-STM[10]、MOEA/D-RWV[11]等調整權重的MOEA/D改進算法,但仍存在求解不穩(wěn)定和時間開銷大等問題。

為解決上述問題,本文提出基于角度自適應調整權重向量的MOEA/D-ATSAW(MOEA/D Based on Angle Trajectory and Self-Adaptive Weight)算法,該算法能夠在迭代中判斷前沿形狀,并自適應地選擇不同的權重向量分配策略,以提高Pareto解集的多樣性。具體而言,本文提出一種基于角度的聚類方法來準確識別前沿的形狀,該方法利用Pareto解的支配關系和分布特性,將歐氏距離計算轉化為角度計算,以簡化計算方式。為提高聚類結果準確性,采用軌跡聚類的方法,結合點集運動特征,將各個Pareto前沿分段盡可能相互連接,以保證算法求解的穩(wěn)定性。最后,MOEAD-AAWV算法根據(jù)聚類-合并結果采用不同的分布策略來分配子問題計算資源,以提高求解結果的多樣性。

1 基于切比雪夫分解的MOEA/D算法

MOEA/D中構造聚合函數(shù)的方法有加權求和法[12]、切比雪夫分解法[13]和基于懲罰的邊界交叉法[1]等,其中切比雪夫分解法應用最為廣泛。在MOEA/D中,將切比雪夫聚合函數(shù)值作為需要優(yōu)化的標量子問題,可以表示為

subject tox∈Ω,

(1)

MOEA/D算法流程如下:

Algorithm1 MOEA/DInput:1. 多目標優(yōu)化問題MOP;2. 算法停止標準:通常為最大迭代次數(shù)MAX gen;3. 種群規(guī)模:N;4. 鄰居數(shù)量:T;5. N個均勻分布的權重向量:λ1,λ2,…,λN。Output: EP(算法運行中得到的非支配解)Step 1. 算法初始化:1.1. EP=?;1.2. 對每個i=1,2,…,N,計算所有權重向量兩兩之間歐氏距離,求出與λi最接近的T個權重向量,得到集合B(i)={i1,i2,…,iT}, 其中i1,2,…,T為種群的下標, λi1,λi2,…,λiT是最接近λi的T個權重向量;1.3. 初始化種群x1,x2,…,xN,并計算相應目標函數(shù)值FVi=F(xi);1.4. 計算出當前最優(yōu)值(近似參考點)z=(z1,z2,…,zm)T。Step 2. 更新種群:對I=1,2,…,N重復以下操作2.1. 繁殖:隨機從B(i)中選取兩個下標k和l, 通過對xk和xl使用遺傳操作產(chǎn)生新解y;2.2. 改良:根據(jù)具體問題對y使用修復或啟發(fā)式,產(chǎn)生y′;2.3. 更新最優(yōu)值z: 對每個j=1,2,…,m, 若fi(y′)>zj(最大化問題中為zj

2 DBSCAN聚類算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一種基于密度的空間聚類算法,最早由Ester等人于1996年提出[14]。該算法通過指定參數(shù)距離閾值Eps和最小鄰居minPts,將具有足夠密度的樣本點劃分為一個簇,并遞歸地對該點鄰居進行相同操作,直到所有樣本點均被劃分或該點鄰居不滿足最小鄰居minPts為止,如圖 1所示。該算法的優(yōu)點是可以處理多種形狀的簇,且無需人為指定簇的數(shù)量。DBSCAN的這種特性適合將其應用于求解未知前沿的多目標優(yōu)化問題的算法,其樣本點p的鄰域可以被表示為

(2)

本文提出一種改進的DBSCAN算法,用于聚類Pareto前沿的帶狀簇。為應對Pareto前沿近似呈扇形分布的情況,該算法優(yōu)化了DBSCAN的距離計算方式。如圖2所示,使用樣本點與坐標軸原點連線與x軸的夾角大小作為樣本位置,將樣本間的角度差的絕對值作為判斷樣本點關系的指標,而不采用計算樣本點與核心點的歐氏距離的方式。通過該方法,數(shù)據(jù)維度從二維降至一維,不僅能降低聚類算法的時間復雜度,還能精準地判斷前沿是否連續(xù),從而采取相應的權重調整策略。需要注意的是,對于Pareto前沿值域不在[0,1]范圍內的函數(shù),該方法失效,因此需要對Pareto集做歸一化操作。

圖1 DBSCAN聚類示意圖

圖2 基于角度的DBSCAN聚類示意圖

圖3 對不連續(xù)前沿聚類示意

3 MOEA/D-ATSAW

在傳統(tǒng)MOEA/D算法中,采用均勻分布的權重向量來優(yōu)化多目標問題,每種權重分布對應一個標量優(yōu)化子問題,并在空間中呈均勻超平面分布。實際上,這種權重向量分布不能很好地適應非凸前沿、尖峰長尾以及不連續(xù)前沿等問題,從而導致較差的求解效果。MEOA/D-AAWV算法則通過自適應地調整權重向量分布,以實現(xiàn)對解集分布稀疏區(qū)域的資源傾斜,進而優(yōu)化求解結果。

3.1 前沿劃分與合并

當算法第一階段結束時,算法所求的解集已總體收斂至Pareto前沿區(qū)域,但往往解集多樣性較差,且部分處于尖峰、長尾或是不連續(xù)前沿端點的極端解難以求解,導致解集在這些區(qū)域中分布稀疏。對這些區(qū)域進行重點優(yōu)化,并對已知前沿通過改進的DBSCAN方法進行聚類,從當前解集中提取前沿信息,包括前沿的分布范圍和區(qū)域密度等信息,如圖 3所示,根據(jù)所得聚類部分數(shù)量,判斷其前沿形狀,對不連續(xù)前沿解集進行聚類,得到多個部分的Pareto前沿,可知其不連續(xù),如圖4。

圖4 對不連續(xù)前沿聚類結果

但此方法并不總是可行的,當算法第一階段所求得解集分布不均勻時,基于密度半徑的DBSCAN算法往往會因為樣本點間距離過大,樣本點分布稀疏而導致一條看似總體連續(xù)的前沿被劃分為多個部分,這將導致第二階段中,權重向量被全部分配于這些區(qū)域而導致空白區(qū)域的“饑餓”現(xiàn)象,且由于這些前沿片段往往長度較小,在其中分布著大量權重向量會導致這些區(qū)域的“飽和”現(xiàn)象。

為彌補DBSCAN方法單純依靠密度距離判斷的缺陷,本文引入軌跡聚類方法[15],并結合船舶軌跡聚類思想[16],通過定義每個前沿部分中Pareto解的方向角θ和角速度ω,判斷Pareto前沿所劃分的每個部分前后是否連續(xù),從而將其稀疏的前沿部分得以相對平滑地連接起來,正確分配權重向量注意力區(qū)域。因而在聚類合并中,對劃分所得的每個前沿部分維持一個角速度ω=Δθ/Δd,由于只關心每個部分前后能否相連,且只需關心前一部分尾部與后一部分頭部夾角關系,夾角通過式(3)計算:

(3)

(4)

前沿劃分-合并流程見算法2。

Algorithm2 基于點集運動狀態(tài)的軌跡合并Input:1. 聚類所得前沿劃分:Clusters;2. 角度閾值:Eps。Output:mergedClustersStep1. 對每個Clusteri,i=1,2,…,k執(zhí)行以下操作1.1 如newCluster為空,則將當前前沿劃分加入新聚類中,轉至Step 1;1.2 計算newCluster尾部變化率ωj=Δθ/Δd和Clusteri的首部夾角及其變化率ωij=Δθ/Δd;1.3 如newCluster和Clusteri的軌跡平滑,即ωij-ωj≤Eps,則將當前前沿劃分加入新聚類列表中,否則將newCluster加入mergedClusters中,并將Clusteri作為新的newCluster,轉至Step 1。Step 2.若newCluster不為空,則將newCluster加入mergedClus-ter中,并輸出mergedCluster。

3.2 自適應分布權重向量

MOEA/D-ATSAW自適應權重流程如算法3所示,其根據(jù)前沿劃分結果,將前沿分為三類:凸前沿、非凸前沿和不連續(xù)前沿。算法根據(jù)運行過程中對前沿分布進行分析,判斷前沿類型,從而選擇不同的調整策略使權重向量分布適應搜索情況。由于子問題與權重向量一一對應,因而在調整權重向量后,還需對子問題與相鄰子問題進行調整[7]。

Algorithm3自適應分布權重向量Input:1. 當前外部人口:EP;2. 聚類參數(shù):Eps, minPts。Output:newVectorsStep 1. 對EP歸一化處理Step 2. 根據(jù)EP計算前沿數(shù)量2.1 對EP進行聚類,其閾值為Eps, 最小鄰居為minPts,獲得前沿分段EP_clusters;2.2 對EP_clusters執(zhí)行Algorithm2,合并分段得到merged-Clusters。Step 3. 判斷mergedClusters中分段數(shù)量,若等于1則為連續(xù)前沿,執(zhí)行Step 4,否則執(zhí)行Step 5Step 4. 若為連續(xù)前沿,執(zhí)行以下操作4.1 根據(jù)凸函數(shù)定義判斷前沿形狀,若為凸函數(shù)則采用均勻分布數(shù)量權重,若為非凸則采用不均勻分布;4.2 將EP按區(qū)域劃分,判斷各區(qū)域數(shù)量;4.3 根據(jù)各區(qū)域Pareto解所占種群比例,乘以數(shù)量權重系數(shù)得到新的區(qū)域分配數(shù)量;4.4 重新分配各區(qū)域的權重向量,得到newVectors。Step 5. 若為不連續(xù)前沿,執(zhí)行以下操作5.1 計算各前沿分段的長度;5.2 根據(jù)各分段所占總長度的比例與Pareto解所占種群比例分配權重向量,得到newVectors。Step 6. 重新調整鄰居B(i)={i1,i2,…,iT},i=1,2,…,NStep 7. 重新調整種群,對每個權重向量λ1,λ2,…,λN分配其切比雪夫值最小的個體?

由于非凸前沿不存在尖峰和長尾，只需維持總體的均勻分布，可在局部稀疏部分做微小調整，如圖5所示。而凸前沿由于存在尖峰和長尾現(xiàn)象，這兩個區(qū)域的子問題分布較少，難以在狹長區(qū)域中獲得均勻的Pareto分布。因此，需要采用特殊的策略使權重向量的分布由均勻轉向兩端稠密、中間相對稀疏。在MOEA/D-ATSAW算法中，采用開口朝上的拋物線函數(shù)做比例映射實現(xiàn)該策略。該函數(shù)具有定義域兩端梯度較大、中間部分梯度較小的特性，可以使權重向量較多地集中在尖峰和長尾區(qū)域，即搜索區(qū)域的高低兩側。分區(qū)數(shù)為10的情況如圖6所示，其中心區(qū)域子問題較為稀疏，第一階段的搜索已使中心區(qū)域子問題密集，由于MOEA/D的精英策略，后期改變權重向量分布不會導致Pareto解丟失，而尖峰長尾區(qū)域則會因為子問題的增多而分布更密集。

圖5 均勻分布權重向量

圖6 不均勻分布權重向量

圖7 MOEA/D-ATSAW在ZDT測試函數(shù)上的近似Pareto前沿及其映射后的權重向量分布

圖8 算法迭代過程中IGD數(shù)值

對于不連續(xù)的Pareto前沿，MOEA/D-ATSAW采用與雷達相似的思想，加上一定誤差范圍(本文中取Eps)的區(qū)域進行加權向量的分配，而不存在Pareto解分布的區(qū)域將不會被分配權重向量，這樣可以避免子問題資源被浪費在空白區(qū)域的無用搜索中，亦能優(yōu)化已有前沿的分布。而前沿部分±Eps擴大前沿部分的搜索區(qū)域，盡可能保證Pareto前沿被完整搜索，即使存在多個不連續(xù)前沿僅能搜索到一個Pareto解的極端情況，MOEA/D-ATSAW也可以經(jīng)過多次調整擴大其搜索范圍，有更高的幾率搜索到完整前沿，提高搜索性能。此外，對某些搜索難度較大的連續(xù)前沿，往往會因初期搜索結果不理想而被誤判為不連續(xù)前沿，因而使用此方法不斷擴大各個部分的搜索范圍，結合聚類-合并策略，可以使MOEA/D-ATSAW能在第二階段搜索中合并成為連續(xù)前沿。

4 實驗與分析

為驗證MOEA/D-ATSAW自適應權重向量對優(yōu)化尖峰、長尾及不連續(xù)前沿優(yōu)化等問題求解結果的有效性，選取廣泛使用的多目標測試函數(shù)ZDT1、ZDT2、ZDT3、ZDT4和ZDT6[17]進行實驗分析，選擇同類改進的自適應權重向量算法MOEA/D-AAWN[18]、MOEA/D-AWA[19]、MOEA/D-M2M[20]與不調整權重向量的基于切比雪夫分解法的多目標優(yōu)化算法MOEA/D[1]，與最具代表性的基于Pareto支配關系和擁擠距離排序的多目標遺傳算法NSGA-II[21]作對比。運用廣泛使用的反向世代距離IGD作為性能指標定量分析算法性能。

4.1 性能指標

使用在多目標優(yōu)化問題研究中應用最為廣泛的反向世代距離IGD(Inverted Generational Distance)[22]作為評價指標來評估算法求解結果的收斂性和多樣性。假設解集PF*為從真實Pareto前沿均勻采樣的一組解，PF為真實Pareto前沿，則反向世代距離IGD可以被表示為

(5)

4.2 參數(shù)設置

為排除其他因素對算法求解效果的影響，在參與實驗的所有算法中，均采用模擬二進制交叉算子(SBX)[23]和多項式變異算子(PM)[24]產(chǎn)生子代，其中交叉概率為CR=1.0，多項式變異概率為MR=1.0，交叉和變異參數(shù)設置為Nc=20，Nm=20。種群規(guī)模N=150，相鄰子問題數(shù)量T=15，最大迭代次數(shù)MAXgen=300，其余參數(shù)與其原文一致。

4.3 實驗結果與分析

實驗結果表明，MOEA/D-ATSAW在優(yōu)化權重向量分布的改進算法中，不論測試函數(shù)的前沿分布連續(xù)或不連續(xù)，相較其他算法均有性能提升，各算法IGD數(shù)據(jù)如表1所示。從表1的結果可以看出，對測試函數(shù)ZDT1、ZDT2、ZDT3、ZDT4和ZDT6，MOEA/D-ATSAW具有最佳性能表現(xiàn)。特別地，對于測試函數(shù)ZDT3的不連續(xù)前沿，MOEA/D-ATSAW算法體現(xiàn)出其優(yōu)越性，IGD指標顯著降低。相比未調整權重向量分布的算法，該算法在優(yōu)化多目標問題上具有明顯的優(yōu)勢。

表1 各算法IGD指標均值(方差)

MOEA/D-ATSAW在ZDT測試集上所得Pareto前沿及其映射后的權重向量分布如圖 7所示，其權重向量取最后一次調整的分布。算法計算EP中各部分前沿的稀疏程度后，為不同密度的前沿分段分配權重向量，在解分布較少的部分權重向量分布相對稠密，而解分布密集的部分減少權重向量的分配，僅留下部分作為優(yōu)化Pareto解分布之用。

5 結語

針對多目標優(yōu)化問題中求解難度較高的復雜前沿和不連續(xù)前沿問題，提出一種基于MOEA/D算法的新型算法——MOEA/D-ATSAW，增加了一種新的聚類-合并Pareto前沿劃分方法，不同于以往計算樣本點歐氏距離的做法，本文根據(jù)Pareto解的分布特征，采用基于幾何角度的方式計算樣本點之間的距離，相比較于傳統(tǒng)方法，該方法的性能開銷更小且更精準。此外，本文結合軌跡聚類中的方法，類似于船舶軌跡聚類，賦予樣本點運動學特征，根據(jù)Pareto前沿分段的分布特性和平滑特征，使其盡可能地合并為一條總體平滑、連續(xù)的Pareto前沿，這種聚類-合并方法所產(chǎn)生的Pareto分段為下一步的權重向量調整策略奠定良好基礎。

同時，還提出了新的自適應多策略權重向量調整機制，它根據(jù)Pareto前沿劃分所得分段，并根據(jù)前沿的分段數(shù)量、分段長度、分段中解的數(shù)量及分布特征判斷前沿類型和形狀，再自適應地采取不同分配策略，針對各個前沿分段或劃分區(qū)域，分配不同數(shù)量和密度的方向向量，同時根據(jù)切比雪夫分解法的幾何特性，將其映射到權重向量。通過這種方法傾斜子問題搜索資源以適應不同前沿類型，獲得更好的Pareto前沿分布。通過相鄰子問題調整和種群重分配，將每個子問題對應到更優(yōu)的權重向量，即切比雪夫函數(shù)值更小的權重向量上，維持算法在調整之后的穩(wěn)定性。

MOEA/D-ATSAW在ZDT測試函數(shù)上的實驗結果表明，在相同的參數(shù)和遺傳操作下，MOEA/D-ATSAW不僅性能和求解效率優(yōu)于其他算法，且權重向量經(jīng)過調整后并未造成求解結果的劇烈波動，其性能指標曲線平滑穩(wěn)定，證明了本文改進的Pareto前沿聚類劃分方法和多策略權重向量調整機制的有效性。后續(xù)研究計劃將MOEA/D-ATSAW算法進一步擴展到高維多目標問題上，利用基于角度的優(yōu)勢降低對高維多目標問題的前沿評估難度，以求更低復雜度地計算前沿信息，為自適應方法提供環(huán)境信息，從而更好調整參數(shù)，加快算法收斂速度。