基于自適應反向學習的多目標分布估計算法

李二超，楊蓉蓉

（蘭州理工大學電氣工程與信息工程學院，蘭州 730050）

0 引言

多目標優化問題（Multi-objective Optimization Problem，MOP）通常是指同時對多個相互作用又相互沖突的優化目標進行求解，因此該類問題在盡量滿足決策者需求的情況下，只能求得多個折中解，即滿意解。目前用于求解多目標問題的優化算法已經被廣泛應用在車輛調度［1］、0-1背包問題［2］、個性化搜索問題［3］和指尖定位［4］等。

多目標優化進化算法的實現主要模擬生物進化特性，比如應用了自然進化中選擇、交叉以及變異等操作的多目標遺傳算法（Non-dominated Sorting Genetic Algorithms Ⅱ，NSGA-Ⅱ）［5］；模擬鳥群或魚群群體行為的多目標粒子群優化算法［6］；模擬螞蟻覓食行為的蟻群算法［7］等。而通過數學建模的方法來解決多目標優化問題的研究工作相對較少。Larra?ga 等［8］提出了一種新的進化算法：基于數學建模和概率統計的分布估計算法（Estimation of Distribution Algorithm，EDA），該算法的提出主要解決遺傳算法中交叉、變異操作破壞積木塊的問題。在EDA 中沒有選擇、交叉以及變異等操作，只是從歷史解中提取決策空間的信息并建立期望解的概率分布模型，對其進行采樣從而產生新解。2008 年Zhang 等［9］提出基于規則模型的多目標分布估計算法（Regularity Model-based Multiobjective Estimation of Distribution Algorithm，RM-MEDA），該算法在建模初期，采用局部的主成分分析方法為被劃分為多個不相交類別的種群建立對應的流形，以刻畫種群分布；再對各個流形建模、采樣，從而產生新解。RM-MEDA 在解決多目標優化問題時主要存在兩個問題：一是在建立概率模型時，RM-MEDA 沒有充分發掘各種不同類型多目標優化問題的特征，這使得所建立的概率模型不夠準確，這也是EDA 普遍存在的問題；二是由于該算法在建模初期對種群進行聚類，不利于子代的搜索，使得RM-MEDA 的全局搜索能力較弱，很難快速收斂。

針對EDA 存在的全局搜索能力差問題，高尚等［10］將摸石頭過河算法與分布估計算法的優點進行結合，首先以一個解為起點，向該起點附近鄰域隨機搜索若干個解，找出這些解中最好的一個解；并挑選部分優秀個體的中心與最好解進行交叉操作，以此解作為下次迭代的結果，然后以此點為起點，再向附近鄰域隨機搜索若干個解，以此類推，最終提高算法的收斂速度和精度。2017 年高尚等［11］提出一種基于正態分布的多目標分布估計算法，依據自然界中很多隨機變量的概率分布都可以近似地用正態分布描述，進而將正態分布引入到分布估計算法中，使得算法有良好的收斂性和分布性，并且效果穩定。RM-MEDA 作為EDA 中的典型優化算法，很多學者對其進行了研究并給出改進的相關策略或方法。羅辭勇等［12］提出了兩步訓練法改進RM-MEDA，與原算法不同的是在建模初期依次采用均值聚類法和流形聚類法進行聚類，改進后的算法明顯縮短了EDA 的尋優時間，但算法的收斂性和種群多樣性并沒有較大改進。為了提高RM-MEDA 的全局搜索能力，很多學者將RM-MEDA 與其他經典的多目標優化算法進行了結合?；谀娼５亩嗄繕诉M化算法（Inverse Modeling based MultiObjectiveEvolutionary Algorithm，IM-MOEA）［13］是另一種基于連續多目標問題的規則屬性的分布估計算法，王慧君［14］將RM-MOEA 與IM-MOEA 設計成一種混合算法，通過IM-MOEA 在算法前期充分挖掘帕累托解集和帕累托前沿的規則，以提高RM-MOEA 的收斂速度和種群的分布性。吳燁燁等［15］對RM-MEDA 的改進是：首先通過正交設計產生的初始種群使得個體均勻分布在可行解域，加快算法的收斂并提高種群的分布性，同時加入遺傳算法來進化算法迭代中的種群。因此該算法初期使用分布估計算法進行快速的全局搜索，在算法后期主要利用遺傳算法的交叉、變異進行局部尋優，增強算法的局部搜索能力。該算法還引入小生境技術和精英策略進行了算法優化，但是在提高算法性能的同時，由于引入多個策略，降低了算法的運行速度。以上對EDA 以及RM-MEDA 的研究，改進的方法適用性不強，有些改進甚至增加了算法的復雜性。

考慮到RM-MEDA 在早期種群中個體分布還未呈現一定的規律時就進行建模，使得產生的新解很難快速收斂；同時，該算法采用隨機的方法初始化種群，使得初始種群不能均勻地分布在可行解空間，影響了算法的尋優速度。本文提出基于自適應反向學習的多目標分布估計算法（Multi-objective Estimation of Distribution Algorithm with Adaptive Oppositionbased Learning，AOL-MEDA），它在RM-MEDA 基礎上，通過自適應引入反向學習，一定程度地提高算法的收斂性和算法迭代中種群個體的多樣性。

1 問題描述

一般的MOP 由N個決策變量參數、M個目標以及約束條件組成，目標函數、約束條件與決策變量之間是函數關系。最優化目標一般可以描述如下：

其中：Ω代表決策空間，x=(x1，x2，…，xN)T∈Ω為N維決策變量；Θ代表目標空間，F(x)=(f1(x)，f2(x)，…，fM(x))T∈Θ為M個目標函數；gi(x) ≤0(i=1，2，…，p)為p個不等式約束條件；hi(x)=0(i=1，2，…，q)為q個等式約束條件。

多目標優化問題就是尋求x=(x1，x2，…，xN)T∈Ω，使得f(x)在滿足約束條件的情況下達到最優。

個體支配關系 對于任意兩個解x，y∈Ω，如果?i∈{1，2，…，M}滿足fi(x) ≤fi(y)，且?j∈{1，2，…，M}滿足fj(x) ＜fj(y)，則稱x支配y（記為x?y）。

Pareto 最優解（Pareto optimal solution） 如果x∈Ω，不存在y∈Ω使得y?x成立，則稱x是Pareto 最優解。所有Pareto最優解組成的解集為Pareto 最優解集。Pareto 最優解對應的目標函數值組成的解集稱為Pareto 前沿（Pareto Front，PF），即：

2 AOL-MEDA

2.1 反向學習機制

反向學習（Opposition-Based Learning，OBL）的概念被Tizhoosh［16］在2005 年提出，通過概率證明了當前解有50%的概率比它的反向解更加遠離全局最優解，其主要思想是在當前個體所在區域依據當前個體信息產生反向個體，并使反向個體與當前個體一起參與競爭，得到的優秀個體進入下一代繁殖。因此反向個體的引入對算法收斂性方面有很大的貢獻，為反向學習機制的收斂性提供了理論上的依據，從而證實了反向學習是提高隨機搜索算法搜索能力的一種有效方法。

定義1反向解。

其中：xij∈[aj，bj]，i=1，2，…，|Popsize|，j=1，2，…，D，|Popsize|為種群規模，D為搜索空間的維度。

定義2中的k可以取不同的實數，當k=0 時=-xij，稱其為基于解對稱的一般反向學習；當k=0.5 時，稱其為基于區間對稱的一般反向學習；當k=1 時，稱其為一般反向學習或廣義的反向學習；而當k為［0，1］區間內的隨機數時，稱其為基于隨機的一般反向學習。

定義3動態的一般反向學習。

其中daj和dbj分別表示當前代中種群搜索空間中第j維上的最小值和最大值，即：

其中：Aj為種群中的個體在第j維上所有取值的集合；k∈[0，1]為一般化系數。

很多學者將反向學習與很多多目標進化算法結合，并設計成相應的混合算法，如與粒子群算法［17］、差分進化算法［18］以及和聲搜索算法［19］等相結合。通過對混合算法性能的測試，驗證了反向學習對原算法的性能有一定程度的提升，進而證明了反向學習在多目標優化算法中的適用性。

本文算法采用動態的一般反向學習策略產生反向種群，從當前種群和反向種群中選擇較好的個體組成新的種群進行算法迭代。引入反向學習策略主要是提高種群中個體的多樣性，擴大種群搜索范圍，使得進化算法能較快地收斂到Pareto最優前沿上。

2.2 自適應調用機制

將反向學習引入RM-MEDA 的出發點是想在RM-MEDA陷入局部收斂時，利用反向學習擺脫早熟的困境。反向學習與其他算法設計的混合算法中，引入反向學習的反向學習概率需要通過大量實驗數據來確定其值，這樣得到的概率值不能很好地處理任意問題，從而在處理不同測試問題時不能充分改善算法的全局收斂性，甚至影響算法本身的性能。

本文采用一種自適應機制［20］來調用反向學習，具體方法為：

Xp、Xc分別表示父代和子代個體。

rij是目標函數的離散相對變化率。當rij的模小于預定的閾值ε，即rij很小時，認為此時算法陷入局部收斂，則在RMMEDA中引入反向學習；否則執行RM-MEDA。

2.3 AOL-MEDA步驟

下面給出基于自適應反向學習的多目標分布估計算法的具體步驟：

輸入 聚類數目K，種群規模N，最大運行代數T；閾值ε。

輸出 算法得到的新種群Pop(t)和每個個體對應的目標函數值。

步驟1 初始化：在決策空間隨機生成初始化種群Pop(0)，計算種群Pop(0)中每個個體的目標函數值；t=0。

步驟2 停止條件：如果t＞T，則終止算法并輸出Pop(t)和它們對應目標函數值；否則執行步驟3。

步驟3 當rij＜ε時，轉至步驟4；否則執行步驟6。

步驟4 反向學習。對Pop(t)中的個體進行動態反向學習并生成反向種群P，評價P中每個解的目標函數值。

步驟5 選擇：采用NSGA-Ⅱ非支配排序的選擇操作，從P∪Pop(t)中選擇N個優秀解作為新的種群Pop(t)。

步驟6 RM-MEDA進化產生新種群Q。

1）建模：對Pop(t)中的解進行訓練，獲得分段的流形并建模。

2）采樣：在每個流形的模型中產生新解，新解組成種群Q，并計算Q中每個個體的目標函數值。

步驟7 選擇：采用非支配排序的選擇操作，從Q∪Pop(t)中選擇N個優秀個體作為下一代種群Pop(t+1)。

步驟8 令t=t+1，跳轉到步驟2。

3 實驗與結果分析

3.1 參數設置

在本文實驗中，算法種群規模N設為100，維度D為30，AOL-MEDA、RM-MEDA兩種算法簇數K都為5，簇的擴展系數均為0.25。摸石頭過河算法與分布估計混合算法（Hybrid Wading across Stream Algorithm-Estimation Distribution Algorithm，HWSA-EDA）［10］中鄰域半徑L=0.1，α=0.5，其中：α為1 時，混合算法是摸石頭過河算法；而α為0 時，混合算法是分布估計算法。IM-MOEA中的參考向量為15，模型數為3。每組實驗獨立運行10次。

AOL-MEDA中需要設置的一個重要參數是目標函數的離散變化率rij的閾值ε，它主要用來判斷算法在迭代過程中是否陷入局部最優，算法中在依據式（6）計算rij時，?f未包含差值的最大值和最小值，因此rij的取值范圍為（0，1），rij越小，表明父代和子代個體相對變化小。本文閾值ε的取值決定反向學習策略是否被引入到算法中，為了反向學習在算法中引入的合理性，ε的取值參考文獻［20］，即ε為1× 10-2。

3.2 多目標測試和評價指標

本文將4 種算法分別在兩目標ZDT 測試問題和三目標DTLZ測試問題中進行性能測試，其中兩目標優化測試函數為ZDT1～ZDT3、ZDT6；三目標優化測試函數為DTLZ2、DTLZ2.1［8］、DTLZ4 和DTLZ7，DTLZ2.1 比DTLZ2 中的約束條件復雜一些。DTLZ4可以測試算法維持一個良好的分布解集的能力；DTLZ7是不連續多模態問題，這一測試函數可以很好地體現算法處理局部最優的能力。

為了更精確地比較4 種算法的性能優劣，對算法做定量對比，本文選用了反世代距離（Inverted Generational Distance，IGD）［21］、收斂性指標γ［5］和超體積（HyperVolume，HV）［22］作為性能評估指標。

1）反世代距離（IGD）。

IGD 指標兼顧了近似最優解集的收斂性和多樣性，是一個綜合評價的性能指標。計算公式如下：

其中：P是優化算法求出的一組近似最優解集；P*為Pareto 真實前沿上均勻采樣得到的一組參考點；|P*|表示P*的基數，即解集P*中解的個數；d(v，P)表示v∈P*到P中所有解的最小歐氏距離。IGD 值越小，則最優解集P能很好地逼近Pareto前沿，并且更均勻地分布在Pareto最優前沿上。

2）收斂性指標γ。

收斂性指標γ是計算算法所獲得的所有最優解與Pareto真實前沿上的最優解之間的最近距離，這些距離的平均值就是收斂性指標γ。公式如下：

其中：|P|表示非支配解集PS中解的數量，d(Pi，P*)表示第i個非支配解與理論Pareto 前沿之間的最小歐氏距離。算法所求解和理論最優解之間的最小距離越小，γ就越小，即算法求得的解越逼近理論最優解，算法的收斂性越好。

3）超體積指標（HV）。

超體積HV 不需要Pareto 真實前沿，而是通過在目標空間設定一個參考點來求得。假設Zr=為目標空間中被所有的Pareto 最優解支配的一個參考點，則超體積表示目標空間中以Zr為邊界被最優解集P中的解所支配的區域的大小，HV指標的計算公式如下：

其中，VOL(·)表示勒貝格計量。HV用來同時評估所得近似最優解集的收斂性和多樣性，HV 越大說明最優前沿P的性能越好。

表1 給出了算法在各個測試函數測試時的迭代次數以及IGD、γ指標計算所需的Pareto真實前沿上的參考點數目。

表1 各個測試函數所用的參數Tab.1 Parameters used by test functions

3.3 實驗結果與分析

為了測試AOL-MEDA 的性能，選擇RM-MEDA、HWSAEDA 和IM-MOEA 作為對比算法。本文算法是基于RMMEDA 進行改進的，與它對比能夠體現改進后的算法在收斂性方面的提高。HWSA-EDA 是EDA 中搜索速度快、全局搜索能力好的一種算法。IM-MOEA 是一種根據個體解在目標空間中的分布信息采用高斯過程建立逆模型的算法，該算法充分利用了Pareto解集和Pareto前沿的規則屬性，使得算法能夠獲得高質量的解。

表2、圖1～4 為4 種算法在兩目標測試問題下的實驗數據及結果；表3、圖5～8為三目標測試問題下的實驗數據和結果。在表2、3中將最好的值加粗表示。

表2 4種算法在ZDT測試集上的IGD、γ和HV的均值及方差Tab.2 Means and variances of IGD，γ and HV for four algorithms on ZDT test set

圖1 不同算法在ZDT1上獲得的最終Pareto前沿Fig.1 Final Pareto fronts obtained by different algorithms on ZDT1

從表2 中的數據及圖1～4 可以看出，在兩目標測試問題中，AOL-MEDA 與RM-MEDA、HWSA-EDA 以及IM-MOEA 相比，在收斂性和多樣性方面都有很大的提升。表2 中數據表明，在相同進化代數下，不論是處理凸函數ZDT1 還是凹函數ZDT2，AOL-MEDA 的性能比對比算法更好；且從圖1 和圖2可以看到AOL-MEDA 獲得的Pareto 解更靠近真實Pareto 前沿，解的分布也較均勻。RM-MEDA 主要處理連續多目標優化問題，但表2 及圖3、4 表明，改進后的AOL-MEDA 相較于對比算法，在處理非連續問題ZDT3 以及非均勻的ZDT6 測試問題時，仍可以很快收斂到Pareto 前沿上，且得到的解集有良好的分布性。從表2 中IGD、HV 的均值可以看到AOL-MEDA 解集的多樣性和分布性優于對比算法，在ZDT1 和ZDT2 中表現更為明顯。

從表3 中的數據及圖5～8 可以看出，在三目標測試問題中，AOL-MEDA 與RM-MEDA、HWSA-EDA 以及IM-MOEA 相比，收斂性均有一定程度的提升。從表3 可以看出：在DTLZ2測試函數上進行算法性能測試時，AOL-MEDA比IM-MOEA稍微差一些，但比RM-MEDA 較好。在較為復雜的DTLZ2.1 中，AOL-MEDA 的結果明顯比對比算法好。從表3 還可以看出，本文算法在解決DTLZ4 測試問題時比對比算法更好，表明了該算法保持了解的良好的分布性，在圖7中也得以證實。表3中DTLZ7數據及圖8結果表明，改進算法在處理多模問題時，相較于對比算法，可以很好地收斂到Pareto 前沿上，且解集分布更均勻。

圖2 不同算法在ZDT2上獲得的最終Pareto前沿Fig.2 Final Pareto fronts obtained by different algorithms on ZDT2

圖3 不同算法在ZDT3上獲得的最終Pareto前沿Fig.3 Final Pareto fronts obtained by different algorithms on ZDT3

圖4 不同算法在ZDT6上獲得的最終Pareto前沿Fig.4 Final Pareto fronts obtained by different algorithms on ZDT6

表3 4種算法在DTLZ測試集上的IGD、γ和HV的均值及方差Tab.3 Means and variances of IGD，γ and HV for four algorithms on DTLZ test set

圖5 不同算法在DTLZ2上獲得的最終Pareto前沿Fig.5 Final Pareto fronts obtained by different algorithms on DTLZ2

在處理兩目標優化問題時，AOL-MEDA 相較RM-MEDA、HWSA-EDA 和IM-MOEA 在算法收斂性和解集的多樣性上有很大的提升，而處理三目標優化問題DTLZ2 時，AOL-MEDA、RM-MEDA 與IM-MOEA 的IGD、γ和HV 的均值和方差相差不多，其中原因可能是EDA 是基于模型的算法，三目標優化問題測試中的種群規模與兩目標優化問題的種群規模都為100，導致三種算法在算法迭代過程中不能建立準確的模型，從而使得算法不能更快地收斂。其中AOL-MEDA 中的反向學習因為種群個數的限制，使得生成的反向個體與當前個體競爭壓力增大。IM-MOEA 作為挖掘Pareto 解集和Pareto 前沿的規則屬性的多目標分布估計算法，在種群個數少以及算法迭代次數少的情況下，使得建立的高斯逆模型不準確，因此該算法在DTLZ4 以及DTLZ7 測試問題中很難像AOL-MEDA 和RM-MEDA 一樣更快收斂到Pareto 前沿上。HWSA-EDA 雖然有較好的全局搜索能力，但因為該算法對解的特征沒有進行分析，使得在本文設置較少迭代次數時，算法性能較差，且收斂速度慢。

圖6 不同算法在DTLZ2.1上獲得的最終Pareto前沿Fig.6 Final Pareto fronts obtained by different algorithms on DTLZ2.1

圖7 不同算法在DTLZ4上獲得的最終Pareto前沿Fig.7 Final Pareto fronts obtained by different algorithms on DTLZ4

圖8 不同算法在DTLZ7上獲得的最終Pareto前沿Fig.8 Final Pareto fronts obtained by different algorithms on DTLZ7

本文將4 種算法分別在兩目標、三目標測試問題中進行測試，通過IGD、γ以及HV 指標的均值和方差進行了定量對比，其均值表明本文算法在處理問題時優于對比算法，表中各個指標的方差表明了AOL-MEDA 相較于對比算法，在解決測試問題時有較好的魯棒性。

4 結語

本文將反向學習策略自適應地引入到RM-MEDA 中，在盡量減少算法運行時間的同時，提高了該算法的收斂性以及算法迭代中種群的多樣性。理論分析及實驗結果表明，AOLMEDA 通過自適應引入反向學習，提高了原算法RM-MEDA的收斂性和多樣性，也有效避免了算法陷入局部最優。在處理兩目標優化問題時，AOL-MEDA 相較對比算法在收斂性和多樣性上有很大提高。但在處理三目標優化問題時效果不是很明顯：一方面是因為算法在三目標優化測試問題中種群個數少；另一方面是因為AOL-MEDA 對陷入局部最優的判斷可能不準確。因此本文所提算法在判斷算法是否陷入局部最優方面還需要進一步研究。