基于改進(jìn)參考點(diǎn)的快速非支配排序遺傳算法研究

肖俊明, 劉凱松, 朱永勝, 謝 亮, 高洪洋

(中原工學(xué)院 電子信息學(xué)院, 河南 鄭州 450007)

近年來，高維多目標(biāo)優(yōu)化問題成為進(jìn)化計(jì)算的研究熱點(diǎn)及難點(diǎn)。為改善高維多目標(biāo)優(yōu)化問題，1980年， Wierzbicki A P最先提出了一種參考點(diǎn)方法，其目的是通過求解一個(gè)成就標(biāo)量問題得到一個(gè)最接近理想?yún)⒖键c(diǎn)的Pareto最優(yōu)解[1]。Deb K等在Evolutionary Multi-objective Optimization(EMO)中使用參考點(diǎn)方法，結(jié)合決策者偏好信息找到了一組Pareto最優(yōu)解集[2]。Mohammadi A等結(jié)合分解策略與參考點(diǎn)方法來搜索優(yōu)選區(qū)域[3]。Figueira J R等通過近似Pareto前沿的并行策略來生成參考點(diǎn)，使用多個(gè)參考點(diǎn)將目標(biāo)空間均勻地分割成不同的區(qū)域，對(duì)于每個(gè)參考點(diǎn)，獨(dú)立地找到一組近似有效的解，以便同時(shí)計(jì)算[4]。Wang R等提出了一種偏好啟發(fā)共同進(jìn)化算法(Preference-inspired Co-evolutionary Algorithm，PICEA)，以便在進(jìn)化過程中同時(shí)優(yōu)化候選解決方案和參考點(diǎn)，即通過較少的候選解決方案使參考點(diǎn)獲得更高的適應(yīng)度，通過滿足盡可能多的參考點(diǎn)使候選解決方案獲得適應(yīng)性[5]。Deb K等根據(jù)當(dāng)前種群獲得了覆蓋整個(gè)目標(biāo)空間的超平面，并在超平面上生成一系列分布均勻的參考點(diǎn)[6]。本文對(duì)參考點(diǎn)的策略進(jìn)行了改進(jìn)，并將其與快速非支配排序遺傳算法(NSGA-Ⅱ)相結(jié)合，形成了基于改進(jìn)參考點(diǎn)的快速非支配排序遺傳算法。

1 快速非支配排序遺傳算法

以最小化為例，假設(shè)一個(gè)具有m維目標(biāo)函數(shù)、n維決策變量的多目標(biāo)優(yōu)化問題，其表達(dá)式為[7]：

(1)

其中:x是決策變量，X是n維決策空間，F(xiàn)(x)為m維目標(biāo)函數(shù)向量。當(dāng)目標(biāo)維數(shù)m≥4時(shí)，F(xiàn)(x)即為高維多目標(biāo)函數(shù)，此問題即為高維多目標(biāo)優(yōu)化問題(Many-objective Optimization Problem)MaOP[8-9]。

Deb K等在非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm，NSGA)的基礎(chǔ)上提出了快速非支配排序遺傳算法(NSGA-Ⅱ)[10]。它的改進(jìn)主要包括三方面：①采用快速非支配排序的方法，使計(jì)算復(fù)雜度大大降低；②定義了擁擠度和擁擠度比較算子，替代了需要指定的共享半徑，使準(zhǔn)Pareto域中的個(gè)體能擴(kuò)展到整個(gè)Pareto域，且均勻分布，保持了種群的多樣性；③引入了精英策略，擴(kuò)大了采樣空間，防止了最佳個(gè)體的丟失，提高了算法的運(yùn)算速度和魯棒性。NSGA-Ⅱ在處理較少目標(biāo)(2個(gè)或3個(gè))時(shí)，優(yōu)化效果很好，但在優(yōu)化高維多目標(biāo)問題時(shí)，其優(yōu)化效果將大大降低。目前存在以下問題：①有限規(guī)模的最優(yōu)解無法近似高維目標(biāo)空間中的Pareto前沿，算法的復(fù)雜度隨目標(biāo)空間維度的增加而變大；②在解決高維多目標(biāo)問題時(shí)，算法的分布性能不佳；③優(yōu)化較多目標(biāo)時(shí)，非支配解的可視化十分困難。

2 參考點(diǎn)策略的改進(jìn)

Liu Y等提出了基于參考點(diǎn)的多目標(biāo)進(jìn)化算法(Many-objective Evolutionary optimization based on Reference Points，RPEA)。該算法重新定義了參考點(diǎn)的選擇方法，并加強(qiáng)了對(duì)Pareto前沿的選擇壓力，同時(shí)保持了解個(gè)體廣泛和均勻的分布[11]。在RPEA算法中，根據(jù)當(dāng)前群體生成了具有良好收斂性和分布性的一系列參考點(diǎn)，以指導(dǎo)個(gè)體進(jìn)化。此外，算法通過計(jì)算目標(biāo)空間中參考點(diǎn)和個(gè)體之間的Tchebychev距離[12]，獲得基于每個(gè)個(gè)體的評(píng)價(jià)，從而選擇優(yōu)良個(gè)體。RPEA的主要特征為：①提出的算法被推廣到一個(gè)共同的框架；②僅利用父代和子代群體中的非支配個(gè)體來產(chǎn)生參考點(diǎn)，從而進(jìn)一步增強(qiáng)這些參考點(diǎn)的性能；③采用基于Tchebychev距離的實(shí)現(xiàn)函數(shù)，以有效地評(píng)價(jià)候選解。其中，參考點(diǎn)選擇策略可表示為：

r=(f1(x)，…，fm(x)-ε，…，fM(x))(1≤m≤M)

(2)

改進(jìn)后的參考點(diǎn)選擇策略表示為：

(3)

RPEA是通過公式(2)在單一目標(biāo)函數(shù)上減小相應(yīng)的目標(biāo)值(ε是大于0的極小值)來生成參考點(diǎn)的，改進(jìn)后的算法按照公式(3)向兩個(gè)目標(biāo)函數(shù)同時(shí)減小相應(yīng)數(shù)值以生成參考點(diǎn)，這樣改進(jìn)后的參考點(diǎn)策略就進(jìn)一步加強(qiáng)了最優(yōu)前沿的選擇壓力。在選擇新個(gè)體時(shí)，刪除具有最小切比雪夫距離的個(gè)體，以避免重復(fù)選擇，同時(shí)刪除具有最小切比雪夫距離的參考點(diǎn)，以保證種群的多樣性。

3 基于改進(jìn)參考點(diǎn)的快速非支配排序算法

本文通過深入研究，將改進(jìn)的參考點(diǎn)策略與快速非支配排序遺傳算法(A Fast Elitist Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ)相結(jié)合，得到了一種可以解決高維多目標(biāo)問題的基于改進(jìn)參考點(diǎn)的快速非支配排序算法(RP-NSGA-Ⅱ)。

3.1 算法應(yīng)用的操作

(1)初始化，由每一個(gè)向量(稱為染色體或基因)組成問題的候選解。問題中的每個(gè)參數(shù)都有一個(gè)變量范圍，且不能為負(fù)。初始化時(shí)應(yīng)盡可能地覆蓋全部的搜索范圍。

(2)交叉操作，通過使用模擬二進(jìn)制交叉算子(SBX)進(jìn)行交叉操作。SBX 是一種二進(jìn)制交叉算子，用來模擬在自然界中觀察到的染色體交叉過程。兩條父代染色體交叉生成兩條子代染色體，保存于父代中染色體的相關(guān)信息在子代染色體中會(huì)得到保護(hù)。數(shù)學(xué)描述如下：

(4)

其中：ci,k表示含有第k個(gè)基因位的第i個(gè)子代；pi,k表示被選擇的父代個(gè)體；βk(≥0)是具有一定概率的隨機(jī)數(shù)。

(5)

公式(5)中β分布可以從(0,1)之間的均勻采樣隨機(jī)數(shù)u中獲得。ηc為交叉點(diǎn)的分布指數(shù)(DIC)，是非負(fù)實(shí)數(shù)，當(dāng)ηc的值比較大時(shí)，子代個(gè)體與父代個(gè)體相鄰的概率就比較大；而當(dāng)ηc的值比較小時(shí)，子代個(gè)體與父代個(gè)體之間的距離就比較遠(yuǎn)。參數(shù)ηc可以根據(jù)實(shí)際情況進(jìn)行自定義。

進(jìn)化過程前期，SBX可以促使算法探索未知空間信息，到進(jìn)化過程后期，算法可以利用個(gè)體信息逐漸收斂。

(3)變異操作，采用多項(xiàng)式變異算子(PM)進(jìn)行變異操作，以防止算法陷入局部最優(yōu)。其數(shù)學(xué)描述如下式：

(6)

(7)

其中：rk是(0,1)之間的均勻采樣隨機(jī)數(shù)；ηm是自定義參數(shù)，稱為變異分布指數(shù) (DIM)。

(4)精英策略，將子代個(gè)體集合與父代個(gè)體集合相結(jié)合，生成下一代的個(gè)體。若父代和子代中最好的個(gè)體都加入過渡個(gè)體集合，則精英策略就可得到保證。根據(jù)非支配排序?qū)^渡個(gè)體集合進(jìn)行分類，隨后每個(gè)最低級(jí)別的非支配集合都會(huì)填補(bǔ)到子代中，直到種群規(guī)模超過目前的個(gè)體規(guī)模。若種群規(guī)模大于N，則對(duì)最后加入子代種群的非支配集進(jìn)行擁擠距離排序，并從中選擇具有較大擁擠距離的個(gè)體，使種群規(guī)模維持在N。

(5)個(gè)體選擇，根據(jù)生成的參考點(diǎn)指導(dǎo)解個(gè)體的進(jìn)化過程，并選擇最優(yōu)解。

3.2 算法流程

RP-NSGA-Ⅱ算法流程見圖1。

圖1 算法流程圖

主要算法步驟如下：

步驟1：初始化種群，設(shè)置種群大小、迭代次數(shù)等參數(shù)。

步驟2：父代種群P通過交叉、變異操作，生成相同種群大小的子代種群P′。

步驟3：對(duì)集合(P+P′)進(jìn)行非支配操作，形成非支配解集Q。

步驟4：集合Q中的每個(gè)個(gè)體根據(jù)公式(3)生成參考點(diǎn)，將生成的參考點(diǎn)進(jìn)行非支配排序，非支配個(gè)體為參考點(diǎn)集合R。

步驟5：根據(jù)切比雪夫距離公式計(jì)算個(gè)體與參考點(diǎn)之間的距離，選擇具有最小切比雪夫距離的個(gè)體，形成子代種群P(t+1)。

步驟6：判斷是否滿足終止條件。若是，則進(jìn)入步驟7；否則，返回步驟2。

步驟7：從子代種群中選擇非支配解并輸出。

4 實(shí)驗(yàn)分析

DTLZ是一個(gè)連續(xù)的問題函數(shù)集，可以應(yīng)用到任意數(shù)量的目標(biāo)和決策變量的問題中(M是目標(biāo)空間維數(shù)，n是決策空間維數(shù))，并且通常將其用于多目標(biāo)優(yōu)化。DTLZ函數(shù)集由具有多種特性的多個(gè)問題組成，例如線性，凹面，偏置或退化的Pareto前沿。DTLZ函數(shù)集的特性見表1。

本文選擇被廣泛使用的Inverted Generation Distance(IGD)指標(biāo)來測(cè)試改進(jìn)后算法的性能。IGD可以測(cè)量解集的收斂性和多樣性，IGD的值越小，算法的性能越好。測(cè)試中，將RP-NSGA-Ⅱ與經(jīng)典NSGA-Ⅱ，具有參考點(diǎn)的RPEA和具有代表性的MOEA/D進(jìn)行性能對(duì)比實(shí)驗(yàn)。為保證對(duì)比實(shí)驗(yàn)的公平性，四種算法均采用相同的參數(shù)設(shè)置：種群大小為100，目標(biāo)數(shù)目為6，變量x維數(shù)為15(DTLZ1中維數(shù)為9)，迭代次數(shù)為1 000。實(shí)驗(yàn)結(jié)果均為各算法獨(dú)立運(yùn)行30次所對(duì)應(yīng)的平均值和標(biāo)準(zhǔn)差，其中最優(yōu)結(jié)果均加粗表示。實(shí)驗(yàn)結(jié)果如表2所示。

表2顯示，MOEA/D在解決DTLZ1時(shí)表現(xiàn)最佳，這是因?yàn)镈TLZ1具有線性和大量局部最優(yōu)的多模態(tài)問題，問題的目標(biāo)值范圍遠(yuǎn)大于其Pareto前沿，而MOEA/D避免了在其他算法中標(biāo)準(zhǔn)化程序容易將原始目標(biāo)轉(zhuǎn)化為錯(cuò)誤尺度的問題。而DTLZ2問題比較容易解決，從實(shí)驗(yàn)結(jié)果可以看出RP-NSGA-Ⅱ具有更好的性能。對(duì)于DTLZ3，MOEA/D具有最佳性能。對(duì)于DTLZ4，RPEA顯著優(yōu)于其他算法，表明該算法具有很強(qiáng)的解決不規(guī)則Pareto陣線問題的能力。對(duì)于DTLZ5和DTLZ6，RP-NSGA-Ⅱ在解決Pareto退化問題時(shí)具有最佳性能。

分析表2中的數(shù)據(jù)，RP-NSGA-Ⅱ算法的優(yōu)化效果遠(yuǎn)遠(yuǎn)優(yōu)于NSGA-Ⅱ算法。RP-NSGA-Ⅱ在處理Pareto問題時(shí)更優(yōu)秀，但是在處理具有多模態(tài)問題時(shí)，性能略有不足。綜上所述，本文提出的基于改進(jìn)參考點(diǎn)的非支配排序算法在解決高維多目標(biāo)問題時(shí)具有良好的收斂性和穩(wěn)定性。

表1 DTLZ測(cè)試函數(shù)集

表2 DTLZ測(cè)試結(jié)果

5 結(jié) 語

本文通過對(duì)參考點(diǎn)策略的深入研究，對(duì)參考點(diǎn)策略提出了改進(jìn)，并將改進(jìn)后的參考點(diǎn)策略與NSGA-Ⅱ算法相結(jié)合，形成了基于改進(jìn)參考點(diǎn)的快速非支配排序算法，有效地提高了算法的選擇壓力。DTLZ函數(shù)測(cè)試實(shí)驗(yàn)表明，RP-NSGA-Ⅱ能夠有效地取得更接近Pareto前沿的最優(yōu)解，適用于解決高維多目標(biāo)問題。未來的研究方向?qū)⒓杏趦蓚€(gè)方面：一是將參考點(diǎn)策略與其他算法相結(jié)合，構(gòu)成在優(yōu)化高維多目標(biāo)問題方面具有更好效果的算法；二是將算法應(yīng)用到實(shí)際工程中去。

參考文獻(xiàn)：

[1] Wierzbicki A P. The use of reference objectives in multiobjective optimization[M].Springer Berlin Heidelberg: Multiple Criteria Decision Making Theory and Application, 1980:468-486.

[2] Deb K, Sundar J, Chaudhuri S, et al. Reference point based multi-objective optimization using evolutionary algorithms[C]//Conference on Genetic and Evolutionary Computation. New York: ACM, 2006:635-642.

[3] Mohammadi A, Omidvar M N, Li X. Reference point based multi-objective optimization through decomposition[C]//Piscataway, NJ: IEEE, 2012:1-8.

[4] Figueira J R, Liefooghe A, Talbi E G, et al. A parallel multiple reference point approach for multi-objective optimization[J]. European Journal of Operational Research, 2010, 205(2):390-400.

[5] Wang R, Purshouse R C, Fleming P J. Preference-inspired coevolutionary algorithms for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(4):474-494.

[6] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: Solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4):577-601.

[7] Zhang Q, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6):712-731.

[8] 孔維健，丁進(jìn)良，柴天佑.高維多目標(biāo)進(jìn)化算法研究綜述[J].控制與決策, 2010,25(3):321-326.

[9] Farina M, Amato P. On the optimal solution definition for many-criteria optimization problems[C]//Piscataway, NJ: IEEE, 2002:233-238.

[10] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation,2002, 6(2): 182-197.

[11] Liu Y, Gong D, Sun X, et al. Many-objective evolutionary optimization based on reference points[J]. Applied Soft Computing,2017, 50:344-355.

[12] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation,2002, 6(2):182-197.