基于偏好的ε-Pareto支配的多目标粒子群算法

李　静，黄天民，陈尚云(西南交通大学数学学院， 四川　成都　611756 )

现实的优化问题一般涉及对多个目标的同时优化[1-4]。进化算法的思想是将实际问题的需求转化为目标函数，再采用某种机制来搜索解，最终解决实际问题。近年来的算法都有一些类似的特征，在采用进化算法进行搜索时，并未严格地模拟生物进化，而是采用适当的措施进行精英保留，在整体上沿用进化的思想。文献[5-7]采用局部搜索的操作，使计算复杂度有所降低，对档案集合的过程进行了更新，具有较好的进化性能和收敛速度，但是对归档集合的规模大小并未限制。文献[8]基于种群多样度理论，采用排序的自适应缩放因子和自适应交叉因子相结合的双变异策略，提出了一种较稳定且收敛速度较快的算法。

Kennedy等模拟鸟群觅食行为得出一种基于种群的解决优化问题的进化算法，并称之为粒子群进化算法[9](particle swarmoptimization,PSO)。该算法的最终目的是得到解决方案使决策者满意，并不需要在整个Pareto 前沿上搜寻最优解。于是，在解决多目标优化问题时，可以将决策者的偏好信息加入到搜索过程中，利用偏好(preference)信息[10-13]引导粒子倾向决策者满意的区域就能有效提高算法的运行效率。文献[14]在粒子群算法的基础上，考虑参考点与参考区的动态变化，提出了一种综合偏好引导策略。考虑到粒子容易陷入局部最优的问题，本文引入了拥挤度函数和突变策略，以提高算法的效率，然后在归档集的筛选中引入了决策者的偏好信息，这样在提高算法运行速度的同时也得到了令决策者满意的Pareto最优解。

1　相关概念

1.1　基本概念

设有m个相互冲突的优化目标

f(X)={f1(X),f2(X),…,fm(X)}，

(1)

给定决策变量X=(x1,x2,…,xn),满足

R={X|X∈Rn,gi(X)≤0,j(X)=0,

i=1,2,…,k;j=1,2,…,l}。

(2)

多目标优化问题的一般描述为

minf(X)={f1(X),f2(X),…,fm(X)}。

(3)

1.2　拥挤度函数

对于Pareto最优解前沿上的解Pk,解Pk的拥挤距离[4]为

1.3　角度偏好区域的设定

本文采用文献[15-16]中的设定方法，预先设定偏好角度α及参考点r的分量ri(i=1,2,…,M)，把参考点r与坐标原点0的连线作为参考线。偏好角度应适当取小，在本文实验中取0.05。参考点是根据各分量与Pareto边界的距离来进行调整。

当产生新的子代个体时，通过

计算新个体与参考线的夹角θ，从而对个体是否位于偏好区域进行判断。若θ≤α，则该个体位于偏好区域；否则，位于非偏好区域。

2　基于偏好的ε-Pareto支配的多目标粒子群算法(AP-εPSO)

2.1　突变的类型

本文的突变[17]是分为2种类型：统一突变和非统一突变。统一突变是指子代中每个决策变量的变化范围都是常数；非统一突变是指子代中每个决策变量的变化范围是随着时间减少的。定义突变率为1/codesize，codesize指编码所有决策变量的字符串总长(在本算法中指的是变量的个数)。为简化数学模型，本文采用渐进缩小的突变，将决策变量个数减少，其次在不改变数量的基础上，对决策变量本身进行改变，最终通过突变使解空间变大。

2.2　算法的主要流程

在AP-εPSO算法中引入突变操作，并且利用ε-Pareto排序、角度偏好来筛选Pareto前沿上的最优解。算法的主要流程如下。

第1步，新个体new-particle偏好区域的设定：

Step1，根据式(5)计算角度θ；

Step2，若θ≤α，则new-particle居于偏好区域，否则，new-particle居于非偏好区域。

第2步，粒子的初始化和具体迭代：

Step1，设定最大迭代次数、参考点及角度值，初始化种群，初始化非支配解，将非支配解归结到外部归档集；

Step2，计算外部归档集中的非支配解的拥挤度，若拥挤度的个数大于可允许的最大值，则仅有拥挤度值大的非支配解被保留下来；

Step3，将种群细分为3部分，分别进行突变操作，第1个子部分不发生突变，第2个子部分发生统一突变，第3个子部分发生非统一突变；

Step4，更新位置、速度，计算新个体是否位于偏好区域，并且更新外部归档集；

Step5，判断是否达到算法终止条件，如是，则输出当前归档集种群作为最终结果，否则转Step3。

本算法在更新外部归档集中引入决策者的偏好信息，通过Pareto支配[16]、ε-Pareto支配[10]求得的Pareto最优解进行筛选，删除位于非偏好区域的Pareto最优解，使最终得出的Pareto最优解的个数减少且目标函数值最优。它的有效性将通过实验进行验证。算法的流程如图1所示，更新外部归档集如图2所示。

图1　算法流程图

图2　更新外部归档集

2.3　对比评价指标与实验结果

2.3.1GD值

当代距离(generational distance,GD)指标[1]定义为一种表示Pareto最优前沿距真实Pareto前沿的远近程度的数值。其表达式为

式中：n为Pareto最优前沿解的数量；通常p=2；di为目标空间中真实Pareto前端的每个向量与其最邻近向量之间的欧几里得距离。

2.3.2SP值

Scott提出一种度量Pareto前沿中邻居向量的距离方差方案，该方法无须设置参数且已知Pareto面，是目前常用的均匀性评价指标之一。评价函数[1]定义为

式中：

i=1,2,…,n，j=1,2,…n；

(8)

2.3.3实验结果

表1为测试函数。表2为测试函数的运行参数。在表1中DTLZ1、DTLZ2及DTLZ3的|XM|=K,决策变量的后K(K=(n-M+1))个变量表示为XM并且g(XM)≥0,在本论文中M=3。

表1　测试函数

表1(续)

表2　算法中的运行参数设置

为验证算法的分布性与收敛性，对比本算法AP-εPSO与G-NSGA-Ⅱ[5]、R-NSGA-Ⅱ[5]以及光束搜索[18]在ZDT1、ZDT2、ZDT3、DTLZ1、DTLZ2、DTLZ3的GD值；并比较本算法AP-εPSO与SPEA2、NSGA-Ⅱ的SP值。偏好角度值设为0.05,二维ZDT1、ZDT2、ZDT3测试函数的参考点分别为(0.3,0.4)、(0.8,0.6)、(0.4,0.6)。三维DTLZ1、DTLZ2、DTLZ3测试函数的参考点分别为(0.5,0.5,0.5)、(0.4,0.7,0.9)、(0.2,0.3,0.7)。

表3示出各算法的GD值。可以看出，AP-εPSO算法的GD值整体上小于其他几种算法，说明收敛性明显强于其他几种算法，所求出来的Pareto边界比较接近真实的Pareto边界。相比其他算法，利用AP-εPSO得出的Pareto解与真实的Pareto前端的距离也是比较接近的，仅在ZDT2上稍差于光速搜索算法的解。

表3　GD指标统计值

表4示出各种算法的SP值。可以看出，在ZDT1与DTLZ2 2个函数上，AP-εPSO的SP值要劣于SPEA2的。这是因为本算法在求解问题时引入了决策者的偏好信息，对Pareto最优解进行了进一步的筛选，使所得出的解都是在决策者的偏好区域内的Pareto最优解，最终解的分布会比较集中。这正是本文所要达到的一种结果。

表4　SP指标统计值

3　结束语

本文将粒子群算法与ε-Pareto支配结合起来，采用精英策略将非支配解提出来组成外部归档集，用拥挤度函数来控制归档集的大小；对整个粒子群采取突变操作，增加粒子的多样性；利用参考点与角度值将决策者提供的偏好信息引入到多目标粒子群算法中，根据与最优个体的角度值大小来判断其是位于偏好区域还是非偏好区域；最终针对新个体与位于归档集中个体所在的不同区域采取不同的筛选条件来更新外部归档集。与经典算法的对比实验,验证该算法具有可行性。该算法仍存在许多待解决的问题，而且在实际优化问题中，如何具体确定参考点及角度值仍需要考虑，下一步主要针对具体的实际问题设定相应的算法。

[1]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社,2006.

[2]郑金华.多目标进化算法及其应用[M].北京:科学出版社, 2007.

[3]郑向伟,刘弘.多目标进化算法研究进展[J].计算机科学,2007,34(7):187.

[4]李艳丽,黄天民,刘雅雅. 一种新型的带有小生境技术和精英集策略的多目标粒子群算法[J]. 西华大学学报(自然科学版),2016,35(1):73.

[5]DEB K,PRATAP A,AGARWAL S,et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J].IEEE Trans on Evolutionary Computation,2002,6(2):182.

[6]KNOWLES J,CORNE D.The pareto archived evolution strategy: a new base line algorithm formulti-objective optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation Piscataway. NJ:IEEE Press,1999: 98-105.

[7]ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength pareto evolutionary algorithm[R]. Technical Report,Zurich,Swiss: Swiss Federal Institute of Technology, 2001.

[8]李荣雨,陈庆倩,陈菲尔.改变种群多样性的双差异差分进化算法[J].运筹学学报,2017,21(1):444.

[9]KENNEDY J,EBERHART R. Particle swarm optimization[C]//Proceedings of the 1995 IEEE International Conference Oil Neural Networks. Piscataway，NY：IEEE Service Center，1995:1942.

[10]DEB K,MOHAN M,MISHRA S. Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions[J]. Evolutionary Computation, 2005, 13(4): 501.

[11]麦雄发，李玲.基于决策者偏好区域的多目标粒子群算法研究[J]．计算机应用研究，2010，27(4):1301.

[12]DEB K,SUNDAR J,BHASKARA U,et al. Reference point based multi objective optimization using evolutionary algorithm[J]. International Journal of Computational Intelligence Research,2006,2(3):273.

[13]李纬，张兴华.一种改进的基于Pareto解的多目标粒子群算法[J]. 计算机仿真,2010，27(5):96.

[14]戴永彬.一种基于综合引导的偏好多目标优化算法[J].中南大学学报(自然科学版),2016，47(9):3072.

[15]郑金华,谢谆志.关于如何用角度信息引入决策者偏好的研究[J].电子学报,2014,42(11):2239.

[16]郑金华,赖念,郭观七.多目标进化算法中基于角度偏好的ε-Pareto 支配策略[J].模式识别与人工智能,2014，27(6):569.

[17]LAUMANNS M, THIELE L, DEB K, et al.Combining convergence anddiversity in evolutionary multi-objective optimization[J].Evolutionary Computation,2002,10(3):263.

[18]DEB K,KUMAR A.Light beam search based multi-objective optimization using evolutionary algorithms [C]// Proc of the IEEE Congress on Evolutionary Computation. Singapor：IEEE, 2007: 2125-2132.