蔡巧珍，譚 瑛，王 艷

(太原科技大學復(fù)雜系統(tǒng)與計算智能實驗室，太原 030024)

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

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

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

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

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

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

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

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

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

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

Step5:根據(jù)得到的個體質(zhì)量mi和個體所受合力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更新個體的速度和位置;

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

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

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

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

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

2.2 評價方法

為了對算法的性能進行分析，在此采用兩個性能評價指標:GD(Generation Distance)和SP(Spacing)。

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

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

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

2.3 實驗結(jié)果

圖1～圖6為NDMOAPO對六個測試函數(shù)生成的Pareto Front與真實的Pareto Front的對比圖。表1與表2為NDMOAPO算法、MOPSO算法與NSGA2算法關(guān)于六個測試函數(shù)的GD與SP值。表3與表4為NDMOAPO算法、SMOAPO算法、VFMOAPO算法和RMOAPO算法關(guān)于六個測試函數(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 實驗結(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的解基本上能覆蓋真實Pareto前沿。由表1與表2可以看出，MOPSO的GD值較小，NDMOAPO的GD值略大于MOPSO的GD值，比NSGA-II的GD值要好，但其解的分布性要比其他兩種算法的解的分布性都要好。對于ZDT1，ZDT2，ZDT3，ZDT4 和ZDT6 函數(shù)，從圖2至圖6中可以看出NDMOAPO算法得到的Pareto前沿接近真實的Pareto前沿。從表1與表2中還可以看出，NDMOAPO的GD值與SP值均要好于其他兩種算法的相應(yīng)指標，因此NDMOAPO算法對真實解集的逼近程度與Pareto解集的分布性要更好。

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

3 結(jié)論

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

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

表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及文獻[9]中的算法的GD值比較Tab.3 The comparison of GD values of NDMOAPO and the algorithm in Literature[9]

表4 NDMOAPO及文獻[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)物理學優(yōu)化的全局優(yōu)化算法設(shè)計及性能分析[D].蘭州:蘭州理工大學，2010.

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

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

[10]王艷，曾建潮.一種基于擬態(tài)物理學優(yōu)化的多目標優(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]張利彪，周春光，馬銘，等.基于粒子群算法求解多目標優(yōu)化問題[J].計算機研究與發(fā)展，2004，41(7):1286-1291.