一種多樣性控制的多目標粒子群算法

劉天宇，王 翥

(1.上海海事大學 信息工程學院，上海 201306；2.上海海事大學 物流工程學院，上海 201306)

現實生活中的很多問題都可以抽象化為具有多個相互沖突目標的多目標優化問題。近些年來，采用進化算法來處理多目標優化問題已經成為研究熱點之一。其中，粒子群算法作為一種經典的群智能算法，由于其參數少及容易實現的特點，被廣泛地應用于求解各種多目標優化問題[1-3]。

對于包括多目標粒子群算法(Multi-Objective Particle Swarm Optimization，MOPSO)[4]在內的多目標進化算法，算法設計的關鍵在于達到種群多樣性及收斂性之間的平衡，以便有效產生一組同時優化多個沖突目標的Pareto最優解集。針對上述問題，目前已經出現了許多改進的MOPSO算法。一些改進算法通過將MOPSO與各種多樣性保持策略及局部搜索策略相結合，來更好地平衡算法的收斂性與多樣性。YU等[5]通過將多種群策略與多目標粒子群算法相結合，提出了一種基于多種群動態協同的多目標粒子群算法。HAN等[6]提出了一種自適應的多目標粒子群算法AGMOPSO。該算法通過采用自適應飛行參數來控制粒子在搜索空間的移動，進而平衡算法的收斂性和多樣性。

此外，另一影響MOPSO算法性能的關鍵在于如何對種群中的每一個粒子獲取合適的全局及個體最優位置，以提高算法的搜索有效性[7]。針對這一問題，文獻[4]中提出了一種被廣泛應用的方法。該方法利用外部種群來存儲算法當前獲得的Pareto最優解集，然后從外部種群中選擇合適的個體作為粒子的全局最優位置。而粒子的個體最優位置則為其在歷史搜索過程中所找到的最優位置。RAQUEL等[8]提出了一種基于擁擠度距離的多目標粒子群算法。該算法首先基于擁擠度距離和變異算子來保證外部種群的多樣性，然后再次利用擁擠度距離從外部種群中選擇出個體的全局最優位置。MARTNEZ等[9]提出了一種基于分解的算法dMOPSO。該算法通過分解策略來確定粒子的全局最優位置。

綜上所述，大多數的改進算法都是在傳統MOPSO的基礎上引入各種算子來提高算法的搜索效率的。其中如何保證種群多樣性幾乎是每種改進算法都必須要考慮的一個關鍵因素。不同于大多數算法只是利用多樣性度量指標評估算法的最終運行結果，文中提出了一種基于多樣性控制的MOPSO算法(MOPSO-DC)。該算法在每一次迭代中都監測當前所獲得的Pareto最優解集的多樣性，并根據多樣性度量指標自適應地選擇不同的粒子更新策略。論文主要工作如下：

(1) 采用一種基于權值向量的度量指標來評估算法在每次迭代中獲得的Pareto最優解集的多樣性。

(2) 采用一種基于Steffensen方法的自適應變異算子，以保持種群多樣性。

(3) 自適應選擇粒子的全局最優位置來實現種群的更新操作。

1 相關工作

1.1 多目標優化問題

以最小化問題為例，一個多目標優化問題可抽象為如下形式：

(1)

其中，x是N維搜索空間中的一個粒子(決策變量)，fj(x) (j=1，2，…，M)為 粒子x的第j個目標函數值，M為目標空間的維數。

因為多目標優化問題包含了M個相互排斥的優化目標，因此優化算法無法找到一個可以同時最優化所有目標的最優解。多目標進化算法的目的就是在搜索空間中找到由一組互不支配的個體構成的Pareto最優解集。Pareto支配及Pareto最優解集[10]定義如下。

Pareto支配：對于式(1)定義的多目標問題，稱搜索空間中的決策變量x1支配x2，即x1?x2，當且僅當?j∈{1，2，…，M}，fj(x1)≤fj(x2)，并且?j∈{1，2，…，M}，fj(x1)

Pareto最優解集：對于式(1)定義的多目標問題，若其搜索空間為Ω，則Pareto最優解集P*為

P*：={x∈Ω|?x′∈Ω，x′?x}。

(2)

1.2 MOPSO算法

MOPSO通過粒子在搜索空間中的移動來搜索Pareto最優解集，其中粒子位置的更新速度受全局及個體最優位置的影響。全局最優位置g記錄了整個種群當前搜索到的最優位置，而個體最優位置pi則記錄了粒子xi在歷史搜索過程中的最優位置。MOPSO中粒子xi的更新過程如下：

(3)

其中，t表示算法迭代次數；w為慣性權重，通常取值為0.4；r1與r2為[0，1]區間中取值的隨機數，分別表示粒子受個體及全局最優位置影響的程度。

由于多目標優化中無法得到可以同時優化所有目標的最優解，因此粒子個體及全局最優位置的獲取也就成了MOPSO算法實現的難點及關鍵之處。筆者提出了一種基于多樣性控制的多目標粒子群算法，通過對算法當前所獲得的Pareto最優解集的多樣性進行評估，進而根據多樣性評估值自適應選擇粒子的全局最優位置。

1.3 Steffensen方法

如何尋找非線性方程f(x)=0的根是科學計算中的一個經典問題，而Steffensen方法[11-12]則是被廣泛應用的一種非線性方程迭代求根方法。Steffensen方法具體操作可表示為

(4)

其中，x0為初始根值，xk和xk+1分別為第k+1次迭代前及迭代后的根值。

2 MOPSO-DC算法設計

2.1 基于權值向量的多樣性評價指標

種群多樣性是影響多目標進化算法性能的一個重要因素。因此，在算法運行過程中對種群多樣性進行實時評估，根據多樣性評估值調整種群的更新策略，可有效避免算法陷入早熟。文中提出了一種基于權值向量的多樣性評價指標來評估算法在每一次迭代中所獲得的Pareto最優解集的多樣性。

該評價指標的核心思想即利用一組在目標空間均勻分布的權值向量，通過計算當前算法獲得的非支配解集所覆蓋的權值向量數目與權值向量總數的比值來評估該非支配解集的分布情況。具體計算過程為

(5)

其中，np為Pareto最優解集覆蓋的權值向量數目，nw為權值向量總數。

圖1 基于權值向量的多樣性 評價指標示意圖

圖1以兩目標優化問題為例，給出了基于權值向量的多樣性評價指標的評估示意圖，其中w1～w3為一組在目標空間均勻分布的權值向量，x1～x3為算法當前獲得的Pareto最優解集(即算法當前外部種群中的個體)。由圖1可得，x1、x2、x3在權值向量集合中分別與w2夾角距離最近，因此整個Pareto解集覆蓋到了權值向量中的一個向量w2。由式(5)可得，當前η值為1/3。根據如上描述，η取值區間為[0，1]。η值越小，則表明當前Pareto最優解集在目標空間中的分布越集中。

若算法當前獲得的Pareto最優解集為P，則對其進行多樣性評價的步驟如下：

步驟1 根據DAS等所提方法[13]產生一組在目標空間均勻分布的權值向量{w1，w2，…，wk}。

步驟2 產生一個k維零向量z=[0，0，…，0]。

步驟3 對P中的任一個體xi，計算與其在目標空間中夾角距離最近的權值向量wj，并設置z(j)=1。

步驟4 計算得出多樣性指標η=sum(z)/k。

由上述步驟可知，η借助權值向量反映了Pareto最優解集在目標空間的分布情況。η取值范圍為[0，1]，η取值越大，則說明當前Pareto最優解集的多樣性越好。

2.2 基于Steffensen方法的自適應變異策略

MOPSO-DC算法利用外部種群存儲算法獲得的Pareto最優解集，并通過在外部種群中選擇合適的個體來作為粒子的全局最優位置。因此，外部種群的多樣性會直接影響粒子種群的搜索能力。文中利用一種基于Steffensen方法的變異策略來增加外部種群的多樣性。當外部種群的η指標小于給定閾值時，則對外部種群中的個體進行變異。如圖2所示，w1～w3為一組在目標空間均勻分布的權值向量，x1～x3為外部種群中的個體。對個體x1，首先從距其最近的幾個權值向量中隨機選擇得出一個權值向量(假設為w1)，然后以降低x1與w1之間的距離D(x1，w1)為目標，對x1進行變異得到距離w1更近的變異個體x'1。通過逐一對外部種群中的個體進行如上操作，得到一組在目標空間中分布較均勻的變異個體。

圖3 距離D(xi，wj)計算過程示意圖

(6)

其中，x'i，k為xi，k經過變異后的值，L(xi，k)=D(xi，wj)-d*。

以外部種群中的某一個體xi為例，其變異操作如下：

步驟1 計算得出與xi夾角距離最近的δ(δ小于權值向量的個數)個權值向量，并從δ個權值向量中隨機選擇一個權值向量wj。

步驟2 計算xi到wj的距離D(xi，wj)=d1+d2。

步驟3 在xi中隨機選擇一維(假設為第k維)進行變異。令d*=rD(xi，wj)，L(xi，k)=D(xi，wj)-d*，其中r∈(0，1)。則根據式(6)，可得出xi，k變異后的值x'i，k。

2.3 自適應粒子更新策略

在MOPSO-DC中，粒子位置的更新借鑒傳統的MOPSO算法，根據式(3)來實現。其中，以每個粒子在歷史搜索過程中獲得的最優位置作為其個體最優位置。而全局最優位置則根據2.1節中獲得的η值自適應地從外部種群中進行選擇得出。當η值小于等于給定閾值時，則對外部種群中的個體根據擁擠度距離[14]進行排序，從擁擠度距離前10%的個體中隨機選擇一個個體作為粒子的全局最優位置。當η值大于給定閾值時，首先計算得出與當前粒子xi夾角距離最近的權值向量wj；然后根據2.2節步驟2從外部種群中選擇與wj距離最近的非支配個體作為xi的全局最優位置。

圖4 MOPSO-DC算法的流程圖

2.4 MOPSO-DC算法流程

圖4為MOPSO-DC算法的流程圖，其具體操作步驟如下：

步驟1 初始化粒子種群，計算每個粒子的適應度值，并選擇粒子種群中的非支配個體作為外部種群，產生一組在目標空間中均勻分布的權值向量W={w1，w2，…，wk}，設置種群的個體最優位置為當前粒子種群。

步驟2 計算當前外部種群的η指標。

步驟3 若η小于給定閾值s，則對外部種群中的每個個體進行變異，并從變異后的種群及原外部種群中選擇非支配個體作為新的外部種群。

步驟4 根據2.3節及閾值s，自適應地從外部種群中為每個粒子選擇全局最優位置。

步驟5 根據式(3)對粒子位置進行更新，并計算其適應度值，并對個體最優位置進行更新。

步驟6 將外部種群更新為算法目前搜索到的非支配個體構成的集合。

步驟7 判斷是否滿足終止條件，若滿足，則輸出外部種群；若不滿足，則跳轉至步驟2進行下一次迭代。

3 實驗分析

為評估算法性能，文中選取了ZDT1～ZDT4、ZDT6、DTLZ1～DTLZ3、WFG1～WFG9作為測試函數，并選擇MOPSO[4]、dMOPSO(MOPSO Based on Decomposition)[9]、NSGA-II(Non-dominated Sorted Genetic Algorithm)[13]、MOEA/D(Multi-objective Evolutionary Algorithm Based on Decomposition)[15]作為對比算法來分析所提出算法的有效性。對MOEA/D，設置大小分別為100(對于2目標問題)和105(對于3目標問題)，其余算法的種群大小均為100。對所有算法，最大函數評價次數為10 000。選擇逆世代距離(Inverted Generational Distance，IGD)[16]及分布指標(SPacing，SP)[17]作為評價算法性能的量化指標。其中，IGD指標用來度量算法產生的Pareto前沿面與真實的Pareto前沿面之間的距離。當IGD值為零時，則表示算法搜索到了真實Pareto前沿面中的所有個體。SP指標則用來度量算法產生的Pareto解集的分布情況。當SP值為零時，則表示算法搜索到的Pareto最優解集中的個體是均勻分布的。每個算法獨立運行30次來獲得最終的統計結果。算法的具體參數設置見表1。

表1 算法的參數設置

3.1 參數分析

MOPSO-DC中，參數s用來控制粒子全局最優位置的選擇。若s取值過小，則算法將會耗費大量的計算量用于保持外部種群的多樣性，有時候甚至可能引起搜索的退化；若s取值過大，則可能會造成多樣性，保持效果較差，算法陷入早熟。因此，為了選擇合適的s取值，以ZDT1、ZDT4、DTLZ2及IGD指標為例，來分析s的不同取值對算法性能的影響。表2給出了MOPSO-DC在不同s取值下30次運行的平均IGD值。其中，當s取值為0.7時，算法針對ZDT1和DTLZ2均取得了最優的IGD值。對于ZDT4，s取值為0.5和0.7時，算法分別取得了最優及第二優的IGD值。因此，在文中將閾值s設置為0.7。

3.2 對比實驗結果與分析

表3和表4為5種算法針對不同測試問題經過30次獨立運行的平均IGD值與SP值。其中括號中的數值為算法在不同測試函數上的排序值，排序值為1則表明該算法在所有算法中針對給定的測試函數表現最好。

根據表3和表4中的統計結果，MOPSO-DC在所有測試函數上的IGD值均優于MOPSO的，且在大多數測試函數上的SP值優于MOPSO的。這說明了MOPSO-DC中所提出策略的有效性。MOPSO-DC中的基于權值向量的多樣性評價指標、基于Steffensen方法的自適應變異策略以及自適應粒子更新策略，能夠有效平衡算法的收斂性及種群多樣性，從而提高了算法的搜索效率。

表3 算法針對不同測試問題的平均IGD值

表4 算法針對不同測試問題的平均SP值

圖5～圖7分別給出了文中算法與對比算法在ZDT 2、ZDT 4、DTLZ 2、WFG 2、WFG 4、WFG 6以及WFG 8上的Pareto前沿面。

圖5 MOPSO-DC與對比算法在ZDT 2函數上的Pareto前沿面

對于函數ZDT 4，MOPSO-DC在IGD指標及SP指標上的表現均要差于dMOPSO和MOEA/D。 對于函數DTLZ 1和DTLZ 3，MOPSO-DC在IGD指標及SP指標上的表現均要差于NSGA-II及MOEA/D。這是由于MOPSO-DC利用自適應粒子更新策略根據計算得出的多樣性評價指標及給定閾值，來判斷是否對外部種群進行變異以及對粒子選擇擁擠度距離較大的全局最優位置，這在一定程度上影響了算法跳出局部最優的能力。因此，算法在處理某些多峰問題時性能差于對比算法，圖6中5種算法在ZDT 4上的Pareto前沿面也驗證了上述結論。

表5給出了算法在針對所有測試函數的平均排序結果。其中，MOPSO-DC在IGD指標和SP指標均取得了最優排序值，這說明雖然MOPSO-DC在某些函數上效果不佳，但綜合所有測試函數來考慮，MOPSO-DC取得了最好的結果。

表5 算法平均排序值

算法在WFG系列測試函數上的統計結果表明，MOPSO-DC對于絕大多數WFG測試函數都取得了最優的IGD值，對WFG 1、WFG 3、WF 5及WFG 6上取得了最優SP值。對于WFG 4、WFG 7～WFG 9，MOPSO-DC取得的平均SP結果差于MOPSO。這是由于MOPSO-DC采用的變異策略首先對于變異后的個體進行評價，然后從變異后的個體與原始外部種群中選擇非支配個體作為新的外部種群。與傳統的變異策略相比，筆者所提變異策略需要耗費一定的函數評價次數。此外，為了保證變異后的個體向著Pareto前沿面靠攏，MOPSO-DC選擇變異個體與原始外部種群中的非支配個體作為新的外部種群，因此有時會造成某些分布較好的變異個體不會被保留，導致算法對于一些測試問題獲得的非支配解集SP指標差于對比算法。圖8～圖11分別給出了MOPSO-DC與對比算法在WFG 2、WFG 4、WFG 6、WFG 8上的Pareto前沿面。以MOPSO-DC與MOPSO的對比圖為例，從圖中可以看出，MOPSO-DC獲得的Pareto最優解集更接近理想的Pareto前沿面，但是MOPSO所獲得Pareto最優解集分布更均勻。

圖8 MOPSO-DC與對比算法在WFG 2函數上的Pareto前沿面

4 結束語

針對傳統MOPSO算法容易早熟的問題，筆者提出了一種基于多樣性控制的多目標粒子群算法(MOPSO-DC)。該算法在每一次迭代中都對外部種群的多樣性進行評估，并根據評估值自適應地選擇是否對外部種群進行變異操作以及選擇不同的粒子種群更新方式。對比實驗表明，MOPSO-DC與傳統MOPSO算法相比，展現了很強的優勢，且與其他對比算法相比，也表現出了很強的競爭性。但實驗結果同樣展現了MOPSO-DC存在一些不足。一方面，在MOPSO-DC采用的基于Steffensen方法的自適應變異策略中，只有當變異個體為非支配個體時才會被保留，這可能造成算法在耗費計算量的同時，不會提升其所獲得的Pareto解集的分布性；另一方面，MOPSO-DC利用自適應粒子更新策略，根據計算得出的多樣性評價指標及給定閾值，來判斷是否對外部種群進行變異，以及對粒子選擇擁擠度距離較大的全局最優位置，這在一定程度上影響了算法跳出局部最優的能力。因此，如何更有效利用獲得的變異個體及增強算法在處理多峰問題時跳出局部最優的能力，是未來的一個研究方向。