改進的快速非支配排序遺傳算法II及其在投資組合中的應用

胡博, 肖輝, 金浩, 汪鐳

(1.同濟大學， 電子與信息工程學院， 上海 201804; 2.上海財經大學， 統計與管理學院， 上海 200433)

0 引言

在過去十幾年，進化計算領域[1-2]已經對多目標優化問題(Multi-objective Optimization Problems, MOPs)進行深入的研究，并提出了許多有效的算法[3]，如快速非支配排序遺傳算法II(NSGA-II)[4]。NSGA-II雖然在多目標優化問題上表現出良好性能，但是其采用的多樣性選擇機制和快速非支配排序策略[4]仍有不少缺陷。針對錦標賽策略存在重復選擇交叉個體的問題，張茂清等[5]引入Levy分布策略和三交叉個體策略以強化后代個體多樣性。同樣針對此問題，汪鐳等[6]提出引入多個交叉父代以降低重復選擇父代的概率。進一步，張茂清等[7]又提出在待交叉父代個體每個維度上引入擾動參數改變其值,然后將擾動父代做正常交叉操作產生新后代,以此避免了后代重復個體產生。

為進一步優化NSGA-II性能，本文重新設計了多樣性評價機制，并進一步將其引入NSGA-II。通過現有測試函數和一個實際投資組合優化問題綜合測試，所提的改進NSGA-II算法(Improved Fast Non-dominated Sorting Genetic Algorithm II, INSGA-II)具有良好的綜合性能。

1 基本NSGA-II分析及其改進

NSGA-II主要過程如下：首先初始化種群P，然后執行快速非支配排序和擁擠度距離計算操作；在此基礎上，采用錦標賽策略構建交叉池，然后執行交叉和變異操作，并得到子代種群Q；合并父代種群P和子代種群Q, 再次執行快速非支配排序和擁擠度距離計算；根據每個個體所在不同前沿面等級和擁擠度距離選擇較優個體保留為子代種群。若滿足結束條件，則輸出當前種群; 否則進入下次循環。

NSGA-II采用的擁擠度距離可表示如下：

(1)

其中，di表示第i個體擁擠度距離，fk(i+1)表示第i+1個個體第k個目標函數，M表示目標函數總數。

如圖1所示，在二維目標空間有A,B,C,D,E和F6個個體。根據擁擠度距離計算式(1)，個體B的擁擠度為4，個體E的擁擠度同樣為4。根據直觀理解，個體B和E具有相同擁擠度距離，但是很明顯個體B比個體E更加擁擠，因為個體B更加靠近C, 而個體E則居于中間位置。因此，基于以上分析，本文提出以下改進計算方式：

圖1 擁擠度距離示意圖

(fk(i)-fk(i-1)-lenk)2

(2)

其中

(3)

根據式(2)，B擁擠度為0.5，個體E擁擠度為0，說明個體E距離其相鄰個體更加均勻。因此，上述改進公式可以在一定程度上彌補原擁擠度評價機制的不足。基于式(2),INSGA-II偽代碼可表述如下。

INSGA-II偽代碼輸入:N(種群大小)輸出:P(種群)1:根據種群規模初始化種群P并計算適應值2:執行快速非支配排序和擁擠度距離操作3:While(是否滿足結束條件)4: 采用錦標賽策略構建交叉池5: 個體間執行交叉和變異操作6: 合并父代種群P和子代種群Q7: 執行快速非支配排序和改進擁擠度距離(式2)操作8: 更新種群9:End

2 實驗及分析

2.1 在測試集上的實驗

本文采用ZDT[4]作為測試函數。對比算法為NSGA-IISDR[8], NSGA-II, MOPSO[9]和SPEA2[4]，對應參數按照開發者建議設置。評價指標為HV和IGD[8]。算法最大評價次數10 000次，每個算法運行20次。采用Friedman檢驗統計算法在不同指標上性能。

表1列出了對比算法在HV指標上實驗結果。從表1中可以看出，INSGA-II在除在ZDT3上均取得較好性能。從最后一行統計結果看出，INSGA-II仍然明顯超過其他算法。表2列出了對比算法在IGD指標上實驗結果。從對比結果可以看出，INSGA-II在6個測試函數上均為最優。從統計結果可看出，INSGA-II性能明顯超過其他對比算法。從表1和表2實驗結果和統計數據上可看出，本文所提策略確實提高了NSGA-II整體性能。

表1 對比算法在HV指標上實驗結果

表2 對比算法在IGD指標上實驗結果

圖2和圖3分別顯示了IGD和HV指標的動態變化過程。從圖2可看出，INSGA-II收斂速度明顯優于其他對比算法；在HV指標上，INSGA-II收劍速度也較為明顯，超過了標準NSGA-II 以及其他算法，說明INSGA-II整體性能出眾。

圖2 算法在IGD指標上的動態數據比較

圖3 算法在HV指標上的動態數據比較

2.2 INSGA-II在投資組合優化上的應用

在人們投資過程中，經常需要最大化期望收益以及最小化風險[10]，具體可表達如下：

(4)

其中，x表示決策矢量，對應每一維度表示每支基金回報率，σi,j表示第i支基金和第j支基金協方差，ri表示第i支基金回報率。第一個目標表示整體投資組合風險，第二個目標表示期望回報率。下列仿真采用的數據集為公開數據集 (https://www.metatrader5.com/cn)。

圖4展示不同算法所求帕爾托前沿面。如圖4所示，INSGA-II所求前沿面的收斂性更加出眾，同時可以看出SPEA2優于NSGA-II, MOPSO和NSGA-IISDR。從圖5中不同算法在HV指標上的收斂性曲線可看出， INSGA-II收斂速度明顯優于NSGA-II, NSGA-IISDR和SPEA2, MOPSO展現出最差收斂速度和收斂性。基于以上分析，可看出INSGA-II綜合性能表現較為突出。

圖4 所求前沿面比較

圖5 算法在HV指標上的動態展示

3 總結

本文針對經典優化器NSGA-II中擁擠度距離機制無法有效區分較為擁擠個體的缺陷，提出了改進擁擠度評價機制, 并進一步提出了改進的INSGA-II。在ZDT測試集和投資組合優化問題上實驗結果和分析表明所提算法的整體性能有了較大的提升。未來的研究工作，應進一步優化投資組合數學模型，以提升該模型在實際應用中的實用性和有效性。