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

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

0 引言

在實(shí)際工程應(yīng)用中，有許多目標(biāo)函數(shù)為2～3個(gè)的優(yōu)化問題[1-3]，且目標(biāo)函數(shù)間具有彼此沖突的特點(diǎn)，此類問題一般被認(rèn)為NP-Hard問題。傳統(tǒng)的方法，如線性規(guī)劃、梯度下降等，由于對(duì)問題特征具有較為嚴(yán)格的要求，導(dǎo)致解決此類問題時(shí)要付出極為昂貴的時(shí)間代價(jià)，甚至在有限時(shí)間內(nèi)無法獲得滿意解。進(jìn)化算法的出現(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作為多目標(biāo)優(yōu)化算法的典型代表，受到很多研究者的廣泛關(guān)注。根據(jù)研究角度不同，可將近些年研究成果作如下分類。

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

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

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

1 基本概念以及錦標(biāo)賽選擇策略

1.1 基本概念

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

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

(1)

s.t.X∈Ω,

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

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

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

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

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

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

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

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

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

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

(3) 重復(fù)上述步驟(2)，直到達(dá)到預(yù)定個(gè)體數(shù)量。

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

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

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

2 基于混合策略的NSGA-II

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

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

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

(2)

其簡(jiǎn)化形式可表示如下：

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

(3)

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

(4)

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

圖2 Lévy分布采樣點(diǎn)Figure 2 Sampling points with Lévy distribution

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

(5)

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

改進(jìn)后交叉算子可表示如下：

(6)

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

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

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

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

3: 快速非支配排序

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

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

6: 對(duì)個(gè)體執(zhí)行變異操作

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

8: End while

9:輸出種群

3 實(shí)驗(yàn)結(jié)果及分析

3.1 參數(shù)設(shè)置

為綜合測(cè)試筆者所提算法性能，將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]進(jìn)行對(duì)比。注意，所有參數(shù)設(shè)置均按照原始參考文獻(xiàn)設(shè)置，有興趣讀者請(qǐng)參閱文獻(xiàn)[5-6,16-17]。實(shí)驗(yàn)所用計(jì)算機(jī)為Inter Core i 5-2400 3.10 GHz CPU,6.00 GB內(nèi)存，Windows7操作系統(tǒng)，運(yùn)行環(huán)境為MATLAB7.9。每個(gè)算法獨(dú)立運(yùn)行20次，對(duì)ZDT測(cè)試函數(shù)集最大迭代100次；對(duì)DTLZ1函數(shù)最大迭代700次；對(duì)DTLZ2、DTLZ4和DTLZ5函數(shù)迭代250次；對(duì)DTLZ3函數(shù)迭代1 000次；種群個(gè)體為50。

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

(7)

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

3.2 算法對(duì)比及分析

表1列出了筆者所提算法和對(duì)比算法在測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果，每個(gè)結(jié)果為算法運(yùn)行20次的IGD的均值與方差，最優(yōu)結(jié)果用黑體顯示。從上述實(shí)驗(yàn)結(jié)果可以看出，與傳統(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)勢(shì)。因此，綜合上述實(shí)驗(yàn)結(jié)果，可以看出筆者所提策略明顯地提高了NSGA-II的性能。

表1 實(shí)驗(yàn)結(jié)果對(duì)比Table 1 Comparison of experimental results

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

圖3 在ZDT3函數(shù)上實(shí)驗(yàn)結(jié)果對(duì)比Figure 3 Comparison of experimental results on ZDT3

4 結(jié)論

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