基于正則性輔助的多目標(biāo)優(yōu)化進(jìn)化算法研究*

龍 娟

(廣西財(cái)經(jīng)學(xué)院信息與統(tǒng)計(jì)學(xué)院，廣西南寧 530003)

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

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

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

1 MOEA概述

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

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

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

2 RAMEA算法

2.1 RAMEA算法框架

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

(1)

算法1RAMEA 框架

輸入:

N:種群的大小;

T:最大進(jìn)化子代;

K:聚類的數(shù)量;

輸出:

總量Pop;

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

②令t=1,…,T

③將總量Pop分成K個(gè)簇:

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

// 高斯建模和采樣

④計(jì)算均值矢量μ 和協(xié)方差矩陣Σ;

⑤每個(gè)j=1,…,K

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

(μ,Σ)

⑦令Gau=Gau∪yj;

⑧結(jié)束

⑨更新Arch:Arch=Arch∪Gau;

// 匹配鄰域

⑩每個(gè)Ck∈C,k=1,…,K

2.2 RAMEA的子代解生成

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

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

輸入:

平均方差μ;

協(xié)方差矩陣Σ；

輸出:

一種新的試驗(yàn)解y；

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

②生成試驗(yàn)解：y=μ+Λs；

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

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

④返回 采樣的試驗(yàn)解y

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

算法3差分進(jìn)化函數(shù)y=DE(xi,x1,x2)

輸入:

xi和它的兩個(gè)父代解x1和x2;

輸出:

新的解y;

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

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

其中r=rand()是一個(gè)隨機(jī)值;

④返回 新解y

2.3 進(jìn)化算法

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

算法4Pop=Select(Pop,Arch)

輸入:

新的試驗(yàn)解集Arch;

Pop總量;

輸出:

更新Pop總量;

①對于每一個(gè)yi∈Arch,i=1,…,n執(zhí)行

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

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

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

⑤結(jié)束

⑥返回 更新Pop存檔

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

3 實(shí)驗(yàn)分析

為驗(yàn)證RAMEA的正確性和有效性，實(shí)驗(yàn)用44個(gè)測試實(shí)例比較分析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算法中的模擬二進(jìn)制交叉算子被DE算子替換。實(shí)驗(yàn)使用F1-F10[3]、IMF1-IMF10[9]、ZDT1-ZDT6[15]、F1-F9[16]和WFG1-WFG9[17]測試數(shù)據(jù)。實(shí)驗(yàn)參數(shù)設(shè)置對算法的性能有很大的影響，因此實(shí)驗(yàn)為每個(gè)被比較的算法選擇最佳參數(shù)，其中NSGA-Ⅱ和SMS-EMOA算法只需要DE和PM的控制參數(shù)。

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

(2)

超體積度量定義為

HV(P,z)=

(3)

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

表1總結(jié)44個(gè)實(shí)例中8種算法在IGD和HV方面的指標(biāo)性能，包括通過Wilcoxon秩、檢驗(yàn)獲得的平均秩和統(tǒng)計(jì)結(jié)果。在測試實(shí)例上的實(shí)驗(yàn)結(jié)果表明，RAMEA的平均秩顯著低于其他對比算法，因此RAMEA具有良好的收斂性和多樣性。

表1 8 個(gè) MOEAs 在 44 個(gè)測試實(shí)例上關(guān)于IGD和HV指標(biāo)的性能Table 1 Performance of 8 MOEAs on 44 test instances in terms of IGD and HV metrics

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

表2 RAMEA獲得的IGD度量值的統(tǒng)計(jì)結(jié)果[平均值(標(biāo)準(zhǔn)差)]Table 2 Statistical results(mean(std.dev.)) of the IGD metric values obtained by RAMEA

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

表3 RAMEA*、RAMEA+和RAMEA在WFG測試實(shí)例上得到的IGD統(tǒng)計(jì)結(jié)果Table 3 Statistical results of IGD obtained by RAMEA*,RAMEA+ and RAMEA on WFG test instance

4 結(jié)論

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