基于非支配排序的多目标拟态物理学优化算法

蔡巧珍，谭 瑛，王 艳

(太原科技大学复杂系统与计算智能实验室，太原 030024)

现实世界中的很多问题通常由多个目标组成，这些子目标之间可能是相互冲突的，某个子目标的改善可能会引起其他子目标性能的降低，因此多目标优化问题通常需要对相互冲突的子目标进行综合考虑，即对各子目标进行折衷。针对多目标优化问题，典型的有Deb等提出的非劣排序遗传算法NSGAII[1]，Zitzler 等提出的强Pareto进化算法SPEA2[2]等。随着多目标优化问题研究的深入，一些新的进化机制也被引入进化多目标优化领域，如Coello Coello等人基于粒子群优化提出的Multi-objective Particle Swarm Optimization(MOPSO)[3]。

拟态物理学优化(Artificial Physics Optimization，APO)算法[4-7]是由谢丽萍和曾建潮于 2009 年提出的。该算法建立个体间与适应值优劣有关的简单引斥力规则，由三部分组成:初始化种群，计算个体所受合力和个体运动。APO算法已经成功用于单目标优化问题中，文献[4]和文献[5]的仿真实验结果表明:APO算法具有较好的全局搜索能力，在收敛性、鲁棒性和稳定性上，APO算法优于PSO算法和传统的遗传算法[8]。

文献[9]提出了基于聚集函数法的无约束多目标拟态物理学优化算法SMOPSO，该算法借鉴聚集函数法的思想，利用APO算法实现了对多目标优化问题中Pareto最优解集的搜索，并且在搜索过程中动态调整惯性权重与引力因子;提出了基于虚拟力排序的多目标拟态物理学优化算法VFMOAOP，该算法根据非劣解集中的个体作用于其他个体的虚拟力之和的大小进行排序，并将作用于其他个体的虚拟力之和的最大者作为全局最优个体;提出了基于序值的多目标拟态物理学优化算法RMOAPO，利用多目标优化领域中的序值概念来定义质量函数，以充分体现出多目标优化问题自身的特点。

上述SMOAPO算法和VFMOAPO算法中，未充分体现Pareto的支配概念，在RMOAPO算法中，Pareto支配关系虽有体现，但在计算邻域拥挤度时，用到的邻域半径参数ε的选取和调整比较困难。针对上述问题，本文提出了基于非支配排序思想的多目标拟态物理学优化算法(Non-dominated MOAPO，NDMOAPO)，通过非支配排序，确定个体层次，然后算出个体拥挤距离，再改进MOAPO中的质量函数，使得算法具有较好的分布性。

1 基于非支配排序的多目标拟态物理学优化算法思想

在MOAPO算法中，全局最好适应值fbest、全局最差适应值fworst、引力常数G及质量函数的选择均是关键[10]。NDMOAPO算法首先通过个体间的非支配关系对群体进行非支配排序，然后计算出每层中的各个个体的拥挤距离，若某层上的个体数小于三个，则对该层上的个体分配整个群体中的最大拥挤距离。因为聚集密度小的个体其拥挤距离反而大，对于这样的个体是予以保留的，以维护种群的分布性。若某层上的个体数大于三个，则对于除边缘个体外的其他个体计算其拥挤距离，并求出最大拥挤距离。对于边缘个体，则直接赋予它本层上的最大的拥挤距离，这样以确保它们能在每次的迭代过程中被保留下来。而全局最好适应值fbest和全局最差适应值fworst则是根据文献[11]中的随机权重方法得到的。

Step1:初始化种群，给定种群规模pn，最大迭代次数tmax，随机产生种群个体的初始位置和初始速度，进化代数n=0;

Step2:算出每个个体对应于目标函数f1，…fn的函数值，然后根据每个个体的函数值对个体进行非支配排序即非支配分层。对各层上排好序的个体进行如下操作:

·求出最大拥挤距离 dmax和最小拥挤距离dmin，边缘个体的拥挤距离则取本层中的最大拥挤距离。

·对前面所算出的目标函数值，求得每个目标函数值对应的最大与最小函数值，再使用赋予随机权重的方式得出全局最好适应值fbest和全局最差适应值fworst.

Step5:根据得到的个体质量mi和个体所受合力Fi，k，结合式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:若满足终止条件，则结束程序;若不满足，则返回Step2.

2 实验与结果分析

为了检测本文提出的算法的效果，本文对上述算法进行了测试。分别采用Schaffer1测试函数与Deb 提出的 ZDT 系列函数[12](ZDT1，ZDT2，ZDT3，ZDT4及 ZDT6)进行测试，并与经典算法 NSGA2[1]，及文献[13]中的MOPSO算法进行比较分析。并将本文算法得到的测试结果与文献[9]中的SMOAPO算法、VFMOAPO算法和 RMOAPO算法进行比较分析。

2.1 使用的测试函数

实验中使用的6个测试函数，均是二维目标的。Schaffer1的决策空间是一维的，ZDT1，ZDT2和ZDT3的决策空间均是30维的，ZDT4和ZDT6的决策空间是10维的。三种算法的群体规模均为50个，最大迭代次数均为200次，每个算法对每个测试函数在相同条件下独立运行30次。与文献[9]中的算法进行比较，选取的最大迭代次数为100次。

2.2 评价方法

为了对算法的性能进行分析，在此采用两个性能评价指标:GD(Generation Distance)和SP(Spacing)。

(1)GD:GD为当代距离，主要用于评价算法的收敛性[3]。其定义如下:

其中n为解集中的个体数目，di为算法中得到的第i个解到全局最优非劣解的最小欧几里得距离。GD越小说明所得的解集越接近全局最优区域。

(2)SP:主要是用于评价算法的分布性，是目前使用最多的用于评价分布性的参数。其定义如下:

2.3 实验结果

图1～图6为NDMOAPO对六个测试函数生成的Pareto Front与真实的Pareto Front的对比图。表1与表2为NDMOAPO算法、MOPSO算法与NSGA2算法关于六个测试函数的GD与SP值。表3与表4为NDMOAPO算法、SMOAPO算法、VFMOAPO算法和RMOAPO算法关于六个测试函数的GD与SP值。

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

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

2.4 实验结果分析

图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 函数，从图2至图6中可以看出NDMOAPO算法得到的Pareto前沿接近真实的Pareto前沿。从表1与表2中还可以看出，NDMOAPO的GD值与SP值均要好于其他两种算法的相应指标，因此NDMOAPO算法对真实解集的逼近程度与Pareto解集的分布性要更好。

从表3与表4可以看出NDMOAPO的GD值略差于 VFMOAPO和 RMOAPO，要好于 SMOAPO，但其解的分布性要好于其他三种算法。通过6个典型的多目标测试函数的优化实验可知，与MOPSO算法、NSGA-II算法、文献[9]中的三种算法相比，提出的NDMOAPO算法能有效地收敛到真实Pareto前沿，并且得到的解集分布更加均匀。

3 结论

本文提出了引入非支配排序思想的多目标拟态物理学算法，通过对整个种群进行排序，再计算拥挤距离，保留适应值好且拥挤距离大的个体，使得算法的分布性较好。通过仿真实验与MOPSO，NSGA2及文献[9]中的三种算法进行比较分析得知，该算法在逼近真实解的程度和解集的分布性上有较好的效果。

由于本算法中在对最优适应值fbest的选取上采用的是随机权重的方式，没有充分体现出多目标优化问题的本质特征。如何采用更好的策略来选取全局适应值，以及算法中用到的相关参数对实验结果的影响还有待进一步研究。

表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，Fogarty.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]谢丽萍.基于拟态物理学优化的全局优化算法设计及性能分析[D].兰州:兰州理工大学，2010.

[8]伊健.基于可行性规则的拟态物理学约束优化算法研究[D].太原:太原科技大学，2011.

[9]王艳.多目标拟态物理学优化算法及其应用研究[D].兰州:兰州理工大学，2011.

[10]王艳，曾建潮.一种基于拟态物理学优化的多目标优化算法[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]张利彪，周春光，马铭，等.基于粒子群算法求解多目标优化问题[J].计算机研究与发展，2004，41(7):1286-1291.