改進(jìn)的快速非支配排序遺傳算法II及其在投資組合中的應(yīng)用

胡博, 肖輝, 金浩, 汪鐳

(1.同濟(jì)大學(xué)， 電子與信息工程學(xué)院， 上海 201804; 2.上海財(cái)經(jīng)大學(xué)， 統(tǒng)計(jì)與管理學(xué)院， 上海 200433)

0 引言

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

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

1 基本NSGA-II分析及其改進(jìn)

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

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

(1)

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

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

圖1 擁擠度距離示意圖

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

(2)

其中

(3)

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

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

2 實(shí)驗(yàn)及分析

2.1 在測試集上的實(shí)驗(yàn)

本文采用ZDT[4]作為測試函數(shù)。對比算法為NSGA-IISDR[8], NSGA-II, MOPSO[9]和SPEA2[4]，對應(yīng)參數(shù)按照開發(fā)者建議設(shè)置。評價(jià)指標(biāo)為HV和IGD[8]。算法最大評價(jià)次數(shù)10 000次，每個(gè)算法運(yùn)行20次。采用Friedman檢驗(yàn)統(tǒng)計(jì)算法在不同指標(biāo)上性能。

表1列出了對比算法在HV指標(biāo)上實(shí)驗(yàn)結(jié)果。從表1中可以看出，INSGA-II在除在ZDT3上均取得較好性能。從最后一行統(tǒng)計(jì)結(jié)果看出，INSGA-II仍然明顯超過其他算法。表2列出了對比算法在IGD指標(biāo)上實(shí)驗(yàn)結(jié)果。從對比結(jié)果可以看出，INSGA-II在6個(gè)測試函數(shù)上均為最優(yōu)。從統(tǒng)計(jì)結(jié)果可看出，INSGA-II性能明顯超過其他對比算法。從表1和表2實(shí)驗(yàn)結(jié)果和統(tǒng)計(jì)數(shù)據(jù)上可看出，本文所提策略確實(shí)提高了NSGA-II整體性能。

表1 對比算法在HV指標(biāo)上實(shí)驗(yàn)結(jié)果

表2 對比算法在IGD指標(biāo)上實(shí)驗(yàn)結(jié)果

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

圖2 算法在IGD指標(biāo)上的動態(tài)數(shù)據(jù)比較

圖3 算法在HV指標(biāo)上的動態(tài)數(shù)據(jù)比較

2.2 INSGA-II在投資組合優(yōu)化上的應(yīng)用

在人們投資過程中，經(jīng)常需要最大化期望收益以及最小化風(fēng)險(xiǎn)[10]，具體可表達(dá)如下：

(4)

其中，x表示決策矢量，對應(yīng)每一維度表示每支基金回報(bào)率，σi,j表示第i支基金和第j支基金協(xié)方差，ri表示第i支基金回報(bào)率。第一個(gè)目標(biāo)表示整體投資組合風(fēng)險(xiǎn)，第二個(gè)目標(biāo)表示期望回報(bào)率。下列仿真采用的數(shù)據(jù)集為公開數(shù)據(jù)集 (https://www.metatrader5.com/cn)。

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

圖4 所求前沿面比較

圖5 算法在HV指標(biāo)上的動態(tài)展示

3 總結(jié)

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