基于維度擾動的快速非支配排序遺傳算法II

張茂清，李東洋，胡 博，汪 鐳，崔志華，郭為安

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

0 引言

多目標(biāo)優(yōu)化問題是指目標(biāo)函數(shù)數(shù)量為2～3個的優(yōu)化問題[1-3]。一般情況下，多目標(biāo)優(yōu)化問題不同目標(biāo)之間具有相互沖突的特點(diǎn)，即一個目標(biāo)性能增加會導(dǎo)致另外一個目標(biāo)性能降低。為求解此類優(yōu)化問題，許多學(xué)者提出了有效的求解算法，如NSGA-II[4]、SPEA2[5]、PEASII[6]以及最近提出的MOEAIGDNS[7]等。NSGA-II[4]是Deb等于2002年提出的算法。由于其在多目標(biāo)優(yōu)化問題上較優(yōu)的求解性能引起了廣大研究者關(guān)注，并被應(yīng)用到許多實(shí)際工程優(yōu)化問題中。根據(jù)不同研究角度，可將近些年對NSGA-II的研究做如下分類。

優(yōu)化NSGA-II中支配關(guān)系，進(jìn)一步拓展算法求解問題范圍。針對實(shí)際工程領(lǐng)域中復(fù)雜非線性多目標(biāo)優(yōu)化問題，賴文星等[8]發(fā)現(xiàn)NSGA-II無法有效識別偽非支配解。為解決此類問題，賴文星等[8]采用快速支配強(qiáng)度排序法構(gòu)造非支配集,引入基于方差的擁擠距離公式,并通過自適應(yīng)精英保留策略動態(tài)調(diào)整精英保留規(guī)模。為在理論上解決NSGA-II中Pareto支配在高維多目標(biāo)優(yōu)化問題上無法區(qū)分有效解的問題，Yang等[9]提出利用基于網(wǎng)格的支配方法來區(qū)分不同個體，并利用網(wǎng)格產(chǎn)生待交叉父代個體。同樣為解決此類問題，Zhang等[10]則提出基于分解的進(jìn)化算法，即將多目標(biāo)優(yōu)化問題分解為多個單目標(biāo)優(yōu)化問題，有效避免了多目標(biāo)優(yōu)化問題中支配關(guān)系，提升了算法的收斂性能。

針對實(shí)際工程應(yīng)用問題特點(diǎn)，改善算法適用性，郝志寬等[11]針對車輛懸架系統(tǒng)中多目標(biāo)優(yōu)化問題特點(diǎn)，提出引入精英保持策略,去除重復(fù)個體,減少變量重復(fù)性,有效提高了算法的效率。面向特定區(qū)域部署的臨近空間通信網(wǎng)絡(luò)需要兼顧考慮資源分配、覆蓋率及載荷功率等多個因素，為了針對性優(yōu)化此類復(fù)雜問題，唐樹祝等[12]將動態(tài)反向?qū)W習(xí)機(jī)制和差分局部變異算子引入NSGA-II，為網(wǎng)絡(luò)實(shí)際部署提供了參考。為應(yīng)對跨區(qū)域突發(fā)事件過程中受災(zāi)點(diǎn)服務(wù)差異化需求問題,宋艷等[13]通過設(shè)計分段染色體編碼方式改進(jìn)NSGA-Ⅱ算法，提升運(yùn)算效率，并且有效地解決了多目標(biāo)選址決策問題。

雖然NSGA-II在理論以及應(yīng)用方面[14]已有廣泛研究，但其采用的錦標(biāo)賽選擇策略(tournament selection)會產(chǎn)生大量重復(fù)個體，從而導(dǎo)致后代種群多樣性受到影響。針對此類問題，筆者設(shè)計具有維度擾動策略的NSGA-II(non-dominated sorting genetic algorithm II based on dimensionality perturbation, DPNSGA-II)，該算法通過采用對部分維度進(jìn)行擾動的方法消除重復(fù)個體，從而有效地提高了算法的整體性能。

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

1.1 基本概念

筆者考慮如下多目標(biāo)優(yōu)化問題[15]：

(1)

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

定義3：pareto最優(yōu)解集在目標(biāo)空間上對應(yīng)點(diǎn)集稱pareto前沿面(paretofront)。

1.2 錦標(biāo)賽選擇策略以及分析

NSGA-II[4]是多目標(biāo)優(yōu)化算法中經(jīng)典的算法,其涉及快速非支配排序、錦標(biāo)賽選擇策略(tournament selection)、交叉算子、變異算子以及擁擠度距離等多種策略。NSGA-II中種群個體間進(jìn)化壓力以及多樣性保持策略主要依賴快速非支配排序以及擁擠度距離的方法。錦標(biāo)賽選擇策略是NSGA-II算法中用于選擇待交叉父代個體的主要方法，如圖1所示。首先從種群中以等概率選擇個體，然后從所選個體中選擇最優(yōu)個體作為父代個體，按照上述方法多次選擇即可產(chǎn)生多個交叉父代。從上述過程可看出，若個體Ii為種群中第一層非支配個體，則其有很大概率在多次選擇較優(yōu)個體時被再次選中，從而導(dǎo)致出現(xiàn)多個重復(fù)個體現(xiàn)象。

圖1 錦標(biāo)賽選擇策略說明

圖2為運(yùn)行NSGA-II 算法時，運(yùn)用錦標(biāo)賽選擇策略單個個體每代最大重復(fù)次數(shù)統(tǒng)計，圖3為算法運(yùn)行到70代時運(yùn)用錦標(biāo)賽選擇策略所產(chǎn)生重復(fù)個體數(shù)量統(tǒng)計，其中運(yùn)行條件為種群個體數(shù)量為100，算法運(yùn)行80代，測試函數(shù)為ZDT1(請見實(shí)驗部分)。從圖2可以看出，算法NSGA-II計算過程中每代都會出現(xiàn)每個個體5次的重復(fù)次數(shù)，最大出現(xiàn)10次重復(fù)。從圖3可看出，就某一代重復(fù)個體而言，較優(yōu)個體出現(xiàn)4次，甚至最高出現(xiàn)10次重復(fù)次數(shù)。若每個個體均按照上述數(shù)量重復(fù)，則可導(dǎo)致后代個體多樣性變差以及算法整體性能降低。

圖2 每代重復(fù)個體統(tǒng)計

圖3 第70代重復(fù)個體數(shù)量統(tǒng)計

2 維度擾動策略

(2)

(3)

(4)

圖4 維度擾動示意圖

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

為驗證筆者所提算法性能，本部分實(shí)驗為兩小部分：

(1)第一部分驗證筆者所提算法參數(shù)λ取1.0E-02、1.0E-03、1.0E-04、1.0E-05對算法性能的影響；

(2)第二部分將筆者所提基于維度擾動的NSGA-II與傳統(tǒng)算法SPEA2[5]、PEASII[6]以及最近提出的算法MOEAIGDNS[7]做對比。表1列出了上述不同算法運(yùn)行所需參數(shù)。其中pc為交叉概率；pm表示變異概率；D為測試函數(shù)變量維度。div為每個目標(biāo)分量個數(shù)。注意，所有參數(shù)設(shè)置均按照原始參考文獻(xiàn)設(shè)置，有興趣讀者請參閱文獻(xiàn)[5-7]。

表1 算法參數(shù)說明

(3)展示種群多樣性指標(biāo)與個體進(jìn)化代數(shù)之間的關(guān)系圖，并進(jìn)一步分析驗證本文前述維度擾動策略所起作用。

為了綜合測試算法性能，筆者采用ZDT測試函數(shù)集[16]，如表2所示。ZDT測試函數(shù)集由Zitzler和Deb在2000年提出，這些函數(shù)具有凸、凹、連續(xù)、非連續(xù)和具有多重局部最優(yōu)等特點(diǎn)，評價指標(biāo)采用IGD[17]。

實(shí)驗所用計算機(jī)為Inter Core i 5-2400 3.10 GHz CPU, 6.00 GB內(nèi)存，Windows7操作系統(tǒng)，運(yùn)行環(huán)境為Matlab7.9。每個算法獨(dú)立運(yùn)行20次，算法最大迭代100次，種群個體為50。

3.1 參數(shù).對算法影響

表2所示為不同λ取值對本文算法的影響，其中每個取值為算法獨(dú)立運(yùn)行20次IGD均值。最后一行為Friedman檢驗結(jié)果ranking值(排序值)，值越小表示算法性能越優(yōu)，F(xiàn)riedman檢驗是對每個算法運(yùn)行20次的IGD均值計算得出的，最優(yōu)值用黑體顯示。對比算法的方式為首先通過比較不同算法在各個測試函數(shù)集上的IGD均值以及在整個測試函數(shù)上占優(yōu)的總數(shù)，然后進(jìn)一步比較Friedman檢驗結(jié)果，綜合以上方法得出最優(yōu)算法。

表2 實(shí)驗算法所求平均IGD對比

從表2可看出，λ=1.0E-04時分別在ZDT1、ZDT2、ZDT4表現(xiàn)較優(yōu)，在ZDT2和ZDT6表現(xiàn)略差。從Friedman檢驗結(jié)果來看，λ=1.0E-04時具有最小檢驗值。因此，綜合而言，當(dāng)λ=1.0E-04時本文算法具有較優(yōu)性能。下面實(shí)驗將采用λ=1.0E-04作為算法DPNSGA-II參數(shù)。

3.2 與現(xiàn)有算法對比

表3列出了筆者所提算法與NSGA-II、PEASII、SPEA2、MOEAIGDNS對比結(jié)果，其中“均值”表示算法運(yùn)行20次的IGD平均值，“方差”表示算法20次求解IGD結(jié)果“方差”。最后一行為Friedman檢驗結(jié)果ranking值，其由在每個測試函數(shù)上對每個算法運(yùn)行20次的IGD均值計算得出。

從表3可以看出，與NSGA-II相比，筆者所提算法在ZDT1、ZDT2、ZDT3、ZDT4上均表現(xiàn)較優(yōu)，說明筆者所提基于維度擾動的策略有效地改善了算法性能。與其他算法相比，筆者所提算法在ZDT3上超過SPEA2性能。就Friedman測試結(jié)果而言，筆者所提算法具有較小ranking值，說明本文算法整體性能較優(yōu)。

圖5展示算法DPNSGA-II、NSGA-II以及真實(shí)前沿面在不同測試函數(shù)上的對比效果。從圖5可以看出，在收斂性方面，算法DPNSGA-II與NSGA-II在ZDT1測試函數(shù)上有明顯差距；在ZDT2上，算法NSGA-II所求結(jié)果均勻性稍差于DPNSGA-II。在ZDT3和ZDT6測試函數(shù)上可明顯看出，NSGA-II算法在某些點(diǎn)上存在明顯偏離真實(shí)pareto前沿面(true pareto front)的個體。在ZDT4上的兩個算法性能表現(xiàn)可以充分說明改進(jìn)算法DPNSGA-II有效地改善了NSGA-II 收斂性，提高了算法的整體性能。

表3 不同算法獲得的IGD值

圖5 不同算法pareto前沿面對比

3.3 種群多樣性指標(biāo)分析

圖6展示了DPNSGA-II和NSGA-II算法在運(yùn)行過程中種群多樣性變化趨勢，其中橫坐標(biāo)表示算法評價次數(shù)(即種群個體與算法運(yùn)行代數(shù)的乘積，此方式相比于以代數(shù)更加精細(xì)反應(yīng)種群多樣性的變化)，縱坐標(biāo)表示多樣性指標(biāo)，所用測試函數(shù)為ZDT1。

圖6 種群多樣性隨代數(shù)變化趨勢說明

根據(jù)第二部分介紹的擾動策略，該方法可以有效減少重復(fù)個體數(shù)量。從圖6種群多樣性變化趨勢對比可以看出，筆者提出的DPNSGA-II 算法在運(yùn)行初期相對于NSGA-II多樣性較差，其原因是在初始化種群時，種群個體間本身具有較大距離，且分布相對均勻，此時筆者所提維度擾動策略只能在個體附近產(chǎn)生擾動，并未產(chǎn)生明顯效果。隨著種群個體不斷進(jìn)化，在算法運(yùn)行到1 000次評價時，DPNSGA-II對應(yīng)種群多樣性明顯優(yōu)于NSGA-II對應(yīng)種群性能，并一直保持到算法運(yùn)行結(jié)束。在1 000次評價之后，個體不斷逼近真實(shí)pareto前沿面，同時，個體間距離不斷縮小，此時維度擾動策略產(chǎn)生作用，使得種群多樣性保持在一定程度，有利于種群向更優(yōu)的方向進(jìn)化。

基于以上討論，綜合比較而言，筆者所提算法DPNSGA-II通過降低算法重復(fù)個體的方式，有效改進(jìn)了算法整體性能，證明筆者所提改進(jìn)策略的有效性。

4 結(jié)論

錦標(biāo)賽選擇策略是NSGA-II用于選擇產(chǎn)生后代的策略，由于其固有缺陷導(dǎo)致產(chǎn)生大量重復(fù)個體。為了解決此問題，筆者提出了基于維度擾動的策略，即通過以當(dāng)前父代位置為期望，融入方差參數(shù)的正態(tài)分布函數(shù)進(jìn)行擾動，以此消除重復(fù)個體現(xiàn)象。通過實(shí)驗數(shù)據(jù)可以說明，提出的基于維度擾動的策略可以有效地提升算法性能，達(dá)到了預(yù)期的效果。后期研究工作將專注于NSGA-II算法性能的進(jìn)一步提升。