基于混合策略的快速非支配排序算法II

張茂清，汪 鐳，崔志華，郭為安

(1.同濟大學 電子與信息工程學院，上海 201804；2.太原科技大學 計算機科學與技術學院，山西 太原 030024；3.同濟大學 中德工程學院，上海 201804)

0 引言

在實際工程應用中，有許多目標函數(shù)為2～3個的優(yōu)化問題[1-3]，且目標函數(shù)間具有彼此沖突的特點，此類問題一般被認為NP-Hard問題。傳統(tǒng)的方法，如線性規(guī)劃、梯度下降等，由于對問題特征具有較為嚴格的要求，導致解決此類問題時要付出極為昂貴的時間代價，甚至在有限時間內無法獲得滿意解。進化算法的出現(xiàn)為此類問題提供了新思路。典型算法如NSGA-II[4]、SPEAII(improved strength pareto evolutionary algorithm)[5],以及NNIA(multi-objective immune algorithm with non- dominated neighbor-based selection)[6]等在此類問題上均表現(xiàn)突出。其中，NSGA-II作為多目標優(yōu)化算法的典型代表，受到很多研究者的廣泛關注。根據(jù)研究角度不同，可將近些年研究成果作如下分類。

就應用角度而言，NSGA-II及其改進方法已經(jīng)被應用到許多實際優(yōu)化問題中。為解決服裝調度生產(chǎn)中最大完成時間和最小延期交貨時間的問題，陸金芳[7]提出改進排序適應度和按需分層策略，極大提高了服裝調度的效率。黃敏鎂等[8]為了最大化供應鏈環(huán)境下協(xié)商Agent自身效用和合作企業(yè)建議相似度，采用了正整數(shù)和小數(shù)混合的實數(shù)編碼方式，并在遺傳操作中增加了約束限制，以剔除算法運行中產(chǎn)生不可行個體。在應急物流系統(tǒng)設計中，需要綜合考慮系統(tǒng)總成本、總耗時以及道路安全性等問題。陳剛等[9]針對此問題特點提出了改進個體交叉和變異方式，并進一步將精英策略融入NSGA-II。在將NSGA-II應用于水污染修復管理模型時，NSGA-II不能有效地收斂到真實Pareto 前沿。為提升NSGA-II收斂性，宋健[10]提出將HCS(hill climber with step)融入NSGA-II，極大地提升了算法收斂能力。

在理論研究方面，NSGA-II也得到了極大的改進。為解決NSGA-II擁擠度距離機制無法有效區(qū)分多樣性個體的缺陷，崔志華等[1]提出了基于平均距離聚類的多樣性評價指標，并進一步提出了基于平均距離聚類的NSGA-II。受無免費午餐定理啟發(fā)，陳輔斌等[11]提出將免疫平衡原理引入NSGA-II選擇策略。為解決NSGA-II中擁擠度距離機制無法衡量個體周圍個體密度的缺陷，王祥[12]提出將密度聚類思想融入到個體擁擠度評價機制，并進一步提出了個體鄰域的構建方法。汪文文等[13]將禁忌搜索的思想融入精英保留策略，有效地平衡了全局搜索和局部搜索。為了拓展NSGA-II在高緯多目標優(yōu)化問題上的性能，Yang等[14]提出利用基于網(wǎng)格支配的方法區(qū)分個體，并進一步利用網(wǎng)格支配產(chǎn)生后代。同樣針對此類問題，Zhang等[15]提出將分解的思想引入到多目標優(yōu)化問題中，可有效避免Pareto支配失效的問題。

雖然NSGA-II在理論和應用方面已經(jīng)取得了很大的進步，但是采用的錦標賽策略會導致重復父代個體的產(chǎn)生，并由此導致后代多樣性受到影響。為解決此問題，筆者從以下兩方面進行改進，第一,引入Lévy分布，增加發(fā)現(xiàn)父代個體周圍潛在較優(yōu)個體的能力；第二，提出三交叉父代策略，進一步降低重復父代個體對后代多樣性的影響。最后提出基于混合策略的NSGA-II(fast non-dominated sorting genetic algorithm II based on hybrid strategies,HSNSGA-II)。

1 基本概念以及錦標賽選擇策略

1.1 基本概念

一個典型多目標優(yōu)化問題可形式化表示如下[1]：

minF(X)=[f1(X),f2(X),…,fM(X)]，

(1)

s.t.X∈Ω,

式中：X=(x1,x2,x3,…,xD)是一個D維決策向量；Ω?Rn為決策空間；M為目標函數(shù)數(shù)量。由于多目標優(yōu)化問題中不同目標間具有相互沖突的特點，導致不存在最優(yōu)個體，而是最優(yōu)解集。以下為多目標優(yōu)化問題中的主要概念。

定義1:若變量X目標函數(shù)f(X)=(f1(X),f2(X),…,fM(X))T，變量X′目標函數(shù)f(X′)=(f1(X′),f2(X′),…,fM(X′))T，當且僅當對于?i∈{1,2,…,M}，fi(X)≤fi(X′)成立，且存在k∈{1,2,…,M}，使得fk(X)

定義2：決策空間上所有Pareto最優(yōu)解構成的集合稱為Pareto最優(yōu)解集。

定義3:Pareto最優(yōu)解集在目標空間上對應解集合稱Pareto前沿面。

1.2 基本NSGA-II框架以及缺陷分析

作為多目標優(yōu)化領域里的典型代表算法，NSGA-II有兩個核心策略，非支配排序和擁擠度距離。非支配排序用于強化種群個體間的選擇壓力，擁擠度距離用于評價個體的多樣性，通過上述兩種策略達到種群個體不斷進化。種群更新主要過程可簡述如下。

設P和Q分別為具有N個個體的父代種群和對應的子代種群。首先，將兩種種群合并為C=P∪Q。為從合并的種群C中選擇出N個后代個體，利用非支配排序策略對種群C進行操作，可得到多個Pareto前沿面。然后，從第1層前沿面開始，累積計算個體數(shù)量，直到第l層個體數(shù)量首次超過N。為從第l層選擇出較優(yōu)個體，利用擁擠度距離計算第l層個體中每個個體的擁擠度，選擇擁擠度距離大的個體作為下一代個體。

NSGA-II中交叉操作和變異操作為常見操作，在此不再贅述。需要指出的是，NSGA-II中選擇操作所用策略為錦標賽策略，描述如下：

(1) 確定每次選擇個體數(shù)量，在此為2個。

(2) 從種群中隨機選擇個體，選擇適應度值較優(yōu)個體作為后代個體。

(3) 重復上述步驟(2)，直到達到預定個體數(shù)量。

從上述步驟可以看出，若個體I為第1層Pareto前沿面上個體，且具有較優(yōu)多樣性指標，則其在下次被選中的概率依然很大。

圖1展示了采用錦標賽策略選擇父代個體重復個體數(shù)量統(tǒng)計數(shù)據(jù)。采用測試函數(shù)為ZDT2,種群數(shù)量為50，關于測試函數(shù)詳細信息在后續(xù)實驗部分詳細闡述。從上述統(tǒng)計數(shù)據(jù)中可以看出，每代都有平均15個個體的重復量，最高甚至達到32個重復個體。這些重復個體雖然攜帶了較優(yōu)的基因，可以為后代個體提供較好的搜索方向，但是也造成了后代多樣性較差的缺陷。

圖1 重復個體數(shù)量統(tǒng)計Figure 1 Statistics of repeated individuals

2 基于混合策略的NSGA-II

針對NSGA-II上述缺陷，筆者提出引入Lévy分布策略和三交叉父代策略。下面簡要介紹Lévy 分布策略，然后詳細介紹本文改進算法。

Lévy分布概率密度函數(shù)可形式化表示如下：

L(δ)～u=t-1-δ, 0<δ<2,

(2)

其簡化形式可表示如下：

L(δ)～φ·u/|v|1/δ，

(3)

其中，u和v是符合高斯分布的隨機數(shù),δ設置為1.5[13],φ定義如下：

(4)

圖2展示了Lévy分布所生成的100個采樣點取值。統(tǒng)計一下Lévy分布取值范圍，可發(fā)現(xiàn)，93%的取值落在[-1.8,1.8]內。從圖2可以看出，Lévy分布不僅可以使算法搜索聚焦于個體局部區(qū)域，也可使搜索跳出局部范圍，增加后代多樣性，避免陷入局部最優(yōu)。

圖2 Lévy分布采樣點Figure 2 Sampling points with Lévy distribution

設P1、P2、P3分別為錦標賽選擇策略所選出父代個體。原交叉算子可定義如下：

(5)

其中，beta是NSGA-II中定義參數(shù)，請參考文獻[4]。

改進后交叉算子可表示如下：

(6)

式中：L即為上文所述L分布函數(shù)。從上式可以看出，Lévy起到擾動作用，可以極大增加發(fā)現(xiàn)父代個體周圍潛在較優(yōu)個體的概率，同時引入P3則可進一步減小父代個體為同一個個體的概率。

基于混合策略的NSGA-II偽代碼如下。

1:初始化種群以及相關參數(shù)

2: While (是否滿足結束條件) do

3: 快速非支配排序

4: 采用錦標賽策略，從種群中選擇較優(yōu)個體

5: 采用式(6)對父代個體執(zhí)行交叉操作

6: 對個體執(zhí)行變異操作

7: 環(huán)境選擇，更新種群

8: End while

9:輸出種群

3 實驗結果及分析

3.1 參數(shù)設置

為綜合測試筆者所提算法性能，將HSNSGA-II傳統(tǒng)算法SPEA2[5]、PEASII[16]、NNIA[6]以及最近提出的算法MOEAIGDNS(multi-objective evolutionary algo-rithm based on enhanced IGD)[17]和ADCNSGA-II(NSGA-II with average distance clustering)[1]進行對比。注意，所有參數(shù)設置均按照原始參考文獻設置，有興趣讀者請參閱文獻[5-6,16-17]。實驗所用計算機為Inter Core i 5-2400 3.10 GHz CPU,6.00 GB內存，Windows7操作系統(tǒng)，運行環(huán)境為MATLAB7.9。每個算法獨立運行20次，對ZDT測試函數(shù)集最大迭代100次；對DTLZ1函數(shù)最大迭代700次；對DTLZ2、DTLZ4和DTLZ5函數(shù)迭代250次；對DTLZ3函數(shù)迭代1 000次；種群個體為50。

采用ZDT測試函數(shù)集[18]，這些函數(shù)具有凸、凹、連續(xù)、非連續(xù)和具有多重局部最優(yōu)等特點；評價指標采用IGD[19]。IGD是一個綜合指標，可同時評價算法收斂性和多樣性，其值越小表示算法性能越優(yōu),定義為：

(7)

式中：P*為目標空間真實Pareto前沿面上均勻分布點的集合；P為算法所求解集；dist(v,P)為點v和集合P中點的最小歐幾里得距離。

3.2 算法對比及分析

表1列出了筆者所提算法和對比算法在測試函數(shù)上的實驗結果，每個結果為算法運行20次的IGD的均值與方差，最優(yōu)結果用黑體顯示。從上述實驗結果可以看出，與傳統(tǒng)算法相比，HSNSGA-II在ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ2、DTLZ5上表現(xiàn)均較為突出，僅在DTLZ1、DTLZ3、DTLZ4上表現(xiàn)較差。相比于最近提出的算法MOEAIGDNS 和ADCNSGA-II，可以看出HSNSGA-II仍然具有較大的優(yōu)勢。因此，綜合上述實驗結果，可以看出筆者所提策略明顯地提高了NSGA-II的性能。

表1 實驗結果對比Table 1 Comparison of experimental results

圖3展示了HSNSGA-II和NSGA-II在ZDT3測試函數(shù)上的實驗結果對比。從圖3可以看出，HSNSGA-II可以搜索到右下角區(qū)域，而標準NSGA-II卻無法有效搜索到該區(qū)域，說明所提混合策略可以提高后代個體的多樣性并達到了預期，進一步驗證了筆者所提策略的有效性。

圖3 在ZDT3函數(shù)上實驗結果對比Figure 3 Comparison of experimental results on ZDT3

4 結論

NSGA-II是多目標優(yōu)化領域較為經(jīng)典算法，然而其采用的錦標賽選擇策略可導致重復選擇父代個體，進而導致后代多樣性受到影響。為解決此問題，筆者提出融合Lévy分布和三交叉父代的策略，第一個策略可有效強化搜索父代周圍潛在個體的能力，第二個策略可進一步降低所選父代為同一個個體的現(xiàn)象。通過實驗對比，驗證了筆者所提算法在多個測試集上的有效性。