分组策略下的高维目标协同进化算法

王丽萍,俞 维，邱飞岳

1(浙江工业大学 计算机科学与技术学院，杭州 310023)2(浙江工业大学 管理学院，杭州 310023)3(浙江工业大学 教育科学与技术学院，杭州 310023)4(浙江省可视媒体智能处理技术研究重点实验室，杭州 310023)

1 引 言

在调度优化[1]、路径规划[2]等现实问题中，通常存在两个及两个以上目标相互冲突，这类问题被称之为多目标优化问题(Multi-objective optimization problems，MOPs).文献[3]将目标数大于等于4的MOPs定义为高维目标优化问题(Many-Objective Optimization Problems，MaOPs).

为求解多目标优化问题，国内外研究者通过模拟自然界行为，提出了一系列智能启发式算法[4].基于支配关系的多目标进化算法是解决多目标优化问题的有效方法之一，但在处理高维目标优化问题时，非支配解在种群中的比例急剧增大，使得原有选择机制功能退化，选择压力急剧下降，阻碍种群收敛至前沿(Pareto Front，PF)，算法性能出现不同程度的下降[5].

这使得越来越多的学者开始关注MaOPs，并提出了一系列改进算法，代表性的算法如下：基于支配关系的高维目标进化算法，在传统的支配算法基础上，通过重新定义支配关系，如RPD-NSGA-II[6]、θ-dominance[7],或者引入新的多样性评价机制，如NSGA-III[8]、SPEA/R[9],以此提高算法性能；基于指标的高维目标进化算法，根据指标值对个体进行排序，如AR-MOEA[10]、MaOEA/IGD[11]等；基于分解的高维目标进化算法，将复杂多目标优化问题分解为多个单目标或多目标优化问题，以此协同优化，如MOEA/D-LWS[12]、MOEA/AD[13]、MOEA/D-AW[14].

近几年，文献[15]提出一种偏好引导地协同优化的思想(Preferences-inspired co-evolutionary algorithms,PICEAs).区别于基于个体间非支配关系的选择机制，PICEAs引入一组随机偏好集，利用随机偏好集与个体的支配关系，协同优化偏好集与种群.文献[16]将此概念进行实例化，提出目标向量引导地协同进化算法(PICEAg),将目标向量(Goal vector)作为偏好集，利用目标向量引导解集收敛.文献[17]表明PICEAg在高维WFG、DTLZ等测试问题上表现较好.但该算法在搜索过程中存在一定缺陷.在进化前期，基于种群与目标向量集间支配关系的选择机制能选择出收敛性较好的解，引导种群快速收敛；但在进化后期，在此机制的选择下，PICEAg易忽视分布性较好但全局搜索能力较弱的解集，其种群多样性降低.

在进化过程中，种群收敛性与多样性间的平衡是制约算法性能的重要因素.文献[18]从优化分解的角度,提出权重向量引导的协同进化算法，利用权重向量对优化问题进行分解，并将其作为偏好，引导权重向量与候选解协同进化.文献[19]从适应度评价的角度，引入距离算子，提高算法多样性.文献[20]从目标向量集的角度，通过动态调整目标向量集上下界值，引导种群快速收敛.

本文将种群进行分组，划分成若干个子种群，利用外部存档集中种群的收敛性与多样性信息，逐代评估子种群进化潜力，以此动态调整目标向量分布，从而提出一种基于目标向量两阶段分配策略的高维目标协同进化算法，最大化利用有限计算资源，维持种群收敛性与多样性间的平衡，提高算法性能.

2 研究背景

2.1 高维目标优化问题及相关定义

高维多目标优化问题的表示如下:

(1)

其中，X=(x1,x2,…,xd)表示d维决策变量；F(x)是决策变量到目标空间的映射，m表示目标数；gi(x)表示第i个约束函数，当k=0时，F(x)为无约束高维目标优化问题.

定义1(Pareto占优).假设a与b均为MaOPs的可行解，当且仅当fj(a)

定义2(非支配解).决策空间中不存在b，使得f(b)

定义3(非支配解集).决策空间中所有非支配解构成非支配解集.

定义4(Pareto前沿).所有非支配解映射至目标空间所构成的曲面称为Pareto前沿.

2.2 PICEA-g

文献[13]所提算法PICEA-g将目标向量作为偏好集，通过目标向量与候选解之间的支配关系计算其各自适应度值，以此选择优秀的候选解及目标向量进入下一代，引导目标向量与候选解共同进化.具体流程见算法1，其中适应度值计算公式可见文献[16].

算法1.PICEA-g

输入：种群大小N；目标向量大小Ng;最大进化代数maxgen

输出：种群P

1.P=Initial(N); //初始化产生大小为N的种群

2.G=Generate_Goal(P,Ng); //产生Ng个目标向量

3.FORt=1TOmaxgen

4.PC=Genetic(P,N);//交叉变异产生大小为N的子代种群PC

5.unionP=P∪PC;//子代与父代种群合并

6.GC=Generate_Goal(unionP,Ng);//产生Ng个目标向量

7.unionG=G∪GC;//父子代目标向量合并

8. [fit_unionP,fit_unionG]=Calculate_fitness(unionP,unionG); //计算种群与目标向量适应度值

9. [P,G]=Select(unionP,unionG,fit_unionP,fit_unionG);//选择适应度值大的N个个体及Ng个目标向量

10.ENDFOR

2.2.1 目标向量分配策略

在算法1中，函数Generate_Goal()表示目标向量的产生.首先在目标空间中寻找各目标上的最大最小值F(P)upper=(maxf1(P),maxf2(P),…,maxfm(P))及F(P)lower=(minf1(P),minf2(P),…,minfm(P))，将其作为目标向量产生的上下界值，如图1(b)所示，其中P=(X1,X2,…,XN).然后根据公式(2)产生Ng个目标向量，其中rand(0,1)表示[0,1]之间的随机数.

G=F(P)lower+rand(0,1)*(F(P)upper-F(P)lower)

(2)

图1 进化前中期DTLZ6问题的解集分布Fig.1 Solution sets obtained by 2-objective DTLZ6 problem in the earlier and middle process of evolutionary

2.2.2 缺陷分析

图1表示在进化前中期DTLZ6问题的解集分布.从图1(a)和图1(b)中可以发现，不同区域上的解收敛至前沿的时间不同，解集在不同区域上的分布也存在差异.处于前沿中心位置的解集分布较稀疏，甚至部分前沿上无解集；而处于前沿边缘位置的解集分布较密集.而原始的目标向量产生方式忽略了这一特性，等概率地为个体分配目标向量，使得中心区域上的所分配的计算资源是难以满足该区域上解集的进化，不利于提高算法的收敛性与多样性.此外，在进化不同阶段，种群选择侧重点是不同的[21].在进化前期，种群倾向于选择收敛性较好的解集，有助于带动其他解加速收敛；而在进化中后期，当解集基本收敛至前沿时，则倾向于选择多样性较好的解集，提高种群多样性.

综上所述，在进化过程中，原有目标向量产生策略无法满足种群进化的需要，不能较好地平衡分布性与收敛性间的关系，降低算法解集质量.因此，需要一种自适应的目标向量分配策略，在进化的不同阶段为不同区域上的个体分配目标向量，以此平衡种群收敛性与分布性，提高算法性能.

3 基于分组策略的高维目标协同进化算法

本文结合解集的多样性及收敛性信息，设计了基于子种群进化潜力的判断机制，在进化过程中动态调整目标向量分布，提出基于分组策略的高维目标协同进化算法，最大化利用有限计算资源，提高算法性能.

3.1 种群分组策略

对于复杂度不同的测试问题，在同等条件下，所获得的第一层非支配解数量不同.相较而言，难优化的问题会获得较少非支配解；相反，简单问题所获得的非支配较多.因此本文将归一化的非支配解数量作为评估子种群进化潜力的指标之一.此外，当解集在目标空间分布较广时，所求解集的边界点一般会分布在前沿的边界上，因此所求解集的边界点间的欧几里得距离最大.但是随着目标维度的增加，欧几里得距离的计算复杂度也随之增加，因此计算子种群内个体距离参考向量的最大角度，将归一化的最大角度作为评估的另一指标，以此衡量子种群分布情况.通常情况下，初始产生的解集往往距离前沿面较远，在一段时间的搜索后，解集基本能收敛到PF.在此时，多样性成为制约算法性能的重要因素，当解集多样性较差时，易产生相似个体，不利于产生收敛性较好的个体，导致搜索停滞甚至后退.算法在进化的不同阶段存在搜索倾向.因此，本文将进化代数作为评估子种群进化潜力的影响因子.子种群进化潜力值如公式(3)所示.

(3)

其中，t表示当前进化代数；tmax表示最大进化代数；NDi表示第i个子种群中非支配解数量；NNDmax和NNDmin分别表示NNDi(i=1,2,…,Nspace)中的最大最小值；βi表示第i个子种群中个体距离参考向量的最大角度；βmax和βmin分别表示βi(i=1,2,…,d)中的最大最小值；Nspace表示子种群数.当进化代数t无限趋近于0,PEi主要取决于子种群的收敛性；当进化代数t无限趋近于tmax,PEi主要取决于子种群的分布性.当子种群中非支配解数量NNDi越小时，PEi值越小，则该子种群进化潜力越大；当子种群中βi越小时，PEi值越小，则该子种群进化潜力越大.

以图2为例,假设存在3个参考向量V1、V2、V3和6个个体P1～P6.θ21、θ22、θ23分别表示个体P2与参考向量的夹角，其中θ21角度最小，因此将个体P2划分到子种群SP1，并以此类推，将种群进行划分，个体P1和P2属于子种群SP1，个体P3、P4和P5属于子种群SP2，个体P6属于子种群SP3.对于子种群SP1，其非支配解数量为2，个体P2与向量的角度大于个体P1，则该子种群的最大角度β1=θ21.子种群进化潜力判断机制如算法2所示.

算法2.种群分组策略

输入：种群P={P1,P2,…,PN}、子种群数Nspace

输出：子种群SP={SP1,SP2,…,SPNspace}、子种群进化潜力值PE={PE1,PE2,…,PENspace}

//将种群分组，划分为若干个子种群SP//

1.初始化产生参考向量V={V1,V2,…,VNspace};

2.θ=;//计算个体与参考向量的角度,θij(i=1,2,…,N;j=1,2,…,Nspace)表示个体Pi到参考向量Vj的角度值

3.FORi=1TON

5.SPk=SPk∪{Pi};//将个体Pi划分到子种群SPk

6.SP_θk=SP_θk∪{θik};//保留个体Pi与参考向量Vk的角度值

7.ENDFOR

//计算子种群进化潜力值PE//

8.FORj=1TONspace

9. [NDj,NNDj]=Find_best(SPj);//找到子种群中的非支配解集NDj，并计算其个数NNDj

10.βj=max(SP_θj);//在子种群SPj内找到距离参考向量Vj最远的个体，将该个体与参考向量Vj的角度值记为βj

11.ENDFOR

12.FORj=1TONspace

13.PEj= Potential_evolution(NND,β,t);//根据公式(3)计算子种群进化潜力；

14.ENDFOR

图2 种群划分和潜力值计算示意图Fig.2 Division of the population and calculation of evolutionary potential

3.2 目标向量分配策略

子代目标向量的产生主要分为两个步骤：首先，根据子种群进化潜力值选择合适子种群，并为子种群分配一定数量的目标向量，加大此子种群的选择压力，实现资源的最大化利用；其次，计算已产生的目标向量数|GC|，在整个目标空间内产生剩余数量的目标向量Ng-|GC|，为剩余子种群一定的选择压力，防止未被选择的剩余子种群产生退化现象,具体如算法3所示.

算法3.目标向量分配策略

输入：子种群SP={SP1,SP2,…,SPNspace}及其进化潜力PE={PE1,PE2,…,PENspace},混合种群unionP,目标向量产生个数Ng,子种群数Nspace

输出：子代目标向量集GC

2.FORj=1 TONspace

3.IFPEj

5.ENDIF

6.GC=GC∪GC′;

7.ENDFOR

8.ranGC=Generate_Goal(jointP,Ng-|GC|);

9.GC=GC∪ranGC;

3.3 算法流程

本文在高维目标协同进化算法基础上，引入一种种群分组策略和目标向量分配策略，具体过程如算法4所示.

算法4.PICEA-g

输入：种群大小N;目标向量大小Ng;最大进化代数maxgen

输出：种群P

1.P=Initial(N)

2.G=Generate_Goal(P,Ng);

3.FORt=1TOmaxgen

4.PC=Genetic(P,N);

5.unionP=P∪PC;

6. [SP,PE]=Judge_potention(P,Nspace]);//种群分组策略

7.GC=Twostage_Goal(unionP,SP,PE,Ng,Nspace);//目标向量分配策略

8.unionG=G∪GC;

9. [fit_unionP,fit_unionG]=Calculate_fitness (unionP,unionG);

10. [P,G]=Select(unionP,unionG,fit_unionP,fit_unionG);

11.ENDFOR

4 仿真结果与分析

为验证基于两阶段资源分配策略的高维目标协同进化算法的有效性，选择DTLZ1-7系列函数[22]作为测试问题集，将本文所提算法与同类型PICEAg在3、5、7、10及15维DTLZ函数上进行仿真对比实验.为保证实验的公平和合理性，两种算法均在PlatEMO平台[23]上独立运行30次，种群规模为100，目标向量数为100，最大进化代数为300，利用运行30后指标方差评估算法稳定性，并采用the Wilcoxon test方法对仿真结果进行显著性分析，其中，“+”、“=”、“-”分别表示在显著水平为5%下优于、近似于、劣于改进后算法.

表1 改进前后算法在DTLZ1-7测试问题上的GD与SP指标值Table 1 GD and SP value of algorithms on DTLZ1-7 problems

4.1 性能评价指标

本文采用世代距离(Generation Distance，GD)[24]及空间分布(Spacing，SP)指标[25]对算法所得解集进行收敛性及多样性评估.

世代距离：所得解集到真实前沿地距离，如公式(4)所示.其中，n表示解集个数，di表示前沿中离第i个个体最近的向量与第i个个体的欧几里得距离.GD值越小，表明解集离前沿越近，收敛性越佳.

(4)

空间分布：算法所求解集的多样性，如公式(5)所示.其中，n表示解集个数，di表示前沿中离第i个个体最近的向量与第i个个体的欧几里得距离.SP值越小，表明算法所得解集在目标空间中均匀分布.

(5)

4.2 算法改进前后对比分析

表1表示各算法在DTLZ系列测试问题上的GD与SP指标对比结果，其中字体加粗表示最优结果，‘M’表示目标数，‘D’表示变量数.DTLZ1和DTLZ3均是具有多模态特性的难优化测试问题，即存在多个局部最优解，其产生的初始种群远离前沿，较难收敛至PF.对于DTLZ1测试问题，除10维目标外，改进后算法在收敛性及多样性上均优于对比算法；对于DTLZ3测试问题，除15维目标外，改进后算法在收敛性及多样性上均优于对比算法，在10维DTLZ3测试上其收敛性优于对比算法.从结果中可以发现，改进后算法在多模态测试问题上取得较好结果，通过动态调整目标向量分布，有目的的增加子种群的选择压力，使其快速收敛.

图3 改进前后算法在3、5、7、10、15维DTLZ1问题上的GD指标BOX图Fig.3 GD box diagram of algorithms before and after improvement on the 3、5、7、10 and 15-objective DTLZ1 problems

图4 改进前后算法在3、5、7、10、15维DTLZ4问题上的GD指标BOX图Fig.4 GD box diagram of algorithms before and after improvement on the 3、5、7、10 and 15-objective DTLZ4 problems

图5 改进前后算法在3、5、7、10、15维DTLZ7问题上的GD指标BOX图Fig.5 GD box diagram of algorithms before and after improvement on the 3、5、7、10 and 15-objective DTLZ7 problems

DTLZ4、DTLZ6及DTLZ7均属于有偏函数，使得分布均匀的决策变量映射到目标空间后不再均匀，该特性增加了维持种群多样性难度.另外DTLZ7还是一个混合的不连续优化问题.从结果中发现，在DTLZ4测试问题上，改进后算法所求解集的收敛性显著优于原算法PICEAg,其多样性略优于对比算法；对于DTLZ6及DTLZ7测试问题，除5维目标空间外，改进后算法在收敛性及多样性上显著优于对比算法.尤其在高维目标优化中，相较于PICEAg算法，改进后算法的算法性能并未显著减弱.这是由于，在进化前期改进后算法根据子种群的收敛性分配目标向量，而在进化后期主要根据其多样性分配，从而为多样性较差的子种群提供分配较多计算资源，以此找到多样性较好的解集，提高种群多样性.

图6 改进前后算法在3维DTLZ1-7问题上的前沿对比图Fig.6 Solution sets obtained by PICEAg and PICEAg-PE on 3-objective DTLZ1-7 problem

图3-图5分别表示改进前后算法在DTLZ1、DTLZ4及DTLZ7测试问题上的GD指标box图.从图3中可以发现，3、5及7维DTLZ1测试问题上，改进后算法的GD平均线及box图的长度均低于原算法.表明改进后算法在3、5及7维DTLZ1测试问题上的算法鲁棒性优于对比算法.在图4 中，对于大多数维度的DTLZ4测试问题，改进后算法的GD平均值优于对比算法，但是其鲁棒性并未明显提高.由此可见改进算法不适用于求解DTLZ2这类测试问题.在图5中，除5维DTLZ7外，改进后算法在其余维度的测试问题上的GD平均值均优于原算法，BOX图中的上下界值离平均值线较近，产生的异常值个数也远远少于原算法.由此可见，对于DTLZ7这类测试问题，改进后算法的收敛性与鲁棒性明显提高.

图6表示改进前后算法在3维DTLZ1-7测试问题上的前沿对比图.由图中可以发现，在DTLZ1、DTLZ6及DTLZ7测试问题上，PICEAg算法所求解集仅收敛至前沿面的部分区域，解集多样性极差；在DTLZ3测试问题上，PICEAg算法所得解集远离前沿且多样性较差；在DTLZ5测试问题上，PICEAg算法所得解集基本收敛至前沿，但部分前沿上解集多样性较差.相比于对比算法，在以上测试问题中,PICEAg-PE所得解集具有较好的收敛性与多样性.PICEAg-PE算法根据非支配解集隐含信息，确定子种群进化潜力，调整目标向量分布，平衡种群的收敛与多样性，提高算法性能.

5 结束语

为平衡进化过程中种群收敛性与多样性的冲突，本文设计一种基于分组策略的高维协同进化算法，调整目标向量分布，平衡种群收敛与多样性.根据仿真实验，结果表明改进后算法所求解集在收敛性及多样性上有显著提高.下一步将对参考向量的分布进行调整，以此适应不同优化问题，增强对前沿形状的敏感性，使目标空间的划分更加合理.