基于遷移學習的NSGAⅡ算法

劉 璐，蔣 艷

（上海理工大學管理學院，上海 200093）

0 引言

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

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

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

上述研究將遷移學習融入進化優化算法，提高了算法性能，但都是對單目標和動態多目標問題的研究，并不適用于靜態多目標。鑒于此，本文基于NSGAⅡ算法融入遷移學習思想，設計了基于遷移學習的NSGAⅡ算法（Tr-NS?GAⅡ），解決靜態多目標優化問題。

1 相關工作

1.1 多目標問題

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

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

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

稱x1支配x2，即x1?x2。

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

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

1.2 NSGAⅡ算法

NSGAⅡ算法［17］相較于NSGA 算法采用了快速非支配排序，從而降低了算法的計算復雜度。同時NSGAⅡ算法提出擁擠度和擁擠度比較算子兩個概念，代替原NSGA 算法需要適應度共享策略。NSGAⅡ算法還引入精英策略，擴大采樣空間，將父代種群和子代種群合并，保證優良個體能夠留存下來?？焖俜侵渑判蚝蛽頂D度距離計算步驟如下：

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

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

1.3 遷移學習

1.3.1 最大均值差異

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

1.3.2 遷移成分分析

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

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

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

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

2 Tr-NSGAⅡ算法

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

輸入：多目標優化問題F（x），個體數N，進化代數，核函數，儲存庫；

輸出：問題的最優解，儲存庫；

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

（2）對于目標函數F（x）隨機產生初始種群N，對種群進行非支配排序，并進行選擇、交叉和變異得到種群Q，記為Xt，Xt 為目標域。

（3）通過TCA 算法學習，選擇合適核函數將源域（Xs）和目標域（Xt）映射到高維希爾伯特空間，得到映射后的源域（Xs_new）和目標域（Xt_new）。

（4）設置初始種群P 為空集。

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

（6）當P 小于N 時，隨機產生N-P 個個體，并入P。

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

（8）得到目標函數最優解，將目標函數放入儲存庫，更新儲存庫。

3 Tr-NSGAⅡ算法實驗

3.1 實驗環境及測試函數

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

3.2 實驗方法

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

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

（2）均勻性。Spacing 表示每個解到其它解的最小距離標準差，Spacing 越小表示解集越均勻，計算公式如下：

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

3.3 實驗結果分析

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

Table 1 Objective functions表1 目標函數

4 結語

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

Table 2 Experimental results of algorithm optimization test function表2 比較算法優化測試函數實驗結果

Table 3 Experimental results of different index change rates between Tr-NSGA Ⅱand NSGA Ⅱ表3 Tr-NSGAⅡ和NSGAⅡ之間不同指標變化率實驗結果