基于事件觸發(fā)的自適應鄰域多目標進化算法

王學武， 夏澤龍， 顧幸生

（華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室，上海 200237）

工業(yè)生產(chǎn)中經(jīng)常存在多個目標的優(yōu)化問題，多目標優(yōu)化算法為此類問題提供了解決辦法，因此多目標進化算法成為近些年的研究熱門[1-2]。在對多目標問題進行優(yōu)化時，主要考慮兩個問題[3]：一是解的收斂性；二是解的多樣性。

為了有效地解決上述兩個問題，眾多學者提供了解決思路。李笠等[4]提出了基于網(wǎng)格排序的多目標粒子群優(yōu)化算法，利用網(wǎng)格排序的方法對粒子群算法非劣解的儲備集進行優(yōu)化，有效地增強了算法的多樣性。Zhang 等[5]提出了一種基于分解的多目標粒子群優(yōu)化算法(MOPSO/D)，將基于分解的多目標算法與粒子群結(jié)合，利用改進變異算子增強解的多樣性，利用儲備集的方式對非劣解進行儲存。Jaimes等[6]指出采用多種群策略對多目標優(yōu)化問題進行求解，利用種群間的信息交流，不僅能夠提高搜索效率，而且能夠增加種群的多樣性。Li 等[7]提出基于差分進化算法的分解多目標優(yōu)化算法(MOEA/DDE)，利用差分進化算法收斂速度快、實現(xiàn)簡單等特點來改進算法。Qi 等[8]提出基于自適應權(quán)重調(diào)整的分解多目標進化算法(MOEA/D with Adaptive Weight Adjustment，MOEA/D-AWA)，采用自適應的方法改變權(quán)重，使解在空間上的分布更加均勻。Yuan 等[9]提出了基于距離更新策略的分解多目標進化算法(MOEA/D with a Distance-Based Updating Strategy，MOEA/D-DU)，采用改進的切比雪夫聚合函數(shù)，利用子問題的垂直距離作為指導，提高算法在高維目標中的應用效果。畢曉君等[10]提出了基于雙種群的約束多目標優(yōu)化算法，采用兩個種群交流和改進的Harmonic 距離對算法進行改進，提高算法優(yōu)化效果。

以上算法在逼近真實前沿面上具有較好的效果，但解的多樣性不足且在空間上分布不夠均勻。為了提高解的多樣性，改善解在空間分布不均勻的問題，協(xié)調(diào)算法搜索過程的收斂性與多樣性，本文提出了基于事件觸發(fā)的自適應鄰域多目標進化算法(MOEA/D-ET)。采用事件觸發(fā)策略協(xié)調(diào)全局搜索與局部搜索，網(wǎng)格法進行全局搜索為局部搜索作指導，MOEA/D 算法進行局部搜索，并且針對解分布不均勻的問題，采用自適應鄰域的方法進行改進。

1 MOEA/D-ET 算法

在搜索過程中，MOEA/D-ET 算法通過事件觸發(fā)機制改變種群全局搜索與局部搜索功能，且產(chǎn)生的子代直接與父代比較、替換，不通過儲備集的方式，可以在保證算法收斂性與多樣性的同時減少計算消耗。

1.1 網(wǎng)格法尋優(yōu)

面對多目標問題時[11]，通常使用笛卡爾坐標系(Cartesian Coordinate System)。網(wǎng)格法則是將笛卡爾坐標系下的粒子坐標進行網(wǎng)格化，并對每個網(wǎng)格中粒子間的相對距離進行定義。根據(jù)粒子間的相對距離以及非支配關(guān)系對網(wǎng)格內(nèi)的粒子進行管理。

定義1[12]網(wǎng)格的上下邊界：在m 個優(yōu)化目標下，設 fmax(x) 為當前種群的最大適應度值， fmin(x) 為當前種群的最小適應度值，網(wǎng)格的上下邊界為 ub與 lb。

式中，div 為網(wǎng)格劃分系數(shù)。

根據(jù)所建立的網(wǎng)格坐標系，計算所有粒子在網(wǎng)格上的坐標。第i 個粒子的網(wǎng)格坐標計算如下：

其中 Gip為網(wǎng)格坐標。求解的坐標進行向下取整操作，則為第i 個粒子的坐標。

在網(wǎng)格坐標系下，粒子間的相對距離為兩粒子橫縱坐標相差之和，例如圖1 中粒子A、B 的相對距離 DAB為4。

圖 1 網(wǎng)格坐標系示意圖Fig. 1 Schematic diagram of grid coordinate system

在網(wǎng)格坐標系上，根據(jù)各個粒子的非支配關(guān)系選擇父代。首先選擇非支配粒子，若兩個不同粒子同為非支配解且在網(wǎng)格坐標系中有相同坐標，如圖1 中D、E 所示，則計算它們的網(wǎng)格坐標點距離(GCPD)[12]，計算公式如下：

選擇GCPD 較小的作為父代，可以免去計算當前個體對所有其他粒子的距離，大大減少計算量。

1.2 基于分解的多目標進化算法

MOEA/D 算法將多目標問題分解成一組若干子目標問題進行求解?？紤]的目標為兩目標和三目標問題時，采用切比雪夫(Tchebycheff)聚合函數(shù)進行求解，描述如下[6]：

其中： λ =(λ1,λ2,···,λk) 為子問題的權(quán)重； fi(x) 為第i 個優(yōu)化目標函數(shù)值； z*為理想?yún)⒖键c。理想?yún)⒖键c的更新公式如下：

如此可將迭代過程中的歷史極小值信息保存下來，使算法收斂速度更快，解的精度得以提高。

采用切比雪夫法求解多目標問題時，需要利用切比雪夫方法找出子問題 g (x|λ,z*) 的最大值。通過改變決策變量 x ，使最大的 g (x|λ,z*) 接近理想?yún)⒖键c，則其余子問題也相應接近理想?yún)⒖键c。

1.2.1 自適應鄰域MOEA/D 在MOEA/D 算法中，子代粒子的產(chǎn)生受其父代鄰域粒子的影響，鄰域的大小對算法有很大的影響。若鄰域設置為固定大小會導致解的分布不均勻，尤其是在凹凸性較大的Pareto 前沿面。如圖2 所示，解在前沿面的中心區(qū)域分布較密集，邊界附近相對稀疏。

圖 2 固定鄰域MOEA/D 非劣解分布圖Fig. 2 Distribution of non-inferior solutions of MOEA/D with uniform neighborhood

若鄰域設置過大，在更新過程中，父代與鄰域內(nèi)的其他個體比較次數(shù)太多，浪費計算資源。此外，過大的鄰域雖然會提升算法的多樣性，但同時會產(chǎn)生偏離Pareto 前沿的新解，導致種群退化。鄰域設置較小，雖然有利于尋找局部最優(yōu)解，逼近真實Pareto 前沿，但無法保證算法的多樣性。基于以上分析，對鄰域進行自適應調(diào)整，自適應調(diào)整方式如下：

1.2.2 MOEA/D 變異策略 MOEA/D 算法將多目標問題分解為多個子目標問題進行求解，Li 等[7]闡述了差分進化策略有利于提高MOEA/D 算法的性能。采取如下方式進行變異：

其中： xi為當前迭代粒子； xr2,xr3為當前種群隨機選擇的差分向量；F 為變異步長；為通過重組產(chǎn)生的新個體。

變異步長F 的大小對解的精度有很大影響。若F 設置較大，每次產(chǎn)生的新個體相對父代變異步長大，算法的多樣性增加，局部搜索能力減弱；F 設置較小則相反。為了在搜索過程中不至于太快陷入局部最優(yōu)，本文設置F 如下：

式中：k 為縮放系數(shù)。通過這種調(diào)節(jié)方式使搜索分為3 個階段：第一階段F 較大，保證了搜索初期種群的多樣性；第二階段F 不斷減小，為過渡階段，保證第三階段不至于太早陷入局部最優(yōu)；第三階段F 設置較小，尋找最優(yōu)解，提高搜索精度。變異策略中交叉概率CR 設為1，可提高種群多樣性，并且使解具有旋轉(zhuǎn)不變的特性。

1.3 選擇策略

1.3.1 全局搜索選擇策略

定義2Pareto 支配關(guān)系： x1， x2∈x ，若fi(x1)≤fi(x2),i=1,2,···,m 且存在 k ∈{1,2,···,m} ，使fk(x1)＜fk(x2) ，則稱 x1支配 x2或 x2受 x1支配，此時的 x1為非支配解。

父代與子代混合，根據(jù)支配關(guān)系進行排序，將非支配解的粒子序號定為1，僅受1 個粒子支配的序號為2，依次類推。排列序號靠前的個體根據(jù)網(wǎng)格法進行選擇，選出與種群大小相同的粒子數(shù)。若序號為1 的粒子數(shù)量小于初始種群大小，則從序號為2 的粒子中引入，以此類推。如此選出的種群在空間上分布較為均勻，同時也相對貼近真實Pareto 前沿面(PF)，可為接下來的局部搜索提供一個較好的指導作用。

1.3.2 局部搜索選擇策略 通過全局搜索選擇的粒子仍存在分布不均勻、不夠貼近真實PF 的問題，因此還需要進行局部搜索。局部搜索采用MOEA/D 算法進行搜索，為了使搜索到的非劣解盡可能貼近真實PF，并且在空間上分布均勻，需要對父代的替換策略進行改進。MOEA/D 算法替換策略如下：

（1）利用自適應方式設置可替換父代的鄰域大小。

（2）計算父代及其鄰域的支配關(guān)系、擁擠距離。

（3）通過變異策略方式生成子代。

（4）子代替換父代鄰域內(nèi)的粒子，替換策略流程圖如圖3 所示。

圖 3 替換策略圖Fig. 3 Substitution strategy

圖3 中，dis(p,o)為父代與鄰域其他粒子的總距離，dis(c,o)為子代與鄰域其他粒子的總距離，fitness為適應度函數(shù)。若鄰域內(nèi)替換的粒子數(shù)過少，種群更新緩慢，收斂速度慢；如果替換數(shù)量較多，收斂速度快，容易陷入局部最優(yōu)，計算成本增加。

1.4 事件觸發(fā)機制

若全局搜索次數(shù)過多，雖然解分布廣泛，但無法有效地逼近真實PF。若搜索次數(shù)過少，就開始進行局部搜索，會陷入局部最優(yōu)，并造成不必要的計算消耗。因此設計事件觸發(fā)機制對全局搜索與局部搜索進行協(xié)調(diào)與平衡。

采用更新粒子比率（ r atio ）對全局搜索與局部搜索進行協(xié)調(diào)與平衡， r atio 計算公式如下：

其中： n um_c 為全局搜索中更新粒子的數(shù)量；N 為種群大??； n um 為局部搜索中更新粒子的數(shù)量。當更新粒子所占比率較大時，說明所產(chǎn)生的非劣解相距PF 較遠，或解在空間上分布不均勻。當更新比率較小時，說明解已經(jīng)逼近PF，此時需要對解的精度與分布性進行提高。

ratio 的大小對算法的分布性與收斂性有一定影響。采用三維測試函數(shù)DTLZ2，在10 維決策空間情況下，改變ratio 的大小對算法HV 與IGD 指標的影響結(jié)果如表1 所示。測試指標IGD 和HV 可以綜合評判算法的收斂性與多樣性，其中IGD 為反轉(zhuǎn)世代距，HV 為非支配解集中所有非支配解與參考點圍成的超立方體的體積。

表 1 ratio 對算法性能的影響Table 1 Influence of ratio on algorithm performance

從表1 可以看出，ratio 為0.55 時，算法的HV 值最大，解分布較廣，但此時不夠貼近真實PF。ratio 為0.25 時，IGD 值最小，解的分布最貼近真實PF，且此時HV 值為次優(yōu)，說明算法在空間分布上較廣。嘗試選擇ratio＞0.55 時觸發(fā)全局搜索，ratio＜0.25 時觸發(fā)局部搜索，通過實驗得出此時的HV 為0.416 098 11，IGD 為0.051 974 819，算法效果反而下降。綜合分析ratio 參數(shù)設置為0.25 較為合適。

1.5 MOEA/D-ET 算法流程

（1）初始化：初始化網(wǎng)格大小div，種群大小N，子代更新比率 r atio ，構(gòu)造權(quán)重向量w，初始化種群，迭代次數(shù)。

（2）更 新： G ene={1,2,···,Generations} ，判 斷ratio的大小以及目標數(shù)，根據(jù)事件觸發(fā)機制選擇觸發(fā)全局搜索機制或局部搜索機制。

（3）輸出：若算法滿足停止條件，則停止并輸出Pareto 前沿及相應的評價指標值，否則返回步驟（2）繼續(xù)執(zhí)行。

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

圖 4 MOEA/D-ET 算法流程圖Fig. 4 Flow chart of MOEA/D-ET algorithm

2 仿真實驗與分析

為了驗證本文算法在求解多目標優(yōu)化問題上的性能，選取3 個系列的測試函數(shù)如表2 所示。其中ZDT、WFG 為二目標測試函數(shù)，DTLZ 為三目標測試函數(shù)，Dim 為決策變量空間維數(shù)。測試環(huán)境為Intel(R)Core(TM) i5-4200H CPU @ 2.80 GHZ。

表 2 ZDT、WFG、DTLZ 測試函數(shù)Table 2 Dimension of decision space in ZDT, WFG and DTLZ

選擇4 個經(jīng)典的多目標算法CMPSO[13]、MOEA/D[5]、NSGA-II[14]、PSEA-II[15]以及2 個最新的多目標算法LG_MOPSO[16]、NSGA-III[17]作為對比算法。其中CMPSO 為基于密集距離的多目標粒子群優(yōu)化算法；MOEA/D 為基于分解的多目標優(yōu)化算法；NSGA-II 為帶精英策略的快速非支配排序遺傳算法；PSEA-II 為利用遺傳算法的機理和基于Pareto 包絡選擇的多目標優(yōu)化算法；LG_MOPSO 為利用聚類選擇指導粒子的多目標粒子群算法；NSGA-III 為一種基于參考點的非支配排序算法。

2.1 實驗參數(shù)設定

在相同條件下對每個算法進行對比，每個算法進行20 次獨立實驗。算法的種群規(guī)模均設為100，迭代次數(shù)為400。在MOEA/D-ET 中，網(wǎng)格大小div在二目標中設置為45，在三目標中設置為20。局部搜索中，子代替換父代個數(shù)設置為10，其余參數(shù)設置如文中所述，其他算法的參數(shù)均參考相應文獻。

2.2 實驗結(jié)果分析

表3～表5 列出了各種算法在IGD 均值（IGDm）、IGD 方差(IGDstd)、HV 均值(HVm)上的實驗結(jié)果，其中的黑體為最優(yōu)結(jié)果。在IGD 均值上，本文算法在13 個測試函數(shù)中有10 個測試函數(shù)的均值都要優(yōu) 于CMPSO、MOEA/D、NSGA-II、PSEA-II、LG_MOPSO、NSGA-III。在另外兩個測試函數(shù)DTLZ1、DTLZ2 上，NSGA-III 效果最好，在本文算法的測試結(jié)果為次優(yōu)。在DTLZ7 測試函數(shù)上LG_MOPSO 效果最好。IGD 方差上，在本文算法在13 個測試函數(shù)中有9個測試函數(shù)的方差都小于其他算法。在ZDT1、ZDT2、ZDT3、WFG4、DTLZ2、DTLZ3 測試函數(shù)上的方差遠遠 小 于 CMPSO、 MOEA/D、 NSGA-II、 PSEA-II、LG_MOPSO、NSGA-III。在其他測試問題上，雖然本文算法的IGD 方差結(jié)果并不是最好，但都達到了10-5，說明算法魯棒性較好。HV 性能指標上，本文算法在13 個測試函數(shù)中有10 個測試函數(shù)的測試結(jié)果要 優(yōu) 于 CMPSO、 MOEA/D、 NSGA-II、 PSEA-II、LG_MOPSO、NSGA-III。在ZDT3 問題上，LG_MOPSO測試結(jié)果最好，在WFG1、DTLZ1 問題上，NSGAIII 測試結(jié)果最好，本文算法表現(xiàn)為次優(yōu)。這說明雖然通過自適應鄰域方式對算法進行了改進，改善了算法在尋優(yōu)過程中解出現(xiàn)中間區(qū)域密集、兩端稀疏的問題，但面對邊緣凹凸性較大問題時，相較于NSGA-III 算法，本文算法在搜索能力上仍需要改進。

表 3 7 種算法的IGD 均值比較結(jié)果Table 3 Comparison of the mean value of IGD index for seven algorithms

表 4 7 種算法的IGD 方差比較結(jié)果Table 4 Comparison of IGD index variance results for seven algorithms

表 5 7 種算法的HV 均值比較結(jié)果Table 5 Comparison of the mean value of HV index for seven algorithms

從表3～表5 可以看出，本文算法在大部分測試函數(shù)上都優(yōu)于CMPSO、MOEA/D、NSGA-II、PSEAII、LG_MOPSO、NSGA-III，尤其在HV 指標上的測試結(jié)果較好。雖然對于測試函數(shù)ZDT3、WFG1、DTLZ1問題上為次優(yōu)，但與最優(yōu)指標僅僅相差10-4～10-2，說明本文算法在空間上分布范圍廣，多樣性較好。在IGD 指標上表現(xiàn)出的效果大部分要優(yōu)于其他算法，在DTLZ7 測試問題上，LG_MOPSO 算法在IGD 均值及方差測試上得到較好的結(jié)果，但在HV 均值上結(jié)果較差，說明該算法在該問題所找出的非劣解空間分布范圍有限，而本文算法在IGD 均值及方差測試上為次優(yōu)，但在HV 均值上結(jié)果最優(yōu)。綜合分析，在DTLZ7 問題上，本文算法也要優(yōu)于LG_MOPSO。NSGA-III 算法在WFG1、DTLZ1 問題上測試效果較好，但本文算法均為次優(yōu)且與最優(yōu)值相差很小，可通過繼續(xù)深入研究鄰域關(guān)系提升算法的性能。以上分析表明，本文算法搜索到的非劣解空間分布廣，多樣性好，在保證解的精度與算法收斂性的同時減少了不必要的計算消耗。

為了更直觀地展示本文算法所獲得非支配解的質(zhì)量和分布情況，繪制非支配解集的分布圖與真實PF 對比，如圖5、圖6、圖7 所示。圖5 示出了ZDT系列部分測試函數(shù)圖，圖6 示出了WFG 系列部分測試圖，圖7 示出了DTLZ 系列部分測試函數(shù)圖。從圖中可以看出，本文算法與真實PF 吻合度較高，解的分布空間廣泛，較好地平衡了求解多目標問題中的收斂性與多樣性。

2.3 固定鄰域與自適應鄰域?qū)Ρ确治?/h3>

設置固定鄰域大小為10、50、100；自適應鄰域設置如文中所述。兩種鄰域方式的種群大小設置為100，迭代次數(shù)為400。

在ZDT1 上的測試結(jié)果如表6 及圖8 所示。從圖8(a)、(b)、(c)可以看出，固定鄰域情況下，將鄰域大小設置較小、適中、較大，非劣解在空間上的分布依舊存在兩端分布稀疏、中心區(qū)域分布集中的現(xiàn)象。從圖8(d)可以看出，采用自適應鄰域策略后，非劣解在空間上的分布更加均勻，改善了固定鄰域下非劣解相對集中于中心區(qū)域的問題，使解在空間上分布更加均勻。

圖 5 ZDT 系列部分測試函數(shù)圖Fig. 5 Part of ZDT series test function diagrams

圖 6 WFG 系列部分測試函數(shù)圖Fig. 6 Part of WFG series test function diagrams

圖 7 DTLZ 系列部分測試函數(shù)圖Fig. 7 Part of DTLZ series test function diagrams

從表6 可以看出，自適應鄰域在IGD 均值上的表現(xiàn)優(yōu)于固定鄰域，說明采用自適應鄰域方式尋找的非劣解更加逼近真實PF。在HV 均值上自適應鄰域的表現(xiàn)同樣優(yōu)于固定鄰域，說明采用自適應鄰域方式尋找到的非劣解空間分布廣。

表 6 4 種鄰域策略在ZDT1 問題上IGD、HV 指標對比Table 6 Comparison of IGD and HV indexes for 4 neighborhood strategies on ZDT1 problem

圖 8 固定鄰域與自適應鄰域在ZDT1 問題測試對比Fig. 8 Comparison of fixed neighborhood and adaptive neighborhood in ZDT1 problem

3 結(jié)束語

本文提出了基于事件觸發(fā)的自適應鄰域多目標進化算法，采用更新粒子比率作為事件觸發(fā)的條件對全局搜索與局部搜索進行調(diào)節(jié)。全局搜索主要采用網(wǎng)格法，旨在保證解的多樣性的情況下在較短時間逼近真實PF。局部搜索采用自適應鄰域MOEA/D方法提高解的精度，使解在空間分布更加均勻。全局搜索與局部搜索產(chǎn)生的非劣解通過事件觸發(fā)機制相互交流，相互指引，大大提高了算法性能。通過對標準測試函數(shù)進行仿真實驗，并與6 個多目標優(yōu)化算法進行比較，結(jié)果表明本文算法所得出的非劣解在多樣性與收斂性上有很大的提升。分析了固定鄰域與自適應鄰域?qū)λ惴ǖ挠绊?，通過測試結(jié)果可以看出，采用自適應鄰域方法在前沿面的逼近與非劣解的分布上都有著很好的效果。接下來會將此算法離散化，應用于焊接機器人[18]軌跡、能耗、變形等參數(shù)的多目標優(yōu)化中。