基于速度交流的多種群多目標粒子群算法研究

劉 彬, 劉澤仁, 趙志彪, 李 瑞, 聞 巖, 劉浩然

(1.燕山大學 電氣工程學院, 河北 秦皇島 066004； 2.燕山大學 信息科學與工程學院, 河北 秦皇島 066004；3.燕山大學 機械工程學院, 河北 秦皇島 066004)

1 引 言

科學研究與工程實踐中存在很多個互相沖突的目標,多目標優(yōu)化就是在這些目標中尋找“折中”的方案[1～2]?；谌后w搜索的進化方法可以并行處理多個目標函數(shù),適用于求解多目標優(yōu)化問題。粒子群優(yōu)化算法(particle swarm optimization,PSO)便是一種基于鳥類覓食行為的群體智能優(yōu)化算法,其結構簡單,參數(shù)設置少,收斂速度快,被廣泛用于解決多目標優(yōu)化問題[3]。但粒子群算法在解決多目標優(yōu)化問題時也面臨一些問題：其快速收斂特性易使種群陷入局部最優(yōu)Pareto前沿；單一的搜索模式易導致粒子收斂精度不高。因此,一些學者對多目標粒子群(multi-objective particle swarm optimization,MOPSO)算法提出了改進：Yang J M[4]等提出自適應混沌MOPSO優(yōu)化算法,利用一種新型動態(tài)加權方法選擇全局最優(yōu)粒子；謝承旺[5]等提出應用檔案精英學習和反向學習的MOPSO算法,應用檔案精英學習增強算法的全局搜索能力,并使用動態(tài)反向學習機制構成變異算子,增加粒子跳出局部最優(yōu)的可能性?；趩畏N群的優(yōu)化算法雖然在一定程度上提高了MOPSO算法性能,但由于算法單一的搜索模式易使每個粒子趨向于種群的“社會部分”,導致解的多樣性降低,搜索性能差[6]。有學者提出將算法的單一種群拆分成多個子種群的方法,采用多個種群并行搜索,以提高種群的多樣性和算法的收斂能力：劉衍民[7]等提出基于動態(tài)多種群的MOPSO算法,采用動態(tài)的方法構建多個子種群并行搜索,并用K-均值聚類算法確定子種群的搜索行為,提高粒子的多樣性以及跳出局部最優(yōu)的能力；劉慧慧[8]等提出基于多種群協(xié)同的MOPSO算法,將多目標優(yōu)化問題分解為多個單目標優(yōu)化問題,每個種群優(yōu)化一個目標,同時將非劣解存儲在外部檔案。

基于以上分析,采用多種群的優(yōu)化算法可以提高粒子的搜索能力,探索更廣闊的解空間,因此,本文提出一種基于速度交流的多種群MOPSO算法(research on multi-population MOPSO algorithm based on velocity communication,MVCMOPSO)。算法將單種群劃分為多個子種群并引入速度交流機制,子種群間通過速度交流分享信息,使粒子飛向不同的方向,探索更多的未知領域,改善粒子單一的搜索模式,提高粒子全局搜索能力,得到質量更好的解。此外,算法采用混沌映射優(yōu)化慣性權重,應用到粒子的速度和位置更新,提高粒子搜索的遍歷性和全局性。粒子在算法運行后期易出現(xiàn)“聚集”現(xiàn)象,為避免粒子陷入局部最優(yōu)Pareto前沿,對各子種群執(zhí)行不同的變異操作,并將算法得到的非劣解存儲在外部檔案[9]。仿真實驗采用多目標測試問題和先進多目標優(yōu)化算法進行對比,實驗結果驗證了算法的有效性。

2 多目標優(yōu)化和粒子群算法

2.1 多目標優(yōu)化

以多目標最小化問題為例,具有n個決策變量、m個優(yōu)化目標的多目標問題[10]可以表示為：

(1)

式中：x=(x1,…,xn)∈X?Rn為n維的決策向量,X為n維的決策空間；y=(y1,…,ym)∈Y?Rm為m維的目標向量,Y為m維的目標空間。目標函數(shù)F(x)定義了m個由決策空間向目標空間的映射函數(shù)；gi(x)≥0代表q個不等式約束；hj(x)=0 代表p個等式約束。

在多目標優(yōu)化問題中,并不存在一個能夠使所有目標值同時達到最優(yōu)的解,而是得到一個Pareto最優(yōu)解集合,在此給出幾個常用的重要定義。

定義1(Pareto支配)[11]稱決策向量xv=(v1,v2,…,vn)對xu=(u1,u2,…,un)是Pareto支配的,記為xv

定義2(Pareto最優(yōu)解集)[11]如果P*={x∈Rn|x′∈Rn,x′

定義3(Pareto前沿PF*)[11]Pareto解集在目標函數(shù)上的映射為PF*={F(x)|x∈P*},映射之后的集合稱為Pareto前沿。

由定義可知,Pareto支配關系決定了多目標優(yōu)化算法迭代過程中個體的優(yōu)劣；Pareto最優(yōu)解集是算法運行結束后所有非支配解集的集合；Pareto前沿是最優(yōu)解集對應的目標函數(shù)映射值的集合。

2.2 粒子群算法

PSO是一種基于群體智能的優(yōu)化算法,每個粒子由速度和位置2個要素構成[12]。速度決定粒子的飛行方向和運動步長,它的改變會導致位置也發(fā)生相應的改變。在第t+1次迭代時,種群中粒子i的速度和位置更新公式為：

vi,d(t+1)=wvi,d(t)+c1r1(pi,d(t)-

xi,d(t))+c2r2(pg,d(t)-xi,d(t))

(2)

xi,d(t+1)=xi,d(t)+vi,d(t+1)

(3)

式中：w為慣性權重,vi,d(t)和xi,d(t)分別為第t次迭代時粒子i的第d維變量的速度和位置,pi,d(t)和pg,d(t)分別為第t次迭代時粒子i的第d維變量歷史最優(yōu)和全局最優(yōu)的位置,c1和c2為學習因子,r1和r2為[0,1]區(qū)間上均勻分布的隨機值。

3 基于速度交流的多種群MOPSO算法

MVCMOPSO算法將單種群劃分為多個子種群,采用速度交流機制實現(xiàn)粒子速度信息共享,使粒子不僅能探索更多的未知領域,還會朝著更好的方向進化；加入混沌序列優(yōu)化慣性權重,進一步提高粒子全局搜索能力；為減少粒子陷入局部最優(yōu)Pareto前沿的可能性,算法在運行后期對每個子種群實行不同的變異操作。

3.1 多種群速度交流機制

大多數(shù)MOPSO算法采用單一種群的搜索模式,所有操作只限定在一個種群中進行,如果個體趨向于一致,算法易陷入局部最優(yōu)Pareto前沿,導致解的分布性比較差。采用多種群進化能很好地提高粒子搜索能力,降低陷入局部最優(yōu)的可能性[13]。粒子群算法中的多種群策略大部分是基于粒子間位置信息的共享,很少考慮粒子的速度信息。本文則將速度信息作為種群間的媒介進行信息交換。根據(jù)種群間的速度信息交流機制進行子種群的劃分,即種群數(shù)量固定,速度信息動態(tài)交流,從而對子種群進行規(guī)劃,有效實現(xiàn)子種群搜索領域的分割,從而增強算法的探索與開發(fā)能力。速度信息交流機制如圖1所示。

圖1 多種群速度信息交流Fig.1 Multi-population speed information exchange

MVCMOPSO根據(jù)速度交流機制選擇合適的種群數(shù)量,將單種群等分為4個子種群P1、P2、P3、P4,設定P1和P2為基本子種群,執(zhí)行標準的PSO搜索行為；P1和P2把各自種群的速度信息分享給子種群P3,進而調整自身種群的運動行為,探索不同于P1和P2的搜索領域；子種群P1、P2和P3再分別將各自種群速度信息分享給子種群P4,以影響子種群P4的搜索行為,使整個粒子群飛向更廣闊的解空間。該方法使4個子種群具有各自的搜索行為,改善了粒子單一的搜索模式,既能滿足子種群間自由競爭,又可以實現(xiàn)子種群間的信息交流,有效提高了粒子的全局搜索能力。

(4)

(5)

式中：vi,d(t)和xi,d(t)分別為第t次迭代時粒子i的第d維變量的速度和位置,w(t)為采用混沌映射優(yōu)化的慣性權重。

(6)

(7)

(8)

(9)

為更清晰地解釋速度交流機制的運行,以二維最小值目標為例,從4個子種群中各選擇一個粒子作為代表,假設分別為x1、x2、x3、x4,對應的任意給定速度分別為v1、v2、v3,如圖2(a)所示。算法在第t次迭代時,利用速度交流機制得到的新的粒子速度分別為v1′、v2′、v3′、v4′,對應位置分別為x1′、x2′、x3′、x4′,算法最終目的是使粒子收斂于真實Pareto前沿。算法在第t+1次迭代時,粒子間再采用速度交流機制分享信息后迭代更新如圖2(b)所示,更新后的粒子速度分別為v1″、v2″、v3″、v4″,對應位置分別為x1″、x2″、x3″、x4″。由圖2可見,粒子間分享速度信息后,相互協(xié)調向著不同的方向運動,探索更多的未知領域,快速向真實Pareto前沿靠近,進一步實現(xiàn)全局搜索。

圖2 粒子協(xié)同進化Fig.2 Particle coevolution

將單種群等分為4個子種群P1、P2、P3和P4并引入速度交流機制,實現(xiàn)了子種群間的速度信息交流,使解空間得到合理有效的搜索規(guī)劃,改善種群的單一搜索模式,極大地提高了種群的全局探索和開發(fā)能力。

3.2 混沌映射優(yōu)化慣性權重

MOPSO算法常因收斂快速而陷入局部最優(yōu),粒子不能有效探索整個解空間?；煦缦到y(tǒng)具有遍歷性、隨機性和穩(wěn)定性的特點[14],為進一步提高算法搜索性能,促進粒子可以在整個解空間進行探索,本文采用混沌映射來優(yōu)化粒子速度,更新式(4)和式(6)中的慣性權重。利用Logistic映射來產生混沌變量：

zt+1=μzt(1-zt)

(10)

式中：μ為控制參數(shù)。設0≤z0≤1,t為當前迭代次數(shù),t=0,1…；μ=4時系統(tǒng)完全處于混沌狀態(tài)。對于Logistic映射,初值z0不能取0、0.25、0.5、0.75和1這5個值,因為這5個取值都會使序列陷入不動點0或0.75。

利用式(10)優(yōu)化慣性權重,將優(yōu)化結果映射到區(qū)間[wmin,wmax]中：

w(t)=wmin+(wmax-wmin)zt

(11)

式中[wmin,wmax]為慣性權重的取值范圍,一般取[0.4,0.9][15]。

再將優(yōu)化以后的慣性權重[式(11)]代入式(4)和式(6)中,使粒子具有遍歷性,提高粒子全局搜索能力。為說明混沌映射對慣性權重的優(yōu)化作用,圖3給出了慣性權重在100次迭代過程中的取值變化。由圖3可見,利用Logistic映射優(yōu)化的慣性權重數(shù)值變化不定(隨機性),但是取值在[0.4,0.9]區(qū)間(穩(wěn)定性),使慣性權重盡可能遍歷所有取值而又在給定范圍內,從而使粒子能夠更好地探索解空間。

圖3 混沌映射優(yōu)化慣性權重Fig.3 Chaotic map optimize inertia weight

3.3 多種變異協(xié)同操作

算法在運行后期,粒子運動速度逐漸減慢,搜索能力降低,易出現(xiàn)“聚集”現(xiàn)象,陷入局部最優(yōu)Pareto前沿。為降低粒子在算法后期陷入局部最優(yōu)的可能性,需添加擾動使粒子能夠及時跳出局部最優(yōu)繼續(xù)探索。本文利用變異機制對粒子施加擾動,考慮到各子種群的搜索模式不盡相同,以進化代數(shù)作為變異的觸發(fā)條件,對4個子種群同時進行4種不同的變異操作,使粒子分散并飛向不同的方向,進行不同路徑的搜索,增大粒子飛向更好解的概率。

設定多種變異觸發(fā)條件為Lt,當進化代數(shù)t

基本子種群P1的搜索模式采用標準粒子群的搜索模式,若使粒子跳出局部最優(yōu),變異程度應該大一些。本文選用反向學習變異[16]對粒子施加擾動,使粒子向著反方向進化,變異后的解可描述為：

(12)

基本子種群P2的搜索模式同樣采用標準粒子群的搜索模式,因此也宜采用變異程度較大的擾動方式。本文選用高斯變異[17],在原個體位置基礎上增加一個高斯分布隨機向量,變異后的解可描述為：

(13)

式中Gaussi(0,1)為服從均值為0,方差為1的高斯分布。

子種群P3的速度融合了基本子種群P1和P2的速度信息,從而攜帶了前兩者的變異信息,因此只需進行程度較小的變異即可。本文選用柯西變異[18],使粒子在原位置基礎上進行小幅度變化,變異后的解可描述為：

(14)

(15)

子種群P4的速度同時受到P1、P2和P3速度的影響,攜帶的變異信息比較多,因此宜采用最小的擾動方式。本文選用非均勻變異[19],變異后的解為：

(16)

式中：

UB和LB分別為子種群P4粒子的位置上限和下限;T為最大迭代次數(shù),b為系統(tǒng)參數(shù)(決定變異運算的非均勻度)。非均勻變異步長Δ(t,y)是一種自適應調節(jié)步長的變異算子,在算法運行后期達到變異觸發(fā)條件后,搜索半徑依概率減小,到算法臨近結束僅在當前解的狹小鄰域中搜索,這樣能夠保證對最優(yōu)解的準確定位,減小從當前鄰域中“逃逸”的概率。

不同的子種群采用不同的變異方式,搜索能力也不同,共同協(xié)助種群在算法后期跳出局部最優(yōu)Pareto前沿,飛向不同的方向繼續(xù)對解空間進行探索。

3.4 算法步驟

MVCMOPSO算法的步驟如下：

Step1：參數(shù)初始化：種群大小為4 N,初始化外部檔案A(0)=Φ,設置最大容量與種群規(guī)模相同為4 N；迭代次數(shù)t=0;迭代次數(shù)為Gmax；

Step2：初始化4個大小為N的子種群,根據(jù)Pareto支配,將非支配解加入A(0),形成A(1)；

Step3：根據(jù)擁擠距離,選擇每個粒子的全局最優(yōu)領導粒子：在A(t)中隨機選取2個粒子,選擇擁擠度距離大的粒子作為全局最優(yōu)領導粒子；

Step4：令t=t+1,進入循環(huán)迭代；

Step5：判斷是否達到變異條件：若迭代次數(shù)t

Step6：將多種群合并為單種群,并將單種群中的個體與A(t)中的非劣解進行Pareto支配比較,如果不被A(t)中的非劣解支配,則加入到A(t)中,判斷A(t)中的解數(shù)量是否大于4 N,如果是,則刪除擁擠距離小的多余的解；

Step7：根據(jù)Pareto支配分別更新子種群粒子歷史最優(yōu)值：若當前解支配歷史最優(yōu)解,則令當前解替代粒子歷史最優(yōu)解；若歷史最優(yōu)解支配當前解,則粒子歷史最優(yōu)解不變,若兩者互不支配,則隨機選擇一個作為粒子歷史最優(yōu)解；更新粒子全局最優(yōu)解；

Step8：終止條件判定：若t

3.5 計算復雜度分析

假設優(yōu)化問題含有m個目標,種群大小為4 N,外部檔案最大容量為A*。種群函數(shù)評價復雜度為O(4mN),擁擠度距離的復雜度為O(mA*logA*)(假設使用快速非支配排序算法),種群和檔案進行Pareto支配比較。如果外部檔案最大容量與種群數(shù)量相同,則MVCMOPSO的計算復雜度為O(16mN2)。

4 仿真驗證與分析

4.1 性能評價指標和實驗參數(shù)設定

為驗證本文提出算法的有效性,將MVCMOPSO與NSGA-Ⅱ[20]、SPEA2[21]、AbYSS[22]、MOPSO[11]、SMPSO[23]、GWASF-GA[24]先進算法進行對比。選取ZDT系列測試函數(shù)[25]ZDT1、ZDT2、ZDT3、ZDT6,以及Schaffer[26]、Kursawe[27]、Viennet2和Viennet3[28]測試函數(shù)進行測試和對比,如表1所示。

表1 多目標優(yōu)化測試函數(shù)Tab.1 Multi-objective optimization test functions

在求解不同多目標優(yōu)化問題時,通過收斂性和多樣性評估指標,驗證多目標優(yōu)化算法的性能。為更清晰定量評價不同的多目標優(yōu)化算法的性能,選用3個指標IGD[29](Inverse Generational Distance,反世代距離)、GD[30](Generational Distance,世代距離)、SP[31](Spread,分布性)綜合評價算法的收斂性和多樣性。

1) IGD指標：IGD可用來綜合評價算法的收斂性和多樣性。IGD指標定義為：

(17)

式中：di為真實前沿PFtrue與得到的Pareto最優(yōu)解之間最短歐氏距離；n為外部檔案中粒子個數(shù)。IGD值越小,表明得到解集的收斂性和多樣性越好。

2) GD指標：GD可用來評價得到解集的收斂性。GD指標定義為：

(18)

式中：di為外部檔案中第i個粒子到真實前沿PFtrue最短歐氏距離,n為外部檔案中粒子個數(shù)。GD值越小,表明得到解集的收斂性越好。

3) SP指標：SP可用來評價得到解集的分布性,即均勻分布在真實Pareto前沿附近的特性。SP指標定義為：

(19)

對各個算法在同一測試問題上獨立運行30次并統(tǒng)計結果,對于兩目標測試函數(shù),種群規(guī)模設置為100,涉及到應用外部檔案的算法,外部檔案規(guī)模同樣設置為100,其他算法實驗參數(shù)按照對應的參考文獻設置。

對于三目標測試函數(shù),種群規(guī)模設置為200。多種變異操作觸發(fā)的迭代次數(shù)Lt設為100,迭代次數(shù)均為300。

4.2 實驗結果分析

7種算法的性能對比結果如表2～表4所示,其中粗體字表示所有對比算法在對應行測試問題中的最優(yōu)評價指標。

表2 7種算法IGD性能指標的均值結果Tab.2 Mean results of 7 algorithms IGD performance indicators

表3 7種算法GD性能指標的均值結果Tab.3 Mean results of 7 performance GD performance indicators

由表2可知,MVCMOPSO在8個測試問題中獲得2個最優(yōu)IGD值,其中在ZDT2測試問題中明顯優(yōu)于其他算法,NSGA-Ⅱ和SPEA2均獲得1個最優(yōu)值,AbYSS和SMPSO均獲得2個最優(yōu)值。除在ZDT6測試問題中MOPSO比MVCMOPSO取得的效果好,其他測試函數(shù)中MVCMOPSO的綜合性能均優(yōu)于MOPSO,說明本文對MOPSO所采取的改進方法是有效的。在ZDT2和Schaffer測試問題中,本文算法均獲得了收斂性和多樣性最好(IGD值最小)的解,說明算法引入的速度交流機制實現(xiàn)了子種群間的信息共享,使粒子能夠在解空間中進行不同區(qū)域的搜索,極大地提高了粒子的全局搜索性能。

由表3可知,MVCMOPSO在8個測試問題中獲得2個最優(yōu)GD值,NSGA-Ⅱ和MOPSO均獲得1個最優(yōu)值,SMPSO和GWASF-GA均獲得2個最優(yōu)值。表2中,SMPSO在ZDT3和Kursawe測試問題中均取得了最好的IGD值,表現(xiàn)出良好的優(yōu)越性,但從表3可得,MVCMOPSO在ZDT3和Kursawe測試問題中的收斂性指標卻優(yōu)于SMPSO,說明MVCMOPSO采用的多種變異協(xié)同操作能夠協(xié)助粒子及時跳出局部最優(yōu),使得到的非支配解能更好地收斂于真實Pareto前沿。

由表4的SP評價指標結果可見,本文算法在8個測試問題中獲得3個最優(yōu)值,NSGA-Ⅱ、AbYSS和MOPSO均獲得1個最優(yōu)值,SMPSO獲得2個最優(yōu)值。在解決ZDT1、Schaffer以及Viennet2測試問題中,本文算法獲得的解集分布性最好,說明算法采用混沌序列優(yōu)化的慣性權重,提高了粒子的遍歷性,促進粒子能均勻分布在真實Pareto前沿。

表4 7種算法SP性能指標的均值結果Tab.4 Mean results of 7 performance SP performance indicators

為直觀展示各算法所得解集的收斂性和分布性,圖4和圖5給出7種算法在Kursawe(二維非連續(xù))和Viennet3(三維連續(xù))測試函數(shù)上的Pareto前沿,圖4(a)和圖5(a)為測試函數(shù)真實Pareto前沿,圖4(b)～圖4(h)和圖5(b)～圖5(h)所得Pareto前沿。

由圖4可見,在解決Kursawe(二維非連續(xù))測試函數(shù)中,SMPSO得到的解收斂性和分布性最好。GWASF-GA得到的解沒有均勻分布在非連續(xù)前沿的第一段前沿,表現(xiàn)為部分密集部分稀松。

由表4也可知,GWASF-GA的SP指標最大,解集的分布性最差。MVCMOPSO得到的解集能很好地收斂于真實Pareto前沿,且分布均勻,說明算法在解決非連續(xù)問題時具有一定的優(yōu)勢,速度交流機制的運用,改善了粒子單一的搜索模式,提高了解的質量。

圖4 7種算法在Kursawe測試函數(shù)上的對比Fig.4 Comparison of 7 algorithms on Kursawe test function

圖5 7種算法在Viennet 3測試函數(shù)上的對比Fig.5 Comparison of 7 algorithms on Viennet 3 test function

由圖5可見,GWASF-GA在優(yōu)化Viennet3(三維連續(xù))測試函數(shù)時只有部分解收斂于真實前沿,盡管它的GD值是最好的,但它的分布性很差。NSGA-Ⅱ、AbYSS、MOPSO、SMPSO解集分布性良好,只有小部分解沒有均勻分布在真實Pareto前沿。MVCMOPSO取得最佳的解集效果,說明算法采取的改進策略有效地提高了待優(yōu)化函數(shù)的解的質量,從而獲得收斂性和分布性最好的解。

5 結 論

為更好地權衡多目標粒子群優(yōu)化算法解集的收斂性和多樣性,改善粒子單一的搜索模式,本文提出了基于速度交流的多種群MOPSO算法。結合實驗得到如下結論：

1) 將單種群等分為4個子種群P1、P2、P3和P4,并引入速度交流機制,實現(xiàn)了速度信息共享,改善了粒子單一的搜索模式,實現(xiàn)了對解空間不同區(qū)域的充分探索,提高了解的全局搜索能力。

2) 采用混沌映射優(yōu)化粒子慣性權重,應用于粒子速度和位置的更新,提高了粒子的遍歷性,使粒子盡可能探索更廣闊的解空間。

3) 在算法運行后期,為降低粒子陷入局部最優(yōu)Pareto前沿的可能性,提出了多種變異協(xié)同操作,每個子種群采用一種變異方式,實現(xiàn)不同的路徑搜索,協(xié)助粒子跳出局部最優(yōu)獲得收斂性和分布性更好的解。

4) 利用不同特征數(shù)據(jù)驗證算法的收斂性和多樣性,同時與NSGA-Ⅱ、SPEA2、AbYSS、MOPSO、SMPSO和GWASF-GA算法進行對比,實驗結果表明,MVCMOPSO算法能夠得到收斂性和多樣性更好的Pareto解。