采用個體進化狀態判定策略的分解類多目標進化算法

李浩君，劉中鋒，王萬良，張 征，張鵬威

1(浙江工業大學 教育科學與技術學院，杭州 310023) 2(浙江工業大學 計算機科學與技術學院，杭州 310023) E-mail：zgdlhj@zjut.edu.cn

1 引 言

在很多現實應用中，多目標問題(MOP)需要同時優化多個目標[1]，這些目標通常是彼此沖突的，沒有一個單一解可以同時優化所有目標.Pareto最優解是不同目標之間最好的折中候選解，多目標進化算法(MOEAs)能夠在單次運行中發現一組有代表性的Pareto最優解，能夠有效解決MOP問題，因此很多MOEAs算法[2-4]已經被提出.

大多數現有MOEAs算法將MOP問題作為一個整體，利用快速非支配排序方法進行優化[5,6].這些MOEAs算法具有較好的收斂性，但分布性較差，不能較好地平衡全局探索和局部開發，易收斂到局部Pareto前沿[7].一個MOP問題的Pareto最優解可能是一個標量問題的最優解，因此可以將MOP問題分解為多個標量子問題.Zhang和Li[8]提出了基于分解方法的分解類多目標進化算法(MOEA/D)，MOEA/D算法將MOP問題分解為N個標量子問題，每一個子問題通過使用其鄰域信息進行優化，每一個子問題在當前種群中都有其目前發現的最優解，所有子問題的最優解組成MOP問題的Pareto最優解集，已經證明MOEA/D算法具有更低的計算復雜度[9-12].

將差分進化算法的多種變異算子應用于MOEA/D是分解類多目標優化領域的一個方向.Li和Zhang[13]提出分解類多目標差分進化算法(MOEA/D_DE)，MOEA/D_DE算法將差分進化算法的一組變異算子引入MOEA/D算法框架，提高了算法的收斂性和多樣性；目前已經有很多研究致力于通過變異算子提高MOEAs算法性能[14-16]，但已有的研究主要采用隨機選擇機制選擇變異算子，不能保證優質解的產生.為了解決這一問題，劉志軍等[17]提出采用概率匹配策略自適應地為多目標差分進化算法選擇變異算子，概率匹配策略將變異算子所生成成功進入下一代解的個數作為歷史信息，并將歷史信息轉化為變異算子被選擇的概率，從而為個體選擇具有較高生成成功子代概率的變異算子.Li等[18]提出老虎機策略用于自適應地為算法選擇變異算子，該策略將進化過程中適應度變化的歷史信息，作為變異算子被選擇的依據.

MOEA/D算法中變異算子的選擇，參考生成成功子代的歷史信息，可以提高特定階段內較好變異算子的選擇概率，能夠在一定程度上提高算法的性能.但是歷史信息不能完全反映個體的當前進化狀態，利用歷史信息為個體選擇變異算子，不能保證算法獲得真實的Pareto最優解集.為了克服已有變異算子選擇策略對個體當前進化狀態信息利用不足的問題，本文提出了采用個體進化狀態判定策略的分解類多目標進化算法(MOEA/D_PE).MOEA/D_PE算法采用個體進化狀態判定策略提高算法選擇合適變異算子的能力，從而保證算法具有較好的收斂性和多樣性.個體進化狀態判定策略是：首先，根據個體與其鄰域內其它個體標量子問題函數值的大小關系，確定個體屬于進化程度較好、較差或一般的概率，從而判定個體的進化狀態；然后，根據個體進化狀態為個體選擇合適的變異算子.個體進化狀態判定策略，充分考慮了個體的當前進化信息，提高了算法平衡全局探索和局部開發的能力，能夠保證算法獲得的Pareto前沿過程中具有良好的收斂性和多樣性.

2 MOEA/D算法

MOEA/D算法利用傳統分解方法將MOP問題分解為一些標量子問題，利用子問題之間的鄰域信息優化MOP問題.

2.1 MOP問題

一個多目標問題(MOP)具有多個待優化的目標.一個MOP問題可以被數學表達為如下：

minimizeF(x)=(f1(x)，…，fm(x))

subjecttox∈Ω

(1)

其中x=(x1，…，xn)∈Rn是一個決策變量向量，Ω是搜索空間的可行域，F：Ω→Rm是由m個目標函數f1(x)，…，fm(x)組成.如果Ω是一個在Rn上封閉并且聯通的區域，而且所有目標是x上連續的，這一問題可以被稱為一個連續的MOP問題.x，y∈Ω，當且僅當fi(x)≤fi(y)對于所有i∈{1，…，m}成立，并且F(x)≠F(y)時，稱x支配y，表示為x?y.一個點x*∈Ω，如果沒有其他x∈Ω支配x*，則稱x*為Pareto最優解.所有Pareto最優解的集合被稱為Pareto最優解集(PS)，Pareto前沿(PF)被定義為PF={F(x)|x∈PS}[1].

2.2 Tchebycheff分解方法

在MOEA/D算法中，一個MOP問題被分解為N個標量子問題，MOEA/D算法優化這些標量子問題得到的最優解集近似真實PF[8，19，12].很多分解方法已經被應用在MOEA/D算法框架中[8，20，21].其中，最為經典的是Tchebycheff分解方法，該方法如公式(2)所示.

subjecttox∈Ω

(2)

2.3 鄰 域

因為在Tchebycheff分解方法中每一個子問題與方向向量相關，并且它的目標函數是方向向量上連續的，如果兩個子問題的方向向量靠近，可以假設這兩個子問題具有相似的最優解.利用這一假設，MOEA/D引入了一個鄰域概念[8].給定一個子問題，它的鄰域是方向向量與其方向向量之間的歐氏距離最近子問題的集合，鄰域內的子問題是它的鄰居.

3 MOEA/D_PE算法

MOEA/D_PE算法是在MOEA/D算法框架基礎上，采用個體進化狀態判定策略，判定個體的進化狀態，為個體自適應選擇符合其進化狀態的變異算子.

3.1 個體進化狀態判定策略

MOP問題包含多個相互沖突的子目標，個體解之間不能直接比較，為了獲得個體解之間的差異，MOEA/D算法通過分解方法將MOP問題轉換為多個標量子問題，如公式(2).gte(x|λ，z*)在方向向量上是連續的，所以方向向量相鄰的子問題可能具有相似的解，同時不同解之間的差異可以通過標量子問題的函數值gte(x|λ，z*)進行直接比較.

個體進化狀態判定策略，是根據當前個體與其鄰域內多個其它個體標量子問題函數值的大小關系，確定個體屬于較好、一般和較差進化狀態的概率，根據個體屬于較好、一般和較差進化狀態的高概率判定個體進化狀態，根據已有的進化狀態判定結果，為個體選擇合適的變異算子.

如果個體標量子問題的函數值優于隨機三個鄰域內其他個體，則該個體具有屬于較好個體的高概率，判定該個體具有較好進化狀態；如果個體標量子問題的函數值均差于鄰域內三個其他個體，該個體具有屬于較差個體的高概率，判定個體屬于較差進化狀態；否則判定個體屬于一般進化狀態.

不同的變異算子具有不同的探索和開發能力.公式(3)是具有較好探索能力的變異算子，公式(4)是具有較好開發能力的變異算子，而公式(5)是一次平滑函數，不具有明顯的探索和開發能力，但可以對數據進行平滑處理.個體進化狀態判定策略是首先判定個體進化狀態，然后為個體選擇合適的變異算子；當個體進化程度較好，應利用公式(4)進行開發操作，以加速收斂；當個體進化程度較差，利用公式(3)對個體進行探索操作；當個體屬于一般進化狀態時，利用公式(5)對種群進行平滑處理，提高種群的多樣性.

vi=xi+F×(xr1-xr2)

(3)

vi=xi+K×(xi-xr1)+F×(xr2-xr3)

(4)

vi=α×xr1+(1-α)×xr2

(5)

xi為當前個體i的目標向量，xr1、xr2和xr3是個體i鄰域內彼此不同且不同于xi的三個目標向量，F為縮放因子取值為0.5，K也是縮放因子，在本文中取值為0.5，α是[0 1]區間上的一個隨機數.

3.2 MOEA/D_PE框架

3.2.1 初始化操作

初始化算法種群和權重向量，令參考點等于個體中最優適應度值；將種群中的Pareto最優解放入外部種群EP；

3.2.2 更新操作

第1步.任意個體i，從其鄰域內隨機取3個不同個體的目標向量xr1、xr2和xr3，比較個體i的目標向量xi，與xr1、xr2、xr3在標量子問題函數值的大小關系，利用個體進化狀態判定策略判定個體屬于鄰域內較好、較差和一般進化狀態的概率，進而判定個體進化狀態；

第2步.根據個體進化狀態，為個體i選擇合適的變異算子，進行遺傳操作(變異和交叉)以生成新解y；如果y的標量子問題函數值優于參考點，則將y的標量子問題函數值賦值到參考點；

第3步.比較y與個體i鄰域內所有個體標量子問題函數值的大小關系，如果個體標量子問題函數值差于y，則將y替代該個體；

第4步.如果y支配EP中的個體，則從EP中移除被支配的個體，并將y添加到EP中；

第5步.重復更新操作；

3.3.3 終止操作

如果滿足終止條件滿足，終止迭代，并輸出EP；否則跳轉到更新操作.

4 實驗研究

本文所有實驗中用到的算法和適應度函數均采用MATLAB語言編碼，利用配備了2.5GHZ Intel Core (TM) i5-2450M CPU的計算機進行實驗.為了評估MOEA/D_PE算法的性能，本文選擇了7個測試函數[22](MOP1～MOP7)，并將MOEA/D_PE算法與MOEA/D_DE算法[13]、最新分解類多目標進化算法MOEA/D_FRRMAB算法[18]和最新非支配排序類多目標遺傳算法NSGA-III算法[23]進行了比較.

4.1 實驗設置

1)種群大小N：在二目標的測試問題中所有算法種群大小被設置為100，而三目標測試問題中，所有算法的種群大小都被設為300.

2)交叉、變異算子：MOEA/D_DE、NSGA-III、MOEA/D_FRRMAB等算法的交叉算子和變異算子參考原文獻，MOEA/D_PE算法根據個體進化狀態判定策略選擇變異算子，交叉算子參考文獻[12].

3)終止條件：所有算法最大評估次數為3000.

4)所有算法在每一個測試問題中均獨立運行30次.

4.2 性能度量

采用翻轉時代距離(IGD)[24，25]評估算法的性能.假設P*是目標空間中均勻分布在PF上的一組Pareto最優解.假設P是算法獲得的，一組近似PF的解集.從P*到P的IGD被定義為：

(6)

其中d(v，P)是v和P中的點之間最小的歐式距離.如果P*足夠大，IGD(P*，P)可以同時測量P的收斂性和多樣性[26].在二目標測試問題中，，選擇了500個PF上均勻分布的點作為P*；在三目標測試問題中，選擇1000個PF上均勻分布的點組成P*.

4.3 測試問題

本文所使用測試問題(MOP1-MOP7)均來自文獻[22]，但本文對測試問題中的g(x)做了修改，使搜索空間為[0，1]n，n=10，MOP1-MOP5是具有兩個目標的多目標測試問題，MOP6、MOP7是具有三個目標的多目標測試問題，詳細內容如表1.

4.4 結果與討論

表2顯示了MOEA/D_DE、NSGA-III、MOEA/D_FRRMAB和MOEA/D_PE四個算法在每一個測試問題中30次獨立運行IGD度量的方差和平均值.為了更好觀察MOEA/D_PE算法與已有分解類多目標進化算法的差別，圖1和2展示了MOEA/D_PE和MOEA/D_DE算法在MOP1-MOP7問題的收斂情況.

觀察表2中的實驗數據可知，MOEA/D_PE算法在5個二目標測試問題MOP1-MOP5中獲得3個最優平均值，NSGA-III算法在MOP4中獲得最優均值，MOEA/D_FRRMAB算法在MOP5中獲得最優均值，MOEA/D_PE算法在MOP4和MOP5中的均值與最優值差別不大，這表明MOEA/D_PE算法在二目標測試問題中獲得更好的精度.同時，MOEA/D_PE算法在二目標測試問題中獲得2個最優方差，說明MOEA/D_PE算法表現出更好的穩定性.MOEA/D_PE算法在二目標測試問題中獲得更好精度和穩定性的原因是，該算法能夠準確判定個體進化狀態，并為個體提供合適的變異算子，從而促進了個體進化.

表2 實驗中各算法IGD度量的平均值和方差Table 2 Mean and variance of IGD measures for each algorithm in the experiment

從表2中三目標測試問題MOP6和MOP7中的實驗數據可知，MOEA/D_PE算法獲得全部最優均值，這表明MOEA/D_PE算法在三目標測試問題中能夠實現較好的精度.同時，MOEA/D_PE算法在MOP7中獲得了最優的方差，在MOP6中，MOEA/D_PE算法的方差僅次于MOEA/D_FRRMAB算法，這說明MOEA/D_PE算法在三目標測試問題中具有較好的穩定性.MOEA/D_PE算法在復雜的三目標測試問題中具有較好精度和穩定性的原因是，Tchebycheff分解方法將問題較好地分解，同時，個體進化狀態判定策略則能夠為個體選擇合適的變異算子，最終，提高了MOEA/D_PE算法收斂精度和穩定性.

從圖1二目標測試問題中可以看出，本文所提出的MOEA/D_PE算法在所有的二目標測試問題中都能收斂到全局Pareto前沿，而MOEA/D_DE算法在MOP4問題目標空間上失去了中間部分的Pareto前沿，未能表現出較好的收斂性能.圖1(a)、(b)、(c)、(d)和(e)收斂情況表明，MOEA/D_PE算法獲得的Pareto前沿更加均勻，這說明MOEA/D_PE算法在MOP1-MOP5二目標測試問題中具有更好收斂到全局Pareto前沿的性能.從圖2可以觀察到，在MOP6和MOP7三目標測試問題中，MOEA/D_PE算法也表現出了較好的收斂性能.這表明，充分利用個體的進化狀態信息，根據不同的進化狀態選擇匹配的變異算子，能夠有效提高算法收斂到全局Pareto前沿的性能和收斂穩定性.

圖1 二目標測試問題MOP1-MOP5的算法收斂圖Fig.1 Algorithm convergence figures of two objective test problems MOP1-MOP5

綜上所述，MOEA/D_PE算法在優化多目標測試問題時，表現出了比MOEA/D_DE、NSGA-III和MOEA/D_FRRMAB算法更好的優化性能，具有較好的收斂性能和多樣性.

5 結論和未來工作

變異算子的選擇是分解類多目標進化算法的重要研究方向，因為變異算子的恰當選擇可以提高算法的收斂性能和多樣性.本文針對變異算子選擇策略問題，提出了采用個體進化狀態判定策略的分解類多目標進化算法，該算法能夠判定個體當前進化狀態，并為個體選擇恰當的變異算子，從而提高了算法的收斂精度和穩定性.通過基準測試函數的仿真實驗，結果表明本文提出的算法具有良好的收斂性能和多樣性.未來將繼續研究采用個體進化狀態判定策略的分解類多目標進化算法的實際應用問題.