第3章 在基于聚合的多目标演化算法中 平衡收敛性和多样性 3.前言 1 .................... 本章旨在提高基于聚合的MOEAs在高维多目标优化中多样性保持方面的能力,从 而更好地平衡收敛性和多样性。本章的贡献概括如下。 (1)本章提出了一个一般性思想以在基于聚合的MOEAs中实现收敛性和多样性的 平衡,该思想利用了目标空间中解到权向量的垂直距离。 (2)本章分别在两个典型的基于聚合的MOEAs(MOEA/D和EFR)中实现了该思 想以增强它们在高维多目标优化中的性能,并形成了两个新的算法,即基于距离更新策略 的MOEA/D,简称MOEA/D-DU;带有排序限制模式的EFR,简称EFR-RR 。 (3)本章给出了一个可选的在线的归一化过程,它能嵌入MOEA/D-DU 和EFR-RR 中以有效解决非归一化问题。这是一个相当新颖的做法,截至本项研究工作发表为止,已 有文献还未对此进行广泛的研究[45,75]。 (4)本章所提出的算法基本包含所有在基于分解的MOEAs中曾经提出的技术,并 将它们扩展到解决MaOPs方面。尽管有些概念是类似的,但是本章实际上将它们有机 地组合在一个算法中。例如,MOEA/D-DU 继承了系统采样(与文献[45]相同)、邻域定 义(与文献[58]相同)、自适应归一化(与文献[45 、75]类似)、首次唯一性替代(与文献[75] 相同)和以优先顺序替代(本章予以介绍)的优点。 (5)本章讨论了所提出的算法与其他已有的基于分解的算法的相似性和不同之处。 基于大量的实验结果,对为什么这些算法在高维多目标优化中劣于所提算法给出了可能 的解释。 (6)在实验研究中,本章建议了一种可以在标准测试集上更加合理公平地比较 MOEAs(带有或不带有复杂归一化过程)性能的做法。 本章后续部分组织如下:3.它们在 2节简要介绍了一些最近提出的基于分解的算法, 某种程度上与本章所提算法类似;3节在分析了MOEA/D和EFR 的缺陷后,给出了本 章的基本思想;3.3. 4节详细介绍了如何利用该基本思想增强MOEA/D和EFR 在高维多 第 3 章在基于聚合的多目标演化算法中平衡收敛性和多样性 目标优化中的性能;3.3. 5节阐述了本章所采用的实验设计;6节从两个方面实验研究了 改进算法的性能;7节将所提改进算法与若干先进算法进行了大量的实验比较;8节 3.3. 对本章工作进行了小结。 3.类似算法简介 2 .......................... 本节将简要回顾最近提出的与本章所介绍算法类似的几个算法。 (1)Qi 等[119]提出了一个改进的MOEA/D算法,称为MOEA/D-AWA 。MOEA/DAWA 从两个方面增强了MOEA/D的性能。首先,MOEA/D-AWA 基于对原始切比雪 夫函数几何性质的分析提出了一种新的权向量初始化方法。其次,MOEA/D-AWA 采用 了一种自适应的权向量调整策略以处理具有复杂Pareto前沿面的问题。这种策略周期 性地调整权值以使子问题的权向量能够自适应地重新分布,从而得到更加均匀分布的解。 (2)Li 等[73]提出使用稳定匹配模型来协调MOEA/D中的选择过程,形成的新的 MOEA/D变体称作MOEA/D-STM 。在MOEA/D-STM 中,子问题和解被认为是两组 智能体。子问题偏好那些能使它的聚合函数值更低的解,而解则偏好那些对应权向量与 之相近的子问题。为了平衡子问题和解之间的偏好关系,MOEA/D-SMT 使用匹配算法 将每个解分配到每个子问题上以平衡进化搜索中的收敛性和多样性。与MOEA/D不 同,MOEA/D-STM 使用生成模式。 (3)Deb等[45]提出了一个基于参考点的高维多目标NSGA-Ⅱ,称作NSGA-Ⅲ,细节 请参见2.3节。需要特别指出的是,NSGAⅢ中结合了一种复杂的归一化技术以有效 1. 处理非归一化问题。 (4)Asafuddoula等[75]针对高维多目标优化提出了一个改进的基于分解的演化算 法,称作I-DBEA 。在I-DBEA 中,子代解只有在不被当前种群中任何解所支配的情况下 才尝试通过替代已有解的方式进入种群。子代解以随机的顺序与种群中所有解逐个竞 争,直到能够完成一次成功的替代或所有解都已比较完整。竞争的依据是两个距离,即 d2 就是上文提及的垂直距离。d2 较小的解胜出。只有当两个所比较解d1 和d2,其中, 该情形下d1 较小的解胜出。另外, 对应的d2 值相等时,才进一步考虑d1, IDBEA 中也 包含一个与NSGA-Ⅲ类似的在线归一化过程。 (5)Wang等[120]提出了一个使用全局替换策略的MOEA/D算法,称作MOEA/D-GR 。 在MOEA/D-GR 中,一旦产生一个新解,它就被关联到能获得最小聚合函数值的那个子 问题上。然后,与这个子问题最接近的若干子问题被选择作为该子问题的替换邻域,新的 解会尝试替换这些子问题的当前解。 注意,MOEA/D-STM 和MOEA/D-GR 只在2和3目标问题上进行了研究和验证 25 。 智能演化优化 26 尽管MOEA/D-AWA 在MaOPs问题上进行了测试,但是问题只限于退化问题。NSGA- Ⅲ和I-DBEA 是专门为高维多目标优化而设计的。另外,NSGA-Ⅲ和I-DBEA 虽然采用 了分解的思想,但是它们仍然依赖Pareto支配来控制收敛性,而不是通过聚合函数,这与 本节所提及的其他方法不同。 3.3 基本思想 ........................ 在基于聚合的MOEAs中,切比雪夫函数可能是最常使用的聚合函数类型。本章采 用切比雪夫函数的改进版本。设λ1,λ2,…,λN 是一组在目标空间中均匀分布的权向量, z* 是理想点,那么对于第j 个子问题,该函数可以定义为 Fj(x)=max m k=1 1 λj,k { |fk(x)-zk* |} (3.1) 其中,对于任意k∈{1,2,…,m },λj,k ≥0且Σm k=1 λj,k =1。若λj,k =0,λj,k 设置为10-6。 这种形式的切比雪夫函数较原始形式[7]有两个优势。首先,均匀分布的权向量将会 使搜索方向在目标空间中也是均匀分布的。其次,每个权向量唯一对应Pareto前沿面上 的一个Pareto最优解。证明可参见文献[119]。这两个优势在一定程度上缓解了算法在 多样性保持方面的难度。 然而在实际中,即使公式(3.1)也是有缺陷的。理想情况下,如果每个如公式(3.1)所 定义的函数Fj 都能够获得最优解,那么就能够同时实现最理想的多样性分布。但是,实 际上对于MOEA/D和EFR,这种情况并不成立。一方面,它们所得到的最终解一般都只 图3.1 二维目标空间中解 的分布示意图 是近优解,不足以隐式地确定最终种群的多样性。例 如,图3.1阐释了,在二维目标空间中,在5个权向量 (λ1,λ2,…,λ5)的辅助下,所得到最终解(A ,B,C,D 和E)的分布,其中,虚线表示按公式(3.1)分解所得子 问题的等高线。可以看出,解的分布并不如权向量的 分布那么均匀。这是因为尽管B 和D 能够分别在函 数F2 和F4 上取得较好的值,但是二者均与它们各自 所对应的搜索方向偏离较远。另一方面,更加重要的 问题出现在进化过程中,在其中,如果只依赖于聚合函 数值,解的选择将会被误导。例如,在图3.1中,存在 另一个解F,它在F2 上的值略差于B。在MOEA/D 中,F 有很大的可能在更新过程中替换B。而在EFR 第3 章 在基于聚合的多目标演化算法中平衡收敛性和多样性 27 中,因为在函数F2 上,B 比F 获得了更好的排序序号,所以F 非常可能在环境选择过程 中被淘汰。然而直觉上,对于权向量λ2,F 实际上是更佳的选择。 值得提及的是,在进化的早期,解通常是远离Pareto前沿面的,这时这种误导性的选 择更容易发生,从而可能导致搜索偏向Pareto前沿面的局部区域。 上述提及的两种情形可以都归因于一个事实,那就是,在目标空间中远离λj 的解也 能得到相对较好的Fj 值。公式(3.1)的等高线可以很好地解释这一问题,且由于稀疏分 布的解以及指数级增长的超体积,这个问题在高维多目标空间中将会变得更加严重。 考虑到所有这些因素,本章的研究动机是,在MOEA/D和EFR中,不仅要考虑一个 解的聚合函数值,而且要考虑它到相应权向量的垂直距离。这种做法期望能够使解接近 其所对应的权向量,从而显式地在进化过程中保持解的理想的分布,最终实现在高维多目 标优化中收敛性和多样性的平衡。值得一提的是,基于惩罚的边界交叉函数(PBI)[7]在 某种程度上隐式地考虑了解与权向量的接近程度,但是它仍然存在上述提到的问题。不 失一般性,本章只考虑公式(3.1)中定义的改进的切比雪夫函数。 假设f(x)=(f1(x),f2(x),…,fm (x))T 是解x 的目标向量,L 是以方向λj 通过 图3.2 二维目标空间中解到权向量 的垂直距离的示意图 z* 的直线,且u 是f(x)在L 上的投影。设dj,2(x)是 在目标空间中从解x 到权值向量λj 的垂直距离,那 么它可以按下式计算: dj,2(x)=‖f(x)-z* -dj,1(x)(λj/‖λj‖)‖ (3.2) 其中,dj,1(x)是z* 和u 之间的距离,且它能够通过下 式得到: dj,1(x)=‖(f(x)-z* )Tλj‖/‖λj‖ (3.3) 图3.2在二维目标空间中阐释了垂直距离dj,2(x)。 接下来,将详细描述如何利用dj,2 (x)分别增强 MOEA/D和EFR的性能。 3.4 算法详解 ........................ 在本节中,两个改进的算法MOEA/D-DU 和EFR-RR将分别在3.4.1节和3.4.2节 中详细介绍。3.4.3节提供了一个可选的归一化过程,它可以嵌入所提算法之中。3.4.4 节分别简要分析了MOEA/D-DU 和EFR-RR 在每代中的计算复杂度。3.4.5节将讨论 所提算法与文献中一些已有算法的相似点和不同点。 智能演化优化 3.1 增强MOEA/D 4. MOEA/D-DU的算法框架如算法3-1所示。算法首先产生一组均匀分布的权向量 Λ=λj-Ⅲ[ λ1,λ2,…,λN ,其中,确定了第 j 个子问题,即Fj 。与NSGA45]类似,MOEA/ D-DU也采用了Das和Dennis的系统方法[121]来产生这些结构化的权向量。在权向量生 x2,…,xN xj 成之后,随机初始化一个包含 N 个解x1,的种群,其中,表示第 j 个子问题 的当前解。在步骤3中,初始化理想点 z *。因为精确地计算 z * 是非常耗时的,它实际 上是由当前所找到的目标fi 的最小值来估计的,且在搜索过程中(i) 不断更新。MOEA/DDU仍然采用与它的前身算法[58]相同的交配限制模式来产生子代解,因此在步骤4~步 骤6中,需要确定每个子问题Fii)。步骤7i) 以1[ 的邻域B(~步骤8迭代执行直至终止条件满 足。在每一迭代中,解xi 的交配解xk 以概率 δ 从它的邻域B(中选择,- δ 的概率 从整个种群中选取。然后对xi 和xk 执行遗传算子,即模拟两点交叉和多项式变异92], 以得到一个新的解y,最后使用 y 来更新理想点和当前种群。 算法3- 1 MOEA/D-DU的算法框架 1: 生成一组权向量Λ←{λ2,…, λ1,λN } 2: 初始化种群P←{x2,…, x1,xN } z * z * 初始化理想点 z * z * 2,…,)T 4:fori←1toN do 3: ←(1, m 6:endfor i2,…,iT },其中,i2,…,是离λ最近的 T 个权向量 5: B(←{λλiT i i)i1,i1,λ 7: while终止条件不满足do 8: fori←1toN do 9: ifrnd()<δthen ←B( 10: i)E(a) 11: else 12: E←{1,2,…,N} 13: endif 14: 随机选择一个下标k∈ E 且k≠ i s( i , 15: y←GeneticOptorxxk )t((a) (r) (e) z *) 16: UpdateIdealPoiny, 17: UpdtCretouain( z *,Λ,P,K) aeunPpltoy, 18: endif 19:endwhile 20:return所有 P 中的非支配解 28 更新策略(算法3-1中的步骤17)是MOEA/D-DU中具有独特性的步骤,也是与原 第 3 章在基于聚合的多目标演化算法中平衡收敛性和多样性 始MOEA/D的显著不同之处。算法3-2详细阐述了该策略,其运行过程如下。一旦生 成新解y,则分别计算它与每个权向量λj , 1, N , 2( 即对于j=2,…,计算垂直距离dj,y), j=1,2,…, N 。然后从这 N 个距离中选择 K 个最小的距离,其中, K . N 是一个控制参 数。假设这 K 个最小的距离是dj1,y),y),…,y),且以非递减的顺序排列, 即dj1,2(y)≤dj2,2(2()。解 y 与解xj1,逐一进行比较, 2(dj2,2(djK ,2( xj2,…,如果一个解 xjk ,k∈{1,2,…, K },满足Fjk (xjk )>Fjk (y),那么解xjk 将被解 y 所替代,更新过程终 止。由上述可见,MOEA/D-DU使用了稳态模式,在当前种群中最多只有一个解可以被 新产生的解 y 所替代。 y)≤djK ,yxjK 算法3n( z *,Λ,P,K) - 2 UpdateCurentPopulatioy, 1:forj←1toN d 2: 计算从 y 向量λj 的垂直距离,即dj,2(到权(o) y) 3:dfr 从(e) N个(o) 距离dj,(n) y),2,…, N 中选出最小的 K 个距离,得到 4: 2(j=1, 2(2(y) dj1,y)≤dj2,y)≤djK ,2( y) 5:fork←1toK do dj2,2(y)≤…≤djK ,2( (( 6: ifFjk y)