基于网格投影的超多目标进化算法

高智阔,陈未如,彭弗楠

(1.沈阳化工大学 计算机科学与技术学院,辽宁 沈阳 110142;2.辽宁省化工过程工业智能化技术重点实验室,辽宁 沈阳 110142)

0 引 言

在社会生产和工程应用等领域,存在着许多的优化问题涉及对多个目标进行优化,并且绝大多数目标之间是相互关联并相互冲突的。当目标数为2或3时,这类问题被称为多目标优化问题(multi-objective optimization problem,MOP)[1]。当目标数大于3时,这类问题被称为超多目标优化问题(many-objective optimization problem, MaOP)[2]。社会实际应用中出现了大量的MaOP例子,如路径规划问题[3]、电力优化问题[4]、零件加工问题[5]等。

针对多目标优化问题,研究人员结合进化算法提出了很多多目标进化算法(multi-objective evolutionary algorithms,MOEAs),根据进化机制[6]不同可将MOEAs分为以下三种:基于支配关系的NSGA-II[7]、基于分解的MOEA/D[8]、基于性能评价指标的IBEA[9]。当目标数量过多时,使用这些算法求解超多目标优化问题的性能降低,在超多目标空间中保持解集的分布性和收敛性也很困难[10]。研究人员针对以上问题提出了很多超多目标进化算法(many-objective evolutionary algorithms,MaOEAs):如NSGA-III[11]在NSGA-II的基础上,引入了参考点针对临界支配层求解个体;R2-EMOA[12]针对种群采用快速非支配排序方法,针对临界层使用R2指标筛选个体;MOEA/DP[13]结合MOEA/D思想,针对投影面分解求解个体;KnRVEA[14]为子种群引入拐点自适应策略和参考向量相关联协同进化每一个子种群;NSGA/P[15]结合MOEA/P[16]的投影面思想,对NSGA-II进行投影支配改进;SPEA/R[17]采用目标空间分解为参考向量的策略,使用多样性优先收敛性第二的选择策略筛选个体。

随着目标维数的增加,种群内的个体大都是互不支配的。使用基于支配关系的多目标进化算法和超多目标进化算法求解个体时会存在解集收敛性和分布性不足的情况,如NSGA-II和NSGA-III。为解决上述问题,该文提出了一种基于网格投影的超多目标进化算法。该算法采用MOEA/P算法的投影思想针对目标空间进行降维操作,将目标空间划分为投影维目标空间和自由维目标空间,降低了对超多目标优化问题的求解难度,针对自由维目标空间引入网格适应度选取策略[18],使得算法求得的解集具有良好的收敛性和分布性。

1 背景知识

1.1 基本概念

多目标优化问题在一般情况下可以描述为最小化问题,数学描述如下:

(1)

(2)

其中,Fi(i=1,2,…,M)是需要最小化的第i个目标;Ω是决策空间。在公式(2)中,g是包含J个等式和不等式的约束函数,h是包含K个等式的约束函数;x=(x1,x2,…,xn)是决策空间中的决策向量;当目标个数M的值大于3时,称其为超多目标优化问题。

定义1 Pareto支配:针对决策空间中的两个个体x和y,有x支配y(记作xy),当且仅当x和y满足:

(3)

定义2 Pareto最优解:针对决策空间中的一个个体x*,当且仅当x*不被该决策空间中的其他任何个体x支配时,则称x*为Pareto最优解。

定义3 Pareto最优解集:由Pareto最优解组成的集合称为Pareto最优解集,即:

P*={x*}={x∈Ω|∃x'∈Ω,x'x}

(4)

定义4 Pareto前沿:P*中的全部个体映射到目标空间的集合,称为Pareto前沿,即:

PF*={F(x)=(F1(x),F2(x),…,FM(x))|

x∈P*}

(5)

1.2 MOEA/P算法框架

MOEA/P算法采用投影的思想,根据决策者的需求将目标空间分解为两部分,分别是投影面和自由维,以三维目标问题为例,如图1所示。其中投影面是决策者主要侧重的目标集,而自由维的目标集则在划分投影面的基础上进一步求解。

图1 将目标空间分解为投影面和自由维

1.3 GrEA算法思想

GrEA算法采用以个体为中心计算的思想,将个体在目标空间中的目标值计算取代为网格坐标值计算,将网格排序(GR)、网格拥挤距离(GCD)和网格坐标点距离(GCPD)作为个体筛选条件,筛选出目标空间中收敛性和分布性较优的个体。

2 GPEA算法

受MOEA/P算法和GrEA算法的启发,该文针对投影维目标空间引入MOEA/P算法的投影思想,针对自由维目标空间引入GrEA算法中的网格适应度策略筛选个体,设计了一种基于网格投影的超多目标进化算法(GPEA)。

2.1 算法基本思想

GPEA算法的基本思想是使用MOEA/P算法框架,将目标空间分解成投影维目标空间和自由维目标空间两部分。其中投影维目标空间被划分成若干个投影格。求解过程中,针对各投影格分别进化。在每代进化中,筛选落入投影格内的个体,再根据GrEA算法的网格思想将自由维目标空间均匀分段成若干自由格,计算个体相对于自由格的空间属性,利用个体非支配排序结果和自由维目标空间个体筛选策略对这些个体进行综合筛选。

2.1.1 自由维目标空间个体筛选策略

自由维目标空间个体选择策略是以个体在自由维目标空间内的自由格排序(FGR)作为首要筛选条件,自由格拥挤距离(FGCD)作为次要筛选条件,自由格坐标点距离(FGCPD)作为最后的筛选条件。

在对第i个自由维目标分配自由格坐标时,自由格下界、上界对应的目标值lbi和ubi见公式(6)和公式(7)。

lbi=mini(P)-(maxi(P)-mini(P))/(2×g)

(6)

ubi=maxi(P)+(maxi(P)-mini(P))/(2×g)

(7)

其中,mini(P)和maxi(P)是种群P在第i个自由维目标中的最小值和最大值,g是对自由维目标空间中各目标的分段数。

自由格在第i个自由维目标中的长度为di,计算方法见公式(8)。

di=(ubi-lbi)/g

(8)

这样,每一自由维的目标都被均匀分割成g个分段,所有自由维上的各个分段组合成自由格。如果把每个自由维各分段标号为0,1,…,g-1,用这些分段标号作为个体的自由格坐标。

定义5 自由格坐标:个体x所落入的自由格的坐标。个体x在第i个自由维上的自由格坐标是该个体所落入自由格在第i自由维上的分段标号。个体x的自由格坐标计算方法见公式(9)。

FGi(x)=⎣(FFi(x)-lbi)/di」

(9)

其中,lbi是自由格下界,di是自由格长度,它们的计算方法见式(6)和式(8),FF(x)=(FF1(x),FF2(x),…,FFf(x))为个体x在f个自由维组成的空间中对应的各自由维坐标向量,FFi(x)则是该向量在第i自由维上的分量。

定义6 自由格距离:自由格距离FGD用于表示个体x和y在自由维目标空间中的自由格坐标的相对位置关系,自由格距离FGD由公式(10)给出。

(10)

当个体x和y的自由格距离值小于自由维数f时,将个体y作为个体x的邻居。在自由维目标空间中,个体x的邻居组成的集合为FN(x)。

定义7 自由格排序:将个体在各个自由维的自由格坐标值的总和作为个体的自由格排序值。公式(11)为个体在自由维目标空间中的自由格排序计算公式。

(11)

定义8 自由格拥挤距离:将个体x在自由维目标空间上与其所有邻居之间的距离作为个体x自由格拥挤距离,其中N(x)是个体x的邻居组成的集合,f是自由维数。公式(12)为个体在自由维目标空间中的自由格拥挤距离计算公式。

(12)

定义9 自由格坐标点距离:将个体在自由维目标空间上的自由维目标值与自由格边界点目标值的欧氏距离作为自由格坐标点距离。公式(13)为个体在自由维目标空间中的自由格坐标点距离计算公式。

FGCPD(x)=

(13)

2.1.2 投影格适应度

投影格适应度是指个体x相对于投影格中心点Z的位置关系,个体的投影格适应度计算方法由公式(14)给出。

GP(x)=

(14)

其中,投影格中心点向量Z=(Z1,Z2,…,Zp);FP为归一化后的投影维目标空间,对应个体x在该空间的归一量为FP(x)=(FP1(x),FP2(x),…,FPp(x));p为投影维目标空间目标数,k为投影维分段数。

2.2 算法框架

GPEA算法框架描述如下:

GPEA算法

输入:

M(目标个数),

N(种群大小),

E(最大进化代数),

DS(标决策空间),

g(自由维自由格分段数),

k(投影维投影格分段数)

输出:目标解集OP

过程:

步骤1:目标空间划分。

根据DS设置将目标空间划分为投影维目标空间和自由维目标空间,其中投影维目标空间目标数为p,自由维目标空间目标数为f;投影维目标空间划分投影格数为kp,自由维目标空间的自由格数为gf;划分投影格并为投影格分配投影格序号i(i=1,2,…,kp)。

步骤2:初始化种群。

设投影格序号i=1,为其初始化大小为N的种群P1;

步骤3:种群进化。

步骤3.1:对种群Pi内的个体进行交叉变异产生子代个体,合并父代和子代的个体组成新种群CPi;计算种群CPi内所有个体的目标函数值,对投影维目标空间进行归一化操作,为所有个体计算投影格适应度;

步骤3.2:从种群CPi中选择N个良好的个体。

将种群CPi内全部个体投影到投影维目标空间中按照个体的投影格适应度进行分类,将落入投影格内的个体放入列表PL中,将落入投影格外的个体放入列表FL中;如果列表PL内的个体数大于等于N,则执行步骤3.2.1,否则执行步骤3.2.2;

步骤3.2.1:针对列表PL内的个体在自由维目标空间中进行非支配排序,生成的R个非支配子集F1,F2,…,FR;将非支配子集内个体依次放入列表LN中并保证LN内个体数小于N,直到Fr,当Fr放入列表LN时,LN内个体数刚好大于等于N;计算非支配子集Fr中个体的自由格排序FGR、自由格拥挤距离FGCD、自由格坐标点距离FGCPD,利用自由维目标空间个体筛选策略依次选择较优的个体放入列表LN中,直至列表LN内的个体数正好等于N。转步骤3.3;

步骤3.2.2:将列表PL内的所有个体放入到列表LN中,依次选择列表FL内投影适应度较优的个体依次放入到列表LN中,直至列表LN内的个体数量正好等于N。转步骤3.3;

步骤3.3:判断投影格种群Pi是否达到了最大进化代数E:

若种群Pi未达到最大进化代数,则将列表LN中的个体作为投影格i的新一代种群Pi,继续执行步骤3的种群进化操作;

若种群Pi达到了最大进化代数,则将列表LN中的个体并入目标解集OP中,并在OP中只保留非支配个体。此时,若i

步骤4:输出OP。

3 实验与分析

3.1 测试问题

该文选取DTLZ[19]测试问题集中的DTLZ1-DTLZ4测试问题作为比较的基础,其中DTLZ1和DTLZ3测试函数为算法收敛到Pareto前沿创造了很多困难,DTLZ2和DTLZ4测试函数用于测试算法处理不同形状问题的能力。这些测试问题都可以扩展到任意个数的目标和决策向量,用其来验证所提算法的性能。

3.2 性能指标

为了评价算法的综合性能,采用了反向迭代距离指标(IGD)[20]来评价算法求得解集的收敛性和分布性。IGD衡量的是算法求得的解集与真实Pareto前沿的个体之间的最小距离的平均值,计算IGD需要预先得到该问题的一组均匀的Pareto前沿真实解集。

IGD指标的计算公式为:

(15)

(16)

其中,S为算法求得的一组Pareto近似解集;P*为一组均匀采样的Pareto前沿点集;x是P*中的个体;s是S中的个体;|P*|是Pareto前沿点集中个体的数量;si是Pareto近似解集中个体s在第i个目标中的目标值;xi是Pareto前沿点集中个体x在第i个目标中的目标值;dist(x,s)是个体x到S最近的个体的欧氏距离。IGD的值越小,算法求得的解集越接近Pareto真实前沿,表明算法求得的解集具有较好的收敛性和多样性。

3.3 实验设计

为了验证该算法的性能,实验选取MOEA/D、GrEA、NSGA-III、NSGA/P、MOEA/DP作为对比,在DTLZ1～DTLZ4测试问题的3、5、7、10目标上进行实验。

交叉变异参数设置:为所有算法使用模拟二进制交叉操作和多项式变异操作,其中交叉概率设置为1,变异概率设置为1/n,n是决策变量个数,交叉变异的分布指标都设置为20。

算法自身对比参数设置:在10目标的DTLZ1～DTLZ4测试问题,决策变量个数n=12,进化代数E=6 000,种群大小N=220,性能指标选用IGD的实验条件下进行算法对比参数设置。为探究投影维目标空间设置对算法性能的影响,设置投影维目标空间数p依次为1,2,…,7,投影维分段数k=2,自由维分段数g=8;为探究投影维分段数k对算法性能的影响,设置k的值依次为1,2,…,7,自由维分段数g=8;为探究自由维分段数g对算法的影响,设置g的值依次为4,6,8,10,12,14,16,投影维分段数k=2。以上每组测试独立运行20次。

不同算法对比参数设置:设置所有测试问题对应的投影维分段数k=2,自由维分段数g=8;针对3目标问题,决策变量个数n=6,种群大小N=190,进化代数E=3 000,投影维数p=1;针对5目标问题,决策变量个数n=8,种群大小N=210,进化代数E=4 000,投影维数p=2;针对7目标问题,决策变量个数n=10,种群大小N=210,进化代数E=5 000,投影维数p=3;针对10目标问题,决策变量个数n=12,种群大小N=220,进化代数E=6 000,投影维数p=4;每组测试独立运行30次。

3.4 结果与分析

图2表示在投影维分段数k和自由维分段数g不变的情况下,投影维数p变化对IGD值变化的曲线。从图中可以看出,当投影维数小于3时,IGD值逐渐减小,使用投影思想可以提高算法的求解效果,降低了算法在自由维目标空间中求解难度;但是在投影维数超过3以后,IGD的值开始缓慢增加,在投影维数过多的时候,个体在自由维目标空间中的收敛性和分布性相对片面地表示个体在目标空间中的收敛性和分布性,此时算法的求解效果较差;当投影维数约占目标总数的1/3时,算法的求解效果较好。

图2 GPEA在DTLZ测试问题上不同 投影维数的IGD变化曲线

图3表示在投影维数p和自由维分段数g不变的情况下,投影维分段数k变化对IGD值变化的曲线。从图中可以看出,随着投影维分段数k的增加,IGD的值越好;在投影维分段数k设置为2及以后,IGD值的变化维持在了一个很小的范围之内;划分投影格对种群进化起促进作用,随着投影维划分段数的增加,进化的投影格也就越多,种群进化的时间成本也就越高,从算法求解时间方面考虑,建议将投影维分段数k设置为2。

图3 GPEA在DTLZ测试问题上不同投影 分段数的IGD变化曲线

图4表示在投影维数p和投影维分段数k不变的情况下,自由维分段数g变化对IGD值变化的曲线。从图中可以看出,随着自由维分段数g的增加,IGD的值越好;在自由维分段数g设置为8及以后,IGD的值得变化维持在了一个很小范围内;自由维网格坐标划分对种群的进化起促进作用,随着自由维划分段数g的增加,单位网格坐标范围减小,对应个体的网格排序值差异越大,在网格适应度计算中网格排序占据主导地位。从算法的求解效率方面考虑,建议将自由维分段数g设置为8。

图4 GPEA在DTLZ测试问题上不同 网格分段数的IGD变化曲线

表1给出了所有算法在DTLZ1～DTLZ4测试问题上得到的IGD均值。从实验结果中可以看出:GPEA在DTLZ1～DTLZ4测试问题上表现良好,在超多目标问题空间中,种群的收敛性和多样性得到了很好的均衡,以下针对每个DTLZ测试问题详细分析算法的性能表现。

表1 不同算法在目标数不同的DTLZ测试问题上获得的IGD均值

续表1

DTLZ1和DTLZ3测试问题具有较多的局部帕累托前沿(Pareto Front,PF),为算法求解此类问题创造了更多的障碍。DTLZ2和DTLZ4测试问题具有不同形状的PF,为算法求解此类问题维持种群多样性提供了困难。从表1可以看出,GPEA在大多数目标上取得了很好的结果,原因是投影维目标空间的投影格分解策略可以协助种群跳出局部PF,网格投影策略可以使种群收敛到Pareto前沿,网格适应度筛选策略可以使种群均匀的覆盖到PF,提高了算法求解此类问题的鲁棒性。

图5为各算法在7目标DTLZ4测试问题上求得最终解集的平行坐标图,从图5可以看出GPEA在收敛性和分布性上取得了较好的结果;MOEA/D存在某目标维解丢失的情况;GrEA和NSGA-III在某目标维上存在局部解集;NSGA/P和MOEA/DP的收敛性和分布性稍弱于GPEA。

4 结束语

针对超多目标优化问题使用多目标进化算法难以保证种群的收敛性和多样性的问题,提出了一种基于网格投影的超多目标进化算法。通过将目标空间拆分,分别构建投影维目标空间和自由维目标空间,使用投影格个体筛选策略和自由维目标空间个体筛选策略保持种群的收敛性和多样性,解决了MOEA求解超多目标优化问题难以平衡种群收敛性和多样性的问题。通过对标准测试函数设置不同参数实验,与MOEA/D、GrEA、NSGA-III、MOEA/DP和NSGA/P进行对比,实验结果表明,GPEA能够很好地处理超多目标优化问题。下一步工作是改进投影格个体选择策略,研究一种新的自由维目标空间适应度函数,并将算法与实际应用更好地结合起来。