融合指標(biāo)分組的高維混合多目標(biāo)進化優(yōu)化

李 玲，郭廣頌

鄭州航空工業(yè)管理學(xué)院 智能工程學(xué)院，鄭州 450046

在實際優(yōu)化問題中，存在很多同時包含顯式指標(biāo)（定量指標(biāo)）和隱式指標(biāo)（定性指標(biāo)）的優(yōu)化類型，如光柵優(yōu)化[1]、鋼梁設(shè)計[2]、柴油機標(biāo)定[3]、機場故障處理[4]等，這類問題稱為混合指標(biāo)優(yōu)化問題。當(dāng)混合指標(biāo)優(yōu)化問題包含4個及以上目標(biāo)時，該問題稱為高維混合多目標(biāo)優(yōu)化問題。盡管近年來提出并得到迅速發(fā)展的NSGA-II、SPEA2、MOEA等多目標(biāo)進化優(yōu)化方法可以有效解決傳統(tǒng)的多目標(biāo)優(yōu)化問題，但是對于高維混合多目標(biāo)優(yōu)化問題，上述方法難以得到問題的Pareto最優(yōu)解。主要原因在于，種群中非被占優(yōu)解的比率會隨著目標(biāo)個數(shù)的增加而急劇增長，使得Pareto 占優(yōu)準(zhǔn)則無法區(qū)分個體性能，這就導(dǎo)致基于密度估計方法的選擇標(biāo)準(zhǔn)成為主導(dǎo)。然而，由于這些算法的密度估計方法無法在高維目標(biāo)空間中恰當(dāng)評估個體性能，結(jié)果保留了大量遠離Pareto前沿的占優(yōu)抵抗解。特別地，當(dāng)優(yōu)化指標(biāo)為混合指標(biāo)時，因隱式指標(biāo)無法用目標(biāo)函數(shù)表示，極大地增加了問題的求解難度。

目前主要有三種途徑求解高維混合多目標(biāo)優(yōu)化問題：（1）考慮優(yōu)化目標(biāo)的多樣性與復(fù)雜性，采用啟發(fā)式算法或智能算法對所有目標(biāo)同時進行Pareto 優(yōu)化[5-6]。啟發(fā)式算法和智能算法在這一研究中表現(xiàn)出巨大潛力，這也是目前求解高維混合多目標(biāo)優(yōu)化問題的主要研究途徑。但同時對所有目標(biāo)進行Pareto占優(yōu)求解，算法計算開銷巨大，收斂性和多樣性較差。（2）采用協(xié)同進化優(yōu)化，縮小子種群搜索空間，提高算法搜索效率[7-8]。協(xié)同進化優(yōu)化方法很適合大規(guī)模多目標(biāo)優(yōu)化問題求解，但對混合指標(biāo)優(yōu)化中兩類指標(biāo)的協(xié)調(diào)問題尚缺乏有效策略。（3）采用交互式進化優(yōu)化，將混合多目標(biāo)問題轉(zhuǎn)化為確定性多目標(biāo)或單目標(biāo)問題[9-11]。該類方法對一維或二維混合指標(biāo)問題效果較好，對于高維混合指標(biāo)問題優(yōu)化效果較差。

由于高維混合多目標(biāo)優(yōu)化問題的兩類指標(biāo)性質(zhì)不同，按傳統(tǒng)多目標(biāo)優(yōu)化思路對混合指標(biāo)加權(quán)轉(zhuǎn)化成確定性多目標(biāo)或單目標(biāo)問題求解，難以確定目標(biāo)權(quán)重。另外，對于隱式指標(biāo)的評價，無論由人直接完成，還是由代理模型完成，相比顯式指標(biāo)運算速度都要慢很多。兩類指標(biāo)進化速度的不一致，會嚴重影響進化優(yōu)化效率和Pareto最優(yōu)解質(zhì)量。文獻[12]將高維多目標(biāo)優(yōu)化問題分解為若干子優(yōu)化問題，采用多種群并行進化求解每一子優(yōu)化問題。結(jié)合高維混合多目標(biāo)特點，如果根據(jù)指標(biāo)性質(zhì)對混合指標(biāo)分組，采用并行進化優(yōu)化，每個子種群只優(yōu)化少量單純顯式指標(biāo)或隱式指標(biāo)，并基于聚合函數(shù)對子種群Pareto解進一步優(yōu)化，則可以利用多種群并行運算快速獲得整體最優(yōu)Pareto解。實現(xiàn)這一思想，需要足夠多滿足多樣性與覆蓋性的樣本，并對隱式指標(biāo)做出準(zhǔn)確的估計。

鑒于此，本文提出一種基于指標(biāo)分組的高維混合多目標(biāo)并行進化優(yōu)化方法。主要思想是：基于人評價的少樣本個體隱式指標(biāo)，采用深度卷積神經(jīng)網(wǎng)絡(luò)實現(xiàn)大規(guī)模種群隱式指標(biāo)預(yù)測；按指標(biāo)相關(guān)性，分別對顯式指標(biāo)和隱式指標(biāo)分組，形成若干子優(yōu)化問題；采用多種群并行進化算法求解各子優(yōu)化問題，并將各子種群的優(yōu)化解組成外部保存集；采用聚合函數(shù)對外部保存集的優(yōu)化解進一步優(yōu)化，獲得優(yōu)化問題的Pareto最優(yōu)解。

本文方法的創(chuàng)新之處是：（1）將兩類指標(biāo)單獨轉(zhuǎn)化成若干個目標(biāo)函數(shù)較少的多目標(biāo)優(yōu)化問題，采用子種群并行進化優(yōu)化求解，提高了問題求解速度；（2）并行進化過程中，在隱式指標(biāo)預(yù)測的同時，允許顯式指標(biāo)完成多次進化，提高了顯式指標(biāo)優(yōu)化進程，縮小了用戶對隱式指標(biāo)評價次數(shù)；（3）采用深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)預(yù)測隱式指標(biāo)，實現(xiàn)大規(guī)模種群評價，指標(biāo)評價更準(zhǔn)確，減輕了用戶疲勞；（4）采用外部保存集對聚合函數(shù)進一步優(yōu)化，保證了Pareto最優(yōu)解的逼近性與分布性。

1 相關(guān)工作

1.1 混合指標(biāo)進化優(yōu)化

混合指標(biāo)優(yōu)化問題是多目標(biāo)優(yōu)化問題的特殊類型，顯式指標(biāo)與隱式指標(biāo)并存是這類問題的顯著特征。相比單純數(shù)值多目標(biāo)優(yōu)化，該問題研究較少，且研究方法主要沿用傳統(tǒng)多目標(biāo)優(yōu)化策略?，F(xiàn)有研究成果中，一類集中于將混合指標(biāo)優(yōu)化問題轉(zhuǎn)化為確定型多目標(biāo)優(yōu)化問題。這類方法大多采用在搜索過程中融入用戶決策的交互式優(yōu)化方法，因為通過人機交互，用戶可以對優(yōu)化結(jié)果的性能指標(biāo)做出更合理的判斷[13]。Satoshi 等將定性與定量指標(biāo)加權(quán)轉(zhuǎn)化為一個適應(yīng)值函數(shù)，采用交互式進化計算進行圖像處理濾波器設(shè)計[14]；Garcia-Hernandez等將用戶評價的隱式指標(biāo)與顯式指標(biāo)合成為一個適應(yīng)值，采用交互式進化優(yōu)化方法求解不等面積設(shè)施布局問題（unequal area facility layout problem，UA-FLP）[15]。另一類研究集中于改進進化策略提高算法性能，或是與第一類情況的混合。Liu等基于啟發(fā)式變異操作和后續(xù)配置一個考慮梯度方法的局部搜索策略，提高算法效率[16]；Liu提出了一種多目標(biāo)蟻群優(yōu)化算法解決UA-FLP中物料搬運成本和距離要求，該方法通過啟發(fā)式技術(shù)將約束問題轉(zhuǎn)化為無約束問題，然后應(yīng)用局部搜索、Pareto優(yōu)化、設(shè)施變形和小生境等策略達到有效的設(shè)施設(shè)計[17]；García-Hernández等提出了一種支持用戶定性標(biāo)準(zhǔn)的多目標(biāo)交互式遺傳算法[18]。由于含有隱式指標(biāo)，對于相同的混合指標(biāo)優(yōu)化問題，采用不同的轉(zhuǎn)化方法，得到的確定優(yōu)化問題是不同的，相應(yīng)地，這些確定優(yōu)化問題的解也可能不同。這意味著，不同的轉(zhuǎn)化方法會得到混合指標(biāo)優(yōu)化問題的不同解，那么決策者如何從這些解中進一步選擇是一個很困難的問題。特別地，上述方法的研究對象均為1個隱式指標(biāo)與1個或2個顯式指標(biāo)的混合情況，沒有涉及高維混合目標(biāo)的優(yōu)化問題。

1.2 協(xié)同進化優(yōu)化

協(xié)同進化優(yōu)化算法（cooperative co-evolutionary algorithm，CCEA）是一種將多變量優(yōu)化問題分解為若干簡單少變量的子優(yōu)化問題，將種群劃分為若干個與子優(yōu)化問題對應(yīng)的子種群的優(yōu)化方法。該方法通過構(gòu)建每個子種群的搜索結(jié)果構(gòu)成問題的完整解，進而得到問題的最優(yōu)解。相對于單目標(biāo)優(yōu)化問題，利用協(xié)同進化優(yōu)化算法求解多目標(biāo)優(yōu)化問題，目前的研究成果較少。Ma等提出一種基于決策變量分析的多目標(biāo)進化算法，并使用控制變量分析來識別目標(biāo)函數(shù)之間的沖突[19]；Li等建立了一個協(xié)同搜索框架用于對3個目標(biāo)特征的選擇，以此克服建模選擇優(yōu)化特征子集過程中保持分類精度和減少特征數(shù)量的矛盾[20]；另外，Tirumala通過2 個子種群協(xié)同進化優(yōu)化深度學(xué)習(xí)網(wǎng)絡(luò)，為深度學(xué)習(xí)與進化優(yōu)化結(jié)合提供了新思路[21]。最近，協(xié)同進化優(yōu)化算法還被用于動態(tài)多目標(biāo)優(yōu)化問題[22-23]。上述方法為求解多目標(biāo)優(yōu)化問題提供了可行途徑。然而，由于缺少預(yù)測隱式指標(biāo)方法及與顯式指標(biāo)協(xié)調(diào)的目標(biāo)函數(shù)構(gòu)建策略，現(xiàn)有協(xié)同進化優(yōu)化算法無法直接用于求解高維混合多目標(biāo)優(yōu)化問題。

2 提出的方法

2.1 優(yōu)化問題

考慮如下一類高維混合多目標(biāo)優(yōu)化問題：

式中，x為n維決策變量；S為x的可行域；fi(x,ci)(i=1,2,…,p)為含參數(shù)ci的顯式性能指標(biāo)對應(yīng)的目標(biāo)函數(shù)；為隱式性能指標(biāo)，是用戶對進化個體滿足程度的定性評價值。

2.2 總體框架

本文提出一種高維混合多目標(biāo)并行進化優(yōu)化方法求解問題（1），總體框架如圖1所示。首先，將高維混合多目標(biāo)優(yōu)化問題按顯式指標(biāo)與隱式指標(biāo)兩類目標(biāo)分組，原優(yōu)化問題被分成規(guī)模較小的K個顯式指標(biāo)和K′個隱式指標(biāo)子優(yōu)化問題；其次，按對子優(yōu)化問題的相關(guān)性，將種群分成K+K′個子種群；然后，每個子種群對應(yīng)優(yōu)化一個子問題，這一過程融入小樣本深度學(xué)習(xí)預(yù)測隱式性能指標(biāo)，通過子種群并行進化提高種群多樣性；最后，將各子種群的Pareto最優(yōu)解集合并成外部保存集，通過優(yōu)化聚合函數(shù)實現(xiàn)聚合優(yōu)化，獲得逼近性最佳解集，再從中選擇出代表性個體推薦給用戶評價，完成一次迭代。

圖1 算法框架Fig.1 Algorithm framework

可以看出，目標(biāo)分組、子優(yōu)化問題進化求解、外部保存集的形成與更新是本文方法的關(guān)鍵技術(shù)。

2.3 目標(biāo)分組

問題（1）包含顯式指標(biāo)與隱式指標(biāo)兩類指標(biāo)，不僅指標(biāo)數(shù)量較多，而且指標(biāo)還可能是沖突的，直接作為優(yōu)化目標(biāo)很難獲得Pareto最優(yōu)解?；诖?，本節(jié)根據(jù)相關(guān)性對問題（1）進行目標(biāo)分組。具體方法是：每一進化代對種群所有個體，計算顯式指標(biāo)目標(biāo)函數(shù)fa(x,c) 與fb(x,c)之間的Spearma 相關(guān)系數(shù)ρa,b,a,b=1,2,…,p,如果ρa,b超過閾值，則fa(x,c)與fb(x,c)可以分為一組，記為。由于隱式指標(biāo)沒有目標(biāo)函數(shù)，則計算每一進化代種群所有個體隱式指標(biāo)值的Pearson 相關(guān)系數(shù)ra′,b′,a′,b′=p+1,p+2,…,p+q,如果ra′,b′超過閾值，則可以分為一組，記為。對于最后沒有匹配的剩余隱式指標(biāo)，則單獨歸為一組。根據(jù)上述分組方法，問題（1）描述的高維混合多目標(biāo)優(yōu)化問題可以分成如下K+K′組：

式中，fkh(x,c),k=1,2,…,K,h=1,2,…,mk，是組Gk包含的第h個顯式指標(biāo)目標(biāo)函數(shù)；,k′=p+1,p+2,…,p+K′,h′=1,2,…,mk′是組Gk+k′包含的第h′個隱式指標(biāo)目標(biāo)函數(shù)，且滿足K+K′≤p+q。

式（2）的分組結(jié)果體現(xiàn)出將問題（1）兩類指標(biāo)中最相關(guān)的目標(biāo)劃為一類，其中K由優(yōu)化問題（1）的顯式目標(biāo)函數(shù)性質(zhì)決定，K′則由隱式指標(biāo)結(jié)果和數(shù)量決定。按式（2）可將問題（1）的1 個優(yōu)化問題分成如下K+K′個子優(yōu)化問題：

與問題（1）相比，式（3）子優(yōu)化問題的優(yōu)化目標(biāo)個數(shù)明顯減少，因此問題復(fù)雜性降低，更容易求解Pareto解。

2.4 子優(yōu)化問題的并行進化求解

對于問題（3），本節(jié)采用子種群并行進化求解，通過多種群并行進化實現(xiàn)高效求解問題（1），具體分為如下三個階段。

（1）深度學(xué)習(xí)

受疲勞限制，人評價個體數(shù)量有限，基于此，本節(jié)采用深度神經(jīng)網(wǎng)絡(luò)的少樣本學(xué)習(xí)方法實現(xiàn)大規(guī)模種群個體的隱式指標(biāo)賦值。記第t代進化種群為x(t)，種群規(guī)模為N，供用戶評價的推薦個體為xc(t),c=1,2,…,Nc，則種群剩余個體記為xre(t),re=1,2,…,N-Nc。將上一代種群DL(t-1)={(xi(t-1),f(xi(t-1)))|i=1,2,…,N}作為初始樣本訓(xùn)練集，Dl(t)={(xc(t),f(xc(t)))|c=1,2,…,Nc}作為小樣本訓(xùn)練集，xre(t)的隱式指標(biāo)通過學(xué)習(xí)獲得。深度學(xué)習(xí)部分基于深度卷積神經(jīng)網(wǎng)絡(luò)構(gòu)建。深度學(xué)習(xí)的初始訓(xùn)練部分，將DL(t-1)的個體{xi(t-1)}以圖片形式作為輸入，直接采用深度神經(jīng)網(wǎng)絡(luò)卷積1 提取個體{xi(t-1)} 的屬性特征，再將屬性向量輸入兩層全連接層訓(xùn)練，得到個體特征。設(shè)個體屬性特征向量為d′，使用卷積核對d′學(xué)習(xí)，經(jīng)過池化層，得到個體特征向量：

對于xi(t-1)的評價值f(xi(t-1))，采用嵌入層處理，獲得個體隱式指標(biāo)向量。將和個體隱式指標(biāo)向量一并通過兩層全連接層訓(xùn)練，得到偏好特征。

采用小樣本訓(xùn)練集Dl(t)對上述分類器按平方梯度幅度損失（squared gradient magnitude loss，SGM）進行微調(diào)，實現(xiàn)小樣本學(xué)習(xí)[24]。Dl(t)的個體{xc(t)}以圖片形式作為輸入，采用卷積2提取個體屬性特征，按式（4）得到個體特征向量。對于推薦個體xc(t)的評價值f(xc(t))，也采用嵌入層處理，獲得個體隱式指標(biāo)向量。將和個體隱式指標(biāo)向量一并通過兩層全連接層訓(xùn)練，得到偏好特征。同理，測試集{xre(t)}采用卷積1和全連接層訓(xùn)練，得到種群剩余個體特征。將和輸入到全連接層，采用Adams算法作為優(yōu)化策略[25]，進行特征匹配。對輸出值進行Logistic Regression，得出剩余個體xre(t)的隱式指標(biāo)預(yù)測概率值：

（2）子種群劃分

為了提高優(yōu)化效率，采用子種群并行優(yōu)化策略。即要求子種群對應(yīng)求解問題（3）的子優(yōu)化問題，這需要各子種群內(nèi)個體的指標(biāo)分布應(yīng)與所優(yōu)化目標(biāo)一致?；诖耍捎脗€體指標(biāo)均衡度劃分子種群[26]。在交互式進化過程中，由于每一代的個體指標(biāo)在決策中所起作用相同，設(shè)指標(biāo)效用系數(shù)為1，且每一代均能收集到相關(guān)數(shù)據(jù)對相應(yīng)指標(biāo)進行評價，故直接將個體xi(t)的顯式指標(biāo)與隱式指標(biāo)分別歸一化，再做升序排列，記為V11(xi(t)),V12(xi(t)),…,V1p(xi(t));V1p+1(xi(t)),V1p+2(xi(t)),…,V1(p+q)(xi(t)),則個體xi(t),i=1,2,…,N的指標(biāo)均衡度為：

其中Gip(t),Giq(t)∈[0,1],Gip(t)、Giq(t)可以反映兩類性能指標(biāo)的動態(tài)差異性，Gip(t)、Giq(t)越大，表明個體的兩類指標(biāo)分布越均衡，反之，兩類指標(biāo)分布差異越大。

采用式（7），對種群個體分別計算式（2）的目標(biāo)分組指標(biāo)均衡度。在兩類指標(biāo)均衡度中，每次選擇一個指標(biāo)均衡度最高的個體，共選擇K+K′個個體。以這K+K′個個體為中心，按基因相似性對種群聚類，則種群可以分成K+K′個子種群。這些子種群的規(guī)模并不相同，但由于按目標(biāo)分組指標(biāo)均衡度劃分聚類，Pareto最優(yōu)解的選擇壓力更大，每一個子種群的個體分布更有利于求解子優(yōu)化問題。

（3）子種群優(yōu)化

從（2）中獲得K+K′個子種群，采用并行優(yōu)化方法，讓每一個子種群采用NSGA-II 對應(yīng)求解一個子優(yōu)化問題。因為每一個子優(yōu)化問題包含的目標(biāo)數(shù)量較少，所以對于每一個子種群采用Pareto 占優(yōu)關(guān)系比較個體性能。采用多種群并行優(yōu)化的優(yōu)勢在于，由于不同子種群優(yōu)化的目標(biāo)不同，各子種群的進化方向也不同，這有利于保持整個進化種群的多樣性。需要說明的是，由于大量隱式指標(biāo)需要深度學(xué)習(xí)獲得，這會造成子優(yōu)化問題的優(yōu)化速度比要慢很多。為了協(xié)調(diào)進化速度，子優(yōu)化問 題每完成一次進化，允許完成多次進化，這樣通過盡快優(yōu)化顯式指標(biāo)提高進化速度，減少用戶評價隱式指標(biāo)的次數(shù)。

2.5 外部保存集的形成

第2.4 節(jié)（3）中子種群的Pareto 最優(yōu)解代表了低維目標(biāo)空間里子優(yōu)化問題的最優(yōu)解，這些最優(yōu)解很可能是問題（1）的局部最優(yōu)解，而非全局最優(yōu)解。為了獲得高維目標(biāo)空間中，逼近性與分布性兼顧的Pareto 最優(yōu)解，需要對子種群的Pareto最優(yōu)解進一步選擇。記第t代的外部保存集為，其中,k=1,2,…,K+K′表示來自第k個子種群的Pareto 最優(yōu)解集，|At|≤N。因為外部保存集由組成，所以每代進化后，外部保存集中的個體將全部更新，其規(guī)模由決定。設(shè)聚合函數(shù)fK+K′(x)為：

式中，加撇的函數(shù)值是對原函數(shù)值歸一化的結(jié)果。ωgh是顯式指標(biāo)目標(biāo)函數(shù)fgh的權(quán)重，本文假設(shè)每個目標(biāo)函數(shù)重要性相同，則ωgh=1/(p-mK)；ωqkh′是隱式指標(biāo)的權(quán)重，同樣認為每個隱式指標(biāo)重要性相同，取ωqkh′=1/(p+q-mK′)。fK+K′(x)是所有子優(yōu)化問題解與參考點之間的加權(quán)切比雪夫距離，優(yōu)化解的fK+K′(x)值越小，到參考點距離越近，解的分布性越好，優(yōu)化解性能也越好。通過At對fK+K′(x)的優(yōu)化，可以平衡所有目標(biāo)函數(shù)，獲得具有好的逼近性能的最優(yōu)解，記為Ct+1。這一聚合優(yōu)化過程的可行解域At是子種群并行優(yōu)化階段的最優(yōu)解域，由于優(yōu)化目標(biāo)只有fK+K′(x)，隨著進化深入，At規(guī)模將不斷縮小，優(yōu)化問題復(fù)雜度也逐漸降低。聚合優(yōu)化過程中，仍采用深度學(xué)習(xí)獲得個體隱式指標(biāo)。最后，按個體相似性，從Ct+1選擇前Nc個個體推薦給用戶，作為下一代評價個體。

3 實驗

3.1 優(yōu)化問題

對于混合指標(biāo)優(yōu)化，目前最廣泛采用的測試問題是設(shè)施布局問題（facility layout problem，F(xiàn)LP）。本文采用屬于FLP 的室內(nèi)布局優(yōu)化問題驗證方法的性能[13]。室內(nèi)布局方案由客廳、臥室等7個居室單元組成，如圖2所示。布局總開間W和總進深H分別為W=12.5 m，H=10 m。該問題包含2個顯式指標(biāo)f1(x,c),f2(x,c)和2個隱式指標(biāo)。其中，f1(x,c)是室內(nèi)面積總造價（單位：元），f1(x,c)由決策變量x=[x1,x2,x3,x4,x5,x6,x7]和參數(shù)c=[c1,c2,c3,c4,c5,c6,c7]組成，決策變量x1～x7代表各居室單元的邊長，x1,x4,x5,x6∈(0,10)，x2,x3,x7∈(0,12.5)，各變量均采用離散值，取值個數(shù)分別為5、12、5、5、5、5、5。將所有變量采用實數(shù)編碼排列，構(gòu)成個體基因型。參數(shù)c1～c7代表各居室單元的單位面積造價，c1=800,c2=1 000,c3=600,c4=1 000,c5=600,c6=600,c7=500。

圖2 室內(nèi)布局Fig.2 Indoor layout

f2(x,c)是公攤面積與墻體面積和（單位：m2），其參數(shù)是公攤系數(shù)c8和墻體系數(shù)c9：

采用Google TensorFlow深度學(xué)習(xí)庫開發(fā)進化優(yōu)化系統(tǒng)。用戶對每代12個推薦個體，在1～100整數(shù)范圍內(nèi)評價該個體的2個隱式指標(biāo)，同時系統(tǒng)計算并顯示每個個體的2個顯式指標(biāo)。在人機交互過程中，系統(tǒng)在后臺運行相關(guān)算法，通過邊交互邊優(yōu)化形式，逐漸生成用戶滿意的室內(nèi)布局方案。

3.2 性能指標(biāo)

因為隱式指標(biāo)不能用目標(biāo)函數(shù)表達，所以問題（1）的真實Pareto前沿面是不確定的，這導(dǎo)致傳統(tǒng)多目標(biāo)優(yōu)化問題的世代距離（generation distance，GD）、反世代距離（inverted generation distance，IGD）等性能指標(biāo)均不適用問題（1）?；诖?，本文采用空間評價指標(biāo)（spacing，SP）[27]和最大傳播距離（maximum spread，MS）[28]評價解集的分布性和延展性，SP 值越小，解集的分布性越好，MS 值越大，解集的延展性越好；采用最好超體積（best hypervolume，bH）評估解集的逼近性[13]，bH 值越大，解集的逼近性越好；采用顯式指標(biāo)均值（E測度）和隱式指標(biāo)均值（I測度）評價解集質(zhì)量；采用迷失度[29]、滿意性和進化耗時Tt等評價不同方法的可用性，Tt由機器耗時Tp和用戶耗時Tu組成，Tp包含深度學(xué)習(xí)時間Tcn和并行程序運行時間Tnp。

3.3 對比方法及參數(shù)設(shè)置

采用本文方法和K均值聚類預(yù)測隱式指標(biāo)開發(fā)的混合指標(biāo)優(yōu)化算法（記為方法1）、采用本文方法但不采用目標(biāo)分組子種群并行進化開發(fā)的混合指標(biāo)優(yōu)化算法（記為方法2）和文獻[13]提出的混合指標(biāo)IGA（記為方法3）3種相關(guān)算法作為對比方法。這3種方法從不同角度求解混合指標(biāo)優(yōu)化問題，具有較強的代表性。

為驗證算法有效性，分別按上述3種方法開發(fā)相應(yīng)系統(tǒng)。方法參數(shù)設(shè)置相同，即種群規(guī)模N=500，用戶評價個體數(shù)Nc=12，單點交叉概率pc=0.95，單點變異概率pm=0.01，最大進化代數(shù)T=10。對于單點交叉操作，父代個體交換隨機選擇的一個交叉點之后的編碼串構(gòu)成新個體；對于單點變異操作，從隨機選擇的一個變異點的基因?qū)?yīng)的離散集合中，隨機選擇一個值代替該變異點的基因，產(chǎn)生新個體。選擇男女各5名在校大學(xué)生作為體驗用戶，分別記為用戶1～10。每位用戶獨立運行對比方法10 次，獨立運行本文方法20 次，其中10次運行結(jié)果用于分析不同參數(shù)或策略對本文方法性能影響，另外10 次運行結(jié)果用于與對比方法比較分析本文方法的性能。

3.4 結(jié)果分析

3.4.1 不同參數(shù)或策略對本文方法性能影響

（1）目標(biāo)分組方法

目標(biāo)分組數(shù)K+K′是本文求解問題（1）的關(guān)鍵參數(shù)，分組數(shù)決定了問題（1）的子優(yōu)化問題規(guī)模，直接影響優(yōu)化結(jié)果。設(shè)Spearman 相關(guān)閾值與Pearson 相關(guān)閾值分別為。依據(jù)第2.3節(jié)，通過可以確定出K+K′。為了比較不同目標(biāo)分組結(jié)果對優(yōu)化性能的影響，本節(jié)設(shè)定不同，并確定出相應(yīng)K+K′，通過性能指標(biāo)比較算法性能，實驗結(jié)果如表1所示。表中括號外的數(shù)據(jù)表示均值，括號內(nèi)的數(shù)據(jù)為標(biāo)準(zhǔn)差，E測度和I測度分別包括2個顯式指標(biāo)測度E-1、E-2和2 個隱式指標(biāo)測度I-1、I-2，粗體顯示的數(shù)據(jù)是所有K+K′分組方法得到的最優(yōu)結(jié)果。

表1 目標(biāo)分組對性能的影響Table 1 Effects of indexs decomposition on performance

（2）深度學(xué)習(xí)預(yù)測隱式性能指標(biāo)

根據(jù)第2.4 節(jié)（1），首先將上一代種群x(t-1)，共500 個個體作為初始樣本訓(xùn)練集DL(t-1)，訓(xùn)練深度學(xué)習(xí)網(wǎng)絡(luò)初始模型，然后將當(dāng)前代12 個用戶評價個體作為小樣本訓(xùn)練集Dl(t)，對初始模型進行修正，最后將當(dāng)前種群剩余488個個體作為測試集{xre(t)}，利用修正后的深度學(xué)習(xí)模型，預(yù)測當(dāng)前種群剩余個體xre(t)的隱式性能指標(biāo)。式（5）中，超參數(shù)偏好模型權(quán)重和個體模型權(quán)重對隱式性能指標(biāo)預(yù)測具有重要影響。偏好特征和種群剩余個體特征均為特征向量。

對于混合指標(biāo)優(yōu)化問題，隱式指標(biāo)預(yù)測最能體現(xiàn)算法的適應(yīng)能力，因此采用隱式指標(biāo)優(yōu)化損失驗證本文算法的泛化性：

圖3 深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)Loss曲線Fig.3 Loss curves of deep learning neural network

（3）子種群并行進化

子種群并行進化是本文求解問題（1）的關(guān)鍵。子種群根據(jù)指標(biāo)均衡度劃分，不同的子種群劃分決定了Pareto最優(yōu)解數(shù)目。Tt和Tnp/Tcn可以反映兩類指標(biāo)協(xié)同進化效果。Tt越小，表明算法速度越快。Tnp/Tcn中，Tnp與Tcn越接近，表明在隱式指標(biāo)深度學(xué)習(xí)預(yù)測的同時，顯式指標(biāo)進化次數(shù)越多，指標(biāo)協(xié)調(diào)性越好。圖4給出了指標(biāo)分組數(shù)目K/K′的變化情況，可以看到，隨著進化深入，K/K′逐漸趨于0.5，即K+K′=1+2。這說明，顯式指標(biāo)分組趨同，隱式指標(biāo)分為2 組，本文方法的指標(biāo)分組策略有效。表2 給出了10 位用戶子種群并行進化統(tǒng)計結(jié)果，其中分別是Gip(t)和Giq(t)的均值。表中10位用戶的均在0.8以上，且差異不顯著，說明子種群并行進化可以獲得良好的指標(biāo)均衡性。10 位用戶的分組結(jié)果中，K均為1，有4 位用戶的K′為2，說明顯式指標(biāo)相關(guān)性一致，隱式指標(biāo)相關(guān)性會因個性偏好產(chǎn)生差異。K′越小，最優(yōu)解越多，可能的原因是將2個個性偏好蘊含相關(guān)的隱式指標(biāo)獨立優(yōu)化，外部保存集中生成的非全局最優(yōu)解較多，但對聚合函數(shù)的Pareto最優(yōu)解較少。K′越大，Tt越大，原因在于對隱式指標(biāo)優(yōu)化的子種群數(shù)量增加，導(dǎo)致并行進化代數(shù)增加，耗時隨之增加。10位用戶的Tnp/Tcn差異不顯著，說明雖然用戶的目標(biāo)分組不同，但是采用子種群并行優(yōu)化的指標(biāo)協(xié)調(diào)性是一致的，即能夠通過盡快優(yōu)化顯式指標(biāo)，減少用戶評價隱式指標(biāo)次數(shù)。

圖4 指標(biāo)分組比值Fig.4 Indexs decomposition ratio

表2 子種群并行進化對性能的影響Table 2 Effects of subpopulation parallel evolution on performance

3.4.2 與其他方法的對比

（1）指標(biāo)均衡性

指標(biāo)均衡性是指標(biāo)分組的基礎(chǔ)，考察進化過程中指標(biāo)均衡性變化對于分析算法性能具有重要意義。本文方法與對比方法的種群指標(biāo)均衡度如圖5 所示。可以看到，本文方法的均高于對比方法，這表明采用本文方法，即便對于不同用戶，問題（1）的顯式指標(biāo)和隱式指標(biāo)均能獲得最佳優(yōu)化。原因在于，本文方法的指標(biāo)分組策略提高了優(yōu)化速度，各子種群可以獲得更好的種群多樣性。因為在隱式指標(biāo)預(yù)測的同時，允許顯式指標(biāo)完成多次進化，提高了顯式指標(biāo)優(yōu)化進程，所以本文方法的略高于。類似地，方法1的顯式指標(biāo)均衡度高于方法2和方法3。由圖5（b）可見，對比方法中，相同進化代內(nèi)變化比略大，這是因為隱式指標(biāo)估計與聚類策略和指標(biāo)分組策略密切相關(guān)，當(dāng)用戶評價個體選擇不同時，深度學(xué)習(xí)的結(jié)果也將不同，這將導(dǎo)致隱式指標(biāo)均衡性的改變。本文方法的隱式指標(biāo)估計策略比對比方法全面，因此變化最小?；诹己玫闹笜?biāo)均衡性，為獲得Pareto最優(yōu)解提供了依據(jù)。

圖5 指標(biāo)均衡度Fig.5 Index equilibrium degree

（2）Pareto最優(yōu)解集質(zhì)量

比較本文方法和對比方法獲得的Pareto最優(yōu)解，對4種方法最優(yōu)解指標(biāo)取均值，統(tǒng)計結(jié)果如表3所示，其中粗體顯示的數(shù)據(jù)為所有方法得到的最優(yōu)結(jié)果。從表中可以看到，本文方法最優(yōu)解數(shù)量最多，說明本文方法可以獲得最多性價比高的布局方案，推薦用戶評價個體更為豐富。4種方法中，本文方法SP最小，方法1比方法2和方法3的SP都小，說明本文方法的Pareto最優(yōu)解分布性最好，原因在于本文方法和方法1均采用子種群并行進化，可以獲得分布性更均勻的Pareto最優(yōu)解。本文方法和方法1 均采用目標(biāo)分組，因為本文方法多數(shù)用戶K+K′為1+1，所以MS接近1，且大于方法1。方法2和方法3 均采用所有性能指標(biāo)加權(quán)的單目標(biāo)優(yōu)化，所以MS均達到最大值。這表明本文方法采用深度學(xué)習(xí)預(yù)測隱式性能指標(biāo)比方法2 更準(zhǔn)確，Pareto 前沿延展性更好。本文方法bH 最大，說明本文方法獲得的Pareto 前沿更接近真實Pareto前沿，原因在于本文方法的探索能力強，更有利于找到最優(yōu)解。本文方法E 測度最小，說明本文方法獲得的Pareto最優(yōu)解造價最低，套內(nèi)面積最大。本文方法I測度最大，說明即便10個用戶存在偏好差異，本文方法獲得的個體評價值仍最高。本文方法E測度最小，反映出本文方法針對存在偏好差異情況下獲得的Pareto最優(yōu)解性價比更高。

表3 Pareto最優(yōu)解集質(zhì)量Table 3 Quality of Pareto optimal solution set

（3）交互性

算法的交互性從可用性和推薦性兩方面評價。征詢用戶對室內(nèi)布局方案的定性評價意見，用戶對室內(nèi)布局方案的偏好概括如下：（1）客廳面積應(yīng)最大；（2）衛(wèi)生間面積應(yīng)在5～8 m2之間；（3）3 個臥室中，臥室1（主臥）面積應(yīng)最大；（4）廚房布局應(yīng)對稱；（5）臥室2和臥室3面積應(yīng)接近；（6）過道不宜太狹窄。結(jié)合上述意見，構(gòu)造評價結(jié)果滿意性指標(biāo)S(x)，如式（12）所示，S(x)值越小，相應(yīng)個體就越滿足上述評價意見，用戶的滿意程度也越高。需要說明的是，由于隱式指標(biāo)評價強烈依據(jù)個性化偏好，式（12）不能充分地表達隱式評價指標(biāo)，只能必要地衡量優(yōu)化結(jié)果滿意性，因此式（12）不能作為隱式指標(biāo)函數(shù)代替參與優(yōu)化。圖6（a）給出了4 種方法的S(x)均值箱圖，由圖可見，本文方法的S(x)值最小。這表明本文方法優(yōu)化結(jié)果更能體現(xiàn)用戶偏好，算法對隱式指標(biāo)的刻畫能力最強。

圖6 可用性指標(biāo)Fig.6 Availability indicators

迷失度用于度量用戶對操作對象的迷茫程度，反映用戶的疲勞性感受[29]：

式中，No′是用戶在一次進化任務(wù)中評價的互異個體數(shù)目，No′是用戶在一次進化任務(wù)中獲得的最優(yōu)評價的個體數(shù)目，T′是算法運行終止進化代數(shù)。當(dāng)迷失度小于0.4 時，用戶不會對操作對象顯示出任何可觀察到的迷失特征，當(dāng)迷失度大于0.5 時，用戶就會出現(xiàn)迷失特征，同時疲勞會快速增加。用戶迷失度箱圖如圖6（b）所示。可以看到本文方法迷失度最小，用戶評價最準(zhǔn)確。

進化耗時Tt反映了算法的優(yōu)化效率，同時也可以表征用戶的疲勞性。交互時間越長，用戶越容易疲勞。4 種方法的Tt箱圖如圖6（c）所示?？梢钥吹奖疚姆椒ê臅r最短，說明本文方法用戶操作時間最短，用戶最不容易疲勞。

通過實驗結(jié)果與分析，本文方法對混合指標(biāo)分組優(yōu)化能獲得分布性和延展性更好的Pareto前沿，深度學(xué)習(xí)預(yù)測隱式指標(biāo)更準(zhǔn)確，子種群并行進化能有效協(xié)調(diào)不同類型的指標(biāo)優(yōu)化。與對比方法相比，本文方法能獲得質(zhì)量更高的Pareto最優(yōu)解集，人機交互性更好。

4 結(jié)束語

高維混合多目標(biāo)優(yōu)化問題包含不同類型指標(biāo)，且數(shù)量較多，求解難度較大。本文提出一種針對該問題的并行進化優(yōu)化方法。該方法基于目標(biāo)相關(guān)性對優(yōu)化目標(biāo)分組，將高維混合多目標(biāo)優(yōu)化問題分解為若干子問題。為了實現(xiàn)目標(biāo)分組，采用深度卷積神經(jīng)網(wǎng)絡(luò)預(yù)測隱式性能指標(biāo)，降低用戶操作負擔(dān)。對于每個子優(yōu)化問題，采用對應(yīng)子種群并行進化，提高問題求解速度。通過室內(nèi)布局優(yōu)化問題驗證該方法的有效性，并與其他多種相關(guān)進化優(yōu)化方法進行比較。實驗結(jié)果表明，本文方法能有效提高算法搜索性能，獲得高質(zhì)量Pareto最優(yōu)解集。高維混合多目標(biāo)優(yōu)化問題的交互式進化求解過程存在偏好波動，這會帶來隱式指標(biāo)的動態(tài)變化，進而改變Pareto最優(yōu)解集。另一方面，如果顯式指標(biāo)存在時間變化參數(shù)，也會帶來Pareto 最優(yōu)解集的動態(tài)變化，這些都給問題求解增加了新的困難。因此，尋找Pareto最優(yōu)前沿的特征點檢測環(huán)境變化，并根據(jù)環(huán)境變化預(yù)測種群進化方向，是進一步研究的問題。