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

王進(jìn)成，顧銀魯，宋楨楨

(銀川能源學(xué)院 基礎(chǔ)部，寧夏 銀川 750021)

在求解多目標(biāo)優(yōu)化問題時[1]，要求盡可能地接近真正的Pareto有效前端；盡可能地保持良好的多樣性；盡可能地使粒子分散均勻.目前，出現(xiàn)了許多經(jīng)典的多目標(biāo)優(yōu)化算法.如Dbe[2]等人利用non-dominated sorting提出了NSGA-Ⅱ算法，Corne[3]等人利用強(qiáng)度Pareto支配的思想提出了SPEA2算法，Coello[4]等人利用外部粒子群來指導(dǎo)該群體外其他粒子的飛行的思想提出了MOPSO算法.

粒子群優(yōu)化算法[5](Particle Swarm Optimization Algorithm，PSO)是由Kennedy博士于1995年提出來的一種群智能優(yōu)化算法，由于該算法簡單收斂速度快且易于實現(xiàn)，近年來就得到了飛速發(fā)展并成為群智能優(yōu)化算法研究領(lǐng)域的熱點(diǎn)之一.用于解決多目標(biāo)優(yōu)化問題的粒子群優(yōu)化算法稱為多目標(biāo)粒子群優(yōu)化算法(Multi-objective particle swarm algorithm，MOPSO).為了提高M(jìn)OPSO粒子的多樣性，本文提出了一種基于競爭機(jī)制策略的多目標(biāo)粒子群優(yōu)化算法.有效地平衡了種群的全局尋優(yōu)能力和局部搜索能力，并且使算法能夠更快的搜索到最優(yōu)位置和收斂于Pareto最優(yōu)邊界.最后，通過對多目標(biāo)測試函數(shù)進(jìn)行仿真試驗，以及與經(jīng)典多目標(biāo)算法NSGA-Ⅱ、SPEA2、MOPSO相比，結(jié)果表明，本文算法在收斂性和分布性方面都有所改善.

1 粒子群優(yōu)化算法

粒子群算法(PSO)是一種模仿鳥類和魚群中個體社會行為的一種啟發(fā)式群體智能算法.該算法穩(wěn)定且高效，是近年來發(fā)展的一種智能全局尋優(yōu)算法.種群中每一只鳥相當(dāng)于粒子群算法中的一個粒子，每個粒子類似于尋找食物的鳥，都有其自身的速度和位置，通過自身學(xué)習(xí)和社會學(xué)習(xí)兩種方式，粒子在搜索空間中運(yùn)動，從而得到全局最優(yōu)解.假設(shè)種群規(guī)模為N的粒子在D維空間內(nèi)進(jìn)行搜索，粒子的速度和位置更新公式為

(1)

(2)

ω=ωmax-t*(ωmax-ωmin)/Tmax，

(3)

上式中，ωmax,ωmin分別為慣性權(quán)重的最大和最小值，一般取0.9和0.4,t表示當(dāng)前迭代次數(shù),Tmax表示最大迭代次數(shù).

2 基于競爭機(jī)制策略的多目標(biāo)粒子群優(yōu)化算法

2.1 競爭機(jī)制策略

本文提出的競爭機(jī)制策略主要是基于支配的方法，在多目標(biāo)粒子群算法中可以快速搜索非支配解集以及構(gòu)建外部檔案集.首先，從群體s中任選一個粒子x，一般情況下選取群體中的第一個粒子.然后，令s=s-{x}，將群體中的每個粒子依次與粒子x依據(jù)目標(biāo)函數(shù)值的Pareto支配關(guān)系進(jìn)行比較.若x

在求解多目標(biāo)粒子群優(yōu)化算法時，每一次迭代都會產(chǎn)生一組非劣解.因此，需要利用外部存檔來儲存每一次迭代所產(chǎn)生的非支配解，而這些解集構(gòu)成了Pareto前端[6].從而每迭代一次，Pareto前端也隨之更新一次.但是，隨著迭代次數(shù)的增加，外部檔案規(guī)模將會增加，算法的復(fù)雜度也將會大大增加.此時需要對外部檔案規(guī)模進(jìn)行控制，從而可以降低算法的復(fù)雜度.本文采用擁擠距離降序排列來限制外部檔案集的規(guī)模.

2.2 個體最優(yōu)解和全局最優(yōu)解的選取

在粒子群算法中，粒子群大小固定，粒子不會被替代，只是調(diào)整它們的個體最優(yōu)解(xbest)和全局最優(yōu)解(gbest)．在多目標(biāo)情況下，全局最優(yōu)解通常存在于一組非劣解中，而不是單個的全局最優(yōu)位置，而且當(dāng)兩者互不支配時，每個粒子可能不止一個個體最優(yōu)解．因此，個體最優(yōu)解和全局最優(yōu)解的選取比單目標(biāo)優(yōu)化更加困難和重要．

(4)

對于多目標(biāo)粒子群優(yōu)化算法的全局最優(yōu)解更新策略，本文從外部檔案集排在前20%的非支配解中隨機(jī)選取全局最優(yōu)解.

2.3 參數(shù)改進(jìn)策略

對于粒子群算法中的慣性權(quán)重ω和學(xué)習(xí)因子c1和c2這兩類參數(shù)，它們對種群在目標(biāo)區(qū)域內(nèi)搜索能力有很大的影響，為此本文對其進(jìn)行了動態(tài)調(diào)整.

慣性權(quán)重ω取決于粒子之前速度對當(dāng)前速度影響程度的大小，能夠有效地平衡算法全局搜索和局部搜索能力.如果ω=0，則粒子速度由當(dāng)前位置所確定，速度本身并不存在記憶，因此很容易陷入局部最優(yōu).而ω≠0時，ω較大的慣性權(quán)重可以加強(qiáng)全局尋優(yōu)能力，反之可以加強(qiáng)局部搜索能力，為了提高算法的搜索性能，本文采用一種新的慣性權(quán)重，其更新公式如下

(5)

上式中，ω(t)隨著迭代次數(shù)而變化.在本文中，p1為最大迭代次數(shù)的三分之一；p2取值為10；ωmax取值為0.5；ωmin取值為0.4；t為當(dāng)前迭代次數(shù).

學(xué)習(xí)因子決定的是粒子搜索過程中本身學(xué)習(xí)能力和群體學(xué)習(xí)能力對粒子運(yùn)動的影響，反映的是粒子間的信息交流.近年來，許多學(xué)者對其進(jìn)行了修正，有學(xué)者提出了異步學(xué)習(xí)因子，當(dāng)算法在初始階段搜索時，會使粒子具有較大的自我學(xué)習(xí)能力和較小的社會學(xué)習(xí)能力；并且在搜索后期，能夠加強(qiáng)粒子向全局最優(yōu)位置移動的能力以及獲得高質(zhì)量的粒子，有利于算法收斂到最優(yōu)解.對于學(xué)習(xí)因子，本文采用上述的新慣性權(quán)重的非線性函數(shù)[7]，其更新公式如下

c1(t)=1.167×ω(t)2-0.1167×ω(t)+0.66，

(6)

c2(t)=3-c1(t)，

(7)

由上述公式可以得出，學(xué)習(xí)因子也隨著慣性權(quán)重的調(diào)整而動態(tài)調(diào)整.

2.4 時變高斯變異

在解決多目標(biāo)優(yōu)化問題時，粒子群算法的快速收斂性未必是優(yōu)勢，反而可能使得種群過早地聚集在某一些粒子周圍或某一塊區(qū)域而喪失多樣性，容易使算法出現(xiàn)早熟現(xiàn)象.因此，為了增強(qiáng)群體多樣性，避免算法陷入局部最優(yōu).本文根據(jù)文獻(xiàn)[8]的思想，設(shè)計一種時變變異算子對外部檔案中的粒子進(jìn)行變異，以產(chǎn)生新的非劣解，其擾動公式如下

(8)

(9)

mut_range=(ub(j)-lb(j))*Pm，

(10)

其中，Pm為變異概率；rg服從均值為0，方差為1的高斯分布；mut_range表示變異的作用范圍；ub(j)和lb(j)分別為第j維決策變量的上界和下界；Mr為變異參數(shù)，本文取值為0.5.

2.5 CMSMOPSO算法的具體步驟

Step1 初始化群體的位置和速度；設(shè)定迭代次數(shù)，種群規(guī)模，算法參數(shù)；

Step2 計算各粒子的適應(yīng)度值；按照支配關(guān)系產(chǎn)生非支配解集；

Step3 更新外部檔案集；

Step4 按照擁擠距離對外部檔案集每個粒子間進(jìn)行降序排列，判斷是否超出設(shè)定的規(guī)模數(shù)，若超出，則清除規(guī)模以外的非支配解；

Step5 更新個體最優(yōu)位置；如果第一代是，則直接將每個粒子初始位置選取為個體最優(yōu)值；否則，根據(jù)Pareto支配關(guān)系更新；

Step6 從排在前20%非支配解的外部檔案集中任意選取全局最優(yōu)位置；

Step7 更新速度公式；如果粒子的速度vi>vmax，則令vi=vmax；如果粒子的速度vi

Step8 更新各粒子下一代的位置，并按照發(fā)生概率Pm對各外部檔案中的粒子進(jìn)行時變高斯變異，避免算法陷入早熟；

Step9 判斷是否滿足條件(最大迭代次數(shù))，如滿足則結(jié)束循環(huán)；否則，返回Step2繼續(xù)迭代.

3 實驗結(jié)果與分析

3.1 性能度量

世代距離(GD)是描述算法運(yùn)算求解得到的非劣解與目標(biāo)問題的真實Pareto前端之間距離的參數(shù)，其數(shù)學(xué)表達(dá)式為[9]

(11)

其中，di表達(dá)式如下

(12)

分布均勻度量(SP)是評價算法求解得到的Pareto最優(yōu)解集中分布性能好壞的一個參數(shù),其數(shù)學(xué)表達(dá)式為[10]

(13)

(14)

上式中，k表示目標(biāo)函數(shù)的個數(shù).SP的值越小，表明算法得到的解的分布性越好.SP的理想值為0,即算法得到的Pareto最優(yōu)解在目標(biāo)空間中是均勻分布的.

3.2 測試函數(shù)

為了測試CMSMOPSO算法的性能，本文選取經(jīng)典多目標(biāo)測試函數(shù)進(jìn)行仿真試驗[11].其測試函數(shù)表示如下.

(i)測試函數(shù)1：ZDT1

搜索空間:x∈[0,1]，維數(shù):n=10.

(ii)測試函數(shù)2：ZDT2

搜索空間:x∈[0,1]，維數(shù):n=10.

(iii)測試函數(shù)3：ZDT3

搜索空間:x∈[0,1]，維數(shù):n=10.

(iv)測試函數(shù)4：DTLZ2

搜索空間:x∈[0,1]，維數(shù):n=10.

(v)測試函數(shù)5：DTLZ4

搜索空間:x∈[0,1]，維數(shù):n=10.

3.3 實驗分析和比較

通過實驗，將本文算法與NSGA-Ⅱ、SPEA2以及MOPSO算法的實驗結(jié)果進(jìn)行對比.設(shè)置種群規(guī)模為100，最大迭代次數(shù)為200，外部檔案集規(guī)模為100，其他每個算法的具體參數(shù)設(shè)置如表1.其中，pc為交叉概率，pm為變異概率，mu為變異比例，sep為變異步長，ng為網(wǎng)格支配最大粒子個數(shù)，cg為交叉比例，aph為膨脹比率.分別將算法NSGA-Ⅱ、SPEA2、MOPSO以及CMSMOPSO在每個測試函數(shù)上獨(dú)立運(yùn)行10次.各個算法對函數(shù)的收斂性(GD)和分布性(SP)比較結(jié)果如表2和表3所示.實驗都是在win7系統(tǒng)matlab 2012a中完成的.

表1 參數(shù)設(shè)置

表2 各個算法對每個測試函數(shù)的收斂性比較結(jié)果

測試函數(shù)GD算法NSGA-ⅡSPEA2MOPSOCMSMOPSOAverage1.93E-022.88E-022.21E-026.72E-04ZDT3Worst2.50E-025.05E-022.58E-027.54E-04Std.Dev.3.57E-039.13E-036.40E-034.20E-05Best8.82E-022.24E-028.05E-024.23E-02Average8.97E-022.53E-029.03E-026.55E-02DTLZ2Worst8.89E-022.40E-028.64E-029.05E-02Std.Dev.6.26E-031.32E-033.74E-031.61E-02Best8.38E-021.61E-021.03E-013.15E-01Average9.55E-022.63E-021.07E-013.83E-01DTLZ4Worst1.10E-012.15E-021.05E-014.74E-01Std.Dev.1.25E-025.02E-031.23E-032.57E-02

表3 各個算法對每個測試函數(shù)的分布性比較結(jié)果

從表2和表3可以看出，在測試函數(shù)ZDT1-ZDT3上，CMSMOPSO算法所得的Pareto前端無論是收斂性指標(biāo)還是分布性指標(biāo)都要比其他算法好；相比NSGA-Ⅱ和SPEA2算法，CMSMOPSO和MOPSO算法所得結(jié)果有很大提升，并且CMSMOPSO算法所得結(jié)果明顯優(yōu)于MOPSO算法.在測試函數(shù)DTLZ2和DTLZ4上，CMSMOPSO算法在收斂性指標(biāo)和分布性指標(biāo)上所得結(jié)果相對較差，有待提高.綜上所述，CMSMOPSO算法可以有效地解決多目標(biāo)優(yōu)化問題.

圖1 NSGA-Ⅱ?qū)DT-1的測試圖 圖2 SPEA2對ZDT-1的測試圖

圖3 MOPSO對ZDT-1的測試圖 圖4 CMSMOPSO對ZDT-1的測試圖

圖5 NSGA-Ⅱ?qū)DT-2的測試圖 圖6 SPEA2對ZDT-2的測試圖

圖7 MOPSO對ZDT-2的測試圖 圖8 CMSMOPSO對ZDT-2的測試圖

圖9 NSGA-Ⅱ?qū)DT-3的測試圖 圖10 SPEA2對ZDT-3的測試圖

圖11 MOPSO對ZDT-3的測試圖 圖12 CMSMOPSO對ZDT-3的測試圖

DTLZ-21.41.210.80.60.40.20000.511.51.510.51stObjective2ndObjectiveTrueParetoCMSMOPSO3rdObjective1.41.210.80.60.40.200.511.51.510.51stObjective2ndObjective3rdObjectiveTrueParetoCMSMOPSODTLZ-4圖13 CMSMOPSO算法在DTLZ2所得Pareto前端圖14 CMSMOPSO算法在DTLZ4上所得Pareto前端

圖1～圖12是4種算法各自在ZDT1-ZDT3測試函數(shù)上所得到的Pareto解，從圖1～圖12中可以明顯看出，CMSMOPSO算法所得到的Pareto解集都要比NSGA-Ⅱ、SPEA2和MOPSO算法好；NSGA-Ⅱ、SPEA2和MOPSO算法有部分解明顯偏離真實Pareto前端；在多樣性方面，對ZDT3測試函數(shù)，可以觀察到MOPSO算法的均勻性較差，而NSGA-Ⅱ、SPEA2和CMSMOPSO算法的均勻程度較好.圖13～圖14是CMSMOPSO算法在DTLZ2和DTLZ4上所得Pareto解，從圖可以明顯看出，CMSMOPSO算法所得Pareto解的均勻程度較差，需要進(jìn)一步提高.綜上所述，CMSMOPSO算法在部分函數(shù)上所得到的Pareto解顯著優(yōu)于其他三種算法.

4 結(jié)論與展望

為了解決多目標(biāo)粒子群優(yōu)化過程中各個解之間存在的資源爭奪和沖突，算法由于趨同性而帶來的早熟無法收斂等缺點(diǎn)，提出了一種基于競爭機(jī)制策略的多目標(biāo)粒子群優(yōu)化算法.通過引入競爭機(jī)制策略和動態(tài)調(diào)整粒子參數(shù)，避免算法陷入局部最優(yōu)解.在算法后期引入時變高斯變異，提高了算法的多樣性.實驗結(jié)果表明，對兩個目標(biāo)測試函數(shù)，CMSMOPSO算法在兩個指標(biāo)上的性能顯著優(yōu)于其他經(jīng)典多目標(biāo)算法，但對三個目標(biāo)測試函數(shù)，CMSMOPSO算法所得結(jié)果并不理想，需要進(jìn)一步改進(jìn)CMSMOPSO算法的性能，使其解決更多的多目標(biāo)優(yōu)化問題.