基于網格排序的多目標粒子群優化算法

李 笠 王萬良 徐新黎 李偉琨

(浙江工業大學計算機科學與技術學院 杭州 310023)(liixac@gmail.com)

基于網格排序的多目標粒子群優化算法

李 笠 王萬良 徐新黎 李偉琨

(浙江工業大學計算機科學與技術學院 杭州 310023)(liixac@gmail.com)

在多目標進化算法中，近年的研究傾向于基于Pareto支配的最優化方法.針對傳統的基于Pareto支配在排序效率上過低的問題，提出了一種基于網格排序的框架，利用網格同時表征收斂性與分布性的特性，結合粒子群算法，提出了一種基于網格排序的多目標粒子群優化算法.與個體兩兩進行比較的基于Pareto支配的策略不同，基于網格排序的機制融合了整個解空間中個體的占優信息，并利用占優信息進行排序，從而高效地得到個體在種群中的優劣關系；結合粒子到近似最優邊界的距離，進一步加強了粒子在解空間中優劣關系的判別.對比實驗分析表明：所提算法不論是在收斂性還是分布性上都具有較好的優勢.在此基礎上，討論了網格劃分數對算法效率的影響，從另一方面驗證了算法的效率.

多目標優化；進化算法；粒子群算法；網格；排序

粒子群優化算法(particle swarm optimization, PSO)是一種模擬鳥群覓食的群智能優化算法，由Kennedy等人[1]提出，通過追隨解空間中2個最優值(個體歷史最優pBest、全局最優gBest)進行尋優，由于其參數簡潔、易于實現，在優化[2]、調度[3]以及一些參數整定[4]、圖形圖像[5]等方面都取得了滿意的效果.但是在研究與工程實踐中，存在多個需要同時考慮的問題，即多目標優化問題(multi-objective problem, MOP)[6-7]，此類問題由于各目標間存在相互約束的關系，通常的線性規劃等常規數值優化方法難以求解.于是，將粒子群優化算法應用到多目標優化成為目前的一個研究熱點.Coello等人[8]第1次將粒子群算法擴展到多目標，利用Pareto支配的思想，提出了MOPSO算法；此后，許多學者對此進行了研究[9-10].

但是在將PSO擴展到多目標優化中，面臨著如下問題與挑戰：

1) 在單目標優化中，個體的適應值能簡單而唯一地被確定；而在多目標優化問題中，存在多個互相制約的目標，個體的適應值不能通過簡單的比較適應值大小進行確定，因此，如何判斷個體的優劣是多目標優化中基礎且關鍵的問題，直接影響粒子群算法中的pBest，gBest的選取，進而影響整個算法的收斂.

2) 單目標優化問題由于其明確的數值關系，能得到一個唯一的最優解；而在多目標優化中，由于多目標問題的特性決定了其很難得到單個最優解，往往存在一組解集，如何獲得一組更加多樣化且包含關鍵信息的解集，以便給決策人員提供更加完整的參考是存在的另一個挑戰.

在個體優劣的判斷中(挑戰1))，目前主流的研究思路是基于Pareto支配，通過比較各個目標上的數值大小，得到個體的支配關系，出現了許多優秀的多目標優化算法.比如Deb等人[11]利用non-dominated sorting提出了NSGA-Ⅱ，Zitzler等人[12]利用強度Pareto支配的思想提出了SPEA2.但是基于Pareto的方法在遇到非凸、多峰以及解空間中存在許多弱支配關系個體時，效率會急劇下降[13].于是，有學者提出了一些解決方法，主要有3類：

1) 松散的Pareto支配.通過擴大支配空間來改善Pareto支配的不足，此概念由Laumanns等人[14]提出;Batista等人[15]改進了L-dominance并提出了cone L-dominance;Zou等人[16]提出了L-dominance,其實質也是屬于Pareto支配.

2) 非Pareto支配的方法.Weighted sum[17]、weighted Tchebycheff[18]、基于分解的方法[19]等.

3) 基于聚合函數的方法，利用構造的聚合函數(aggregation function)對個體優劣進行判別，主要有基于Max-min適應值法[20]等.

在解的多樣性保持方面(挑戰2)，主要有：小生境方法，模擬自然界生物的“物以類聚”[21]來維持種群的分布性；利用個體之間相異或相似度的聚類方法[22]、利用個體的密度信息包括聚集密度法[23]以及信息熵[24]等.信息熵是衡量分布的混亂程度或分散程度的一種度量，分布越分散，信息熵就越大；分布越集中，信息熵就越小.采用信息熵的辦法可以在一定程度上維持群體的多樣性.但是從熵的定義可以看出，此種方法是從群體整體出發，缺乏對群體內部個體之間關系的刻畫，對于種群進化過程當中的多樣性與分布性的調控不是很有效.聚集密度主要是計算種群中個體兩兩之間的歐氏距離，利用個體的密度信息來維持種群的多樣性.

基于網格的方法在多目標優化算法當中有較好的應用.Leong等人[25]通過構建網格來維持解的多樣性.Knowles等人[26]采用自適應網格來存放得到的非支配向量.Yang等人[27]利用網格技術應用于進化算法求解高維多目標優化問題.但是，這些網格方法本質都是以解空間中的個體為對象進行計算，不一定能保證算法的收斂，從而影響算法的效果[28].

本文利用網格同時表征收斂性與分布性的特性，通過坐標映射，利用對個體在網格坐標系中占優情況進行排序，結合個體與近似最優邊界的歐氏距離，提出了一種新的gBest，pBest選取策略，結合粒子群優化算法，提出了一種基于網格排序的多目標粒子優化算法.

1 相關工作

1.1 多目標優化問題

一個典型的多目標優化問題包含多個目標同時優化，不失一般性，對于一個最小化的多目標優化問題有表達式：

X=(X1,X2,…,Xn)T

F:Ω→M，
fi:Ω→n.

其中,i=1,2,…,M，F(X)是目標函數；X為決策向量，Ω為可行解集；n為決策空間，M為目標空間.f:n→M為目標映射函數.

1.2 粒子群優化算法

在粒子群算法中，每個粒子代表1個潛在的解，粒子在解空間中根據個體歷史最優粒子與全局最優粒子的飛行方向通過更新迭代逐漸靠近最優解.

將粒子群優化算法應用于多目標優化問題具有一定優勢：

1) 與遺傳算法等進化算法類似，粒子群算法也是通過規模較大的個體并行地在解空間上對非劣解進行搜索；

2) 由于粒子群是跟隨自身最優粒子與全局最優粒子的方向，具有一定“記憶”功能，因此，具有較高的運行速度與計算效率.一類多目標粒子優化算法如圖1所示：

Fig. 1 A framework of MOPSO圖1 一類多目標粒子群優化算法框架

從圖1中可以看出，多目標粒子群算法相對于單目標的粒子群算法來說，多出了外部檔案集的構造與維護，另外在gBest與pBest的選取上面具有完全不同的機制.由于粒子群固有的跟蹤特性，如果直接套用原來單目標粒子群算法的最優粒子選擇機制，將會使粒子跟蹤非支配解，從而使得算法收斂于非劣解的局部范圍而難以到達真實最優邊界.因此在將粒子群算法應用于多目標優化問題時，必須要解決全局最優位置與自身最優位置的選取問題.另一方面，對于外部檔案集來說，擁擠、無序的非劣解使得算法的輸出極不均勻，影響了實際應用的效果.基于以上分析，本文將從最優粒子選取機制、外部檔案集的更新維護等方面展開.

2 基于網格排序的MOPSO算法

2.1 網格坐標與網格排序

2.1.1 網格坐標系

在多目標優化問題中，空間中的個體經歷了從決策空間Ω?n到目標空間Π?r的轉換，如一個多目標優化問題的解X*∈P*(決策空間)或者Y*=minf(X*)(目標空間).圖2展示了一個典型的空間轉換(對于最小化問題f1(x)=x2，f2(x)=(x-2)2，x∈).

Fig. 2 A typical space-shifting in MOP圖2 多目標優化中一個典型的空間轉換

在決策空間中，利用各種方法(占優、支配)，通過更新迭代求解.不管是在目標空間還是決策空間，都是基于笛卡兒坐標系(Cartesian coordinate system).本文利用網格的方法，將決策空間進行劃分，同時將多目標優化問題的空間從笛卡兒坐標系映射到網格坐標系，將個體的數值坐標映射為網格坐標.下面對此進行描述.

定義1. 網格坐標的上下邊界.設在決策空間中，第m個目標上函數的最小值、最大值分別為minfm(X),maxfm(X)，則在第m個目標上網格上下邊界um,lm為

(2)

(3)

其中，c為網格坐標的劃分數，這里根據種群大小來決定取值.

利用定義1的上下邊界，結合個體在決策空間中的坐標可得到個體在網格坐標系中的坐標.

定義2. 網格坐標.設fm(X)為個體Xi在第m個目標上的函數值，對應的網格坐標為

(4)

Fig. 3 A case of mapping from decision space to grid space圖3 決策空間到網格空間的映射實例

從圖3可以看出，與笛卡兒坐標系類似，網格坐標系可以反映個體的分布情況；另一方面，在網格坐標系中個體的密度信息同時被反映出來.這是將坐標系轉為網格的重要因素.

2.1.2 網格排序

如引言所述，多目標優化問題的一個重點與難點是解空間中個體優劣的判斷，由于進化算法的尋優是通過各個體的更新迭代進行，個體的優劣直接影響算法的效果.為此，本文借鑒Pareto支配的概念，在網格坐標系中，通過構造整體的累加函數對個體的支配關系進行排序，得到整個解空間中個體的優劣關系.先介紹Pareto支配的定義.

定義3. Pareto支配.對于任意2個個體x,y∈f以及對應的目標向量F(x)，F(y)∈M，x支配y(xy)當且僅當?i∈{1,2,…,M},fi(x)≤fi(y)且?j∈{1,2,…,M},fj(x)

從定義3可以看出，Pareto支配是通過判斷個體在各目標上函數值大小進而判斷支配性.受此啟發，本文通過對解空間中個體優于其他個體的情況進行累加，得到個體的全局網格排序.

定義4. 全局網格排序(global grid ranking,GGR).定義個體的全局網格排序為個體在網格坐標下，各目標上個體優于解空間內其他個體次數的和為

GGR(Xi)

(5)

其中，GGR(Xi)為個體Xi的全局網格排序，M為目標個數，Gm(Xi)為個體Xi在目標m上的網格坐標，find(·)函數為找出滿足條件(·)的個數.從式(5)可以看出，個體的全局網格排序值越大，支配的個體越多.例如在圖3中，個體p5的GGR值為8，支配了其他剩余個體.

在排序的過程中會遇到全局網格排序值相同的情況，我們通過接下來的策略進行解決.

2.2 分布性保持策略

多目標優化問題的目標之一是希望得到的解盡可能多且均勻分布于最優邊界，解的分布性也是衡量算法優劣的一個方面[29].

如前所述，網格坐標不僅能反映個體在解空間中的分布情況，還能通過網格內個體的數量來判斷個體的聚集情況；從優化角度來說，既能反映算法的收斂性，又能反映解分布的多樣性.在網格坐標系中，如果網格中會遇到個體在同一個網格中，說明這些個體密度值較大，分布性較差.本文通過定義混合網格距離衡量此情況下個體的優劣.

定義5. 混合網格距離(hybrid grid distance,HGD).定義個體到所在網格的最小邊界點的歐氏距離作為網格混合網格距離來判斷同一網格內個體的優劣：

HGD(Xi)=

(6)

其中，fm(Xi)為個體Xi的實際函數值，Gm(Xi)為個體Xi的網格坐標.個體的混合網格距離越小，說明離實際最優邊界越近*對于最小化的優化問題，真實最優邊界靠近坐標原點，因此到網格左下角的距離能近似地反映個體到真實最優邊界的距離.，在排序值相同的情況下應當被優先選取.在圖4中，個體p3,p4在同一網格內，其排序值相同，但是從圖4中可以明顯看出，p3的混合網格距離小于p4，說明p3個體離真實最優邊界近，在這種情況下p4應該被排除.

Fig. 4 A case of hybrid grid distance圖4 一個混合網格距離實例

2.3 最優個體選取及外部檔案集維護

2.3.1 最優個體選取

如引言所述，pBest,gBest是粒子群優化算法中2個非常重要的參數，決定著整個種群的飛行方向，直接影響整個算法的收斂效果.對于pBest的選擇較簡單，主流的研究都是基于Pareto支配關系[30]，在當前粒子位置與個體歷史最優位置中選取非支配的粒子作為pBest，如果互不支配，則在當中隨機選取；gBest的選取則相對復雜，許多學者也對此進行了研究，主要有3類方法：

1) 隨機選擇[8].對于存儲于外部檔案集的非支配個體來說，隨機選取一個個體作為群體的gBest是最簡單的方法，容易出現在粒子集中的區域選擇概率大，不利于粒子在最優邊界的分布，降低了群體的多樣性.

2) 聚集密度法[31-32].計算當前粒子與外部檔案集中非劣解的歐氏距離，選取其中距離最小的粒子作為gBest.

3) Mostaghim[33]利用構造的函數sigma計算各粒子的值.計算該粒子的sigma值與外部檔案集所有成員sigma值之間的距離，選擇距離最小的外部檔案集中的成員作為該粒子的gBest.當解集中的成員過于擁擠時，sigma方法會增加算法的選擇壓力.

本文從粒子的全局網格排序、混合網格距離出發，提出一種新的簡潔高效的gBest，pBest計算方法.從2.1節、2.2節的分析可以看出，對于具有最大全局網格排序值的個體來說，其支配解空間中其他剩余個體將此個體選為gBest能使算法獲得較好的收斂性；如果多個個體同時具有最大網格排序值，則利用定義5的混合距離選取距離最優邊界最近的個體作為算法的gBest.

對于pBest的選取相對簡單，比較當前粒子與歷史最優粒子的全局網格排序，選取排序值較大者作為pBest.與gBest選取類似，如果兩者排序值相同，則利用混合距離篩選.

依據“全局網格排序為主，混合網格密度為輔”與最優粒子(gBest，pBest)選取策略，基于網格排序的多目標粒子群算法具有與單目標粒子群算法媲美的高效率，只需判斷單個排序值與密度信息，算法收斂速度快且能獲得分布性較好的最優解集.

2.3.2 外部檔案集的維護

保存與維護非支配解是多目標粒子群算法的重要部分，一般處理方法是建立一個外部檔案集用來存放獲得的非劣解.當非劣解集的數量達到規定值時，需要對其進行維護，一方面提高算法搜索效率，另一方面維護gBest的多樣性，從而為種群的進化提供更大的搜索空間.為粒子選擇合適的gBest能增加外部檔案集的多樣性，兩者互相促進，獲得更加均勻的最優邊界集.

本文將外部檔案集大小設定為N,N為種群大小，先利用混合網格距離(式(6))排除掉同一網格中的其他粒子，再利用2.2節的混合網格距離與2.1.2節的粒子全局網格排序信息(定義3)，每次取剩余個體降序排列的前50%(N2)加入外部檔案集.由于外部檔案集中整個群體的分布已發生改變，所以每次需重新計算綜合排序值(定義3)，再根據得到的綜合排序值排序，取得N，得到整個算法的最優邊界值.

2.4 算法流程

根據標準粒子群優化算法的框架流程，結合全局余量排序策略，GrRMOPSO算法描述如下：

算法1. GrRMOPSO.

① 初始化:種群大小N、目標個數M；

② for 種群中的粒子i隨機產生粒子的速度與位置； 網格空間映射； 評估；

end for

③ 更新外部檔案集；

④ fort=1 to 最大迭代次數

for 種群中的粒子i選出含多個粒子的網格，利用式(6)排除掉網格中較劣的個體； 計算粒子的全局網格排序(式(5))； 選取gBest，pBest； 更新個體的位置與速度； 取剩余個體降序排列的前50%(N/2)加入外部檔案集；

end for

for 外部檔案集中每個粒子j選出含多個粒子的網格，利用式(6)排除掉網格中較劣的個體； 計算粒子的全局網格排序(式(5))； 利用2.3節策略得到外部檔案集；

end for

更新外部檔案集;

t←t+1;

end for

2.5 算法復雜度分析

算法的時間復雜度表現為算法的執行時間隨著輸入規模的增長而增長的數量級大小，在很大程度上反映出一個算法的優劣程度.在本文所提的基于網格排序的多目標粒子群算法中，設種群規模為N、目標個數為M，主要步驟的時間復雜度如表1所示：

可以看出，算法的復雜度主要在排序與外部檔案集的維護計算過程中，整個算法的復雜度為O(MN2)，與NAGA-Ⅱ[11]，MOPSO[8]等優秀的多目標算法一致.

3 實驗對比及分析

3.1 測試函數

為了驗證算法的有效性，本節選取了4個代表性的多目標優化算法(NSGA-Ⅱ[11],σMOPSO[33],cdMOPSO[34],D2MOPSO[35])，并在一些標準測試函數上進行對比實驗，包括KUR[36],ZDT{1,2}[37],DTLZ{1,2,5}[38].選取的這些測試函數涵蓋了各種多目標優化問題，包括線性、非凸函數等，采用的對比算法的參數以及函數分別如表2、表3所示.在比較實驗中,各對比算法的種群大小均設置為N=100，外部檔案的最大容量均設為E=100，最大迭代次數為Tmax=300.

Table 2 Parameters for Candidates表2 5種對比算法采用的參數

3.2 評價標準

通常來說，對一個算法的評估主要從收斂性與解的多樣性2方面考慮.本文采用逆世代距離(inverted generational distance,IGD)[39]與間距(spacing,S)[40]對算法進行評價.在這2個指標的基礎上，本文采用錯誤率(error ratio,ER)[41]對得到的解的質量進行評估.

1) 逆世代距離IGD.其表示為當前搜索到的非支配解同Pareto前端的距離：

IGD(P,P*)

(7)

Table 3 Benchmark Functions表3 測試函數

2) 間距S.描述解向量的分布性，通過與收斂到實際Pareto前端的比較從而對算法搜索到的非支配解的分布程度進行度量，計算方法為

(8)

3) 錯誤率ER.描述算法搜索到的非支配解的錯誤率，計算方法為

(9)

對于式(9)，如果第i個解是實際Pareto前端集合內的元素，則ei=0，否則ei=1.

3.3 實驗結果及分析

在進行詳細的統計數據分析之前，對各算法得到的解進行形象化展示是非常有意義的.表4、表5展示了各對比算法得到的非劣解集與真實Pareto前端的對比.

Table 4 Non-Inferior Solutions Obtained by Candidates on Bi-Objective Functions表4 5種對比算法在雙目標測試函數上的非劣解集

· Ture Pareto front; * Instance

Table 5 Non-Inferior Solutions Obtained by Candidates on Tri-Objective Functions表5 5種對比算法在3目標測試函數上的非劣解集

· Ture Pareto front; * Instance

從表4、表5中可以看出，各算法在簡單的雙目標問題上都能取得較好的效果，比較接近真實Pareto前端，說明這些算法能輕松應對簡單的優化問題，特別是在KUR測試函數上，各對比算法都取得了分布較均勻的解；在3目標優化問題上，對比算法效果稍微有點區別，NSGA-Ⅱ在DTLZ1問題上有一部分解偏離了真實Pareto前端.從總體上看，所提算法不論是在收斂性還是解的分布性上都具有優勢.

下面從統計數據的角度進一步說明.為了減少隨機性的影響，各算法獨立運行30次.圖5以盒圖(boxplot)的形式展示了各算法在IGD指標上的對比情況，表6、表7展示了各算法在Spacing指標、ER指標上的運行情況.

Fig. 5 IGD metric results on test suites圖5 5種算法在不同測試函數的IGD指標

InstanceNSGA-ⅡσMOPSOcdMOPSOD2MOPSOGrRMOPSOMeanStdMeanStdMeanStdMeanStdMeanStdKUR1.72E-016.77E-028.33E-022.98E-033.42E-021.19E-038.76E-031.07E-042.11E-031.34E-04ZDT19.70E-023.22E-025.63E-021.27E-036.39E-012.02E-016.11E-022.43-E037.76E-022.76E-02ZDT25.22E-023.10E-038.94E-024.30E-023.18E-029.10E-037.23E-032.06E-037.12E-032.33E-03DTLZ13.27E-018.90E-023.90E-021.45E-028.01E-023.89E-029.45E-025.33E-031.22E-016.39E-03DTLZ29.42E-022.27E-028.70E-024.12E-029.02E-023.20E-023.21E-031.22E-033.74E-031.37E-03DTLZ55.08E-022.19E-024.53E-021.28E-025.22E-022.32E-025.36E-023.12E-024.29E-021.19E-02

Table 7 Spacing Metric Results表7 5種算法上的Spacing指標

從這些統計數據可以看出，GrRMOPSO在大部分指標上占有優勢，說明了所提算法的有效性.

3.4 網格劃分數分析

在GrRMOPSO中存在一個需要用戶調整的參數網格劃分數c，c的大小對算法存在一定影響，如果c值過大，解空間劃分過細，不能體現網格劃分的優勢；c值過小的話同一網格內粒子過多，會給后續的選擇帶來較大壓力.因此，本節討論c值對算法性能的影響.

在KUR測試函數上采用IGD指標，驗證c值從5～20之間的取值對算法性能的影響(其他參數保持不變)，如圖6所示：

Fig. 6 IGD values with different numbers of c on KUR圖6 不同網格劃分數c在KUR函數上對應的IGD值

從圖6中可以看出，在網格劃分數小于9的時候對算法效果影響較大，即較小的劃分數c會影響算法的性能，因為過多的粒子聚集在同一個網格內，給算法后續的選擇帶來較大壓力.

另一方面，GrRMOPSO主要是利用全局網格排序來判斷個體優劣進而引導算法尋優，不同的網格劃分數c影響了粒子的網格坐標，進而影響著算法的排序.本節特定劃分數c選取4個不同值分別為5,10,15,20，采用KUR作為測試函數，將排序形象化地進行展示.

為了保持對比的統一性，減少隨機性的誤差，在不同c值情況下，我們利用程序隨機產生一個初始種群，保存并固定為不同c值測試上的初始種群，利用粒子在解空間中的分布結合其排序值，得到不同迭代情況下排序策略對種群的引導情況，實驗結果如圖7所示.

從圖7中可以看出，當網格劃分數過小(c=5)，解空間中會存在過多相同排序值從而影響排序的效率，從另一方面驗證了網格劃分數的影響.另外，在c=10與c=20之間，c對排序值影響較小.

Fig. 7 A sketch map on ranking with different c (different colors represent different sort values)圖7 不同網格劃分數c對排序的影響示意圖(不同顏色代表不同的排序值)

4 結束語

本文從網格坐標出發，將決策空間進行映射，利用網格的同時表現收斂性與分布性的特點，利用個體對解空間中其他剩余粒子的占優情況，結合整個解空間中粒子的分布信息對粒子進行排序；提出了一種基于網格的距離計算方式，用于處理相同網格內多個粒子的情況；在此基礎上，提出了一種基于網格排序的多目標粒子群優化算法.通過分析與實驗可以得出：

1) 通過全局網格排序能夠較好地得到粒子的排序信息，進而引導算法收斂；

2) 網格劃分數對算法效果有一定影響，過小的網格劃分不利于算法的排序操作.

當前的基于網格排序的框架只是應用在低維(2維、3維)優化問題以及粒子群算法并取得了較好的效果，下一步的研究計劃將此框架擴展到高維多目標優化問題，畢竟高維優化問題對Pareto排序更為敏感.另外，將基于網格排序的機制應用于其他優秀的進化算法也是下一步即將開展的工作.

[1]Kennedy J, Eberhart R. Particle swarm optimization[C] //Proc of IEEE Int Conf on Neural Networks. Piscataway, NJ: IEEE, 1995: 1942-1948

[2]Li Jie, Zhang Junqi, Jiang Changjun, et al. Composite particle swarm optimizer with historical memory for function optimization[J]. IEEE Trans on Cybernetics, 2015, 45(10): 2350-2363

[3]Shou Yongyi, Li Ying, Lai Changtao. Hybrid particle swarm optimization for preemptive resource-constrained project scheduling[J]. Neurocomputing, 2015, 148: 122-128

[4]Chiou Juingshian, Tsai Shunhung, Liu Mingtang. A PSO-based adaptive fuzzy PID-controllers[J]. Simulation Modelling Practice and Theory, 2012, 26: 49-59

[5]Zhao Yulei, Guo Baolong, Wu Xianxiang, et al. Image reconstruction algorithm for ECT based on dual particle swarm collaborative optimization[J]. Journal of Computer Research and Development, 2014, 51(9): 2094-2100 (in Chinese)(趙玉磊, 郭寶龍, 吳憲祥, 等. 基于雙粒子群協同優化的 ECT 圖像重建算法[J]. 計算機研究與發展, 2014, 51(9): 2094-2100)

[6]Dujardin Y, Vanderpooten D, Boillot F. A multi-objective interactive system for adaptive traffic control[J]. European Journal of Operational Research, 2015, 244(2): 601-610

[7]Lee K-B, Kim J-H. Multiobjective particle swarm optimization with preference-based sort and its application to path following footstep optimization for humanoid robots[J]. IEEE Trans on Evolutionary Computation, 2013, 17(6): 755-766

[8]Coello C A C, Lechuga M S. MOPSO: A proposal for multiple objective particle swarm optimization[C] //Proc of the 2002 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2002: 1051-1056

[9]Xie Chengwang, Zou Xiufen, Xia Xuewen, et al. A multi-objective particle swarm optimization algorithm integrating multiply strategies[J]. Acta Electronica Sinica, 2015, 43(8): 1538-1544 (in Chinese)(謝承旺, 鄒秀芬, 夏學文, 等. 一種多策略融合的多目標粒子群優化算法[J]. 電子學報, 2015, 43(8): 1538-1544)

[10]Mao Chengying, Yu Xinxin, Xue Yunzhi. Algorithm design and empirical analysis for particle swarm optimization-based test data generation[J]. Journal of Computer Research and Development, 2014, 51(4): 824-837 (in Chinese)(毛澄映, 喻新欣, 薛云志. 基于粒子群優化的測試數據生成及其實證分析[J]. 計算機研究與發展, 2015, 51(4): 824-837)

[11]Coello C A C, Lechuga M S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197

[12]Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization[C] //Proc of the Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Berlin: Springer, 2001: 95-100

[13]Deb K. Multi-objective genetic algorithms: Problem difficulties and construction of test problems[J]. Evolutionary Computation, 1999, 7(3): 205-230

[14]Laumanns M, Thiele L, Deb K, et al. Combining convergence and diversity in evolutionary multiobjective optimization[J]. Evolutionary Computation, 2002, 10(3): 263-282

[15]Batista L S, Campelo F, Guimar?es F G, et al. Pareto coneε-dominance: Improving convergence and diversity in multiobjective evolutionary algorithms[C] //Proc of Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2011: 76-90

[16]Zou Xiufen, Chen Yu, Liu Mingzhou, et al. A new evolutionary algorithm for solving many-objective optimization problems[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2008, 38(5): 1402-1412

[17]Marler R T, Arora J S. The weighted sum method for multi-objective optimization: New insights[J]. Structural and Multidisciplinary Optimization, 2010, 41(6): 853-862

[18]Zhang Qingfu, Li Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans on Evolutionary Computation, 2007, 11(6): 712-731

[19]Asafuddoula M, Ray T, Sarker R. A decomposition based evolutionary algorithm for many objective optimization[J]. IEEE Trans on Evolutionary Computation, 2015, 19(3): 445-460

[20]Balling R, Wilson S. The maxi-min fitness function for multi-objective evolutionary computation: Application to city planning[C] //Proc the 2001 Annual Conf on Genetic and Evolutionary Computation (GECCO’2001). New York: ACM, 2001: 1079-1084

[21]Wei Lingyun, Zhao Mei. A niche hybrid genetic algorithm for global optimization of continuous multimodal functions[J]. Applied Mathematics and Computation, 2005, 160(3): 649-661

[22]Pulido G T, Coello C A C. Using clustering techniques to improve the performance of a multi-objective particle swarm optimizer[C] //Proc of the 2004 Annual Conf on Genetic and Evolutionary Computation (GECCO’2004). Berlin: Springer, 2004: 225-237

[23]Luo Biao, Zheng Jinhua, Xie Jiongliang, et al. Dynamic crowding distance? A new diversity maintenance strategy for MOEAs[C] //Proc of the 4th Int Conf on Natural Computation. Piscataway, NJ: IEEE, 2008: 580-585

[24]Wang Yaonan, Wu Lianghong, Yuan Xiaofang. Multi-objective self-adaptive differential evolution with elitist archive and crowding entropy-based diversity measure[J]. Soft Computing, 2010, 14(3): 193-209

[25]Leong W F, Yen G G. PSO-based multiobjective optimization with dynamic population size and adaptive local archives[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2008, 38(5): 1270-1293

[26]Knowles J, Corne D. Properties of an adaptive archiving algorithm for storing nondominated vectors[J]. IEEE Trans on Evolutionary Computation, 2003, 7(2): 100-116

[27]Yang Shengxiang, Li Miqing, Liu Xiaohui, et al. A grid-based evolutionary algorithm for many-objective optimization[J]. IEEE Trans on Evolutionary Computation, 2013, 17(5): 721-736

[28]Li Bingdong, Li Jinlong, Tang Ke, et al. Many-objective evolutionary algorithms: A survey[J]. ACM Computing Surveys (CSUR), 2015, 48(1): 1-13

[29]Adra S F, Fleming P J. Diversity management in evolutionary many-objective optimization[J]. IEEE Trans on Evolutionary Computation, 2011, 15(2): 183-195

[30]Alvarez-Benitez J E, Everson R M, Fieldsend J E. A MOPSO algorithm based exclusively on pareto dominance concepts[C] //Proc of Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2005: 459-473

[31]Raquel C R, Naval Jr P C. An effective use of crowding distance in multiobjective particle swarm optimization[C] //Proc of the 7th Annual Conf on Genetic and Evolutionary Computation. New York: ACM, 2005: 257-264

[32]Dai Cai, Wang Yuping, Ye Miao. A new multi-objective particle swarm optimization algorithm based on decomposition[J]. Information Sciences, 2015, 325: 541-557

[33]Mostaghim S, Teich J. Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO)[C] //Proc of 2003 IEEE Swarm Intelligence Symp. Piscataway, NJ: IEEE, 2003: 26-33

[34]Raquel C R, Naval Jr P C. An effective use of crowding distance in multiobjective particle swarm optimization[C] //Proc of the 7th Annual Conf on Genetic and Evolutionary Computation. New York: ACM, 2005: 257-264

[35]Al Moubayed N, Petrovski A, McCall J. D2MOPSO: MOPSO based on decomposition and dominance with archiving using crowding distance in objective and solution spaces[J]. Evolutionary Computation, 2014, 22(1): 47-77

[36]Kursawe F. A variant of evolution strategies for vector optimization[M]. Berlin: Springer, 1991: 193-197

[37]Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195

[38]Deb K, Thiele L, Laumanns M, et al. Scalable multi-objective optimization test problems[C] //Proc of 2002 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2002: 825-830

[39]Zitzler E, Thiele L, Laumanns M, et al. Performance assessment of multiobjective optimizers: an analysis and review[J]. IEEE Trans on Evolutionary Computation, 2003, 7(2): 117-132

[40]Schott JR. Fault tolerant design using single and multicriteria genetic algorithm optimization[D]. Boston: Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, 1995

[41]Van Veldhuizen DA. Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations[D]. Ohio: Department of Electric Computer Engineer, Air Force Institute of Technology, 1999

Multi-Objective Particle Swarm Optimization Based on Grid Ranking

Li Li, Wang Wanliang, Xu Xinli, and Li Weikun

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023)

In multi-objective evolutionary algorithms, the majority of researches are Pareto-based. However, the efficiency of Pareto optimality in objective space will deteriorate when there are numerous weak dominance relations. Aiming at this problem, this paper presents a framework of grid-based ranking. By integrating gird strategy, which features both convergence and distribution, with the particle swarm optimization (PSO), we propose a novel grid-based ranking multi-objective particle swarm optimization (MOPSO). Unlike the strategy of Pareto-based dominance which conducts a pairwise comparison between individuals, the grid-based ranking mechanism combines the individual dominance information in the entire solution space, and takes advantage of this information to sort. As a result, we gain the merits of the relationship between individuals in the population effectively and efficiently. By incorporating the distance between particles and approximate optimal front, we reinforce the judgement of the merits of the relationship among particles in the solution space. The experimental assessment indicates that the proposed method in this paper has relative advantages in both convergence and distribution. On this basis, we discuss the influence of grid partition on efficiency in terms of the distribution of ranks over the process of evolutionary, which verifies the efficiency of the algorithm from the other aspect.

multi-objective optimization; evolutionary algorithm; particle swarm optimization (PSO); grid; ranking

Li Li, born in 1986. PhD candidate of Zhejiang University of Technology, Hangzhou, Zhejiang, China. Student member of CCF. His main current research interests include evolutionary computation, scheduling optimization, and multi-objective optimization.

Wang Wanliang, born in 1957. Professor and PhD supervisor in Zhejiang University of Technology, Hangzhou, Zhejiang, China. His main research interests include intelligent computing, scheduling optimization.

Xu Xinli, born in 1977. PhD. Associate professor in Zhejiang University of Technology, Hangzhou, Zhejiang, China. Her main research interests include intelligent computing, scheduling optimiza-tion, and wireless sensor networks (xxl@zjut.edu.cn).

Li Weikun, born in 1990. Master candidate of Zhejiang University of Technology, Hangzhou, Zhejiang, China. Student member of CCF. His main research interests include evolutionary computation and multi-objective optimization (lwk_zjut@hotmail.com).

2016-02-17；

2016-06-30

“十二五”國家科技支撐計劃基金項目(2012BAD10B01)；國家自然科學基金項目(61379123) This work was supported by the National Science & Technology Pillar Program During the Twelfth Five-Year Plan Period (2012BAD10B01) and the National Natural Science Foundation of China (61379123).

王萬良(zjutwwl@zjut.edu.cn)

TP18