基于博弈機制的多目標粒子群優化算法

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

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

0 引 言

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

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

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

1 相關工作

1.1 粒子群算法

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

1.2 博 弈

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

(1)

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

(2)

2 基于博弈機制的多目標粒子群算法

2.1 混沌映射

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

(3)

其中，Xi是混沌數，i為迭代次數。

2.2 多尺度混沌變異策略

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

算法1展示了該多尺度混沌變異策略，該策略首先將初始化后的群體使用擁擠距離，對每個粒子進行降序排列。排在前20%的粒子，分布不是很密集，不容易陷入局部最優，可以用小半徑μ*r進行變異，其中μ是變異尺度；排在后20%的粒子由于容易陷入局部最優，因此使用較大的變異半徑r；中間60%的粒子，因為陷入局部最優的概率處于兩者之間，所以隨機從以上兩種方法中選擇一種進行變異。具體變異過程看算法1。其中(M,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算法的跟博弈群優化器理論還是存在差異，原始的博弈理論是將初始化種群劃分成兩部分，一半是博弈成功者，另一半是博弈失敗者，博弈失敗者向博弈成功者學習更新，主框架如算法2所示。

算法2： main

輸入： POP(種群大小)； Iter(當前迭代次數)

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

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

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

(2)while Iter<=MaxIter

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

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

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

(6)end while

(7)Return FP

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

2.4 新博弈更新機制

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

算法3： 博弈更新機制

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

Iter(當前迭代次數)， MaxIter(最大迭代次數)

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

(1) 將NP設為空集

(2) forXi∈Xdo

(3) 從E中隨機選兩個粒子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) 執行ChaosMutation

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

(14)end for:

(15)多項式變異

(16)Return NP

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

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

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

(4)

X′i=Xi+v′i

(5)

其中，c4和c5是[0,1]之間的隨機產生的向量，Xw是博弈成功者的位置，Xi是粒子的當前位置，vi是粒子的當前速度。

圖1 兩精英粒子進行博弈

2.5 時間復雜度分析

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

基于博弈的GMOPSO

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

未采用博弈的MOPSO

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

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

3 實驗仿真

3.1 實驗設置

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

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

3.2 IGD對比分析

表1和表2展示了6種對比算法和本文算法在21個測試函數上進行的28項的測試值，其中含有IGD的平均值和標準差，以及t檢驗結果，t測試中“+”、“-”和“=”分別表示強于、弱于和等于本文算法在對應測試函數上的顯著性區分結果，使用字體加粗的方法把所得結果在每一個測試函數上的最小IGD的值進行了標記。表1中和表2中M代表目標個數。

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

從表2中得出，與目前流行的多目標進化算法相比，本文提出的GMOPSO算法在標準測試函數上整體表現良好，在14項標準測試函數中IGD值明顯優于其它算法，說明了博弈機制的有效性。從t檢驗來看，相比SMPSO算法，本文算法在20項標準測試函數上強于它，6項測試函數劣于它，兩個測試函數與它持平。相比改進的MMOPSO算法，本文算法在16項測試函數上強于它，9項測試函數劣于它，3項測試函數與它持平。與MPSOD算法相比較，本文算法在21項測試函數上優于它，4項函數劣于它，3項函數與它持平。

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

3.3 Pareto前沿比較

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

表1 4種算法在標準測試函數上的IGD平均值和標準差

表2 4種算法在標準測試函數上的IGD平均值和標準差

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

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

4 結束語

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