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

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

0 引 言

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

PSO算法的改進(jìn)部分集中在加快算法的收斂速度和獲得多樣性較好的解上，因此針對(duì)收斂性方面，Hu等[2]提出了一種從進(jìn)化過(guò)程中檢測(cè)反饋信息，用于動(dòng)態(tài)調(diào)整種群在開(kāi)采和開(kāi)發(fā)中平衡的算法。楊等[3]給出了一種融合策略，引入分解思想和支配并存的思想，在速度和位置更新時(shí)，引入“多點(diǎn)”變異，即隨著迭代的增加，根據(jù)相應(yīng)判據(jù)對(duì)其位置的更新做出不同的變異，最后將更新后的種群和最優(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)，但是這一問(wèn)題并沒(méi)有較好的解決，因此本文提出了一種基于博弈機(jī)制的多目標(biāo)粒子群算法(game mechanism based multi-objective particle swarm optimization，GMOPSO)。

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

1 相關(guān)工作

1.1 粒子群算法

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

1.2 博 弈

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

(1)

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

(2)

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

2.1 混沌映射

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

(3)

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

2.2 多尺度混沌變異策略

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

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

算法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) 通過(guò)擁擠距離選出10%的粒子加入E

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

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

(6)end while

(7)Return FP

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

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

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

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

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

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

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

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

(2) forXi∈Xdo

(3) 從E中隨機(jī)選兩個(gè)粒子X(jué)a,Xb

(4) 計(jì)算粒子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)多項(xiàng)式變異

(16)Return NP

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

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

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 時(shí)間復(fù)雜度分析

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

基于博弈的GMOPSO

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

未采用博弈的MOPSO

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

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

3 實(shí)驗(yàn)仿真

3.1 實(shí)驗(yàn)設(shè)置

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

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

3.2 IGD對(duì)比分析

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

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

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

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

3.3 Pareto前沿比較

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

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

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

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

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

4 結(jié)束語(yǔ)

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