基于遷移學(xué)習(xí)的NSGAⅡ算法

劉 璐，蔣 艷

（上海理工大學(xué)管理學(xué)院，上海 200093）

0 引言

進(jìn)化優(yōu)化算法是一種基于模擬自然生物進(jìn)化過程的算法，通過使用染色體表示問題的解，選擇適合的染色體群進(jìn)行復(fù)制、交叉、變異和選擇，產(chǎn)生新的更能適合環(huán)境的染色體群［1］。此過程不斷循環(huán)迭代，直到找出最適合環(huán)境的個體，得到問題的最優(yōu)解。

1993 年Srinivas 等［2］設(shè)計(jì)了非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm，NSGA），這是第一代多目標(biāo)進(jìn)化算法之一；2002 年Deb 等［3］對NSGA 算法進(jìn)行改進(jìn)，在此基礎(chǔ)上提出第二代多目標(biāo)進(jìn)化算法NSGAⅡ算法（Non-dominated Sorting Genetic Algorithm Ⅱ，NSGAⅡ）。NSGAⅡ算法由于提高了種群的進(jìn)化水平和搜索效率，成為目前最流行的多目標(biāo)進(jìn)化算法之一；陶文華等［4］將差分進(jìn)化融入NSGAⅡ算法，差分進(jìn)化算法對初始種群進(jìn)行交叉和變異操作得到新種群，該算法獲得的Pareto 最優(yōu)解集更均勻；路艷雪等［5］通過設(shè)計(jì)正態(tài)分布交叉算子和改進(jìn)的自適應(yīng)變化變異算子，能夠快速獲取Pareto 最優(yōu)解集，提高了算法的收斂速度和精確度。

傳統(tǒng)的進(jìn)化優(yōu)化算法中初始種群都是隨機(jī)產(chǎn)生的，沒有考慮之前是否優(yōu)化過相似問題，都是從零開始搜索解。遷移學(xué)習(xí)［6-7］是通過已有知識解決具有相關(guān)性但不同源域問題的一種新的機(jī)器學(xué)習(xí)方法。相比于傳統(tǒng)機(jī)器學(xué)習(xí)方法，遷移學(xué)習(xí)并不要求訓(xùn)練樣本和測試樣本獨(dú)立分布，也不需要大量的訓(xùn)練樣本，適用于小數(shù)據(jù)樣本量訓(xùn)練。遷移學(xué)習(xí)在文本處理［8］、情感分類［9］、圖像數(shù)據(jù)處理［10］和推薦系統(tǒng)［11］等領(lǐng)域應(yīng)用很好。目前，遷移學(xué)習(xí)在進(jìn)化優(yōu)化領(lǐng)域有了一定應(yīng)用，F(xiàn)eng 等［12］將遷移學(xué)習(xí)運(yùn)用到車輛路徑問題中，提出文化基因進(jìn)化框架；徐茂鑫等［13］提出新的遷移蜂群優(yōu)化算法并應(yīng)用到電力系統(tǒng)的無功優(yōu)化中；Dinh 等［14］在使用遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)權(quán)重時，將源任務(wù)得到的個體解集進(jìn)行保存，在處理新任務(wù)時從個體解集中遷移出個體代替初始個體；邱立明［15］在動態(tài)多目標(biāo)優(yōu)化的算法框架Tr-DMOEA 基礎(chǔ)上提出基于流形的遷移動態(tài)多目標(biāo)優(yōu)化算法并運(yùn)用到多任務(wù)優(yōu)化問題研究中；楊康［16］提出基于相似歷史信息遷移學(xué)習(xí)的骨干粒子群優(yōu)化算法并應(yīng)用到旅行商問題中。

上述研究將遷移學(xué)習(xí)融入進(jìn)化優(yōu)化算法，提高了算法性能，但都是對單目標(biāo)和動態(tài)多目標(biāo)問題的研究，并不適用于靜態(tài)多目標(biāo)。鑒于此，本文基于NSGAⅡ算法融入遷移學(xué)習(xí)思想，設(shè)計(jì)了基于遷移學(xué)習(xí)的NSGAⅡ算法（Tr-NS?GAⅡ），解決靜態(tài)多目標(biāo)優(yōu)化問題。

1 相關(guān)工作

1.1 多目標(biāo)問題

多目標(biāo)優(yōu)化問題［1］（Multi-objective Optimization Prob?lem，MOP）一般由決策變量、目標(biāo)函數(shù)和約束條件組成，可以寫成如下形式：

式中，x=(x1,x2,x3,...xn)∈D為決策變量，y=(f1,f2,...,fm)∈Y表示目標(biāo)向量，D為決策空間，Y為目標(biāo)空間。

定義1（Pareto 支配）設(shè)MOP 的兩個可行解為x1、x2，對應(yīng)的目標(biāo)F(x1)、F(x2)滿足以下條件時：

稱x1支配x2，即x1?x2。

定義2（Pareto最優(yōu)解集）對于MOP 的可行解x*滿足{x*|?x,x?x*}，可行解x*稱為Pareto 最優(yōu)解，所有可行解組成的集合即為Pareto 最優(yōu)解集（POS，Pareto Optimal Set）。

定義3（Pareto 最優(yōu)前沿）對于MOP 的最優(yōu)前沿POF（Pareto Optimal Front，POF），是POS 映射在目標(biāo)空間上的值，POF={y*|y*=F(x*),x*∈POS} 。

1.2 NSGAⅡ算法

NSGAⅡ算法［17］相較于NSGA 算法采用了快速非支配排序，從而降低了算法的計(jì)算復(fù)雜度。同時NSGAⅡ算法提出擁擠度和擁擠度比較算子兩個概念，代替原NSGA 算法需要適應(yīng)度共享策略。NSGAⅡ算法還引入精英策略，擴(kuò)大采樣空間，將父代種群和子代種群合并，保證優(yōu)良個體能夠留存下來。快速非支配排序和擁擠度距離計(jì)算步驟如下：

（1）快速非支配排序。首先計(jì)算出所有個體兩兩之間的支配關(guān)系，得到當(dāng)前群體的非支配解集，記為第一層；再從剩余的個體中找出非支配解集，記為第二層，循環(huán)到所有個體都被分層。

（2）擁擠度距離。擁擠度距離是估量一個解的空間周圍解的聚集程度。對于每個目標(biāo)函數(shù)，先對非支配解集中的解按照函數(shù)值大小排序，再計(jì)算周圍兩個解構(gòu)成的立方體平均邊長，結(jié)果即為擁擠度距離，另外邊界的擁擠度距離設(shè)為無窮。

1.3 遷移學(xué)習(xí)

1.3.1 最大均值差異

定義4（最大均值差異）將源域和目標(biāo)域的數(shù)據(jù)通過特征映射函數(shù)映射后，求兩者的均值之差即為最大均值差異［18］（Maximum Mean Discrepancy，MMD），其中φ表示χ→H的映射，公式如下：

1.3.2 遷移成分分析

遷移學(xué)習(xí)按照學(xué)習(xí)方法劃分為基于樣本的遷移學(xué)習(xí)、基于特征的遷移學(xué)習(xí)、基于模型的遷移學(xué)習(xí)和基于關(guān)系的遷移學(xué)習(xí)4 類。本文設(shè)計(jì)的算法采取基于特征的遷移學(xué)習(xí)中的遷移成分分析。Pan 等［19］提出遷移成分分析（Transfer Component Analysis，TCA）方法。TCA［20-21］在處理領(lǐng)域自適應(yīng)問題時，當(dāng)源域和目標(biāo)域邊緣分布不同時，通過映射函數(shù)將兩個領(lǐng)域的數(shù)據(jù)映射到一個高維的再生核希爾伯特空間（Reproducing Kernel Hilbert Space，RKHS），使得映射后的數(shù)據(jù)在映射空間中分布相似，數(shù)據(jù)距離縮小，屬性相近。在TCA 算法中引入核矩陣K 和L 如下所示：

令φ(x)=WTκx，則K 可以寫成：

將K 帶入MMD 公式，其中K 是一個對稱矩陣：

最終將TCA 優(yōu)化目標(biāo)化簡得到公式（6），其中H是一個中心矩陣H=In1+n2-1/(n1+n2)11?，I是(n1+n2)維單位矩陣，μtr(W?W) 是懲罰項(xiàng)，(KLK+μI)-1KHK的前m 個特征值就是源域和目標(biāo)域降維后的數(shù)據(jù)。

2 Tr-NSGAⅡ算法

傳統(tǒng)的進(jìn)化優(yōu)化算法都是從定義域中隨機(jī)產(chǎn)生初始種群，本文引入遷移學(xué)習(xí)思想設(shè)計(jì)Tr-NSGAⅡ算法。首先建立一個儲存庫，存儲函數(shù)的一些歷史信息，包括目標(biāo)維數(shù)、決策變量維數(shù)、特殊函數(shù)（例如三角函數(shù)、冪函數(shù)等）和函數(shù)的最高次冪等特征，及函數(shù)的Pareto 最優(yōu)解集，將其作為源域記為Xs，其中Pareto 最優(yōu)解集內(nèi)解的個數(shù)為S。當(dāng)獲得新任務(wù)時，提取目標(biāo)函數(shù)特征，與儲存庫中的函數(shù)比較，找出最相似的函數(shù)；再對目標(biāo)函數(shù)隨機(jī)產(chǎn)生初始種群并進(jìn)行非支配排序，得到的種群T記為目標(biāo)域Xt。將Xs 和Xt 通過TCA 算法學(xué)習(xí)得到Xs_new 和Xt_new。針對Xs_new 中每個個體s計(jì)算Xt_new 中個體t與其歐幾里得距離，得到L（l1,l2,...,ls），li為一個s與Xt_new 中所有t的歐幾里得距離，并對每個li進(jìn)行內(nèi)部排序，取第一個數(shù)li1構(gòu)成M；在M中返回Xt_new 中個體序號，找出Xt 中對應(yīng)個體形成新的種群。如果M中元素個數(shù)過少，為了保證種群的多樣性，源域和目標(biāo)域的定義域不一定相同，以避免局部收斂，按照一定比例r選取li，r的取值范圍為［10%，20%］。Tr-NSGAⅡ算法流程如下：

輸入：多目標(biāo)優(yōu)化問題F（x），個體數(shù)N，進(jìn)化代數(shù)，核函數(shù)，儲存庫；

輸出：問題的最優(yōu)解，儲存庫；

（1）建立儲存庫，提取目標(biāo)函數(shù)的特征，與儲存庫中的函數(shù)比較，找出最相似的原函數(shù)，并記其Pareto 最優(yōu)解集為Xs，Xs 為源域。

（2）對于目標(biāo)函數(shù)F（x）隨機(jī)產(chǎn)生初始種群N，對種群進(jìn)行非支配排序，并進(jìn)行選擇、交叉和變異得到種群Q，記為Xt，Xt 為目標(biāo)域。

（3）通過TCA 算法學(xué)習(xí)，選擇合適核函數(shù)將源域（Xs）和目標(biāo)域（Xt）映射到高維希爾伯特空間，得到映射后的源域（Xs_new）和目標(biāo)域（Xt_new）。

（4）設(shè)置初始種群P 為空集。

（5）對于Xs_new 中的每個個體，計(jì)算Xt_new 中的個體與其歐幾里得距離，找出最小值，返回Xt_new 中個體序號，并在Xt 中找出對應(yīng)個體并入種群P。

（6）當(dāng)P 小于N 時，隨機(jī)產(chǎn)生N-P 個個體，并入P。

（7）令進(jìn)化代數(shù)為零，利用NSGAⅡ算法對種群P 進(jìn)行快速非支配排序、擁擠度距離排序和精英選擇策略進(jìn)行更新。

（8）得到目標(biāo)函數(shù)最優(yōu)解，將目標(biāo)函數(shù)放入儲存庫，更新儲存庫。

3 Tr-NSGAⅡ算法實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境及測試函數(shù)

本實(shí)驗(yàn)采用Python3.7 實(shí)現(xiàn)所提出的算法，測試環(huán)境為Intel（R）Core（TM）、1.30GHzCPU、16GBRAM。儲存庫里的函數(shù)為ZDT1～4、ZDT6 系列、BNH 和Belegundu，目標(biāo)函數(shù)共有10 個［1］，具體形式見表1。

3.2 實(shí)驗(yàn)方法

本文選用4 種不同的評價(jià)指標(biāo)，從解的收斂性、解集的均勻性和算法的綜合性能來評價(jià)解的有效性。

（1）收斂性。GD 表示算法所獲得的非支配解集P 與問題真實(shí)的Pareto 前沿P*之間的平均最小距離，GD 越小表示算法的收斂性越好，計(jì)算公式如下：

（2）均勻性。Spacing 表示每個解到其它解的最小距離標(biāo)準(zhǔn)差，Spacing 越小表示解集越均勻，計(jì)算公式如下：

（3）算法綜合性能。IGD 表示算法所獲得的非支配解集與問題真實(shí)的Pareto 前沿P*距離的平均值。IGD 越小表示算法的綜合性能越好，即算法的收斂性和解集多樣性越好，計(jì)算公式如下：

3.3 實(shí)驗(yàn)結(jié)果分析

將兩種算法分別運(yùn)行30 次，找出其中最優(yōu)解。對于收斂性指標(biāo)GD，有80% 的函數(shù)下降，其中兩個函數(shù)變化率在5% 以下，一個函數(shù)變化率在5%～50% 之間，5 個函數(shù)變化率增加了50% 以上。函數(shù)TNK 最多改善99.97%，說明Tr-NSGAⅡ算法相對于NSGAⅡ算法收斂性能得到很好優(yōu)化。對于解集均勻性指標(biāo)Spacing，有60% 函數(shù)下降，其中一個函數(shù)變化率在5% 以下，3 個函數(shù)變化率在5%～50%之間，兩個函數(shù)在50% 以上，函數(shù)TNK 收斂性能優(yōu)化率達(dá)到100%，說明Tr-NSGAⅡ算法所得到的解集分布較為均勻。對于算法綜合性能指標(biāo)IGD，80% 的函數(shù)綜合性能得到改善。函數(shù)Con 和函數(shù)4 變化率在5% 以下，有3 個函數(shù)變化率在5%～50%，3 個函數(shù)變化率在50%～100% 之間，其中修改后的ZDT1 函數(shù)和修改后的ZDT6 函數(shù)綜合性能都得到很好改善，變化率在95% 以上，表明Tr-NSGAⅡ算法收斂性和解集的多樣性較NSGAⅡ提高很多，即Tr-NS?GAⅡ算法的綜合性能更好。綜上，引入歷史信息的Tr-NSGAⅡ算法在種群的搜索效果明顯好于NSGAⅡ算法，解集的均勻性和多樣性得到提高。測試函數(shù)實(shí)驗(yàn)結(jié)果如表2所示，Tr-NSGAⅡ和NSGAⅡ之間不同指標(biāo)變化率實(shí)驗(yàn)結(jié)果如表3 所示。

Table 1 Objective functions表1 目標(biāo)函數(shù)

4 結(jié)語

本文設(shè)計(jì)了基于遷移學(xué)習(xí)思想的Tr-NSGAⅡ算法，在存有歷史信息的儲存庫中找出相似的歷史問題得到源域，通過TCA 算法將源域和目標(biāo)域映射到高維再生核希爾伯特空間，即將歷史信息遷移到新的目標(biāo)函數(shù)中，得到含有歷史信息的種群，再利用NSGAⅡ算法繼續(xù)求解目標(biāo)函數(shù)。對10 個改進(jìn)的多目標(biāo)測試函數(shù)進(jìn)行試驗(yàn)，結(jié)果證明Tr-NSGAⅡ算法有效提高了種群的搜索效率，算法的收斂性能得到改善，優(yōu)化了解集的均勻性和多樣性，表明遷移學(xué)習(xí)可以融入進(jìn)化優(yōu)化算法解決靜態(tài)多目標(biāo)問題。但是本文所用的歷史任務(wù)和新任務(wù)之間屬性類似，實(shí)驗(yàn)數(shù)據(jù)集來源于標(biāo)準(zhǔn)的多目標(biāo)函數(shù)測試集，當(dāng)面對實(shí)際問題（如選址問題、背包問題和車間調(diào)度問題）時，歷史任務(wù)和新任務(wù)之間匹配策略應(yīng)該如何設(shè)計(jì)還需進(jìn)一步研究。

Table 2 Experimental results of algorithm optimization test function表2 比較算法優(yōu)化測試函數(shù)實(shí)驗(yàn)結(jié)果

Table 3 Experimental results of different index change rates between Tr-NSGA Ⅱand NSGA Ⅱ表3 Tr-NSGAⅡ和NSGAⅡ之間不同指標(biāo)變化率實(shí)驗(yàn)結(jié)果