基于分解的多目标进化算法MOEA/D

标签：进化算法目标问题 MOEA 向量 MOGLS

本文基于MOEA/D论文进行部分翻译、解释，是学习笔记的一部分。

结构和原文完全相同，大家可以用于辅助阅读论文。

如有错误，欢迎指出，感谢！

原文：MOEA/D: A Multiobjective Evolutionary AlgorithmBased on Decomposition. Qingfu Zhang, Senior Member, IEEE, and Hui Li

Abstract

基于分解的多目标进化算法(MOEA/D)：将多目标优化问题分解为多个标量优化子问题，并同时进行优化。每个子问题仅利用其相邻子问题的信息进行优化，使得MOEA/D每代的计算复杂度低于MOGLS和非支配排序遗传算法II (NSGA-II)。实验结果表明，采用简单分解方法的MOEA/D在多目标0-1背包问题和连续多目标优化问题上优于或近似于MOGLS和NSGA-II。

结果表明，采用目标归一化的MOEA/D方法可以处理不等尺度的目标，而采用高级分解方法的MOEA/D方法可以为3目标测试实例生成一组分布非常均匀的解。

本文还对MOEA/D的小种群能力、可扩展性和灵敏度进行了实验研究。

基于分解的多目标进化算法MOEA/D
Multiobjective Evolutionary Algorithm Based on Decomposition 核心思想：将原始的多目标问题转化为多个标量优化问题，每个子问题都关注于原始问题的一个特定方面或视角。
MOEA/D + 目标归一化 => 处理规模悬殊的目标 MOEA/D + 高级分解方法 => 为3-目标测试实例生成一组分布非常均匀的解

索引术语

Computational complexity：计算复杂性 Decomposition：分解 Evolutionary algorithm：进化算法 Multiobjective optimization：多目标优化 Pareto optimality：最优性

一、介绍

1.MOP

（1）定义

多目标优化问题(MOP)可以表述为:

$\Omega$ ：决策（变量）空间 $\Omega \rightarrow R ^{m}$ ：由m个实值目标函数组成，其中 $R^{m}$ 是目标空间。可达到的目标集合定义为 $\left \{F(x)| x \epsilon \Omega \right \}$

（2）解释

多目标优化问题MOP（Multiobjective optimization problem）：是优化问题的一个重要分支，它涉及同时优化两个或两个以上的目标函数。这些目标函数之间通常是相互冲突的，即一个目标的改善可能会导致另一个或多个目标的性能下降，因此不可能同时使所有目标都达到最优值。MOP的目标是在这些相互冲突的目标之间找到最佳的折中方案，从而得到一组均衡解，而不是单一的全局最优解。

（3）决策空间和目标空间

决策空间（Decision space）：所有可能决策的集合，又名变量空间（variable space），即变量的取值范围。

目标空间（Objective Space）：所有可能目标函数值的集合。
eg:
假设我们有一个简单的生产优化问题，目标是最大化某种产品的利润。
在这个问题中，我们可能有两个决策变量：
生产数量（x）：表示我们计划生产的产品数量。
广告投入（y）：表示我们计划用于产品推广的广告费用。
这两个决策变量(x, y)构成了我们的变量空间（或决策空间），即变量空间是生产数量和广告投入的所有可能组合，如(500, 1000)。
目标函数则是利润函数，它依赖于生产数量和广告投入，可以表示为 f(x, y)，即目标空间是利润的所有可能取值。

（4）连续MOP

如果 $x\epsilon R^{n}$ ，所有的目标都是连续的，且 $\Omega$ 表示为：

其中 $h_{j}$ 是连续函数，则我们称（1）为连续MOP。

通常情况下，由于（1）中的目标相互矛盾，因此无法产生同时最大化所有目标。我们必须平衡这些目标，目标间的最佳权衡可以用 Pareto最优来定义。

2.Pareto最优解

（1）定义

u主导v当且仅当： ①对所有的 $i\epsilon \left \{ 1,...,m \right \}$ 有 $u_{i}\geq v_{i}$ 。 ②至少存在一个 $j\epsilon \left \{ 1,...,m \right \}$ 使得 $u_{j}> v_{j}$ 。 Pareto最优解x*：没有任何一个x可以使x主导x*，即在Pareto最优解上，对一个目标优化必然会导致至少一个其他目标恶化。

（2）解释

帕累托最优解，多目标优化问题中的一个核心概念。它指的是在多个目标函数中，无法再改善一个目标函数的值而不损害其他目标函数值的解决方案。具体来说，如果在一个多目标优化问题中，存在一个解，使得不存在其他任何解能够在所有目标上都取得更好的结果，同时不导致至少一个目标的结果变差，那么这个解就被称为Pareto最优解。在多目标优化问题中，由于各个目标之间往往存在冲突，一个目标函数的改进可能会导致另一个目标函数的性能下降。因此，Pareto最优解并不是在所有目标上都达到最优的解，而是在各个目标之间达到了一个均衡状态。

（3）帕累托集合和帕累托前沿

帕累托集合PS（ Pareto Set ）：所有帕累托最优点的集合。 帕累托前沿PF（ Pareto Front ）：所有帕累托最优目标向量的集合。 Pareto set包含了所有无法被其他解支配的解，而Pareto front则是这些解在目标空间中的投影。在实际应用中，首先，通过优化算法求解得到Pareto set；然后，将Pareto set投影到目标空间中，即可视化表示得到Pareto front；最后，根据Pareto front进行决策分析。 PS和PF共同描述了多目标优化问题的最优解集和最优前沿，为决策者提供了在多个冲突目标之间做出权衡的依据。

（4）近似PF

在多目标优化的许多实际应用中，决策者在选择最终的首选解时需要近似于PF。大多数MOPs可能有多个甚至无限个帕累托最优向量，获取完整的最优向量是非常耗时的，且大量信息溢出，决策者可能对有过多的帕累托最优向量的处理不感兴趣。因此，许多多目标优化算法都是寻找可管理数量的Pareto最优向量，这些向量沿PF 均匀分布，从而很好地代表整个PF，一些研究人员也试图通过使用数学模型来近似PF。

3.聚合函数

在温和条件下，MOP的Pareto最优解，即目标为 $f_{i}$ 的集合的标量优化问题的最优解。因此，对目标优化问题的逼近可以分解为若干标量目标优化子问题。在MOP中，聚合函数是将多个目标函数转化为单个目标函数的关键工具，聚合函数的选择直接影响了优化问题的求解效果和效率。几种构造聚合函数的方法：加权和法、Tchebycheff法、边界相交方法。

4.适应度

在这些MOEAs中，大多数现代先进算法并不直接采用分解策略（decomposition），而是将整个MOP视为一个整体来处理，不将每个个体解与特定的标量优化问题相关联。

（1）引入

在传统的标量优化问题中，所有解都可以直接通过其目标函数值进行比较，算法的目标是找到单一的最优解。然而，在MOPs中，由于存在多个相互冲突的目标，解之间无法形成完整的排序关系，即一个解并不总是优于另一个解，解之间的比较是复杂的，可能互不支配。从而，MOEAs的目标转变为找到一组Pareto最优解，这些解在目标空间中尽可能分散，以全面代表整个Pareto前沿。因此，传统的为标量优化设计的选择算子无法直接应用于非分解的MOEAs中。

（2）适应性评估（Fitness Assignment）的重要性

为了在多目标环境下有效地使用进化算法，需要一种机制来为每个个体解分配一个相对适应度值，以反映其在选择过程中的效用，通过合理的适应性评估，可以将标量优化的进化算法扩展到处理MOPs。适应度评估不仅为选择操作提供了依据，还通过平衡多样性和质量来指导算法的搜索方向，从而有效地解决了多目标优化问题。

（3）流行的适应性评估策略

基于交替目标的适应性评估：如向量评估遗传算法（Vector Evaluated Genetic Algorithm, VEGA）通过交替优化不同的目标来分配适应度，这种策略简单直观，但可能无法很好地平衡多个目标。基于支配的适应性评估：这类方法通过比较解之间的支配关系来分配适应度。例如，Pareto存档进化策略（Pareto Archived Evolution Strategy, PAES）、强度Pareto进化算法II（Strength Pareto Evolutionary Algorithm II, SPEA-II）和非支配排序遗传算法II（Nondominated Sorting Genetic Algorithm II, NSGA-II）等算法都是基于这种策略。

（4）其他增强技术

除了适应性评估外，还有一些其他技术可以进一步提升MOEAs的性能，如交配限制（mating restriction）来避免相近解的过度繁殖，多样性维护（diversity maintenance）来保持解集的多样性，利用MOPs的某些特性（如问题可分解性），以及使用外部种群来存储非支配解等。

5.MOEA/D

MOEA/D是一种新的多目标进化算法，其核心思想是将多目标优化问题（MOP）显式地分解为N个标量优化子问题，这种分解策略使得算法能够通过进化一群解来同时解决这些子问题。在MOEA/D中，每个子问题（即标量聚合函数）的优化只依赖于其相邻子问题的信息，这种依赖关系是基于子问题聚合系数向量之间的距离来定义的。相邻子问题的最优解应该非常相似，这有助于算法在搜索空间中保持解的多样性和收敛性。
MOEA/D具有以下几个显著特征：

分解方法的简单高效集成：MOEA/D将分解方法引入多目标进化计算，且提供了一种简单而高效的方式，不仅简化了算法设计，还提高了算法的求解效率。
优化标量子问题而非整体MOP：MOEA/D通过优化标量子问题来间接解决多目标优化问题，这避免了直接处理整体MOP时遇到的适应度分配和多样性维护等难题，因为每个子问题都可以独立地进行优化，并且可以利用相邻子问题的信息来指导搜索方向。
较低的计算复杂度和优越的性能：与NSGA-II和MOGLS等算法相比，MOEA/D在每一代的计算复杂度更低。这得益于其分解策略，使得算法能够并行地优化多个子问题。在解决0-1多目标背包测试实例时，MOEA/D在解的质量上优于MOGLS（当两者使用相同的分解方法时）。在连续多目标测试实例上，MOEA/D的性能也表现出色，特别是当使用先进的分解方法时，其性能远优于NSGA-II。此外，即使使用较小的种群规模，MOEA/D也能够产生数量较少但分布非常均匀的解集。
目标归一化技术的集成：为了处理目标函数尺度差异较大的多目标问题，MOEA/D可以很方便地集成目标归一化技术。这种归一化处理有助于消除不同目标之间的尺度差异，使得算法能够更公平地评估解的质量，并提高算法的鲁棒性和适应性。
便于利用标量优化方法：由于MOEA/D中的每个解都对应于一个标量子问题，因此算法可以很方便地利用标量优化方法来加速子问题的求解过程。相比之下，非分解MOEAs由于无法将多目标问题分解为标量子问题，因此很难直接利用这些标量优化方法的优势。而MOEA/D通过分解策略，使得标量优化方法的应用变得自然而高效。

二、三种MOPs的分解方法

有几种方法可以将PF的近似问题转化为若干标量优化问题。下面，我们将介绍在我们的实验研究中使用的三种方法。

多目标优化问题MOP(1)如下，放这里方便大家对照：

A. 加权和法

这种方法考虑了不同目标的凸组合。
设 $\lambda = \left ( \lambda _{1},...,\lambda _{m} \right )^{T}$ 为权重向量，即对于所有 $i=1,...,m$ ， $\lambda _{i}\geq 0$ 且 $\sum_{i=1}^{m}\lambda _{i}=1$ 。
则下式标量优化问题的最优解为:

是(1)的帕累托最优点，如果(1)表示最小化，则(2)中的“最大化”应改为“最小化”。
其中我们用 $g^{ws}\left ( x\mid \lambda \right )$ 强调 $\lambda$ 是该目标函数中的系数向量，而x是要优化的变量。为了生成一组不同的Pareto最优向量，可以在上述标量优化问题中使用不同的权向量 $\lambda$ 。
如果PF是凹的(在最小化的情况下是凸的)，这种方法可以很好地工作。然而，在非凹PFs的情况下，这种方法并不能得到所有的Pareto最优向量。

思路：

给不同的目标赋予不同的权重，最大化时，需要最大化的目标权重给正值，需要最小化的目标权重给负值，将最小化正数问题转换为最大化负数问题，再加权和组合一起求最大值。

通过不同的权重 λ 可以得到不同的最优解，权重的选择取决于决策者对各个目标的重视程度。不同的权重组合可能导致不同的Pareto最优解，这反映了不同偏好下的最优决策。

在加权求和之前，可能需要对目标函数进行归一化或标准化处理，以确保它们在同一量级上，从而避免某些目标因量纲或范围过大而主导优化过程。

缺点：有效性受到PF形状的限制，在最大化问题中，如果PF是凹的，通常能够很好地工作。

eg: 假设我们有一个简单的生产优化问题，目标是最大化某种产品的利润，最小化成本。
在这个问题中，我们可能有两个决策变量：
生产数量（x）：表示我们计划生产的产品数量。
广告投入（y）：表示我们计划用于产品推广的广告费用。
设利润函数为 f(x, y)，成本函数为 g(x, y)。

在这个例子中，我们可以将成本函数 g(x,y) 取反，即最小化成本变为最大化负成本，然后与利润函数 f(x,y) 加权求和。
设 λ1 和 λ2 分别为利润和成本的权重，且 λ1+λ2=1，则加权和法的目标函数为：
F(x,y)=λ1f(x,y)−λ2g(x,y)
我们的目标是找到 (x,y) 使得 F(x,y) 最大。

B. 切比雪夫法

在这种方法中，标量优化问题为

其中 $\lambda= \left ( \lambda _{1}, \lambda _{2},..., \lambda _{m} \right )$ 是一个权重向量，表示各个目标函数的相对重要性。 $z^{*}=\left ( z_{1}^{*},..., z_{m}^{*} \right )^{T}$ 是参考点，即对 $i=1,...,m$ 有 $z_{i}^*{}=max\left \{ f_{i}\left ( x \right ) \mid x\epsilon \Omega \right \}$ 。

帕累托最优点 $x^{*}$ 存在一个权向量 $\lambda$ ，使得 $x^{*}$ 是(3)的最优解，(3)的每个最优解都是(1)的帕累托最优解。因此，通过改变权向量可以得到不同的帕累托最优解。
这个表达式的目的是找到一个决策变量x*，使得在所有目标函数相对于参考点的偏差中，加权后的最大偏差（即每个目标函数与参考点之间的距离在加权后的最大值）最小化。

这种方法的一个缺点是它的聚合函数对于连续的MOP来说不是平滑的。但是，由于我们的算法不需要计算聚合函数的导数，因此在本文提出的EA框架中仍然可以使用它。

思路：

计算当前各个目标函数与参考点之间距离在加权后的值，并取其中的最大值，通过最小化这个值来不断接近参考点，参考点指明了优化方向或目标。即我们试图找到一个平衡点，使得没有一个目标函数与参考点之间的偏差过大，同时考虑到不同目标之间的相对重要性。

缺点：

聚合函数对于连续的MOP来说不是平滑的，可能导致优化算法在搜索过程中陷入局部最优解，收敛速度减缓，甚至某些情况下会出现振荡现象。若权重向量分布不均匀或数量不多时，得到的解集可能在目标空间中分布不均匀。

C. 边界交叉法BI

在一定的正则性条件下，连续MOP的PF是其可达到目标集的最右上边界的一部分。从几何上讲，这些BI方法的目的是找到最顶端边界和一组线的交点。如果这些线在某种意义上是均匀分布的，那么我们可以期望得到的交点能够很好地近似整个PF。这些方法能够处理非凹PF。

在数学上，我们考虑以下标量优化子问题：

其中λ和z*分别为权重向量和参考点。

如图1所示，约束z*-F(x)=dλ确保F(x)始终在L上，即方向为λ并经过z*的直线。目标是将F(x)推得尽可能高，使其达到可实现目标集的边界，达到或接近PF。

其中F(x)是目标函数向量。
z*是参考点，通常是一个理想点或是一个足够大的点，以确保优化过程朝向PF进行。
λ是权重向量，用于定义从参考点z*出发的直线的方向。

上述方法的缺点之一是它必须处理等式约束，在我们的实现中，我们使用惩罚方法来处理等式约束。具体如下：

其中，θ预定义惩罚因子用于调整d1和d2之间的相对重要性。
如图所示：

d1(λ方向的距离)：z*与F(x)在λ方向上投影y的差。
d2(λ垂直方向的距离)：计算F(x)和L间的距离，实际上是在计算F(x)与一个由 z*沿λ反方向移动d1距离后得到的点y之间的距离。这个移动后的点可以看作是F(x)在λ方向上应该接近的一个“目标点”。

如果设置得当，(4)和(5)的解应该非常接近，我们将这种方法称为基于惩罚的边界交叉(PBI)方法。

与Tchebycheff方法相比，PBI方法(或通用BI方法)的优点如下：

在两个以上目标的情况下，PBI法和Tchebycheff法使用同一组均匀分布的权重向量，PBI法得到的最优解应比 Tchebycheff法得到的最优解分布更均匀，特别是当权重向量数量不多时。
PBI的支配关系确定性更高。

直接处理等式约束可能会使问题变得复杂且难以求解
=>引入惩罚项是一种常用的策略，通过将约束转化为目标函数中的惩罚项。
=>从而将约束优化问题转化为无约束优化问题。

然而，这些好处是有代价的。必须设置惩罚因子的值，惩罚因子过大或过小都会使惩罚方法的性能下降。
过小的惩罚因子，即使约束被显著违反，惩罚项对目标函数的贡献也相对较小。这会导致算法在优化过程中更倾向于最小化原始目标函数，而不太关注约束条件是否得到满足。因此，算法可能会找到违反约束的次优解。
过大的惩罚因子相反，惩罚项可能会变得过于严厉，以至于主导了目标函数。这会导致算法在搜索过程中过于保守，总是优先考虑满足约束条件，即使这样做会牺牲目标函数的值。这种情况下，算法可能难以跳出局部最优解，或者无法充分探索解空间以找到全局最优解，可能导致算法错过了一些潜在的好解。

上述方法可用于将PF的近似分解为若干标量优化问题，大量均匀分布的权重向量通常会产生一组Pareto最优向量，这些向量可能不是均匀分布的，但可以很好地近似PF。

三、基于分解的多目标进化算法MOEA/D

A. 总体框架

本文提出的基于分解的多目标进化算法(MOEA/D)需要对所考虑的MOP进行分解。任何分解方法都可以达到这个目的。在下面的描述中，我们假设采用了Tchebycheff方法。

多目标优化问题MOP(1)如下，放这里方便大家对照：

1. 问题分析

设 $\lambda ^{1},...,\lambda ^{N}$ 为一组均匀分布的权向量， $z^{*}$ 为参考点。
如第2节所示，利用Tchebycheff方法可将(1)的PF的逼近问题分解为N个标量优化子问题，第 j 个子问题的目标函数为

其中 $\lambda ^{^{j}}=\left ( \lambda _{1}^{j},..., \lambda _{m}^{j} \right )^{T}$ 。MOEA/D在一次运行中同时最小化所有这N个目标函数。

$g^{te}$ 是 $\lambda$ 的连续函数，当 $\lambda ^{i}$ 与 $\lambda ^{j}$ 接近时， $g^{te}\left ( x\mid \lambda ^{i},z^{*} \right )$ 的最优解应与 $g^{te}\left ( x\mid \lambda ^{j},z^{*} \right )$ 的最优解接近。因此，关于这些权重向量接近 $\lambda ^{i}$ 的 $g^{te}$ 的任何信息都应该有助于优化 $g^{te}\left ( x\mid \lambda ^{i},z^{*} \right )$ ，这是MOEA/D背后的主要原理。

在MOEA/D中，权向量 $\lambda ^{i}$ 的邻域定义为其在 $\left \{ \lambda _{1},..., \lambda _{N}\right \}$ 中最近的几个权向量的集合。第i个子问题的邻域由 $\lambda ^{i}$ 邻域中所有权向量的子问题组成。总体种群由迄今为止为每个子问题找到的最佳解组成。在MOEA/D中，只有邻近子问题的当前解被用来优化子问题。

权重向量和子问题：在MOEA/D中，每个子问题都由一个权重向量λ表示，这个权重向量决定了不同目标之间的相对重要性。
邻域：为了促进子问题之间的信息交换和合作，MOEA/D引入了邻域的概念。一个子问题（或权重向量λ）的邻域定义为该权重向量在空间中最近的几个权重向量的集合。
邻域子问题和优化：在MOEA/D中，每个子问题都维护一个当前最好的解。当优化一个特定的子问题时，算法不仅考虑该子问题自身的信息，还考虑其邻域内其他子问题的信息，算法会利用邻域内子问题的当前解来指导当前子问题的优化过程。这种机制促进了不同子问题之间的协同进化，有助于算法找到更好的Pareto前沿近似。
MOEA/D的总体（或种群）：由所有子问题的当前最好解组成，这些解代表了算法在搜索空间中的当前知识，是算法进一步搜索的起点。通过不断迭代更新这些解，MOEA/D能够逐步逼近真正的Pareto前沿。

2. MOEA/D每轮保持的数据

在每一代 t ，使用Tchebycheff方法的MOEA/D保持：

一个有N个点的种群 $x^{1},...,x^{N}\epsilon \ \Omega$ ，其中 $x^{i}$ 是第 i 个子问题的当前解；
$FV^{1},...,FV^{N}$ ，其中 $FV^{i}$ 是 $x^{i}$ 的F值，即对于 $i=1,...,N$ ， $FV^{i}=F\left ( x^{i} \right )$ ；
$z=\left ( z_{1} ,...,z_{m} \right )^{T}$ ，其中 $z_{i}$ 是到目前为止找到的目标 $f_{i}$ 的最佳值；
外部种群(external population, EP)，用于存储搜索过程中发现的非支配解。

3. 算法工作流程

算法工作如下：

Input：

MOP(1)，即多目标优化问题；
一个终止条件（如达到最大迭代次数、解的质量不再显著提高等）；
N：在MOEA/D中考虑的子问题数量；
$\lambda ^{1},...,\lambda ^{N}$ ：均匀分布的N个权重向量；
T：每个权重向量邻域内权重向量的个数。

Output：EP（用于存储搜索过程中找到的非支配解的外部种群）

Step 1：初始化
Step 1.1：设 $EP=\Phi$
                EP是存储当前找到的非支配解的集合，初始时没有任何解。
Step 1.2：计算每个权重向量的邻域
                计算任意两个权重向量之间的欧氏距离，为了确定每个权重向量的邻居，需要计算所有权重向量对之间的欧氏距离。然后计算出离每个权重向量最近的T个权重向量，这些向量构成了该权重向量的邻域。对于每个 $i=1,...,N$ ，设集合 $B\left ( i \right )= \left \{ i_{1},..., i_{T}\right \}$ ，其中 $\lambda ^{i_{1}},...,\lambda ^{i_{T}}$ 是最接近 $\lambda ^{i}$ 的 T 个权向量。
Step 1.3：生成初始种群
                随机或通过特定于问题的方法生成初始种群，即N个初始解 $x^{1},...x^{N}$ ，每个解对应一个权重向量，设 $FV^{i}= F\left ( x^{i} \right )$ 。
Step 1.4：初始化理想点z
                通过特定于问题的方法初始化理想点 $z=\left ( z_{1}, ..., z_{m} \right )^{T}$ ，用于后续比较解的优劣。

Step 2：更新
对于每个权重向量（即每个子问题），   $i=1,...,N$ ，重复以下步骤：
        Step 2.1：交叉
                从B(i)中随机选择两个指标k、l，即在邻域内随机选择两个解（索引为k 和l），然后利用遗传算子由 $x^{k}$ 和 $x^{l}$ 生成一个新的解 y。由于 $x^{k}$ 和 $x^{l}$ 是 $\lambda ^{i}$ 邻居中的当前最优解，它们交叉后的后代y有望成为 $\lambda ^{i}$ 对于问题的良好解。
        Step 2.2：改善
                对 y 应用特定于问题的修复/改善启发式生成 y' ，提高解的质量。这个步骤的目的是确保y'是有效的，可能包括修复不可行解或进一步搜索更好的解。
        Step 2.3：更新z
对每一个 $j=1,...,m$ ，如果 $z_{j}< f_{j}\left ( y' \right )$ ，设 $z_{j}=f_{j}\left ( y' \right )$ 。即如果 y' 在当前目标表现优于理想点z，则更新z在当前目标下的值。
        Step 2.4：更新邻域解
对每一个 $j\epsilon \ B(i)$ ，如果 $g^{te}\left ( y'|\lambda ^{j},z \right )\leq g^{te}\left ( x^{j}|\lambda ^{j},z \right )$ ，则更新邻域解 $x^{j}= y'$ 、 $FV^{j}= F\left ( y' \right )$ 。即如果 y' 根据聚合函数表现得更好，则更新该邻域内的解为 y' ，并更新相应的适应度值。
        Step 2.5：更新外部种群EP
从EP中除去所有由 F(y') 支配的向量。
                如果EP中没有向量支配F(y')，则将F(y')加到EP中。

Step 3：终止条件
如果满足终止标准，则终止并输出EP。否则转至 Step 2 。

在多目标优化中，理想点 z*是一个虚构的点，其每个坐标都是所有目标函数在当前解集上的最小值。然而，由于优化问题的复杂性，我们往往无法找到这样的点。
因此我们只能用一个近似的理想点z来代替，这个近似的理想点z在算法开始时通过某种问题特定的方法初始化（如Step 1.4所示），并在算法迭代过程中不断更新（如Step 2.3所示），以反映当前解集在各个目标上的最佳表现。

这个流程展示了MOEA/D如何通过分解多目标优化问题为一系列单目标子问题，并利用权重向量的邻域关系来协同进化这些子问题的解，最终通过EP来逼近整个多目标问题的Pareto前沿。

B. 讨论

1.MOEA/D 中考虑有限数量子问题的原因

在MOEA/D中使用的权重向量是N个预选权重向量中的一个，这些权重向量是预先选定的，通常均匀分布在目标空间中，以确保算法的搜索能够覆盖整个Pareto前沿。MOEA/D通过同时优化这些子问题来逼近Pareto前沿，每个子问题代表了对Pareto前沿的一个不同视角或偏好。

而MOGLS在每次迭代时随机生成一个权重向量，旨在尽可能优化所有可能的聚合函数（即权重向量的所有可能组合），以期望发现更好的Pareto解。由于计算资源总是有限的，因此优化所有可能的聚合函数不是很实际。且决策者通常只需要一组有限数量的、均匀分布的Pareto解，而不是一个无限大的解集。因此，优化所有可能的聚合函数并不符合决策者的实际需求。

相比之下，决策者只需要有限个均匀分布的Pareto解，优化有限个选定的标量优化子问题不仅是现实合适的，而且能够有效地利用计算资源，满足决策者的需求。

2.如何在 MOEA/D 中保持多样性

如第一节所述，MOEA需要保持其人口的多样性，以产生一套具有代表性的解决方案。大多数非分解MOEA，如NSGA-II和SPEA-II，在选择解决方案时使用拥挤距离来保持多样性。然而，在这些算法中，产生均匀分布的Pareto最优目标向量并不容易。

在MOEA/D中，将一个MOP分解为多个标量优化子问题，当前种群中的不同解决方案与不同的子问题相关联，这些子问题之间的“多样性”自然会导致种群的多样性。

子问题的多样性：由于每个子问题都与一个独特的权重向量相关联，只要权重向量均匀分布、选择得当，则子问题在目标空间中的均匀覆盖，自然地在种群中引入多样性，那么MOEA/D将有很好的机会产生均匀分布的Pareto解。
进化过程中的邻域关系：MOEA/D采用了一种邻域合作的思想，即每个解在进化过程中不仅关注自身的优化，还与其邻近的子问题解进行协作。这种协作机制有助于在整个Pareto前沿上均匀分布解，因为每个解都尝试在其邻域内找到更好的解，从而推动整个种群向Pareto前沿逼近。

综上所述，MOEA/D通过分解多目标优化问题为一系列单目标优化子问题，并利用权重向量的均匀分布和邻域合作机制来维护种群的多样性，从而有可能产生均匀分布的Pareto最优解集。

3.MOEA/D 中的交配限制和T 的作用

T指的是邻域的大小，即每个子问题在分解策略下考虑的相邻子问题的数量。
交配限制：在MOEA/D中，只有子问题最近邻的当前解才能用于优化子问题，即只有当两个解对应两个相邻的子问题时，它们才有机会配对。

T太小：当T设置得过小时，每个子问题只与极少数其他子问题相邻。这意味着在遗传操作中，被选中进行交叉或变异的两个解（即两个父代解）很可能来自于非常相似的子问题。由于这些子问题之间的高度相似性，它们的解也可能非常相似。因此，通过遗传操作生成的子代解（即后代解）很可能非常接近其父母解，导致算法在搜索空间中的探索能力受限。这种情况下，算法可能容易陷入局部最优，因为它没有足够的多样性来探索新的、可能更优的解区域。
T太大：如果T设置得过大，每个子问题将与大量的其他子问题相邻。虽然这增加了算法的多样性，但由于相邻子问题的权重向量可能差异较大，导致它们的解在搜索空间中可能分布得较远。这意味着被选中的两个父代解可能并不适合当前正在优化的子问题。因此，它们的后代解也可能不是该子问题的良好候选解，从而削弱了算法的利用能力。

简而言之

T太小：亲本很相似，孩子和亲本也很相似，算法缺乏探索搜索空间新领域的能力
T太大：亲本对于所考虑的子问题可能很差，削弱了算法的开发能力，增加了计算量。

C. MOEA/D的变体

MOEA/D的框架非常灵活，允许使用不同的分解方法和策略来增强其性能或适应不同的问题特性。以下是对MOEA/D一些变体及其特点的展开解释：

1. 不同的分解方法

我们可以在MOEA/D中使用任何其他分解方法。当采用加权和方法时，MOEA/D不需要维持z。MOEA/D的核心在于其分解策略，常用的分解方法包括加权和方法（Weighted Sum Approach）、切比雪夫方法（Tchebycheff Approach）和边界交叉法（Boundary Intersection Approach, BI），不同的分解方法都有其适用的场景和优缺点。

分解方法

优点

缺点

适用场景

加权和方法

1. 加权和方法通过为每个目标函数分配一个权重，然后将这些加权后的目标函数相加，形成一个单一的目标函数进行优化。这种方法直观易懂。

2. 偏好信息明确时，更容易通过调整权重获得符合期望的解。

3. 计算上相对简单，计算效率高。

1. 不适用于非凸的Pareto前沿。

2. 权重选择敏感，需要决策者具备一定的先验知识。

1. 目标函数间可比较且偏好信息明确的多目标优化问题。

2. PF为凸或近似凸形状的问题。

切比雪夫方法

1. 通用性强，能处理复杂PF形状，包括非凸和不连续的PF。

2. 该方法通过最小化每个目标函数值与参考点之间的最大偏差来寻求平衡解，有助于找到Pareto前沿上的均匀分布点。

1. 计算资源需求可能较高。

2. 参考点选择困难，对算法性能有影响。

1. PF形状复杂、非凸或不连续的多目标优化问题。

2. 需要找到Pareto前沿上均匀分布点的场景。

边界交叉法

1. 直接针对Pareto前沿进行搜索，有助于找到更接近真实PF的解。

2. 可能更适用于具有复杂PF形状（如断开、重叠）的问题。

1. 实现相对复杂，需要更多技术和算法支持。

2. 性能受内部参数和算法实现细节影响。

1. PF形状非常复杂或具有特殊性质（如断开、重叠）的多目标优化问题

2. 需要高精度逼近真实PF的场景

2. 子问题更新策略

MOEA/D的【Step 2.2 改善】允许通过标量优化方法来更新子问题的解，这是其一大特色。然而，这一步骤并不是必须的，特别是当【Step 2.1 交叉】（如通过遗传操作产生新解）已经能够产生可行解时。

3. 外部种群（EP）

外部种群（EP）在MOEA/D中用于存储找到的近似Pareto最优解集，以辅助算法在搜索过程中保持解的多样性。使用外部种群EP也是一种选择，尽管它通常对提高算法的性能非常有帮助。另一种方法是在不维护EP时返回最终内部种群作为PF的近似值。
当然，在MOEA/D框架下，一些变体可能通过限制EP的大小来避免内存溢出问题，或者采用更复杂的策略来更新EP，如基于密度的选择、自适应EP大小调整等。

MOEA/D的变体通过改变分解方法、子问题更新策略以及外部种群的使用方式，来适应不同的多目标优化问题和需求。这些变体在保持MOEA/D基本框架的同时，通过引入新的技术和策略来提升算法的性能和适用范围。

四、MOEA/D 和 MOGLS 对比

下面，我们首先介绍MOGLS，然后分析MOGLS和MOEA/D的复杂性。我们还比较了这两种算法在多目标0/1背包问题的一组测试实例上的性能。选择MOGLS进行比较的主要原因是它也是基于分解的，并且在多目标0/1背包问题上优于许多流行的算法。

多目标优化问题MOP(1)如下，放这里方便大家对照：

A. MOGLS

MOGLS的基本思想是将MOP(1)重新表述为所有加权Tchebycheff函数或所有加权和函数的同时优化。

在每次迭代中，MOGLS保持：

一组当前解(CS)，以及这些解的F值；
外部种群(EP)，用于存储非支配的解决方案。

如果MOGLS优化了加权Tchebycheff函数，它也应该保持：

$z=\left ( z_{1},...,z_{m} \right )^{T}$ ，其中 $z_{i}$ 是目前为止找到的目标 $f_{i}$ 的最大值。

MOGLS需要两个控制参数K和S。K是临时精英人口的规模，S是CS的初始规模。

Input：

MOP(1)，即多目标优化问题；
停止标准（如达到最大迭代次数、解的质量不再显著提高等）；
K：临时精英种群的规模；
S：初始种群的规模。

Output：EP（用于存储搜索过程中找到的非支配解的外部种群）

Step 1：初始化
        Step 1.1：生成S个初始解
                随机或通过特定问题的方法生成S个初始解 $x^{1},...,x^{S}$ 。然后，CS初始化为 $\left \{ x^{1},...,x^{S} \right \}$ 。
        Step 1.2：初始化理想点z
                通过特定于问题的方法初始化理想点 $z=\left ( z_{1}, ..., z_{m} \right )^{T}$ ，用于后续比较解的优劣。
        Step 1.3：初始化外部种群EP
                将EP初始化为CS中所有非支配解的F值的集合。

Step 2：更新
        Step 2.1：交叉
                均匀随机生成一个权向量 λ 。从CS中选择K个最优解，对Tchebycheff聚集函数 $g^{te}$ 和权向量 λ ，形成一个临时精英群体(TEP)。
                从TEP随机抽取两个解，然后利用遗传算子从这两个解生成一个新的解 y 。
        Step 2.2：改善
                对 y 应用特定于问题的修复/改善启发式生成 y' ，提高解的质量。这个步骤的目的是确保y'是有效的，可能包括修复不可行解或进一步搜索更好的解。
        Step 2.3：更新z
对每一个 $j=1,...,m$ ，如果 $z_{j}< f_{j}\left ( y' \right )$ ，设 $z_{j}=f_{j}\left ( y' \right )$ 。即如果 y' 在当前目标表现优于理想点z，则更新z在当前目标下的值。
        Step 2.4：更新TEP中的解
                如果 y' 在权向量 λ 上优于TEP中关于 $g^{te}$ 的最差解，并且不同于TEP中关于F值的任何解，则将其添加到集合CS中。如果CS的大小大于 $K\times S$ ，则删除CS中最老的解。
        Step 2.5：更新外部种群EP
从EP中除去所有由 F(y') 支配的向量。
                如果EP中没有向量支配F(y')，则将F(y')加到EP中。

Step 3：终止条件
如果满足终止标准，则终止并输出EP。否则转至 Step 2 。

与使用Tchebycheff方法的MOEA/D一样，z 被用作 $g^{te}$ 中z*的替代品。
对于加权求和法的MOGLS， $g^{te}$ 应替换为 $g^{ws}$ ，不需要存储 z，因此应删除步骤2.3。MOGLS需要保留所有当前解决方案的F值，因为这些F值将在步骤2.4中用于计算 $g^{te}$ 的值。

B. MOEA/D和MOGLS的复杂度比较

1. 空间复杂度

在搜索过程中，MOEA/D需要维护其N个解的内部种群和外部种群EP，而MOGLS则存储当前解集CS和外部种群EP。CS的大小逐渐增大，直到达到其上界，建议设为 $K\times S$ 。因此，如果MOGLS算法中的 $K\times S$ 远大于MOEA/D算法中的N，且两种算法产生的非支配解数量大致相同，则MOEA/D算法的空间复杂度低于MOGLS算法。

2.计算复杂度

在比较多目标优化算法MOEA/D和多目标梯度局部搜索算法MOGLS的计算复杂度时，我们主要关注它们在单个迭代步骤（特别是【Step 2：更新】）中的计算需求，MOEA/D和MOGLS的主要计算成本都涉及到【Step 2：更新】。下面详细展开对这两个算法【Step 2：更新】中各个子步骤的计算复杂度分析。

（1）Step2.1的计算复杂度

MOEA/D的【Step 2.1：交叉】：在MOEA/D中，【Step 2.1：交叉】通常涉及从当前种群中随机选择两个解进行遗传操作，这个步骤的计算复杂度较低，通常不涉及对整个解空间的大量计算。

MOGLS的【Step 2.1：交叉】：MOGLS的【Step 2.1：交叉】需要生成临时精英群体TEP，这通常涉及到计算当前解空间中所有点的 $g^{te}$ 值，这一步的计算复杂度是 $O\left ( m\times \mid CS \mid \right )$ 。如果对TEP的选择采用朴素选择方法，则需要 $O\left ( K\times \mid CS \mid \right )$ 基本操作。而MOEA/D中的【Step 2.1：交叉】只需要随机选取两个遗传算子的解，由于|CS|可能非常大，MOGLS这个步骤的计算成本显著高于MOEA/D的【Step 2.1：交叉】。

（2）Step2.2和2.3的计算复杂度

MOEA/D和MOGLS的【Step 2.2：改善】和【Step 2.3：更新z】：在MOEA/D和MOGLS中，步骤2.2和2.3的计算复杂度是相似的，因为它们都依赖于评估函数和种群更新的策略。

（3）Step2.4的计算复杂度

MOEA/D的【Step 2.4：更新邻域解】：涉及更新与试验解相关联的权重向量或子问题的邻居信息，这个步骤的计算复杂度通常是O(T)，其中T是子问题的数量或权重向量的数量。

MOGLS的【Step 2.4：更新TEP中的解】：涉及更新与试验解相关的其他数据结构或参数，由于MOGLS的局部搜索特性，这一步的计算复杂度可能与目标数量K相关，通常是O(K)。

当T和K相近时，这两个步骤的计算成本差异不大。

因此，可以得出结论，在单个迭代步骤中，MOEA/D的计算成本低于MOGLS。

C. 多目标0-1背包问题

给定一组n个物品和一组m个背包，多目标0-1背包问题(MOKP)可以表示为：、

其中 $p_{ij}\geq 0$ 为背包 i 中物品 j 的利润， $w_{ij}\geq 0$ 为背包 i 中物品 j 的重量， $c_{i}$ 为背包 i 的容量。
$x_{i}=1$ 意味着该物品 i 被选中并放入所有背包中。
公式为要利润最大，同时服从于每个包 i 的重量小于 i 包总容量 $c_{i}$ 。

MOKP是NP-hard的。

NP-hard属于一类非常难解决的问题，没有已知的多项式时间算法能够解决所有实例（或许根本不存在）。

但是如果给了该问题的一个答案，可以在多项式时间内判断这个答案是否正确，这种可以在多项式时间内验证一个解是否正确的问题称为NP问题，亦称为易验证问题类。

MOKP可以对资源分配中的各种应用进行建模，模拟多种资源分配应用中的问题，涉及到如何有效、公平地分配有限资源以满足多个目标或需求。已经提出了上述问题的一组9个测试实例，MOGLS优于许多MOEA，在本文中，我们还将使用这9个实例来比较MOEA/D和MOGLS的性能。

D. MOEA/D和MOGLS在MOKP(多目标0-1背包问题)中的实现

1. 修复方法

为了将EA应用于MOKP，我们需要一个启发式方法来修复不可行解。
设 $y=\left ( y_{1},...,y_{n} \right )^{T}\epsilon \left \{ 0,1 \right \}^{n}$ 为(7)的不可行解。注意(7)中的 $w_{ij}$ 和 $p_{ij}$ 是非负的，可以从中删除一些项（即将某些 $y_{i}$ 的值从1更改为0）以使其可行。

Input：

MOP（7）；
一个解： $y=\left ( y_{1},...,y_{n} \right )^{T}$ ；
一个要最大化的目标函数： $g:\left \{ 0,1 \right \}^{n}\rightarrow R$ .

Output：一个可行解 $y'=\left ( y_{1}',...,y_{n} '\right )^{T}$ .

Step 1：如果 y 可行，则设 y'=y 并返回 y'。

Step 2：设 $J=\left \{ j\mid 1\leq j\leq n\ and\ y_{j}= 1 \right \}$ 、
$I=\left \{ i\mid 1\leq i\leq m\ and\ \sum_{j=1}^{n}w_{ij}y_{j}> c_{i} \right \}$
即全部物品的物品号并初始化为1(放进去)，且在此情况下每个背包的重量＞背包容量。

Step 3：选择 $k\epsilon J$ 使得

从 y 中移除第 j 个物品，则 $y^{j-}$ 仅在位置 j 变为0 ，其他的都不改变，即 $y_{j}^{j-}= 0$ ，对于其他所有 $i\neq j$ ， $y_{i}^{j-}=y_{i}$ 。
设 $y_{k}=0$ ，执行【Step 1】。

arg min：使得...达到最小值的自变量值。
在这种方法中，从 y 中一个接一个地删除项，直到 y 变得可行。我们想要找到一个物品 j，移除它后目标函数值的减少量与该物品重量的比值是最小的，并把物品号赋给 k，再让 $y_{k}=0$ ，即移除那些对目标函数贡献较小但重量较大的物品。

2. MOGLS实现

为了进行公平的比较，我们直接使用Jaszkiewicz最新的MOGLS实现用于MOKP，MOGLS与Tchebycheff结合的方法细节如下。

（1） $z= \left ( z_{1} ,...,z_{m} \right )^{T}$ 的初始化：对于每个目标函数 $f_{i}$ ，随机生成一个初始点，应用修复方法到这个随机生成的点上，以产生一个可行的解。设 $z_{i}$ 为结果点的 $f_{i}$ 值， $z_{i}$ 代表了在所有可行解中，目标函数 $f_{i}$ 可能达到的最小值（或至少是一个很好的估计）。
（2）EP和CS初始化：
EP：外部种群，用于存储找到的Pareto最优解或近似最优解。
CS：候选解集，用于在算法迭代过程中存储和评估解。
设EP=∅，CS=∅。然后，重复S次：
        ①生成权重向量
                使用[29]中描述的抽样方法随机生成一个权向量 $\lambda$ 。
        ②生成随机解
                随机生成一个解 $x=\left ( x_{1} ,...,x_{n} \right )^{T}\ \epsilon \left \{ 0,1 \right \}^{n}$ ，其中 $x_{i}=1$ 的概率等于0.5（这假设了背包问题中的二进制决策变量）。
        ③应用修复方法和目标函数
                以 $-g^{te}\left ( x\mid \lambda ,z \right )$ 为目标函数（注意负号，用于将最小化问题转化为最大化问题），将修复方法应用于x，得到可行解 x'。
        ④更新EP和CS
                把 x' 加到CS。从EP中删除所有受 F(x') 支配的向量，如果EP中没有向量支配 F(x') ，则将 F(x') 添加到EP中。
（3）步骤2.1中的遗传算子：单点交叉首先应用于两个解，并生成一个子代解，然后对其应用标准变异操作，生成一个新的解 y。变异以0. 01的概率对子代解的每个位置进行独立变异。
（4）步骤2.2中的启发式：使用本节描述的修复方法将不可行解转换为可行解。

3.MOEA/D实现

我们在步骤2.1中使用与MOGLS实现中相同的遗传算子和步骤2.2中的修复方法。z的初始化也与MOGLS中相同。 $x^{i}$ (第个子问题的初始解)的初始化如下所示。

步骤1.3中 $x^{i}$ 的初始化：以 $-g^{te}\left ( x\mid \lambda^{i} ,z \right )$ 为目标函数，将修复方法应用于随机生成的解。设 $x^{i}$ 为结果解。

在上述MOEA/D和MOGLS的实现中使用了Tchebycheff聚合函数 $g^{te}$ 。
在我们的实验研究中，这两种算法使用加权和方法的实现与Tchebycheff方法的实现相同，只是它们在修复方法中使用 $g^{ws}$ 作为目标，并且不维护 z 。

P.S.若使用加权和的方法

多目标0-1背包问题两个目标：
①最大化总价值 V(x)
②最小化总重量 W(x)
其中，x 是一个二进制向量，表示每个物品是否被选中放入背包中。
在0-1背包问题中，当我们同时面临最大化总价值 V(x)和最小化总重量 W(x)时，为了统一处理这两个目标，我们将最小化目标 W(x)转化为最大化−W(x)。
问题就变成了同时最大化 V(x)和−W(x)，这仍然是一个最大化问题：
①最大化总价值 V(x)
②最大化−W(x)（即“反向”的最小化总重量目标）

加权和方法：
对于加权和方法，我们直接对各个目标进行加权求和。对于包含最小化和最大化目标的问题，我们会对最小化目标取负，以确保整个表达式是最大化的。
因此，目标函数可以写为： $CombinedObjective\left ( x \right )=\lambda _{1}V(x)-\lambda _{2}W(x)$
这里，λ1和λ2是非负权重，分别对应于最大化总价值和最小化总重量的重要性。

E. 参数设置

对于MOGLS中的所有实例，K（临时精英人口的规模）设置为20。S（初始种群规模）在不同实例中的值如表1所示。

对于所有测试实例，MOEA/D中的T设置为10。在MOEA/D中，N 和 $\lambda ^{1},...,\lambda ^{N}$ 的设置由参数 H 控制，更准确地说， $\lambda ^{1},...,\lambda ^{N}$ 是所有权重向量，每个权重从其中取值

因此这样的向量个数为

表1列出了每个测试实例的MOEA/D中 N 和 H 的值。对于具有两个目标的实例，MOEA/D中的 N （权重向量个数、子问题个数）值与MOGLS中的 S （初始种群规模）值相同。
对于所有具有三个目标的实例，H=25，因此N=351。
对于所有具有四个目标的实例，H=12，然后N=455。
值得注意的是，MOGLS的内部种群CS的大小可以达到 $K\times S$ ，远远大于MOEA-D的内部种群。

上述生成MOEA-D权重向量的方法，在我们的实验中效果良好。然而，当目标的数量 m 很大时，它可能导致一个非常大的 N。

两种算法都在修复方法调用 $500\times S$ 次后终止。

在我们的实验研究中， $g^{ws}$ 和 $g^{te}$ 都被用于修复方法。其中，W-MOEA/D (W-MOGLS)表示使用 $g^{ws}$ 的MOEA/D (MOGLS)， T-MOEA/D (T-MOGLS)表示使用 $g^{te}$ 的MOEA/D (MOGLS)。

P.S.权重向量数 $N=C_{H+m-1}^{m-1}$ 的计算过程

给定两个整数m和H，我们需要输出一组均匀分布的权重向量集合，这些权重向量的特点是它们的元素之和为1 ，且元素取自集合 $A=\left \{ \frac{0}{H},\frac{1}{H},...,\frac{H}{H} \right \}$ 。

直接问题：从集合A中选择m个数，使得它们的和为1，即a1+a2+…+am=1
问题抽象：为了简化问题，我们可以将问题转化为从集合 B={0,1,2,…,H} 中选择m个数，使得它们的和为 H，即b1+b2+…+bm=H。
进一步地，我们可以将这个问题再转化为从集合 C={1,2,3,…,H+1} 中选择m个数，使得它们的和为 H+m，即c1+c2+…+cm=H+m，其中 cn=bn+1。
组合解释：和为(H+m)可以看作有(H+m)个球排成一排，共有(H+m−1)个空，选 m个数可以用插板法做，选择其中(m-1)个空隙进行插板，分为m份，所以总个数为 $N=C_{H+m-1}^{m-1}$ 。

F. 实验结果

MOGLS和MOEA/D在同一台计算机上的每个测试实例上都独立运行了30次。由于MOPs的性质，需要使用多个性能指标来比较不同算法的性能。在我们的实验中，使用了以下性能指标。

1.覆盖率(C-metric)

设A和B是一个MOP的PF的两个近似值，C(A,B)定义为B中被A中至少一个解占主导地位的解的百分比，即:

C(A,B)=1表示B中的所有解都被A中的某些解支配，而C(A,B)=0表示B中的所有解都不被A中的某个解支配。
C(A,B)不一定等于1-C(B,A)，这是因为支配关系是不对称的，即A中的解支配B中的解，并不意味着B中的解不能在某些情况下支配A中的解。因此，在评估两个算法的性能时，通常会同时考虑C(A,B)和C(B,A)以获得更全面的评估结果。

2.到PF中代表点的距离(D-metric)

设 P*（PF中代表点）是沿PF均匀分布的点的集合，设 A 是PF的近似值，则 P* 到 A 的平均距离定义为

其中 d(v,A) 是 v 与 A 中点之间的最小欧几里德距离。如果 |P*| 足够大，可以很好地表示PF, D(A,P*) 在某种意义上可以度量 A 的多样性和收敛性。为了使 D(A,P*) 的值较低，集合 A 必须非常接近PF并且不能错过整个PF的任何部分。

D-metric是衡量近似解集A与Pareto Front之间距离的一种性能指标。具体来说，它计算了 P* 中每个点到 A 中最近点的平均欧氏距离。这个距离越小，说明A中的解越接近Pareto Front，并且A在Pareto Front上的覆盖越全面。

在我们不知道实际PF的情况下，我们可以将 P* 设为PF的上近似值。Jaszkiewicz通过用多个均匀分布的 λ 求解(3)切比雪夫的线性规划松弛版本，得到每个0/1背包测试实例的很好上近似值。对于每个双目标实例，上近似值中的点数为202，对于3目标实例为1326，对于4目标实例为3276。在我们的实验中，P* 被设置为这样一个近似。这意味着，尽管不知道真实的Pareto Front，但可以通过这种方法来评估算法生成的近似解集A的性能。

3.实验结果

表II给出了每个算法在每个实例中使用的平均CPU时间。

表III给出了两种算法在两种不同修复方法下得到的最终逼近C-metric值的均值。

表IV显示了每个实例的MOEA/D和MOGLS的D-metric值的平均值和标准差。

图3显示了30次运行中EP从P*开始的平均D-metric（y轴）随每个算法对每个测试实例的修复方法调用次数（x轴）的演变。由于D-metric值的范围很大，我们在图3中使用对数尺度来表示平均D-metric值的坐标轴。

图4和图5绘制了三个双目标实例中每种算法中D-metric值最低的EP分布。

我们可以这样说:

从表II中可以明显看出，在相同的修复方法调用次数（即相同的尝试解数量）下，MOEA/D比MOGLS需要更少的计算时间。平均而言，MOEA/D所需的CPU时间约为MOGLS所需的14%，即MOEA/D的速度是MOGLS的7倍。这一观察结果与我们在第IV-B节中对MOEA/D和MOGLS计算复杂度的分析一致。
图3清楚地表明，对于所有测试实例，无论是使用加权和方法还是Tchebycheff方法，MOEA/D都需要更少的修复方法调用次数来最小化D-metric值，这说明了MOEA/D在解决MOKP问题时比MOGLS更加高效和有效。
表III和表IV显示，在大多数测试实例上，无论是D-metric还是C-metric，MOEA/D（无论是加权和还是Tchebycheff方法）获得的最终解的质量都优于MOGLS。仅有一个实例（250–4）在C-metric上MOEA/D略逊于MOGLS。以实例500–3为例，T-MOGLS生成的最终解中，有90.97%被T-MOEA/D的解所支配，而反之仅有2.42%。
图4和图5的展示了在一些实例上，MOEA/D生成的解集在质量上明显优于MOGLS，尤其是在解集的前沿部分。
表4还显示，MOEA/D在D-metric上的标准差小于MOGLS，表明MOEA/D在解决这些问题时更加稳定。
表4和图3显示，加权和方法在MOEA/D和MOGLS上都优于Tchebycheff方法，这表明不同的MOEA/D和MOGLS分解方法会有不同的性能。

总的来说，MOEA/D在解决多目标背包问题（MOKP）时，不仅在计算效率上远高于MOGLS，而且在解的质量和稳定性方面也表现出色。因此，可以得出结论，MOEA/D是这些MOKP测试实例上更优的算法选择。

五、MOEA/D 和 NSGA-II 对比

A. 多目标连续测试套件

ZDT 测试实例在优化算法，特别是多目标优化算法的评估中扮演着重要角色。它们是一系列标准测试函数，这些测试函数旨在为多目标遗传算法（MOGA）的性能评估提供标准化的测试平台，通过模拟实际工程中的复杂优化问题，来全面检验优化算法的性能。

ZDT测试函数具有以下特点：
①多目标性：ZDT测试函数通常包含两个或更多个需要同时优化的目标函数，这些目标函数之间往往是相互冲突的，即一个目标的改善可能导致另一个目标的恶化。
②多样性：ZDT测试函数集包含多个测试函数（如ZDT1到ZDT6等），每个函数都设计了不同的优化挑战，如不同的帕累托前沿形状（线性、凸形、凹形、不连续等）和复杂度，以全面检验算法的性能。
③挑战性：这些函数的解空间范围通常很大，且包含多个局部最优解，增加了求解的难度，从而能够更好地评估算法的全局搜索能力和解的质量。

以ZDT1为例，它是一个双目标优化问题，其目标函数是线性相关的。在解决ZDT1问题时，算法需要同时优化两个目标函数，以找到它们的Pareto最优解集。这个解集在二维空间中表现为一条曲线（即 Pareto前沿），算法的性能可以通过其找到的解与真实Pareto前沿的接近程度来评估。

在实验中，我们使用了5个广泛使用的双目标ZDT测试实例和2个3目标测试实例来比较MOEA/D与NSGA-II，后者是最成功的非分解 MOEA 之一，所有这些测试实例都是目标的最小化。

ZDT1的PF是凸形的，ZDT2的PF是非凸形的。

ZDT3的PF互不关联，ZDT4有许多局部PF帕累托前沿。

ZDT6的PF是非凸的，帕累托解在帕累托前沿的分布是非常不均匀的，即对于决策空间中帕累托集合中的一组均匀分布的点，它们的图像挤在目标空间帕累托前沿的一角。

DTLZ1的PF是非凸的，且帕累托最优解的函数值满足 $\sum_{i=1}^{3}f_{i}=1\ with\ f_{i}\geq 0$ .

DTLZ2 的PF是非凸的，且帕累托最优解的函数值满足 $\sum_{i=1}^{3}f_{i}^{2}=1\ with\ f_{i}\geq 0$ .

B. NSGA-II

NSGA-II（Non-dominated Sorting Genetic Algorithm II）是一种用于解决多目标优化问题的遗传算法，主要特点在于它不使用外部种群，而是通过一系列高效的步骤来生成和维护一个高质量的种群。

NSGA-II在第一代维持一个大小为N的种群 $P_{t}$ ，并通过以下方式从 $P_{t}$ 产生 $P_{t+1}$ 。
Step 1) 使用选择、交叉和突变从 $P_{t}$ 创建后代群体 $Q_{t}$ 。
Step 2) 从 $P_{t}\cup Q_{t}$ 中选择N个最优解形成 $P_{t+1}$ 。
NSGA-II中每代的计算复杂度主要是由非支配排序过程决定的，为 $O(mN^{2})$ ，其中m为目标的个数，N为其总体大小。

总之，NSGA-II通过结合非支配排序和拥挤距离估计，有效地解决了多目标优化问题中的解选择问题，同时保持了种群的多样性和收敛性。

非支配排序（Fast Nondominated Sorting）：
NSGA-II 使用一种快速的非支配排序算法来将种群中的个体分成不同的前沿（Fronts）。每个前沿中的个体在当前的评估标准下是相互非支配的，即没有一个个体在所有目标上都优于另一个个体。排序过程从最优（即没有任何其他个体能支配它）的个体开始，逐步扩展到较劣的个体。这个过程的时间复杂度为 $O(mN^{2})$ ，其中m是目标数量，N是种群大小。
拥挤距离估计（Crowded Distance Estimation）：
在同一前沿中的个体之间，NSGA-II 通过计算它们的拥挤距离来进一步区分。拥挤距离是基于每个个体周围其他个体在每个目标上的差异来计算的，它反映了该个体周围解的密集程度。拥挤距离大的个体意味着它们周围的解较少，因此更有可能被选为下一代的一部分，以增加种群的多样性。

C. 用于比较的 MOEA/D 变体

为了进行公平的比较，我们在实验中使用了以下MOEA/D的变体。

去除外部种群EP：
在传统的MOEA/D中，外部种群（EP）用于存储当前找到的非支配解，并作为算法迭代过程中精英保留的机制。NSGA-II本身并不使用外部种群，为了比较的一致性，MOEA/D现在直接返回其内部种群作为对Pareto前沿（PF）的近似，不需要【Step 2.5：更新外部种群EP】。
去除修复/改进方法：
在MOEA/D中，有时会引入修复或改进步骤来尝试改善解的质量，特别是在解违反某些约束时。在对比实验中，去除了这一步，因此不需要进行【Step 2.2：改善】。
使用gts而不是gws：
$g^{ts }$ 在【Step 2.4：更新邻域解】中使用，我们不使用 $g^{ws }$ 主要是因为加权和方法无法处理非凸PF。

这些修改使得MOEA/D的变体在算法复杂性和内存需求上与NSGA-II更加相似，从而能够在一个更公平的平台上比较这两种算法的性能。与NSGA-II相比，MOEA/D中唯一额外的内存需求是用于存储 z ，z 的大小为 $O(m)$ ，与总体大小相比非常小，这使得MOEA/D在内存使用上与NSGA-II更加接近。

D. MOEA/D 变体与 NSGA-II 计算复杂度比较

在上述MOEA/D的变体中，主要的计算成本在【Step 2：更新】中。MOEA/D在【Step 2：更新】生成N个试验解，NSGA-II每代生成N个试验解。

【Step 2.2：改善】和【Step 2.5：更新外部种群EP】已经从这个变体中删除。
【Step 2.1：交叉】只是随机选择两个遗传算子的解，算成本相对较低。
【Step 2.3：更新z】执行O(m)个比较和赋值，其中m是目标函数的数量，因为它涉及到对每个目标值的比较。
【Step 2.4：更新邻域解】计算新生成解到T个邻居解的距离 $g^{te}$ 值，计算一个这样的值需要O(m)个基本操作，共需要O(mT)个基本操作。
由于【Step 2：更新】在每次迭代中生成N个新解，因此总体计算复杂度是 $O(mNT)$ 。

如果MOEA/D和NSGA-II使用相同的种群大小，则它们每代的计算复杂度之比为

由于T小于N，每代MOEA/D变体的计算复杂度都低于NSGA-II，这是因为MOEA/D变体通过限制每个新解只与T个邻居解进行比较和更新，减少了整体计算成本。

E. 实验设置

种群大小（N）：对于所有2目标的测试实例，NSGA-II和MOEA/D的种群大小都设置为100；对于其他两个3目标的测试实例，种群大小设置为300。这意味着在搜索过程中，算法会同时考虑多个候选解（个体），以寻找最优解集。
迭代次数：两种算法都运行了250代后停止。每一代代表算法的一次迭代，包括选择、交叉、变异等遗传操作。
初始种群生成：两个算法开始时，会在整个解空间中随机选择一组初始解作为起点。MOEA/D中的 $z^{i}$ 初始化为初始种群中 $f_{i}$ 的最低值。
模拟二进制交叉（SBX）和多项式变异：这两种遗传操作在NSGA-II和MOEA/D中都得到了应用。SBX用于生成新的解（后代），而多项式变异则用于在后代上引入小的随机变化，以增加种群的多样性。
控制参数：
分布指数设置为20。
交叉率设置为1.00，这意味着每个个体都会参与交叉操作。
变异率设置为1/n，其中n是决策变量的数量。
MOEA/D特有的设置：
权重向量（λ）：MOEA/D使用了一组权重向量来指导搜索过程，使其能够同时考虑多个目标。这些权重向量 $\lambda ^{1},...,\lambda ^{N}$ 的设置与第四章-E节中的描述相同。
T的设置：在MOEA/D中，T被设置为20。
实验重复次数：对于每个测试实例，NSGA-II和MOEA/D都独立运行了30次。

F. 实验结果

1. CPU时间

从表V 可以看出，对于相同的函数评价次数，MOEA/D在2目标测试实例上平均运行时间大约是NSGA-II的两倍，而在3目标测试实例上则超过8倍。这表明在处理多目标问题时，MOEA/D在效率上优于NSGA-II，特别是在目标数量增加时，这种优势更加明显。这与在第五章-D节中进行的复杂度分析是一致的。

2. D-metric

D-metric：用于衡量当前种群与理想Pareto前沿（PF）之间的距离。
为了计算D-metric，对于2目标测试实例，选择了一个包含500个均匀分布点的集合P*作为参考；对于3目标实例，则选择了990个点。
当目标函数的求值成本很高时，函数求值的次数很重要。图6 展示了随着函数评价次数的增加，两种算法在D-metric值上的收敛情况。结果显示，在ZDT4、ZDT6、DTLZ1和DTLZ2测试实例上，MOEA/D在减少D-metric值方面比NSGA-II更快收敛，即MOEA/D在函数评估次数方面的收敛速度比NSGA-II快得多；而在其他三个测试实例上，两者的收敛速度相近或MOEA/D稍慢。

3. C-metric

C-metric：用于评估算法找到的最终解集的质量。
表VI 显示，在C-metric上，MOEA/D在所有测试实例（除了ZDT4）上获得的最终解集质量都优于NSGA-II。这表明MOEA/D在大多数情况下能够找到更接近理想Pareto前沿的解集。

表VII 给出了每种算法在各自测试实例上获得的最终解决方案的D-metric值的均值和标准差。结果显示，在D-metric的评估下，MOEA/D在ZDT4、ZDT6以及两个3目标测试实例上获得的最终解决方案优于NSGA-II，而在其他三个实例上则稍逊一筹。

图7 和图8 通过在目标空间中展示每种算法在各自测试实例上D值最低的运行中所获得的最终解决方案的分布，进一步可视化了这一结果。这些图形表明，在解决方案的均匀性方面，MOEA/D在ZDT1、ZDT2、ZDT6以及两个3目标测试实例上表现优于NSGA-II。然而，在ZDT4上，两者的表现大致相当；在ZDT3上，MOEA/D的表现则较差，因为它在PF的两个左端部分找到的解决方案少于NSGA-II。MOEA/D在ZDT3上的不佳表现可能与该测试实例中目标函数的不均匀缩放有关。

从上面的结果我们可以得出结论，对于这些测试实例，使用Tchebycheff方法的MOEA/D比使用相同数量的功能评估的NSGA-II需要更少的CPU时间。在解质量方面，两种算法在2目标测试实例上的性能基本相同，但MOEA/D在2个3目标测试实例上优于NSGA-II。

G. MOEA/D更多努力

在上述实验中，我们使用了一种非常简单的MOEA/D实现，分解方法是经典的Tchebycheff方法，我们没有进行任何客观的归一化。如第二章-C节所述，就解决方案一致性而言，Tchebycheff方法可能比BI方法表现更差，特别是当目标数量超过两个时。众所周知，当目标是不同尺度时，目标归一化对于提高解的均匀性是非常有用的。
回顾图7和图8，在上述MOEA/D实现中为ZDT3、DTLZ1和DTLZ2找到的解决方案在均匀性方面并不令人满意。特别是，ZDT3中的两个目标具有不同的缩放比例，而DTLZ1和DTLZ2则具有三个目标。这引发了两个问题：

使用其他高级分解方法的MOEA/D：MOEA/D与其他高级分解方法(如PBI方法)是否可以为DTLZ1和DTLZ2等3目标测试实例找到更均匀分布的解决方案?
带有目标归一化的MOEA/D：目标归一化的MOEA/D在ZDT3中不同比例目标的情况下是否表现更好?

我们做了一些实验来研究这两个问题。下面，我们报告我们的实验结果。

1. 使用PBI方法的MOEA/D

我们在两个3-objective测试实例上使用PBI方法测试了MOEA/D。在我们的实验中， $g^{bip}$ 中的惩罚因子被设置为5，其他设置与上述小节中使用Tchebycheff方法实现MOEA/D时的设置完全相同。

表VIII 比较了两种不同分解方法下NSGA-II和MOEA/D的平均D-metric值。D-metric是衡量解集均匀性和覆盖范围的指标，值越小表示解集的质量越高。

结果表明，使用PBI方法的MOEA/D在这两个3目标实例上的D-metric值远低于NSGA-II和使用Tchebycheff方法的MOEA/D，表明其解集的均匀性和覆盖范围更优。

图9 显示了采用PBI方法对两个3目标测试实例进行30次独立MOEA/D测试时D-metric值最低的非支配前沿的分布。

与图8相比，图9中的解集在目标空间中分布得更加均匀，且更好地覆盖了Pareto前沿。

综上，在这两个3-objective实例上，采用PBI方法的MOEA/D比采用Tchebycheff方法的MOEA/D表现要好得多。这些结果表明，在求解具有两个以上目标的MOPs时，将其他先进的分解方法纳入MOEA/D是值得研究的。但是采用高级分解方法的MOEA/D可能需要更多的人力，例如，在PBI方法中设置惩罚因子的值。

2. 目标归一化

在接下来的实验中，我们仍然使用Tchebycheff方法，不改变参数设置。然而，我们将一个简单的目标归一化技术结合到MOEA/D中，以讨论在使用多目标进化算法（MOEA/D）处理具有不同量纲（即不同规模或范围）的目标函数时，目标归一化技术能否帮助改善算法的性能。
目标归一化是一种常用的技术，用于将不同量纲的目标函数值转换到相同的尺度上，以便算法能够更公平地处理这些目标，目标归一化问题在数学规划界和进化计算界都做了大量的研究。

一种非常简单的归一化方法是将目标 $f_{i}\, \, \left (i=1,...,m \right )$

其中， $z^{*}= \left ( z_{1}^{*},...,z_{m}^{*} \right )^{T}$ 为参考点，通常是一个理想点，即每个目标都尽可能小的点，与第二章相同。
$z^{nad}= \left ( z_{1}^{nad},...,z_{m}^{nad} \right )^{T}$ 是每个目标都尽可能大的点，即 $z_{i}^{nad}= max\left \{ f_{i}\left ( x \right )\mid x\epsilon PS \right \}$ 。在目标空间中，是Pareto前沿的上界。
这样，每个目标在PF中的范围变为 [0,1]。

事先计算 $z^{nad}$ 和 $z^{*}$ 并不容易，也没有必要。在我们的实现中，我们将 $z^{*}$ 替换为 z，并将每个 $z_{i}^{nad}$ 替换为 $\widetilde{z}_{i}^{nad}$ ，即当前总体中 $f_{i}$ 的最大值。

因此，在使用Tchebycheff方法进行连续MOPs的MOEA/D的【Step 2.4：更新邻域解】中，将 $g^{te}$ 由

替换为

即将内部归一化后再乘以权重。

我们用Tchebycheff方法和上述归一化技术在ZDT3和ZDT1的修改版本上测试了MOEA/D，其中 $f_{2}$ 被 $10f_{2}$ 取代以模拟不同量纲的目标。图10 绘制了改良版ZDT1经归一化和不经归一化的MOEA/D单次运行得到的非支配解。

图11 显示了对ZDT3进行一次MOEA/D归一化后得到的非支配解。

图10 和图11 ，以及NSGA-II和ZDT3未归一化的MOEA/D的解图，清楚地表明，在目标函数量纲差异较大的情况下，归一化技术显著改善了MOEA/D的性能，特别是在解的均匀性方面。

总之，我们对本小节开头提出的两个问题有非常积极的答复。在MOEA/D中使用其他复杂的分解和归一化技术将是我们未来的研究课题。

六、在MOEA/D中可扩展性、灵敏性和小群体性

A. MOEA/D 中 T 的灵敏度

T是MOEA/D的主要控制参数。
为了研究连续和离散MOPs在MOEA/D中性能对T的敏感性，我们在第四节中对背包实例250-2使用加权和方法测试了MOEA/D的不同设置，并在第五节中对ZDT1使用Tchebycheff方法测试了MOEA/D的实现。除T的设置外，所有参数设置均与第四节E和第五节E相同。
如图12 所示，在背包实例250-2上，当T从10到50时，MOEA/D的性能都很好，在ZDT1上，除了很小的T值外，其他所有的T值都很好。
因此，我们可以断言MOEA/D对T的设置不是很敏感，至少对于与这些测试实例相似的MOP来说是这样。这意味着在解决这类问题时，用户不需要过于精细地调整T的值来获得良好的性能。

在图12所揭示的结果中，当T值非常小时，MOEA/D在两个测试实例（背包问题实例250-2和ZDT1）上的表现都不佳。这一现象可以通过第三节B3中提到的观点来解释：当T值过小时，MOEA/D在探索能力上表现不足。
即：当T值非常小时，MOEA/D的子问题权重向量之间的差异会变得非常小，亲本相似，后代也会相似，这导致算法在搜索空间中的探索能力受限，子问题之间的搜索方向变得非常接近，从而难以覆盖整个解空间。

具有大T的MOEA/D在背包实例250-2上效果不佳的事实可以通过我们在第三节B3中的分析来解释，因为在这个实例中，两个具有非常不同权重向量的子问题的解决方案是非常不同的。
具有大T的MOEA/D在ZDT1上表现良好的原因可能是因为即使两个权向量不同，其相关子问题的最优解也非常相似。事实上，除了第一个子问题外，其他子问题的最优解都是相同的。

在离散问题（如背包问题实例250-2）中，如果T值设置得很大，子问题之间的权重向量差异会显著增加。由于离散问题的解空间是离散的，且解之间的转换可能不是平滑的，因此两个权重向量差异很大的子问题可能对应着完全不同的解集。这会导致算法在搜索过程中难以有效地利用相邻子问题的信息，因此，MOEA/D在T值较大时可能在离散问题上表现不佳。
在连续问题（如ZDT1）中，即使两个权重向量不同，由于目标函数和约束条件的连续性，它们对应的最优解可能在大多数分量上都非常相似。这种特性使得MOEA/D在T值较大时在连续问题上仍然能够有效地利用相邻子问题的信息，并通过权重向量的变化来引导搜索过程，从而找到高质量的全局最优解。

B. 使用小规模种群的MOEA/D

如第一节所述，决策者可能不希望在高计算成本下拥有大量的帕累托最优解，他们通常对以低计算成本获得少量均匀分布的解决方案感兴趣。在下面，我们将展示使用小种群的MOEA/D可以得到帕累托最优解。

我们以ZDT1为例，在第五节中使用MOEA/D和Tchebycheff方法。除了总体大小N=20，其他参数设置与第五节相同。为了比较，我们还在ZDT1上运行N=20的NSGA-II，两种算法在250代之后停止，如第五节所示。

图13 为N=20时，NSGA-II和MOEA/D单次运行得到的最终解。很明显，MOEA/D找到了20个分布非常均匀的Pareto解，而NSGA-II未能在给定的代数内达到PF。MOEA/D的这种优势来自于它的分解策略。

C. 可扩展性

为了研究函数评估次数的计算成本如何随着决策变量数量的增加而增加，我们在具有不同决策变量数量的ZDT1上，尝试了除最大生成次数为1000（即函数评估最大次数为100*1000=10^5）外，参数设置相同的第五节C中MOEA/D的变体。我们发现，在每个决策变量数量的30个独立运行中的每一次运行中，MOEA/D都将D-metric值降低到0.005以下，因此根据我们在第5节中的经验，最终解非常接近PF。图14 给出了具有不同决策变量数量的ZDT1用于将D-metric值降低到0.005以下的函数评估的平均次数。很明显，随着决策变量数量的增加，函数评估的平均次数呈线性增长。

在这个测试实例中，MOEA/D的线性可扩展性应该是由于两个事实：
1)子问题数量固定：无论决策变量有多少，MOEA/D的标量优化子问题的数量都固定为100，不需要随着决策变量的增加而增加，因为MOP的内在维数是由目标的数量决定的，而不是决策变量的数量。
2)单个优化复杂度：各标量优化的复杂度随决策变量的数量呈线性增长。这是因为随着决策空间的增大，找到最优解所需的搜索空间也相应增大，从而增加了计算成本。

七、结论

分解是求解MOPs的传统数学规划方法中广泛使用的一种方法。相比之下，大多数MOEA将MOP视为一个整体，并且在搜索过程中主要依靠支配来衡量解决方案的质量。这些算法可能不太擅长生成沿PF均匀分布的解。

本文提出了一种简单通用的基于分解的进化多目标优化算法MOEA/D。首先采用分解方法将MOP分解为若干标量优化问题。然后，利用EA同时优化这些子问题。MOEA/D总体中的每个单独的解决方案都与一个子问题相关联,根据子问题权向量的距离定义子问题间的邻域关系。在MOEA/D中，子问题的优化使用其相邻子问题的当前信息，因为两个相邻子问题应该具有接近的最优解。我们分别在多目标背包问题和连续多目标问题上比较了MOEA/D与MOGLS和NSGA-II。

我们的分析表明，MOEA/D的计算复杂度低于MOGLS和NSGA-II，实验结果也证实了这一点。在解的质量方面，在大多数测试实例上，采用简单分解方法的MOEA/D优于MOGLS和NSGA-II，或者性能与MOGLS和NSGA-II相似。我们已经证明，在两个连续的3目标测试实例上，使用PBI方法的MOEA/D能够在PF上生成具有代表性的Pareto最优解的非常均匀的分布。我们还证明了采用朴素目标归一化技术的MOEA/D可以很好地处理不同尺度的目标。

即：
1)低计算复杂度：与MOGLS和NSGA-II相比，MOEA/D具有较低的计算复杂度，这得益于其分解和并行优化的策略。
2)良好的解质量：在大多数测试实例上，MOEA/D使用简单的分解方法时，其解的质量要么优于，要么与MOGLS和NSGA-II相当。
3)均匀的解分布：MOEA/D能够生成在PF上非常均匀的代表性Pareto最优解分布，这对于实际应用中的决策制定非常重要。
4)处理不同规模目标的能力：通过简单的目标归一化技术，MOEA/D能够有效处理目标尺度差异大的问题。

这些结果表明，只要付出更多的努力，MOEA/D可以得到更有效的实施。

我们通过实验研究了MOEA/D的可扩展性和对邻域大小T的敏感性。我们发现计算成本随着决策变量的数量呈线性增长，并且MOEA/D对T的设置不太敏感。我们还表明MOEA/D擅长以低计算成本找到少量均匀分布的Pareto解。

将数学规划方法与进化算法相结合，在标量优化问题中已取得了巨大成功。本文的工作为将长期研究于数学规划领域的分解策略引入到进化算法中，用于多目标优化，提供了一种非常自然的方式。未来，随着分解策略和其他标量优化技术的发展，可以更容易地将它们集成到MOEA/D的框架中，以进一步提高其效率和效果。

标签：进化,算法,目标,问题,MOEA,向量,MOGLS
From： https://blog.csdn.net/ekili/article/details/140779573

基于分解的多目标进化算法MOEA/D

Abstract

索引术语

一、介绍

1.MOP

（1）定义

（2）解释

（3）决策空间和目标空间

（4）连续MOP

2.Pareto最优解

（1）定义

（2）解释

（3）帕累托集合和帕累托前沿

（4）近似PF

3.聚合函数

4.适应度

（1）引入

（2）适应性评估（Fitness Assignment）的重要性

（3）流行的适应性评估策略

（4）其他增强技术

5.MOEA/D

二、三种MOPs的分解方法

A. 加权和法

B. 切比雪夫法

C. 边界交叉法BI

三、基于分解的多目标进化算法MOEA/D

A. 总体框架

1. 问题分析

2. MOEA/D每轮保持的数据

3. 算法工作流程

B. 讨论

1.MOEA/D 中考虑有限数量子问题的原因

2.如何在 MOEA/D 中保持多样性

3.MOEA/D 中的交配限制和T 的作用

C. MOEA/D的变体

1. 不同的分解方法

2. 子问题更新策略

3. 外部种群（EP）

四、MOEA/D 和 MOGLS 对比

A. MOGLS

B. MOEA/D和MOGLS的复杂度比较

1. 空间复杂度

2.计算复杂度

C. 多目标0-1背包问题

D. MOEA/D和MOGLS在MOKP(多目标0-1背包问题)中的实现

1. 修复方法

2. MOGLS实现

3.MOEA/D实现

P.S.若使用加权和的方法

E. 参数设置

F. 实验结果

1.覆盖率(C-metric)

2.到PF中代表点的距离(D-metric)

3.实验结果

五、MOEA/D 和 NSGA-II 对比

A. 多目标连续测试套件

B. NSGA-II

C. 用于比较的 MOEA/D 变体

D. MOEA/D 变体与 NSGA-II 计算复杂度比较

E. 实验设置

F. 实验结果

1. CPU时间

2. D-metric

3. C-metric

G. MOEA/D更多努力

1. 使用PBI方法的MOEA/D

2. 目标归一化

六、在MOEA/D中可扩展性、灵敏性和小群体性

A. MOEA/D 中 T 的灵敏度

B. 使用小规模种群的MOEA/D

C. 可扩展性

七、结论

相关文章

赞助商

阅读排行