基于博弈機(jī)制的多目標(biāo)粒子群優(yōu)化算法

喻金平，王 偉，巫光福，梁 文

(1.江西理工大學(xué) 工程研究院，江西 贛州 341000；2.江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000)

0 引 言

優(yōu)化問題大部分都是多目標(biāo)優(yōu)化問題，(multi-objective optimization problems，MOPs)，多個目標(biāo)函數(shù)之間存在相互沖突，需要同時進(jìn)行優(yōu)化。PSO[1](particle swarm optimization)算法因其收斂速度快，參數(shù)設(shè)置少的優(yōu)點(diǎn)，因此被廣泛用于解決MOPs。

PSO算法的改進(jìn)部分集中在加快算法的收斂速度和獲得多樣性較好的解上，因此針對收斂性方面，Hu等[2]提出了一種從進(jìn)化過程中檢測反饋信息，用于動態(tài)調(diào)整種群在開采和開發(fā)中平衡的算法。楊等[3]給出了一種融合策略，引入分解思想和支配并存的思想，在速度和位置更新時，引入“多點(diǎn)”變異，即隨著迭代的增加，根據(jù)相應(yīng)判據(jù)對其位置的更新做出不同的變異，最后將更新后的種群和最優(yōu)解集進(jìn)行非支配排序，能很好提升算法的收斂性。在改進(jìn)種群的多樣性方面，韓等[4]給出了高斯混沌變異和精英學(xué)習(xí)的自適應(yīng)方案，使用自適應(yīng)參數(shù)的機(jī)制和精英學(xué)習(xí)方法，有效提升了算法的多樣性。韓等[5]給出了參考點(diǎn)的高維多目標(biāo)粒子群算法，使用參考點(diǎn)作為依據(jù)，利用坐標(biāo)空間中的參考點(diǎn)選出多樣性良好的粒子，有效保持了解的多樣性。種群多樣性丟失、收斂快、容易陷入局部最優(yōu)一直是本研究的重點(diǎn)，但是這一問題并沒有較好的解決，因此本文提出了一種基于博弈機(jī)制的多目標(biāo)粒子群算法(game mechanism based multi-objective particle swarm optimization，GMOPSO)。

本文首先采用了多尺度混沌變異的策略，在算法追求快速收斂的同時，避免陷入局部最優(yōu)。一種新的精英粒子的選取方式，采用了非占優(yōu)解排序[6]和擁擠距離[3]共同排序，該方法可以較好提升算法的收斂性，不需要存儲全局最優(yōu)粒子的外部集，降低了算法時間復(fù)雜度。提出了一種粒子更新機(jī)制，博弈機(jī)制，提升了所得解的多樣性。

1 相關(guān)工作

1.1 粒子群算法

PSO在1995年被就提出了。PSO算法源自對一群在指定區(qū)域內(nèi)尋找食物的鳥群運(yùn)動的研究，將鳥抽象為不計重量和體積的粒子，食物被定義為所得解。這些粒子被隨機(jī)分散在次區(qū)域中，并且具有一定的初始速度，每輪循環(huán)迭代中，粒子都是根據(jù)自身歷史最優(yōu)位置和當(dāng)前種群中全局最優(yōu)的粒子更新自己的速度和位置。其中速度和位置更新公式請參考文獻(xiàn)[1]。

1.2 博 弈

博弈理論是PSO的一個變體，由Cheng等[7]提出，用來解決SOPs(single-objective optimization problems)。在博弈機(jī)制中，通過博弈對粒子進(jìn)行更新，而不是使用全局最優(yōu)粒子和個體最優(yōu)粒子，從而大大提高了種群的多樣性，避免了算法過早收斂。具體來講，在博弈機(jī)制中，粒子從當(dāng)前的種群中隨機(jī)兩兩配對進(jìn)行博弈，博弈失敗的粒子則通過向勝利者學(xué)習(xí)來更新自身的速度和位置，勝利者則保持原有的狀態(tài)，直接過渡到下一輪迭代，以此類推，直至所有粒子更新完畢。種群更新公式如下

(1)

Xf,i(k+1)=Xf,i(k+1)+vf,i(k+1)

(2)

2 基于博弈機(jī)制的多目標(biāo)粒子群算法

2.1 混沌映射

多目標(biāo)粒子群算法以快速收斂著稱，但是收斂過快容易陷入局部最優(yōu)，使得所得解不真實，所以需要采用混沌變異機(jī)制，使其跳出局部最優(yōu)，因此，本文采用了Tent[8]映射公式如下

(3)

其中，Xi是混沌數(shù)，i為迭代次數(shù)。

2.2 多尺度混沌變異策略

如上所述，過快的收斂速度導(dǎo)致算法容易陷入局部最優(yōu)，所以在算法初期使用上一部分提出的混沌映射的方法，使算法跳出該局部最優(yōu)，其中變異的距離由粒子的分布情況決定，不同的稀疏程度采用不同的變異方案。

算法1展示了該多尺度混沌變異策略，該策略首先將初始化后的群體使用擁擠距離，對每個粒子進(jìn)行降序排列。排在前20%的粒子，分布不是很密集，不容易陷入局部最優(yōu)，可以用小半徑μ*r進(jìn)行變異，其中μ是變異尺度；排在后20%的粒子由于容易陷入局部最優(yōu)，因此使用較大的變異半徑r；中間60%的粒子，因為陷入局部最優(yōu)的概率處于兩者之間，所以隨機(jī)從以上兩種方法中選擇一種進(jìn)行變異。具體變異過程看算法1。其中(M,N)表示用混沌模型產(chǎn)生的混沌序列，Crowding(pop)表示計算種群中粒子的擁擠距離并將其用降序排列。

算法1： ChaosMutation

輸入： 種群pop(M,N)變異尺度μ

輸出： 新種群Npop

(1)初始賦值r=(Xmax-Xmin)/2，μ=0.3

(2)Tent(M,N)

(3)Crowding(pop)

(4)for I=1∶M

(5) If (I<0.2*M)

(6) r=μ×r

(7) else if (I>0.8*M)

(8) r=r

(9) else if (rand>0.5)

(10) r=μ×r

(11) else

(12) r=r

(13) end if

(14) end if

(15) t=Tent (I,:)

(16) Npop(I,:)=pop(I,:)+r*(2*t-1)

(17)End for

2.3 GMOPSO框架

本文提出的GMOPSO算法的跟博弈群優(yōu)化器理論還是存在差異，原始的博弈理論是將初始化種群劃分成兩部分，一半是博弈成功者，另一半是博弈失敗者，博弈失敗者向博弈成功者學(xué)習(xí)更新，主框架如算法2所示。

算法2： main

輸入： POP(種群大小)； Iter(當(dāng)前迭代次數(shù))

MaxIter(最大迭代次數(shù))； E(精英集)

輸出： FP(粒子的最終位置)。

(1)初始化所有粒子的位置(X)和速度(V)

(2)while Iter<=MaxIter

(3) 通過擁擠距離選出10%的粒子加入E

(4) 執(zhí)行博弈機(jī)制更新粒子的位置和速度

(5) 環(huán)境選擇，選出新的種群

(6)end while

(7)Return FP

本算法是基于精英集確定的前提下的博弈，即待更新粒子從精英集中隨機(jī)選出兩個精英粒子，進(jìn)行博弈，博弈成功者將成為引導(dǎo)者，引導(dǎo)待更新粒子和博弈失敗者進(jìn)行更新，博弈成功者將維持原有的速度和方向前進(jìn)。其主要框架如算法2，由兩部分組成：新博弈機(jī)制的速度更新部分和種群環(huán)境選擇部分。其中環(huán)境選擇部分是出自SPEA2[9]，博弈機(jī)制的速度更新將會在2.4部分詳細(xì)介紹。

2.4 新博弈更新機(jī)制

新的博弈更新機(jī)制如算法3所示，采用夾角角度比較，不再是適應(yīng)度值進(jìn)行比較，在多目標(biāo)情況下，過度強(qiáng)調(diào)適應(yīng)度值，往往會使部分粒子遠(yuǎn)離局部最優(yōu)，導(dǎo)致算法總體收斂效果很差，比較角度能有效改善這個問題。其核心過程就是，非精英粒子從精英集中隨機(jī)選出兩個精英粒子，計算兩個精英粒子間與非精英粒子之間的夾角，所成夾角小的粒子將成為這個粒子的引導(dǎo)者。博弈機(jī)制循環(huán)開始于精英粒子的確定，精英粒子是通過非占優(yōu)排序[7]和擁擠距離[1]來選出的。非占優(yōu)排序是依據(jù)個體的非劣解水平對種群分層。它是一個循環(huán)的適應(yīng)值分級過程，首先找出種群的第一層非占優(yōu)解，記為F1，然后將第一層刪去，接著找第二層，以此類推，直至所有的粒子都分好層。接下來根據(jù)每一層的粒子計算擁擠距離并降序排列。擁擠距離是在同一級別中，該粒子與相鄰前后兩粒子間所能形成的最大矩形的邊長和。

算法3： 博弈更新機(jī)制

輸入： X(粒子的位置)， V(速度)， E(精英集)

Iter(當(dāng)前迭代次數(shù))， MaxIter(最大迭代次數(shù))

輸出： NP(粒子的新位置)

(1) 將NP設(shè)為空集

(2) forXi∈Xdo

(3) 從E中隨機(jī)選兩個粒子Xa,Xb

(4) 計算粒子a，b與粒子x之間夾角θ1和θ2

(5) ifθ1<θ2

(6)Xw=Xa;

(7) else

(8)Xw=Xb;

(9) end if

(10) 使用式(4)，式(5)更新粒子的位置和速度

(11) while Iter < 0.4*MaxIter

(12) 執(zhí)行ChaosMutation

(13) 將更新的粒子位置和速度加入到NP中

(14)end for:

(15)多項式變異

(16)Return NP

該機(jī)制十分突出的一點(diǎn)就是，精英集粒子只需要通過擁擠距離和非占優(yōu)排序選舉出來，而且對于精英集的規(guī)模的選擇也十分重要，較小的精英集將會導(dǎo)致早熟收斂，較大的精英集能延緩收斂的速度，避免陷入局部最優(yōu)，所以我們將精英集的大小設(shè)定為粒子種群數(shù)量的10%。

當(dāng)精英集粒子確定完畢后，進(jìn)行博弈，博弈成功者將作為全局最優(yōu)粒子指引種群中其它粒子飛行，在每一對博弈當(dāng)中，待更新粒子從精英集中隨機(jī)選出兩個精英粒子a和b，兩個精英粒子就兩者與非精英粒子從坐標(biāo)軸遠(yuǎn)點(diǎn)出發(fā)所形成的夾角進(jìn)行博弈，所形成角度小的博弈成功，如圖1所示，精英粒子a與非精英粒子x形成的夾角θ1小，故而粒子a引導(dǎo)粒子x進(jìn)行速度和位置更新，速度更新公式如下。從選擇精英到比較角度這整個過程稱之為博弈，因為精英粒子的選擇是隨機(jī)的，待更新粒子不清楚最終會選定哪個引導(dǎo)者，引導(dǎo)者自身的屬性會決定粒子更新的效果，屬性較好的引導(dǎo)者引導(dǎo)更新效果更好，反之，屬性一般的引導(dǎo)者引導(dǎo)更新效果次之，粒子更新效果完全取決于引導(dǎo)者，所以稱之為博弈

v′i=c4vi+c5(Xw-Xi)

(4)

X′i=Xi+v′i

(5)

其中，c4和c5是[0,1]之間的隨機(jī)產(chǎn)生的向量，Xw是博弈成功者的位置，Xi是粒子的當(dāng)前位置，vi是粒子的當(dāng)前速度。

圖1 兩精英粒子進(jìn)行博弈

2.5 時間復(fù)雜度分析

博弈機(jī)制，不需要外部儲備集，能有效加快算法的收斂速度，本文以時間復(fù)雜度來分析本文算法的收斂速度，本文算法和MOPSO都用到了非占優(yōu)排序，而非占優(yōu)排序最慢需要O(mn2)， 最快需要O(mnlogn)， 非占優(yōu)排序采用最快情況下的時間復(fù)雜度。

基于博弈的GMOPSO

O(M*(mnlog(n)+n+2mnlog(2n)))

未采用博弈的MOPSO

O(M*(2mnlog(2n)+n+2mnlog(2n)))

其中，M為最大迭代次數(shù)；m為目標(biāo)的個數(shù)；n是種群中粒子的個數(shù)。由以上可知，采用博弈機(jī)制能有效提升算法的收斂速度。

3 實驗仿真

3.1 實驗設(shè)置

本文使用的測試函數(shù)是現(xiàn)今比較流行的測試函數(shù)系列，分別是ZDT系列、DTLZ系列和WFG系列測試函數(shù)，總共21個函數(shù)構(gòu)成，進(jìn)行28項測試。ZDT系列中，由于ZDT5是布爾函數(shù)，使用此測試函數(shù)需要二進(jìn)制編碼，所以就沒有用該測試函數(shù)，ZDT系列標(biāo)準(zhǔn)測試函數(shù)進(jìn)行兩目標(biāo)測試。DTLZ系列由DTLZ1至DTLZ7組成的一類標(biāo)準(zhǔn)測試函數(shù)，DTLZ系列標(biāo)準(zhǔn)測試函數(shù)分別進(jìn)行了兩目標(biāo)和三目標(biāo)測試，WFG系列標(biāo)準(zhǔn)測試函數(shù)進(jìn)行三目標(biāo)測試。對比算法分別是NSGA-II[10]、MOEAD[11]、MOPSO[2]、MPSOD[12]、MMOPSO[13]、和SMPSO[14]，這些算法都是常用的經(jīng)典對比算法，故本文將與這些算法對比來驗證算法的有效性。

本次實驗是在Windows7系統(tǒng)下完成的，算法性能評價指標(biāo)采用的是逆代距IGD(inverted generational distance)和Pareto前沿。所有算法的種群大小設(shè)為100，有外部集的算法其存檔容量均設(shè)為100，測試函數(shù)運(yùn)行次數(shù)除了DTLZ3迭代1000次以外，其它的測試函數(shù)均迭代300次，所有算法獨(dú)立運(yùn)行50次，所得結(jié)果是50次獨(dú)立運(yùn)行的IGD的平均值及標(biāo)準(zhǔn)差，IGD值越小，算法得出解得性能就越好。

3.2 IGD對比分析

表1和表2展示了6種對比算法和本文算法在21個測試函數(shù)上進(jìn)行的28項的測試值，其中含有IGD的平均值和標(biāo)準(zhǔn)差，以及t檢驗結(jié)果，t測試中“+”、“-”和“=”分別表示強(qiáng)于、弱于和等于本文算法在對應(yīng)測試函數(shù)上的顯著性區(qū)分結(jié)果，使用字體加粗的方法把所得結(jié)果在每一個測試函數(shù)上的最小IGD的值進(jìn)行了標(biāo)記。表1中和表2中M代表目標(biāo)個數(shù)。

從表1可以看出，4個算法中，原始的MOPSO算法性能最差，本文提出的算法性能最佳。在28項標(biāo)準(zhǔn)測試函數(shù)當(dāng)中，GMOPSO在15項標(biāo)準(zhǔn)測試函數(shù)中取得了較好的IGD值，尤其是在ZDT系列和WFG系列中。MOEAD在3項標(biāo)準(zhǔn)測試函數(shù)中取得了最小的IGD值，但有16項標(biāo)準(zhǔn)測試函數(shù)次于本文算法；MOPSO在1項標(biāo)準(zhǔn)測試函數(shù)中表現(xiàn)較好，但有26項標(biāo)準(zhǔn)測試函數(shù)劣與本文算法；NSGAII在10項標(biāo)準(zhǔn)測試函數(shù)中表現(xiàn)最好，但有18項標(biāo)準(zhǔn)測試函數(shù)差于本文算法。

從表2中得出，與目前流行的多目標(biāo)進(jìn)化算法相比，本文提出的GMOPSO算法在標(biāo)準(zhǔn)測試函數(shù)上整體表現(xiàn)良好，在14項標(biāo)準(zhǔn)測試函數(shù)中IGD值明顯優(yōu)于其它算法，說明了博弈機(jī)制的有效性。從t檢驗來看，相比SMPSO算法，本文算法在20項標(biāo)準(zhǔn)測試函數(shù)上強(qiáng)于它，6項測試函數(shù)劣于它，兩個測試函數(shù)與它持平。相比改進(jìn)的MMOPSO算法，本文算法在16項測試函數(shù)上強(qiáng)于它，9項測試函數(shù)劣于它，3項測試函數(shù)與它持平。與MPSOD算法相比較，本文算法在21項測試函數(shù)上優(yōu)于它，4項函數(shù)劣于它，3項函數(shù)與它持平。

綜上所述，與現(xiàn)有的各種多目標(biāo)粒子群算法相比較，本文提出的GMOSPO能在保證快速收斂的同時保持種群的多樣性，這也證實了GMOPSO所提出的博弈機(jī)制能很好的平衡收斂性和多樣性，并且在求解多目標(biāo)優(yōu)化問題上具有良好的性能和前景。

3.3 Pareto前沿比較

表3給出了性能對比中較好的4個算法在部分測試函數(shù)的Pareto前沿比較圖。從表中可以看出：所給出的標(biāo)準(zhǔn)測試函數(shù)中，本文算法僅在ZDT4標(biāo)準(zhǔn)測試函數(shù)上性能較差，不能有效收斂至Pareto前沿，且最終結(jié)果所得的粒子群分布不均，但是在其它展示出來的標(biāo)準(zhǔn)測試函數(shù)上都能表現(xiàn)出良好的性能；在ZDT2標(biāo)準(zhǔn)測試函數(shù)上，本文算法能很好的收斂至Pareto前沿，性能最差的是MOPSO算法，沒有收斂到Pareto前沿，另外兩個算法雖然能收斂到 Pareto 前沿，但是分布不是很均勻；在ZDT3標(biāo)準(zhǔn)測試函數(shù)上，本文算法相比其它算法性能最好，但是分布存在不均勻，性能最差的是MOPOS算法，圖片上分布比較均勻，但是與Pareto前沿相差很多，不能收斂到前沿，另外兩種算法表現(xiàn)不是很理想，算法的收斂性和種群的多樣性表現(xiàn)都較差；在ZDT4標(biāo)準(zhǔn)測試函數(shù)上，NSGAII算法性能最好，能兼顧收斂性和多樣性，另外3種算法都性能較差；就DTLZ4標(biāo)準(zhǔn)測試函數(shù)上的對比來看，本文算法性能最好，最終所得解能有效收斂至真實前沿，且分布很均勻，MOEAD算法性能最差，另外兩種算法能收斂到Pareto前沿，但是分布不是很均勻；就DTLZ5標(biāo)準(zhǔn)測試函數(shù)上的對比來看，GMOPSO與NSGAII都表現(xiàn)較好，圖片中展示了這兩個算法具有較好的收斂性和多樣性。MOEAD性能最差，雖然能收斂到Pareto，但是分布不均；就DTLZ7標(biāo)準(zhǔn)測試函數(shù)上的對比來看，本文算法性能最好，算法收斂性較好和所得解多樣性較完善，原始的MOPSO算法性能最差。

表1 4種算法在標(biāo)準(zhǔn)測試函數(shù)上的IGD平均值和標(biāo)準(zhǔn)差

表2 4種算法在標(biāo)準(zhǔn)測試函數(shù)上的IGD平均值和標(biāo)準(zhǔn)差

表3 各算法在部分測試函數(shù)上的Pareto前端

綜上所述可知，新的精英粒子選取方式可以很好地提升算法的收斂性，并且博弈機(jī)制的隨機(jī)性，不同于原始算法，種群在一輪迭代中全局引導(dǎo)者只有一個，導(dǎo)致眾多粒子遠(yuǎn)離自身最優(yōu)的位置，多樣性丟失，在精英集中選擇的隨機(jī)性，以及比較兩個隨機(jī)選出的精英粒子與待更新粒子之間夾角的過程有效維護(hù)了種群的多樣性，以及多尺度混沌變異有效跳出局部最優(yōu)能夠很好地保持算法的多樣性，很好提升了算法的性能，使得本文算法能有效收斂到真實的Pareto前沿。

4 結(jié)束語

本文提出了一種特殊機(jī)制的多目標(biāo)粒子群算法即博弈機(jī)制。通過使用多尺度混沌變異以及特殊的精英粒子選取方式來提高群智能算法普遍存在的容易陷入局部最優(yōu)的問題，博弈機(jī)制下的粒子更新方式，所有粒子都能成為引導(dǎo)者，很好維持了種群的多樣性。待更新者通過博弈成功者的速度和位置更新自己的速度和位置，因為博弈是在當(dāng)前的種群挑選出的精英粒子中進(jìn)行的，所以就省去了保存粒子個體最優(yōu)和全局最優(yōu)粒子的外部集策略，極大降低了算法的時間復(fù)雜度。就本文所做的研究和實驗結(jié)果來看，本文算法在三目標(biāo)問題上取得的成績比在二目標(biāo)問題上取得成績要好，說明本文提出的算法傾向于進(jìn)行高維多目標(biāo)優(yōu)化。在3類測試函數(shù)上與現(xiàn)今流行的多目標(biāo)進(jìn)化算法相比，結(jié)果表明了本文所提出的GMOPSO算法在算法收斂性和所得解的多樣性上性能優(yōu)良。