基于非支配排序的多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法

蔡巧珍，譚 瑛，王 艷

(太原科技大學(xué)復(fù)雜系統(tǒng)與計(jì)算智能實(shí)驗(yàn)室，太原 030024)

現(xiàn)實(shí)世界中的很多問題通常由多個(gè)目標(biāo)組成，這些子目標(biāo)之間可能是相互沖突的，某個(gè)子目標(biāo)的改善可能會引起其他子目標(biāo)性能的降低，因此多目標(biāo)優(yōu)化問題通常需要對相互沖突的子目標(biāo)進(jìn)行綜合考慮，即對各子目標(biāo)進(jìn)行折衷。針對多目標(biāo)優(yōu)化問題，典型的有Deb等提出的非劣排序遺傳算法NSGAII[1]，Zitzler 等提出的強(qiáng)Pareto進(jìn)化算法SPEA2[2]等。隨著多目標(biāo)優(yōu)化問題研究的深入，一些新的進(jìn)化機(jī)制也被引入進(jìn)化多目標(biāo)優(yōu)化領(lǐng)域，如Coello Coello等人基于粒子群優(yōu)化提出的Multi-objective Particle Swarm Optimization(MOPSO)[3]。

擬態(tài)物理學(xué)優(yōu)化(Artificial Physics Optimization，APO)算法[4-7]是由謝麗萍和曾建潮于 2009 年提出的。該算法建立個(gè)體間與適應(yīng)值優(yōu)劣有關(guān)的簡單引斥力規(guī)則，由三部分組成:初始化種群，計(jì)算個(gè)體所受合力和個(gè)體運(yùn)動(dòng)。APO算法已經(jīng)成功用于單目標(biāo)優(yōu)化問題中，文獻(xiàn)[4]和文獻(xiàn)[5]的仿真實(shí)驗(yàn)結(jié)果表明:APO算法具有較好的全局搜索能力，在收斂性、魯棒性和穩(wěn)定性上，APO算法優(yōu)于PSO算法和傳統(tǒng)的遺傳算法[8]。

文獻(xiàn)[9]提出了基于聚集函數(shù)法的無約束多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法SMOPSO，該算法借鑒聚集函數(shù)法的思想，利用APO算法實(shí)現(xiàn)了對多目標(biāo)優(yōu)化問題中Pareto最優(yōu)解集的搜索，并且在搜索過程中動(dòng)態(tài)調(diào)整慣性權(quán)重與引力因子;提出了基于虛擬力排序的多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法VFMOAOP，該算法根據(jù)非劣解集中的個(gè)體作用于其他個(gè)體的虛擬力之和的大小進(jìn)行排序，并將作用于其他個(gè)體的虛擬力之和的最大者作為全局最優(yōu)個(gè)體;提出了基于序值的多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法RMOAPO，利用多目標(biāo)優(yōu)化領(lǐng)域中的序值概念來定義質(zhì)量函數(shù)，以充分體現(xiàn)出多目標(biāo)優(yōu)化問題自身的特點(diǎn)。

上述SMOAPO算法和VFMOAPO算法中，未充分體現(xiàn)Pareto的支配概念，在RMOAPO算法中，Pareto支配關(guān)系雖有體現(xiàn)，但在計(jì)算鄰域擁擠度時(shí)，用到的鄰域半徑參數(shù)ε的選取和調(diào)整比較困難。針對上述問題，本文提出了基于非支配排序思想的多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法(Non-dominated MOAPO，NDMOAPO)，通過非支配排序，確定個(gè)體層次，然后算出個(gè)體擁擠距離，再改進(jìn)MOAPO中的質(zhì)量函數(shù)，使得算法具有較好的分布性。

1 基于非支配排序的多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法思想

在MOAPO算法中，全局最好適應(yīng)值fbest、全局最差適應(yīng)值fworst、引力常數(shù)G及質(zhì)量函數(shù)的選擇均是關(guān)鍵[10]。NDMOAPO算法首先通過個(gè)體間的非支配關(guān)系對群體進(jìn)行非支配排序，然后計(jì)算出每層中的各個(gè)個(gè)體的擁擠距離，若某層上的個(gè)體數(shù)小于三個(gè)，則對該層上的個(gè)體分配整個(gè)群體中的最大擁擠距離。因?yàn)榫奂芏刃〉膫€(gè)體其擁擠距離反而大，對于這樣的個(gè)體是予以保留的，以維護(hù)種群的分布性。若某層上的個(gè)體數(shù)大于三個(gè)，則對于除邊緣個(gè)體外的其他個(gè)體計(jì)算其擁擠距離，并求出最大擁擠距離。對于邊緣個(gè)體，則直接賦予它本層上的最大的擁擠距離，這樣以確保它們能在每次的迭代過程中被保留下來。而全局最好適應(yīng)值fbest和全局最差適應(yīng)值fworst則是根據(jù)文獻(xiàn)[11]中的隨機(jī)權(quán)重方法得到的。

Step1:初始化種群，給定種群規(guī)模pn，最大迭代次數(shù)tmax，隨機(jī)產(chǎn)生種群個(gè)體的初始位置和初始速度，進(jìn)化代數(shù)n=0;

Step2:算出每個(gè)個(gè)體對應(yīng)于目標(biāo)函數(shù)f1，…fn的函數(shù)值，然后根據(jù)每個(gè)個(gè)體的函數(shù)值對個(gè)體進(jìn)行非支配排序即非支配分層。對各層上排好序的個(gè)體進(jìn)行如下操作:

·求出最大擁擠距離 dmax和最小擁擠距離dmin，邊緣個(gè)體的擁擠距離則取本層中的最大擁擠距離。

·對前面所算出的目標(biāo)函數(shù)值，求得每個(gè)目標(biāo)函數(shù)值對應(yīng)的最大與最小函數(shù)值，再使用賦予隨機(jī)權(quán)重的方式得出全局最好適應(yīng)值fbest和全局最差適應(yīng)值fworst.

Step5:根據(jù)得到的個(gè)體質(zhì)量mi和個(gè)體所受合力Fi，k，結(jié)合式vi，k(t+1)=wvi，k(t)+ αFi，k/mi，?i≠best和式 xi，k(t+1)=xi，k(t)+vi，k(t+1)，?i≠ best更新個(gè)體的速度和位置;

Step6:若滿足終止條件，則結(jié)束程序;若不滿足，則返回Step2.

2 實(shí)驗(yàn)與結(jié)果分析

為了檢測本文提出的算法的效果，本文對上述算法進(jìn)行了測試。分別采用Schaffer1測試函數(shù)與Deb 提出的 ZDT 系列函數(shù)[12](ZDT1，ZDT2，ZDT3，ZDT4及 ZDT6)進(jìn)行測試，并與經(jīng)典算法 NSGA2[1]，及文獻(xiàn)[13]中的MOPSO算法進(jìn)行比較分析。并將本文算法得到的測試結(jié)果與文獻(xiàn)[9]中的SMOAPO算法、VFMOAPO算法和 RMOAPO算法進(jìn)行比較分析。

2.1 使用的測試函數(shù)

實(shí)驗(yàn)中使用的6個(gè)測試函數(shù)，均是二維目標(biāo)的。Schaffer1的決策空間是一維的，ZDT1，ZDT2和ZDT3的決策空間均是30維的，ZDT4和ZDT6的決策空間是10維的。三種算法的群體規(guī)模均為50個(gè)，最大迭代次數(shù)均為200次，每個(gè)算法對每個(gè)測試函數(shù)在相同條件下獨(dú)立運(yùn)行30次。與文獻(xiàn)[9]中的算法進(jìn)行比較，選取的最大迭代次數(shù)為100次。

2.2 評價(jià)方法

為了對算法的性能進(jìn)行分析，在此采用兩個(gè)性能評價(jià)指標(biāo):GD(Generation Distance)和SP(Spacing)。

(1)GD:GD為當(dāng)代距離，主要用于評價(jià)算法的收斂性[3]。其定義如下:

其中n為解集中的個(gè)體數(shù)目，di為算法中得到的第i個(gè)解到全局最優(yōu)非劣解的最小歐幾里得距離。GD越小說明所得的解集越接近全局最優(yōu)區(qū)域。

(2)SP:主要是用于評價(jià)算法的分布性，是目前使用最多的用于評價(jià)分布性的參數(shù)。其定義如下:

2.3 實(shí)驗(yàn)結(jié)果

圖1～圖6為NDMOAPO對六個(gè)測試函數(shù)生成的Pareto Front與真實(shí)的Pareto Front的對比圖。表1與表2為NDMOAPO算法、MOPSO算法與NSGA2算法關(guān)于六個(gè)測試函數(shù)的GD與SP值。表3與表4為NDMOAPO算法、SMOAPO算法、VFMOAPO算法和RMOAPO算法關(guān)于六個(gè)測試函數(shù)的GD與SP值。

圖1 Schaffer1的Pareto前沿Fig.1 The Pareto front of Schaffer1

圖2 ZDT1的Pareto前沿Fig.2 The Pareto front of ZDT1

2.4 實(shí)驗(yàn)結(jié)果分析

圖3 ZDT2的Pareto前沿Fig.3 The Pareto front of ZDT2

圖4 ZDT3的Pareto前沿Fig.4 The Pareto front of ZDT3

圖5 ZDT4的Pareto前沿Fig.5 The Pareto front of ZDT4

圖6 ZDT6的Pareto前沿Fig.6 The Pareto front of ZDT6

從圖1可以看出，NDMOAPO的解基本上能覆蓋真實(shí)Pareto前沿。由表1與表2可以看出，MOPSO的GD值較小，NDMOAPO的GD值略大于MOPSO的GD值，比NSGA-II的GD值要好，但其解的分布性要比其他兩種算法的解的分布性都要好。對于ZDT1，ZDT2，ZDT3，ZDT4 和ZDT6 函數(shù)，從圖2至圖6中可以看出NDMOAPO算法得到的Pareto前沿接近真實(shí)的Pareto前沿。從表1與表2中還可以看出，NDMOAPO的GD值與SP值均要好于其他兩種算法的相應(yīng)指標(biāo)，因此NDMOAPO算法對真實(shí)解集的逼近程度與Pareto解集的分布性要更好。

從表3與表4可以看出NDMOAPO的GD值略差于 VFMOAPO和 RMOAPO，要好于 SMOAPO，但其解的分布性要好于其他三種算法。通過6個(gè)典型的多目標(biāo)測試函數(shù)的優(yōu)化實(shí)驗(yàn)可知，與MOPSO算法、NSGA-II算法、文獻(xiàn)[9]中的三種算法相比，提出的NDMOAPO算法能有效地收斂到真實(shí)Pareto前沿，并且得到的解集分布更加均勻。

3 結(jié)論

本文提出了引入非支配排序思想的多目標(biāo)擬態(tài)物理學(xué)算法，通過對整個(gè)種群進(jìn)行排序，再計(jì)算擁擠距離，保留適應(yīng)值好且擁擠距離大的個(gè)體，使得算法的分布性較好。通過仿真實(shí)驗(yàn)與MOPSO，NSGA2及文獻(xiàn)[9]中的三種算法進(jìn)行比較分析得知，該算法在逼近真實(shí)解的程度和解集的分布性上有較好的效果。

由于本算法中在對最優(yōu)適應(yīng)值fbest的選取上采用的是隨機(jī)權(quán)重的方式，沒有充分體現(xiàn)出多目標(biāo)優(yōu)化問題的本質(zhì)特征。如何采用更好的策略來選取全局適應(yīng)值，以及算法中用到的相關(guān)參數(shù)對實(shí)驗(yàn)結(jié)果的影響還有待進(jìn)一步研究。

表1 NDMOAPO及比較算法MOPSO和NSGA2的GD值比較Tab.1 The comparison of GD values of NDMOAPO，MOPSO and NSGA2

表2 NDMOAPO及比較算法MOPSO和NSGA2的SP值比較Tab.2 The comparison of SP values of NDMOAPO，MOPSO and NSGA2

表3 NDMOAPO及文獻(xiàn)[9]中的算法的GD值比較Tab.3 The comparison of GD values of NDMOAPO and the algorithm in Literature[9]

表4 NDMOAPO及文獻(xiàn)[9]中的算法的SP值比較Tab.4 The comparison of SP values of NDMOAPO and the algorithm in Literature[9]

[1]DEB K，PRATAP A，AGRAWAL S，et al.A Fast and Elitist Multi-Objective Genetic Algorithm:NSGA2II[R].KanGAL Report No.200001.India，2000.

[2]ZITZLER E，LAUMANNS M，THIELE L.SPEA2:Improving the strength Pareto evolutionary algorithm[C]//Giannakoglou K，Tsa-halis DT，Périaux J，Papailiou KD，F(xiàn)ogarty.Evolutionary Methods for Design，Optimization and Control with Applications to Industrial Problems.Berlin:Springer-Verlag，2002.95-100.

[3]COELLO COELLO CA，PULIDO GT，LECHUGA MS.Handling multiple objectives with particle swarm optimization[J].IEEE Trans on Evolutionary Computations，2004，8(3):256-279.

[4]Xie L P，Zeng J C.A Global Optimization Based on Physicomimetics Framework[C]//The 2009 World Summit on Genetic and Evolutionary Computation，Shanghai，2009，609-616.

[5]Xie Liping，Zeng Jianchao，Cui Zhihua.Using Artificial Physics to Solve Global Optimization Problems[C]//the 8th IEEE International Conference on Cognitive Informatics(ICCI 2009)，Hong Kong，2009，502-508.

[6]Xie L P，Zeng J C，Cui Z H.On mass effects to artificial physics optimization algorithm for global optimization problems[J].International Journal of Innovative Computing and Applications(IJICA)，2010，2(2):69-76.

[7]謝麗萍.基于擬態(tài)物理學(xué)優(yōu)化的全局優(yōu)化算法設(shè)計(jì)及性能分析[D].蘭州:蘭州理工大學(xué)，2010.

[8]伊健.基于可行性規(guī)則的擬態(tài)物理學(xué)約束優(yōu)化算法研究[D].太原:太原科技大學(xué)，2011.

[9]王艷.多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法及其應(yīng)用研究[D].蘭州:蘭州理工大學(xué)，2011.

[10]王艷，曾建潮.一種基于擬態(tài)物理學(xué)優(yōu)化的多目標(biāo)優(yōu)化算法[J].控制與決策，2010，25(7):1040-1044.

[11]PARSOPOULOS K E，VRAHATIS M N.Particle swarm optimization method in multi-objective problems[C]//SAC 2002，Madrid，2002:603-607.

[12]ZITZLER E，DEB K，and THIELE L.Comparison of Multi-objective Evolutionary Algorithms:Empirical Results[J].Evolutionary Computation，2000，8(2):173-195.

[13]張利彪，周春光，馬銘，等.基于粒子群算法求解多目標(biāo)優(yōu)化問題[J].計(jì)算機(jī)研究與發(fā)展，2004，41(7):1286-1291.