工程实践和科学研究中,经常需要同时对多个目标进行优化,目标函数个数超过4个并且需要同时处理的多目标优化问题,称为高维多目标优化问题(many-objective optimization problem,简称MOP)^{[1, 2, 3, 4, 5]}.由于高维多目标优化中,多个目标之间往往是相互冲突的,一个子目标性能的改善可能会引起另一个或多个子目标性能的降低,只能通过折中的方法使所有目标尽可能达到最优^{[1, 2, 3]}.此外,高维的特性使得计算复杂度和搜索空间急剧扩增.以上特性,使高维多目标优化成为目前国内外智能优化领域最难解决的优化问题之一^[4,5].

近10年来,由于进化算法(evolutionary algorithms,简称EAs)能够有效解决高维复杂非线性优化问题而被广泛用于多目标优化领域,并形成热门研究方向,即,进化多目标优化(evolutionary multi-objective optimization,简称EMO).迄今为止,国内外研究者已相继提出大量多目标进化算法(multi-objective evolutionary algorithms,简称MOEAs),其中最具代表性且应用范围最广的MOEAs包括第二代多目标进化算法中的NSGA-II,SPEA2,OMOPSO,NNIA,DEMO等^{[1, 2, 3, 4, 5, 6]}.然而大量实践研究表明:现有的MOEAs在2~3目标多目标优化问题的求解上能够取得良好的收敛性和解集分布性;但在求解MOPs时,这些基于Pareto支配(Pareto dominance,简称PD)的MOEAs性能将急剧恶化^{[4, 5, 6]},无法满足MOPs求解的收敛性和分布性需求.

由于MOPs求解难度极大,当前国内外高维多目标进化算法MOEAs的研究首先致力于收敛性能的提高,其次考虑改善解集分布性^[6].总结国内外现有针对高维多目标优化提升MOEAs收敛性的改进方法,主要可分为以下3类^[7].

(1) 仍采用基于Pareto支配的排序方法,结合缩小空间技术或利用偏好信息降低目标维数^{[8, 9, 10]}.该类方法只适用于能够预知偏好信息或目标主次的问题;

(2) 设计宽松的Pareto支配方法,如e占优^[11]、E支配^[12]、模糊支配^[13]、L支配^[4]等.该类方法虽然在一定程度上增大了非支配个体的选择压力,但降低了排序结果的合理性与可信性,并且随着目标个数的持续增加,仍面临着选择压力退化的问题,不能从根本上解决问题;

(3) 采用非Pareto支配排序方法^[14],设计新的评价准则或适应度函数对种群个体进行比较与排序.该类方法能够获得较好的解集收敛性,典型代表包括平均等级排序(average ranking,简称AR)^[15]、关系偏好排序(relation favour,简称RF)^[16]等.

通过对现有高维多目标优化技术的深入研究,本文提出一种基于全局排序的高维多目标差分进化算法GR-MODE(global ranking based many-objective differential evolution),其创新点主要包括:

(1) 采用新的非Pareto支配排序方法,即全局排序策略,以提高种群个体区分能力,增强选择压力,引导种群收敛.个体排序值计算考虑与种群中所有个体在所有目标上的性能差异;

(2) 采用基于Harmonic平均拥挤距离的全局密度估计方法,精确估计个体拥挤程度,维护解集分布性;

(3) 设计新的精英选择策略和适应度值评价函数,综合衡量个体的收敛性及分布性,提升算法整体性能.

将GR-MODE与现有5种国内外高效的MOEAs在标准测试函数集DTLZ{1,2,4,5}上进行对比实验,结果表明:GR-MODE在4~30维多目标优化问题上的求解性能具有明显优势,尤其适合于高维复杂多目标优化问题的求解.

不失一般性,一个具有n维决策变量、m维目标函数的多目标优化问题,以最小化为例,可表述为公式(1)的形式:

其中,x称为决策变量,X是n维的决策空间;y称为目标函数,Y是m维的目标空间;目标函数y=F(x)定义了映射函数和同时需要优化的m个目标,若m>=4,则公式(1)称为高维多目标优化问题.对于决策空间内的任意两点x,xÎX,当x^*的目标函数值都不大于并且至少存在一个小于x的目标函数值时,称x^*Pareto支配x,记为x^*f_px;若x^*不受种群中其他个体支配,则称x^*为Pareto非支配解.种群中所有非支配解构成的集合称为Pareto最优解集,对应的目标函数构成的解集称为Pareto前沿.

国内外高维多目标优化技术的研究内容主要包括两大组成部分:(1) MOEAs模型研究;(2) 基于群智能优化算法的多目标进化策略研究.前期实验研究结果表明,单纯提升进化策略的性能对于改善MOEAs的整体性能效果并不显著.因此,高维多目标优化求解性能的提升需要从MOEAs模型以及进化策略两方面进行改进.

现有的高维多目标进化算法大多仍采用以精英保留机制为特征的第二代MOEAs模型,其基本框架如图 1所示.为提高高维环境下MOEAs的求解性能,现有研究主要针对模型中的精英选择(涵盖支配排序方法及密度估计)部分进行性能改进.

图 1

Fig. 1

Fig. 1 Workflow of the MOEAs图 1 MOEAs模型基本框架

现有高维多目标进化算法中,用作进化策略的群智能优化算法主要包括遗传算法(genetic algorithm,简称GA)、粒子群优化(particle swarm optimization,简称PSO)、人工免疫系统(artificial immune system,简称AIS)等. Coello CAC等学者的实验研究表明:目前性能最好的进化策略为差分进化算法(differential evolution,简称DE)^[17],其强大的全局搜索能力有利于提高高维复杂空间中MOEAs的计算性能.

为提高现有MOEAs在高维多目标优化问题上的求解性能,本文提出一种基于全局排序的高维多目标差分进化算法GR-MODE.针对高维多目标特性对MOEAs模型中的个体适应度赋值方法及精英选择策略进行全面改进,进化策略采用DE,提高高维复杂空间中的计算能力,力争获得MOEAs整体求解性能的提升.

现有MOEAs在高维多目标优化问题上表现不佳的关键原因在于其采用的支配排序方法在高维环境下性能受限,支配排序方法的功能在于综合衡量个体在多个目标上的目标值,从而决定个体之间的优劣关系以进行精英选择.现有MOEAs绝大多数基于Pareto支配,然而Pareto支配在高维多目标情况下存在着严重的缺陷,即:当目标维数增多时,Pareto支配关系衡量个体优劣的功能逐渐弱化,使得种群中非支配解个体的数量呈指数级上升,通常数次迭代后种群中几乎所有个体均为非支配个体,MOEAs无法从种群中选择出相对优秀的个体进入下一代.这大大削弱了种群逼近Pareto前沿的选择压力,MOEAs的收敛性能受到严重破坏,极易导致陷入局部最优或求解失败.

国内外学者针对这一问题进行了大量研究工作,现有的主要改进方法可以分为两种:(1) 应用缩小空间技术或利用用户偏好信息降低目标维数,简化高维多目标优化问题,降低求解难度^{[8, 9, 10]},然而该方法仅适用于能够预知冗余目标和用户偏好信息的情况,不具有普适性;(2) 采用较为宽松的Pareto支配方法,通过放宽Pareto支配关系增大个体之间收敛性能差异的可比较性,增大种群精英选择压力,避免非支配个体比例过高,利用收敛性较优的个体引导种群进化,增强算法收敛性能^{[11, 12, 13]},然而该方法降低了排序结果的合理性与可信性,并且随着目标个数的持续增加,仍面临选择压力退化的问题,不能从根本上解决问题.

目前,最前沿的解决方法是采用非Pareto支配的排序方法,通过设计新的评价准则对种群个体进行比较与排序,从而彻底消除Pareto支配所带来的问题^[15,16,18].基于这种思想,本文所提算法GR-MODE采用一种新的非Pareto支配排序方法^[5],即全局排序(global ranking,简称GR),应用新的评价准则对种群个体进行比较与排序.在新的全局排序机制中,个体两两在目标空间中进行比较,定义种群POP中每个个体X_i的全局排序值GR(X_i)等于该个体在所有目标上与种群中所有其他个体相应目标值的差值之和,计算公式如公式(2)所示.

其中,个体X_j为种群POP中不同于X_i的任意个体;mÎ[1,M]为目标维数;f_m为个体在第m个目标上的归一化函数值,计算公式如公式(3)所示.

其中,g_m,max和g_m,min分别为当前种群POP中所有个体在第m维目标函数上的最大值和最小值.根据GR排序机制,对于个体X_i和X_j,若X_i在第m个目标上优于X_j,即f_m(X_i)<f_m(X_j),则二者差值取值为0;否则,差值等于f_m(X_i)-f_m(X_j).只有当X_i与种群中所有其他个体相比,在所有目标上的差值之和GR(X_i)小于X_j与种群中所有其他个体相比,在所有目标上的差值之和GR(X_j)时,才能够称X_i的收敛性优于X_j.全局排序能够综合衡量个体在种群中与其他所有个体之间在各维目标上的差异程度,只有当某个体在各维目标上的适应度值与其他个体相比整体较优时,才被视为优秀个体.该方法能够精确定位种群中每个个体的优劣程度,每个个体具有全局唯一的排序值,大幅提升了种群个体等级多样性,有效增强了精英选择的压力.

命题1. 种群个体的全局排序值GR具有唯一性.

证明:假设种群POP规模为N,N个个体的全局排序值分别为

$\begin{array}{l} GR({X_1}) = \sum\limits_{m = 1}^M {\max ({f_m}({X_1}) - {f_m}({X_2}),0)} + \sum\limits_{m = 1}^M {\max ({f_m}({X_1}) - {f_m}({X_3}),0)} + ... \\+ \sum\limits_{m = 1}^M {\max ({f_m}({X_1}) - {f_m}({X_N}),0)} ,\\ GR({X_2}) = \sum\limits_{m = 1}^M {\max ({f_m}({X_2}) - {f_m}({X_1}),0)} + \sum\limits_{m = 1}^M {\max ({f_m}({X_2}) - {f_m}({X_3}),0)} + ... \\+ \sum\limits_{m = 1}^M {\max ({f_m}({X_2}) - {f_m}({X_N}),0)} ,\\ ...\\ GR({X_i}) = \sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_1}),0)} + ... + \sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_{i - 1}}),0)} + \\ {\rm{ }}\sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_{i + 1}}),0)} + ... + \sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_N}),0)} ,\\ ...\\ GR({X_N}) = \sum\limits_{m = 1}^M {\max ({f_m}({X_N}) - {f_m}({X_1}),0)} + \sum\limits_{m = 1}^M {\max ({f_m}({X_N}) - {f_m}({X_2}),0)} + ... \\+ \sum\limits_{m = 1}^M {\max ({f_m}({X_N}) - {f_m}({X_{N - 1}}),0)} . \end{array}$

对于种群中任意一个个体X_i(1≤i≤N),其在第m维目标上的归一化目标函数值f_m(X_i)Î[0,1],因此,

f_m(X_i)-f_m(X₁)Î^{[-1, 1]},f_m(X_i)-f_m(X₂)Î^{[-1, 1]},…,f_m(X_i)-f_m(X_N)Î^{[-1, 1]},

由此得出:

max(f_m(X_i)-f_m(X₁),0)Î[0,1],max(f_m(X_i)-f_m(X₂),0)Î[0,1],…,max(f_m(X_i)-f_m(X_N),0)Î[0,1],

由此得出:

$\begin{array}{l} \sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_1}),0)} \in [0,M],\sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_2}),0)} \in \\ [0,M],...,\sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_N}),0)} \in [0,M], \end{array}$

由此得出:

$GR({X_i}) = \sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_1}),0)} + ... + \sum\limits_{m = 1}^M {\max ({f_m}({X_i}) - {f_m}({X_N}),0)} \in [0,M \times N].$

即,个体X_i的全局排序值GR(X_i)为取值范围[0,MxN]内的任意实数.假设在种群POP中存在不同于个体X_i的任意一个个体X_j(1≤j≤N),个体X_j的全局排序值GR(X_j)等于个体X_i的全局排序值GR(X_i)的概率等同于在取值范围[0,MxN]内取一个特定的正实数使其数值等于GR(X_i).由于本文计算过程中目标函数值f的数值精度为10^-4,因此上述概率等于(10⁴MN)^-1.由于M≥3且N的取值为100,因此概率(10⁴MN)^-1的取值小于10^-6,即,种群POP中存在任意两个体全局排序值GR相等的概率小于10^-6,在实际计算过程中可基本忽略不计,因此可得出结论:种群中个体的全局排序值GR具有全局唯一性.证明完毕.  □

基于非Pareto支配的全局排序方法能够生成多样性良好的排序等级,实验研究的结果表明:MOEAs中排序等级多样性越好,越有利于个体精英的选择,从而增大了选择压力.为验证全局排序方法GR对排序等级多样性的影响,测量基于GR的典型多目标进化算法NSGA-II在通用测试函数DTLZ{1,2,4,5}上的排序等级多样性,并与目前国内外性能最优的4种支配及排序方法进行对比,包括Pareto支配(简称PD)、平均排序(简称AR)、关系偏好(简称RF)及L支配(简称LD).等级多样性衡量指标采用文献^[19]中提出的排序等级平均相对熵re.对于规模为N的种群POP,定义RÎ[1,N]为种群中排序等级总数,即,种群中个体最少属于1个等级而最多属于N个等级.函数D(r)定义了第r等级中个体数目,rÎ[1,R],排序等级平均相对熵re的计算公式如公式(4)所示.

从公式(4)可知:熵值re越大,表明种群中个体等级分布多样性越大,越能够保证充足的选择压力;反之,熵值re越小,表明种群中个体等级分布多样性就越不充足,选择压力有待于加强.实验中,DTLZ{1,2,4,5}函数目标维数取值为{4,10,30},相应的决策变量维数取值为{10,20,50}.实验统计结果如表 1和图 2所示,各项数据为独立运行30次的平均值.

表 1(Table 1)

Table 1 Average relative entropy of ranks distribution 表 1 等级分布平均相对熵对比结果 目标维数 支配排序方法 DTLZ1 DTLZ2 DTLZ4 DTLZ5 平均值 M=4 PD 0.234 5 0.251 3 0.342 4 0.232 3 0.265 1 AR 0.915 7 0.910 8 0.933 8 0.949 6 0.927 5 RF 0.017 0 0.084 0 0.057 0 0.287 1 0.111 3 LD 0.633 4 0.633 0 0.709 1 0.538 7 0.628 6 GR 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 M=10 PD 0.180 2 0.147 4 0.021 3 0.156 1 0.126 3 AR 0.972 9 0.978 9 0.953 7 0.982 7 0.972 1 RF 0.104 0 0.047 0 0.100 0 0.174 9 0.106 5 LD 0.555 9 0.588 2 0.735 5 0.570 1 0.612 4 GR 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 M=30 PD 0.065 7 0.155 7 0.003 3 0.076 0 0.075 2 AR 0.997 0 0.984 9 0.969 9 0.988 0 0.985 0 RF 0.117 0 0.020 0 0.014 7 0.201 0 0.088 2 LD 0.548 1 0.591 2 0.727 6 0.629 5 0.624 1 GR 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0

Table 1 Average relative entropy of ranks distribution 表 1 等级分布平均相对熵对比结果

图 2

Fig. 2

Fig. 2 Average relative entropy of ranks distribution图 2 排序等级分布平均相对熵

根据表 1中的数据绘制出各支配排序机制平均相对熵的分布图,如图 2所示.

图 2显示了5种支配排序方法对应排序等级分布的相对熵re,其中,PD的平均相对熵re在目标维数增多时逐渐下降,说明种群中个体排序等级逐渐减少,非支配个体逐渐增多,选择压力减小;AR的平均相对熵re随目标维数的增加而增大,说明其选择压力逐渐提升;RF的平均相对熵re最小,排序性能始终不佳;LD的相对熵较为稳定,始终保持在相对较高水平.5种方法中,只有GR的平均相对熵re始终为1,说明其能够有效维持种群个体等级多样性及选择压力,可促进种群收敛.

高维多目标优化问题的求解目标之一,即为维护进化群体的多样性,使求得的近似Pareto最优解集在目标空间中具有较好的分布特性(如均匀分布),且分布范围尽可能广.实现该目标需要体现出种群个体在目标空间的分布情况,个体之间的结构和联系主要表现为个体在目标空间中的疏密远近,但截止到目前,尚未有公认的有效分布度评价方法^[20].早期的分布度评价方法多采用小生境法,即区域法,新近发展的MOEAs中通常引入密度评估策略为个体估计邻域密度值,以反映个体周围的拥挤程度,密度值越大,则个体分布性越差.通过在进化群体(或设置的外部种群)中保留邻域密度较小的个体,保证搜索到的最优解集的分布特性.

现有的密度评估策略主要包括NSGA-II采用的拥挤距离法、PAES采用的网格法以及SPEA采用的聚类法等,这些方法都需要使用距离测度,MOEAs将两个个体间的距离定义为相应目标向量间的欧式距离.相比较于网格法和聚类法,拥挤距离法无需用户参数设置,计算复杂度低,时耗较小,因此适用性更强.然而,现有的拥挤距离法的本质均为基于欧式距离的局部密度估计法,仅估计个体自身邻域范围内2或k(k<N)个个体之间的拥挤程度,不能精确反映目标空间中个体之间的结构和联系^[21].

因此,本文采用Harmonic平均距离^[21]对种群个体进行全局密度估计,在个体两两之间欧氏距离计算的基础上进行二次距离计算,利用种群中所有个体之间的距离信息精确衡量每个个体在全局范围内的拥挤程度,从而有效避免少数“极值解”或“偏远解”对个体拥挤程度的影响.对于种群中的个体X_i,假设目标空间中与其距离最近的k个个体的欧式距离分别为d_i,1,d_i,2,d_i,3,…,d_i,k,则个体X_i的Harmonic平均距离Hd(X_i)如公式(5)所示.

为保证在全局范围内对个体拥挤程度进行精确估计,公式(5)中,k取值为N-1.即,个体X_i的密度估计考虑种群中除自身外所有个体的影响,由此在一定程度上提高拥挤距离的精确性,提升目标空间中个体间疏密远近程度的测量精度,以促进种群多样性的提升.

现有大多数MOEAs在精英选择时首先保留收敛性指标较好的个体,分布性指标居于次要位置.在这一思想的引导下,国内外现有大多数MOEAs的适应值评价方法仅仅计算个体在各维目标上的函数值,再通过各类支配排序方法比较其优劣,并没有将个体分布性指标(如拥挤距离)计算在内.高维多目标优化问题中,决策及目标空间搜索范围极大扩张,改进后的支配排序方法虽然能在一定程度上增强选择压力,提升收敛性能,但若未对分布性给予足够重视,将极易导致种群陷入局部最优甚至收敛停滞.针对这一问题,GR-MODE设计了新的精英选择策略及相应的个体适应值评价方法,综合考虑收敛性指标和分布性指标,以决定精英个体的选择.对于种群中个体X_i,假设其在所有目标函数上与种群中其他个体相应目标值的差值之和为GR(X_i),且其在种群中的Harmonic平均距离为Hd(X_i),则其全局适应度值fitness(X_i)如公式(6)所示.

fitness(X_i)=w₁xGR(X_i)-w₂xHD(X_i) (6)

其中,w₁和w₂为在[0,1]之间取值的权重系数,用于协调收敛性及分布性的权重,文中取值分别为1.5和0.5.

基于上述全局排序策略、全局密度估计以及精英选择这3个方面的改进措施,提出基于全局排序的高维多目标差分进化算法GR-MODE.GR-MODE的复杂度主要来自全局排序和全局密度估计,设种群规模为N,目标数为M,算法GR-MODE的计算复杂度为O(MN²),与NSGA-II相当.GR-MODE算法的具体操作步骤如下:

Step 1. 随机生成算法初始种群,确定算法相应参数:种群规模N,最大迭代次数Gen.将初始种群作为最初父代种群,计算个体适应度值;

Step 2. 判断是否满足终止条件:若不满足,则转到Step 3;否则,输出当前种群作为最终的最优解集;

Step 3. 对当前种群进行进化操作,包括变异、交叉和选择,生成规模为N的子代种群;

Step 4. 合并父代种群和生成的子代种群,规模为2N;

Step 5. 根据第2.1节、第2.2节所述,分别对合并后种群进行全局排序、全局密度估计操作;

Step 6. 在全局排序及全局密度估计结果的基础上,根据第2.3节所述,对合并后种群进行精英选择操作,剪切种群至规模N.转至Step 2.

为了验证本文算法GR-MODE在高维多目标优化问题上的求解性能,将其与DEMO^[21],MOSAHS^[22],OMOPSO^[23],SDEMO^[24]和SPEA2^[25]这5种目前具有代表性的MOEAs在4,10,30目标的DTLZ测试函数集上进行对比实验.选用可扩展为任意目标维数和自变量维数的通用测试函数DTLZ{1,2,4,5}^{[21, 22, 23, 24, 25]}.所有实验在硬件配置为Intel Pentium,CPU:G620,4G内存,2.6GHz主频,win7 64位操作系统的计算机上进行.

将GR-MODE与其他5种MOEAs分别在目标个数为4,10,30的DTLZ函数集上进行测试.

· 4目标时DTLZ函数集参数设置为:目标个数为4,变量X的维数为10,算法的迭代次数为1 000;

· 10目标时DTLZ函数集参数设置为:目标个数为10,变量X的维数为20,算法的迭代次数为3 000;

· 30目标时DTLZ函数集参数设置为:目标个数为30,变量X的维数为50,算法的迭代次数为5 000.

种群规模N设置为100,采用10 000个均匀分布的Pareto最优解作为真实Pareto前沿的近似解集.

为了评价各种算法的性能,选取目前国内外通用的世代距离GD和间距度量指标S作为收敛性和分布性评价标准^{[21, 22, 23, 24, 25]},其中,世代距离GD用于测量算法最终所得最优解集与真实Pareto前沿的逼近程度,评价算法的收敛性;间距度量指标S用来评价解集在目标空间上的分布性.为保证实验公平性和科学性,对比算法的控制参数设置均采用相应原文献中的推荐值,且所有实验结果均为各种算法独立运行30次对应GD和S的统计平均值,统计结果见表 2~表 5,各项对比实验中的最优结果均用黑体加粗表示.

表 2(Table 2)

Table 2 Experimental results on DTLZ1 problem 表 2 测试函数DTLZ1的实验统计结果 算法 4目标 10目标 30目标 GD S GD S GD S DEMO 28.000 4 2.042 3 45.219 2 4.383 5 74.789 3 9.082 3 MOSAHS 11.585 6 1.725 1 39.392 6 3.005 8 87.441 4 3.015 3 OMOPSO 6.617 3 1.074 4 39.986 0 3.996 0 63.209 1 6.899 1 SDEMO 29.387 8 2.158 6 58.932 2 5.318 0 109.156 4 9.241 6 SPEA2 5.883 8 0.287 8 48.252 9 6.682 8 128.584 7 28.325 2 GR-MODE 1.704e-4 9.686e-4 0.539 2 0.924 3 16.435 2 1.933 7

Table 2 Experimental results on DTLZ1 problem 表 2 测试函数DTLZ1的实验统计结果

表 3(Table 3)

Table 3 Experimental results on DTLZ2 problem 表 3 测试函数DTLZ2的实验统计结果 算法 4目标 10目标 30目标 GD S GD S GD S DEMO 0.062 3 0.011 7 0.129 0 0.030 5 0.166 7 0.045 6 MOSAHS 0.030 3 0.008 3 0.059 1 0.011 5 0.141 7 0.002 0 OMOPSO 0.012 6 0.007 5 0.069 9 0.021 1 0.108 0 0.032 8 SDEMO 0.054 6 0.010 6 0.142 7 0.031 1 0.238 3 0.044 1 SPEA2 0.041 0 0.013 5 0.213 3 0.044 4 0.435 7 0.129 1 GR-MODE 4.762e-6 2.003e-4 3.557e-5 2.369e-3 3.908e-5 1.346e-2

Table 3 Experimental results on DTLZ2 problem 表 3 测试函数DTLZ2的实验统计结果

表 4(Table 4)

Table 4 Experimental results on DTLZ4 problem 表 4 测试函数DTLZ4的实验统计结果 算法 4目标 10目标 30目标 GD S GD S GD S DEMO 0.060 4 0.013 1 0.114 0 0.033 8 0.185 7 0.085 0 MOSAHS 0.032 5 0.009 6 0.076 5 0.003 0 0.155 3 0.004 4 OMOPSO 0.005 8 0.003 5 0.080 5 0.021 4 0.140 7 0.064 5 SDEMO 0.029 2 0.011 9 0.115 9 0.032 9 0.226 5 0.062 3 SPEA2 0.034 5 0.034 5 0.202 6 0.059 2 0.418 9 0.143 9 GR-MODE 1.157e-6 2.083e-4 2.386e-5 3.347e-3 1.681e-4 1.926e-4

Table 4 Experimental results on DTLZ4 problem 表 4 测试函数DTLZ4的实验统计结果

表 5(Table 5)

Table 5 Experimental results on DTLZ5 problem 表 5 测试函数DTLZ5的实验统计结果 算法 4目标 10目标 30目标 GD S GD S GD S DEMO 0.019 8 0.005 3 0.011 6 0.005 0 0.008 1 0.004 0 MOSAHS 0.010 0 0.003 1 0.007 7 0.005 9 0.004 9 0.003 5 OMOPSO 0.021 3 0.004 4 0.013 9 0.003 7 0.007 9 0.004 0 SDEMO 0.024 9 0.004 9 0.015 7 0.004 9 0.007 5 0.003 9 SPEA2 0.040 2 0.007 0 0.025 1 0.004 7 0.018 9 0.003 7 GR-MODE 4.509e-05 9.168e-04 3.507e-05 2.986e-04 2.334e-04 1.652e-04

Table 5 Experimental results on DTLZ5 problem 表 5 测试函数DTLZ5的实验统计结果

表 2~表 5分别统计了函数DTLZ{1,2,4,5}求解过程中GR-MODE与5种先进MOEAs收敛性指标GD和分布性指标S的统计平均值的对比实验结果.分析表中的统计数据可以看出:GR-MODE在高维多目标函数求解中与目前性能较优的5种多目标进化算法相比,具有明显优势,具体表现为以下3点.

(1) GR-MODE在4~30维DTLZ{1,2,4,5}上的平均世代距离GD值均远远小于其他5种算法,说明GR-MODE的收敛性能大幅度提升,所获得的最优解集更逼近理论Pareto前沿.原因在于GR-MODE算法中的全局排序方法GR是从解个体之间“优于目标数目”及“优于目标幅度”两个角度来度量个体之间的接近程度的.由于任意个体在种群中相比较于其他所有个体时,“优于目标数目”的总和可能与其他个体相同,但“优于目标幅度”的总和在10^-4精度下与其他个体相同的概率极低,因此,种群中每个个体拥有不同的GR值,这实质上大幅细化了Pareto支配比较关系的粒度,提高了关系的区分能力,因而可以大幅度提高种群选择压力,促使种群向Pareto最优前沿逼近.

GR-MODE在4~30维DTLZ1,DTLZ2和DTLZ4上的分布性指标S值均相对较小,说明GR-MODE获得的最优解集中个体分布更加均匀,Harmonic平均拥挤距离能够在一定程度上提高个体密度估计精度,促进解集分布性维护;

(2) GR-MODE能够成功求解函数DTLZ{1,2,4,5}并获得最佳的性能指标值.根据DTLZ{1,2,4,5}函数各自功能特性可以看出:GR-MODE在高维多目标优化过程中能够获得良好的收敛性能和分布性能,且目标维数增多时仍具有较强的运算能力;

(3) GR-MODE在函数DTLZ{1,2,4,5}的求解过程中,当目标维数目由4增至30,即目标维数逐渐增大时,由于求解复杂度的大幅提升,GR-MODE与其他算法一样呈现出性能恶化的趋势,但GR-MODE的收敛性和分布性指标仍能稳定保持在相对较高的水平.说明GR-MODE具有相对较强的稳定性,适合于高维多目标优化问题的求解.

为了提高现有多目标进化算法MOEAs在高维多目标优化问题上的求解性能,提出一种基于全局排序的高维多目标差分进化算法GR-MODE.GR-MODE采用了新的全局排序策略,有效增强了算法选择压力,无需用户偏好和目标主次信息;采用了基于Harmonic平均拥挤距离的全局密度估计方法,提高了解集分布性;设计了新的精英选择策略和新的适应度值评价函数,有效平衡了个体的收敛性及分布性.

4,10,30目标测试函数集DTLZ{1,2,4,5}的实验结果显示:GR-MODE与现有多种高效MOEAs相比,在收敛性和分布性上都有较大幅度的提升,适合于高维复杂多目标优化问题的求解.