王啟翔，許 峰

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001）

2007年，Zhang[1]提出了基于多目標(biāo)分解的MOEA/D，但是隨著目標(biāo)維數(shù)的上升，全局搜索能力下降，容易陷入局部最優(yōu)。為了改善MOEA/D 算法，許多學(xué)者做了大量研究、改進(jìn)工作。2018年，Ryoji[2]分析了MOEA/D 的控制參數(shù)；2020年，Dong[3]提出了自適應(yīng)權(quán)重 MOEA/D；Zhang[4]提出了基于信息反饋的MOEA/D；Wang[5]提出了自適應(yīng)演化策略MOEA/D；Zhang[6]提出了多階段動(dòng)態(tài)演化MOEA/D；Fan[7]提出了基于角度約束的MOEA/D。

2009年，張敏[8]提出了一種基于正態(tài)分布交叉的MOEA算法；2019年，Zhang[9]將差分算子引入 MOEA 算法，提出了一種雙變量控制MOEA/D 算法。本文在上述工作的基礎(chǔ)上，將正態(tài)分布交叉算子和差分進(jìn)化算子引入MOEA/D，構(gòu)成協(xié)同進(jìn)化，并用標(biāo)準(zhǔn)多目標(biāo)優(yōu)化測(cè)驗(yàn)函數(shù)對(duì)改進(jìn)算法進(jìn)行了性能測(cè)試，驗(yàn)證了新算法的有效性。

1 MOEA/D 算法

MOEA/D 通過預(yù)先設(shè)定的權(quán)重向量將復(fù)雜的多目標(biāo)優(yōu)化問題轉(zhuǎn)變?yōu)橐幌盗械膯文繕?biāo)問題，每一個(gè)子問題使用與其相鄰的子問題提供的參考信息，相互協(xié)同進(jìn)化，主要用于求解MaOP。該算法采用Tchebycheff 分解法，MOEA/D 的基本步驟如下：

（1）N：子問題的個(gè)數(shù)；

（2）N 個(gè)均勻分布的權(quán)重向量：λ1，λ2，...，λN；

（3）T：每個(gè)權(quán)重向量鄰居的個(gè)數(shù)。

步驟1 初始化：

（1）設(shè)EP=Φ。

（2）計(jì)算任意兩個(gè)權(quán)重向量之間的歐幾里德距離，為每個(gè)權(quán)重向量選出最近的T 個(gè)權(quán)向量作為它的鄰域。即 λi1，λi2，...，λiT是離 λi最近的 T 個(gè)權(quán)重向量，i=1，2，…，N，令 B（i）={i1，i2，…，iT}。

（3） 根據(jù)權(quán)重向量來產(chǎn)生初始種群 x1，x2，…，xN。

步驟2 更新：

對(duì) i=1，2，…，N：

（1）從 B（i）中隨機(jī)選取兩個(gè)序號(hào) k，l，對(duì) xk和 xl執(zhí)行SBX 算子產(chǎn)生一個(gè)新的解y。

（4）更新EP：剔除EP 中受y 支配所有的向量，并且在EP 中向量都不支配y 時(shí)，令EP=EP∪{f（y）}。

步驟3 終止條件：如果滿足終止條件，則停止并輸出EP，否則轉(zhuǎn)步驟2。

2 交叉算子

交叉算子是進(jìn)化算法領(lǐng)域中最為關(guān)鍵的存在，交叉算子的優(yōu)劣往往能夠決定算法的優(yōu)劣。最經(jīng)常用的交叉算子就是Deb 提出的模擬二進(jìn)制交叉算子，其定義為：對(duì)兩個(gè)父代個(gè)體 X1和 X2，如下操作得到子代個(gè)體

其中，j=1，2，…，n，α 是隨機(jī)變量，每一維上都要重新產(chǎn)生，方式如下：

μ 是分布在（0，1）上的隨機(jī)數(shù)；η 是交叉參數(shù)。

正態(tài)分布交叉算子（NDX）是張敏[8]等在2009年提出的，就是將正態(tài)分布引入SBX 算子中，其定義為：對(duì)兩個(gè)父代個(gè)體 X1和 X2，如下操作得到子代個(gè)體

其中，μj是（0，1）區(qū)間上的隨機(jī)數(shù)。

在設(shè)計(jì)NDX 的時(shí)候，引入重組操作，增強(qiáng)了NDX 算子空間搜索能力。NDX 相較SBX 的優(yōu)勢(shì)在于對(duì)大量的個(gè)體進(jìn)行重組操作，能夠擴(kuò)大種群的多樣性，提供更大的搜索范圍。

DE/best/2 引入了最優(yōu)解個(gè)體引導(dǎo)搜索方向，變異個(gè)體的生成受到最優(yōu)解個(gè)體的制約，搜索范圍將圍繞最優(yōu)解展開，因而使得算法的收斂速度大大增加，趨向最優(yōu)解的能力提高，然而若當(dāng)前最優(yōu)解個(gè)體為局部極值點(diǎn)，則會(huì)因?yàn)榉N群多樣性降低而增大陷入局部最優(yōu)解的可能性。

3 協(xié)同進(jìn)化策略

在多目標(biāo)進(jìn)化算法中，如果一個(gè)算法能有一個(gè)優(yōu)秀的產(chǎn)生子種群的策略，那么這個(gè)算法的性能必定會(huì)大大提高。MOEA/D 利用模擬二進(jìn)制交叉算子SBX 來生成子代，并且取得比較好的效果，但是該算法的搜索能力較弱，生成的種群多樣性較差，且SBX 算子易產(chǎn)生劣質(zhì)子代等等。針對(duì)這些缺陷，本文利用NDX 正態(tài)分布交叉算子和DE/best/2 差分進(jìn)化算子來構(gòu)建協(xié)同進(jìn)化策略，替換SBX 算子，讓NDX 算子和DE/best/2 算子共同生成子代。

首先NDX 可以對(duì)子問題鄰域內(nèi)大量的個(gè)體進(jìn)行重組操作，使父代個(gè)體更具多樣性，從而能夠產(chǎn)生多樣性的個(gè)體，擴(kuò)大種群多樣性，提供更大的搜索范圍；其次，從NDX 產(chǎn)生的種群中，執(zhí)行DE/best/2。

4 協(xié)同進(jìn)化策略改進(jìn)的MOEA/D 算法

步驟1 初始化參數(shù)。生成一組分布均勻的權(quán)向量λ1，λ2，……，λN，計(jì)算子問題鄰域 B（i）={i1，i2，…，iT}，根據(jù)權(quán)向量生成一個(gè)初始隨機(jī)種群 P＝{x1，x2，…，xN}，取每一個(gè)目標(biāo)值的最小值作為參考點(diǎn)

步驟2 種群更新。

對(duì) i=1，2，…，N

（1） 對(duì) B（i）中所有個(gè)體，兩兩執(zhí)行 NDX 算子，得到新的子代種群記為Q（i）。

（2） 將 B（i）和 Q（i）合并，記為 Rt。

（3）從Rt選擇合適的個(gè)體，執(zhí)行DE/best/2 算子，生成新個(gè)體y。

（4）若zj

步驟3 更新EP。如果新生成的解y 不被EP 中的任何解所支配，并刪除由y 主導(dǎo)的解。

步驟4 終止條件：如果滿足終止條件，則停止并輸出EP。否則轉(zhuǎn)到步驟2。

5 數(shù)值實(shí)驗(yàn)與性能測(cè)試

為了評(píng)測(cè)改進(jìn)算法的收斂性和分布性，選取下面兩個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行數(shù)值計(jì)算：

其中，-4≤x1，x2，x3≤4。

其中，-5≤x1，x2，x3≤5。

首先進(jìn)行非支配解個(gè)數(shù)的生成比例實(shí)驗(yàn)，這是評(píng)測(cè)算法收斂性的一種直觀方法。下面給出了非支配解不同生成比例時(shí)F1的Pareto 最優(yōu)前沿。

圖1 40%非支配個(gè)體

圖2 60%非支配個(gè)體

上述圖1-圖4 圖形顯示，對(duì)于固定的種群規(guī)模，隨著非支配解比例的增加，算法較好地逼近了理論上的Pareto 最優(yōu)前沿。這在一定程度上表明，改進(jìn)算法具有較好的收斂性。

下面再將改進(jìn)算法與標(biāo)準(zhǔn)MOEA/D 算法進(jìn)行比較。下面給出兩種算法的對(duì)比Pareto 最優(yōu)前沿。

從上述圖5-圖6 圖形可以清楚地看出，改進(jìn)的MOEA/D 與標(biāo)準(zhǔn)的MOEA/D 相比，有較好的分布性和均勻性。

圖3 80%非支配個(gè)體

圖4 90%非支配個(gè)體

圖5 F2MOEA/D 的Pateto 最優(yōu)前沿

6 結(jié)論

圖6 F2 改進(jìn)MOEA/D 的Pateto 最優(yōu)前沿

受以往工作的啟發(fā)，本文將正態(tài)分布交叉算子和差分進(jìn)化算子引入MOEA/D，數(shù)值實(shí)驗(yàn)表明，改進(jìn)后的算法維持了MOEA/D 的良好收斂性，而且較MOEA/D 在分布性和均勻性方面有了一定程度的改進(jìn)。不過，這不可避免地增加了算法的復(fù)雜度。