劉 璐,蔣 艷
(上海理工大學(xué)管理學(xué)院,上海 200093)
進化優(yōu)化算法是一種基于模擬自然生物進化過程的算法,通過使用染色體表示問題的解,選擇適合的染色體群進行復(fù)制、交叉、變異和選擇,產(chǎn)生新的更能適合環(huán)境的染色體群[1]。此過程不斷循環(huán)迭代,直到找出最適合環(huán)境的個體,得到問題的最優(yōu)解。
1993 年Srinivas 等[2]設(shè)計了非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm,NSGA),這是第一代多目標進化算法之一;2002 年Deb 等[3]對NSGA 算法進行改進,在此基礎(chǔ)上提出第二代多目標進化算法NSGAⅡ算法(Non-dominated Sorting Genetic Algorithm Ⅱ,NSGAⅡ)。NSGAⅡ算法由于提高了種群的進化水平和搜索效率,成為目前最流行的多目標進化算法之一;陶文華等[4]將差分進化融入NSGAⅡ算法,差分進化算法對初始種群進行交叉和變異操作得到新種群,該算法獲得的Pareto 最優(yōu)解集更均勻;路艷雪等[5]通過設(shè)計正態(tài)分布交叉算子和改進的自適應(yīng)變化變異算子,能夠快速獲取Pareto 最優(yōu)解集,提高了算法的收斂速度和精確度。
傳統(tǒng)的進化優(yōu)化算法中初始種群都是隨機產(chǎn)生的,沒有考慮之前是否優(yōu)化過相似問題,都是從零開始搜索解。遷移學(xué)習(xí)[6-7]是通過已有知識解決具有相關(guān)性但不同源域問題的一種新的機器學(xué)習(xí)方法。相比于傳統(tǒng)機器學(xué)習(xí)方法,遷移學(xué)習(xí)并不要求訓(xùn)練樣本和測試樣本獨立分布,也不需要大量的訓(xùn)練樣本,適用于小數(shù)據(jù)樣本量訓(xùn)練。遷移學(xué)習(xí)在文本處理[8]、情感分類[9]、圖像數(shù)據(jù)處理[10]和推薦系統(tǒng)[11]等領(lǐng)域應(yīng)用很好。目前,遷移學(xué)習(xí)在進化優(yōu)化領(lǐng)域有了一定應(yīng)用,F(xiàn)eng 等[12]將遷移學(xué)習(xí)運用到車輛路徑問題中,提出文化基因進化框架;徐茂鑫等[13]提出新的遷移蜂群優(yōu)化算法并應(yīng)用到電力系統(tǒng)的無功優(yōu)化中;Dinh 等[14]在使用遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)權(quán)重時,將源任務(wù)得到的個體解集進行保存,在處理新任務(wù)時從個體解集中遷移出個體代替初始個體;邱立明[15]在動態(tài)多目標優(yōu)化的算法框架Tr-DMOEA 基礎(chǔ)上提出基于流形的遷移動態(tài)多目標優(yōu)化算法并運用到多任務(wù)優(yōu)化問題研究中;楊康[16]提出基于相似歷史信息遷移學(xué)習(xí)的骨干粒子群優(yōu)化算法并應(yīng)用到旅行商問題中。
上述研究將遷移學(xué)習(xí)融入進化優(yōu)化算法,提高了算法性能,但都是對單目標和動態(tài)多目標問題的研究,并不適用于靜態(tài)多目標。鑒于此,本文基于NSGAⅡ算法融入遷移學(xué)習(xí)思想,設(shè)計了基于遷移學(xué)習(xí)的NSGAⅡ算法(Tr-NS?GAⅡ),解決靜態(tài)多目標優(yōu)化問題。
多目標優(yōu)化問題[1](Multi-objective Optimization Prob?lem,MOP)一般由決策變量、目標函數(shù)和約束條件組成,可以寫成如下形式:
式中,x=(x1,x2,x3,...xn)∈D為決策變量,y=(f1,f2,...,fm)∈Y表示目標向量,D為決策空間,Y為目標空間。
定義1(Pareto 支配)設(shè)MOP 的兩個可行解為x1、x2,對應(yīng)的目標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 映射在目標空間上的值,POF={y*|y*=F(x*),x*∈POS} 。
NSGAⅡ算法[17]相較于NSGA 算法采用了快速非支配排序,從而降低了算法的計算復(fù)雜度。同時NSGAⅡ算法提出擁擠度和擁擠度比較算子兩個概念,代替原NSGA 算法需要適應(yīng)度共享策略。NSGAⅡ算法還引入精英策略,擴大采樣空間,將父代種群和子代種群合并,保證優(yōu)良個體能夠留存下來??焖俜侵渑判蚝蛽頂D度距離計算步驟如下:
(1)快速非支配排序。首先計算出所有個體兩兩之間的支配關(guān)系,得到當(dāng)前群體的非支配解集,記為第一層;再從剩余的個體中找出非支配解集,記為第二層,循環(huán)到所有個體都被分層。
(2)擁擠度距離。擁擠度距離是估量一個解的空間周圍解的聚集程度。對于每個目標函數(shù),先對非支配解集中的解按照函數(shù)值大小排序,再計算周圍兩個解構(gòu)成的立方體平均邊長,結(jié)果即為擁擠度距離,另外邊界的擁擠度距離設(shè)為無窮。
1.3.1 最大均值差異
定義4(最大均值差異)將源域和目標域的數(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è)計的算法采取基于特征的遷移學(xué)習(xí)中的遷移成分分析。Pan 等[19]提出遷移成分分析(Transfer Component Analysis,TCA)方法。TCA[20-21]在處理領(lǐng)域自適應(yīng)問題時,當(dāng)源域和目標域邊緣分布不同時,通過映射函數(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)化目標化簡得到公式(6),其中H是一個中心矩陣H=In1+n2-1/(n1+n2)11?,I是(n1+n2)維單位矩陣,μtr(W?W) 是懲罰項,(KLK+μI)-1KHK的前m 個特征值就是源域和目標域降維后的數(shù)據(jù)。
傳統(tǒng)的進化優(yōu)化算法都是從定義域中隨機產(chǎn)生初始種群,本文引入遷移學(xué)習(xí)思想設(shè)計Tr-NSGAⅡ算法。首先建立一個儲存庫,存儲函數(shù)的一些歷史信息,包括目標維數(shù)、決策變量維數(shù)、特殊函數(shù)(例如三角函數(shù)、冪函數(shù)等)和函數(shù)的最高次冪等特征,及函數(shù)的Pareto 最優(yōu)解集,將其作為源域記為Xs,其中Pareto 最優(yōu)解集內(nèi)解的個數(shù)為S。當(dāng)獲得新任務(wù)時,提取目標函數(shù)特征,與儲存庫中的函數(shù)比較,找出最相似的函數(shù);再對目標函數(shù)隨機產(chǎn)生初始種群并進行非支配排序,得到的種群T記為目標域Xt。將Xs 和Xt 通過TCA 算法學(xué)習(xí)得到Xs_new 和Xt_new。針對Xs_new 中每個個體s計算Xt_new 中個體t與其歐幾里得距離,得到L(l1,l2,...,ls),li為一個s與Xt_new 中所有t的歐幾里得距離,并對每個li進行內(nèi)部排序,取第一個數(shù)li1構(gòu)成M;在M中返回Xt_new 中個體序號,找出Xt 中對應(yīng)個體形成新的種群。如果M中元素個數(shù)過少,為了保證種群的多樣性,源域和目標域的定義域不一定相同,以避免局部收斂,按照一定比例r選取li,r的取值范圍為[10%,20%]。Tr-NSGAⅡ算法流程如下:
輸入:多目標優(yōu)化問題F(x),個體數(shù)N,進化代數(shù),核函數(shù),儲存庫;
輸出:問題的最優(yōu)解,儲存庫;
(1)建立儲存庫,提取目標函數(shù)的特征,與儲存庫中的函數(shù)比較,找出最相似的原函數(shù),并記其Pareto 最優(yōu)解集為Xs,Xs 為源域。
(2)對于目標函數(shù)F(x)隨機產(chǎn)生初始種群N,對種群進行非支配排序,并進行選擇、交叉和變異得到種群Q,記為Xt,Xt 為目標域。
(3)通過TCA 算法學(xué)習(xí),選擇合適核函數(shù)將源域(Xs)和目標域(Xt)映射到高維希爾伯特空間,得到映射后的源域(Xs_new)和目標域(Xt_new)。
(4)設(shè)置初始種群P 為空集。
(5)對于Xs_new 中的每個個體,計算Xt_new 中的個體與其歐幾里得距離,找出最小值,返回Xt_new 中個體序號,并在Xt 中找出對應(yīng)個體并入種群P。
(6)當(dāng)P 小于N 時,隨機產(chǎn)生N-P 個個體,并入P。
(7)令進化代數(shù)為零,利用NSGAⅡ算法對種群P 進行快速非支配排序、擁擠度距離排序和精英選擇策略進行更新。
(8)得到目標函數(shù)最優(yōu)解,將目標函數(shù)放入儲存庫,更新儲存庫。
本實驗采用Python3.7 實現(xiàn)所提出的算法,測試環(huán)境為Intel(R)Core(TM)、1.30GHzCPU、16GBRAM。儲存庫里的函數(shù)為ZDT1~4、ZDT6 系列、BNH 和Belegundu,目標函數(shù)共有10 個[1],具體形式見表1。
本文選用4 種不同的評價指標,從解的收斂性、解集的均勻性和算法的綜合性能來評價解的有效性。
(1)收斂性。GD 表示算法所獲得的非支配解集P 與問題真實的Pareto 前沿P*之間的平均最小距離,GD 越小表示算法的收斂性越好,計算公式如下:
(2)均勻性。Spacing 表示每個解到其它解的最小距離標準差,Spacing 越小表示解集越均勻,計算公式如下:
(3)算法綜合性能。IGD 表示算法所獲得的非支配解集與問題真實的Pareto 前沿P*距離的平均值。IGD 越小表示算法的綜合性能越好,即算法的收斂性和解集多樣性越好,計算公式如下:
將兩種算法分別運行30 次,找出其中最優(yōu)解。對于收斂性指標GD,有80% 的函數(shù)下降,其中兩個函數(shù)變化率在5% 以下,一個函數(shù)變化率在5%~50% 之間,5 個函數(shù)變化率增加了50% 以上。函數(shù)TNK 最多改善99.97%,說明Tr-NSGAⅡ算法相對于NSGAⅡ算法收斂性能得到很好優(yōu)化。對于解集均勻性指標Spacing,有60% 函數(shù)下降,其中一個函數(shù)變化率在5% 以下,3 個函數(shù)變化率在5%~50%之間,兩個函數(shù)在50% 以上,函數(shù)TNK 收斂性能優(yōu)化率達到100%,說明Tr-NSGAⅡ算法所得到的解集分布較為均勻。對于算法綜合性能指標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ù)實驗結(jié)果如表2所示,Tr-NSGAⅡ和NSGAⅡ之間不同指標變化率實驗結(jié)果如表3 所示。
Table 1 Objective functions表1 目標函數(shù)
本文設(shè)計了基于遷移學(xué)習(xí)思想的Tr-NSGAⅡ算法,在存有歷史信息的儲存庫中找出相似的歷史問題得到源域,通過TCA 算法將源域和目標域映射到高維再生核希爾伯特空間,即將歷史信息遷移到新的目標函數(shù)中,得到含有歷史信息的種群,再利用NSGAⅡ算法繼續(xù)求解目標函數(shù)。對10 個改進的多目標測試函數(shù)進行試驗,結(jié)果證明Tr-NSGAⅡ算法有效提高了種群的搜索效率,算法的收斂性能得到改善,優(yōu)化了解集的均勻性和多樣性,表明遷移學(xué)習(xí)可以融入進化優(yōu)化算法解決靜態(tài)多目標問題。但是本文所用的歷史任務(wù)和新任務(wù)之間屬性類似,實驗數(shù)據(jù)集來源于標準的多目標函數(shù)測試集,當(dāng)面對實際問題(如選址問題、背包問題和車間調(diào)度問題)時,歷史任務(wù)和新任務(wù)之間匹配策略應(yīng)該如何設(shè)計還需進一步研究。
Table 2 Experimental results of algorithm optimization test function表2 比較算法優(yōu)化測試函數(shù)實驗結(jié)果
Table 3 Experimental results of different index change rates between Tr-NSGA Ⅱand NSGA Ⅱ表3 Tr-NSGAⅡ和NSGAⅡ之間不同指標變化率實驗結(jié)果