錢小宇，葛洪偉，蔡明

（1. 江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122; 2. 江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122; 3. 江南大學 信息化建設與管理中心，江蘇 無錫 214122）

粒子群算法自1995年被Kennedy和Eberhart提出后[1]，由于其簡單高效，收斂速度快，逐漸在優(yōu)化算法中脫穎而出。隨之粒子群算法被Coelloran應用到多目標優(yōu)化問題上[2-3]，得到了各界的廣泛認可。后來更多學者對多目標粒子群算法(MOPSO)進行了更深入的研究：Raquel等[4]使用了擁擠距離作為適應值對粒子進行排序；Li等[5]通過整合粒子的GMR(global margin ranking)和粒子密度信息的方法來對粒子進行排序，能高效快速地選擇出pbest和gbest粒子；除了對排序選擇的方法進行優(yōu)化外，有的利用聚合函數(shù)來對多個目標函數(shù)進行處理[6]；有的使用了目標空間分解的方法來保障粒子最優(yōu)解的多樣性[7]；以及將MOPSO和其他優(yōu)化算法進行交叉使用，如教與學方法[8]、差分方法[9]等, 通過一定的比例調(diào)用MOPSO。

上述的這些方法不斷地對MOPSO的多樣性和全局收斂進行改進和優(yōu)化，雖然取得了較好的研究成果，但是這些方法的改進策略只對MOPSO某一性能效果進行改進，其他的性能指標并沒有同時得到很好的改進。例如：文獻[7]中，多樣性方面得到很大的提升，但是其收斂性方面仍有很大不足。所以，本文借鑒Pareto支配強度[10]和連續(xù)變異的方法[11]對基于目標空間分解方法的多目標粒子群算法[7]進行優(yōu)化，在給每個子區(qū)域分配粒子時，刪除沒有歸屬的粒子，給沒分到粒子的區(qū)域初始化新的粒子，增加獲得較優(yōu)粒子的可能性。這樣既從整體和局部兩方面提升了粒子的收斂性，同時多樣性也得到了一定的優(yōu)化提升，這種新的算法被稱為基于目標空間分解和連續(xù)變異的多目標粒子群優(yōu)化算法(multi-objective particle swarm optimization based on decomposition and continuous mutation ，MOPSO/DC)。

1 多目標優(yōu)化問題

1.1 基本概念

式中： x =(x1,x2,···,xn) 為 n 維 決策變量； m 為目標函數(shù)的個數(shù)； g ( x) 函 數(shù)為目標函數(shù)的 q 個不等式約束； h ( x) 為 目標函數(shù)的 p 個等式約束。所有這些滿足條件的決策變量用集合 ? 表 示，Y={F(x)|x∈?}為目標空間。接下來介紹4個關于多目標問題的重要定義。

定義1 Pareto支配。解 d , e ∈? ， d 支 配 e，記為 d ? e，滿足下面的兩個關系式：

定義2 Pareto最優(yōu)。如果 x 是Pareto最優(yōu)解，則在 ? 中 ， ? ?z∈? 使 z ? x 成立。

定義3 Pareto最優(yōu)解集(P S )：

1.2 粒子群優(yōu)化

粒子群算法中的粒子由速度信息和位置信息組成，更新公式為

式中：k指粒子群中第k個粒子；t為當前迭代次數(shù)；W為權衡局部搜索和全局搜索的參數(shù)，W∈[0.1,0.9]； C1和 C2為學習因子，其大小都為2；R1和 R2都是[0，1]之間的隨機數(shù)；P指當前粒子最好位置pbest；G指引導粒子gbest的位置；指在第t次迭代中第k個粒子的速度；指在第t次迭代中第k個粒子的位置。

2 MOPSO/DC算法

2.1 目標空間分解

把 目標 空間 Y 分 成 M 個 子 區(qū) 域 Y1，Y2，···，YM。令 j ∈ { 1,2,···,M}，對任一給定的第j個子區(qū)域，每個目標函數(shù)在所有目標函數(shù)中所占有的權重所組成的向量(a1,a2,···,am) 定 義為該子區(qū)域的中心向量 Aj。當目標函數(shù)個數(shù) m =2 時 ，則第 j 子區(qū)域的中心向量 Aj表示為當 m =3 時，進行兩層循環(huán)，令 k1為第1層(外層)循環(huán)變量， k2為第2層(內(nèi)層)循環(huán)變量， k1從 0取到h， k2從0取到 h - k1， 每 次 循 環(huán) 令其中h和M滿足：當 時h取最小值，則第u個子區(qū)域的中心向量為當m>3 時 ，進行 m - 1 層 循環(huán)， k1為第一層循環(huán)變量(最外層)，依次由外向內(nèi)，令 ki為第i層循環(huán)變量，km-1為第 m - 1 層 (最內(nèi)層)循環(huán)變量， k1從0取到h，k2從0取到 h - k1， ki從 0取到 ( h -k1-k2- · ··ki)，最里層循環(huán)變量km-1從0取到 ( h -k1-k2-···km-2)，每次循環(huán)令生個中心向量，這些向量的下標為若M ， 則 從 下 標 u = 2 開始，以為步長依次刪除M 個下標對應的中心向量，然后將剩下的M個中心向量依次作為 Aj，j=1, 2, ···, M。通過每個子區(qū)域的中心向量找出該子區(qū)域的T個相鄰的子區(qū)域, 參考指標為兩個中心向量的余弦值。

2.2 粒子的分類與更新

在對粒子進行分配時，通過參考點確定每個粒子的方向向量[7]。令參考點為 R ( r1,r2,···,rm)，其中為目標函數(shù)個數(shù)。例如：如圖1所示， f1和 f2表示兩個目標函數(shù)，m=2，則圖中粒子C的方向向量為從點R(r1,r2)指向點C的向量X，X=C-R。通過比較粒子方向向量和所有子區(qū)域中心向量的余弦值，確定該粒子屬于最大余弦值所對應的中心，向量子區(qū)域。

圖 1 粒子的方向向量Fig. 1 Direction vector of the particle

在對粒子進行分配時會有以下兩種特殊情況：

1)有的子區(qū)域粒子數(shù)大于子區(qū)域的容量Vol時，通過適應值進行取舍，適應值公式為式中：T是Pareto支配強度，其數(shù)值為當前粒子支配的粒子數(shù)，在適應值計算中加入了Pareto支配強度T，增強每個子區(qū)域中的粒子趨向真實PF的能力；參數(shù)a表示支配強度對適應值的影響程度，，M指目標空間子區(qū)域數(shù)；CD為擁擠距離，通過每個目標函數(shù)值對粒子進行排序，序列兩端粒子在當前目標函數(shù)中的擁擠距離設為5，其他粒子在當前目標函數(shù)中的擁擠距離為在序列中該粒子前后兩粒子的目標函數(shù)值之差的絕對值，最后將求出的該粒子在每個目標函數(shù)中計算的擁擠距離之和作為當前該粒子的擁擠距離CD。

計算該子區(qū)域包含的粒子的適應值，從大到小排序，選擇序列中前30%的粒子，再從這些粒子中選擇離所在子區(qū)域中心向量最近的Vol個粒子，多余的劣質(zhì)粒子刪除。

2)當子區(qū)域粒子數(shù)少于該子區(qū)域容量Vol時，由于情況1)中已經(jīng)對劣質(zhì)的粒子進行刪除，為了盡可能保證整體的優(yōu)越性，所以重新初始化該子區(qū)域所缺數(shù)目的粒子作為該區(qū)域的粒子，增加獲得較優(yōu)粒子的可能性，增加粒子多樣性。然后計算新粒子的目標函數(shù)值。

2.3 連續(xù)變異操作

當只采用一種方法進行變異時，不能兼顧全局粒子和局部粒子的特性。在MOPSO/DC中提出差分+柯西[12]+高斯[13]連續(xù)的變異策略，公式為式中：X為當前引導粒子gbest的位置；X1和X2是從EPOP中隨機選出的兩個不同粒子的位置。這樣在變異時可保留全局粒子的一部分性質(zhì)，起到一定信息交流的作用，增加了多樣性。t為當前迭代的次數(shù)，gmax為最大迭代次數(shù)， g ( 1)=2，g(t+1)=和分別是對gbest的位置進行變異操作之后產(chǎn)生的新粒子。每次變異后讓產(chǎn)生的新粒子和當前的gbest進行比較，選擇支配權優(yōu)先的作為gbest，然后進行后續(xù)變異操作，直到3次變異結束，最終確定引導粒子gbest。

高斯變異步長較短，能很好地吸取局部粒子性質(zhì)，柯西變異具有相對大的步長，能進行較大范圍的變異，具有全局范圍變異的特性，這樣能很好地產(chǎn)生全新的粒子。觀地看出，柯西分布具有較寬的變異范圍，粒子具有較大范圍的變異。用這3種方法進行變異操作，既增強了

圖 2 標準高斯和分布柯西分布對比Fig. 2 Comparison of standard Gaussian and Cauchy distributions

gbest的引導能力，同時gbest吸取局部或全局粒子的性質(zhì)，促進了粒子之間信息交流共享，增加了多樣性。

2.4 MOSPO/DC步驟

1)初始化2N個粒子的位置，這些粒子的位置集合記為POP，初始化N個速度，這些速度集合記為V，設目標函數(shù)的個數(shù)為m，當前迭代次數(shù)為t，初始化最大迭代次數(shù)gmax、每個子區(qū)域容量Vol∈[1,3]、鄰域個數(shù)T以及子區(qū)域數(shù)目M。

2)進行目標空間分解操作。

3)計算粒子群POP目標函數(shù)值，選出每個目標函數(shù)的最小值作為參考點R用于計算每個粒子的方向向量，方向向量的計算參考圖1。

4)進行粒子的分類與更新操作，接著將當前所有子區(qū)域粒子的位置信息存入集合EPOP中，最后更新參考點R，并重新計算每個粒子的方向向量，清空POP備用。

5)gbest的選擇：產(chǎn)生[0，1]之間的隨機數(shù) r1,當r1>0.8時，隨機從EPOP集合中選擇一個粒子作為當前粒子的gbest；否則，在該粒子所在區(qū)域的鄰域內(nèi)操作。首先計算該粒子鄰域中每個子區(qū)域的中心向量和該子區(qū)域中粒子方向向量的余弦值，然后選出余弦值最大的子區(qū)域中的粒子作為當前粒子的gbest。過多地使用變異會讓算法變得更加隨機，降低了算法的效率，所以產(chǎn)生[0,1]之間的隨機數(shù)r2,當r2<0.6時，對選出的引導粒子位置進行連續(xù)變異操作，確定最終的引導粒子gbest。否則，不對gbest進行變異操作。

6)pbest的選擇：產(chǎn)生[0,1]之間的隨機數(shù)r3，當r3>0.8時，隨機從EPOP中選擇一個粒子；否則，從該粒子的所在區(qū)域的鄰域中隨機選擇一個粒子。讓當前粒子和這個隨機選出的粒子進行比較，選出支配權優(yōu)先的作為當前粒子的pbest。

7)通過上述選出的gbest和pbest，以及粒子速度更新式(5)和位置更新式(6)產(chǎn)生下一代新的粒子群體，這些新粒子位置集合記為NPOP，下一代新的速度集合重新覆蓋集合V。

8)如果當前迭代次數(shù)t大于最大迭代次數(shù)gmax，則循環(huán)結束，輸出EPOP作為最優(yōu)解集，否則把NPOP和EPOP合并放入POP中，然后跳轉至3)，繼續(xù)循環(huán)。

3 實驗分析

為了測試所提出的MOPSO/DC算法的性能，將其與目前較流行的MOPSO/D[7]、MOPSOTL[8]、MOPSODE[9]和NNIA[14]算法進行對比，實驗中同樣選擇了文獻[7]中的6個測試函數(shù)，依次為F1，F(xiàn)2···F6。為了定量比較5種算法的性能，采用以下3種廣泛使用的性能指標：HV[15]，測量了粒子收斂于真實PF的效果以及最優(yōu)解集的多樣性，所獲得值越大越好；GD[16]，指算法獲得的PF到真實PF的距離，數(shù)值越小越接近真實PF，效果越好；IGD[15]，顯示真實PF到算法所得到PF的距離，值越小越能說明算法得到的PF上的點可以分散地均勻地收斂于真實PF上。

MOPSO/DC參數(shù)設置：當目標函數(shù)個數(shù)m=2時， M =500 。 當 m =3 時， M =1 035。V o l=1，N=M Vol， T =[0.1N]，粒子維度n=10，最大循環(huán)次數(shù)gmax=1 000，一共進行了30次實驗求各性能指標的均值和標準差。其他算法參數(shù)請參考文獻[7]。

MOPSO/DC與其他算法關于這6個測試函數(shù)的3種性能指標對比結果見表1，表中給出了通過MOPSO/DC和其他4個算法獲得關于這6個問題的IGD、GD和HV的平均值和標準差。從表1中可以看出：1)MOPSO/DC獲得的IGD平均值遠小于其他4種算法；2)MOPSO/DC獲得的GD平均值都是最佳的，除F3函數(shù)外，不過關于F3的GD均值，本算法也優(yōu)于MOPSO/D算法[7]；3)通過MOPSO/DC獲得的HV值總體來說比其他算法獲得的HV值好(除F1函數(shù))，說明MOPSO/DC的收斂性以及解的多樣性也相當好。整體來說，MOPSO/DC的這3個性能指標優(yōu)于其他4個算法，對MOPSO/D算法進行了很好的改進。

表 1 各算法效果指標對比Table 1 Comparison of the effect of each algorithm

MOPSO/DC算法的仿真圖如圖3，結果顯示該算法得到的PF和真實PF完全重合。

通過這些對比實驗得出結論：MOPSO/DC對原算法[7]的收斂性和多樣性進行了很好地優(yōu)化，增強了粒子趨向真實PF的效果，并且具有很好的穩(wěn)定性。

圖 3 測試函數(shù)的仿真圖Fig. 3 Test function's simulations

4 結束語

本文提出的算法采用目標空間分解與子區(qū)域粒子更新和對引導粒子gbest的位置進行連續(xù)變異的方法來提高粒子多樣性和收斂性，對原算法的不足之處進行了很好地彌補和優(yōu)化。通過和4個不同種類的優(yōu)化算法對不同種測試函數(shù)進行多種性能的測試對比實驗證明，MOPSO/DC整體效果最好，具有很高收斂性，多樣性方面也有提升?？傊?，MOPSO/DC對多目標優(yōu)化問題的多個性能指標同時進行了很好的優(yōu)化。未來的研究重點是，將該算法更好地適應更多目標的優(yōu)化問題，增強其通用性，用于解決實際問題。