基于正則性輔助的多目標優化進化算法研究*

龍 娟

(廣西財經學院信息與統計學院，廣西南寧 530003)

多目標優化是在多個優化目標之間選取最優的折中解，即帕累托最優解集(Pareto Optimal Solutions Set，POSS)，POSS在目標空間中的映射是帕累托前沿(Pareto Front，PF)。多目標優化方法大致可分為兩種：一種是基于聚合技術的傳統優化方法，如加權約束法，但該方法需要明確問題的有關信息，權重和約束參數調節困難[1]；另一種是多目標優化進化算法(Multi-objective Optimization Evolutionary Algorithms，MOEA)，其對沖突目標進行折中，在一次運行中獲得一個近似解集，同時在優化進化過程中，將維持種群解視為常數以逼近POSS (或PF)[2]，因此非常適合于解決多目標優化問題(Multi-objective Optimization Problems，MOP)。

現有的多目標優化進化算法是先初始化種群，然后循環執行子代重組和環境選擇，直到滿足終止條件[2]。Zhang等[3]和Zhang等[4]表明環境選擇算子和子代重組算子是多目標優化進化算法中的兩個關鍵因素。現有的環境選擇研究大多集中在環境選擇算子的設計和分析上[5]。一般來說，根據環境選擇方法可以將算法分為3類：基于帕累托顯性的MOEA是根據帕累托優勢關系對種群進行排序，然后估計個體密度，從而選擇優勢水平和密度較好的解提供給后代[6]；基于指標的MOEA是給出每個解的適應度值，并通過優化總體指標間接求解一個多目標優化問題[7]；基于分解的MOEA是將一個MOP分解為一系列子問題，然后在基于分解的多目標優化進化算法(Multi-Objective Evolutionary Algorithm Based on Decomposition，MOEA/D)中協同優化這些子問題。MOEA/D作為一種通用的多目標優化進化算法，在分解方法[8]、權重調整、后代繁殖等多方面得以改進。上述MOEA都直接使用為單目標優化設計的子代重組算子，例如模擬二叉交叉(SBX)、粒子群優化(PSO)、微分進化(DE)和分布估計算法(EDA)。這些單目標優化的子代重組算子，在一定程度上忽略了MOEA的性質，導致重組算子在求解多目標優化時的性能較差。與單目標優化不同，MOP需要多個POSS。決策空間中MOP的POSS是分段連續的(m-1)維流形(m是目標數)，也可被看作是正則性[3]。正則性對種群解進行劃分和建模，然后用(m-1)-D正則性模型(D是維數)來顯式逼近POSS。在此基礎上，基于概率模型的、具有流形性質的抽樣復制也有較多研究[9]。另外，近期的研究主要集中在基于流形性質的交配約束條件[10]，利用聚類方法學習種群結構信息，定義解之間的鄰域關系，并通過基于鄰域的交配重組進行局部利用。上述兩種基于規則特性的子代重組算子處理MOP各有優缺點[11]，具體來說，基于概率模型的采樣和基于鄰域的交配重組代表兩種不同的子代生成策略。基于概率模型的采樣通過概率模型提取種群的全局分布信息，并從構建的模型中抽取新的子代解；而受限于交配限制策略的遺傳算子則利用個體的局部信息生成子代解。Sun等[12]指出子代的生成可以結合局部信息和全局信息。在此基礎上，Li等[13]提出一種自適應策略，以平衡不同子代重組算子之間的關系。因此，在子代中將局部信息和全局信息結合起來是一種更有效的方法。

為在子代重組中利用更多的信息，通過結合基于概率模型的采樣和基于鄰域的交配重組，生成子代解和MOEA的流形結構信息，本研究提出一種基于正則性輔助的多目標優化進化算法(Regularity Assisted Multi-objective Optimization Evolutionary Algorithm，RAMEA)。該算法擬使用k-均值聚類方法學習種群結構信息，并用聚類的平均向量建立高斯模型，通過高斯采樣和基于鄰域的交配重組生成新的子代解;取樣的子代解作為交配父代嵌入每個集群中，以生成其他子代解，實現聯合全局和局部信息的多目標優化算法，豐富多目標優化算法中輸入信息量，提高多目標優化算法的性能。

1 MOEA概述

根據正則性，可認為連續MOP的最優解不是一個隨機分布，而是一個規則的拓撲結構。因此，MOEA既可以通過流形結構的近似實現POSS，又可使用聚類算法提取流形結構，并使用結構化信息指導個體的復制，從而提高算法的搜索效率。POSS正則性在MOEA中的應用主要從以下兩個方面進行：一是用概率模型來逼近從種群中學習到的MOP的POSS，并從中迭代抽取子解，再利用已建立的(m-1)-D正則性模型來近似多目標分布估計算法[3]中POSS的流形結構；二是進一步提出基于分解和概率建模的MOEA，通過鄰域解圍繞子問題建立多元高斯模型[11]。簡而言之，POSS的流形結構可以用概率模型來近似。

Zhang等[4]提出一種自組織多目標進化算法(Self-organizing Multi-objective Evolutionary Algorithm，SMEA)，利用種群的流形結構特性設計交配限制機制，即使用聚類學習方法提取種群結構信息進行重組。自組織映射用于定義解之間的鄰域關系，則可通過與相鄰解匹配來生成新的子代解。此外，k-均值和譜聚類方法用于執行交配限制。自適應多目標進化算法(Adaptive Multi-objective Evolutionary Algorithm,AMEA)可以利用學習到的種群結構信息進行基于自適應模型的采樣和交配限制的混合設計[12]。然而，基于正則性的MOEA也面臨諸多挑戰。例如，作為分布算法的多目標估計，在基于正則性屬性的建模方法中，種群全局分布信息用于建模和采樣，因此缺乏單個局部信息，無法保證對個體信息的有效利用[14]。而且，在這些建模方法中，由于概率模型不足所導致的參數敏感性、高計算成本和低效率也受到質疑[12]。就交配限制策略而言，全局探索和局部開發之間的平衡始終是一項具有挑戰性的任務，這是由交配限制概率定義所決定的[4]。上述研究雖然設計了一些自適應匹配策略來調整交配限制，但算法的復雜度和計算開銷相應增加，其有效性有待進一步驗證。

綜上所述，減少參數的影響、平衡篩選和交配重組是影響算法性能的關鍵因素。另外，在基于模型的方法中，種群的全局分布信息可被提取出來用于建模和采樣，而個體的局部信息可被用于鄰域交配重組。因此，本研究提出一種結合全局信息和局部信息，并基于正則性生成MOEA的高質量解的算法，即RAMEA算法，以期實現多目標優化。

2 RAMEA算法

2.1 RAMEA算法框架

本研究提出的RAMEA算法的主要特點是將子代生成的全局信息、局部信息與POSS正則性相結合。在子代生成中，RAMEA維護一個群體Pop和一個外部種群存檔Arch，其中Arch用于保存生成的新解以供環境選擇。采用k-均值聚類方法提取種群結構信息，并用每個聚類的均值向量集建立多元高斯概率模型。然后進一步從高斯概率模型中抽取K個采樣的子代解嵌入每個聚類中，以改進基于鄰域的交配重組。RAMEA算法中，N表示種群的大小，T表示最大進化子代，K表示聚類的數量。算法初始化時，使用種群N的隨機解定義Pop的初始值，通過k-均值聚類方法將種群劃分為K個聚類，并使用外部種群存檔Arch輔助RAMEA進化。計算平均向量μ和協方差矩陣Σ，以建立多元高斯概率模型：

(1)

算法1RAMEA 框架

輸入:

N:種群的大小;

T:最大進化子代;

K:聚類的數量;

輸出:

總量Pop;

①隨機初始化總量:Pop={x1,…,xN};

②令t=1,…,T

③將總量Pop分成K個簇:

C={C1,…,CK},and an archiveArch=?;

// 高斯建模和采樣

④計算均值矢量μ 和協方差矩陣Σ;

⑤每個j=1,…,K

⑥用高斯采樣生成試探解:yj=GaussianSample

(μ,Σ)

⑦令Gau=Gau∪yj;

⑧結束

⑨更新Arch:Arch=Arch∪Gau;

// 匹配鄰域

⑩每個Ck∈C,k=1,…,K

2.2 RAMEA的子代解生成

RAMEA使用高斯采樣和基于鄰域的交配重組來生成新的子代解，其中采樣解不僅作為子代解，還可以作為交配父代添加到每個集群中。RAMEA的高斯采樣算法流程如算法2所示。y=GaussianSample(μ,Σ)是高斯采樣函數，其通過Cholesky分解方法將協方差矩陣Σ分解為下三角矩陣Λ，然后從標準高斯分布n(0,1)中采樣向量sj(j=1,…,n)，最后生成子代解。

算法2高斯采樣函數y=GaussianSample(μ,Σ)

輸入:

平均方差μ;

協方差矩陣Σ；

輸出:

一種新的試驗解y；

①執行Cholesky分解：Σ=ΛΛT;從N(0,I)中采樣一個向量s=(s1,…,sn);

②生成試驗解：y=μ+Λs；

③通過(i=1,…,n)修復解y:

其中ai和bi是變量xi的上下邊界；

④返回 采樣的試驗解y

由于DE算子在單目標優化中的性能往往優于其他遺傳算子，RAMEA使用基于鄰域的交配重組生成新的子代解，如算法3所示。差分進化函數y=DE(xi,x1,x2)通過使用當前解xi及其交配父代x1、x2生成子代解y。首先使用DE算子生成一個子代解，然后使用多項式變異算子對子代解進行變異。在該算法中，F是DE算子的控制參數，pm為交叉概率，η為交叉分布指數。對于處理復雜的POSS，將另一個DE的參數CR在RAMEA中設置為1，這樣可以保證DE運算符在對任何正交坐標旋轉保持不變[7]。

算法3差分進化函數y=DE(xi,x1,x2)

輸入:

xi和它的兩個父代解x1和x2;

輸出:

新的解y;

①通過該式產生新的解:y′=xi+F×(x1-x2)

其中ai和bi是變量xi的最低和最高的邊界值;

其中r=rand()是一個隨機值;

④返回 新解y

2.3 進化算法

RAMEA使用基于超體積度量(Hypervolume，HV)的種群選擇方法來更新種群。在算法4中，種群在Pop=Select(Pop,Arch)中更新。FNS()表示快速非支配排序，用于將Pop∪y劃分為L個不同的非支配層，其中B1是最好層，BL是最差層。然后，在最差層BL中找到超體積值最差的個體進行移除。在Zhou等[11]中有超體積計算Δφ的詳細描述。

算法4Pop=Select(Pop,Arch)

輸入:

新的試驗解集Arch;

Pop總量;

輸出:

更新Pop總量;

①對于每一個yi∈Arch,i=1,…,n執行

②{B1,…,BL}=FNS(Pop∪{yi})

③x*=argminx∈{Pop∪{yi}}Δφ(x,BL)

④令Pop=Pop∪{yi}/{x*}

⑤結束

⑥返回 更新Pop存檔

在每一代中都需考慮總體時間復雜度。就子代而言，RAMEA的兩種操作包括k-均值聚類過程和復制算子。k-均值聚類過程需要O(TKNn)，其中T是迭代次數，K是聚類數，N表示種群大小，n為樣本個數。復制算子的時間復雜度為O(Nn)。此外，RAMEA中的基于超體積度量的選擇方法，其快速非支配排序的運行時間為O(mN2)，HV計算中的運行時間為O(Nm)。綜上所述，每一代RAMEA的時間復雜度為O(TNKn+Nn+mN2+Nm)。

3 實驗分析

為驗證RAMEA的正確性和有效性，實驗用44個測試實例比較分析RAMEA與AMEA (Assisted Multi-Objective Optimization Evolutionary Algorithm)、RM-MEDA (Regularity Model-based Multi-Objective Estimation of Distribution Algorithm)、IM-MOEA (Improved Multi-Objective Evolutionary Algorithm)、SMEA、MOEA/D-DE、NSGA-Ⅱ (Nondominated Sorting Genetic Algorithm-Ⅱ)、SMS-EMOA (S-metric Selection-Estimation Multi Objective Algorithm ) 7種算法，其中NSGA-Ⅱ和SMS-EMOA算法中的模擬二進制交叉算子被DE算子替換。實驗使用F1-F10[3]、IMF1-IMF10[9]、ZDT1-ZDT6[15]、F1-F9[16]和WFG1-WFG9[17]測試數據。實驗參數設置對算法的性能有很大的影響，因此實驗為每個被比較的算法選擇最佳參數，其中NSGA-Ⅱ和SMS-EMOA算法只需要DE和PM的控制參數。

為證明RAMEA的性能，并衡量MOEA解的收斂性和多樣性，實驗采用反世代距離(Inverted Generational Distance，IGD)[18]和超體積度量兩種常用的質量指標。假設P*表示沿整個PF均勻分布的一系列已知最佳點，P表示由MOEA獲得的近似前沿(Approximation Front，AF)。IGD指示器的定義如下：

(2)

超體積度量定義為

HV(P,z)=

(3)

式中，VOL()是勒貝格測度，z=(z1,…,zm)T是所有帕累托最優解的參考點，設置z=1.1×max(f1,…，fm)。通過計算近似前沿和參考點之間的空間體積，HV可以判斷近似前沿的優劣。HV值越大，近似前沿越好。

表1總結44個實例中8種算法在IGD和HV方面的指標性能，包括通過Wilcoxon秩、檢驗獲得的平均秩和統計結果。在測試實例上的實驗結果表明，RAMEA的平均秩顯著低于其他對比算法，因此RAMEA具有良好的收斂性和多樣性。

表1 8 個 MOEAs 在 44 個測試實例上關于IGD和HV指標的性能Table 1 Performance of 8 MOEAs on 44 test instances in terms of IGD and HV metrics

在RAMEA中，聚類數K是一個重要參數，決定了高斯模型和采樣子代解的序列解數。為研究該參數的靈敏度，使用GLT測試實例分別在K=3，5，8，10，15的情況下測試RAMEA，每個實例執行20次。從表2可以看出，不同的K值對ZDT1-ZDT5實例的IGD值的平均值和標準差沒有明顯影響。對于ZDT6，平均值為相鄰值，且當K=8時標準差最低。簡而言之，RAMEA能夠為ZDT1-ZDT6產生相對較小的IGD值，但不是非常顯著，這表明RAMEA對聚類數K不敏感。

表2 RAMEA獲得的IGD度量值的統計結果[平均值(標準差)]Table 2 Statistical results(mean(std.dev.)) of the IGD metric values obtained by RAMEA

為研究高斯采樣對RAMEA性能的影響，研究比較了RAMEA的兩個其他變體：RAMEA*(RAMEA中無高斯采樣)和RAMEA+(取樣解僅作為子代)。實驗在WFG測試實例(2個目標，11個變量)中進行，最大生成數設置為300。如表3所示，在9個文本實例中，RAMEA在其中6個實例上的表現優于另外兩個變體。平均秩越小，說明算法效果越好。就平均排名而言，RAMEA是最好的，而變體RAMEA*排名最后。RAMEA性能優異的兩個原因在于高斯采樣與鄰域交配相結合，以及把取樣子代解作為交配父代，而不僅僅是子代。

表3 RAMEA*、RAMEA+和RAMEA在WFG測試實例上得到的IGD統計結果Table 3 Statistical results of IGD obtained by RAMEA*,RAMEA+ and RAMEA on WFG test instance

4 結論

本研究提出的RAMEA綜合了高斯概率模型采樣和交配重組兩種策略的優勢，且利用種群全局分布信息和個體局部信息，通過k-均值聚類方法將每一代種群劃分為K個不同的聚類，用K個聚類的均值向量建立高斯模型，通過高斯采樣和基于鄰域交配重組生成子代解。實驗結果表明，RAMEA算法的收斂性和多樣性優于文中對比的算法，未來可以將本研究方法與不同的MOP及應用結合，用于動態多目標優化、特征選擇等研究領域。