论文链接：MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition
参考博客：
【1】MOEAD_qq_37780048的博客-CSDN博客_moead
【2】https://blog.csdn.net/sinat_33231573/article/details/80271801
【3】进化计算（八）——MOEA/D算法详解Ⅱ_南木长的博客-CSDN博客，MOGLS和MEA/D算法的比较
【4】进化计算（七）——MOEA/D算法详解_南木长的博客-CSDN博客_moead算法
【5】一种基于分解的多目标优化算法 MOEA/D
【6】MOEA/D 三种分解方式的理解
【7】MOEA/D 算法详解_一条菜鸟鱼的博客-CSDN博客_moea算法
【8】进化计算（九）——MOEA/D代码实现及中文详解（Matlab）南木长的博客-CSDN博客进化算法代码
【9】如何理解MOEAD 算法？ - 知乎 (zhihu.com)
【10】基于分解的多目标进化优化MOEA/D三种聚合函数的理解 - Vae永Silence - 博客园 (cnblogs.com)
还阅读了一本书：郑金华、邹娟老师写的《多目标进化优化》，书中详细的介绍了多目标优化算法中的许多细节。
关于什么是多目标优化的小白笔记：多目标优化算法_小白笔记 - 简书 (jianshu.com)
！！论文中第二节介绍了MOPs的三种分解方法。第三节介绍MOEA/D。第四节和第五节比较了MOEA/D与MOGLS和NSGA-II，并表明MOEA/D优于或表现类似于MOGLS和NSGA-II。第六节对MOEA/D进行了更多的实验研究。
一、多目标优化分解 DECOMPOSITION OF MULTIOBJECTIVE OPTIMIZATION
有几种方法可以将PF的近似问题转换为许多标量化问题，在文章中介绍了三种方法。
A：加权和方法 Weighted Sum Approach
这种方法考虑了不同目标的凸组合，我们可以看看下面的公式，其中是一个权重向量，
是i从1-m，然后得到下面的标量优化问题的最优解。论文中的公式：
其中f(x)表示目标函数。两个向量相乘表示向量的内积或数量积，几何含义为一个向量在另一个向量的映射。
如图所示，图中有两个目标f1 和f2，灰色的部分就是x。我们现在仅观察f1，f1的权重向量为λ。那么λf1的几何意义就是f1上的点向λ作垂线，也就是图中的很多平行线，又被叫做是等高线*。加权和方法需要找的是从原点到垂直点的最短距离。我们可以看到，如图所示A点在λ上的投影距离是最短的。此时我们再看f2，从f2向λ方向做投影，在经过A点的时候，此时原点到垂直点的最短距离，也是A点在λ上的投影距离是最短的。拓展到更高的维度上也是一样的，我们调整λ的方向，最终能够获得所有帕累托前沿面（FP）上的点。也就是图中的绿色曲线。
论文中提到最大值，但实际上是求整个帕累托前沿面，为了生成一组不同的帕累托最优向量，可以在上述标量优化问题中使用不同的权重向量。如果PF是凹的（在最小化的情况下是凸的），这种方法可以很好地工作。然而，在非凹PF的情况下，并不是每个帕累托最优向量都可以通过该方法获得。也有一些其他的方法来克服这些缺点，例如ε-约束。
B：切比雪夫方法 Tchebycheff Approach
在这个方法里面标量优化问题的定义如下：
其中
如果还不能理解，可以说有点像神经网络中的梯度下降，经过一个批量（batch）过后，我们通常会求这个批量的平均损失loss，此时，我们将平均函数变成求最大值函数，那么其思想和切比雪夫方法类似，如果最大的损失都收敛了，那么其他样本的损失也都收敛。整个损失函数也就是收敛到了一个较小的值。
这是我看到的较为好理解的解释了，将坐标系变换之后，他和加权和方法有一定的类似。但是加权和方法使用的是求和操作，而切比雪夫方法使用的是求最大值的操作。如果从向量内积的几何意义投影的角度来看的话，例如λ向量的上方，我们可以画λ向量在f1向量上的投影，然后我们需要寻找f1上原点到垂直点之间的最短距离。图片中展示的是寻求最小值的情况，最终会收敛到黄色的点。随着λ方向的变化，使用切比雪夫方法最终能够寻找出帕累托前沿面（PF）上的所有解。
可以通过改变权重向量来获得不同的帕累托最优解。这种方法的一个缺点是，对于连续的MOP，其聚合函数并不平滑。然而，它仍然可以用于本文提出的EA框架中，因为我们的算法不需要计算聚合函数的导数。
C：边界交叉方法
最近的几种MOP分解方法，如法线边界交集法和归一化法线约束法可以被归类为BI方法。它们是为连续MOP设计的。在某些正则性条件下，连续MOP的PF是其可达到目标集的最右上边界的一部分。
几何上，这些BI方法旨在找到最顶部边界和一组线的交点。如果这些线在某种意义上是均匀分布的，则可以预期所得交点提供了对整个PF的良好近似。这些方法能够处理非凸PF。在本文中，我们使用了一组从参考点发出的线。数学上，我们考虑以下标量优化子问题。
其中的λ和z就是上面所提到的权重和参考点。
式子中等式约束其目的是为了保证F(x)位于权重向量λ的方向上，通过减小d来使算法求出的解逼近PF。但该条件不太容易实现，故将其改进为基于惩罚机制的边界交叉法（penalty-basedboundary intersection approach）。
θ是预设的惩罚参数，y点是F(x)在L线上的投影，d1在图中的意义为y和z之间的距离。d2是F(x)和L之间的距离（即，y和F（x）之间的距离）。如果θ选取的合适，那么上述公式就会和普通的BI算法的公式十分接近。后面将会称这种方法为PBI（基于惩罚机制的边界交叉法）方法。
边界交叉法的核心思想在于缩短理想点 z与 实际点或者说个体 M 之间的距离。就是如果不把解放在权重方向的向量上，就必须要接受惩罚，距离权重方向越远，受的惩罚越大，以此来约束算法向权重向量的方向生成解。
见名知意, PBI的精髓在于其加入了惩罚机制。 该惩罚机制在实际点距离理想点越远时惩罚力度越大(实质上也是迫使点更快趋近理想点), 与深度学习中的基于学习的SGD类似, 能够根据不同的实际情况来增大或缩小 学习率。
相较于切比雪夫方法，PBI方法或者说一般的BI方法有如下优点：
- 在两个以上目标的情况下，假设PBI方法和Tchebycheff方法都使用相同的均匀分布权重向量集，PBI中得到的最优解应该比Tchebycheff方法获得的最优解分布得更均匀，特别是当权重向量的数量不多时。
- 如果x支配y，g(x) == g(y)依旧是可能的，即使这对于PBI或者BI方法来说是罕见的。
当然这样的设计也是有弊端的，因为我们必须设置惩罚因子，也就是θ，总所周知，过大或者过小的θ都会降低惩罚方法的性能。
上述方法可用于将PF的近似分解为多个标量优化问题。
大量均匀分布的权重向量通常会导致一组帕累托最优向量，这些向量可能不会均匀分布，但可以很好地逼近PF。
文献中有许多其他分解方法也可以用于我们的算法框架。因为我们的主要目的是研究算法框架的可行性和效率。在本文的实验研究中，我们只使用了上述三种分解方法。
二、基于有分解的多目标优化的框架结构 THE FRAMEWORK OF MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION (MOEA/D)
A：总体框架
本文提出的基于分解的多目标进化算法（MOEA/D）需要对所考虑的MOP进行分解。任何分解方法都可以达到这个目的。在下面的描述中，我们假设采用了切比雪夫方法。当使用其他分解方法时，修改以下MOEA/D非常简单。
设λ是一组偶数传播权重向量，z是参考点。正如我们前面所提到的，PF的近似问题可以通过使用切比雪夫方法分解为标量优化子问题，第n个子问题的目标函数为。
在一轮的MOEA/D算法迭代中同时最小化这些目标函数。
请注意是关于连续的λ的，如果
接近
的话，那么
也会接近
。这就是MOEA/D的主要机制，相邻的权重向量有助于帮助多目标优化。
在MOEA/D中，权重向量被定义为几个最接近的向量集合
。第i个子问题的邻域由权重向量来自邻域的所有子问题的λ组成。总体由迄今为止为每个子问题找到的最佳解决方案组成。在MOEA/D中，仅利用其相邻子问题的当前解决方案来优化子问题。
在每一代中，使用切比雪夫方法计算的MOEA/D为：
- 一共有N个输入点
,
是第i个问题的当前解。
-
，
是
- z是迄今为止对目标发现的最优解
- 外部种群（EP），被用作存储在搜索的过程中的非支配的解决方案。
整体的算法工作如下：
输入：
- 确定多目标优化（MOP）问题
- 算法终止条件
- N: 考虑将MOEA/D问题分解为多少个子问题
- 均匀分布的N个权重向量：
- T: 每个邻域中权重向量的个数 (圈的大小)
输出：EP，（即外部种群，存储非支配的解决方案）
第一步 step1：初始化 Initialization
- 设置一个EP，空集
- 计算任意两个权重向量的欧几里得距离，然后计算出与每个权重向量最接近的T个权重向量。设置集合
,
，是最接近
的T权重向量。
- 随机的或者通过特定问题方法，生成一个初始种群
- 通过特定问题方法初始化
（因为z*难以计算，所以作者使用了特定的方法）
第二步 step2：更新 Update
开启循环 1 - N：
-
基因重组：随机的从 B(i) 中选择两个索引：k，l; 然受将
通过遗传操作子产生一个新的解y
-
改进：应用特定于问题的修复/改进启发式方法，得到
。（这是为了防止
不满足约束条件）
-
更新z：for j in range(1,m): if
-
更新邻居解决方案：for j in B(i): if
-
更新EP：删除EP中所有被向量
支配的向量，并将其加入到EP集合中。
第三步 step3：停止标准 Stopping Criteria
- 如果满足停止条件，则停止并输出。否则，转至步骤2。
B：几个讨论 Discussions
- 为什么子问题只有有限个：MOEA/D预先生成N个权重向量，构成N个子问题，针对每个子问题的计算复杂度基本相同。而MOGLS为了力求优化所有可能的聚合函数，在每次迭代时随机生成权重向量。实际上，决策者通常只需要有限个均匀分布的Pareto解。因此，为了减少计算资源的浪费，选取有限的子问题是合适且有必要的。
- MOEA/D采用什么方法保留种群多样性：针对非分解优化算法是在选择机制中使用拥挤距离等算法保留种群多样性，但是这种算法不易生成均匀分布的Pareto最优解。在MOEA/D算法中，当前种群的不同解与不同子问题相关，显而易见的，子问题的多样性会影响种群多样性。因此，只要正确选择分解方法和权重向量生成合适的子问题，MOEA/D算法就会在【各个子问题都能被较好优化的情况下】生成一组在PF上均匀分布的最优解。
-
交配限制和T邻居个数）的选择：
交配限制:MOEA/D算法中，只使用当前子问题的T个邻居子问题来优化当前解。也就是说，只有两个解属于两个邻居子问题，它们才有可能交配。
T的选择：T太小，子代解和父代解会十分接近，从而使得算法缺乏探索其他搜索区域的能力；T太大，生成算子的两个输入解性能会很差，从而导致子代解性能也很差，影响算法的搜索能力。此外，T太大也会在更新邻居解步骤时产生较大的计算复杂度。
MOEA/D的变体
- MOEA/D算法可以使用任意的分解方法。使用加权和算法时不需要参考向量z。
-
或者
作为目标函数进行启发式优化。如果通过基因重组就能生成可行解，也可以省略改善这一步。
- 是否使用外部种群EP也是可选的。如果没有EP存储非支配解，也可以返回最后的内部种群作为PF的近似解。其他较为复杂的更新EP的策略也可以很容易地引入MOEA/D算法框架。
- cMOGA也可以看作是基于分解的进化算法。本质上，它也是使用邻居关系来约束交配。和MOEA/D算法的不同点在于为生成算子选择解以及更新内部种群这两个步骤。在cMOGA算法中，为了处理非凸PF，需要在每一代将EP中的解插入到内部种群中（因为cMOGA算法使用加权和分解方法且它没有在内部种群中保存迄今为止每个子问题的最优解的机制）。
